Notes for Lecture 2 - Tuesday September 7th, 2004
Return to the main StudentFrontPage.
- Scribe = Frances Haugen
- Editor = Mel Chua
- Editor = Katie Rivard
- Editor =
- Editor =
Contents
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.
- Paramaters are the names that are bound to the arguments inside the procedure.
- Arguments are the things that are passed to the procedure.
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
- Everything is an expression
- Everything has a value
- We use the returned value instead of modifying past values (mutation)
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:
- In functional programming, there is
- No enforcement of contract/ADT
- No mutation
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
- Scheme only has one assignment, "define".
Lisp would work fine with if and begin even if it didn't have cond, but cond makes the code look cleaner.
- In this version of Scheme(PLT), you can use square or round brackets (because it is easier to match differnt-shaped brackets) but square brackets are not universal while round brackets are.
- If, cond, and define are called special forms because they have special evaluation rules.
eq? asks, are my arguments the same? = is the numeric equality. eq? should work on small numbers, but I am not confident that eq? will work on fractions, because a fraction could be 1/2 or .5, and it might not consider it to be the same thing. eq? is are they the same identical object -- the same piece of memory. = is only for numbers and asks if they are the same value. eq? and = are regular procedures. For instance:
> (= 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
We have everything we need to write any program. With the exception of mutation, we have everything that is in lisp or can be built in lisp. There are other alternative syntaxes, like let, that can be built out of lambda, but they're mostly just a shorthand.
Abstract Data Types
Two abstract data types are stack and queue. === Stack ===
- A stack is a data structure with several methods
empty? stack - Is the statck empty?
push element stack - add things onto the stack
top stack - peek at the first element - returns an element
pop stack - pops(removes) the top element from the stack, and returns the new stack.
- A stack is a data structure with several methods
(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.
(define push (lambda (elt stac) (cons elt stac)))
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)
- As the size of your problem grows, how much more "expensive" does the solution get? For instance, if I feed a function 100 items and it takes x seconds, how much longer will it take the same function to do 200 items? (x, x^2...)
- We have a notation for this called O(n) (O stands for "on the order of.")
f(n) is 0(g(n)) if f(n) =< k g(n) for all n > some n_{0}.
In order of decreasing efficiency...
- Order(1)
- Order(log n)
- Order(n)
- Order(n log n)
- Order(n^2)
- Order(2^n)
There are a couple other things like Big O.
- Theta(n) - tight bound (exactly n steps)
- Omega(n) - bound below (greater than n steps)
- O(n) - bound above (less than n steps)
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
- Implement/play with implementing a queue in Scheme. Before you do this, you'll probably want to try to build some procedures that do the following things:
- Counts elements in a list (cdr down the list)
+1 to each number -> list incremented (ie make (1 2 5 4) into (2 3 6 5))
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.