I. Explicit State (Ch 6)
 A. quiz
------------------------------------------
        QUIZ FOR CHAPTER 6

[concepts] What is the difference
 between declarative and imperative
 programming?

[Utility] What are the advantages of
 explicit state?

[Abstraction] How does explicit state
 help abstraction?  Encapsulation?

[Model] How are cells modeled?

[Exchange] How do you get assignment from
 the Exchange primitive?  Access?

[Vs. Declarative] Is programming with
 state declarative? Why or why not?

[Vs. Declarative] Can program that uses
 state be declarative?

[Aliasing] What is an alias?
 What problems can it cause?

[Equality] What is the difference between
 structural and token equality?
 Which is used for cells?

[Data abstraction]
  What is a data abstraction?
  How does it differ from an ADT? Object?

[Data abstraction organization]
  What are the different ways to
   organize a data abstraction?
  What are their advantages
   and disadvantages?

[Polymorphism] What is polymorphism?
 What is ad hoc polymorphism?
 How is it achieved with different
  organizations of data abstractions?

[Binary methods] What is a binary method?
 How do the different data abstraction
  organizations differ in their treatment
  of binary methods?

[Parameter passing] Describe how each
 parameter passing mechanism works:
  call by value, reference, value-result,
  result, name, and need.

[Revocable capabilities] How can you get
 a revocable capability using cells?
------------------------------------------
II. Concepts (intro to Ch 6, 6.1-6.2)
 A. declarative vs. imperative
   What's the meaning of "declarative programming"?
 B. state
------------------------------------------
            STATE

def: state is a time-indexed sequence
     of values

Implicit (declarative) state:

  - accumulator arguments
  - doesn't live apart from calls

Explict state:

  - lives apart from calls' arguments
  - hidden from callers

        CELLS FOR EXPLICIT STATE

Operations

  NewCell : <fun {$ T}: <Cell T>>
  @ : <fun {$ <Cell T>}: T>
  := : <fun {$ <Cell T> T}: T>

------------------------------------------
    Why is hiding the state from callers important?
    Can explicit state be programmed in the declarative model?
 C. state and system building (6.2)
  1. abstraction
------------------------------------------
          PRINCIPLE OF ABSTRACTION

All systems have 2 parts:

   - specification
   - implementation

Layers:

   - Specification is often simpler
   - Build system in layers
------------------------------------------
     What point of view is used to write specifications?
     What's meant by building a system in layers?
     Why is that helpful?
  2. systems that grow + system properties (6.2.1)
------------------------------------------
     HOW TO SUPPORT ABSTRACTION

Needs:

  - growth/change
      ==> accumulate knowledge

  - abstraction/modularity
      ==> protect/hide knowledge

  - compositionality (combining parts)
      ==> encapsulation of knowledge
          + control of dependencies

  - instantiation (parameterization)
      ==> abstract/parameterize knowledge
     
------------------------------------------
   How did we get encapsulated state
      from the message passing model? 
   Why not make all state global?
  3. component-based programming (6.2.2) + OOP (6.2.3)
------------------------------------------
          COMPONENTS

- procedures
- functors (compilation units)
- concurrent actors
- objects
------------------------------------------
III. stateful model (6.3)
 A. cells (6.3.1)
  1. syntax
------------------------------------------
               CELLS

<s> ::= ...
    | {NewCell X C}
    | {Exchange C X Y}

Statement Sugars:

   X = C:=Y
==>
   {Exchange C X Y}

   C := Y
==>
   _ := C:= Y

   X = @C
==>
   

Expression Sugars

   {NewCell X}
==>
   local C in {NewCell X C} C end

   {Exchange C X}
==>
   local Y in {Exchange C X Y} Y end

   @C
==>
   local X in X = @C  X end

------------------------------------------
    What does {NewCell X C} do?
    What does {Exchange C X Y} do?
    What does @C do?
    How does the desugaring for X = @C work?
  2. semantics
------------------------------------------
         RECALL MUTABLE STORE DOMAIN

  m in MutableStore = Variable -> Variable

Operations:
  {}: MutableStore
  update: MutableStore
             -> Variable x Variable
             -> MutableStore
  lookup: MutableStore x Variable
             -> Variable
  lookup(update(m)(y,x), z)
     = if z == y then x else lookup(m,z)

Notation:
  write x:y for a binding in MutableStore
  typical m is {p1:s1, p2:s2}
  update({p1:s1})(p2, s2) = {p1:s1, p2:s2}
  lookup({p1:s1, p2:s2}, p1) = s1

------------------------------------------
------------------------------------------
           SEMANTICS

Sequential (-d->) configurations:
      
 (ST,s,m) in State =
    Stack x Store x MutableStore
  + Message

   Message = String
   Stack = (<Stmt> x Environment)*
   Store = Variable -> Value
      
 T = Message
   + { (nil,s,m) | s in Store,
                   m in MutableStore}

[NewCell call]
  (({NewCell X Y},E)|Rest, s, m)
  -d-> (Rest, s', m')
    where n is a cell name
      and n not in range(s)
      and unbound(s, E(Y))
      and s' = bind(s)(s(E(Y)), n)
      and m' = update(m)(E(Y), E(X))

[Exchange call]
  (({Exchange X Y Z},E)|Rest, s, m)
  -d-> (Rest, s', m')
    where determined(s, E(X))
      and s(E(X)) is a cell name
      and w = lookup(m)(E(X))
      and m' = update(m)(E(X), E(Z))
      and s' = bind(s)(s(E(Y)), w)

------------------------------------------
    Why is the update in [NewCell call] update(m)(E(Y), E(X)),
       and not update(m)(E(X), E(Y))?
    What should happen if determined(s, E(Y))?
    What's different between [NewCell call] and [NewPort call]?
    Why make a difference?
    In what sense is Exchange atomic?
    In the [Exchange call] rule, is it okay if Y or Z is unbound?
    What should happen if E(X) is unbound in the Exchange call rule?
    What should happen if E(X) is bound to a port name in the
    Exchange call rule?
    How should the memory management (gc) rules be changed?
------------------------------------------
          EXAMPLE

% File ModelTest.oz
local C One Z OldC in
  {NewCell One C}
  One = 1
  {Exchange C OldC Z}
end






------------------------------------------
  3. relation to declarative programming (6.3.3)
    Is a stateful program declarative?
    Can we write programs in the stateful model
     that act declaratively? 
    Can you write an iterative version of Reverse of a List
    using a cell?  Is your answer declarative?
  4. sharing and equality (6.3.4)
   a. sharing or aliasing
------------------------------------------
         SHARING OR ALIASING

def: Two identifiers are *aliases* if
     they refer to the same cell

Example:

declare
X = {NewCell 0}
Y = X
Y := 99
{Browse @X}
------------------------------------------
        Is aliasing a good thing?
------------------------------------------
       STRUCTURAL VS TOKEN EQUALITY

declare
X = lang(name: "oz")
Y = lang(name: "oz")
CX = {NewCell X}
CY = {NewCell Y}

{Browse @CX == @CY}
{Browse CX == CY}

------------------------------------------
        What does this display?  Why?
IV. data abstraction (6.4)
 A. eight ways to organize a data abstraction (6.4.1)
------------------------------------------
     PROPERTIES OF DATA ABSTRACTIONS

        ^       ^
 Bundled|      / Stateful
        |     /
        |    /
        |   /
        |  /
  not   | /not Stateful
 Bundled|/
        |----------------------------->
            Not Secure         Secure

Data abstraction is:

secure, if encapsulation can be enforced
          by the language
open, if it is not secure

stateful, if it must be implemented using
            explicit state
stateless, if it is not stateful

bundled, if it contains just objects
unbundled, if it has both values and ops

------------------------------------------
        Who enforces encapsulation if the language doesn't?
------------------------------------------
            BUNDLING

Unbundled data abstraction = ADT

   Can be secured by

   Examples: CLU, Ada 83

Bundled data abstraction = Class (spec)

   Reynolds's term: procedural data abstr.

   Operations (methods) inside objects
------------------------------------------
        In an unbundled abstraction, can the values make use of
        explicit state?
 B. variations on a stack (6.4.2)
  1. StackOpenDeclUnbun.oz -- open, declarative, unbundled
------------------------------------------
% $RCSfile: StackOpenDeclUnbun.oz,v $
declare
local
   fun {NewStack} nil end
   fun {Push S E} E|S end
   fun {Pop S ?E}
      case S
      of X|S1 then E=X S1
      end
   end
   fun {IsEmpty S} S==nil end
in
   Stack=stack(new:NewStack push:Push
	       pop:Pop isEmpty:IsEmpty)
end

% $RCSfile: StackOpenDeclUnbunTest.oz,v $
\insert 'StackOpenDeclUnbun.oz'
\insert 'StackDeclUnbunTest.oz'

% $RCSfile: StackDeclUnbunTest.oz,v $
\insert 'Test.oz'
declare S1 S2 S3 S4 S5 X Y
S1 = {Stack.new}
{Test {Stack.isEmpty S1} '==' true}
S2 = {Stack.push S1 3}
{Test {Stack.isEmpty S2} '==' false}
S3 = {Stack.push S2 4}
{Test {Stack.isEmpty S3} '==' false}
S4 = {Stack.pop S3 X}
{Test X '==' 4}
{Test {Stack.isEmpty S4} '==' false}
S5 = {Stack.pop S4 Y}
{Test Y '==' 3}
{Test {Stack.isEmpty S5} '==' true}

------------------------------------------
     What does NewStack do? Push? Pop? IsEmpty?
     Is this persistent?
     Why is it open?
     Why does the test need all those variables?
  2. StackSecureDeclUnbun.oz -- secure, declarative, unbundled
------------------------------------------
% $RCSfile: StackSecureDeclUnbun.oz,v $
\insert 'NewWrapper.oz'
declare
local
   Wrap Unwrap
   {NewWrapper Wrap Unwrap}
   fun {NewStack} {Wrap nil} end
   fun {Push S E} {Wrap E|{Unwrap S}} end
   fun {Pop S ?E}
      case {Unwrap S}
      of X|S1 then E=X {Wrap S1}
      end
   end
   fun {IsEmpty S} {Unwrap S}==nil end
in
   Stack=stack(new:NewStack push:Push
	       pop:Pop isEmpty:IsEmpty)
end

% $RCSfile: StackSecureDeclUnbunTest.oz,v $
\insert 'StackSecureDeclUnbun.oz'
\insert 'StackDeclUnbunTest.oz'

------------------------------------------
     How does this differ from the previous one?
     When is Wrap used? Unwrap?
  3. StackSecureDeclBun.oz -- secure, declarative, bundled
------------------------------------------
% $RCSfile: StackSecureDeclBun.oz,v $
\insert 'NewWrapper.oz'
declare
local
   fun {StackObject S}
      fun {Push E} {StackObject E|S} end
      fun {Pop ?E}
	 case S
	 of X|S1 then E=X {StackObject S1}
	 end
      end
      fun {IsEmpty} S==nil end
   in
      stack(push:Push
	    pop:Pop isEmpty:IsEmpty)
   end
in
  fun {NewStack} {StackObject nil} end    
end

% $RCSfile: StackSecureDeclBunTest.oz,v $
\insert 'Test.oz'
\insert 'StackSecureDeclBun.oz'
declare S1 S2 S3 S4 S5 X Y
S1 = {NewStack}
{Test {S1.isEmpty} '==' true}
S2 = {S1.push 3}
{Test {S2.isEmpty} '==' false}
S3 = {S2.push 4}
{Test {S3.isEmpty} '==' false}
S4 = {S3.pop X}
{Test X '==' 4}
{Test {S4.isEmpty} '==' false}
S5 = {S4.pop Y}
{Test Y '==' 3}
{Test {S5.isEmpty} '==' true}

------------------------------------------
     What does NewStack do? Push? Pop? IsEmpty?
     Is this persistent?
     Why are the tests different?
     Is this OO?
     How is this secure without using wrappers?
  4. StackSecureStateBun.oz -- secure, stateful, bundled
------------------------------------------
% $RCSfile: StackSecureStateBun.oz,v $
declare
fun {NewStack}
   C={NewCell nil}
   proc {Push E} C:=E|@C end
   fun {Pop}
	 case @C
	 of X|S1 then C:=S1 X
	 end
      end
      fun {IsEmpty} @C==nil end
in
   stack(push:Push
	 pop:Pop isEmpty:IsEmpty)
end

% $RCSfile: StackSecureStateBunTest.oz,v $
\insert 'Test.oz'
\insert 'StackSecureStateBun.oz'
\insert 'StackStateBunTest.oz'

% $RCSfile: StackStateBunTest.oz,v $
\insert 'Test.oz'
declare S X Y
S = {NewStack}
{Test {S.isEmpty} '==' true}
{S.push 3}
{Test {S.isEmpty} '==' false}
{S.push 4}
{Test {S.isEmpty} '==' false}
{S.pop X}
{Test X '==' 4}
{Test {S.isEmpty} '==' false}
{S.pop Y}
{Test Y '==' 3}
{Test {S.isEmpty} '==' true}

------------------------------------------
     What's different about Push and Pop now?
     How can you see this is stateful?
     How does the statefulness get reflected in the interface?
     How is the object represented?
     Why is it secure? 
  5. StackSecureStateBunProcDispatch.oz -- secure, stateful, bundled
------------------------------------------
% $RCSfile: StackSecureStateBunProcDispatch.oz,v $
declare
fun {NewStack}
   C={NewCell nil}
   proc {Push E} C:=E|@C end
   fun {Pop}
	 case @C
	 of X|S1 then C:=S1 X
	 end
      end
      fun {IsEmpty} @C==nil end
in
   stack(push:Push
	 pop:Pop isEmpty:IsEmpty)
end

% $RCSfile: StackSecureStateBunProcDispatchTest.oz,v $
\insert 'Test.oz'
\insert 'StackSecureStateBunProcDispatch.oz'
\insert 'StackStateBunTest.oz'

------------------------------------------
     How is the object represented?
     How does that differ from the previous version?
     Why do the same tests work?
     What are the efficiency differences?
     How does this differ from the stateless version?
  6. StackSecureStateUnbun.oz -- secure, stateful, unbundled
------------------------------------------
% File StackSecureStateUnbun.oz
\insert 'NewWrapper.oz'
declare
local
   Wrap Unwrap
   {NewWrapper Wrap Unwrap}
   fun {NewStack}
      {Wrap {NewCell nil}}
   end
   proc {Push S E} C={Unwrap S} in
      C:=E|@C
   end
   fun {Pop S}
      C={Unwrap S}
   in
      case @C
      of X|S1 then C:=S1 X
      end
   end
   fun {IsEmpty S} @{Unwrap S}==nil end
in
   Stack=stack(new:NewStack push:Push
	       pop:Pop isEmpty:IsEmpty)
end

% $RCSfile: StackSecureStateUnbunTest.oz,v $
\insert 'Test.oz'
\insert 'StackSecureStateUnbun.oz'
declare S X Y
S = {Stack.new}
{Test {Stack.isEmpty S} '==' true}
{Stack.push S 3}
{Test {Stack.isEmpty S} '==' false}
{Stack.push S 4}
{Test {Stack.isEmpty S} '==' false}
X = {Stack.pop S}
{Test X '==' 4}
{Test {Stack.isEmpty S} '==' false}
Y = {Stack.pop S}
{Test Y '==' 3}
{Test {Stack.isEmpty S} '==' true}

------------------------------------------
    How is this like the secure, declarative, unbundled version?
    How does it differ from that?
    How does it differ from the bundled stateful versions?
 C. Polymorphism (6.4.3)
------------------------------------------
          POLYMORPHISM

def: an operation is *polymorphic* iff
     it works correctly for arguments
     of different implementation types.

------------------------------------------
     What's an implementation type?
     What about in bundled data abstractions where the 'argument'
     is implicit?
     What are the advantages?
     Can each organization of ADTs be polymorphic?
     What is required to do polymorphism in the ADT (unbundled) style?
  1. Collection type
   a. unbundled, implemented by stacks
------------------------------------------
      UNBUNDLED (ADT) COLLECTION TYPE

% $RCSfile: CollectionSecureStateUnbun.oz,v $
\insert 'NewWrapper.oz'
\insert 'StackSecureStateUnbun.oz'
declare
local Wrap Unwrap
   {NewWrapper Wrap Unwrap}
   fun {NewCollection}
      {Wrap {Stack.new}}
   end
   proc {Put C X}
      S={Unwrap C}
   in
      {Stack.push S X}
   end
   fun {Get C}
      S={Unwrap C}
   in
      {Stack.pop S}
   end
   fun {IsEmpty C}
      {Stack.isEmpty {Unwrap C}}
   end
in
   Collection=collection(new:NewCollection
			 put:Put
			 get: Get
			 isEmpty:IsEmpty)
end

% $RCSfile: CollectionSecureStateUnbunTest.oz,v $
\insert 'Test.oz'
\insert 'CollectionSecureStateUnbun.oz'
declare C X Y
C = {Collection.new}
{Test {Collection.isEmpty C} '==' true}
{Collection.put C 3}
{Test {Collection.isEmpty C} '==' false}
{Collection.put C 4}
{Test {Collection.isEmpty C} '==' false}
X = {Collection.get C}
{Test X '==' 4}
{Test {Collection.isEmpty C} '==' false}
Y = {Collection.get C}
{Test Y '==' 3}
{Test {Collection.isEmpty C} '==' true}

------------------------------------------
        Is this stateful?
        How would you implement a version of collection that has
        the same interface, but that does sets instead of stacks?
        How would you work with both stacks and sets with this interface?
   b. bundled, implemented by stack
------------------------------------------
    BUNDLED (OBJECT) COLLECTION TYPE

% $RCSfile: CollectionSecureStateBun.oz,v $
\insert 'StackSecureStateBun.oz'
declare
fun {NewCollection}
   S = {NewStack}
   proc {Put X} {S.push X} end
   fun {Get} {S.pop} end
   fun {IsEmpty} {S.isEmpty} end
in
   collection(put:Put get:Get
	      isEmpty:IsEmpty)
end

% $RCSfile: CollectionSecureStateBunTest.oz,v $
\insert 'Test.oz'
\insert 'CollectionSecureStateBun.oz'
declare
C = {NewCollection}
{Test {C.isEmpty} '==' true}
{C.put 3}
{Test {C.isEmpty} '==' false}
{C.put 4}
{Test {C.isEmpty} '==' false}
X={C.get}
{Test X '==' 4}
{Test {C.isEmpty} '==' false}
Y={C.get}
{Test Y '==' 3}
{Test {C.isEmpty} '==' true}
   
------------------------------------------
        What is the difference?
        How would you implement a version of collection that has
        the same interface, but that does sets instead of stacks?
        How would you work with both stacks and sets with this interface?
  2. Binary methods
   How would you make a union operation on collections in these 2 styles?
  3. ad hoc vs. parametric
------------------------------------------
    AD HOC vs. PARAMETRIC POLYMORPHISM

In *ad-hoc* polymorphism, different code
  is run for different argument types.

E.g., (static) operator overloading

In *parametric* or *universal*
   polymorphism, the
   code is same for all types.
------------------------------------------
 D. parameter passing (6.4.4)
------------------------------------------
       PARAMETER PASSING MECHANISMS

                   action
             at call   at return  
mechanism  | copy:     copy:      Langs
===========|=============================
value        value     -          Java
reference    address   -          Oz
value-result address   result     Ada 83
             value
result       address   result     Ada out
name         address   -          Scala
             of thunk
need         address   -          Haskell
             of thunk

------------------------------------------
  1. call by reference
------------------------------------------
          CALL BY REFERENCE

For actuals           pass
=================================
 identifiers          address id denotes

 other expressions    address of temp
                          holding value

Makes aliases between:
   actual ids and formals

Found in:
      Fortran,
      Pascal (var params),
      C++ (& params),
      Oz

------------------------------------------
  2. call by value
------------------------------------------
          CALL BY VALUE

For actuals           pass
=================================
 all expressions      value

No aliasing, each formal has own location

Found in:
      C
      Java, C#,
      C++,

------------------------------------------
      If you have call by reference, how to simulate call by value?
      How would you write an increment procedure, Inc,
      to act like it was called by value in Oz?
  3. call by value-result, by result
------------------------------------------
          CALL BY VALUE-RESULT

For actuals           pass
=================================
 identifiers          address id denotes

 other expressions    address of temp
                          holding value

On return, copy final value from formal
           back to actual

No aliasing, each formal has own location
But can have interference at end

Found in:
      Algol W,
      Ada,

------------------------------------------
     What if actual arguments are repeated?
     What should call by result do?
      If you have call by reference, how to simulate call by value-result?
      How would you write an increment procedure, Inc,
      to act like it was called by value-result in Oz?
  4. call by name
------------------------------------------
          CALL BY NAME

For actuals           pass
=================================
 literals             value
 procedure literals   value (= closure)

 other expressions    address of thunk
                          (frozen actual)

Def: a *thunk* is a prameterless function

Can have interference throughout

Found in:
      Algol 60
      Scala

------------------------------------------
      Do you need macros if you have call by name?
      How would you write an increment procedure, Inc,
      to act like it was called by name in Oz?
  5. call by need
------------------------------------------
          CALL BY NEED

For actuals           pass
=================================
 literals             value
 procedure literals   value (= closure)

 other expressions    address of thunk
                          (frozen actual)

Can have interference throughout

Only evaluate thunk once,
     save value when used

Found in:
      Haskell
      Oz

------------------------------------------
      How would you write an increment procedure, Inc,
      to act like it was called by name in Oz?
 E. Revocable capabilities (6.4.5)
   What's a capability?
------------------------------------------
         REVOCABLE CAPABILITIES

Capability + method to revoke it

% $RCSfile: Revocable.oz,v $
declare
proc {Revocable Obj ?R ?RObj}
   C={NewCell Obj}
in
   proc {R}
      C := proc{$ M}
	      raise invokedError end
	   end
   end
   proc {RObj M}
      {@C M}
   end
end
------------------------------------------
        What does RObj do?
        What does R do?
        How does it work?
        Why did we need state for this?