riccardotommasini/ppl

This repository contains the material related to the practical classes of the course Principles of Programming Languages

Principle of Programming Languages

This repository contains the material related to the practical classes of the course Principles of Programming Languages

Slack channels is available here to discuss about course issues and PPL related topis. Use @polimi.it or @mail.polimi.it email to access it.

Old Courses Material (Git Tags)

• 2016
• 2017

05/10/2018 Scheme 1

• Basic Concepts: recursion, tail recursion, conditional structures, variable binding (define, let), named let

23/10/2018 Scheme 2

• Higher Order Functions: map and fold
• Structs: trees
• Macros:
  • (++)
  • motivating example: thunking
• Continuation: code comparison break vs continue

26/10/2018 Scheme 3

• Macros + Continuations:
  • for in
  • break and continue
  • try-catch
  • coroutines

09/11/2018 Haskell 1

• data vs newtype
• higher-order functions
• pattern matching
• strict vs lazy

20/11/2018 Haskell 2

• trees
• functor
• foldable
• type class

23/11/2018 Haskell 3

• tree2
• tconcatmap
• applicative

04/12/2018 Haskell 4

• state monad
• exercises on it

18/12/2018 Erlang 1

• hello world
• pub sub example

21/12/2018 Erlang 2

ppl's Issues

change repository name to PPL

Reasoning on State monad and unwrapping of do notation

In my journey to understand the State monad I decided to try and unwrap the do notation into a series of binds (>>=) and subsequently apply the bind definition to further understand how the value and the state in a State monad are carried on between bound computations.

This post is intended as a way to confirm what I think happens and to correct my thoughts in case I understood it wrong.

Anyways, here is the starting snippet
runState (do { cur<- getState; putState(cur+1) ; return "a" }) 34
which results in ("a", 35)

I copy here also the useful definitions.

data State s a = State {runState :: s -> (a, s)}

instance Monad (State s) where
    return = pure
    sa >>= f = State $ \s -> 
        let (a, s') = runState sa s
            sb = f a
            (b, s'') = runState sb s'  
            in (b, s'')

getState :: State s s 
getState = State $ \s -> (s, s)

putState :: s -> State s ()
putState new = State $ \_ -> ( (), new)

From the bind (>>=) implementation it is pretty clear how the value a is transmitted to the function f, what is not so clear is how the state s is carried as well and how modifications to it (like the ones made by putState) are executed and persisted.
Or at least, it wasn't for me.

First step is to translate the do notation into a series of binds
runState ( getState >>= (\cur -> putState (cur+1) >>=(\_-> return ("a"))) ) 34

Let's call State a the result of all the computation inside runState's argument
State a = getState >>= (\cur -> putState (cur+1) >>=(\_-> return ("a")))

We know that State a will be a state that when run will return a function which will take a state (34 in this case) and return a tuple (value, newState).

Applying the definition of bind to State a we get this

State a = State $ \34 ->
	let (34, 34) = runState getState 34
		b = f 34
		(b, s'') = runState b 34
		in (b, s'')

getState returns a tuple with the state given to it both as value and newState, that's why I already "executed" it.
As per definition the value (34) will be fed to f, the newState (34) will be fed to b when running it.

What is f?
b = f 34 = (\34 -> putState (34+1) >>=(\_-> return ("a")))
it will return the State b, that once run will return a function which will expect an s and give back a tuple

Unwrapping once again what is happening in f..

State b = State $ (\s -> 
   let (v,s’) = runState (putState (34+1)) s
          c = f2 v
         (v’,s’’) = runState c s’
         in (v’,s’’)

again, what's f2?
f2= (\_-> return ("a"))

Notice that the lambda discards the argument because in the do notation a line without the "var<-" part corresponds to (>>) which translates to ... >>= (_ -> ...)

return ("a") is immediate from the definition. I call the result State c.
State c = State (\s -> ("a" , s))

Now we can start to go upwards. We know that "c = f2 v" is State c, that when run will take a state and return a tuple with "a" as value and a newState.
Remember also that the result of putState is discarding whatever s it receives and putting its argument as the new state, () as the value.

State b = State $ (\s -> 
	let ((),35) = runState (putState (34+1)) s -- s is ignored by putState
               c = State (\s -> ("a" , s) -- f2 ()
               ("a",35) = runState c 35
               in ("a",35)

As per (>>=) definition, c will be run with the state resulting from running putState, which is 35.
the value "()" is discarded in favor of "a" by f2

The result appears to be already there, but how is it transferred towards outer functions?

Now that we know what State b is let's substitute it

State a = State $ \34 ->
	let (34, 34) = runState getState 34
		b = State (\s -> ("a", 35)
		("a", 35) = runState b 34
		in ("a", 35)

Since putState ignored the s in favor of 35, and return only concerned itself with the value "a", state b will always be a function giving back the tuple ("a", 35) in response to whatever s we throw at her.
this means that runState b 34 is ("a", 35), and that's the result of running State a.

The complete (not executable) unwrapping is attached, rename it as .hs and use a wide monitor if possible.
stateExe2.txt

Again, this is just the transcription of my reasoning, so that you can correct me if i'm wrong and stop my nightmares. Please.

TdE 20170705

In class we saw this exercise taken from the above mentioned exam

-- 2) Define a purely functional (i.e. non destructive)
-- version of the reverse presented in Es. 1.3.
-- which takes a binary tree and keeps
-- it structure, but “reversing” all the values in the leaves
-- E.g.

-- t1 = Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3),
-- E.g. revtree t1 is Branch (Branch (Leaf 3) (Leaf 2)) (Leaf 1).

we solved it this way

tfringe :: Tree a -> [a]
tfringe Nil = []
tfringe (Leaf v) = [v]
tfringe (Branch l r) = (tfringe r) ++ (tfringe l)

revtree :: Tree a -> Tree a
revtree t1 = a where 
	(a,_) = revtree' t1 (tfringe t1) where
		revtree' :: Tree a -> [a] -> (Tree a, [a])
		revtree' Nil xs = (Nil,xs)
		revtree' (Leaf v) (x:xs) = ((Leaf x),xs)
		revtree' (Branch l r) xs = let (l', xs') = revtree' l xs;
									   (r', xs'') = revtree' r xs'
								    in ((Branch l' r'),xs'')

Unless I understood something wrong, the revtree of a tree like

let t3 = (Branch (Branch (Leaf 3) (Leaf 4)) (Branch Nil (Leaf 5)))

should be

(Branch (Branch (Leaf 5) Nil) (Branch (Leaf 4) (Leaf 3)))

while the above solution gives

Branch (Branch (Leaf 5) (Leaf 4)) (Branch Nil (Leaf 3))

and this is because in revtree' whenever we pattern match a (Nil,xs) we substitute it with (Nil,xs)
which doesn't work when the Nil is not in a symmetrical position.

how can we solve this issue?

It would suffice to write down Nil in our list given by tfringe whenever it is matched (and not []), but Nil is of type Tree, not of type a and the compiler gives an error on types when trying to build a list of a

I remember it being addressed in class but missed the answer.
Any help would be appreciated, Thanks.

Exercise on continuations from 20170720 exam

@riccardotommasini Can you give me some feedback on the solution I tried to come up with on this exercise from 20170720 exam? Thank you! 😄

Exercise 1

Consider the following code:

(define (print+sub x y)
    (display x)
    (display " ")
    (display y)
    (display " -> ")
    (- x y))

(define (puzzle)
 (call/cc (lambda (exit)
            (define (local e)
             (call/cc
              (lambda (local-exit)
                (exit (print+sub e
                                 (call/cc
                                 (lambda (new-exit)
                                  (set! exit new-exit)
                                  (local-exit #f))))))))
            (local 6)
            (exit 2))))

1. Describe how it works.
2. What is the output of the evaluation of (define x (puzzle))? What is the value of x?
3. Can you see problems with this code?

Solutions

Assumption: While discussing the execution of this program I assume that the call-with-continuation is implemented with a stack-strategy.

Question no. 1

Immediately after puzzle is invoked, the call/cc expression causes the creation of a continuation object named exit pointing right at the end of function puzzle. After defining function local, the execution procedes by evaluating (local 6). The call/cc within local causes the creation of a new continuation object named local-exit pointing right before the evaluation of the expression (exit 2). Execution procedes by evaluating the exit object with expression e1 = (print+sub e ...).

My speculation here is that the address of the exit object is pushed on the execution stack at this very moment; the purpose of this comment will become clear later.

So we need to evaluate expression e1 which require us to evaluate first e and e2 = (call/cc (lambda (new exit) ...)). The evaluation of call/cc in e2 creates a new continuation object named new-exit pointing within the evaluation of (print+sub e e2).

Going with the evaluation of e2 we set varibale exit to new-exit so now exit and new-exit point to the same continuation (i.e.: within the evaluation of (print+sub e e2)).
Then we evaluate (local-exit #f). This causes the stack to be replaced with the continuation object pointed by local-exit, that is the evaluation of (exit 2). But now exit points to the same continuation of new-exit causing the evaluation of (print+sub e 2).

The evaluation prints on stdout the value of e and " 2 -> ", returning the result of e - 2. At this point we can evaluate the expression (exit e1) with e1 = e - 2. At first glance, you might think that because exit was set to new-exit we replace the current continuation with the one pointed by new-exit, causing again the evaluation of print+sub and looping over and over.

Although, because of what I speculated above, the address where to jump after evaluating exit is already set on the execution stack, so it points to the original continuation, i.e. at the end of function puzzle. So eventually, the evaluation of puzzle returns e - 2 .

Question no. 2

Replacing e with 6 in the description above, we understand that the program prints on the stdout the following:

6 2 -> 

and the value of x is 4.

Question no. 3

I can only spot one problem (aside from the cruelty of the exercise designer). I did not read the Scheme standard, but the behavior of this piece of code could be undefined, i.e. interpreter-implementation dependent. In fact, if the evaluation of (exit (print+sub e ...)) is lazily evaluated, i.e. the continuation object pointed by exit is looked up only when all the expression parameters have been evaluated, we end up with a different behavior, that is: a loop as described above.

[LAST ERLANG CLASS] Easier brancy?

What if we simply impose an order in the reception of the messages from the subtrees?
They'll just stack in the mailbox, no deadlock should arise:

brancy(L, R, Fun) ->
	receive
		{ask, P} ->
			% they ask their sons for the values
			L ! {ask, self()},
			R ! {ask, self()},
			% at this point you expect an answer...
			receive
				{L, V1} -> Op1 = V1
			end,
			receive
				{R, V2} -> Op2 = V2
			end,
			% now you evaluate your function for the father
			P ! {self(), Fun(Op1, Op2)}
	end.

This sounds easier to me...

Use tags to archive course material

Pattern matching and data types

I'm trying to solve the 99 Haskell questions that you find at this link

I'm dealing with the following problem:

Flatten a nested list structure.

Transform a list, possibly holding lists as elements into a `flat' list by replacing each list with its elements (recursively).

It is said that a new data type is needed since Haskell's built-in lists are homogenous.
This is the new data type:

data NestedList a = Elem a | List [NestedList a]

Then the function is defined as follows:

myFlatten :: (NestedList a) -> [a]
myFlatten (Elem a ) = [a]
myFlatten (List (x:xs)) = (myFlatten x) ++ (myFlatten (List xs))
myFlatten (List []) = []

I don't understand how pattern matching works in this case from the theoretical point of view.
For example, if we consider

myFlatten (Elem a ) = [a]

In this caseElem ais a data constructor, right?
But how does pattern matching work in general with user-defined data types?

Regards,

Luca

exercise on continuations (from previous course)

Hello, I was looking at an exercise presented in a previous course (here: https://github.com/gioenn/pl/blob/master/ex4.rkt)

it mimics a parallel computation with tasks, a queue and accessory coroutines like enqueue, dequeue, fork and yield.

code is as following

(define *queue* '())

(define (empty-queue?)
  (null? *queue*))

(define (enqueue x)
  (set! *queue* (append *queue* (list x))))

(define (dequeue)
  (let ((x (car *queue*)))
    (set! *queue* (cdr *queue*))
    x))

(define (fork proc)
  (call/cc (lambda(k)
             (enqueue k)
             (proc))))

(define (yield)
  (call/cc (lambda(k)
             (enqueue k)
             ((dequeue)))))

(define (c-exit)
  (if (empty-queue?)
      (exit)
      ((dequeue))))

(define ((do-stuff-n-print str max))
  (let loop ((n 0))
    (display str)
    (display " ")
    (display n)
    (newline)
    (yield)
    (if (< n max)
        (loop (+ 1 n))
        (c-exit))))

(define (main)
  (begin
    (fork (do-stuff-n-print "This is A" 3))
    (fork (do-stuff-n-print "This is B" 4))
    (displayln "End")
    (c-exit)))

running (main) will fork A and B and display "end".

this is the output:

This is A 0 
This is B 0
This is A 1
End
This is B 1
This is A 2
This is B 2
This is A 3
This is B 3
This is B 4

in my understanding each fork puts in the queue the continuation (at the point it is called) and then call the process being forked.

When fork A 3 is called , the continuation and therefore what is enqueued should be "fork B, display end".

Afterwards process "do stuff n print A 3" is called, it will print "A 0" and yield.

Yield enqueues the continuation (this time it will be the loop inside dostuffnprint) and executes the result of dequeue ( there are double parenthesis around dequeue in yield).

The result of dequeue is the fist of the queue "fork B, display end, loop A=0" -> fork B.
The fork will enqueue the continuation (which should be display END ?) and executes dostuffnprint B 4.
"B 0" will be printed and yield called which will enqueue the loop in B.

At this point the queue should be "display end, loop A=0, (display end?), loop B=0"
and in my understanding "display end" should be called;
WHICH DOESN'T HAPPEN because another round of loop in A -> A 1 is called before printing end and continuing with alternating the two "processes", without calling end again even it is part of the continuation of fork A and of the continuation of fork B.

so what i don't understand is:

• why there is another round of A 1 instead of calling immediately display end after A 0 and B 0
• why display end is not called twice

i'm sure it is something silly i can't grasp, but i figured to ask it here and not privately to share the knowledge.

Thanks,
Massimo.

use issue to catch student questions

BLACK JACK WITH COROUTINES, TRY-CATCH AND STRUCTS

Blackjack

A player consists of two elements

1. A data structure that contains the turn in hand (continuation), name and current score
2. a function/macro encapsulating the player behavior (why a macro, because I may want to standardize it as (play actions ... until conditions ... pass (yield) )

When a player reaches 21 set its status to winner
When a player goes beyond 21 throws a loosing exception
A player can yield the next turn
The status of the game correspond to several co-routines representing the players
the game stops, i.e., it must be re-evaluated (but cards remain the same) when a player wins

Interesting, implements the split when a player has two or more cards can split his/her game and proceed as it if what two players

Soluzioni tema d'esame 8.2.2019

Buongiorno, ho letto le soluzioni dell'esercizio di haskell e mi sembra di capire che tale versione non rispetti la interchange law (http://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Applicative.html) degli applicative:

La definizione è questa:

instance Applicative BFlist where
	pure x = BFlist Fwd [x]
	x <*> y = bflconcatmap (\f -> fmap f y) x

Pure crea una BFlist in direzione forward, come ci si aspetta, mentre <*> invoca bflconcatmap passando come argomenti x e una lambda. Questa lambda utilizza fmap delle BFList, definita come

	fmap f (BFlist d x) = BFlist d (fmap f x)

Poichè fmap non può cambiare la direzione della lista si ha che la lambda utilizzata nella definizione di applicative può esclusivamente ritornare bflist che hanno la stessa direzione di y.

Questa lambda è utilizzata in bflconcatmap

	bflconcatmap f x = bflconcat $ fmap f x

bflconcatmap invoca bflconcat passando come argomento fmap f x.
Come prima, questa fmap può solo ritornare una lista che ha la stessa direzione di X.
Questo implica l'argomento di bflconcat diventa (BFlist (DIR_X) [(BFlist (DIR_Y) [content]), ...]). Cioè una BFList che ha la direzione di x e che contiene delle bflist che hanno la direzione di y.

A questo punto bflconcat, definita come:

bflconcat (BFlist d v) = foldr (<++>) (BFlist d []) (BFlist d v)

invoca foldr, la quale opera all'interno della bflist più esterna, e ragiona esclusivamente sulle liste interne, concatenandole. La conseguenza è che la direzione di x è ignorata al fine di calcolare il risultato e la direzione sarà sempre uguale a quella di y, e la concatenazione delle liste interne avviene come una concatenazione comune, perchè tutte le direzioni sono uguali.

Infatti, testandolo risulta

*SOLUTION> bb = (BFlist Bwd [(+1), (+2), (+3)])
*SOLUTION> bf = (BFlist Fwd [(+1), (+2), (+3)])
*SOLUTION> bf <*> (BFlist Fwd x)
+[2,3,4,3,4,5,4,5,6]
*SOLUTION> bf <*> (BFlist Bwd x)
-[2,3,4,3,4,5,4,5,6] 
*SOLUTION> bb <*> (BFlist Fwd x)
+[2,3,4,3,4,5,4,5,6]
*SOLUTION> bb <*> (BFlist Bwd x)
-[2,3,4,3,4,5,4,5,6]      

ma questa è una violazione delle leggi degli applicative, poichè dovrebbero rispettare

u <*> pure y = pure ($ y) <*> u 
(oppure u <*> pure x = pure (\f -> f x) <*> u)

u <*> pure y avrà sempre una direzione pari a Fwd, poichè pure inizializza il membro a destra con tale valore.
Mentre pure ($ y) <*> u avrà sempre una direzione pari a quella di u. Il che significa che se u è uguale a (BFlist Bwd Content) allora la legge non è rispettata.

è questo ragionamento corretto o esiste un qualche passaggio che non ho compreso?

Distinti saluti.

Did I get this right?

I don't know if this is a meaningful comment but I was reasoning for a hour an half on this piece of code to understand it properly and I think I got somewhere. I'd like to check with you if my reasoning is correct.

I was trying to justify why the code is working by taking a look at the type of the <*> operator. So the signature is:
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
And we implement it for State this way:
(State f) <*> (State d) = ...

Because State is of kind * -> * -> * it is parametric in 2 types, while the Applicative operator requires an applicative of kind * -> *. So we overload the applicative class for State by making it parametric with this line:
instance Applicative (State s) where ...

So, in the overloading of <*> for State, the types a and b in f (a -> b) -> f a -> f b refer to the result types of States! Namely the a in newtype State st a = State {runState :: st -> (a, st)}.
Here's why we can write the following line of code:
... in (f' f'', s'') ...

In this code, f' is the result of the left-hand-side operand of <*> which, by definition of <*>, has type (a -> b) so it is a function. Hence we can apply it to the result of the right-hand-side operand which is of type a.

That wasn't clear to me at the first place, I'm not sure whether this was stated in the class because I missed it but it took me a while to figure that out. And it may be wrong. I'd appreciate some feedback on this to check if what I said is true. Thanks.

ppl/haskell/Prepared/ESE20171205.hs

Lines 32 to 47 in a61508c

	-- (<*>) :: Applicative f => f (a -> b) -> f a -> f b
	instance Applicative (State s) where
	pure a = State $ (\s -> (a, s))
	(State f) <*> (State d) = State $ \s ->
	let (f', s') = f s
	(f'', s'') = d s'
	in (f' f'', s'')
	-- The (<*>) action takes the input state,
	-- and obtains the function f and an updated state st,
	-- then passes the updated state s' to f, obtaining
	-- the argument f'' and an updated state s'', and finally
	-- we package up the application f' f'' and the final state s'' into a pair.
	-- It is important to understand that (<*>) specifies an order
	-- in which the state is used: left-hand (function) argument first,
	-- then the right-hand argument.