Scheme Notes

Constructs

Define a variable

(define pi 3.14159)

cond

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

cond can also be used with else:

(define (abs x)
  (cond ((< x 0) (- x))
        (else x)))

if

(if (predicate) (consequent) (alternative))

Example:

(define (abs x)
  (if (< x 0)
      (- x)
      x))

Logical composition operations

(and (e1) ... (en)) # value of the last one is returned if all are true
(or (e1) ... (en)) # first value that's true is returned
(not (e))

lambda

lambda is used to create procedures in the same way as define, except no name is specified for the procedure:

(lambda ((formal parameters)) (body))

(lambda (x) (+ x 4))

The only difference is that the procedure has not been associated with any name in the environment. In fact, they are equivalent:

(define (plus4 x) (+ x 4)) ~ (define plus4 (lambda (x) (+ x 4)))

And a lambda is used anywhere a defined procedure can be used:

(plus4 4) ~ ((lambda (x) (+ x 4)) 4)

let

Another use of lambda is in creating local variables in procedures.

(let (((var1) (exp1)) # (var1) have the value (exp1), etc, in the body
      ((var2) (exp2))
      ...
      ((varn) (expn)))
     (body))

A let expression is simply syntactic sugar for the underlying lambda application:

((lambda ((var1)...(varn))
    (body))
 (exp1)
 ...
 (expn))

~

(let (((var1) (exp1))
      ...
      ((varn) (expn)))
     (body))

Furthermore, the scope diagrams below make it clear that the values of the bound variables are calculated outside the scope of the variables themselves (the body of the let).

Debugging

Printing a session transcript with a trace

(transcript-on "lab1")
(load "pigl.scm")
(pigl ’scheme)
(trace pigl) ;;; you can specify which procedures to trace
(pigl ’scheme)
(transcript-off)
(exit)

After the above commands, you'll find a file, lab1, with the transcript.

Pairs

;;; Construct a pair
(define x (cons 1 2))`

;;; Extract first part of a pair
(car x) ;;; 1

;;; Extract second part of a pair
(cdr x) ;;; 2 

Lists

Three constructors:

• list: It takes any number of arguments, each of which can be anything, and returns a list containing those arguments as its elements:

> (list ’(a list) ’word 87 #t)
((a list) word 87 #t)

This seems very straightforward, but in practice it’s not the most useful constructor, because it can be used only when you know exactly how many elements you want in the list. Most list programming deals with arbitrary sequences, which could be of any length. List is useful when you use a fixed-length list to represent an abstract data type, such as a point in three-dimensional space:

(define (point x y z)
  (list x y z))

• cons: adds one new element at the front of an existing list:

> (cons ’(new element) ’(the old list))
((new element) the old list)

(Of course, cons really just takes two arguments and makes a pair containing them, but if you’re using that pair as the head of a list, then the effect of cons in terms of the list abstraction is to add one new element.) This may seem too specific and arbitrary to be useful, but in fact cons is the most commonly used list constructor, because adding one new element is exactly what you want to do in a recursive transformation of a list:

(define (map fn seq)
  (if (null? seq)
      ’()
      (CONS (fn (car seq))
            (map fn (cdr seq)))))

• append: used to combine two or more lists in a way that “flattens” some of the structure of the result. It returns a list whose elements are the elements of the arguments, which must be lists:

> (append ’(one list) ’(and another list))
(one list and another list)

It’s most useful when combining results from multiple recursive calls, each of which returns a subset of the overall answer; you want to take the union of those sets, and that’s what append does.