I. Declarative Computation Model (Ch 2) A. quiz ------------------------------------------ QUIZ FOR CHAPTER 2 [Defining languages] How are languages defined? [Syntax] Give an EBNF grammar for phone numbers of the form 555-1212. [Semantics] What is one way to give meaning to a programming language? Why is it precise? [Data structures in the model] What is a single-assignment store? What are (declarative) variables? What are the values in the declarative model? What is a partial value? What is a store entity? What is a dataflow variable? [Semantics of Statements] What is the meaning of: X = Y X = true proc {$ X Y Z} Z = X+Y end [Operations] What is the difference between X = Y and X == Y ? [Scoping] What is static scoping? Why is it useful for reasoning? What is the meaning of the procedure local X in X = 541 proc {$ Y Z} Z = X+Y end end What does it mean with dynamic scoping? What are the free identifiers in proc {$ Y Z} Z = X+Y end ? What are the free identifiers in {proc {$ Y Z} Z = X+Y end X Q} ? [Dataflow] What is the meaning of local Z in {proc {$ Y Z} Z = X+Y end 3 Z {Browse Z} end Why is dataflow behavior sensible? In what way does dataflow behavior make debugging difficult? [Abstract Machine] How does the abstract machine work, in general terms? [Pattern Matching] How is pattern matching done by case? [Static scoping] How is static scoping realized in the abstract machine? [Last call optimization] What is last call optimization? Why is it useful? [Garbage Collection] How can you prevent storage from being collected? [Sugars and abstractions] What is the difference between a syntactic sugar and a linguistic abstraction? What sugars does Oz have? What does the "$" nesting marker do? How are function definition desugared into procedure definitions? How are their calls desugared? [Exceptions] Why does a language need an explicit exception mechanism? What values are used in Oz for exceptions? What happens if both an exception is thrown in a try and a raise is thrown in a finally clause? [Functional Languages] What is the lambda calculus? How is it related to the declarative model? What restrictions eliminate the need for unbound variables? [Unification] What does the unification algorithm do? How can cyclic structures arise? [Typing] How is strong typing different from static typing? What are the advantages of dynamic typing? ------------------------------------------ II. Kernel Language for the Declarative Computation Model A. motivation (2) What does programming involve? What computation models should we be interested in? B. Defining langauges (2.1) 1. how langauges are defined 2. syntax ------------------------------------------ EXTENDED BACKUS-NAUR FORM (EBNF) Example ::= { } ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ------------------------------------------ Can you give an EBNF grammar for phone numbers of the form 555-1212? 3. semantics (2.1.2) ------------------------------------------ SEMANTICS Goals: - simple - mathematical - reason about correctness - reason about efficiency Kernel Language Approach: [ Practical Language ] | | v [ Kernel Language ] E.g., fun {Sqr X} X * X end -translates-to-> proc {Sqr X Y} {'*' X X Y} end ------------------------------------------ How to define the kernel language? What characteristics needed for kernel language? Why? a. linguistic abstractions What is a linguistic abstraction? b. syntactic sugar What is a syntactic sugar? How is it different from a linguistic abstraction? C. declarative computation model details (2.2-2.5) 1. single-assignment store (2.2) ------------------------------------------ SINGLE-ASSIGNMENT STORE (2.2) Stores are sets of variables partitioned into: - sets of unbound but equal variables - singleton sets of determined variables bound to numbers, records, or procedures Notation and Type: sigma, s in Store = Variable -> PUValue x,y,z in Variable PUValue = Value + Set(Variable) V in Value = Number + Record + Closure + Variable (P,E) in Closure = x Environment ES in Set(Variable) dom(s) is the domain of s unbound(s,x) = (s(x) in Set(Variable)) aliases(s,x) = s(x), if unbound(s,x) determined(s,x) = (s(x) in Value) ------------------------------------------ ------------------------------------------ NOTATION FOR SINGLE-ASSIGNMENT STORES Example 1: s = { x1, x2 = x3 } means s(x1) = {x1} // x1 is unbound s(x2) = {x2, x3} s(x3) = {x2, x3} pictured as: x1 [ *-]--->[unbound {x1}] x2 [ *-]--->[unbound {x2, x3}] x3 [ *-]-/ Example 2: { x1 = 541, x2 = [3,4], x3 = [3,4], x4 } pictured as: x1 [541] x2 [ *-]--->[ 3|*-]->[ 4|nil] x3 [ *-]--/ x4 [unbound] ------------------------------------------ How would you implement this? What is a value store? a. value creation (2.2.3) and operations on the store (2.8.2.2) ------------------------------------------ OPERATIONS ON THE STORE Allocation next: Store -> Variable alloc: Store -> Store such that: next(s) not in dom(s) next(s) in dom(alloc(s) unbound(alloc(s), next(s)) Binding of variables to values: bind: Store -> (Set(Variable) x Value) -> Store (bind(s)(ES, value))(y) = if y in ES then value else s(y) Binding of variables to variables: bind: Store -> Set(Variable) x Set(Variable) -> Store (bind(s)(ES1, ES2))(y) = if y in ES1 or y in ES2 then ES1 U ES2 else s(y) Example: bind({x1=x2, x3, x4=nil})({x1,x2}, 5) = {x1=5, x2=5, x3, x4=nil} Suppose s is {x1=x2=x3, x4, x5, x6=6, x7=7} What is: bind(s)({x4},{x5}) bind(s)({x4},{x1,x2,x3}) bind(s)({x5}, 5) bind(s)({x1,x2,x3}, 123) ------------------------------------------ ------------------------------------------ Unification of variables: unify: Store -> (Variable x Variable) -> (Store + (Failure x Store)) where Failure = String unify(s)(x, y) = if unbound(s,x) and unbound(s,y) then bind(s)(s(x), s(y)) elseif unbound(s,x) and determined(s,y) then bind(s)(s(x), s(y)) elseif unbound(s,y) and determined(s,x) then bind(s)(s(y), s(x)) elseif determined(s,x) and determined(s,y) then if s(x) in Number and s(y) in Number then if s(x) == s(y) then s else ("equality...", s) end elseif s(x) in Closure and s(y) in Closure then if equalClosures(s(x), s(y) then s else ("equality...", s) end else // assuming both are records let l(l1:x1, ..., ln:xn) = s(x) l'(l1':y1,...,lm':ym) = s(y) in if l==l' and [l1,...,ln] == [l1',...,lm'] then listUnify(s)([x1,...,xn], [y1,...,ym]) else ("equality...", s) end E.g., suppose s is {x1=x2=x3, x4, x5=n(l:7), x6=n(l:x1)} What is: unify(s)(x1,x4) unify(s)(x4,x1) unify(s)(x1,x5) unify(s)(x5,x6) ------------------------------------------ Can you write listUnify? b. environment (2.2.4-5) ------------------------------------------ ENVIRONMENT E in Environment = VIdentifier -> Variable Example: Program text: X = 541 1. value creation: x1 = 541 2. identifier binding X = x1 Now have environment: E(X) = x1 store: s(x1) = 541 Pictured: E s X [ *-]----> x1 [541] Notation E = {X --> x1} s = {x1 = 541} ------------------------------------------ What is the value of X? What is dereferencing? ------------------------------------------ NOTATIONS Environment manipulations adjunction: (E + {X --> x})(Y) = if Y == X then x else E(Y) restriction: (E| )(Y) {X1, ...,Xn} = if Y in {X1, ..., Xn} then E(Y) else undefined ------------------------------------------ What's the domain of the restriction? c. partial values (2.2.6) ------------------------------------------ PARTIAL VALUES (2.2.6) def: A *partial value* is a data structure that may contain unbound variables. Example: declare X Y X = person(name:"George", age: Y) What environment and store does this produce? ------------------------------------------ What happens after the binding Y = "25" is done? ------------------------------------------ COMPATABILITY OF VALUES Declarative variables can be bound to variables. X = Y Pictured: X [ *-]-----> x1 [ *-]---> [unbound {x1, x2}] / Y [ *-]-----> x2 [ *-]-/ Whenever a value is bound to one, the other sees it. declare X Y X = Y Y = 25 {Browse X} ------------------------------------------ Can this work for more than 2 variables? d. dataflow variables (2.2.8) ------------------------------------------ DATAFLOW EXECUTION What if a varaible is used before it is bound? 1. Get garbage from memory 2. Get default value for type (0) 3. Give error message and stop 4. Illegal, complain at compile time 5. Wait until variable is bound ------------------------------------------ Why do these? What languages do these? What does Oz do? 2. Kernel Language (2.3) a. Syntax (2.3.1) Why would you include all of these in the language? Why leave out some things, e.g., = ? why records? b. Values and types (2.3.2) ------------------------------------------ TYPES def: a *type* is a set of values with a set of operations Types in the declarative model Value Number Int Char Float Record Tuple Literal Bool Atom ... List String ... Procedure ... ... ------------------------------------------ What does v has type T mean? What does a subtype mean in this interpretation of types? What is dynamic typing? Why do it? i. Basic types (2.3.3) ii. Records (2.3.4-5) ------------------------------------------ RECORDS (2.3.4) Creation newrec(field1: Val1) Operations: ------------------------------------------ What's the operation for creating a record? What are the operations on records? How can records be used to make enumerations? variants? What does == do for records? What is the difference between X = Y and X == Y ? iii. Procedures (2.3.4-5) ------------------------------------------ PROCEDURES Creation: proc { $ X Y } Y = X+X end Operations: ------------------------------------------ What are the operations on procedures? 3. Kernel Language Semantics (2.4) a. basic concepts (2.4.1) i. Static Scoping ------------------------------------------ STATIC SCOPING def: In *static scoping*, each identifier, X, def: In *dynamic scoping*, each identifier, X, Example: local X F T in local X in X=2 F = proc {$ Y ?Z} Z=X+Y end end X=1 {F 10 T} {Browse T} end ------------------------------------------ What does the example give with each kind of scoping? In the example, does it matter if X=1 occurs after the declaration of F? What is the meaning of the procedure local X in X = 541 proc {$ Y Z} Z = X+Y end end with dynamic scoping? ii. Free and bound identifier occurrences (p. 64) ------------------------------------------ FREE AND BOUND IDENTIFIER USES def: In proc {$ X ?Y} Exp) end X and Y are declarations formal parameters. They binds all occurrences of that identifier in Exp, unless there is an intervening declaration of these formals. {proc {$ X ?Y} Y=X end F1 Z} {{{proc {$ X ?Y} Y=proc {$ X ?Y} Y={X F} end end} F Z} F1 Z1} def: an identifier X *occurs free* in and expression Exp iff def: an identifier X *occurs bound* in Exp iff Exp contains a use of X that is bound by a declaration of X in Exp ------------------------------------------ in the first expression, what does X refer to? ------------------------------------------ EXAMPLES F, F1 occur free in: F1 {F F1} proc {$ B ?Res} Res=F end B, B1 occur bound in: proc {$ B ?Res} Res = B end proc {$ B1 ?R1} R1= proc {$ B ?R} R={B1 B} end end There can be a mix: {fun {$ B} B end F} ^ ^ bound-/ \-free occurrence occurrence The same variable can occur both ways: {fun {$ N} N end N} ^ ^ bound-/ \-free occurrence occurrence Variables that are free in a subexpression may be bound in a larger expression fun {$ F} {fun {$ B} {B F1} end F} end ------------------------------------------ So if n occurs free in a expression, does that mean it doesn't occur bound? ------------------------------------------ FOR YOU TO DO What are the (a) free, and (b) bound identifiers in ... fun {$ X} fun {$ Y} X end end {G {Tail X}} fun {$ X} {G {Tail X}} end fun {$ G} fun {$ X} {G {Tail X}} end end ------------------------------------------ iii. procedure values or closures (p. 65) ------------------------------------------ CURRYING function: fun {$ LS1 LS2 LS3} {Append LS1 {Append LS2 LS3}} end curried form: fun {$ LS1} fun {$ LS2} fun {$ LS3} {Append LS1 {Append LS2 LS3}} end end end FOR YOU TO DO Curry the following definition: fun {$ X Y} X+Y end ------------------------------------------ Can this be done in C++? ------------------------------------------ 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? ------------------------------------------ PROCEDURE VALUES ARE CLOSURES def: a *closure* is: code for a procedrue and an environment ------------------------------------------ So, in general, what in C++ is like a closure? b. The abstract machine (2.4.2) i. little step semantics in general ------------------------------------------ COMPUTATION (LITTLE STEP) SEMANTICS Meaning Programs <-------> Answers | ^ input | | output | | v -->* | State ------------> T def: a in Meaning[[P]] iff ------------------------------------------ ii. terminal transition systems ------------------------------------------ TERMINAL TRANSITION SYSTEM (TTS) (State, -->, T) State: -->: T: -->* reflexive, transitive closure ------------------------------------------ What are the possible outcomes for a program? iii. TTS for Oz ------------------------------------------ TTS FOR OZ (ST,s) in State = Stack x Store + Message Stack = ( x Environment)* T = {([],s) | s in Store} + Message Message = String input[[S]] = ([(S,{})], {}) output(([],s)) = s output(Msg) = Msg ------------------------------------------ What states are terminal? How should we define the transitions (-->)? ------------------------------------------ TRANSITIONS (-->) [skip] ((skip, E) | Rest, s) --> (Rest, s) [sequence] ((S1 S2, E) | Rest, s) --> ((S1, E) | (S2, E) | Rest, s) [local] ((local X in S end,E)|Rest, s) --> ((S,E')|Rest, s') where E' = E+{X-->x} and x = next(s), and s' = alloc(s) [var-var binding] ((X=Y, E) | Rest, s) --> (Rest, s') where s' = unify(s)(E(X), E(Y)) and isStore(s') [var-var bindingerror] ((X=Y, E) | Rest, s) --> ((raise failure(Msg) end, E) | Rest, s') where (Msg,s') = unify(s)(E(X), E(Y)) [value creation to unbound] ((X=V, E) | Rest, s) --> (Rest, s') where unbound(s, E(X)) and v = MV[[V]](E) and s' = bind(s)(s(E(X)),v) [value unification] ((X=V, E) | Rest, s) --> (Rest, s3) where determined(s, E(X)) and y = next(s) and s' = alloc(s) and v = MV[[V]](E) and s'' = bind(s')({y},v) and s3 = unify(s'')(E(X),y) and isStore(s3) [value creation error] ((X=V, E) | Rest, s) --> ((raise failure(Msg) end, E) | Rest, s3) where y = next(s) and s' = alloc(s) and v = MV[[V]](E) and s'' = bind(s')({y},v) and (Msg, s3) = unify(s'')(E(X),y) [if-true] ((if X then S1 else S2 end,E)|Rest, s) --> ((S1, E)|Rest, s) where determined(s, E(X)) and s(E(X)) == true [if-false] ((if X then S1 else S2 end, E)|Rest, s) --> ((S2, E)|Rest, s) where determined(s, E(X)) and s(E(X)) == false [if-error] ((if X then S1 else S2 end, E)|Rest, s) --> ((raise error(...) end, E)|Rest, s) where determined(s, E(X)) and not(s(E(X)) == true) and not(s(E(X)) == false) [application] (({X Y1 ... Yn}, E)|Rest, s) --> ((Body, E')|Rest, s) where determined(s,E(X)) and s(E(X)) in Closure and [Z1, ..., Zn] = args(s(E(X))) and Body = body(s(E(X))) and E' = env(s(E(X))) + {Z1 -->E(Y1)} + ... + {Zn -->E(Yn)} [application-error] (({X Y1 ... Yn}, E)|Rest, s) --> ((raise error(...),E) | Rest, s) where determined(s,E(X)) and not(s(E(X)) in Closure) or s(E(X)) does not have n arguments [case-match] ((case X of L(F1: X1 ... Fn:Xn) then S1 else S2 end, E)|Rest, s) --> ((S1, E') | Rest, s) where determined(s,E(X)) and isRecord(s(E(X))) and Label(s(E(X))) == L and Arity(s(E(X))) == [F1, ..., Fn] and E' = E + {X1 -->s(E(X)).F1, ..., Xn -->s(E(X)).Fn} [case-else] ((case X of L(F1: X1 ... Fn:Xn) then S1 else S2 end, E)|Rest, s) --> ((S2, E) | Rest, s) where determined(s,E(X)) and not(isRecord(s(E(X)))) or not(Label(s(E(X))) == L) or not(Arity(s(E(X))) == [F1 ... Fn]) ------------------------------------------ What happens if one of the variables in var-var binding is not in the domain of the environment, E? What free variables are allowed in a program? What's the parameter passing mechanism? What happens to an if-statement when the condition variable is not determined? Can the matching case change the store? ------------------------------------------ MEANING OF VALUE EXPRESSIONS MV: ValueExpression -> Environment -> Value MV[[X]](E) = E(X), where X in MV[[N]](E) = N, where N in MV[[L]](E) = L, where L in MV[[L(F1:X1, ..., Fn:Xn)]](E) = L(F1: MV[[X1]](E), ..., Fn: MV[[X1]](E)), where L(F1:X1, ..., Fn:Xn) in MV[[proc {$ F1 ... Fn} Body end]](E) = (proc {$ F1 ... Fn} Body end, E|FVP), where FVP = FV(Body) \ {F1 ... Fn} is the set of free identifiers in the procedure ------------------------------------------ iv. Examples (2.4.5) ------------------------------------------ EXAMPLES let S1 = local X in X=2 {Browse X} end Then ([(S1,{})], {}) --> ([(X=2 {Browse X}, {X-->x1})], {x1}) --> ([(X=2, {X-->x1}) ({Browse X}, {X-->x1})], {x1}) --> ([({Browse X}, {X-->x1})], {x1=2,x2=2}) --> ------------------------------------------ ------------------------------------------ ANOTHER EXAMPLE local X in local Y in Y = proc {$ ?R} R=X end X=1 local X in X=2 local Z in {Y Z} {Browse Z} end end end end ------------------------------------------ v. sugars ------------------------------------------ SYNTACTIC SUGARS local X1 ... Xn in S end ==> local X1 in ... local Xn in S end ... end {P E} ==> local X in X=E {P X} end ------------------------------------------ How would you generalize the last one? c. Memory management (2.5) i. Last call optimization (2.5.1) What is a last call optimization? What is it useful for? Does the semantics already to this? ii. Garbage collection (2.5.2-4) Why is garbage collection useful? Does the semantics already allow it? III. Extensions for a Practical Langauge (2.6-2.8) Why not just program in the kernel language? A. Syntactic conventions (2.6.1) ------------------------------------------ SYNTACTIC SUGARS FOR DECLARATIONS AND PATTERNS local X = E in S end ==> local X in X=E S end lit(f1:E1, ..., fn: En) ==> local X1 = E1 in ... local Xn = En in lit(f1:X1, ..., fn:Xn) end ... end local = in ==> local X1 ... Xn X0 in X0 = = X0 end ------------------------------------------ Any conditions on the new variables in the last one? How does this get back to kernel syntax? Why do they preserve meaning? What sugars would help with if and case statements? How could you desugar the short-curcuiting andthen and orelse? ------------------------------------------ NESTING MARKERS Use '$' to turn a statement into an expression Examples: {Obj get($)} ==> local X in {Obj get(X)} X end ------------------------------------------ What's the general rule for this? B. Expressions and Functions (2.6.2) ------------------------------------------ EXPRESSIONS AND FUNCTIONS How to translate into kernel syntax: fun {Add1 X} X+3 end {Add1 3} {Add1 3 * 4} {Add1 {Add1 3 * 4}} ------------------------------------------ C. Interactive Interface (2.6.3) How can you think of declare in terms of kernel syntax? Could you write a rule in the TTS for Oz for declare? D. Exceptions (2.7) Why do we need exception handling? Why not just check return codes? ------------------------------------------ EXCEPTION HANDLING EXAMPLE proc {Assert B Msg} if B then skip else raise 'Assertion failed: ' # Msg end end end try {Assert false oops} {Browse skipped} catch S#M then {Browse S#M} end {Browse hi} ------------------------------------------ What happens in the above? ------------------------------------------ TRANSITIONS FOR EXCEPTIONS [try] ((try S1 catch X then S2 end, E) | Rest, s) --> ((S1, E) | (catch X then S2 end, E) | Rest, s) [raise] ((raise X end, E) | Rest, s) --> ((Sc, Ec') | Rest', s) where (catch Y then Sc end, Ec) | Rest' = findHandler(Rest) and Ec' = Ec + {Y -->E(X)} [raise-error] ((raise X end, E) | Rest, s) --> "Uncaught exception" where nil = findHandler(Rest) [catch] ((catch X then S2 end, E) | Rest, s) --> (Rest, s) ------------------------------------------ Does the variable in a raise have to be determined? How would you define findHandler? What's that statement catch X then S2 end added in [try]? Why is its semantics to do nothing? ------------------------------------------ SUGARS try S1 finally S2 end ==> try S1 catch X then S2 raise X end end S2 try S1 catch X then S2 finally S3 end ==> try try S1 catch X then S2 end finally S3 end ------------------------------------------ How could we use pattern matching with try? How would you desugar that? What kind of data should be used for exceptions to help matching? E. Functional Languages (2.8.1) 1. foundational calculus ------------------------------------------ LAMBDA CALCULUS E ::= X | \X . E | E E | (E) parsing rules: scope of \X extends as far as possible application associates to the left example: \x . y z z means (\x . ((y z) z)) In Oz this is E ::= X | fun {$ X} E end | {E E} | (E) example: fun {$ X} {{Y Z} Z} end ------------------------------------------ In what way is this more primitive than the kernel langauge? How would you write a TTS for the lambda calculus? 2. functional programming on complete values How can we restrict the model to only work with complete values? F. Entailment and disentailment (2.8.2.4) ------------------------------------------ ENTAILMENT X == Y means X and Y are structurally equal blocks if some nodes are different but one is unbound What happens when we do: declare R1 R2 X R1 = pig(weight:100) R2 = pig(weight:X) {Browse R1 == R2} declare R1 R2 X R1 = pig(weight:X) R2 = pig(weight:X) {Browse R1 == R2} declare R1 R2 X R1 = horse(weight:X) R2 = pig(weight:X) {Browse R1 == R2} ------------------------------------------ What answers do these give? G. Static vs. Dynamic Typing (2.8.3) ------------------------------------------ STATIC VS. DYNAMIC TYPING def: A *type error* is def: A langauge has a *static type system* iff def: A *dynamic type system* catches type errors ------------------------------------------ Can a langauge have no type errors? Is calling a number as a procedure a type error? What are other examples? What about accessing an array outside its bounds? What about casting an object to a type it doesn't have in Java? Which is more general? Which makes separate compilation easier to implement? Which is better for exploratory programming? Which is better for safety critical systems? Which has faster compiled code? Which does Oz have? Is it possible to blend static and dynamic typing?