03 09 12

Page 1

Principles of Programming Languages, 2012.09.03 Notes: - Total available time: 2h. - You may use any written material you need. - You cannot use computers, phones or laptops during the exam. Exercise 1, Scheme (11 pts) Let us consider trees memorized in Scheme as hierarchical lists (e.g. numeric expressions like (+ 2 3 (- 4 5) (/ 3 2))). 1. Define a short, purely functional version of procedure numnodes, that accepts a tree and returns its number of nodes (e.g. (numnodes '(+ 2 3 (/ 1 3) (- 2 2 4 -7)))) should return 11). 2. Define a lower-level, efficient, purely iterative version of numnodes. 3. Comment the following code, giving meaningful names to capitalized elements (i.e. H1 V1 …). Also, please show a meaningful example usage. (define (H1 H2) (call/cc (lambda (V1) (for-each (lambda (x) (call/cc (lambda (V2) (V1 (cons x V2)) ))) H2) 'V3))) Exercise 2, Haskell + Prolog (9 + 6 pts) 1. Define a datatype Exp to represent generic expressions containing symbols and numbers e.g. b(b(3,4,5),node(d,e)). 2. Declare Exp as an instance of Show, such that we can obtain representation exactly like "b(b(3,4,5),node(d,e))" (i.e. deriving Show is considered unacceptable) 3. Define a function, called subst, that accepts an expression e and two atoms, x and y, and returns a new expression e' where every instance of x is replaced by y. 4. Define a simplified version of subst in Prolog, considering that expressions are at most binary (e.g. a(1,b(a,2)) is acceptable, while b(b(3,4,5),node(d,e)) is not. Exercise 3, C++ (6 pts) Alice is a young programmer. She is starting learning C++. Figure X (below) is one of the first programs she has written, a map of interconnections among some cities. Inner classes ConstDerefIterator and City are reported in Figure Y and in Figure Z respectively.…