Today's topics:
* Functional Abstraction
* Substitution Model of Evaluation
We've already seen:
* Simple uniform syntax:
(operator operand1 ... operandn)
* Simple evaluation rule:
eval each subform, then apply operator's value to operands'
values.
Example: (/ (* 4 3) (+ 2 1)) ==> 4
* Two special forms: DEFINE and METHOD
So far we have handwaved a lot in understanding the evaluation process --
determining the value of Dylan expressions
- Substitution Model -- formal means of understanding Dylan
expressions (at least ones without assignment, which we wont
use for quite a while). Most critical thing in first half of CS212!
----------------------------------------------------------------------
A method
* Packages up a computation
* Puts a black box around an operation
In some weird way, (* x x) is squaring. Except that this
doesn't quite make sense.
Similarly averaging is (/ (+ x y) 2)
If you want to package squaring or averaging for later use, you need
to
* Tell which variables are involved
* And what order they're in.
Squaring involves one variable, x.
To package it up in Dylan, we use the special form called METHOD (does not
follow the normal evaluation rule)
- METHOD makes a procedure
You saw METHOD in section.
(method ((x <number>)) (* x x))
| | |
| | +--- BODY: an expr to eval once you've got x.
| |
| +--------- PARAMETER LIST: just one param, called x which is a <number>.
|
+--------------- method: the special form that means, make a procedure.
Or, read it as:
* method The method
* ((x <number>)) Taking the number x as the single parameter
* (* x x) Returning the value of the expression (* x x)
NOTE: <number> is one of the pre-defined types in Dylan. Each
name (parameter or variable) has a type.
*** the method form by itself does NO COMPUTATION!
*** It creates an OBJECT which CAN do the computation
*** when used in first position in a combination.
*** computation happens when it is APPLIED (applied means used in
first position in a combination)
(/ 1 0) produces an error
(method () (/ 1 0)) is not an error (yet.) It is a procedure of no arguments!
what makes the second one of these produce an error??
((method () (/ 1 0))) when it is applied (used)
NOTE: creating a procedure (using METHOD) is completely separate
from naming it (using DEFINE).
Dylan != C
----------------------------------------------------------------------
[We also contrast the following --- use if there are questions]
(define (foo <number>) 3)
(define (bar <function>) (method () 3))
foo evaluates to 3
bar evaluates to however Dylan prints out a procedure object
(foo) generates an error, application of a non-procedure object, 3
(bar) evaluates to 3
If you understand these examples, then you are a long way towards
understanding evaluation of simple Dylan expressions.
----------------------------------------------------------------------
Mantra: Everything in Dylan has a value; everything is an expression.
[REPEAT THIS A FEW TIMES]
1's Value is 1
method returns a PROCEDURE OBJECT as its value:
* a method of doing some computation at a later time.
* Putting it in a box
* METHODs (procedures) are first class objects
- Anything you can do with all other values, you can do with
procedures.
- Give them as arguments
- Return them
- Store them in variables
- Put them in data structures
By the evaluation rule, we know how to use a procedure object:
* Put it in the first position of a combination, but this can be
tedious, so we also use DEFINE to name objects
((method ((x <number>)) (* x x)) 5) ==> 25
versus
(define (square <function>) (method ((x <number>)) (* x x)))
(square 5)
has the same meaning! We will get more precise about this in a moment.
NOTE: <function> is another pre-defined type
Now we can use square conveniently too.
(square 5) ==> 25
(square 3) ==> 9
(+ (square 2) (square 3)) ==> 13
*** NOTE: We can now use square just as if it were a primitive operation,
like + - * / etc.
----------------------------------------------------------------------
*** Clean the board here ***
*** And write small ***
Now, we have progressed to the point where we can try implementing
Heron of Alexandria's square root algorithm from last time:
(define (heron-sqrt <function>)
(method ((x <number>))
; Try some guess for sqrt(x)
; we always pick 1.
(try 1 x)))
(define (try <function>)
(method ((guess <number>) (x <number>))
;; If it's good enough guess
(if (good-enough? guess x)
;; Then stop and return the old guess
guess
;; Otherwise, try an improved guess.
(try (improve guess x) x)
)))
(define (good-enough? <function>)
(method ((guess <number>) (x <number>))
(< (abs (- (square guess) x)) 0.0001)))
(define (improve <function>)
(method ((guess <number>) (x <number>))
(/ (+ guess (/ x guess)) 2.0)))
(define (square <function>)
(method ((x <number>))
(* x x)))
*** Leave the code on the board! ***
Note that try is a *recursive* definition, it calls itself.
* We will see that it is actually *iterative*, because
no state is built up on successive recursive calls
* This use of recursion is more like loop, while, and do.
Paid commercial advertisement: There's a difference between recursive
DEFINITIONS (like try) and recursive *processes*. That's for another
lecture though.
----------------------------------------------------------------------
We've snuck in a new beast:
(if test consequent alternate)
is a *special* *form* and doesn't follow the usual evaluation rule (which is,
evaluate all the subexpressions, then apply the first value - the operator -
to the remaining values - the arguments).
IF's special rule is:
1. Evaluate the test
2. If the test is true, evaluate and return the consequent
3. If the test is false,evaluate and return the alternate.
It *only* evaluates one arm.
* You wouldn't want to do both.
What's true?
#t is true
#f is false
In fact, almost anything is true:
#f is the *only* false value
(if #t A B) evaluates to A
What is (if 0 10 20)? 10, of course!
(C can be cured)
MORE ON THIS AND RELATED FORMS IN RECITATION.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
This is *all* we need to write that sqrt procedure!
* No assignment := (Dylan != C)
* No while loops
----------------------------------------------------------------------
From this you can sort of see the processing in sqrt:
*** Go through this out loud, quickly ***
(sqrt 2)
calls
(try 1 2)
calls
(good-enough? 1 2) which returns false,
so do
(try (improve 1 2) 2)
and (improve 1 2)
calls
(average 1 2)
which returns 3/2,
so we call (try 3/2 2) as the new guess.
This is all a little fuzzy; we can be considerably more precise about (and get
a better understanding of) exactly what Dylan expressions do.
A *model* of the *evaluation* *process*:
evaluation - reducing an expression to a value (like 4, for instance)
----------------------------------------------------------------------
We use Substitution Model covered in the handout on the web (available today).
[Get used to checking the web page!]
It is a MODEL:
- A tool to help us understand the values that our procedures
are computing (NOT WHAT THE COMPUTER DOES!)
- It helps us reason about programs.
[This is one of the few things in 212 you should probably memorize!]
There are two basic rules of the model:
1. To *evaluate* a combination (other than a special form), *evaluate*
the subexpressions of the combination, then *apply* the procedure
object that is the value of the leftmost subexpression to the
remaining values.
2. To *apply* a compound procedure to a set of arguments, *evaluate*
the body of the procedure with each argument SUBSTITUTED for the
corresponding parameter.
Notation:
(...) means *evaluation*, Rule 1
[...] means *application*, Rule 2.
We'll draw a box around any object that has already been evaluated,
to distinguish them from symbols that must be evaluated:
*** Use braces here to denote boxes ***
5 is a symbol
{5} is some computer representation of the number 5.
* is a symbol
{mult} is its value, the multiplication function.
The symbol and the computer representation are DISTINCT entities.
Procedure objects need notation:
{proc (params) body}
is the value of (method (params) body)
NOTE: proc is not part of Dylan (any more than mult is).
(method ((<number> x)) (+ x 5)) evaluates to {proc ((<number> x)) (+ x 5)}
----------------------------------------------------------------------
Let's now evaluate (square 5) where square is defined as above.
* square evaluates to {proc ((<number> x)) (* x x)} because
that's the value we defined square to have with define -- by
a special form rule we'll see later.
* 5 evaluates to {5}
Now rule 1 says, apply {proc ((<number> x)) (* x x)} to {5}:
[{proc ((<number> x)) (* x x)} {5}]
by rule 2, this gives us the body of the proc --- (* x x) --- with x
replaced by {5}:
(* {5} {5})
`*' evaluates to {mult}
[{mult} {5} {5}]
We're now beyond the substitution model's rules, because {mult} and {5} are
primitives. All that the substitution model does is tell us how to reduce
expressions to values, these are all values.
Each operation in some sense has its own special-case rules, in this case
mult simply performs multiplication, resulting in
{25}
----------------------------------------------------------------------
Here's a more complicated example:
1. (sqrt 2)
2. [ {proc ((<number> x)) (try 1 x)} {2} ]
3. (try 1 {2})
4. [ {proc ((<number> guess) (<number> x)) ...} {1} {2} ]
*** If is a special form, so we handle it specially (has its own rule
in the model):
5. (if (good-enough? {1} {2})
{1}
(try
(improve {1} {2})
{2})
)
By the rule for if, we first evaluate the test:
[ {proc ((<number> guess) (<number> x)) ...} {1} {2} ]
(< (abs (- (square {1})) {2}) 0.01)
...
#f
Now by the special rule for IF we evaluate the alternative
because the test was false:
6. (try (improve {1} {2}) {2})
We have to evaluate this "inside out" because in order to evaluate
all the subexpressions we need a value for the second subexpression which is
itself a combination. We get this value by
[ {proc ((<number> guess) (<number> x)) ...} {1} {2} ]
(average {1} (/ {1} {2}))
[{proc (a b) (/ (+ a b) 2)} {1} {2}]
(/ (+ {1} {2}) 2)
...
{1.5}
Now we have evaluated each subexpression of (try (improve {1} {2}) {2})
resulting in
[ {proc ((<number> guess) (<number> x)) ...} {1.5} {2}]
Substituting the body of the procedure with values {1.5} and {2}
We're back at something that looks like step 4.
The pattern repeats.
7. (if (good-enough? {1.5} {2})
{1.5}
(try
(improve {1.5}{2})
{2})
The test is #f so by reasoning analogous to above,
(try (improve {1.5}{2}) {2}) evaluates to {1.416667}
8. [ {proc ((<number> guess) (<number> x)) ...} {1.416667} {2} ]
9. (if (good-enough? {1.416667} {2})
{1.416667}
(try (improve {1.416667} {2})))
The test of the if evaluates to #t in this case so
the value is thus {1.416667}
With the Substitution Model, we have a very precise model for
determining the value of expressions....
AT LEAST, FOR NOW. It breaks when we add assignment, but that
won't happen for quite a while. We'll write some complicated
programs without it. That's part of the lesson: you don't need
to depend on assignment as much as you do. Kick the habit.
----------------------------------------------------------------------
Important points in today's lecture:
* Recapped the evaluation rule, DEFINE and METHOD
* Introduced the special form IF --
simple if-then-else conditional
* PROCEDURAL ABSTRACTION: - Put a computational process in a box
METHOD builds the box
Naming is a separate issue, can associate a name using DEFINE
* Substitution Model
- Precise model for evaluating expressions
= Two basic rules:
= To Evaluate a combination,
evaluate subexpressions
apply procedure to arguments
= To apply a compound procedure
Substitute arguments in body
Evaluate body.