02 02 2024 E TS

Page 1

Principles of Programming Languages, 2024.02.02 Important notes - Total available time: 2h (multichance students do not need to solve Exercise 1). - You may use any written material you need, and write in English or in Italian. - You cannot use electronic devices during the exam: every phone must be turned off and kept on your table. - You cannot use library functions not covered in class in your code. Exercise 1, Scheme (11 pts) Consider the following data structure, written in Haskell: data Expr a = Var a | Val Int | Op (Expr a) (Expr a) instance Functor Expr where fmap _ (Val x) = Val x fmap g (Var x) = Var (g x) fmap g (Op a b) = Op (fmap g a) (fmap g b) instance Applicative Expr where pure = Var _ <*> Val x = Val x Val x <*> _ = Val x Var f <*> Var x = Var (f x) Var f <*> Op x y = Op (fmap f x) (fmap f y) Op f g <*> x = Op (f <*> x) (g <*> x) instance Monad Expr where Val x >>= _ = Val x Var x >>= f = f x Op a b >>= f = Op (a >>= f) (b >>= f) Define an analogous in Scheme, with all the previous operations, where the data structures are encoded as lists – e.g. Op (Val 0) (Var 1) is represented in Scheme as ‘(Op (Val 0) (Var 1)). Exercise 2, Haskell (11 pts) Consider the following datatype definition. data F b a = F (b -> b) a | Null 1) Make F an instance of Functor, Applicative, and Monad. 2) Using an example, show what >>= does in your implementation. Exercise 3, Erlang (11 pts) Consider a list L of tasks, where each task is encoded as a function having only one parameter: a PID P. When a task is called, it runs some operations and then sends back the results to P, in this form: {result, <Task_PID>, <Result_value>}; a task could also fail for some errors. Define a server which takes L and runs in parallel all the tasks in it, returning the list of the results (the…