[FrontPage] [TitleIndex] [WordIndex

Notes for Lecture 2 - Tuesday September 7th, 2004

See also CodeSeptember7, which contains the stack code from this lecture in a format suitable for insertion into a scheme buffer (but not as much explanation as is here). Also, that page has a second, more refined example of the stack abstraction.

Note: Abstract Data in Scheme vs Java/Python

The difference between abstract data types in Scheme and Java/Python lies in that Scheme is not an object oriented langage. In an object oriented language, all methods of an abstract type are attached to objects of that type -- you would call push on a stack object. In Scheme, they're not (necessarily) attached -- you would call push and give the stack as one of the procedure's arguments.

Stuff We Know About Scheme

We all learned about define, which creates a new entity. Most importantly, define gives something a name.

People have a tendancy to get confused by the difference between define and lambda.

 (define <name> <expression>)

define does NOT create a procedure; it gives something a name. (Angled brackets mean "put something real here")

(lambda (<paramaters>) <expressions of the body>)

Lambda makes a procedure. Lambda doesn't evaluate the arguments, it just stores the expressions in a box to be used later on.

Since we tend to define procedures often, there is a shortcut:

(define (<name> <param list>)
  <expressions of the body>

There is an invisible lambda in the expression above. Note the difference between the following definitions:

(define empty?  ; creates new procedure named empty? using lambda
  (lambda (stack)
    (null? stack)))

(define (empty? stack) ; same as last function - lambda just not explicit, but it's there
  (null? stack))

(define empty? null?) ; gives you the same result as last two, but sets `empty?` equal to the `null?` procedure instead of creating new procedure

Sometimes you define things that return a procedure; in this case, the "long way" definition will have two lambdas; the short way will still have two, but only one is visible.

In scheme, a procedure can be used anywhere that any other piece of information could be used. This means that they can be passed to procedures, returned from procedures, be saved away for later, etc -- we say that in Scheme, procedures are first class. This means you can do a lot of nice things. You can write code where part of the code gets applied later. You can sortof do this with Java (with Runables). There is a Paul Graham essay about why you would want to use Lisp. I will handout something on this later. Other languages have parts of lambda functionality, too -- notably Python.

For example, you know that there will be code that generates buttons, but you don't know which buttons you'll need, so you could pass in the code you'll need at the time. Dynamically loaded Runnables (like in Java) could possibly do this as well, but it would be harder.

Lisp, however, is not the answer to everything. Lisp is a good tinkering language and sometimes a good production language, but Lisp doesn't run as fast as many other languages. If you need to have your code run very fast, you often re-write the critical section (the most time-intensive part) in a fast language like C. The speed of Lisp probably won't be an issue in this class.

Lisp is what it is because it is a minimal math based language. The are suprisingly few fundamental building blocks -- what you really need to make the language work. In addition to define and lambda, we also have two conditionals(though you really need only one)

(if <test> <then> <else>)

It always evaluates the <test> and then the <then> or <else> if <test> is true or false, respectively.

(cond (<test 1> <consequent 1a> <consequent 1b> ...)
      (<test 2> <consequent 2> ...)
      ...
      (else <consequent else>))

This is really just a compound if expression. The big difference between cond and if is that if only tests one thing. It is possible to have embed a lot of ifs to get the effect of a cond, but cond is much cleaner to read because things aren't tabbed as far.

In cond, you can have muliple consequences for each test, which can be very useful in debugging -- just have the program print output to the screen before carrying on with the program. Scheme will throw away all the consequent results except the last consequent (which it returns).

An equivalent way to do this multiple-expression thing is to use a begin:

(begin <expression 1> <expression 2>... <expression n>)

As with the consequents in cond, begin executes all the expressions, and returns the result of the nth expression.

Note: What is functional programming?

Most popular languages today(C, Java, Python) are procedural languages. There is another kind of programming called functional programming, in which

This can be an advantage/disadvantage. On the plus side, since objects never change, backtracking -- going back to a previous solution -- is very easy. However, classical styles of concurrent programming become very difficult, and you need to be careful when there are multiple threads of control.

Lisp is a functional programming language which has been extended to include some mutation to make it easier to use. In this class though, we should avoid using mutation, and code in a functional style.

Differences between object-oriented and functional programming:

Sometimes you want to use a functional style even if the language is object oriented.

Lisp does all its own memory allocation and garbage collection.

More Scheme Syntax Notes

> (= 3 3)
#t
> (eq? 3 3)
#t
> (= 'a 'a)
ERROR: expects type <number> as 2nd argument, given: a; other arguments were: a
> (eq? 'a 'a)
#t
> 

The cons cell: Lisp's data structure

A cons cell looks like this: ->[ ][ ]

This is an object reference. It's like a label name. You're sticking the label on the object. You always hold it by the pointer; you can't get ahold of the box part. You can ask, what's in the first cell, what's in the second cell using first and rest, but the historically authentic names are CAR(current address register) and CDR(current decrement register).

(cons 1 2)

makes the picture -> [ 1 ] [ 2]

(cons 1 (cons 2 '()))

makes the picture -> [ 1 ][->] [ 2 ][/]

The first box contains a value, the second box points to the next object in the list or terminates the list. A list is just a series of cons cells.

When you are uncertain of what you just built, you might want to draw a picture.

If you are curious what is in the CDR of what you just built:

(cdr (cons 1 (cons 2 '())))

It will return [2][/].

Things are displayed as (<car>.<cdr>). In lisp, you rarely use cons cells that have actual values in the CDR. You either put another reference or a null. The [1][->] [2][/] format is very extendable because you can just add more references along the line.

You might think that [1][->] [2][/] might display as (1.(2.())), but it really displays as (1 2) because lisp is optimized for making printed lists look prettier.

 (cons 1 (cons 2 '()))

 prints as:

 (1 2)

'<expr> or (quote <expr>) is the opposite of printing. It means "give me the thing that would print as the following expression".

If we do an eq? between these two forms, it would not equate them.

'(1 2)
prints as:
(1 2)

'(1.2)
prints as
(1 . 2)

'(1.(2.()))
(1 2)

Note: Nothing in the quoted expression will be evaluated.

If I want to make a list, in addition to just quoting it, I can use list to create the right number and format of cons cells:

(list 1 2)

gives
(1 2)
or
( 1 . ( 2 . () ) )

'x is the same as (quote x). When I write ', it is turned into a (quote <expression>) form.

'(quote x)
prints as:
'x

(car '(quote x))
prints:
quote

because '(quote x) is a list with quote in the first box and x in the second box.

Example

>(define x '(1 2))
>(car x)
1
>(cdr x)
(2)

1 is returned from car because x is only one cons cell. The first box is 1 and the second box is pointing at another cons cell [2][/]. As a result, (cdr x) returns a list (2 nil).

Everything in Lisp is stored internally as a cons form. The cons cell is the only data structure in lisp.

Scheme: Now you know

Abstract Data Types

(define empty?         // defines the empty? function
  (lambda (stack)
    (null? stack)))

(define (empty? stack) // defines the empty? function with a hidden lambda
   (null? stack))

(define empty? null?)  // binds the symbol `empty?` to the procedure `null?`

The first and second are identical (it is an example of syntaxical sugar, it makes it easier to read). Because the first two have a lambda within them, they create a new procedure. The third does not. It just uses a previously defined procedure.

Contract of "push" is adding the object to the top of the stack. (Note that we don't have to call our stack "stack" -- just be consistent with your own code)

 > (define es '())
 > (push 'foo es)
 (foo)
 > es
 ()
 > (define new-stack (push 'foo es))
 > new-stack
 (foo)

Note that in order to have the new stack, you have to hold on to the return value of the modifying procedure, and not the stack you passed to the procedure.

let takes a rather weird syntax.

(let ((<name> <expression1>)
     (<name> <expression2>)
     ...   ) ;; this binds each name to an expression, within the body.
     <body-expressions>)     

Its as if you had called a procedure, with expression1 and expression2 as the arguments for the procedure. Inside of the let, you can call the names instead of the expressions themselves. This temprorarily binds things to the names.

Now we'll see a stack implementation that takes advantage of Lisp's functional programming-ness.

(define stack-eg
   (lambda (stack)
     (let (( tmp (read))) ;; read -- reads a "word" from the user
      (display stack) ;; display -- print to the screen
      (newline)
      (if (eq? tmp 'end)
        stack
        (stack-eg (push tmp stack))))) ;; call self again with new stack -- just keep pushing input into the stack

> (stack-eg '())
Input: this is another test of how the stack works end
()
(this)
(is this)
(another is this)
(test another is this)
(of test another is this)
(how of test another is this)
(the how of test another is this)
(stack the how of test another is this)
(works stack the how of test another is this)
>

How to define pop:

(define pop
 (lamda (stack)
  (cdr stack)))

(define top
  (lambda (stack)
   (car stack)))

Note/Concept Intro: How expensive are these actions computationally? (Big O)

In order of decreasing efficiency...

  1. Order(1)
  2. Order(log n)
  3. Order(n)
  4. Order(n log n)
  5. Order(n^2)
  6. Order(2^n)

There are a couple other things like Big O.

complexity: (Big-O notation, expensiveness of calculations) http://en.wikipedia.org/wiki/Big_O_notation

Why do we care? We want to find an approximation for the running time (say) of a function which is close to the actual behavior. We can always over-estimate how long it will take to finish the computation (say it's a 2^n instead of n; you know not to feed it too much data.)

1 cons is 1 unit of computation

Example: How long it takes to push or pop is not effected by the size of the stack, because most of the stack isn't touched. Stack push/pops are O(1) (constant time).

Queue

(empty? q) -> boolean
(enq elt q) -> q w/element attached - enqueue's the element
(front q) -> element in q that's the oldest
(deq q) -> q with oldest element removed

Queue is "British" for line. The first person who got in line is the first person to get on the bus. A stack is a pile of cafeteria trays.

A Queue: Hop on ->[4][3][2][1] -> hop off.

Homework for next time

Do not spend more than an hour on the queue abstract data type. Note: you can use "length" but you likely won't learn as much as you would by exploring the structural nature of the system.


2013-07-17 10:43