10 02 16 1

Page 1

Principles of Programming Languages 2016.02.10 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. Introduction Figure 1: Simply-linked circular list (Clist) A simply-linked circular list (called Clist from now on) is a list in which the last node points to the first node (see figure). It is sometimes useful to have a sentinel last node, i.e. a node that does not contain data. The sentinel is used e.g. to check if we have traversed the whole list. An empty list contains only the sentinel node, that points to itself. 1 Scheme 1.1 Data structure definition and constructors (7 points) Define a data structure for Clists (hint: use struct), together with a constructor for an empty Clist, and a variant of the cons operation for Clists, which adds a new element as the head of the previous Clist. 1.2 Map (4 points) Define cmap, a map operation for Clists. 1 2 Haskell 2.1 Type definition and Eq (5 points) Define a data structure for Clists with a data declaration. Make Clist an instance of Eq – beware: equality test must always terminate. 2.2 Conversions from/to ordinary lists (6 points) Define two functions list2clist and clist2list, that are used to convert an ordinary list to a Clist, and vice versa. Write their types. 2.3 Map (6 points) Define cmap, a map operation for Clists. Write its type. 3 Prolog (5 points) Define a predicate with one argument to check if a given string is a palindrome. E.g. palindrome("sator arepo tenet opera rotas") should return true. 2 Solutions Scheme (struct cnode (value next) #:mutable) (define *end* ’---end---) (define (cend) ; builds a sentinel node (let ((node (cnode *end* #f)))…