I. data abstraction (2.1) A. terminology ------------------------------------------ DATA ABSTRACTION terms: data abstraction, ADT example: nonnegative integers divide program into 2 parts 1. knows about representation (the ADT implementation) 2. doesn't know details of representation (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 my-cell (cell 342)) > (cell-ref my-cell) 342 > (vector? my-cell) > my-cell 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-of T) rep type (vector-of T) ;;;;; in cell.scm (deftype cell (forall (T) (-> (T) (cell-of T)))) (deftype cell-ref (forall (T) (-> ((cell-of T)) T))) ;;;... (defrep (forall (T) (cell-of T)) (forall (T) (vector-of T))) (define cell ;; TYPE: (lambda (x) (vector x))) (define cell-ref ;; TYPE: (lambda (x) (vector-ref x 0))) ------------------------------------------ II. an abstraction for inductive data types (2.2) A. declaration and use (2.2.1) ------------------------------------------ ABSTRACTION FOR INDUCTIVE DATA (2.2) problem: want representation of grammars ::= | ( ) Want: constructors access Solution: defining constructors: access syntax: ------------------------------------------ 1. define-datatype ------------------------------------------ DEFINE-DATATYPE DESCRIBES CONSTRUCTORS For the grammar: ::= | ( ) (define-datatype This defines the following procedures leaf-node : interior-node : bintree? : ------------------------------------------ ------------------------------------------ SYNTAX ::= ( define-datatype { ( {}* ) }+ ) ::= ( ) ::= ::= ::= ::= ------------------------------------------ ------------------------------------------ SEMANTICS (define-datatype tn tn? (vn1 (fn11 pe11) ... (fn1q pe1q)) ... (vnk (fnk1 pek1) ... (fnkr pekr))) where pe11 : (type-predicate-for te11) ... pe1q : (type-predicate-for te1q) ... pek1 : (type-predicate-for tek1) ... pekr : (type-predicate-for tekr) declares the constructors vn1 : (-> (te11 ... te1q) tn) ... vnk : (-> (tek1 ... tekr) tn) and the type predicate tn? : (type-predicate-for tn) and the type name tn : (variant-record (vn1 (fn11 te11) ... (fn1q te1q)) ... (vnk (fnk1 tek1) ... (fnkr tekr))) ------------------------------------------ ------------------------------------------ FOR YOU TO DO What are the types of the constructors for (define-datatype vehicle vehicle (bicycle (maker symbol?)) (auto (maker symbol?) (year number?))) How would you make an object that describes: 1. A schwinn bicycle? 2. A 1991 Honda auto? ------------------------------------------ 2. variant records ------------------------------------------ VARIANT RECORDS def: a *union type* is a type that contains values of ______________ different types. def: a *discriminated union type* is a union type whose values def: a *variant record type* is a type that is a discriminated union type, in which the contained types are all _________________. ------------------------------------------ When is a type defined with define-datatype a record type? When is it a variant-record type? What's a variant-record type like in C? In Pascal? Ada? 3. cases expressions ------------------------------------------ CASES EXPRESSION ALLOWS ACCESS (define small-tree (interior-node 'a (leaf-node 7) (leaf-node 3))) (leaf-sum (leaf-node 7)) ==> 7 (leaf-sum small-tree) ==> 10 (leaf-sum (interior-node 'b small-tree small-tree)) ==> 20 (deftype leaf-sum (-> (bintree) number)) (define leaf-sum (lambda (tree) (cases ------------------------------------------ What's this like in C? In Pascal? ------------------------------------------ SYNTAX ::= ( cases {}+ ) | ( cases type-name expression {}* ( else ) ) ::= ::= ( ( {}* ) ) ::= ::= ::= ------------------------------------------ ------------------------------------------ SEMANTICS (cases tn e (vn1 (fn11 ... fn1q) e1) ... (vnk (fnk1 ... fnkr) ek) (else ee)) check that: e : tn tn : (variant-record (vn1 (fn11 te11) ... (fn1q te1q)) ... (vnk (fnk1 tek1) ... (fnkr tekr)) ...) there is some T such that, ee : T and for all 1 <= i <= k, ei : T If for some 1 <= i <= k, e = (vni v1 ... vs) then return otherwise return ee. ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write the procedure height: (-> (bintree) number) Examples: (define small-tree (interior-node 'a (leaf-node 7) (leaf-node 3))) (height (leaf-node 7)) ==> 1 (height small-tree) ==> 2 (height (interior-node 'b small-tree small-tree)) ==> 3 ------------------------------------------ III. abstract syntax (2.2.2) ------------------------------------------ ABSTRACT SYNTAX (2.2.2) 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-datatype expression expression? (var-exp (id symbol?)) (lambda-exp (id symbol?) (body expression?)) (app-exp (rator expression?) (rand expression?))) ------------------------------------------ Can you define an abstract syntax for if expressions? literals? ------------------------------------------ PARSING AND UNPARSING parse concrete ---------> abstract ^ / \----------/ unparse Examples of parse (parse 'x) = (var-exp 'x) (parse '(f x)) = (app-exp (var-exp 'f) (var-exp 'x)) ------------------------------------------ ------------------------------------------ CODE FOR PARSE (deftype parse-expression (-> (datum) expression)) (define parse-expression (lambda (datum) (cond ((symbol? datum) (var-exp datum)) ((and (list? datum) (= 3 (length datum)) (eq? 'lambda (car datum))) (lambda-exp (caadr datum) (parse-expression (caddr datum)))) ((and (list? datum) (= 2 (length datum))) (app-exp (parse-expression (car datum)) (parse-expression (cadr datum)))) (else (eopl:error 'parse-expression "Invalid concrete syntax ~s" datum))))) ------------------------------------------ why is the error case there? does that catch all errors? ------------------------------------------ UNPARSE USING VARIANT-CASE (deftype unparse (-> (expression) datum)) (define unparse-expression (lambda (exp) (cases expression exp ------------------------------------------ ------------------------------------------ FOR YOU TO DO (free-vars (parse-expression '(lambda (x) (car x)))) ==> (car) (load "set-ops.scm") ;;; use set-of, set-remove, set-union (deftype free-vars (-> (expression) (set-of symbol))) (define free-vars (lambda (exp) (cases expression exp (var-exp (id) ------------------------------------------ A. handling Kleene star or plus (p. 51ff) ------------------------------------------ ABSTRACT SYNTAX FOR KLEENE STAR To represent a starred production, use a list. Concrete syntax: ::= | | (if ) | (lambda ({}*) ) | ( {}*) Abstract syntax: (define-datatype expression expression? (lib-exp (datum number?)) (var-exp (id symbol?)) (if-exp (test-exp expression) (true-exp expression) (false-exp expression)) (lambda-exp (app-exp -------------------------------------- -------------------------------------- EXAMPLE USING THIS GRAMMAR (deftype free-vars (-> (expression) (set symbol))) (define free-vars (lambda (exp) (variant-case exp (lit-exp (datum) the-empty-set) (var-exp (id) (set-of id)) (if-exp (test-exp true-exp false-exp) (set-union (free-vars test-exp) (set-union (free-vars true-exp) (free-vars false-exp)))) (lambda-exp (ids body) ------------------------------------------ IV. representation strategies for data types (2.3) A. motivation and overview ------------------------------------------ TRANSFORMING PROCEDURAL REPS TO ABSTRACT SYNTAX TREE REPS (2.3) Why? In semantics, often specify ADTs that are like functions: Idea: A. Represent each way to construct a value of such an ADT by a _________. To observe the stored information, apply them. B. If need efficiency, represent each way to construct a value by a __________ in a variant record type. To observe the stored information, use a cases expression, and the body of the corresponding ______________. ------------------------------------------ ------------------------------------------ PICTURE OF TRANSFORMATION (nnnnnnnnnnnnnnnnnn) ( ) ( ADT ) ( ) (uuuuuuuuuuuuuuuuuu) ^ ^ / \ / \ / \ !---------------! !-----------------! ! procedural rep! ! AST rep ! ! ! **> !(variant records)! ! ! ! ! !---------------! !-----------------! ------------------------------------------ B. procedural reps (2.3.2) ------------------------------------------ EXAMPLE: INFINITE SEQUENCES type seq with Constructors seq-repeat: (-> (number) seq) seq-generator: (-> ((-> (number) number)) seq) seq-add: (-> (seq seq) seq) Observers: seq-nth: (-> (seq number) 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 (deftype seq-repeat (-> (number) seq)) (deftype seq-generator (-> ((-> (number) number)) seq)) (deftype seq-nth (-> (seq number) number)) (deftype seq-add (-> (seq seq) seq)) (defrep seq (-> (number) number)) (define seq-repeat (lambda (num) (lambda (n) num))) (define seq-generator (lambda (f) (lambda (n) (f n)))) (define seq-nth (lambda (s n) (s n))) (define seq-add (lambda (s1 s2) ------------------------------------------ Which are the constructors? How did we represent them? Which are the observers? How did we program them? How is this like objects? C. abstract syntax tree representation (2.3.3) ------------------------------------------ TRANSFORMING TO ASTs (1) How? 1. Constructors: give a define-datatype with a variant record to remember each constructor's arguments (define seq-repeat ; procedural rep (lambda (num) (lambda (n) num))) (define seq-generator (lambda (f) (lambda (n) (f n)))) (define seq-add (lambda (s1 s2) (lambda (n) (+ (seq-nth s1 n) (seq-nth s2 n))))) ;;; ... becomes ... (define-datatype seq seq? (define seq-repeat repeated-seq) (define seq-generator generated-seq) (define seq-add added-seq) ------------------------------------------ what are the free varrefs in the body of seq-repeat? seq-generator? Can you add them all up at the time you make one of these kinds of sequences? ------------------------------------------ TRANSFORMING TO ASTS (2) How? 2. Use the code from each closure in the corresponding case of the observer cases expression (define seq-nth ; procedural version (lambda (s n) (s n))) (define seq-nth ; ast version (lambda (s n) (cases seq s ( ------------------------------------------ What are the cases? will this still work with our examples? D. environment example ------------------------------------------ ENVIRONMENT SPECIFICATION def: An *environment* is a function that maps symbols to values. type environment with constructors: empty-env : (-> () environment) extend-env : (-> ((list-of symbol) (list-of datum) environment) environment) observer: apply-env : (-> (environment symbol) datum) BEHAVIOR (empty-env) = {} (extend-env (list 's1 ... 'sn) (list v1 ... vn) f) = (apply-env f s) = ------------------------------------------ How would you represent these by procedures? ------------------------------------------ FOR YOU TO DO Transform the following to the AST rep. (define empty-env (lambda () (lambda (sym) (eopl:error 'apply-env "No binding for ~s" sym)))) (define extend-env (lambda (syms vals env) (lambda (sym) (let ((pos (list-index sym syms))) (if (<= 0 pos) (list-ref vals pos) (apply-env env sym)))))) (define apply-env (lambda (env sym) (env sym))) ------------------------------------------ E. alternatives (2.3.4), skip? ------------------------------------------ OPTIMIZATION ALTERNATIVES For convenience or efficiency consider other representations Environments built using grammar: ::= (empty-env) | (extend-env (list {}*) (list {}*) ) Can represent this directly: ::= () | ((({}*) ({}*)) . ) Observe that we look up the symbols, and get an index, so can use a vector for the values: ::= () | ((({}*) #({}*)) . ) Looks like: ((sym-list4 . val-vector4) (sym-list3 . val-vector3) ... (sym-list1 . val-vector1)) ------------------------------------------ What serves as the tags to discriminate these options? which is more convenient?