Submission instructions:

Submit a single Scheme .ss file. Write the solution to the second exercise as a comment.

---------------------------------------

1. Consider the interpreter for BCFAE here:
http://www.daimi.au.dk/~ko/teaching/pl/plt8-boxes.ss

Your task is to thread the store through the interpreter
using the following Monad and helper functions:



; M a = s -> Value*Store (a,s)   for any store type s

; note the generalized contract - we use the datatype
; as a general pair constructor
(define-type Value*Store
  [v*s (value any/c) (store any/c)])

; bind: M a -> (a -> M b) -> M b
(define (bind f g)
  (lambda (s)
    (type-case Value*Store (f s)
      [v*s (v s2) ((g v) s2)])))

; return : a -> M a
(define (return x) (lambda (s)  (v*s x s)))

; get : M s
(define (get s)
  (v*s s s))

; put : s -> M ()

(define (put s)
  (lambda (_) (v*s empty s)))


Feel free to use the "do" macro:

(define-syntax do
  (syntax-rules (<-)
    ((do expr              ) expr)
    ((do (v <- expr) . rest) (bind expr (lambda (v) (do . rest))))
    ((do expr        . rest) (bind expr (lambda (v) (do . rest)))))) 



After your transformation, the type of the interp function should be

; interp: Expr Env -> M BCFAE-Value, where s = Store

and a test of the interpreter should look like

((interp mytestprogram (emptyEnv)) (emptyStore)))

Furthermore, the interpreter should never expose the structure of the Monad,
i.e., all operations are build using only bind/return/get/put, but never
constructed directly by hand (e.g., "lambda (store) ...)").

---------------------------------------------------------------------------


2. To qualify as a monad, one does not only need a type constructor and a
bind/return implementation of the correct type. In addition, monads must
respect the following three algebraic laws:

a) (bind (return x) f)  == (f x)
b) (bind m return) == m
c) (bind (bind m f) g) == (bind m (lambda (x) (bind (f x) g))) 


i. Rephrase the laws in terms of do-notation
ii. Prove that the identity monad and the Maybe monad satisfy the laws.
iii. Discuss why monads should obey these laws