I. Declarative Programming Techniques (Ch 3) A. Why When is declarative programming useful? Why is it useful? What is referential transparency? B. How 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 just programming with specifications? II. 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 {SumFromTo I J} if I > J then 0 else I + {SumFromTo I+1 J} end end ------------------------------------------ How to make it iterative? ------------------------------------------ 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? 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: left: right: ) ------------------------------------------ How does the type definition resemble a grammar? 2. Natural Numbers ------------------------------------------ RECURSIVE NATURAL NUMBERS ::= zero | succ ( ) Examples: 0 represented by zero 1 represented by succ(zero) 2 represented by succ(succ(zero)) 3 represented by succ(succ(succ(zero))) ------------------------------------------ ------------------------------------------ NATURAL NUMBER EXAMPLES ::= zero | succ ( ) Outline: fun {F N} case N of succ (P) then ...{F P}... % inductive case else ... % basis 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: T}: > such that {DeleteFirst Ls Sought} returns a new list that is like Ls, but without the first occurrence of Sought in Ls (if any). {Test {DeleteFirst nil b} '==' nil } {Test {DeleteFirst a|b|c|b|nil b} '==' a|c|b|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)))) succ(succ(zero)) } == 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) {Eval equalExp(subExp(intLit(5) intLit(4)) intLit(1))} == boolLit(true) ------------------------------------------ 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) Grammar: ::= # 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 (skip) 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 resource 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 max(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) III. Procedural Abstraction (Higher-Order Programming, 3.6) ------------------------------------------ def: the *order* of a function F is 1+(maximum order of F's arguments), where the order of a non-function argument is 0. def: A function is *higher-order* if its order is greater than 1. ------------------------------------------ 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 a. for iteration (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. 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: Concat: >}: > All: }: Boolean> ------------------------------------------ c. 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? ------------------------------------------ AN EXAMPLE: COMPOSE 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 ) How to write this: ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write a procedure Twice Twice: }: > Examples: {{Twice Not) true} == false == {Not {Not true}} {{Twice fun {$ N} N+1 end} 3} == 5 == {{fun {$ N} N+1 end} {{fun {$ N} N+1 end} 3}} ------------------------------------------ 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) ------------------------------------------ ------------------------------------------ EXAMPLE: INFINITE SEQUENCES Write the following functions to implement Repeat: }: > Generate: : }: > Nth: }: > Add: }: > For example: declare Ones = {Repeat 1} Halves = {Generate fun {$ N} 1.0/{IntToFloat {Pow 2 N}} end} {Show {Nth Ones 33}} {Show [{Nth Halves 0} {Nth Halves 1} {Nth Halves 2} {Nth Halves 3} {Nth Halves 30}]} shows: 1 [1.0 0.5 0.25 0.125 9.3132e~010] ------------------------------------------ How can we represent something infinite in a computer? B. Loop abstractions (3.6.2-3) 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 E in L do {Stmt E} end With pattern match: for foo(X Y) in L do {Stmt X Y} end Collection of results: for Elem in Ls collect: Results do {Results {F Elem}} end ------------------------------------------ How would you precisely define these? How would you write a loop that sums the elements of a list of numbers, LoN? How would you write a function that returns all the numbers in a list LoN that are strictly greater than N? IV. 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? ------------------------------------------ EXAMPLES USING THESE declare fun {StackSize Stk} if {IsEmpty Stk} then 0 else 1+{StackSize {Pop Stk _}} end end fun {StackElements Stk} if {IsEmpty Stk} then nil else local E Rest in Rest={Pop Stk E} E|{StackElements Rest} end end end fun {StackEqual S1 S2} {StackElements S1} == {StackElements S2} end ------------------------------------------ ------------------------------------------ Specification forall E:T, ST: : {IsEmpty {NewStack}} == true {IsEmpty {Push ST E}} == false {StackEqual {Pop {Push ST E} _} ST} local Y in _={Pop {Push ST E} Y} Y end == E try _{Pop {NewStack} _} false catch _ 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, Sample ------------------------------------------ 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 implementations 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 of Value type: NewName: > == : }: > Specification: ({NewName} == {NewName}) = false ------------------------------------------ Is NewName referentially transparent? 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? V. 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 VI. 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) (skip) 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? What is this like in C, C++, and Java? ------------------------------------------ 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 ------------------------------------------ What is this like in C, C++, and Java? 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 %% file Combinators.oz % Example of how to write a module in Oz functor $ import % This section isn't needed for this example System(showInfo show) export s: S k: K define % The S combinator fun {S F} fun {$ G} fun {$ X} {{F X} {G X}} end end end % The K (constant) combinator fun {K C} fun {$ X} C end end end ------------------------------------------ 2. compilation 3. linking ------------------------------------------ % LINKING MODULES local [Combinators] = {Module.link ['Combinators.ozf']} S = Combinators.s K = Combinators.k in % In this part we use the abbriviations defined above {StartTesting 'Combinators'} {Test {{Combinators.k 7} 6} '==' 7} local I = {{S K} K} in {Test {I 3} '==' 3} end end ------------------------------------------ What is Module.link returning? 4. libraries