I. Declarative Programming Techniques (Ch 3) A. quiz ------------------------------------------ QUIZ FOR CHAPTER 3 [Motivation] When is declarative programming useful? [Definition] How is declarative programming defined? [Iteration] Make the following iterative: fun {Product Ls} case Ls of E|Es then E*{Product Es} else 1 end end [Recursion] Suppose ::= zero | succ ( ). Write Mult: }: > that multiplies two s. [Recursion] Write DeleteFirst: }: > such that {DeleteFirst Sought Ls} returns a new list that is like Ls, but without the first occurence of Sought in Ls (if any). [Recursion] Suppose ::= boolLit( ) | intLit( ) | subExp( ) | equalExp( ) | ifExp( ) Write the following Eval: }: > such that {Eval subExp(intLit(5) intLit(4))} = intLit(1) [Differnce Lists] What are difference lists useful for? What are their limitations? [Procedural abstraction] How can you make a statement S into a procedure? [Genericity] Generalize the following two procedures by making an abstraction of them both: fun {Preorder T} case T of leaf then nil [] tree(key: L value: V left: Left right: Right) then (L#V) | {Append {Preorder Left} {Preorder Right}} end end fun {IncTree T} case T of leaf then leaf [] tree(key: L value: V left: Left right: Right) then tree(key: L value: 1+V left: {IncTree Left} right: {IncTree Right}) end end Use the generalization to write Preorder and IncTree. [Instantiation] Write a curried version of foldTree. Use that to write Preorder and IncTree. [ADTs] How is an ADT different from a data type specification? [Data abstraction] What is an invariant property of data? [Security] What kinds of problems could happen if an ADT is implemented as a collection of functions? [Encapsulation] How does encapsulation relate to these problems? How does the name mechanism preserve encapsulation? [Read only views] Why are read-only views needed in the declarative model? [development] How would you develop a small application? [modules] What is a module? [functors] What is a functor? [linking] How are modules linked? ------------------------------------------ II. Declarative Programming Techniques (Ch 3) A. Why When is declarative programming useful? Why is it useful? What is referential transparency? B. How What does a good declarative program look like? What technique can be used to simplify declarative program structures? How can we tell if a program is declarative? Why does the declarative model lead to declarative programs? Is declarative programming programming with specifications? III. Declarative Programming Techniques (3.2-3.5) A. iterative computation (3.2) What is an iterative computation? 1. general schema (3.2.1, 3.3.3, 3.4.3) ------------------------------------------ ITERATIVE COMPUTATION (3.2) Is this iterative? fun {FromTo X Y} if X > Y then nil else X | {FromTo X+1 Y} end end How about this? fun {SumFromTo I J} if I > J then 0 else I + {SumFromTo I+1 J} end end ------------------------------------------ How to make it iterative? Does this pattern work from FromTo? ------------------------------------------ FOR YOU TO DO Make the following iterative: fun {Product Ls} case Ls of E|Es then E*{Product Es} else 1 end end ------------------------------------------ 2. When to use Iteration ------------------------------------------ WHEN TO USE ITERATION 0. When need efficiency 1. When the data doesn't maintain "place" 2. When need to return directly to caller ------------------------------------------ what are some examples of this that we have seen? 3. Control Abstraction (3.2.4) ------------------------------------------ ABSTRACTION OF ITERATION (3.2.4) Consider fun {SumFromToIter JnR} J#R=JnR in if I > J then R else {SumFromToIter J-1#R+J} end end fun {SqrtIter Guess} if {GoodEnough Guess} then Guess else {SqrtIter {Improve Guess}} end end What do they have in common? How do they differ? Can we make the differences arguments? ------------------------------------------ B. Data-driven recursion (3.4) 1. Type notation (3.4.1) ------------------------------------------ TYPE NOTATION (GRAMMARS) ::= red | blue | green ::= zero | succ ( ) ::= nil | T '|' ::= leaf | tree ( key: value: T left: right: ) ------------------------------------------ How does the type definition resemble a grammar? 2. Natural Numbers ------------------------------------------ RECURSIVE NATURAL NUMBERS ::= zero | succ ( ) % representation creation fun {FromInteger I} if I =< 0 then zero else succ({FromInteger I-1}) end end What is {FromInteger 0} {FromInteger 2} ------------------------------------------ ------------------------------------------ NATURAL NUMBER EXAMPLES ::= zero | succ ( ) To define a function F: }: T> recursively, write fun {F N} case N of zero then ... % basis [] succ (P) then ... % inductive case end end How to write Plus: }: >? ------------------------------------------ How does the structure of the program resemble the type definition? ------------------------------------------ FOR YOU TO DO Write Mult: }: > that multiplies two s. Write Equals: }: > without using Oz's == on arguments. ------------------------------------------ 3. Working with lists (3.4.2.6) ------------------------------------------ RECURSION OVER FLAT LISTS ::= nil | T '|' Write Add1Each: {Add1Each nil} = nil {Add1Each 1|3|5|nil} = 2|4|6|nil {Add1Each 3|5|nil} = 4|6|nil ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write DeleteFirst: }: > such that {DeleteFirst Sought Ls} returns a new list that is like Ls, but without the first occurence of Sought in Ls (if any). {Test {DeleteFirst b nil} nil } {Test {DeleteFirst b a|b|c|nil} a|c|nil } ------------------------------------------ 4. structure of data determines structure of code a. non-empty lists ------------------------------------------ GENERALIZING HOW TO WRITE RECURSIONS ::= sing(T) | cons(T ) Write MaxNEL: }: T> such that {MaxNEL sing(3)} = 3 {MaxNEL cons(5 sing(3))} = 5 {MaxNEL cons(3 cons(5 sing(3)))} = 5 Write Nth: }: T> such that {Nth sing(3) zero} = 3 {Nth cons(8 sing(3)) succ(zero)} = 3 {Nth cons(0 (cons 1 cons(2 sing(3)))) {FromInteger 2} } = 2 ------------------------------------------ b. More programming language like grammars ------------------------------------------ RECURSION OVER GRAMMARS ::= boolLit( ) | intLit( ) | subExp( ) | equalExp( ) | ifExp( ) Write the following Eval: }: > such that {Eval subExp(intLit(5) intLit(4))} = intLit(1) ------------------------------------------ What are the base cases? Where should there be a recursion? Examples for each recursive case? 5. Difference Lists (3.4.4) a. Basics of Difference Lists ------------------------------------------ DIFFERENCE LISTS (3.4.4) Idea L1 # L2 represents list L1 minus elements of L2 Example: (1|2|3|X) # X means (1|2|3|nil) Main advantage: Lists of form (a|b|...|X) # X can be appended in constant time Example: To append (1|2|3|X) # X and (4|5|Y) # Y bind X to (4|5|Y) to get (1|2|3|4|5|Y) # Y ------------------------------------------ Why not just use (1|2|3|X) instead of (1|2|3|X) # X ? ------------------------------------------ FOR YOU TO DO Write AppendD: }: > Examples: {AppendD (2|3|X)#X (3|5|Y)#Y} = (2|3|3|5|Y)#Y {AppendD X#X (3|5|Y)#Y} = (3|5|Y)#Y ------------------------------------------ What are the limitations of difference lists? b. Applications c. Queues and Performance (3.4.5) What's efficiency issue in implementing FIFO queues in the declarative model? What's the difference between ephemeral and persistent data? How could we get amortized constant time queues? How could we get constant time queues with dataflow variables? Can we delete elements from a queue that aren't present? d. Trees (3.4.6-7) e. Parsing (3.4.8) C. Time and space efficiency (3.5) What's the recommended general approach for calculating resourse usage? 1. Time (3.5.1) ------------------------------------------ EXECUTION TIMES OF KERNEL INSTRUCTIONS S T(S) skip X = Y X = V S1 S2 T(S1) + T(S2) local X in S end k + T(S) proc {$ ...} S end if X then S1 k + max(T(S1),T(S2)) else S2 end case X of P then S1 else S2 end {F Y1 ... Yn} T_F(size_F( I_F({Y1,...,Yn}))) where I_F is the subset of used arguments and size_F is a measure function and T_F is a function specific to F ------------------------------------------ What's the time needed for skip? How can unification be constant time? What's the time to do closure formation? How can pattern matching in case be constant time? 2. Memory usage (3.5.2) What needs to be measured for space? Which is more important? ------------------------------------------ MEMORY CONSUMPTION OF KERNEL INSTRUCTIONS S M(S), in words skip 0 X = Y 0 X = V memsize(v) S1 S2 M(S1) + M(S2) local X in S end 1 + M(S) proc {$ ...} S end if X then S1 max(M(S1),M(S2)) else S2 end case X of P max(M(S1),M(S2)) then S1 else S2 end {F Y1 ... Yn} M_F(size_F( I_F({Y1,...,Yn}))) where I_F is the subset of used arguments and size_F is a measure function and M_F is a function specific to F ------------------------------------------ Does the value always need to be completely created in X=V? What's the size of a closure? 3. Amortized complexity (3.5.3) What's amortized complexity? What are the techniques used to compute it? 4. Does performance still matter? (3.5.4) IV. Procedural Abstraction (Higher-Order Programming, 3.6) A. Basic Operations (3.6.1) What are the 4 basic operations of higher-order programming? 1. procedural abstraction How can you make a statement S into a procedure? Suppose we want two variants of a procedure that are similar, but differ a bit? 2. genericity What's an example of passing function arguments we've seen already? a. for lists ------------------------------------------ ABSTRACTING A COMMON PATTERN fun {Sum Ls} case Ls of E|Es then E+{Sum Es} else 0 end end fun {Product Ls} case Ls of E|Es then E*{Product Es} else 1 end end ------------------------------------------ What are the parts specific to computing the sum? the product? How can you write Sum and Product using FoldR? What is {FoldR (1|(2|(3|nil))) Number.'-' 0}? ------------------------------------------ FOR YOU TO DO Using FoldR, write: Sum Product Concat: >}: > All: }: Boolean> ------------------------------------------ b. for trees ------------------------------------------ FOR YOU TO DO ::= leaf | tree ( key: value: T left: right: ) Generalize: fun {Preorder T} case T of leaf then nil [] tree(key: L value: V left: Left right: Right) then (L#V) | {Append {Preorder Left} {Preorder Right}} end end fun {IncTree T} case T of leaf then leaf [] tree(key: L value: V left: Left right: Right) then tree(key: L value: 1+V left: {IncTree Left} right: {IncTree Right}) end end ------------------------------------------ How would you use the result to write Preorder and IncTree? 3. instantiation (currying) (3.6.6) ------------------------------------------ INSTANTIATION or RULES TO PRODUCE RULES Aka: factories, generators, curried functions Examples: fun {MakeSort Comparison} fun {$ Ls} {Sort Ls Comparison} end end Use of MakeSort: SortGT = {MakeSort fun {$ X Y} X > Y end} {SortGT List1} {SortGT List2} ... ------------------------------------------ How could we do this for the tree example? How would you use the that to write Preorder and IncTree? ------------------------------------------ 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} ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write procedure Compose such that: {{Compose Head Tail} [a b c]} = b = {Head [b c]} = {Head {Tail [a b c]}} {{Compose Not IsEmpty} nil} = false = {Not {IsEmpty nil}} (The examples assume that: fun {Head L} X|_=L in X end fun {Tail L} _|Xs=L in Xs end fun {IsEmpty L} L == null end ) ------------------------------------------ 4. embedding ------------------------------------------ EMBEDDING Putting closures in data is useful for: - explicit lazy evaluation - modules = records of operations - components, which return modules - manipulating actions as data (e.g., in testing) ------------------------------------------ B. Loop abstractions (3.6.2-3) (skip) 1. FoldL and other loops over lists (3.6.2) Does it do any good in the declarative model to run an action {A I} for each integer I in 1 to 10? 2. linguistic support for loops (3.6.3) What's the difference between a declarative and imperative loop? ------------------------------------------ FOR LOOPS IN OZ Simple counting: for I in A .. B do {Stmt I} end With step S: for I in A .. B; S do {Stmt I} end For lists: for X in L do {Stmt X} end With pattern match: for foo(X Y) in L do {Stmt X Y} end Collection of results: for foo(X Y) in L collect: C do {Stmt X Y C} end ------------------------------------------ How would you precisely define these? V. Abstract data types (3.7) A. definition and examples ------------------------------------------ ABSTRACT DATA TYPES (3.7) def: A *data type* or *type* is a set of values with a set of operations on them. Examples: Integers with +, -, *, iv, ... Bool with Not, And, Or def: An *abstract data type* or ADT is a data type ------------------------------------------ How is an ADT different from a data type specification? 1. stacks (3.7.1) ------------------------------------------ DECLARATIVE STACK (3.7.1) Signature: NewStack: > Push: T}: > Pop: T}: > IsEmpty: }: > ------------------------------------------ Which are observers? Which construct new stacks? ------------------------------------------ Specification forall E:T, ST: : {IsEmpty {NewStack}} = true {IsEmpty {Push ST E}} = false {Pop {Push ST E} _} = ST local Y in {Pop {Push ST E} Y} Y end = E try X in {Pop {NewStack} X} false catch Y then true end = true ------------------------------------------ What's going on with Pop? What do these last two equations mean? What's an implementation of Stack that satisfies these specifications? What's another one? How do we specify that this is persistent? 2. A non-free type, Increasing ------------------------------------------ HIDDEN DATA WITH AN INVARIANT Signature: NewSample: }: > Average: }: > Median: }: > Specification for all I, J, K, L: , F: try {Average {NewSample I J K}} catch X then F end = if 0 =< I andthen I < J andthen J < K then {IntToFloat I+J+K}/3.0 else F end try {Median {NewSample I J K}} catch X then L end = if 0 =< I andthen I < J andthen J < K then J else L end ------------------------------------------ Suppose Inc is a value of type , what can we say about {Average Inc} and {Median Inc}? Using only the operations on a value Inc of type , can one figure out what the 3 arguments to the constructor are? What are two possible implemetations of this ADT? Can someone figure out what the 3 arguments to the constructor are if they know how the implementation works? 3. dictionaries (3.7.1) (skip) ------------------------------------------ DICTIONARIES (3.7.1) Signature: NewDictionary: > Put: }: > CondGet: }: > Domain: }: >> where ::= | Specification: {Domain {NewDictionary}} = nil {Domain {Put D F V} = F|{Domain D} {CondGet {NewDictionary} F V} = V {CondGet {Put D F V} F V2} = V {CondGet {Put D F V} F2 V2} = {CondGet D F2 V2} ------------------------------------------ What would be an implementation? B. security (3.7.4) 1. problems What kinds of problems could happen if an ADT is implemented as a collection of functions? ------------------------------------------ SECURITY OF ADTS Want to prevent: alteration = discovery = impersonation = -- James Morris, 1973 Encapsulation = all code for an ADT is in one place ------------------------------------------ Why is alteration a bad thing? Why is discovery a bad thing? Why is impersonation a bad thing? Are the ADT implementations we've seen so far secure? What's the connection between encapsulation and maintenance? What's the connection between encapsulation and security? What's an open program? Why is that a problem for security? 2. solutions (3.7.4-5) What are general approaches to securing your cell phone? a. names (3.7.5) ------------------------------------------ NAMES TO PROTECT VALUES (3.7.5) Signature: NewName: > == : }: > Specification: ({NewName} == {NewName}) = false ------------------------------------------ Is this possible in the declarative model? ------------------------------------------ WRAPPING AND UNWRAPPING proc {NewWrapper ?Wrap ?Unwrap} Key={NewName} in fun {Wrap X} {Chunk.new w(Key:X)} end fun {Unwrap W} try W.Key catch _ then raise error(unwrap(W)) end end end end ------------------------------------------ ------------------------------------------ SAMPLE AS A SECURE ADT declare local Wrap Unwrap in {NewWrapper Wrap Unwrap} fun {NewSample I J K} if 0 =< I andthen I < J andthen J < K then {Wrap sample(average: {IntToFloat I+J+K}/3.0 median: J)} else raise badArguments(I J K) end end end fun {Average Sample} sample(average: AV ...) = {Unwrap Sample} in AV end fun {Median Sample} sample(median: MV ...) = {Unwrap Sample} in MV end end ------------------------------------------ How does this prevent discovery? Impersonation? Can you write Stack using NewWrapper? b. protecting unbound variables Does wrapping protect unbound variables? ------------------------------------------ READ-ONLY VIEW OF VARIABLE !!X means X, which can only be read from ------------------------------------------ What does read only mean in the declarative model? How to implement this? 3. capabilities (3.7.7) ------------------------------------------ CAPABILITIES (3.7.7) def: a *capability* is an unforgeable entity with an associated set of rights ------------------------------------------ How could we represent rights? How can we implement the principle of least authority using capabilities? VI. Nondeclarative needs (3.8) Are nondeclarative operations needed to interface with the world? What is a module? A. text input/output with files (3.8.1) ------------------------------------------ FILE MODULE declare [File] = {Module.link ['File.ozf']} L = {File.readList "foo.txt"} D = {WordFreq L} {File.writeOpen 'word.freq'} for X in {Domain D} do {File.write {Get D X} # ' occurrences of word ' # X # '\n'} end ------------------------------------------ ------------------------------------------ VIRTUAL STRINGS - Data that specifies a string - Avoids actual concatenation Examples: 'a virtual string' 'a' # ' virtual' # "string" ['a' ' virtual ' 'string'] ------------------------------------------ Why is it useful to avoid explicit concatenation? B. Text input/output with a graphical user interface (3.8.2) C. Stateless data I/O with files VII. Program Design and Modules (3.9) What do the book's authors consider the distinction between small and large programs? A. design methodology (3.9.1) How would you develop a small application? B. example program requirements (3.9.2) C. Software components (3.9.3) 1. modules and functors ------------------------------------------ MODULES Modules have: - an interface, represented by a record - an implementation ------------------------------------------ what is the implementation? can the interface record see the implementation? how is the implementation hidden from clients? ------------------------------------------ FUNCTORS A functor is a function that: - takes module interfaces as arguments - creates a new module - returns the new module's interface Syntax (Table 3.8): ::= ... | functor [ import { }+ ] [ export { }+ ] define { }+ [ in ] end ::= [ at ] | ( { } + ) ::= [ : ] ::= | ::= [ : ] ::= ... | functor [ $ ] [ import { }+ ] [ export { }+ ] define { }+ [ in ] end ------------------------------------------ can we also make a functor into an expression? what's the unit of compilation in Mozart? How are modules linked into a program? What's the module environment? ------------------------------------------ EXAMPLE declare functor Combinators export s: S k: K define fun {S F} fun {$ G} fun {$ X} {{F X} {G X}} end end end fun {K C} fun {$ X} C end end end ------------------------------------------ 2. compilation 3. libraries