(selected from Textbook chapter10 plus Scheme notes from 1997)

DrScheme is a graphical Windows IDE for Scheme programming, and can be downloaded from Rice University at http://www.cs.rice.edu/CS/PLT/packages/drscheme/.

Procedures are first class values in Scheme.

They can be:

• Bound to variables
• Passed as arguments to other procedures
• Returned as values of other procedures

Examples are given below.

PROCEDURE BOUND TO VARIABLE: lambda

The function (lambda (n) (display n)) is bound to variable show.

PROCEDURE PASSED AS ARGUMENT: example is MAP

Works like ML map: (map function list)

• applies function to each member of list
• useful application of lambda

map is defined as a recursive function.

define (map f x)
   (cond ((null? x) '( ))
       (else (cons (f (car x)) ( map f (cdr x)))
       )
   )
)

PROCEDURE AS PROCEDURE RESULT: example is currying

(e.g. write a two-parameter procedure as a one parameter procedure that returns a one parameter procedure)

(add5 7) what is result?

(add8 7) what is result?

(curry+ 6) 5) what is result?

BEGIN

Forces sequential evaluation of list elements, from left to right

Example:

PROCEDURE vs. SYNTACTIC FORM

Since all statements are lists and all procedure calls are lists, can all statements be expressed as procedure calls?? No. Here's why:

procedure: all arguments are evaluated before procedure begins

syntactic form: expression evaluation determined by Scheme semantics

examples of procedures: +, - , * , / , car, cdr, cons

what about 'if'?? can it be a procedure?
(no, why not?)

What about 'and'? 'or'? Can they be procedures?
(not if short-circuit desired)

recall: when does short circuit affect state of computation?
(when unevaluated expression causes side effect)

Nothing we've seen so far causes side effects.

ASSIGNMENT

- rarely necessary

- causes side effects

- syntax (set! variable expression)

- changes binding

- example:

(define count 0)
(define (sigma n)
   (set! count (+ count 1))
   (if (> n 0)
      (+ n (sigma (- n 1)))
      0
   )
)

STORAGE ALLOCATION (boxes and cons cells)

1. conceptually, structure of objects created by cons.
2. atoms (values, symbols) stored as Box
3. pairs stored as cons cell, a pair of pointers
   - left one points to car, right one points to cdr
4. proper list: right pointer either null or points to cons cell. (cons 1 (2))
5. improper list: right pointer points to box. E.g. (cons 1 2)
6. empty list represented by null right pointer.
7. example: (cons 3 (cons 4 (cons 5 ())))
   - builds 3-cell linked list
   - equivalent to ‘(3 4 5) or (list 3 4 5)
8. example: (cons (cons 3 ()) (cons 4 (cons 5 ())))
   - equivalent to ‘( (3) 4 5)
   - how many cons cells? (no longer linear)
9. consider what happens when you do:
   (define a ‘(3 4 5))
   then change the binding with:
   (set! a ‘(1 2))
   What happens to the linked list representing ‘(3 4 5) ?
10. consider what happens when you do:
    (define a ‘(1 2))
    (define b ‘(3 4 5))
    (define c (cons 0 (append a b))) ; resulting list?
    (set-car! b a) ; make a the car of b; c affected?
    (set! c ‘(6)) ; are a and b affected?
    

EQUALITY

Two different equality tests are provided: equal? and eq?

In essence, former tests all components for equal values; latter tests pointer equivalence (alias) or atom value.

Try: (equal? '(1) '(1)) and (eq? '(1) '(1))

Try: (equal? 1 1) and (eq? 1 1)

How does one create an alias in scheme?

This reinforces that lists are implemented using pointers.

Related Home Pages: notes | CSC 326 | Peter Sanderson | Computer Science | SMSU

Peter Sanderson ( PeteSanderson@mail.smsu.edu )