Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

G6021 COMPARATIVE PROGRAMMING

1. Consider the following program written in Haskell syntax:

sq x = x*x

twice (f,x) = f(f(x))

inf x = inf (x+1)

(a)  Draw the reduction graph for twice (\x->x,3+4). Underline all redexes. [15 marks]

(b)  Describe in one sentence what is meant by the most general type of a function.  For each of the functions:  sq, twice and inf, give the most general type.                                                                            [15 marks]

(c) Are the following statements true? Give a one-sentence justification for each.

i.  inf (inf 0) is a well-typed expression.

ii.  inf (inf 0) will terminate with call-by-name strategy.

iii.  sq 4+ inf 4 is a well-typed expression.

iv. All well-typed Haskell programs terminate.                       [10 marks]

(d) Write a PCF function to add two numbers.   Include all types in your answer.      [10 marks]

2.   (a)     i.  For the following two types, draw the type trees and find the most general unifier, if one exists.

(A ! B) ! (B ! C) ! A ! C

D ! E ! D [10 marks]

ii.  Define a function in Haskell that has the most general type:

(A ! B) ! (B ! C) ! A ! C [10 marks]

iii.  Give the un-curried version of the function in Question 2(a)ii. Include the Haskell code and the type of this function.       [10 marks]

(b)  Explain why Prolog would fail to find a solution to the following program, and suggest two ways in which this can be resolved.

even(s(s(X)))      even(X).

even(0).

?even(Y). [10 marks]

(c) What is the occurs check? Give an example of the occurs check in both type reconstruction and Prolog evaluation.                      [10 marks]

3.   (a) Consider the following Haskell data type:

data Tree = Empty | Node Int Tree Tree

Write Haskell functions for the following operations:

i. mapTree: apply a function to each element of the tree. Give the most general type of your function.       [10 marks]

ii. flatTree:   Convert  a  Tree into  a  list.     You  can  use  append (++)  in  your  definition.     Give  the  most  general  type  of  this function.                                             [10 marks]

iii. flatTreeAcc:   Convert  a Tree into  a  list  using  an  accumulating parameter. You cannot use append (++) in your definition. Give the starting value for the accumulating parameter, and give the most general type of this function.                       [10 marks]

(b) Write Prolog clauses to convert a Tree data type into a list. You may use the append program in your answer.       [10 marks]

(c) Write Java classes to  represent the Tree data  structure.    Compare Java, Prolog, and Haskell for 1) representing this data type, 2) writing operations over this data type.                          [10 marks]