Scheme_1_Elements.ppt
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 1!
!
Elements of Functional Programming!
Abelson & Sussman & Sussman chapter 1.1
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 2!
!
APP – Part A – A deeper look at programming!
• In this part of APP we use the language Scheme to explore:
– Functional programming
– Programming in general
• We can only scratch the surface but we will look at:
– Functional programming in Scheme.
– Building data abstractions.
– Modularity, Objects and state.
• These topics correspond to chapters 1, 2 and 3 of the
textbook (over 350 pages!!).
• We will skip some sections (phew!).
– But the skipped parts still make interesting reading.
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 3!
!
Getting started with Scheme!
• Scheme is an interpreted language.
• To start the interpreter type:
scheme!
!
• The following prompt should appear
1 ]=>!
!
• The scheme interpreter is now waiting for us to type in some
expressions.
• NOTE: this shows use of MIT Scheme (used in SICP), as installed on
CATS computers – we will also show you DrRacket, which you can
install on your own machine
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 4!
!
Expressions in Scheme!
• Scheme is a (mostly) functional languages.
• As with all functional languages computation consists of the
evaluation of expressions.
– e.g. (+ (* 4 3) (- 6 4)) => (+ 12 2) => 14
• Note that all Scheme functions are prefix.
– keeps things simple but you have to draw lots of brackets.
• To get Scheme to evaluate an expression you just type that
expression in:
1 ]=> (+ (* 4 3) (- 6 4))
• Gives:
;Value: 14!
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 5!
!
If you get into trouble!
• as with all interpreters it is possible to get into trouble:
(+ 3 true)!
error in eval loop!
2 error>
• This is Scheme asking for debug commands.
• To get back to the normal prompt type Control-C (twice)
• To get out of the system entirely type control-D at the
normal prompt
End of Input Stream reached
Happy Happy Joy Joy!
• Scheme likes that.
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 6!
!
Definitions in Scheme (A&S1.1.2)!
• Scheme has a rich set of primitive operations.
– If all we could do is evaluate expressions containing these
operations then scheme would be a sophisticated calculator.
– Fortunately, as with most languages, we can extend this set of
operations.
• Scheme also lets programmers add their own operations
• in a file test.scm:
(define size 2)!
• at our scheme prompt
(load “test.scm”)
…
size
2!
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 7!
!
More definitions in scheme!
• Some more definitions:
(define pi 3.14159)!
(define radius 10)!
• We can write expressions in terms of our definitions:
(* pi (* radius radius))
• We can write other definitions in terms of our definitions:
(define circumference (* 2 (* pi radius)))!
• Upon evaluation
circumference!
62.8318!
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 8!
!
Defining functions!
• Define can also be used to define functions:
(define (square x) (* x x))!
(define (sum-of-squares x y)(+ (square x)(square y))!
• at the command prompt
(sum-of-squares 3 4)
25!
• More definitions
(define (first x y) x) ;fn returning its first arg!
(define (const0) 0) ;a constant function!
• At the prompt
(first (const0) 3)!
0
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 9!
!
More language elements!
• For a language to be complete, a programmer must be
allowed to specify:
1. a sequence of computations.
2. conditional computation.
3. repetitive computation.
• We have already seen how Scheme supports the first of
these, indirectly, through evaluation of simple expressions.
• Scheme supports the second using primitives if and cond
– explained next slide.
• Scheme supports the third using recursive definitions
– explained after that.
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 10!
!
Conditional Expressions!
• Scheme provides an if expression:
(define (abs x)
(if (< x 0)
(- x)
x))!
• And a cond expression:
(define (abs x)
(cond ((< x 0) (- x))
((= x 0) x)
((> x 0) x)))!
• Alternatively:
(define (abs x)
(cond ((< x 0) (- x))
(else x )))!
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 11!
!
Conditional expressions!
• Conditional expressions are supported by the usual boolean
operators:
– and, or and not
• Examples:
(and (< 3 4) (= 2 3))!
(or (and (< 3 4) (= 2 3)) (= 5 5))!
(define (>= x y) (or (> x y) (= x y)))!
(define (>= x y) (not (< x y))!
!
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 12!
!
Repetition!
• In Scheme, repetition is expressed using recursive
definitions.
• Examples:
(define (factorial x)
(if (= x 0)
1
(* x (factorial (- x 1)))))!
(define (log2 x)
(if (< x 2)!
0
(+ 1 (log2 (/ x 2))))!
!
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 13!
!
Substitution model of evaluation(A&S 1.1.5)!
• Functions are applied to their arguments.
• To do this:
1. Arguments are evaluated
2. Arguments are substituted into the function body
3. The function body is evaluated.
• Example:
(sum-of-squares 4 3) =>
(+ (square 4) (square 3)) =>
(+ (* 4 4) (square 3)) =>
(+ 16 (square 3)) =>
(+ 16 (* 3 3)) =>
(+ 16 9) => 25
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 14!
!
Applicative vs Normal order evaluation!
• Scheme expressions are (by default) evaluated in
applicative order.
• That is: leftmost-innermost
– Most programmers are familiar with this order.
• There are other evaluation orders.
• Normal order is an important one: leftmost-outermost
– Example of this on next slide.
• Is order important?
– In functional programs the result is not affected by evaluation order.
However….
• Order will sometimes determine whether we get a result at
all! – see next.
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 15!
!
Applicative vs. Normal Order evaluation!
• Example – we have the definitions:
(define (forever a) (forever a))!
(define (first x y) x)!
• Now, evaluate (first 3 (forever 2)) in applicative order:
(first 3 (forever 2)) => {definition of forever}
(first 3 (forever 2)) => {definition of forever}
(first 3 (forever 2)) => …. computation never stops
• Now evaluate same expression in normal order:
(first 3 (forever 2)) => {definition of first}
3
• Normal order terminated and Applicative order didn’t
– normal order evaluated first first rather than forever first
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 16!
!
Church-Rosser Theorems 1 and 2!
• Two important theorems about evaluation orders.
• Church-Rosser theorem 1 – you can evaluate a functional
expression in any order and, if you get a result using both
orders, both results will be the same.
– This is a nice theorem – order doesn’t affect our result – one less
thing to worry about.
• Church-Rosser theorem 2 – if evaluation of an expression
can possibly terminate then normal order evaluation of that
expression will terminate.
– If termination is a concern then using normal order gives the best
chance of completion.
– However, applicative order is easy to understand and, often, more
efficient so many languages use applicative order anyway.
• These theorems work only if there are no side-effects.
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 17!
!
Example: Square Roots (A&S 1.1.7)!
• Newtons method for finding square-roots
– guess, divide into original number, average with last guess, continue…
– until the square of the guess is close to the original number.
Guess Quotient Average
1 (2/1) = 2 ((2 + 1)/2) = 1.5
1.5 (2/1.5) = 1.3333 ((1.3333 + 1.5)/2) = 1.4167
1.4167 (2/1.4167) = 1.4118 ((1.4167 + 1.4118)/2) = 1.4142
1.4142
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 18!
!
Square roots!
• The iteration in the previous slide can be implemented as:
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))!
• Define improve:
(define (improve guess x)
(average guess (/ x guess)))!
• Define average:
(define (average x y) (/ (+ x y) 2))!
• Define good-enough?:
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))!
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 19!
!
Square Roots!
• Finally, define the sqrt function to call sqrt-iter with an initial
guess of 1.0.
(define (sqrt x) (sqrt-iter 1.0 x))!
• Note, as with other programming languages there is more
than one way of writing a given function in Scheme.!
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 20!
!
Alternative definition (A&S 1.1.8)!
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))!
• Note the use of local definitions.
• Note the removal of x, the local parameter, from the local
definitions.
• x is now free in the context of the local definitions
– Though it is bound in the context of the outer definition.!
!Advanced Programming Paradigms !!
© 2013 The University of Adelaide/1.0 ! ! ! ! ! !Intro Scheme-3/Slide 21!
!
Exercises: !
• First, satisfy yourself that sqrt works. Then try:
• A&S (SICP) 1.4, 1.5, 1.7