03 07 14

Page 1

Principles of Programming Languages 2014.07.03 Notes • Total available time: 2h. • Y ou may use any written material you need. • Y ou cannot use computers or phones during the exam. 1 Scheme A program collects data from different nodes of the network and put them in a list containing elements of different types - we call this list “unsorted”. E.g. (3 "bob" #(6 6 1) 4 #(1 2) -2 end 9) . We want to take from the unsorted list all the elements that are numbers or vectors: the numbers are summed, while the vectors are collected in another list (it is not necessary to maintain the order of the original list). To memorize the data, we introduce a structure called demuxed, that has two fields named num and vec. E.g. for the previous case: 5 and (#(6 6 1) #(1 2)) , respectively. 1.1 Imperative (5 pts) Define the demuxed data strucure, and a procedure (called demux-imperative) that has two parameters d and l. d is a demuxed data strucure, while l is an unsorted list. This procedure must update d with data from l, stopping when the element end is found, if present. 1.2 Tail recursive (6 pts) Assume that demuxed is immutable. Define a functional, tail-recursive proceduredemux-tail-rec that takes an unsorted list and returns a demuxed data structure containing the data, processed as in before. Y ou may use as many additional parameters as you need, but you must specify their initial value. 2 Haskell Consider a variant of the problem seen in Exercise 1: an unsorted list can contain list of elements of some type, integer numbers, or the special value End. E.g. (in a pseudo-Haskell syntax) [3, [6, 6, 1], 4, [1, 2], -2, End, 9] . 2.1 Data structures (5 pts) Define the data structure for the unsorted list, and Demuxed, analogous to the structure introduced in Exer- cise 1 (i.e. with two…