01 09 2022 E TS

Page 1

Principles of Programming Languages, 2022.09.01 Important notes - Total available time: 2h. - You may use any written material you need, and write in Italian, if you prefer. - 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 (10 pts) We want to implement a version of call/cc, called store-cc, where the continuation is called only once and it is implicit, i.e. we do not need to pass a variable to the construct to store it. Instead, to run the continuation, we can use the associated construct run-cc (which may take parameters). The composition of store-cc must be managed using in the standard last-in-first-out approach. E.g. if we run: (define (test) (define x 0) (store-cc (displayln "here") (set! x (+ 1 x))) (displayln x) (set! x (+ 1 x)) x) (test) we will get: here 1 2 and if we call (run-cc) we get: 2 3 and the continuation is discarded. Exercise 2, Haskell (10 pts) We want to implement a binary tree where in each node is stored data, together with the number of nodes contained in the subtree of which the current node is root. 1. Define the data structure. 2. Make it an instance of Functor, Foldable, and Applicative. Exercise 3, Erlang (12 pts) We want to implement a parallel foldl, parfold(F, L, N), where the binary operator F is associative, and N is the number of parallel processes in which to split the evaluation of the fold. Being F associative, parfold can evaluate foldl on the N partitions of L in parallel. Notice that there is no starting (or accumulating) value, differently from the standard foldl. You may use the following libray functions: lists:foldl(<function>, <starting value>, <list>) lists:sublist(<list>,…