For this lab, you'll be using a Scheme interpreter. To start the
interpreter, type `scheme48` in a shell window. This will start the
Scheme interpreter, which will then show its prompt:

bradbert-8:At this point, anything that you type will be interpreted, and the result will be printed. To exit scheme48, type ",exit". The remainder of this tutorial will be a sample scheme session. You may want to start upscheme48Welcome to Scheme 48 0.36 (made by sethml on Fri Nov 18 03:12:22 PST 1994). Copyright (c) 1993, 1994 by Richard Kelsey and Jonathan Rees. Please report bugs to scheme-48-bugs@martigny.ai.mit.edu. Type ,? (comma question-mark) for help. >

>Strings are also atoms which evaluate to themselves:; Anything starting with a semicolon is a comment.>1 ; An integer.1 >-562-562 >23.78 ; A floating-point number.23.78 >99999999999999999999999999999999999 ; Integers have no limits.99999999999999999999999999999999999 >2/3 ; We can even use fractions!2/3 >4/81/2

>There are also atoms called symbols. Symbols must be prefixed by a single quote, since otherwise they are interpreted as variables (see below):"This is a string""This is a string"

>There are also two special atoms, #t and #f, which are the cannonical true and false values. They don't need to be quoted:'a'a >'this-is-an-atom'this-is-an-atom >'ATOMS-are-CASE-insensitive'atoms-are-case-insensitive >'I/contain-weird^characters+666!'i/contain-weird^characters+666!

>#t#t >#f#f

>forgot-a-quoteError: undefined variable forgot-a-quote (package user) 1>^D>,levels offWon't push command level on errors >forgot-a-quoteError: undefined variable forgot-a-quote (package user) >

>Note that lists (as well as procedure calls, see below) can contain new-lines (they're the same as any other white space). This means that if you forget the proper number of closing parentheses, the Scheme interpreter will just sit there, waiting for you to finish your list.'(1 2 3)'(1 2 3) >'(list of symbols)'(list of symbols) >'((list 1) (list 2))'((list 1) (list 2)) >'() ; The empty list.'()

>You notice above that the name of a procedure evaluates to a(+ 2 3)5 >(+ (/ 6 3) 2) ; Calculate 6 / 3 + 2.4 >(list 1 2 3) ; list puts its arguments into a list.'(1 2 3) >(list 'a 'b 'c)'(a b c) >+ ; Procedure names evaluate to procedures!'#{Procedure 139 +} >list'#{Procedure 230 list}

>(lambda (x) (+ x x)) ; A procedure to double a number...'#{Procedure 6755} >((lambda (x) (+ x x)) 8) ; We can call this procedure!16 >((lambda (x y) (/ (+ x y) 2)) 16 20) ; This procedure takes 2 arguments.18

>So, by using(define six 6)>six6 >(define up 'down)>up'down

>(define double (lambda (x) (+ x x)))>(define average (lambda (x y) (/ (+ x y) 2)))>(double 5)10 >(average -10 4)-3

>Some other random procedures:(+ 6 7)13 >(+ 1 2 3 4 5)15 >(* 999999 999999)999998000001 >(/ 12345 54321)4115/18107 >(/ 3.1415 2)1.57075 >(= 3 4)#f >(= 3 3)#t >(< 1.1 2)#t >(>= 3 4)#f

>Some list procedures (these will become clearer in the section below):(equal? 'a 'b) ; equal? compares two objects.#f >(equal? 'a 'a)#t >(equal? 1 1)#t >(equal? '(a b (c d)) '(a b (c d)))#t >(null? '(a)) ; null? returns #t only on the empty list.#f >(null? '())#t >(not #t)#f >(not #f)#t >(string>? "abc" "def") ; Compare two strings.#f >(string>? "def" "abc")#t

>(car '(a b c)) ; car returns the first element in the list...'a >(cdr '(a b c)) ; cdr returns the rest.'(b c) >(cdr '(b c))'(c) >(cdr '(c))'() >(cdr '())Warning: argument type error (cdr '()) (procedure wants: (:pair)) (arguments are: (:null)) Error: exception (cdr '()) >(cons 'a '(b c))'(a b c) >(cons (car '(a b c)) (cdr '(a b c)))'(a b c) >(append '(first list) '(second list))'(first list second list)

struct list_element { void *data; struct list_element *next; }You notice that the element structure essentially consists of two pointers. In Scheme, lists are also constructed of data structures consisting of two pointers, but the pointers are allowed to point to any type of object. These structures are called pairs. You could think of a pair as:

struct pair { void *car; void *cdr; }(Historical footnote: the fields are named

A list consists of a sequence of pairs, each of which contains a pointer to
a list element in its `car`, and a pointer to the next element in
the list in its cdr. The cdr of the last element in the list points to the
empty list. For instance, the list `'(1 2 3)` would be stored in
memory as:

+-----+ /->+-----+ /->+-----+ | car --> 1 | | car --> 2 | | car --> 3 +-----+ | +-----+ | +-----+ | cdr ------/ | cdr ------/ | cdr --> '() +-----+ +-----+ +-----+Now

+-----+ | car --> 'a +-----+ | cdr --> 'b +-----+This is represented as

(cond (condition1 result1) (condition2 result2) . . . )

>(define zeroness (lambda (x) (cond ((equal? 0 x) 'zero) (#t 'non-zero))))>(zeroness 0)'zero >(zeroness 4)'non-zero >(define sign (lambda (n) (cond ((> n 0) 1) ((< n 0) -1) (#t 0))))>(sign 67.3)1 >(sign -12)-1 >(sign 0)0

(define fib (lambda (n) (cond ((or (= n 0) (= n 1)) 1) (#t (+ (fib (- n 1)) (fib (- n 2)))))))Now, in Scheme48:

>(load "fib.scm")fib.scm . >(fib 20)10946

>Now for a procedure to find the length of a list. An empty list is of length 0. A non-empty list is one item longer than its cdr. This can be implemented as:(define factorial (lambda (n) (cond ((= 0 n) 1) (#t (* n (factorial (- n 1)))))))>(factorial 0)1 >(factorial 5)120 >(factorial 50)30414093201713378043612608166064768844377641568960512000000000000

>Now for a more powerful procedure:(define list-length (lambda (l) (cond ((null? l) 0) (#t (+ 1 (list-length (cdr l)))))))>(list-length '(a b c d e))5 >(list-length '())0 >(list-length 123)Error: exception (cdr 123)

>By the way,(define map (lambda (f l) (cond ((null? l) '()) (#t (cons (f (car l)) (map f (cdr l)))))))>(map zero? '(1 0 3 0 6)) ; zero? happens to be built-in...'(#f #t #f #t #f) >(map (lambda (n) (* 2 n)) '(1 2 3 4 5 6))'(2 4 6 8 10 12)

SML