I. data types in Scheme A. Scheme universe of types do any not do that? What's the advantage? ------------------------------------------ THE SCHEME TYPE UNIVERSE (not to scale) datum !------------------!=================-! ! boolean ! null ! ! ! !-----------!------! list ! ! ! !_______________________! ! ! char ! pair ! !-----------!-------------------------! ! ! ! ! number ! procedure ! ! ! ! !--------!-----------------!----------! !string / ! \ port ! ! / ! \ ! ! / symbol ! vector \ ! !-------------------------------------! ------------------------------------------ B. characteristics What characterizes (specifies) an Abstract Data Type (ADT)? ------------------------------------------ CHARACTERISTICS OF DATA TYPES IN PROGRAMMING LANGUAGES Characteristics - Values + abstract + external (printed form) - Operations + procedures + syntax of literals + special forms --------------------------------------------------------- 1. booleans --------------------------------------------------------- EXAMPLE, THE BOOLEANS - Values - Operations + procedures: not, eqv? + syntax of literals: #t, #f + special forms: if, cond, and, or ------------------------------------------ 2. numbers Can you write a procedure "mod7" that returns the result of taking its argument modulo 7? 3. strings ------------------------------------------ STRINGS Values + abstract: finite sequences of chars + printed: "a string", "\"hi\"" Operations + procedures: string, string-append, string-ref (0 based), string-length, string=?, string-ci=?, string?, string<=?, ... string-ci?, ... substring, ... + syntax of literals: "a string" ------------------------------------------ 4. symbol ------------------------------------------ SYMBOLS Values: + abstract: nonempty finite sequences of characters + printed: a-symbol, mySymbol, +, append!, ... Operations: + procedures: eqv?, eq? (fast equality test) + special forms: quote, ' (quote a-symbol) 'a-symbol '+ 'if 'lambda 'quote ------------------------------------------ 5. lists a. summary of lists ------------------------------------------ LISTS (list-of T) Values + abstract: finite sequences of T + printed: (), (a b), (c d e), ... Operations + procedures: cons, car, cdr, null? length, append, list, ... + syntax of literals: '(), '(a b), ... Examples: '(1 2) = (list 1 2) = (cons 1 (cons 2 '())) BOX AND POINTER VIEW DOT NOTATION VIEW !-----------! ( . ) ! | ! car cdr !-----------! car cdr (cons 1 (cons 2 '())) ------------------------------------------ b. proper list examples can you write a procedure to return the second element of a list? how would you test that? can you write a procedure to return the third element of a list? Can you write yodaize? 6. pairs (improper lists) ------------------------------------------ PAIRS vs. LISTS def: a *pair* (or cons cell) is def: A *list* is def: an *improper list* is a pair that is not ------------------------------------------ So is list a subset of pair? Is null a subset of list? is an improper list a list? ------------------------------------------ DOT NOTATION Quotation '(a b c) = (list 'a 'b 'c) = '(1 . 2) = ------------------------------------------ ------------------------------------------ FOR YOU TO DO DOT NOTATION EQUIVALENTS value printed as expression dotted list ========================================= '() () () (cons 1 '()) (1 . ()) (1) (cons 1 (cons 2 '())) (cons 1 2) (cons (cons 1 '()) '()) ------------------------------------------ What's the dot notation for: (cons 4 (cons 5 6)) (cons 'a 'b) ? 7. vectors ------------------------------------------ VECTORS (vector-of T) Values + abstract: finite sequences of cells containing T objects + printed: #(), #(a b), #(c d e), ... or #0(), #2(a b), #3(c d e), ... Operations + procedures: vector, make-vector, vector-ref, vector-set!, vector-length, ... + syntax of literals: '#(), '#(a b),... Examples ------------------------------------------ C. equality predicates --------------------------------------------------------- EQUALITY PREDICATES > (eq? (cons 1 '()) (cons 1 '())) #f > (equal? (cons 1 '()) (cons 1 '())) #t > (equal? (vector 1 2 3) (vector 1 2 3)) #t > (eq? (vector 1 2 3) (vector 1 2 3)) #f > (eq? 9876543210 9876543210) #f > (equal? 9876543210 9876543210) #t --------------------------------------------------------- II. Expressions in Scheme (and other languages) A. fundamental expressions ------------------------------------------ SYNTACTIC PARTS OF A PROGRAMMING LANGUAGE program definition statements expressions literals (#t, #\c, "a str") variable references (x, ls) procedure calls ( (f x), (car ls) ) ------------------------------------------ What's the translation of 5 + 6 + 7 into Scheme? How would sqrt(cos(x + 5)) be translated into Scheme? What's the syntax of a procedure call in Scheme? What's a rule for forming the Scheme from the algebraic notation? B. definitions, programs, read-eval-print loop (quickly) 1. definitions ------------------------------------------ DEFINITIONS Scheme syntax examples (define pi ; TYPE: number 3.14159) Terminology: - special form - keyword ------------------------------------------ What is like this in C++? Pascal? 2. programs ------------------------------------------ PROGRAMS Scheme syntax: a series of definitions and expressions Example (define pi 3.14159) (define greeting "Welcome!") (define is-pi? (lambda (n) (= n pi))) (display greeting) (newline) (is-pi? pi) Semantics: Terminology - top level (pi vs. n) ------------------------------------------ ------------------------------------------ READ-EVAL-PRINT LOOP What the interpreter does (exit) ---> read ----> ^ \ / v print eval ^-----/ ------------------------------------------ C. if-expressions (1.1.3) ------------------------------------------ IF-EXPRESSIONS Transcript of Scheme examples > (if #t 3 4) > (define x 2) > (if (zero? x) (+ x 3) x) > (if (< x 0) (- x) x) ------------------------------------------ So what's the Scheme syntax? Is the else-part required? Why would it be? How does this differ from an if statement in C++ or Java? What's this like in C/C++/Java? Anything like this in Visual Basic? III. procedures 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: # 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))) (deftype map (forall (S T) (-> ((-> (S) T) (list-of S)) (list-of T)))) (define map (lambda (proc ls) (if (null? ls) '() (cons (proc (car ls)) (map proc (cdr ls)))))) ------------------------------------------ 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) ---------------------------------------------------------