Transcript document
Scheme • Although Scheme is syntactically a simple language, it supports sophisticated modeling: higher-order functions are a powerful tool in describing problems. • Many ideas in design patterns have their roots in functional programming (e.g. strategy allows us to treat methods as first-class, a decorator acts like a function which maps a function to a function – think of the stream decorators in Java). • With mutation (the ability to change a name-value binding in an environment) sophisticated systems can be built quite compactly. 1 Review of evaluation model • Numbers evaluation to “themselves” (a character string representing a number evaluates to its base 10 numeric representation). • For example: > 213 213 if you ask Scheme to evaluate a number you get the number as a result 2 Evaluating names • A name is evaluated by looking it up. Lookup starts in the current environment, and continues along the chain of statically-linked environments until either a binding is found (in which case the corresponding value is returned) or it isn’t (in which case an error occurs). • For example (assuming no binding for x exists yet): > x Error: reference to undefined identifier: x > (define x 12) > x 12 > 3 Primitives • Primitives, such as + and -, are ordinary names with name-value bindings established at start-up in the primitive environment, the base environment for evaluation (base in the sense that it’s static link is null). • We can use + wherever we need a function. • For example: > (define applyOperator (lambda (op) (op 3 4))) > (applyOperator +) 7 > (applyOperator -) -1 > • We can also rebind the names of primitives (not a good idea in general, but this shows that primitives are not treated differently from other names in the language). > (+ 3 4) 7 > (define + -) > (+ 3 4) -1 name “+” refers to addition function name “+” now refers to subtraction function 4 lambda forms • A lambda form (lambda abstraction) defines a function in Scheme. • Informally, the syntax is: (lambda (<parameters>) <body>) • When a lambda form is evaluated a closure results (which is printed as #<procedure:name>). • For example: > (define addOne (lambda (p) (+ p 1))) > addOne #<procedure:addOne> > 5 Function applications • A function application is evaluated by first evaluating each expression inside the application, then applying the function to its arguments. • This is accomplished by first creating a new environment in which the function’s parameters are bound to its arguments, and then evaluating the function’s body with respect to the new environment (which is now the current environment). 6 Evaluating (addOne 4) primitive env + cons … <proc> <proc> <proc> user env p addOne (+ p 1) p 4 (+ p 1) 7 Local bindings • Local bindings can be created using a letform: (let ((a 1) (b 2)) <body>) • Let is just syntactic sugar for a procedure application; the above is equivalent to: ((lambda (a b) <body>) 1 2) 8 Evaluating (define foo (let ((a 1) (b 2)) (lambda (c) (+ a b c)))) primitive env + cons … c <proc> <proc> <proc> (+ a b c) user env ab addOne foo (lambda (c) (+ a b c)) a b 1 2 (lambda (c) (+ a b c)) 9 Mutation • set! allows an existing name-value binding to be changed. 10