I. records (3.4) A. declaration and use (3.4.1) ------------------------------------------ RECORDS (3.4) problem: want to have named, random access to components of heterogeneous collection not random access: ((name "Tom") (age 22) (lang Scheme)) ((name "Sally") (age 23) (lang C++)) not named: #("Tom" 22 Scheme) #("Sally" 23 C++) records: (define-record person (name age lang)) (define tom ; TYPE: person (make-person "Tom" 22 'Scheme)) (define sally ; TYPE: person (make-person "Sally" 23 'C++)) (person->age sally) ==> 23 (person->name tom) ==> "Tom" (person? sally) ==> #t ------------------------------------------ How would you get the langauge that tom works with? What's this like in C? In Pascal? ------------------------------------------ FOR YOU TO DO Write the procedure average-age: (-> (person person) number) Examples: (average-age tom sally) ==> 22.5 (average-age tom (make-person "baby" 0 'baby-talk)) ==> 11 ------------------------------------------ how might these be implemented? ------------------------------------------ RECORD DECLARATION SYNTAX ::= (define-record ( {}* ) ) ::= ::= SEMANTICS (define-record auto (name age)) declares the operations: make-auto : (-> (S T) (auto S T)) auto? : (-> (datum) boolean) auto->name : (-> ((auto S T)) S) auto->age : (-> ((auto S T)) T) i.e., you can write: (define mycar ;; TYPE: (auto symbol number) (make-auto 'honda 7)) (auto? mycar) (auto->name mycar) (auto->age mycar) ------------------------------------------ B. variant records ------------------------------------------ VARIANT RECORDS def: a *union type* is a type that contains values of ______________ different types. def: a *variant record type* is a type that is a union type, in which the contained types are all _________________. ------------------------------------------ What's this like in C? In Pascal? Ada? ------------------------------------------ VARIANT RECORDS FOR MODELING GRAMMARS a. Use records for each "interesting" production Example: ::= (lambda () ) | ( ) | (define-record lambda (formal body)) b. Change the types of the operations ------------------------------------------ ------------------------------------------ A .DEF FILE FOR THIS GRAMMAR ;;; In the file record-lambda-1-exp.def (defrep lambda-1-exp datum) (deftype lambda? (-> (lambda-1-exp) boolean)) (deftype make-lambda (-> (symbol lambda-1-exp) lambda-1-exp)) (deftype lambda->formal (-> (lambda-1-exp) symbol)) (deftype lambda->body (-> (lambda-1-exp) lambda-1-exp)) (deftype varref? (-> (lambda-1-exp) boolean)) (deftype make-varref (-> (symbol) lambda-1-exp)) (deftype varref->var (-> (lambda-1-exp) symbol)) (deftype app? (-> (lambda-1-exp) boolean)) (deftype make-app (-> (lambda-1-exp lambda-1-exp) lambda-1-exp)) (deftype app->rator (-> (lambda-1-exp) lambda-1-exp)) (deftype app->rand (-> (lambda-1-exp) lambda-1-exp)) ------------------------------------------ II. abstract syntax (3.4.3) ------------------------------------------ ABSTRACT SYNTAX (3.4.3) idea: identify each rule in the grammar with a record that a. b. def: *abstract syntax* ignores details of def: *concrete syntax* gives details needed for humans to write and read. CONCRETE SYNTAX OF LAMBDA CALCULUS ::= (lambda () ) | ( ) | | AN ABSTRACT SYNTAX (define-record lambda (formal body)) ------------------------------------------ Can you define an abstract syntax for if expressions? literals? ------------------------------------------ PARSING AND UNPARSING parse concrete ---------> abstract ^ / \----------/ unparse Examples of parse (parse 'x) = (make-varref 'x) ==> #(varref x) (parse '(f x)) = (make-app (make-varref 'f) (make-varref 'x)) ==> #(app #(varref f) #(varref x)) ------------------------------------------ ------------------------------------------ CODE FOR PARSE (define parse ;; TYPE: (-> (datum) ;; lambda-1+number-exp) (lambda (exp) (cond ((number? exp) (make-lit exp)) ((symbol? exp) (make-varref exp)) ((and (list? exp) (= (length exp) 3) (eq? (car exp) 'lambda)) (make-lambda (caadr exp) (parse (caddr exp)))) ((and (list? exp) (= (length exp) 2)) (make-app (parse (car exp)) (parse (cadr exp)))) (else (error "parse: bad syntax in expression:" exp))))) (define parse-lambda-1+number-exp parse) ------------------------------------------ why is the error case there? does that catch all errors? ------------------------------------------ SYNTAX OF VARIANT-CASE ::= (variant-case { ( ) }+ (else )) ::= ::= ( {}* ) ::= ------------------------------------------ ------------------------------------------ UNPARSE USING VARIANT-CASE (define unparse ; p. 85 ;; TYPE: (-> (lambda-1+number-exp) ;; datum) (lambda (exp) (variant-case exp (lit (datum) datum) (else (error "unparse: Invalid abstract syntax" exp))))) ------------------------------------------ ------------------------------------------ EQUIVALENT USING COND (don't do this) (define unparse ; p. 85 ;; TYPE: (-> (lambda-1+number-exp) ;; datum) (lambda (exp) (cond exp ((lit? exp) (lit->datum exp)) ((varref? exp) (varref->var exp)) ((lambda? exp) (list 'lambda (list (lambda->formal exp)) (unparse (lambda->body exp)))) ((app? exp) (list (unparse (app->rator exp)) (unparse (app->rand exp)))) (else (error "unparse: Invalid abstract syntax" exp))))) ------------------------------------------ ------------------------------------------ DETAILS OF THE DESUGARING (variant-case e_0 (name_1 (f_11 ... f_1k) e_1) ... (name_n (f_n1 ... f_nm) e_n) (else e_n+1)) ==> (let ((*record* e_0) (cond ((name_1? *record*) (let ((f_11 (name_1->f_11 *record*)) ... (f_1k (name_1->f_1k *record*))) e_1)) ... ((name_n? *record*) (let ((f_n1 (name_1->f_n1 *record*)) ... (f_nm (name_1->f_nm *record*))) e_n)) (else e_n+1)))) ------------------------------------------ ------------------------------------------ WORKING WITH ABSTRACT SYNTAX USING VARIANT-CASE (free-vars (parse '(lambda (x) (car x)))) ==> (car) FOR YOU TO DO ;;; fill in the rest of this ;;; (define free-vars ;; TYPE: (-> (lambda-1+number-exp) ;; (set symbol)) (lambda (exp) (variant-case exp (lit (datum) the-empty-set) (varref (var) use set-of, set-remove, and set-union ------------------------------------------ A. handling Kleene star or plus (p. 86, bottom) ------------------------------------------ ABSTRACT SYNTAX FOR KLEENE STAR Use a list ::= | | (lambda ({}*) ) | (if ) | ( {}*) (define-record lit (datum)) (define-record varref (var)) (define-record lambda (formals body)) (define-record if (test-exp then-exp else-exp)) (define-record app (rator rands)) (define free-vars ;; TYPE: (-> (lambda+if-exp) ;; (set symbol)) (lambda (exp) (variant-case exp (lit (datum) the-empty-set) (varref (var) (set-of var)) (lambda (formals body) ------------------------------------------ III. data abstraction (3.5) A. terminology ------------------------------------------ DATA ABSTRACTION terms: data abstraction, ADT example: records divide program into 2 parts 1. knows about representation (the ADT) 2. doesn't know details of rep (the client) def: a program exhibits if it works correctly with any correct implementation of an ADT. example: ------------------------------------------ Are C programs independent of the representation of numbers? What good is this? B. opaque vs. transparent implementations ------------------------------------------ OPAQUE VS. TRANSPARENT REPS > (define-record app (rator rand)) > (define my-app (make-app (make-varref 'car) (make-varref 'ls))) > (app? my-app) > (vector? my-app) > my-app def: a type is *opaque* if otherwise it is transparent. ------------------------------------------ which kind does Scheme have? C++? What's the advantage of an opaque type? of transparent? C. type checking and ADTs ------------------------------------------ TYPE CHECKING AND ADTS abstract type (cell T) rep type (vector T) ;;;;; in cell.def (defrep (cell T) (vector T)) (deftype make-cell (-> (T) (cell T))) (deftype cell-ref (-> ((cell T)) T)) ... ;;;;; in cell.scm (define make-cell ;; TYPE: (lambda (x) (vector x))) (define cell-ref ;; TYPE: (lambda (x) (vector-ref x 0))) ------------------------------------------ IV. transforming procedural reps to data structure reps (3.6) A. motivation and overview ------------------------------------------ TRANSFORMING PROCEDURAL REPS TO DATA STRUCTURE REPS (3.6) Why? In semantics, often specify ADTs that are like functions: Idea: represent such an ADT by a _________ if need efficiency, transform to record How? represent the _______'s environment as a record, use the code from the _______ in the operation that "apply"s the record representation ------------------------------------------ ------------------------------------------ PICTURE OF TRANSFORMATION (nnnnnnnnnnnnnnnnnn) ( ) ( ADT ) ( ) (uuuuuuuuuuuuuuuuuu) ^ ^ / \ / \ / \ !---------------! !-----------------! ! procedural rep! ! record rep ! ! ! **> ! ! ! ! ! ! !---------------! !-----------------! ------------------------------------------ B. procedural reps (3.6.1) ------------------------------------------ EXAMPLE: INFINITE SEQUENCES seq = Nat -> number Constructors seq-repeat: (-> (number) seq) seq-generator: (-> ((-> (Nat) number)) seq) seq-add: (-> (seq seq) seq) Observers: seq-nth: (-> (seq Nat) number) Example: > (define ones (seq-repeat 1)) > (seq-nth ones 3) 1 > (define halves (seq-generator (lambda (n) (/ 1 (expt 2 n))))) > (seq-nth halves 0) 1 > (seq-nth halves 1) 0.5 > (seq-nth halves 2) 0.25 > (seq-nth halves 99) 1.577721810442e-30 > (seq-nth (seq-add ones halves) 2) 1.25 ------------------------------------------ how would you represent seqs as closures? ------------------------------------------ INFINITE SEQUENCES AS PROCEDURES (define seq-repeat (lambda (num) (lambda (n) num))) (define seq-generator (lambda (f) (lambda (n) (f n)))) (define seq-nth (lambda (seq n) (seq n))) (define seq-add (lambda (s1 s2) ------------------------------------------ C. record representation (3.6.2) ------------------------------------------ TRANSFORMING TO RECORDS (1) How? 1. Constructors: a record type for each closure's environment (define seq-repeat ; procedural rep (lambda (num) (lambda (n) num))) (define seq-generator ; procedrual rep (lambda (f) (lambda (n) (f n)))) ;;; ... becomes ... (define-record repeated-seq ) (define-record generated-seq ) (define seq-repeat make-repeated-seq) (define seq-generator make-generated-seq) ------------------------------------------ what are the free varrefs in the body of seq-repeat? seq-generator? ------------------------------------------ FOR YOU TO DO Define a record type that is the transform of the procedural rep for seq-add. (define seq-add (lambda (s1 s2) (lambda (n) (+ (s1 n) (s2 n))))) ------------------------------------------ Can you add them all up at the time you make one of these kinds of sequences? ------------------------------------------ TRANSFORMING TO RECORDS (2) How? 2. use the code from the closure in the operation that "apply"s the record representation (define seq-nth ; procedural version (lambda (seq n) (seq n))) (define seq-nth ; record version (lambda (seq n) (variant-case seq ( ------------------------------------------ What are the cases? will this still work with our examples? ------------------------------------------ FINITE FUNCTIONS Idea behind environments, stores, ... (ff T): (-> (D) T), where D is a finite set of symbols Example: environments env: def: the *intension* of a function is def: the *extension* of a function is How could we represent a finite function? ------------------------------------------ What kinds of operations would we want for this ADT? How would those act on particular kinds of representations? ------------------------------------------ FINITE FUNCTIONS create-empty-ff: (-> () (ff T)) extend-ff: (-> (symbol T (ff T)) (ff T)) apply-ff: (-> ((ff T) symbol) T) ;; REQUIRES: symbol in the domain of ff BEHAVIOR (create-empty-ff) = {} (extend-ff s d f) = (apply-ff f s) = (apply-ff (create-empty-ff) s) is an error (apply-ff (extend-ff s d f) s2) = ------------------------------------------ How would you represent these by procedures? ------------------------------------------ FOR YOU TO DO 1. Give record declarations for the constructors for "finite functions". (define create-empty-ff (lambda () (lambda (symbol) (error "empty-ff: no association " "for symbol" symbol)))) (define extend-ff (lambda (sym val ff) (lambda (symbol) (if (eq? symbol sym) val (apply-ff ff symbol))))) 2. Translate the following to the record representation. (define apply-ff (lambda (ff symbol) (ff symbol))) ------------------------------------------ ------------------------------------------ EXTENDING A FINITE FUNCTION WITH SEVERAL ASSOCIATIONS Why? binding formals to actuals declaring a record etc. ; PROCEDURAL REPRESENTATION (define extend-ff* ; p. 95 ;; TYPE: (-> ((list symbol) ;; (list T) ;; (ff T)) ;; (ff T) (lambda (sym-list val-list ff) (let ((val-vector (list->vector val-list))) (lambda (symbol) (let ((val (ribassoc symbol sym-list val-vector '*fail*))) (if (eq? val '*fail*) (apply-ff ff symbol) val)))))) ------------------------------------------ Why have the let outside the inner lambda? Isn't it used only once? ------------------------------------------ RECORD REPRESENTATION (p. 95) (define-record extended-ff* (define extend-ff* (lambda (sym-list val-list ff) (make-extended-ff* sym-list (define apply-ff (lambda (ff symbol) (variant-case ff (empty-ff () (error "empty-ff: no association " "for symbol" symbol)) (extended-ff (sym val ff) (if (eq? symbol sym) val (apply-ff ff symbol))) (extended-ff* ------------------------------------------ D. alternatives (3.6.3) ------------------------------------------ OPTIMIZATION ALTERNATIVES For convenience or efficiency consider other equivalents to records. Suppose only use extend-ff*. Records: #(extended-ff* sym-list4 val-vector4 #(extended-ff* sym-list3 val-vector3 ... #(extended-ff* sym-list1 val-vector1 #(empty-ff))) List of pairs (ribcage): ((sym-list4 . val-vector4) (sym-list3 . val-vector3) ... (sym-list1 . val-vector1)) ------------------------------------------ which is more convenient?