Scheme

WHY STUDY FUNCTIONAL LANGUAGES

• Lambda Calculus invented before computers.
• Historically important in recursive function theory: LISP first introduced as a RFT notation.
• Highly elegant and rather abstract: complex structures like programming languages built from a few simple rules.
• Large body of work in the semantics of programming languages based on FL ideas and λ calculus.
• Pure and unsullied by any hint of "practical" (commercial or military) use.

WHY STUDY FUNCTIONAL LANGUAGES

Well, I lied...turns out FLs are increasingly practically important.

• Processors aren't getting any faster... heating problems.
• Multicores are an answer? If you can dig this hole in an hour, how long will it take 100 diggers like you? Coordination, sharing results, waiting for sub-results, debugging when nothing runs the same way twice,....!!
• URCS has been at the forefront of parallel and distributed processing research since 1975. (Butterfly then, GPUs and cluster computing now).
• Functional programming seen as current best hope for future programming languages for parallel computing.
• Arguably best-known current languages:
• For more, try Parallel Bars (Economist June 4 2011)

SCHEME

Functional Language (Scott Chapter 10). Program is function from inputs to outputs, defined by simpler functions through refinement: e.g. Lisp, ML, Haskell.

Scheme is dialect of LISP, introduced 1975 by G.J. Sussman (MIT) and Guy Steele (CL). Pedagogy to practical. Hewitt: Planner, Actors. GJS: Conniver, Scheme.

General-purpose. Like LISP and Prolog, often associated with AI. Elegant, interactive, deep (repays study).

Operations on numbers (complex, real, int, rational, arbitrary precision), characters, strings, symbols, lists, vectors. Automatic allocation and garbage collection. Objects are first class, in sense that they live independently of block structure after allocation.

Small set of core forms, other syntax built on top, some libraries. Programs represented by the same data structures used in the language.

Refs: ANSI/IEEE, Revised5 Report on Alg. Lang. Scheme.
Note the Text is on line! Scheme Programing Language, edition 3

WHAT'S NEW IN SCHEME?

Non-Lisp features: Identifiers are statically scoped; inner block defs shadow outer ones. Good for modularity, readability, debuggability.

Procedures may be defined in a block and called elsewhere. Identifiers bound to procedures like other objects. Procedure carries its static context with it. Recursion is basic; tail recursion is changed to looping.

Continuations embody the state of the computation at any given point. Invoking one continues the computation from that point. Obvious uses: jumpouts (break, continue), co-routines, backtracking....

Can define extended syntactic forms...emulate entire other languages, for example. Engines support multitasking.

We're recommending "Dr. Scheme", now known as Racket

On our UG server,
/usr/staff/drracket/bin/drracket
should work, or
/usr/staff/drscheme/bin/drscheme
(old version).

It used to be that the "professional" language (textual version) was the only real choice. The tutorial languages all were too restricted. Don't know current choices. Languages used to vary over platforms too...(mac, PC).

SYNTAX

Programs are made of forms (lists), identifiers (symbols), constants (strings, numbers, etc). Newlines ignored (not true for MatLab), indentation is common. Comments are after ;.

Lists and forms represented by lists are grouped with (), as in (a b c),
(* (- x 2) 4). Empty list is (). Some schemes allow [] for (), which improves readability: [...] → (...). But some Schemes don't recognize [].

Boolean true and false are #t and #f. Conditionals also treat () as false, all else is true. No limit to identifier length, case-insensitive: abcd, aBcD are same.

Lists are: (a b c), NOT (a,b,c).

NAMING CONVENTIONS

Somewhat like Perl, Scheme has (sort of, some) conventions for procedure names:

Predicates end with ? (eq?, zero?,...). Type predicates like pair? are created from name of type and ?. >, <, <=, >= are exceptions.

Most char, string, vector procesures start with char-, string-, and vector-, e.g. string-append. (some list procedures start with list but most don't.)

Procedures to convert between types look like type1->type2, e.g vector->list.

Procedures with side-effects end in !, like set!, except for I/O procedures.

Top-level system identifiers used as Scheme system parameters use *..* e.g. *collect-notify*.

EXPRESSIONS

Data objects, procedure applications in prefix form. Lists in (), Lists look like proc. app, so quote them to avoid evaluation:
(quote (+ 2 3)) or
'(* 8 9). Note the programs ``look like the data''.

cons, car, cdr. Dotted pairs.
(list 'a 'b 'c) => (a b c)

How evaluate
(proc arg1 arg2 ... argn) ?
1) get value of proc,
2) get values of arg1 ... argn,
3) apply value of proc to values of arguments. (Recursively of course).
Order of argument evaluation not defined and may vary at random! Procedure evaluation is not just name lookup:
((car (list + - * /)) 2 3)

Except for quoted expressions, which are not evaluated.

INTERACTION

The waiter, or listener, or top-level, is a read-evaluate-print cycle (Prolog, Matlab). Below, response is given after ⇒ .

Type expression, see its value immediately. Can also type to file and use load commmand to load it. Make a transcript with transcript-on. ``` 42 ⇒ 42 2/7 ⇒ 2/7 (+ 4 5) ⇒ 9 '(+ 4 5) ⇒ (+ 4 5) '(+ 4 5) ⇒ (+ 4 5) (car '(a b c)) ⇒ a (cdr '(a b c)) ⇒ (b c) (cons'a '( b c)) ⇒ (a b c) (cadr '(a b c)) ⇒ b (cadddr '(a b c)) ⇒ () ```

MORE SIMPLE E.G.s

``` (define square ;top-level def. ; names next value (lambda (n) ; create a function ; of one arg (* n n))) ; return arg*arg. (square 5) => 25 (square 1/2) => 1/4 ```

(load ``reciprocal.ss'') ; use of load

N.B. attempting to use an undefined identifier gives error, e.g. (i-am-not-defined). UNLESS it's within a lambda expression; it trusts you to define later.

LET Expressions

Bind value to variable within body of the let (let-bound identifiers).:

``` (let ([x 2]) (+ x 3)) => 5 ; gen. form (let ([id val] ...) exp1 exp2...) ;; it works for functions! (let ([double-cons (lambda (x) (cons x x))]) (double-cons 'a)) => (a.a) ```

Nested lets assure ordered evaluation, or can use let* which binds left to right, so earlier values can be used later. Only innermost binding of duplicated identifiers visible in body; it shadows the outer bindings.

LAMBDA Expressions

Like a let expression with parameters. In fact, let exprs ARE lambda exprs underneath. Also bind vars like let, have a body like let

``` (lambda (x) (+ x x)) => #<procedure> ```

general form: (lambda (id ...) exp1 exp2 ...)

most common use: application:
((lambda (x) (+ x x)) (* 3 4)) => 24

bind actual params to formals, evaluate. Clearly usually want to make a procedure the value of a variable, then we can use it easily more than once. Could do that with a let or a define, say.

The identifier list can be a proper list (id ...), a single identifier id, or an improper list
(id1 id2 ... . idn). 2nd puts all args in single list. 3rd fills up proper list, remainder into idn.

LET and LAMBDA

``` (let ([f (let ([x 'a]) (lambda (y) (cons x y)))]) ; bindings at creation stay (f 'b)) ⇒ (a.b) (let ([f (let ([x 'a]) (lambda (y) (cons x y)))]) (let ([x 'i-am-not-a]) (f 'b))) ⇒ (a.b) ; still! ```

let is a syntactic extension defined with lambda and proc. application:

(let ([id val] ...) exp1 exp2 ...)
is expanded to
((lambda (id ...) exp1 exp2) val...)

TOP-LEVEL DEFINITIONS

If need object (like procedure) accessible anywhere, use define: that binding visible everywhere except when shadowed. ``` (define double-any (lambda (f x) ; two args (f x x))) (double-any + 10) => 20 (define doubler (lambda (f ) ; one arg (lambda (x) (f x x)))) ;rtns fn (define double (doubler +)) (define double-cons (doubler cons)) (double-cons 'a) => (a . a) ;; redefine with doubler (define double-any (lambda (f x) ((doubler f) x))) (double-any double-any double-any) ;-} ```

CONDITIONAL EXPRESSIONS

if is a syntactic form, not procedure (it doesn't evaluate all its arguments first!). or and and similar. ``` (define abs (lambda (n) (if (< n 0) ;test (- 0 n) ;consequent n))) ;alternative ```

(or exp ...) evaluates exps L to R, returns first true one or last one. ``` (or #f 'a #f) => a. ```

and evaluates looking for false, returns value of last exp evaled.

Predicates and =,>,<,<=,>=.
null?('(x y z)) gives false.
equal? returns true if two args have same structure. Type predicates like pair?, number?.

COND Multi-branched if: ``` (define abs (lambda (n) (cond [(= n 0) 0] ;;; each case can have ;;; multiple stmts....good! [(< n 0) (- 0 n)] [else n]))) ;;; or [(> n 0) n] w/o else ```

RECURSION

Can use trace to see what happens ``` (define list-copy (lambda (ls) (if (null? ls) '() (cons (car ls) (list-copy (cdr ls)))))) (define tree-copy (lambda (tr) (if (not (pair? tr)) tr (cons (tree-copy (car tr)) (tree-copy (cdr tr)))))) (tree-copy '((a.b).c))⇒((a . b) . c) ```

MAPPING

Apply a procedure to every element of a list. Use existing procedures or roll your own. Can apply multi-arg proc. to multiple lists. ``` (map (lambda (x) (* x x)) '(1 -3 -5 7)) ⇒ (1 9 25 49) (map cons '(a b c) '(1 2 3)) ⇒ ((a.1) (b.2) (c.3)) ```

ASSIGNMENT

Assignment is Not LISPish! Not at all in the spirit!! Politically Incorrect! Assts that are necc. and convenient in other languages often unnec and inconv. in Scheme. E.g. sequence expression evaluation (like the quadratic formula) with a sequence of assignments. In Scheme can use let more briefly and clearly (dependence and lack of it between subexprs).

Still if you want to maintain internal state, subvert normal block structure...

``` (define count ; returns 0,1,2,...per call. (let ([next 0]) ; avoids global, top-level (lambda () (let ([v next]) (set! next (+ next 1)) v )))) (define make-counter ; mult. indep. counters (lambda () (let ([next 0]) (lambda () (let ([v next]) (set! next (+ next 1)) v ))))) (define count1 (make-counter)) (define count2 (make-counter)) ``` Likewise could implement stack with private list, send it push and pop etc. messages..

LOCAL BINDING

let, let*, letrec, rec, fluid-let

recall let doesn't guarantee any order of evaluations of its clauses, but let* works left to right (p. 61).

letrec, rec allow mutually recursive objects, usually procedures. Use when have circular dependence among identifiers and order of their evaluation is unimportant. Fluid-let is temporary assignment...good only in fluid-let body.

e.g. ``` (letrec ([even? (lambda (x) (or (zero? x) (odd? (1- x))))] ; note a new op 1- [odd? (lambda (x) (and (not (zero? x)) (even? (1- x))))]) (even? 20)) => #t ```

E.g. VECTOR-SCALAR MULTIPLY

Creates new vector equal to v scaled by x. ``` (letrec ; since you may want to call ; other functions ; in the vector-matrix package ([vec-sca-mul (lambda (v x) (let* ([n (vector-length v)] [r (make-vector n)]) (do ([i 0 (1+ i)]) ((= i n) r) ;return (vector-set! r i (* (vector-ref v i) x) ))))])) ```

MORE BINDING FORMS

(define id exp)
define( (id spec) exp1 exp2...)

Second form good shorthand for binding identifiers to procedures. Same as ``` (define id (lambda spec exp1 exp2...)) ```

Internal Definitions can appear at front of lambda body or any form derived from lambda... ``` (lambda idspec (define id val) ... ; can also use ; letrec here! exp1 exp2 ...) ```

CONTROL

Procedures:
( < procedure > exp ...),
(apply < procedure > obj ... list)

Note last allows variable number of args.

Quote:
(quote obj), (quasiquote obj) (unquote obj), (unquote-splicing obj)

Shorthand for various forms of quote, like ', `, ,@. Unquote forms only good inside quasiquote, which allows unquotes.

``` (quasiquote (a b (unquote-splicing (reverse '(c d e))) f g)) ``` yields (a b e d c f g)

Sequencing: (begin exp1 exp2 ...): evals in sequence; implicit in many forms.

CONDITIONALS

``` (if test-exp then-exp else-exp) (if test-exp then-exp) (when test-exp exp1 exp2) ;do if true (unless test-exp exp1 exp2) ;do if false (not obj) (and exp ...) (or exp ...) (cond (test-exp exp ...) ... (else exp ...)) (cond (test-exp exp ...) ...) ; if no default (case val (key exp ...) ... (else exp ...)) (case val (key exp ...) ...) (record-case val (key idspec exp ...) ... (else exp ...)) (case val (key idspec exp ...) ...) ``` The last for destructuring records (tagged lists). Compare using eqv? (be aware of these tests).

MAPPING

Map applies proc to corresponding elts of lists. Op order not specced, resulting output list is in order. for-each does not return list but works in order. Do is form of iteration. ``` (map procedure list1 list2 ...) (for-each procedure list1 list2 ...) ; do until true or done (ormap procedure list1 list2 ...) ; do until false or done (andmap procedure list1 list2 ...) (ormap member '(a b c) '((c b) (b a) (a c))) => (b a) (do ((id val update) ...) (test res ...) exp ...) ```

DELAYED EVALUATION

delay, force can implement lazy evaluation (we'll see that again): only evaluate when needed and remember the answer in case asked again (``memo functions'').

EQ, EQV, EQUAL

Traditional in LISP: when are things the same? Same value? Same storage location? Lots of cases! Detailed rules, examples, etc. in language reference.

(eq? obj1 obj2) Basically, same pointer value.

(eqv? obj1 obj2) Basically, ``operationally equivalent'': compare equal with relevant operator (=, char=?). Procedures with same arguments returning same values with same side effects are operationally equivalent.

(equal obj1 obj2) Have same structure and contents: print the same. Pairs, strings, vectors have correspondingly equal values. More generally true, but longer to compute.

OTHER OPERATIONS ON OBJECTS

! means "causes side effects". ``` boolean?, null?, pair?, list?, atom?, number?, complex?, real?, rational?, integer?, char?, output-port?, procedure? ... cons, car, cdr, caar,cadr,... mcons, mcar, mcdr, set-mcar! set-mcdr! (make-list n), (make-list n obj), (list obj ...), (list* obj ... final-obj), (length list), (list-ref list n), (list-tail list n), (last-pair list), (list-copy list), (tree-copy tree), (append list ...), (append! list ...), (reverse list), (reverse! list), ([memq, memv, member] obj list), ([remq[!], remv[!], remove[!]] obj list), ([substq[!], substv[!], subst[!]] obj tree), ([assq, assv, assoc] obj alist), (sort[!] predicate list) (merge[!] predicate list1 list2) ``` Association List: proper list with elements that are key,value pairs (key.value). Like database.

NUMBERS

Four types, operations. Bases and other prefixes ``` #d or #i, #o, #b, #x: number base 10, 8, 2, 16; ``` Scheme supports floating point, integers, and rationals (5/7). Reps can be [in]exact. Normal predicates (zero? even?...), operations, except cute rules often expand operation's semantics for e.g. ``` (- 4 3 2 1} ⇒ -2 (/ 60 5 4 3 2) ⇒ 1/2 ``` Here the first argument of the list is the first argument of the operation, and the sum of the rest of the arg. list is the second.

Also 1+, 1-, quotient, remainder (for integer q and r), ``` modulo, truncate, floor, ceiling, round, abs, max, min, gcd, lcm, expt, expt-mod, random, exact->inexact, inexact->exact, rationalize, ... numerator, imag-part, angle, sqrt, exp, sin, cos, tan, asin,... atan. ```

CHARACTERS, STRINGS, VECTORS, SYMBOLS

Similar to numbers: the operations and predicates you'd expect for manipulating, comparing, converting, etc.

Vectors are like arrays: accessed by index, not sequentially. Can be defined with length declaration ``` #(a b c), #4(a b c d), #1000(0) ``` Symbols are used for identifier names, but can also be constructed by the user. Symbols that print the same are identical in the eq? sense and can be compared quickly (using the symbol table). Useful for record-structure tags, messages between programs, names for objects in an association list. Famous operation gensym returns a new symbol. Also Structures.

INPUT OUTPUT

Seems straightforward, but may vary with system.

Uses I/O ports, i.e. a pointer to a stream of chars (typically a file): like a Pascal file pointer. So get open, close, read, unread, read-char, eof-object?, clear-input-port, write, display, pretty-print, newline. eof_object? is true if you see the EOF object, whatever that is... think eof?.

Formatted output with format.

SYSTEM OPERATIONS

Loading, evaluation: (load filename [eval-proc]), eval, extend-syntax, expand (for syntactic extensions), compile-file, eval-when, ...

Top-Level Values: define, (define-top-level-value symbol obj) (last evals symbol), other easy t-l-v ops.

Transcripts: (transcript-on filename), (transcript-off).

Garbage Collection: (collect)

Statistics: time, display-statistics, cpu-time, real-time, bytes-allocated, date-and-time

Tracing: trace-lambda, trace-let, trace, untrace

Error and exceptions: error, *stack-overflow-handler* , etc.

NAMED LET

A let that's even more like a lambda: implements recursive looping or iteration. E.g. ``` (lambda (n) % name used as func in body. (let f ((i 2)) if (>= i n) '() % return nil if yes (f (+ 1 i)))) % else 'iterate' ```

CONTINUATIONS

Simple idea: a general, space-time goto. Allows saving and continuing computations at any point. So in a way the idea is simple, but its use sometimes looks mysterious.

(call-with-current-continuation procedure) or (call/cc procedure)

Simple use: ``jumpouts'' like break, continue, return: leaving nested computations without returning thru them all. Scheme is pretty good at obvious instances (e.g. ormap, andmap), but let's pretend. We'd like (not working code!): ``` ;;; Return the first element ;;; in LIST for which ;;; wanted? returns a true value. (define (search wanted? lst) (for-each (lambda (element) (if (wanted? element) (return element))) lst) #f) ``` Again, that red return is what we want to happen, not what we can really do.

EXIT CONTINUATIONS

How achieve that ormap-like behavior? call/cc gets as argument another procedure which corresponds to the return proc. we want, which itself is called with a single argument. When the call is made to the 'return' procedure, the call to call/cc returns, and returns with the argument passed to the 'return' procedure.

``` ;;; Rtn 1st elt in LST for which ;;; WANTED? returns true (define (search wanted? lst) [call/cc ;;; we write our own nameless procedure ;;; that captures the continuation in 'return' ;;; for our later use (lambda (return) (for-each (lambda (element) (if (wanted? element) (return element))) ;;; use it here lst) #f)] ;; [..] evaluates to X ;; when (return X) ) ) ``` When hit return, return from whole call/cc expression with its argument. Here we invoke continuation before call/cc returns.

EXIT CONTINUATIONS CONT

We can pass our return procedure off to another procedure outside the scope of the call/cc: ``` ;;; if Like ELEMENT? Call LIKE-IT. (define (treat element like-it) (if (good-element? element) (like-it 'likeaction))) ;;; Call TREAT on LIST elts, ;;; with proc. to call ;;; when TREAT likes this element. (define (search treat lst) [call/cc (lambda (return) (for-each (lambda (element) (treat element return)) lst) #f)] ;; can return here from (treat ..) ) ``` Jump from within treat proc. to exit at call/cc in search: a non-local exit.

CONTINUATION AS CONTROL

Using a named procedure (with an example).

A continuation is something used to continue. Handing it around is handing around where control will pass to next. ``` (define return #f) (+ 1 [call/cc (lambda (cont) (set! return cont) ;; return = cont 1)] ;; cont returns here ) ⇒ 2 ;; and now return still = cont! ``` The call to + evaluates to 2, since the call/cc expression terminates normally, returning 1. But the set! binds the continuation cont to return out at top level. So return is a procedure, and invoking it passes control to the spot where the call/cc returns. Soo...

(return 99) ⇒ 100, (return 3) ⇒ 4, etc.

DIVING INTO THE BOTTOM OF A RECURSION

This is just an extreme continued example of keeping a continuation around as a variable and using it.

``` ; global variable (define base_case #f) (define fac (lambda (x) if (= x 0) [call/cc lambda(k) (set! base_case k) 1] ;; [...] returns recursion base case ;; (k X) returns X as base case (* x (fac (- x 1))))) ;; As above, after set!, (base_case X) ;; returns X as base case (as value of [..]). (fac 4) ⇒ 24 (base_case 2) ⇒ 48 ``` This is perfectly analogous to the last "+1" example, only here the continuation is at the bottom of a stack of recursive calls, where the base case is evaluated before returning up a level. Thus if we supply an argument to the continuation, that argument becomes the value of the base case and the rest of the recursions unwind using it.

CO-ROUTINING WITH CONTINUATIONS

Multiple routines call each other, pass control back and forth, possibly never complete: producers and consumers, time-sharing, whatever. Each procedure calls other one passing along a continuation, and receiving one in return...a bit mind-blowing but...

Pretty good examples if you Google(TM) for ``Scheme Continuation Tutorial'', or so.

Enough for now, though.

SYNTACTIC EXTENSION

Like Prolog's, only more so.

Another paradigmatical and usually behind-the-scenes Scheme feature: a powerful syntax extension facility. Implements most of Scheme itself, and not hard to implement entire other languages.

In fact, the only core syntactic forms are constant, identifier, the functions quote, lambda, if, set!, begin, and ().

Other syntactic forms (e.g. let, do) are defined in terms of core forms. To see how, try expand. To do your own, look for extend-syntax, which acts a little like define.