I. Declarative Programming Techniques (Ch 3)
 A. Why declarative programming?
  When is declarative programming useful? Why is it useful?
------------------------------------------
 WHEN IS DECLARATIVE PROGRAMMING USEFUL?





  WHY IS IT USEFUL?





------------------------------------------
  Why is declarative programming deterministic?
  What do we mean by an expression being deterministic?
  What is referential transparency?
------------------------------------------
       REFERENTIAL TRANSPARENCY

def: A model is referentially transparent












------------------------------------------
 B. How
    What technique can be used to simplify declarative program structures?
    How can we tell if a program is declarative?
------------------------------------------
    WHEN IS A PROGRAM DECLARATIVE?







------------------------------------------
    Why does the declarative model lead to declarative programs?
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. Programming tips
------------------------------------------
          TIPS FOR SAVING TIME
      WHEN DOING RECURSIVE PROBLEMS

 1. Write out your own examples if needed
 	a. base case(s)
 	b. related simpler example



 2. Write out the type.
    Assume the inputs match this type.

        
 3. Use an outline that matches the grammar
    for the input data type.







 4. Fill in the outline
    by generalizing the examples
   a. What's returned in the base case(s)?
   b. How do we get the answer
      from
       - recursive call's answer, and
       - other information?

 5. Debug bottom up from subexpressions, 
    replacing recursive calls 
    with expected results.

 6. One function per nonterminal.
    Don't mix 2 recursions in a function.
------------------------------------------
  2. Type notation (3.4.1)
------------------------------------------
          TYPE NOTATION (GRAMMARS)

<Color> ::= red | blue | green


<Nat> ::= zero
      | succ ( <Nat> )


<List T> ::= nil
         | <T> '|' <List T>

Equivalently:

<List T> ::= nil
         | '|'(1: <T> 2: <List T>)


<BTree T> ::= leaf
          | tree ( key: <Literal>
                   value: <T>
                   left: <BTree T>
                   right: <BTree T> )


Examples in these grammars:





------------------------------------------
     How does the type definition resemble a grammar?
  3. Natural Numbers
------------------------------------------
     RECURSIVE NATURAL NUMBERS

<Nat> ::= zero
      | succ ( <Nat> )

Examples:

0 represented by  zero
1 represented by  succ(zero)
2 represented by  succ(succ(zero))
3 represented by  succ(succ(succ(zero)))


------------------------------------------
------------------------------------------
         FOLLOWING THE GRAMMAR FOR
  RECURSIVE FUNCTIONS OVER NATURAL NUMBERS

<Nat> ::= zero
      | succ ( <Nat> )

Outline that follows this grammar:

   fun {F N}
     case N of
        zero then ...             % basis
     [] succ (P) then ...{F P}... % inductive case
     end
   end
------------------------------------------
     In what sense does that look like the grammar?
------------------------------------------
        EXAMPLE DEVELOPMENT

Write Plus, which adds two <Nats>

What are some examples?






What's the type?


What's the outline?
How do we fill it in?










------------------------------------------
     How does the structure of the program resemble the type definition?
------------------------------------------
         FOR YOU TO DO

Write Mult that multiplies two <Nat>s.









Write Equals that tells if two <Nat>s are equal,
without using Oz's == on <Nat> arguments.









------------------------------------------
  4. Working with lists (3.4.2.6)
------------------------------------------
       RECURSION OVER FLAT LISTS

<List T> ::= nil 
           | T '|' <List 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: <fun {$ <List T> T}:
                        <List 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 }








 

------------------------------------------
  5. structure of data determines structure of code
   a. non-empty lists
------------------------------------------
  GENERALIZING HOW TO WRITE RECURSIONS

<NEList T> ::= sing(T)
           | cons(T <NEList T>)


Write:
   HeadNEL: <fun {$ <NEList T>}: T>
   TailNEL: <fun {$ <NEList T>}: <NEList T>>












Write 
   AppendNEL: <fun {$ <NEList T> <NEList T>}: <NEList T>>
such that
  {Test {AppendNEL sing(3) sing(4)} 
              '==' cons(3 sing(4))}
  {Test {AppendNEL cons(5 sing(3)) sing(4)} 
              '==' cons(5 cons(3 sing(4)))}
  {Test {AppendNEL cons(7 cons(5 sing(3))) cons(8 sing(1))}
      '==' cons(7 cons(5 cons(3 cons(8 sing(1)))))}













------------------------------------------
------------------------------------------
           FOR YOU TO DO

Using
   Max: <fun {$ <Number> <Number>}: <Number>>

Write
   MaxNEL: <fun {$ <NEList T>}: T>
such that
  {MaxNEL sing(3)} == 3
  {MaxNEL cons(5 sing(3))} == 5
  {MaxNEL cons(3 cons(5 sing(3)))} == 5











------------------------------------------
   b. Multiple nonterminals
------------------------------------------
           MULTIPLE NONTERMINALS

Recall our last tip:

 6. One function per nonterminal.
    Don't mix 2 recursions in a function.

Example:

A computer manufacturer (HAL)
sells single computers and "grids"

  <Computer> ::=
     single(name: <String> diskSizes: <List <Int>>)
   | grid(name: <String> elements: <List <Computer>>)
  <String> ::= <List <Char>>
  <Char> ::= <Int>
  <List T> ::= nil
            | T '|' <List T>

Examples:

 single(name: "xz400" diskSizes: [2 4 8])

 grid(name: "small"
      elements: [single(name: "xz400" diskSizes: [2 4 8])])

 grid(name: "maxFlow"
      elements:
        [single(name: "xz400" diskSizes: [2 4 8])
         single(name: "9000" diskSizes: [8 16])
         grid(name: "small"
              elements: [single(name: "xz400"
                                diskSizes: [2 4 8])])])
------------------------------------------
------------------------------------------
              EXAMPLE PROBLEM

Write "SuperSize", which
  (a) puts "super-" in front of each name,
  (b) doubles all disk sizes.

Examples:

{Test {SuperSize single(name: "xz400" diskSizes: [2 4 8])}
   '==' single(name: "super-xz400" diskSizes: [4 8 16])}

{Test {SuperSize
 grid(name: "small"
      elements: [single(name: "xz400" diskSizes: [2 4 8])])}
 '=='
  grid(name: "super-small"
       elements: [single(name: "super-xz400"
                         diskSizes: [4 8 16])])}

{Test {SuperSize
 grid(name: "maxFlow"
      elements:
        [single(name: "xz400" diskSizes: [2 4 8])
         single(name: "9000" diskSizes: [8 16])
         grid(name: "small"
              elements: [single(name: "xz400"
                                diskSizes: [2 4 8])])])}
 '=='
 grid(name: "super-maxFlow"
      elements:
        [single(name: "super-xz400" diskSizes: [4 8 16])
         single(name: "super-9000" diskSizes: [16 32])
         grid(name: "super-small"
              elements: [single(name: "super-xz400"
                                diskSizes: [4 8 16])])])}

What's the type?


What's the outline?
How do we fill it in?


















------------------------------------------
   c. More programming language like grammars
------------------------------------------
     RECURSION OVER GRAMMARS

<Exp> ::= boolLit( <Bool> )
      | intLit( <Int> )
      | subExp( <Exp> <Exp> )
      | equalExp( <Exp> <Exp> )
      | ifExp( <Exp> <Exp> <Exp> )

Write the following

  Eval: <fun {$ <Exp>}: <Exp>>

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?
  6. Difference Lists (3.4.4)
   a. Basics of Difference Lists
------------------------------------------
         DIFFERENCE LISTS (3.4.4)

Grammar:

 <DiffList T> ::= <List T> # <List T>


Idea
   L1 # L2
 represents list L1 minus elements of L2
 invariant: L2 is a tail of L1.

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:
     <fun {$ <DiffList T> <DiffList T>}:
          <DiffList T>>

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) (skip, put on supplement)
   What's the recommended general approach for calculating resource usage?
  1. Time (3.5.1)
------------------------------------------
  EXECUTION TIMES OF KERNEL INSTRUCTIONS

S                  T(S)

skip               k

X = Y              k0*max(size(X),size(Y))

X = myrec(f1:X1    k1 + k2*n
     ... fn:Xn)
X = proc           k3' + k3*|FV(S) - {X1,...,Xn}|
    {$ X1 ... Xn}
      S end 

S1 S2              T(S1) + T(S2)

local X in S end   k4 + T(S)

if X then S1       k5 + max(T(S1),T(S2))
else S2 end

case X of          k7 
  r(f1:X1...fn:Xn)  + k6*n
    then S1         + max(T(S1), T(S2))
  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
------------------------------------------
        Why is the time needed for skip constant?
        Can unification be done 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)
X = proc           k1 
    {$ X1 ... Xn}   + n 
    S end           + k2*|FV(S) - {X1,...,Xn}|

S1 S2              max(M(S1),M(S2))

local X in S end   1 + M(S)

if X then S1       max(M(S1),M(S2))
     else S2 end

case X of            max(n+M(S1), M(S2))
  r(f1:X1 ... fn:Xn)
    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.

Examples:
     Add1: <fun {$ Int}: Int>

     Map: <fun {$ <List T> <fun <T>:S>}: <List S>>

------------------------------------------
 A. Basic Operations (3.6.1)
   What are the 4 basic operations of higher-order programming?
------------------------------------------
   4 KINDS 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: <fun {$ <List T> <fun {$ T S}: S> S}: S>
  Append: <fun {$ <List T> <List T>}: <List T>>
   and "andthen"
write:
   Concat: <fun {$ <List <List T>>}: <List T>>

     {Concat nil} == nil
     {Concat [[4 5 6] nil} == [4 5 6]
     {Concat [[1] nil [2 3] [4 5 6] nil]} '==' [1 2 3 4 5 6]

   All: <fun {$ <List Boolean>}: Boolean>

     {All [true true false]} == false
     {All {true true]} == true
     {All nil} == true

------------------------------------------
   c. for trees
------------------------------------------
             FOR YOU TO DO

<BTree T> ::= leaf
          | tree ( key: <Literal>
                   value: T
                   left: <BTree T>
                   right: <BTree T> )

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

    WRITE FOLDTREE AS A GENERALIZATION











------------------------------------------
  How would you use the result to write Preorder and IncTree?
  3. instantiation (currying) (3.6.6)
------------------------------------------
 INSTANTIATION or RULES THAT 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 the function Compose such that:

  {{Compose Head Tail} [a b c]}
	== {Head {Tail [a b c]}}
	== {Head [b c]}
	== b

   {{Compose Not IsEmpty} nil}
	== {Not {IsEmpty nil}}
	== false

(The examples assume that:
  fun {Head L} X|_=L in X end
  fun {Tail L} _|Xs=L in Xs end
  fun {IsEmpty L} L == nil end
)

How to write this:








------------------------------------------
------------------------------------------
        SUMMARY OF STEPS FOR 
   MAKING A HIGHER-ORDER FUNCTION

 1. Starting from examples, name the roles
 2. Generalize the result expression,
    using role names, write it down
 3. Wrap fun declarations around it,
    corresponding to the arguments
------------------------------------------
------------------------------------------
	   FOR YOU TO DO

Write a procedure Twice

 Twice: <fun {$ <fun {$ T}: T>}: <fun {$ T}: T>>

Examples:
   {{Twice Not} true}
	== {Not {Not true}}
	== true
   {{Twice fun {$ N} N+1 end} 3}
	== {{fun {$ N} N+1 end}
	    {{fun {$ N} N+1 end}
             3}}
	== 5












------------------------------------------
  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 <Seq>

   Repeat: <fun {$ <Number>}: <Seq>>
   Generate: <fun {$ <fun <Number>: <Number>}: <Seq>>
   Nth: <fun {$ <Seq> <Integer>}: <Number>>
   Add: <fun {$ <Seq> <Seq>}: <Seq>>


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

       FORM WITH COLLECT: 
  USEFUL IN DECLARATIVE MODEL

Collection of results:

   for Elem in Ls collect: Results
   do
      {Results {F Elem}}
   end

   for foo(X _) in L collect: Xs
   do
      {Xs X}
   done

------------------------------------------
        How would you precisely define these?
        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 +, -, *, div, ...
          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 INCH = 1 MILE?

     ^^^^^^^^^^^^^)
   (  Abstraction  )
   (   1/2          )
   (        3/4    )
    (uuuuuuuuuuuuu)

          ^
          |
          | Abstraction Function
          |
          |
   |------------------|
   | [1 2]   [6 8]    |
   |------------------|
------------------------------------------
  1. stacks (3.7.1)
------------------------------------------
        DECLARATIVE STACK (3.7.1)

Signature:

 NewStack: <fun {$}: <Stack T>>
 Push: <fun {$ <Stack T> T}: <Stack T>>
 Pop: <fun {$ <Stack T> T}: <Stack T>>
 IsEmpty: <fun {$ <Stack T>}: <Bool>>
------------------------------------------
   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: <Stack T>:

  {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: <fun {$ <Int> <Int> <Int>}:
                 <Sample>>
 Average: <fun {$ <Sample>}: <Float>>
 Median: <fun {$ <Sample>}: <Float>>

Specification
   for all I, J, K, L: <Int>, F: <Float>:

 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 <Sample>, what can we say
       about {Average Inc} and {Median Inc}?
    Using only the operations on a value Inc of type <Sample>,
       can one figure out what the 3 arguments to the constructor are?
------------------------------------------
    Q: 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: <fun {$}: <Dict>>
 Put: <fun {$ <Dict> <Feature> <Value>}:
           <Dict>>
 CondGet:
     <fun {$ <Dict> <Feature> <Value>}:
          <Value>>
 Domain: <fun {$ <Dict>}:
               <List <Feature>>>

where 
  <Feature> ::= <Atom> | <Integer>


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: <fun {$}: <Name>>
 == : <fun {$ <Name> <Name>}: <Bool>>

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 undetermined variables
     Does wrapping protect undetermined variables?
------------------------------------------
    READ-ONLY VIEW OF VARIABLE (FUTURES)

!!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) (skip)
------------------------------------------
METHODOLOGY FOR DEVELOPING SMALL APPLICATIONS

- informal specification (requirements)
- examples, including boundary conditions
- exploration of programming fragments and basic operations
   (bottom up exploration)
- structure and coding (some structure from modules)
- testing and reasoning to check correctness and efficiency
- judging quality (correctness, efficiency, maintainability
                   extensibility, simplicity)
------------------------------------------
 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


            client
               |
               v
   interface(op1: Op1, ... opn: OpN)
   |                               |
   |      module                   |
   |       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):

<statement> ::= ...
  | functor <variable>
    [ import { <selection> }+ ]
    [ export { <feature> }+ ]
    define { <declarationPart> }+
    [ in <statement> ] 
    end

<selection> ::= <variable> [ at <atom> ]
  | <variable> ( { <named-feature> } + )

<feature> ::= [ <field-name> : ]
              <variable>

<field-name> ::= <atom> | <int>

<named-feature> ::= <field-name>
                    [ :  <variable> ]

<expression> ::= ...
  | functor [ $ ]
    [ import { <selection> }+ ]
    [ export { <feature> }+ ]
    define { <declarationPart> }+
    [ in <statement> ] 
    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