Transcript 02 Scheme Tutorial

Scheme Tutorial
Goals
• Combine several simple ideas into one
compound idea to obtain complex ideas
• Bring two ideas together to obtain relations
• Seperate ideas from all other ideas that
accompany them in real existence to obtain
general ideas (this is called abstraction)
by John Locke, An Essay Concerning Human Understanding (1690)
Features of LISP
• Recursive Functions of Symbolic Expressions and
Their Computation by Machine (John McCarthy, 1960)
• LISP stands for LISt Processing
• An interpreted language (not efficient)
• Second oldest language (after FORTRAN)
• Designed to solve problems in the form of
symbolic differentiation & integration of algebraic expressions
Features of LISP
• LISP’s ability
– to represent procedures as data
– to manipulate programs as data
• LISP is currently a family of dialects
(share most of the original features)
• Scheme is a dialect of LISP
(small yet powerful)
Characteristics of SCHEME
• Supports functional programming - but not on
an exclusive basis
• Functions are first class data objects
• Uses static binding of free names in
procedures and functions
• Types are checked and handled at run time no static type checking
• Parameters are evaluated before being passed
- no lazyness
Elements of Language
• Primitive expressions – simple expressions
• Means of combination – compound expressions
• Means of abstraction – compound objects can
be named and manipulated as units
Scheme Expressions - 1
> 395
395
> (+ 137 349)
486
> (/ 10 6)
1.66667
Scheme Expressions - 2
Prefix Notation
take arbitrary number of arguments
> (+ 21 35 12 7)
75
> (* 25 4 12)
1200
Scheme Expressions - 3
Prefix Notation
allow combinations to be nested
> (+ (* 3 5) (- 10 6) )
19
> (* (+ 3 (- (+ 2 1) 5) (/ 4 2)) (* 3 2))
Read – Eval – Print loop
Scheme Pretty-Printing
> (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))
(+ (* 3
(+ (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6))
> (load “e1.scm”)
Scheme Naming
> (define size 2)
> size
2
> (* 5 size)
10
> (load “e2.scm”)
Compound Procedures
> (define (square x) (* x x))
> (square 3)
9
(define (< name > < formal parameters >) < body > )
> (load “e3.scm”)
Substitution model for procedure application
Conditional Expressions
> (define (abs x)
(cond ((> x 0) x)
((= x 0) 0)
((< x 0) (- x))))
> (define (abs x)
(cond ((< x 0) (- x))
(else x)))
Conditional Expressions
(cond (<p1> <e1>)
(<p2> <e2>)
:
(<pN> <eN>))
p is predicate
either true (non-nil) or
false (nil)
e is consequent expression
returns the value of it
Conditional Expressions
> (define (abs x)
(if (< x 0)
(- x)
x))
(if <predicate> <consequent> <alternative>)
Logical Operators
Primitive operators : < , > , =
Logical operators : and , or , not
> (define (>= x y)
(or (> x y) (= x y)))
Example: another definition of (>= x y)
Example: 5 < x < 10
Procedures
different than mathematical functions
x = the y such that y  0 and y2 = x
> (define (sqrt x)
(the y (and (>= y 0) (= (square y) x))))
Mathematics – declarative (what is)
Programs – imperative (how to)
Square Roots by Newton’s Method
> (load “e4.scm”) - 2 = 1.4142...
Square Roots by Newton’s Method
break the problem into subproblems
how to tell whether a guess is good enough
how to improve a guess
how to calculate the average of two numbers
etc.
each of the above tasks is a procedure
Square Roots by Newton’s Method
sqrt
sqrt-iter
good-enough?
square
abs
> (load “e4.scm”)
improve
average
Procedures – Black Box Abstractions
(define (square x)
(* x x))
(define (square x)
(exp (+ (log x) (log x))))
Procedural Abstractions
(define (square x) (* x x))
(define (square y) (* y y))
(define (square variable) (* variable variable))
parameter names that are local to the procedure
bound variables – change throughout the procedure
does not change the meaning of the procedure
free variables – if a variable is not bound in the proc
(define (good-enough? guess x)
(< (abs (- (square guess) x)) .001))
Internal Definitions
Encapsulation – hiding details
> (load “e4.scm”)
Nesting definitions – block structure
> (load “e5.scm”)
Lexical scoping – not necessary to pass x explicitly
to internal procedures, so x becomes free variable
in the internal definitions
> (load “e6.scm”)
Procedures
Procedure :
a pattern for the local evolution of
a computational process.
At each step,
the next state of the process is computed from
its current state according to the rules of
interpreting procedures.
Linear Recursion
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720
process does grow and shrink
Linear Recursion
n! = n * (n-1) * (n-2) ... 2 * 1
n! = n * (n-1)!
n! = n * ( (n-1) * (n-2)! )
n! = n * ( ... ( (n-1) * (n-2) * ... * 1! ) ) ... )
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
Linear Iteration
(factorial 6)
(fact-iter
1 1 6)
(fact-iter
1 2 6)
(fact-iter
2 3 6)
(fact-iter
6 4 6)
(fact-iter
24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720
process does not grow and shrink
Linear Iteration
Product, counter = 1
do while counter < n
product = counter * product
counter = counter + 1
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
Tree Recursion
Fibonacci numbers : 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Fib( n ) =
0
if n = 0
1
if n = 1
Fib(n-1) + Fib(n-2)
otherwise
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
Tree Recursion
Fib(5)
Fib(4)
Fib(3)
Fib(3)
Fib(2)
Fib(2) Fib(1) Fib(1) Fib(0)
Fib(1) Fib(0)
Fib(2)
Fib(1) Fib(0)
Fib(1)
Tree Recursion
For Fibonacci numbers,
Use linear iteration instead of tree recursion
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
Exponentiation – linear recursion
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
Exponentiation – linear iteration
(define (expt b n)
(exp-iter b n 1))
(define (exp-iter b counter product)
(if (= counter 0)
product
(exp-iter b
(- counter 1)
(* b product))))
Exponentiation – fast method
bn = (bn/2)2
if n is even
bn = b * bn-1
if n is odd
(define (fast-exp b n)
(cond ( (= n 0) 1)
( (even? n) (square (fast-exp b (/ n 2))))
(else (* b (fast-exp b (- n 1))))))
(define (even? n)
(= (remainder n 2) 0))
Greatest Common Divisor
GCD( a , b ) is defined to be the largest integer that evenly
divides both a and b.
GCD( a , b ) = GCD( b , r ) where r is the remainder of a / b.
GCD(206, 40)=GCD(40,6)=GCD(6, 4)=GCD(4, 2)=GCD(2, 0)=2
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
Higher-Order Procedures
Build abstractions by assigning names to common patterns
(define (cube x) (* x x x))
Procedures that manipulate data
i.e. accept data as argument and return data
What about procedures that manipulate procedures
i.e. accept procedures as argument and return procedures
Higher-Order Procedures
Procedures as Parameters
(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))
(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a) (sum-cubes (+ a 1) b))))
Procedures as Parameters
(define (<name> a b)
(if (> a b)
0
(+ (<term> a)
(<name> (<next> a) b))))
Procedures as Parameters
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
(define (sum-cubes a b)
(define (inc x)
(+ x 1))
(sum cube a inc b))
Procedures using Lambda
Lambda – define anonymous
(lambda (x) (+ x 1))
(lambda (<formal-parameters>) <body>)
(define (sum-cubes a b)
(sum (lambda (x) (* x x x))
a
(lambda (x) (+ x 1))
b))
Procedures using Lambda
Lambda – define anonymous
(define (plus4 x) (+ x 4))
(define plus4 (lambda (x) (+ x 4))
Lambda Calculus
A lambda expression describes a "nameless" function
Specifies both the parameter(s) and the mapping
Consider this function: cube (x) = x * x * x
Corresponding lambda expr: (x) x * x * x
Can be "applied" to parameter(s) by placing the
parameter(s) after the expression
((x) x * x * x)(3)
The above application evaluates to 27
Lambda Calculus
Based on notation 
(lambda (l) (car (car l)))
l is called a "bound variable";
think of it as a formal parameter name
Lambda expressions can be applied
((lambda (l) (car (car l))) '((a b) c d))
Lambda Examples
> (define x 6)
> (lambda (x) (+ x 1))
> (define inc (lambda (x) (+ x 1)))
> (define same (lambda (x) (x)))
> (if (even? x) inc same)
> ((if (even? x) inc same) 5)
6
Lambda Examples
> ((lambda(x) (+ x 1)) 3)
4
> (define fu-lst (list (lambda (x) (+ x 1)) (lambda (x) (* x 5))))
> fu-lst
(#<procedure> #<procedure>)
> ((second fu-lst) 6)
30
Internal Definitions
Internal definitions: the special form, LET
(let ( (x ‘(a b c))
(y ‘(d e f)) )
(cons x y))
* Introduces a list of local names (use define for toplevel entities, but use let for internal definitions)
* Each name is given a value
Using Let to Define Local Variables
f(x,y) = x(1 + xy)2 + y(1 – y) + (1 + xy)(1 – y)
a = 1 + xy
b=1–y
f(x,y) = xa2 + yb + ab
Using Let to Define Local Variables
(define (f x y)
(define a (+ 1 (* x y)))
(define b (– 1 y))
(+ (* x (square a))
(* y b)
(* a b)))
Using Let to Define Local Variables
(define (f x y)
(let ((a (+ 1 (* x y)))
(b (– 1 y)))
(+ (* x (square a))
(* y b)
(* a b)))
Using Let to Define Local Variables
(define (f x y)
((lambda (a b)
(+ (* x (square a))
(* y b)
(* a b)))
(+ 1 (* x y))
(– 1 y)))
Using Let to Define Local Variables
(let ((<var1> <exp1>)
(<var2> <exp2>)
:
(<varN> <expN>))
<body>)
Procedures as Returned Values
The derivative of x3 is 3x2
Procedure
: derivative
Argument
: a function
Return value
: another function
Derivative Procedure
If f is a function and dx is some number,
then Df of f is the function whose value
at any number x is given (limit of dx) by
f(x + dx) – f(x)
D f(x) = ---------------------dx
Procedures as Returned Values
(define (deriv f dx)
(lambda (x)
(/ (- (f (+ x dx)) (f x))
(dx)))
> ((deriv cube .001) 5)
75.015
Pairs
Compund Structure called Pair
<pair> constructor procedure “cons <head> <rest>”
<head> extractor procedure “car <pair>”
<rest> extractor procedure “cdr <pair>”
(cadr <arg>) = (car (cdr <arg>))
(cons 1 2)
2
1
Box & Pointer
Representation
Pairs (continued)
(cons (cons 1 2) (cons 3 4))
3
1
4
2
(cons (cons 1 (cons 2 3)) 4)
4
1
2
3
Hierarchical Data
Pairs enable us to represent hierarchical data
hierarchical data – data made up of parts
Data structures such as sequences and trees
Data Structures
Lists
(list <a1> <a2> ... <aN>) is equal to
(cons <a1> (cons <a2> (cons ... (cons <aN> nil))...)
List Operations – append, delete, list, search, nth, len
Sets
> (load “e8.scm”)
Trees
> (load “e9.scm”)
Symbols and Quote
(define a 1)
(define b 2)
(list a b)  (1 2)
(list ‘a ‘b)  (a b)
(car ‘(a b c))  a
(cdr ‘(a b c))  (b c)
Data Abstraction
from Primitive Data to Compund Data
Real numbers – Rational numbers
Operations on primitive data : +, -, *, /
Operations on compound data : +rat, -rat, *rat, /rat
Generic operators for all numbers : add, sub, mul, div
Rational Numbers
(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
(define (+rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (denom x) (numer y))
(* (denom x) (denom y))))
Use of Complex Numbers
Operations on compound data : +rat, -rat, *rat, /rat
+c -c *c
/c
Complex arithmetic package
Rectangular representation
Polar representation
List structure and primitive machine arithmetic
Use of Numbers
Generic operators for all numbers : add, sub, mul, div
add sub mul div
Generic arithmetic package
+rat –rat *rat /rat
Rational
arithmetic
+c –c *c /c
Complex arithmetic
Rectangular
Polar
+ – * /
Real
arithmetic
List structure and primitive machine arithmetic
Complex Arithmetic - 1
z = x + i y where i2 = -1
Im
Real coordinate is x
y
z = x + i y = r eiA
Imaginary coordinate is y
r
A
x
Re
(define (make-rect x y) (cons x y))
(define (real-part z) (car z))
(define (imag-part z) (cdr z))
Complex Arithmetic - 2
z = x + i y = r eiA
Magnitude is r
Angle is A
(define (make-polar r a)
(cons (* r (cos a)) (* r (sin a))))
(define (magnitude z)
(sqrt (+ (square (car z)) (square (cdr z)))))
(define (angle z)
(atan (cdr z) (car z)))
Complex Arithmetic - 3
(define (+c z1 z2)
(make-rect (+ (real-part z1) (real-part z2))
(+ (imag-part z1) (imag-part z2))))
(define (*c z1 z2)
(make-polar (* (magnitude z1) (magnitude z2))
(+ (angle z1) (angle z2))))
Complex Arithmetic - 4
We may choose to implement complex numbers in
polar form instead of rectangular form.
(define (make-polar r a) (cons r a))
(define (make-rect x y)
(cons (sqrt (+ (square x) (square y))) (atan y x)))
The discipline of data abstraction ensures that the
implementation of complex-number operators is
independent of which representation we choose.
Manifest Types
A data object that has a type that can be recognized
and tested is said to have manifest type.
(define (attach-type type contents)
(cons type contents))
For complex numbers,
we have two types rectangular & polar
Manifest Types
(define (type datum)
(if (not (atom? datum))
(car datum)
(error “Bad typed datum – Type ” datum)))
(define (contents datum)
(if (not (atom? datum))
(cdr datum)
(error “Bad typed datum – Contents ” datum)))
Complex Numbers
(define (make-rect x y)
(attach-type ‘rect (cons x y)))
(define (make-polar r a)
(attach-type ‘polar (cons r a)))
(define (rect? z)
(eq? (type z) ‘rect))
(define (polar? z)
(eq? (type z) ‘polar))
Complex Numbers
(define (real-part z)
(cond ( (rect? z)
(real-part-rect (contents z)))
( (polar? z)
(real-part-polar (contents z)))))
(define (imag-part z)
(cond ( (rect? z)
(imag-part-rect (contents z)))
( (polar? z)
(imag-part-polar (contents z)))))
Complex Numbers
(define (real-part-rect z) (car z))
(define (imag-part-rect z) (cdr z))
Let Expressions
(let ((a 4) (b -3))
(let ((a-squared (* a a))
(b-squared (* b b)))
(+ a-squared b-squared)))
25
Let Expressions
(let ((x 1))
(let ((x (+ x 1)))
(+ x x)))
4
Let Expressions
Shadowing may be avoided by choosing different
names for variables. The expression above
could be rewritten so that the variable bound
by the inner let is new-x.
(let ((x 1))
(let ((new-x (+ x 1)))
(+ new-x new-x)))
4
Lambda Expressions
((lambda (x) (+ x x)) (* 3 4)) ⇒ 24
Because procedures are objects, we can establish a
procedure as the value of a variable and use the
procedure more than once.
(let ((double (lambda (x) (+ x x))))
(list (double (* 3 4))
(double (/ 99 11))
(double (- 2 7)))) ⇒ (24 18 -10)
Lambda Expressions
(let ((double-any (lambda (f x) (f x x))))
(list (double-any + 13)
(double-any cons 'a))) ⇒ (26 (a . a))
Lambda Expressions
(define double-any
(lambda (f x)
(f x x)))
The variable double-any now has the same status as cons or the
name of any other primitive procedure. We can use doubleany as if it were a primitive procedure.
(double-any + 10) ⇒ 20
(double-any cons 'a) ⇒ (a . a)
Lambda Expressions
(map abs '(1 -2 3 -4 5 -6)) ⇒ (1 2 3 4 5 6)
(map cons '(a b c) '(1 2 3)) ⇒ ((a . 1) (b . 2) (c . 3))
(map (lambda (x) (* x x)) '(1 -3 -5 7)) ⇒ (1 9 25 49)
Lambda Expressions
(define map1
(lambda (p ls)
(if (null? ls)
'()
(cons (p (car ls))
(map1 p (cdr ls))))))
(map1 abs '(1 -2 3 -4 5 -6)) ⇒ (1 2 3 4 5 6)
Lambda Expressions
(let ((x 'a))
(let ((f (lambda (y) (list x y))))
(f 'b))) ⇒ (a b)
The occurrence of x within the lambda expression refers to the x
outside the lambda that is bound by the outer let expression.
The variable x is said to occur free in the lambda expression or
to be a free variable of the lambda expression.
The variable y does not occur free in the lambda expression
since it is bound by the lambda expression.
Free & Bound Variables
> (occurs-free? ’x ’x)
#t
> (occurs-free? ’x ’y)
#f
> (occurs-free? ’x ’(lambda (x) (x y)))
#f
> (occurs-free? ’x ’(lambda (y) (x y)))
#t
> (occurs-free? ’x ’((lambda (x) x) (x y)))
#t
> (occurs-free? ’x ’(lambda (y) (lambda (z) (x (y z)))))
#t
Free & Bound Variables
We can summarize these cases in the rules:
• If the expression e is a variable, then the variable x occurs
free in e if and only if x is the same as e.
• If the expression e is of the form (lambda (y) e), then the
variable x occurs free in e if and only if y is different from x
and x occurs free in e.
• If the expression e is of the form (e1 e2), then x occurs free in
e if and only if it occurs free in e1 or e2. Here, we use “or”
to mean inclusive or, meaning that this includes the
possibility that x occurs free in both e1 and e2. We will
generally use “or” in this sense.
Free & Bound Variables
(define occurs-free?
(lambda (var exp)
(cond
((symbol? exp) (eqv? var exp))
((eqv? (car exp) ’lambda)
(and (not (eqv? var (car (cadr exp))))
(occurs-free? var (caddr exp))))
(else
(or
(occurs-free? var (car exp))
(occurs-free? var (cadr exp)))))))