[2/8/99] =============================================================================== * IMPORTANT (& constant) NOTE: USE THE NEWSGROUP! =============================================================================== * Note about PS#1 question 4 - this is a very easy exercise, all you have to do to do it is to avoid "standard" (C/C++/Java) thinking and go into functional mode thinking. =============================================================================== * In PS#1 - the generator is responsible _only_ for the breaking of a line segment into several - so, for example, the side parameter should never be touched by it - it exists only to be passed back on to side. This property of functions has a name - "cohesion" - procedures with strong cohesion are procedures that have a body that is doing things related to one aspect. [real-world] example for strong cohesion: A car has a component that contains all of the widgets that supply the information needed for driving, and another place for all the "extra" stuff (A/C, radio etc). =============================================================================== * At this stage some people are confused, thinking that we are doing things that are really strange and different from "normal" languages. This is not true - what we are using is actually normal programming, here is an example: SCHEME C++/Java -------------------- (define (side len lev) void side( int len, int lev ) { (if (<= lev 0) if (lev <= 0) (draw len) draw(len); (begin else { (side (/ len 3) (- lev 1)) side(len/3, lev-1); (turn -60) turn(-60); (side (/ len 3) (- lev 1)) side(len/3, lev-1); (turn 120) turn(120); (side (/ len 3) (- lev 1)) side(len/3, lev-1); (turn -60) turn(-60); (side (/ len 3) (- lev 1))))) side(len/3, lev-1); } } (define (fact n) int fact( int n ) { (if (zero? n) if (n == 0) 1 return 1; (* n (fact (- n 1))))) else return n * fact(n-1); } (define (fact0 n a) int fact0( int n, int a ) { (if (zero? n) if (n == 0) a return 1; (fact0 (- n 1) (* n a)))) else return fact0(n-1, n*a); } (define (fact n) (fact0 n 1)) int fact( int n ) { return fact0(n, 1); } -------------------- Differences between the Scheme code and the C++ code: + The syntax is very different, but this is _just_ syntax - you could define a C++-like language using Scheme syntax, and you could define a Scheme-like language using C++ Syntax (e.g, Javascript). + Every expression returns a value, so naturally, there is no need for a "return" statement. (The difference between the C++ "if" statement and its ternary "? :" operator). Of course, some expressions are such that we don't care about their return values, such expressions are said to return unspecified values (e.g, the result of a define expression). + Types are not attached to _variables_, but to _values_. Therefore type checking is done at run-time. Note - standard C also has no types, actually no types at all: everything is just a number (e.g, the value of strings is actually a pointer to the character array). + One feature of the functional approach in Scheme is what makes a big difference - the using values as normal ("first-class") objects. We even have the ability to create and use anonymous functions. This might be hard to get used to, but it gives us great power. The idea of using functions as values is becoming more and more popular these days, for example, Javascript treats functions (example below). =============================================================================== * Formal evaluation examples - the last example from the class notes, use those slides. When looking at them, it looks like we're doing some math instead of running a program, so describe the general operations that these rules dictate, for example, we say: -------------------- {} |- (define z 1) ==> {z := 1} by rule 6 because {} |- 1 => 1 by rule 1 -------------------- A more straightforward way would be to say: -------------------- * To evaluate (define z 1) in the empty environment, evaluate 1 (in this environment) first and get a new environment binding z to this value. * Evaluating 1 returns 1 * So now continue using an environment using 1 as z's binding. -------------------- =============================================================================== * Passing functions as values - simple example: -------------------- (define (f g) (g 2 3)) (f +) ==> 5 (f *) ==> 6 (f (lambda (x y) (+ (square x) (square y)))) ==> 13 -------------------- Note - here is the last example in Javascript: -------------------- function f(g) { return g(2,3); } function square(x,y) { return x*x + y*y; } f(square) ==> 13 -------------------- A note - you can go over these examples using the formal reduction rules and they will work fine. =============================================================================== * Generalizing code example - an important technique - used in PS#1: -------------------- (define (f x) (+ x 1)) (f 3) ==> 4 -------------------- That can be generalized to add something other than 1 by simply turning it into a variable: -------------------- (define (f x y) (+ x y)) (f 3 2) ==> 5 -------------------- We can even generalize a function and use that as an argument: -------------------- (define (f x g) (g x 1)) (f 3 +) ==> 4 (f 3 -) ==> 2 (f 3 (lambda (x y) (+ (square x) (square y)))) ==> 10 -------------------- A more complicated example: -------------------- (define (square-deriv x) (/ (- (* (+ x 0.0001) (+ x 0.0001)) (* x x)) 0.0001)) -------------------- Note that square is not a Scheme built-in - we should define it: -------------------- (define (square x) (* x x)) -------------------- We can generalize the dx argument to get: -------------------- (define (square-deriv x dx) (/ (- (square (+ x dx)) (square x)) dx)) -------------------- And we could further generalize the square function away: -------------------- (define (deriv f x) (/ (- (f (+ x dx)) (f x)) dx)) -------------------- =============================================================================== * The "let" form, and the way it is almost equivalent to a lambda form -------------------- (let ((x 1) (y 2)) (+ x y)) vs. ((lambda (x y) (+ x y)) 1 2) -------------------- A problem: -------------------- (let ((f (lambda (n) (if (zero? n) 1 (* n (f (- n 1))))))) (f 3)) -------------------- doesn't work because the way that let is defined (its semantics that we get be the semantics of lambda abstraction and application) - here's an example why: -------------------- ((lambda (f) (f 3)) (lambda (n) (if (zero? n) ...))) ((lambda (n) (if (zero? n) ...)) 3) (if (zero? 3) ... f...) -------------------- And it is clear now that f is unbound. =============================================================================== * All Induction materials will be introduced in class. =============================================================================== * Induction: A first simple & quick mathmatical example: Prove that Sum(1..n) = (n^2+n)/2 - using the recipe given in class: INDUCTION RECIPE:

+ What variable n are you doing induction on? + What is the property P[n]? + Prove base case, typically P[0]. + Assume P[m], prove P[m+1] (sometimes write n instead of m). Our proof: + The induction is on the number n. + The property is P(n): Sum(1..n) = (n^2+n)/2, for all n's from 1 on. + Base case - here we have 1 as the base case (but could also use 0): 1 = Sum(1..1) = (1^2+1)/2 = 1 + Assume Sum(1..n) = (n^2+n)/2, should show Sum(1..n+1) = ((n+1)^2+(n+1))/2: Sum(1..n+1) = 1 + ... + n + n+1 = Sum(1..n) + n + 1 = (n^2+n)/2 + n + 1 ==> Here we're using the assumption = (n^2+n)/2 + (2n+2)/2 = (n^2 + 3n + 2)/2 but: ((n+1)^2+(n+1))/2 = (n^2 + 1 + 2n + n + 1) / 2 = (n^2 + 3n + 2)/2 And we're done. =============================================================================== * There's a strong correspondence between any [constructive] proof and a program that actually implements it - when you solve a problem by writing a program, you're actually doing the same job as _proving_ that there is a solution. An example of this matching will relate an inductive proof and a recursive program: The problem is the Towers of Hanoi: Initial state: Three piles of discs, each disc has a unique diameter, they are initially piled from the biggest on the bottom to the smallest on the top - on pile #1. Task: Move all to pile #3 Rules: - Can move only one disc at a time - Can only move the top disc of a pile to the top of another - Can't put a disc on a smaller one. The proof is trivial - and directly corresponds to a recursive program: -------------------- (define (solve-hanoi n-discs from-pile to-pile help-pile) (if (= n-discs 1) (move-disc 1 from-pile to-pile) (begin ; This uses side-effect... (solve-hanoi (- n-discs 1) from-pile help-pile to-pile) (move-disc n-discs from-pile to-pile) (solve-hanoi (- n-discs 1) help-pile to-pile from-pile)))) (define (hanoi n) (solve-hanoi n 1 3 2)) -------------------- =============================================================================== * Strong-induction is very similar to what we saw (weak induction) - but here we have a different recipe: STRONG INDUCTION RECIPE: + What variable n are you doing induction on? + What is the property P(n)? + Assume P(0), P(1), ... P(n), prove P(n+1). Use that to prove a more general Hanoi problem - same task & goal, but the initial state is all discs are spread randomly on all piles. [This is too long to show as a program - just go over the proof.] Idea: Locate the biggest disc, "hide" it and whatever beneath it, Arrange all of the rest on another pile (using the assumption), move the biggest to the last (now empty) pile, pile the rest on top of it (again, using the assumption). A difference that we have here - we didn't had any "base case" to check - but our "induction step" was supposed to work also if the assumption is vacuously true. ===============================================================================