24 07 15

Page 1

Principles of Programming Languages 2015.07.24 Notes • NAME: __________________________________ • Did you present a small project? YES / NO • 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 1.1 Urmax (6 points) Define a tail recursive procedure, called urmax, that takes a list of lists ((a1 1a1 2a1 3...)(a2 1a2 2a2 3...)(a3 1a3 2a3 3...)...) and returns (max a1 1 a2 2 a3 3 ...). E.g. (urmax ’((-1)(1 2)(1 2 3)(10 2 3 -4))) is 3. 1.2 Higher order functions (5 points) Define a variant of urmax based on higher order functions like map (you cannot use iterative loops or recur- sion in it). 2 Haskell 2.1 Lists as instances of Num (6 points) Make lists of numbers a instances of the class Num. If the two lists have different length, you must assume that the missing elements of the shorter are all 0. E.g. [1,2,3] * [2,-1] should be [2,-2,0]. (Remember that you need to define methods for +, -, *, abs, signum, and fromInteger.) 2.2 List of lists of lists... (3 points) Define a recursive data structure of type TT which can be used to represent lists of Int of any depth (e.g. in Scheme ’(1 2 (3 9) ((1) -7)) ). 1 2.3 Lile (3 points) Define a predicate lile, which, given a TT value, check if it contains its own length. E.g., using a Scheme-like notation (lile ’(2 1)) holds, while (lile ’(1 2 1)) does not. 2.4 Lileg (5 points) Define a version of the predicate lile, called lileg, which takes a value of typeTT, and check if all the lists in it contain their length. E.g., using a Scheme-like notation: (lileg ’(2 (2 (1)) 3)) must hold. 3 Prolog (5 points) Define a non-deterministic Finite State Automata simulator in Prolog. 2 Solutions Scheme (define (urmax LL) (define (urr LL k m) (if (null? LL) m (let* ((x…