Scheme Introduction and Examples

Scheme Introduction and Examples

Pure Scheme uses no assignment statements, nor does it define iterative constructs like FOR or WHILE loops. All actions are performed by function calls. Luckily, functions can return complex structures, with no penalty in speed, because data in Scheme is represented by LISTs.

List format:

<symbol> ::= any sequence of characters other than those specifically reserved.

<seq> ::= <empty> | <item><seq> /* separated by white space */

<list> ::= (<seq>)

Examples:

(+ 1 2), (cons (car a) (3)), ((start "string"))

An <atom> cannot be decomposed by Scheme operations (Exception: "explode"); a <list> L consists of a first item, called (car L), and the rest of L, called (cdr L).

A <list> can be created by the (cons A L) function call, which makes A the first element of a list whose cdr is list L. The special object (), the null list, should be the starting point for constructing lists (Scheme can actually use (cons A B) to produce a thing called a dotted pair, written (A . B). Such a thing is an improper list, but some Scheme functions can make use of it.) Function calls in Scheme are written (F arg1 arg2 … ) – that is, the first element of a list is the function name, the other elements are its arguments. Thus, (car L) is in fact a function call, calling the function named "car" on argument "L".

The names "car" and "cdr" are traditional.

Pure Scheme has the functions car, cdr, and cons built in, together with three "predicates", each of which returns either () (standing for "false") or something else (usually #t) standing for "true". The predicates are: atom?, null?, and eq?. eq? is true if and only if its two arguments "point to" the same list structure or atom. One conditional test is defined: (cond (t1 a1) (t2 a2)…(else aN)). This structure is evaluated by testing t1, then t2, etc, until a test tI is found which evaluates to be not false. The value of the expression is then the value of the corresponding action aI. (else aN) is a pair whose test is always true. Finally, Scheme can define functions, using the form
(define (f parameters) body), where parameters is a sequence of 0 or more "names" (using the C convention for names), and "body" is a list expression. When a function f is called, by (f a b c), the arguments a, b, and c are each "evaluated", then their values are "bound" to the corresponding parameter names. Finally, the "body" is evaluated, with the value of a parameter name being the value that name was "bound to" during argument evaluation. Pure Scheme has been extended to include as built-in functions most arithmetic operations on numbers, as well. If you need to "protect" an argument from being evaluated, precede it with ‘: ‘A stands for A itself, not the value of A.

Examples:

Note: A semi-colon starts a comment, which extends to the end of the line. The functions below have NOT been tested -- they MAY work...

;(member? A L): Is object A a member of list L?

(define (member A L) (cond

((null? L) ())

((eq? A (car L)) #t)

(else (member A (cdr L)))

))

;(append M L): Return the list (M1 … Mj L1 … Lk), where M is (M1 … Mj), and L is (L1 … Lk)

(define (append M L) (cond

((null? M) L)

(else (cons (car M) (append (cdr M) L)))

))

;(length L): Returns the number of elements in list L.

(define (length L) (cond

((null L) 0)

(else (plus 1 (length (cdr L))))

))

;(reverse L): Returns (Lk … L1), where L is (L1 … Lk).

(define (reverse L) (cond

????

;(Fibb N): Returns the Nth Fibbonacci number: 1 1 2 3 5 8 13 …

(define (Fibb N) (cond

((< N 3) 1)

(else (plus (Fibb (minus N 1)) (Fibb (minus N 2))))

))

;(perm L): Returns a list whose elements are all the ways list L can be rearranged. For example, (perm ‘(1 2 3)) is ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)). I’d like to do this by removing the first element of L, computing "perm" of the rest of L, then inserting that first element of L into each permutation of L in all possible positions. I’ll later define an auxiliary function "enter" to do those insertions.

(define (perm L) (cond

((null? L) (list L)) ; (perm ()) is (()).

(else (enter (car L) (perm (cdr L))))

))

(define (enter A L) (cond

((null? L) ())

(else (append (enter1 A (car L)) (enter A (cdr L))))

))

(define (enter1 A L) ; Returns a list of copies of L, with A entered into a distinct position of L in each copy.

(enter2 () A L)) ; (enter2 S A L) treats S as a stack of elements removed from the front of L. It forms a new copy by reversing S onto (cons A L), then forms more copies by stacking (car L) on S, and calling enter2 again.

(define (enter2 S A L) (cond

((null? L) (join S (list A)))

(else (cons (join S (cons A L)) (enter2 (cons (car L) S) A (cdr L))))

))

(define (join S L) (cond

((null? S) L)

(else (join (cdr S) (cons (car S) L)))

))