I. Kernel Language for the Declarative Computation Model A. motivation (2) What does programming involve? B. Defining languages (2.1) 1. how languages 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? Is C a kernel language? C++? a. linguistic abstractions What is a linguistic abstraction? What are some linguistic abstractions in C++ or Java? b. syntactic sugar What is a syntactic sugar? How is it different from a linguistic abstraction? What are some syntactic sugars in C++ and Java? 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 (2.8.2.2) 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 variable 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) ------------------------------------------ KERNEL LANGUAGE SYNTAX (TABLES 2.1, 2.2) ::= skip | | local in end | = | = | if then else end | case of then else end | '{' {} '}' ::= ::= | | ::= | ::= | ( {:} ) ::= proc '{' $ {} '}' end ::= | ::= | | ::= true | false ------------------------------------------ Why would you include all of these in the language? Why leave out some things, e.g., = ? What is a case statement like in C, C++, or Java? 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? How does this type system compare to that of C, C++, and Java? 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? What are these kinds of operations called in Java? 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? What kind of scoping is in C, C++, and Java? The Unix shell? 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 bind 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 an 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 an 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 {CAppend LS1} fun {$ LS2} fun {$ LS3} {Append LS1 {Append LS2 LS3}} end end end Use of it: {{{CAppend [1 2]} [3 4]} [5 6]} FOR YOU TO DO Curry the following definition: fun {Add X Y} X+Y end Use the curried version to add 2 and 3 ------------------------------------------ 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? ------------------------------------------ GRAVITATIONAL FORCE FIELDS AS CURRIED FUNCTIONS declare G = 6.670e~11 %% UNITS: N * m^2 / kg^2 fun {Square R} %% UNITS: m -> m^2 R*R end fun {GravForce M1 R M2} %% UNITS: kg x m x kg -> N if R == 0.0 then 0.0 else G * M1 * M2 / {Square R} end end fun {GravField M1} %% UNITS: kg -> m -> kg -> N fun {$ R} fun {$ M2} if R == 0.0 then 0.0 else G * M1 * M2 / {Square R} end end end end %%% USING IT MassOfEarth = 5.96e24 %% UNITS: kg RadiusOfEarth = 6.37e6 %% UNITS: m EarthsField %% UNITS: m -> kg -> N = {GravField MassOfEarth} ForceAtSurface %% UNITS: kg -> N = {EarthsField RadiusOfEarth} ------------------------------------------ ------------------------------------------ PROCEDURE VALUES ARE CLOSURES def: a *closure* is: code for a procedure 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 is 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 = {(nil,s) | s in Store} + Message Message = String input[[S]] = ((S,{})|nil, {}) output((nil,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] ((X=V, E) | Rest, s) --> (Rest, s3) where 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 S2 end let S2 = local R in X=2 R=X end Then ((S1,{})|nil), {}) --> ((S2, {X-->x1})|nil, {x1}) --> ((X=2 R=X, {X-->x1,R-->x2})|nil, {x1,x2}) --> ((X=2,{X-->x1,R-->x2})| (R=X,{X-->x1,R-->x2})|nil, {x1,x2}) --> ((R=X,{X-->x1,R-->x2})|nil, {x1=2,x2,x3=2}) --> (nil, {x1=2,x2=2,x3=2}) ------------------------------------------ Is this final state terminal? ------------------------------------------ ANOTHER EXAMPLE local X in local Y in Y = proc {$ ?R} R=X end X=true local X in X=false local Z in {Y Z} if Z then skip else Z=X end end end end end let S0 = local X in S1 end % statements S1 = local Y in S2 S3 S4 end S2 = Y = proc {$ ?R} R=X end S3 = X=true S4 = local X in S5 S6 end S5 = X=false S6 = local Z in {Y Z} S7 end S7 = if Z then skip else Z=X end E2 = {X-->x1, Y-->x2} % environments E3 = {X-->x5, Y-->x2} E4 = {X-->x5, Y-->x2, Z-->x6} C1 = (proc {$ ?R} R=X end, {X-->x1}) % a closure s5 = {x1=true,x2=C1,x3=C1,x4=true,x5} % some stores s6 = {x1=true,x2=C1,x3=C1,x4=true,x5,x6} s7 = {x1=true,x2=C1,x3=C1,x4=true,x5,x6=true} We calculate as follows... ((local X in S1 end,{})|nil, {}) --> ((local Y in S2 S3 S4 end,{X-->x1})|nil, {x1}) --> ((S2 S3 S4,{X-->x1,Y-->x2})|nil, {x1,x2}) --> ((Y = proc {$ ?R} R=X end,E2)|(S3 S4,E2)|nil, {x1,x2}) --> ((X=true,E2)|(local X in S5 S6 end,E2)|nil, {x1,x2=C1,x3=C1}) --> ((local X in S5 S6 end,E2)|nil, {x1=true,x2=C1,x3=C1,x4=true}) --> ((S5 S6,{X-->x5,Y-->x2})|nil, {x1=true,x2=C1,x3=C1,x4=true,x5}) --> ((local Z in {Y Z} S7 end,E3)|nil, s5) --> x6}> (({Y Z} S7,E4)|nil, s6) --> (({Y Z},E4)|(S7,E4)|nil, s6) --> ((R=X,{X-->x1,R-->x6})|(S7,E4)|nil, s6) --> ((if Z then skip else Z=X end,E4)|nil, s7) --> ((skip,E4)|nil, s7) --> (nil, s7) ------------------------------------------ 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. Memory organization (extra topic) How do we represent the environment and the store in a single address space on a conventional computer? ----------------- | Code | |---------------| | Static Data | | (constants) | |---------------| | run-time | ~ Environment | stack of ARs | | | | | | | v | \\\\\\\\\\\\\\\\| |\\\\\\\\\\\\\\\| | (heap) | ~ Store ----------------- Why is an activation record needed for every *call* of a procedure, instead of one for each procedure? How to access the values of local variables in the environment? --------------------- Aho and Ullman's design for Activation Record (using static links): __________________________ RET: | returned value | | (for functions) | |________________________| PAR: | | | actual parameters | | | |________________________| | DL: | dynamic link | | |________________________| | SL: | static link | fixed | | (or display) | size | |________________________| fields | IP: | saved machine status | <_________ EP (env pointer) | | (ip and other regs) | |________________________| VAR: | local data | | (storage for vars) | |________________________| | | TEMP:| temporaries | | | |\\\\\\\\\\\\\\\\\\\\\\\\\ <____ SP (stack pointer) --------------------- does saved part save information about caller or callee? How would this be used in making a call? How would this be used in a return? ii. Last call optimization (2.5.1) What is a last call optimization? ------------------------------------------ fun {Length Lst} case Lst of _|T then 1+{Length T} else 0 end end Tracing this: {Length 1|2|3|4|nil} fun {Length Lst} {LengthIter Lst 0} end fun {LengthIter Lst N} case Lst of _|T then {LengthIter T N+1} else N end end Tracing this: {Length 1|2|3|4|nil} ------------------------------------------ What is it useful for? Does the semantics already to this? Do C, C++, and Java require this optimization? What does that say about using recursion in these languages? iii. Garbage collection (2.5.2-4) Why is garbage collection useful? Does the semantics already allow it? Does C do garbage collection? C++? Java? What kinds of error does garbage collection prevent? Does garbage collection prevent memory leaks? II. Extensions for a Practical Language (2.6-2.8) Why not just program in the kernel language? A. Syntactic conventions (2.6.1) ------------------------------------------ SYNTACTIC SUGARS FOR VALUES, DECLARATIONS, AND PATTERNS lit(f1:E1, ..., fn: En) ==> local X1 = E1 in ... local Xn = En in lit(f1:X1, ..., fn:Xn) end ... end local X = E in S end ==> local = in ==> ------------------------------------------ Any conditions on the new variables in the last one? How does this get back to kernel syntax? Why do they preserve meaning? ------------------------------------------ PATTERNS IN FUNCTION DEFINITIONS In general: proc {P ... 1 ... n ...} S end ==> proc {P ... X1 ... Xn ...} case X1 of 1 then ... case Xn of n then S end ... end end where X1 ... Xn are fresh Example fun {First A#_} A end ==> ------------------------------------------ How would you call First? How could you use this to define Head and Tail functions for lists? What sugars would help with if statements? How could you desugar the short-circuiting andthen and orelse? What sugars help with case statements? How would you desugar the use of "andthen" in case clauses? How would you desugar the use of constants in case clauses? What are these like in C, C++, and Java? ------------------------------------------ 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? How would you translate proc {P X} X=Y end ? B. Expressions and Functions (2.6.2) What's the desugaring rule for fun declarations? What rule desugars calls to functions? ------------------------------------------ EXPRESSIONS AND FUNCTIONS How to translate into kernel syntax: fun {Add1 X} X+3 end R = {Add1 3} R = {Add1 3 * 4} R = {Add1 {Add1 3 * 4}} ------------------------------------------ Can you use these rules in C or Java? 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? What languages have exception handling? ------------------------------------------ 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 ------------------------------------------ Do these sugars give the same semantics as in Java? 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 (skip) ------------------------------------------ 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 language? 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) (skip, already covered) ------------------------------------------ STATIC VS. DYNAMIC TYPING def: A *type error* is def: A language has a *static type system* iff def: A *dynamic type system* catches type errors ------------------------------------------ What kind of typing does Java have? Can a language 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?