;;
;;
;; Week 1.2 - Higher-order Procedures
;;
;;
;;
;; First, Truth and Falsity.
;; o Definitions can vary amoung languages
;; o In scheme:
;; o #f is false
;; o Everything else is true (#t, 3, 0, (), +)
;;
;; TODAY: Generalization
;; o A powerful mechanism to make programming easier.
;; o Other langauges make generalization difficult
;; o In scheme, we use higher-order
;; procs to generalize operations
;; o higher-order procs are possible due
;; to first-class functions
;; First-class functions
;; o (Almost) unique to scheme
;; o Means:
;; 1 Functions as value of a variable
;; 2 Functions as actual argument value
;; 3 Functions as return values
;; 4 Functions in aggregates
;; 1. Value of variable:
(define plus +)
(plus 1 2)
(define - +)
(- 1 2)
;; 2. Function as AA Value
;; Easy
(if #t + -)
;; Harder
(define (square x) (* x x))
(define (squares s)
(if (empty? s)
s
(se (square (first s))
(squares (bf s)))))
(squares '(1 2 3 4))
(define (cube x) (* x x x))
(define (cubes s)
(if (empty? s)
s
(se (cubes (first s))
(cubes (bf s)))))
(squares '(1 2 3 4))
;; Generalize the pattern:
(define (every func sent)
(if (empty? sent)
sent
(se (func (first sent))
(every func (bf sent)))))
(every square '(1 2 3 4))
(every cube '(1 2 3 4))
;;
;; Another example:
;;
(define (keep-numbers sent)
(cond ((empty? sent) sent)
((number? (first sent)) (se (first sent)
(keep-numbers (bf sent))))
(else (keep-numbers (bf sent)))))
(keep-numbers '(greg 4 carolen 10 alex))
(define (keep-evens sent)
(cond ((empty? sent) sent)
((even? (first sent)) (se (first sent)
(keep-evens (bf sent))))
(else (keep-evens (bf sent)))))
(keep-evens '(1 2 3 4 5 6 7 8))
;; Generalize ...
(define (keep pred? sent)
(cond ((empty? sent) sent)
((pred? (first sent)) (se (first sent)
(keep pred? (bf sent))))
(else (keep pred? (bf sent)))))
(keep number? '(greg 4 carolen 10 alex))
(keep even? '(1 2 3 4 5 6 7 8))
;;
;; Of course, we can hook these together to do interesting things:
;;
(every square (keep number? '(greg 4 carolen 10 alex)))
;; 3. Return value of another function
;; o So far, we can do ...
(if #t + -)
;; o Limited by having to use functions
;; that are already defined.
;; o Could be much more powerful if we could
;; create procedures inside of functions
;; (Not just top-level)
;;
;; UNNAMED FUNCTIONS
;;
;; o Create functions on-the-fly
;; o New Special Form: lambda
;; o Form: (lambda (args) body)
;; o Returns a procedure
;; o Use anywhere you can use a procedure
(lambda (x) (* x x))
((lambda (x) (* x x)) 3)
((if #f
(lambda (x) (* x x))
(lambda (x) (+ x x)))
3)
;; The truth about define:
(define (foo alex) (+ alex 1))
;; ==
(define foo (lambda (alex) (+ alex 1)))
;; First-Class Data
;; 3. Functions as return values, cont.
;; Involved example: compose
(define (square x) (* x x))
(define (double x) (+ x x))
(square (double 4))
(double (square 4))
;; Generalize ...
(define (compose f g)
(lambda (x) (f (g x))))
(define sd (compose square double))
(define ds (compose double square))
(define ss (compose square square))
(sd 4)
(ds 4)
;;
;; Aside: why not (define (sd) (compose square double))?
;;
;; translates to:
(define sd (lambda () (compose square double)))
(sd 4)
((sd) 4)
;;
;; Functions as return values
;;
(define (1+ x) (+ x 1))
(every 1+ '(1 2 3 4 5))
(define (2+ x) (+ x 2))
(every 2+ '(1 2 3 4 5))
;; simplify ... use unnamed
(every (lambda (x) (+ x 1)) '(1 2 3 4 5))
(every (lambda (x) (+ x 2)) '(1 2 3 4 5))
;; generalize further ...
(define (make-adder n) (lambda (x) (+ n x)))
(define 1+ (make-adder 1))
(1+ 3)
(every (make-adder 1) '(1 2 3 4 5))
(every (make-adder 100) '(1 2 3 4 5))
;;
;; Combine it all together:
;;
;; More Predicates:
(define (5< x)
(< 5 x))
(5< 6)
(5< 4)
(define (even-and-5