PPL20200629


SCHEME
Define the construct define-with-types, that is used to define a procedure with type constraints, both for the parameters and for the return value. The type constraints are the corresponding type predicates, e.g. number? to check if a value is a number.
If the type constraints are violated, an error should be issued.

E.g.
(define-with-types (add-to-char : integer? (x : integer?) (y : char?))
  (+ x (char->integer y)))
defines a procedure called add-to-char, which takes an integer and a character, and returns an integer.


HASKELL
We want to implement a queue, i.e. a FIFO container with the two operations
enqueue and dequeue with the obvious meaning. A functional way of doing this is
based on the idea of using two lists, say L1 and L2, where the first one is used
for dequeuing (popping) and the second one is for enqueing (pushing) When
dequeing, if the first list is empty, we take the second one and put it in the
first, reversing it This last operation appears to be O(n), but suppose we
have n enqueues followed by n dequeues; the first dequeue takes time
proportional to n (reverse), but all the other dequeues take constant time.
This makes the operation O(1) amortised that is why it is acceptable in many
applications.

1) Define Queue and make it an instance of Eq
2) Define enqueue and dequeue, stating their types


HASKELL (ii)
Make Queue an instance of Functor and Foldable

HASKELL (iii)
Make Queue an instance of Applicative

ERLANG
Define a "functional" process buffer, called fuffer, that stores only one value and may receive messages only from its creator. fuffer can receive the following commands:
'set' to store a new value
'get' to obtain the current value
'apply F' to apply the function F to the stored value
'die' to end
'duplicate' to create (and return) an exact copy of itself



SOLUTIONS

(define-syntax define-with-types
  (syntax-rules (:)
    ((_ (f : tf (x1 : t1) ...) e1 ...)
     (define (f x1 ...)
       (if (and (t1 x1) ...)
           (let ((res (begin
                        e1 ...)))
             (if (tf res)
                 res
                 (error "bad return type")))
           (error "bad input types"))))))


data Queue a = Queue [a] [a] deriving Show

to_list (Queue x y) = x ++ reverse y

instance Eq a => Eq (Queue a) where
    q1 == q2 = (to_list q1) == (to_list q2) 

enqueue :: a -> Queue a -> Queue a
enqueue x (Queue pop push) = Queue pop (x:push)

dequeue :: Queue a -> (Maybe a, Queue a)
dequeue q@(Queue [] []) = (Nothing, q)
dequeue (Queue (x:xs) v) = (Just x, Queue xs v)
dequeue (Queue [] v) = dequeue (Queue (reverse v) [])

instance Functor Queue where
    fmap f (Queue x y) = Queue (fmap f x) (fmap f y)

instance Foldable Queue where
    foldr f z q = foldr f z $ to_list q 

q1 +++ (Queue x y) = Queue ((to_list q1) ++ x) y

qconcat q = foldr (+++) (Queue [][]) q

instance Applicative Queue where
    pure x = Queue [x] []
    fs <*> xs = qconcat $ fmap (\f -> fmap f xs) fs


fuffer(Data, PID) ->
    receive
        {set, PID, V} ->
            fuffer(V, PID);
        {get, PID} ->
            PID!Data, fuffer(Data, PID);
        {apply, PID, F} ->
            fuffer(F(Data), PID);
        {die, PID} -> ok;
        {duplicate, PID} ->
            PID ! spawn(?MODULE, fuffer, [Data, PID]),
            fuffer(Data, PID)
    end.