I. procedures (Little Schemer, Chapter 8) A. as data ------------------------------------------ PROCEDURES Values + abstract: partial mappings from a domain to a range with side-effects on store + external (printed) form: in SCM: # # in Chez Scheme: # in Dr. Scheme: # or # Operations + procedures: apply + special forms: lambda, ______ ------------------------------------------ B. creation ------------------------------------------ LAMBDA MAKES PROCEDURE VALUES examples: (lambda (n) (+ n 1)) (lambda (x y) (/ (+ x y) 2)) terminology: - closure - formal, formal parameter, bound variable - anonymous procedure ------------------------------------------ What other langauges use anonymous procedures? ------------------------------------------ USE OF ANONYMOUS PROCEDURES > ((lambda (n) (+ n 1)) 3) 4 > (map (lambda (n) (+ n 10)) '(4 5 6)) (14 15 16) ------------------------------------------ C. naming ------------------------------------------ NAMING PROCEDURES (deftype one number) (define one 1) (deftype add1 (-> (number) number)) (define add1 (lambda (n) (+ n one))) ------------------------------------------ D. first-class values ------------------------------------------ FIRST-CLASS VALUES def: a value is *first-class* if it can be Examples of types with first-class values: type FORTRAN C Scheme number boolean array record pointer procedure ------------------------------------------ Are procedures first-class values in FORTRAN? C? Scheme? Are arrays first-class values in C/C++? 1. uses of first-class procedures ------------------------------------------ AN EXAMPLE: COMPOSE Want procedure ((compose car cdr) '(a b c)) = b = (car '(b c)) = (car (cdr '(a b c))) ((compose not null?) '()) = #f = (not (null? '())) ((compose not zero?) x) = (not (zero? x)) In general: ((compose f g) x) = (f (g x)) How to write this: ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write a procedure twice (deftype twice (forall (T) (-> ((-> (T) T)) (-> (T) T)))) Examples: ((twice not) #t) = #t = (not (not #t)) ((twice (lambda (n) (+ n 1))) 3) = 5 = ((lambda (n) (+ n 1)) ((lambda (n) (+ n 1)) 3)) ------------------------------------------ 2. currying (pp. 26-28) ------------------------------------------ CURRYING procedure: (lambda (ls1 ls2 ls3) (append ls1 (append ls2 ls3))) ;; TYPE: (forall (T) ;; (-> ((list-of T) (list-of T) ;; (list-of T)) ;; (list-of T))) curried form: (lambda (ls1) (lambda (ls2) (lambda (ls3) (append ls1 (append ls2 ls3))))) ;; TYPE: (forall (T) ;; (-> ((list-of T)) ;; (-> ((list-of T)) ;; (-> ((list-of T)) ;; (list-of T))))) procedure: (lambda (x y) (+ x y)) ;; TYPE: (-> (number number) ;; number) curried form: (lambda (x) (lambda (y) (+ x y))) ;; TYPE: (-> (number) ;; (-> (number) ;; number)) ------------------------------------------ How is the type of the curried form related to the original type? ------------------------------------------ CURRYING IN C++? #include typedef int (*func)(int); int takes_y(int y) { return(x + y); } func cadd(int x) { return(&takes_y); } int main() { cout << (cadd(2))(3) << endl; } ------------------------------------------ does this work? ------------------------------------------ CORRECTED C++ PROGRAM #include typedef int (*func)(int, int); class closure { public: closure(int x_val, func f_val) : x(x_val), f(f_val) {} int call(int arg) { return f(x, arg); } private: const int x; const func f; }; int add(int x, int y) { return x + y; } closure* cadd(int x) { return new closure(x, add); } int main() { cout << cadd(2)->call(3) << endl; } ------------------------------------------ So, in general, what in C++ is like a closure? E. uses of curried procedures ------------------------------------------ GRAVITATIONAL FORCE EXAMPLE (define G ;; TYPE: N * m^2 / kg^2 6.670e-11) (define square ;; TYPE: (-> (m) m^2) (lambda (r) (* r r))) (define grav-force ;; TYPE: (-> (kg m kg) N) (lambda (m1 r m2) (if (zero? r) 0.0 (/ (* G (* m1 m2)) (square r))))) (define grav-force-c ;; TYPE: (-> (kg) ;; (-> (m) ;; (-> (kg) ;; N))) (if (zero? r) 0.0 (/ (* G (* m1 m2)) (square r)))) ------------------------------------------ ------------------------------------------ USING IT (define mass-of-earth ;; TYPE: kg 5.96e24) (define radius-of-earth ;; TYPE: m 6.37e6) (define earths-force ;; TYPE: (-> (grav-force-c mass-of-earth)) (define force-at-surface ;; TYPE: (-> (earths-force radius-of-earth)) > ;;; force in N on me (force-at-surface 77) > ;;; force in N on 1kg (a liter of coke) (force-at-surface 1) ------------------------------------------ how would you compute forces at distance of moon's orbit by earth? how would you compute forces exerted by the sun? F. variable arity procedures (1.3.3) ------------------------------------------ VARIABLE ARITY PROCEDURES (1.3.3) def: arity = the number of arguments a procedure can take Examples built-in to Scheme: Special form in Scheme: (lambda x body) (deftype sum (-> (number ...) number)) (define sum (deftype sum-of-list (-> ((list-of number)) number)) (define sum-of-list (lambda (lon) (if (null? lon) 0 (+ (car lon) (sum-of-list (cdr lon)))))) Semantics - caller's arguments made into list - the formal denotes a list in the body ------------------------------------------ What in C is like this? does a language have to have these? does language have to allow you to write them yourself? ------------------------------------------ FOR YOU TO DO Implement the following: (deftype product (-> (number ...) number)) (product ) ==> 1 (product 3) ==> 3 (product 4 3) ==> 12 (product 7 6 5 4) ==> 840 (deftype list (forall (T) (-> (T ...) (list-of T)))) (list ) ==> () (list 'a) = (a) (list 'a 'b) = (a b) ------------------------------------------ Does list have to be built-in to Scheme? --------------------------------------------------------- UNRESTRICTED LAMBDA AND APPLY ((lambda args (f args)) e1 e2 ...) = (f (list e1 e2 ...)) (apply f (list e1 e2 ...)) = (f e1 e2 ...) So, for all procedures f and lists ls: (apply (lambda args (f args)) ls) = (f ls) ---------------------------------------------------------