University of Sussex Informatics
Spring 2020
Limits of Computation
Assignment 1 (Deadline 5.03.2020, 4pm)
You need to submit your answers electronically on Canvas at the E- submission point. You must submit several files as specified in this assignment. One file must be a pdf file containing the answers to Questions 1–4. Please make sure that all answers for Questions 1–4 are in one single document. In case you use Word, please ensure that you convert your file into a pdf document before submission1.
Your submission must also contain the files containing the programs that answer Questions 5 and 6. For Question 5 you must submit a file concat.while and a file concat.F. For Question 6 you submit a file intF.while and potentially additional programs that intF calls as macros. For our test rig to be able to execute your files, please give the files the specified name. You may call programs published on the Canvas site and those don’t need to be included in your submission.
Please do not write your name anywhere, but it is advisable to in- clude your candidate number as comment in each submitted docu- ment. Please make sure you check after submission that you actually have submitted the correct files.
YOU MUST WORK ON THE ASSIGNMENT ON YOUR OWN! The standard rules for collusion and plagiarism apply and any cases dis- covered will be reported and investigated.
There are SIX questions and you must answer all of them. They cover the material of Lectures 1 to 7.
1In Word, this works usually by using the printing menu and then saving as pdf instead of sending to a printer.
1
The language F
The language F is a simple functional language that uses the data type of binary trees you know from WHILE. F-programs consist of one expression that can make use of one recursive function definition.
Let us make this more precise by giving the syntax of the language.
⟨program ⟩ ⟨expression ⟩
::= in X out ⟨expression⟩ where f(X) ::= X
= ⟨expression⟩
nil |
cons ⟨expression⟩ ⟨expression⟩ |
hd ⟨expression⟩ |
tl ⟨expression⟩ |
if ⟨expression⟩ then ⟨expression⟩ else f(⟨expression ⟩)
⟨expression⟩ |
A program is an expression with one (fixed) input variable X and one output which is the result of an expression. The expression can refer to one recursive definition of a function called f with fixed formal parameter X. Note that X is the only variable in use, as (global) input variable to the program as well as the local argument of function f. The latter means that f can never directly access the program’s global (input) variable.
The first five clauses for expressions are also available in (core) WHILE. But an F-expression can also be a conditional2 or a function application of the form f(E). Note that there is always just one such function definition and the name of the function is fixed as f. The function may, of course, be called many times, also in a nested fashion. For instance, cons f(X) f(nil) is a legal expression as aref(f(X))andf(cons f(hd X) f(f(X))).
As an example, here is the WHILE-program add from our lectures written as F- program. As usual, the two inputs are wrapped up in a single list:
in X out f(X) where f(X) = if hdX
then cons nil f(cons tl hd X cons hd tl X nil)
else hd tl X
It implements the usual recursive definition of addition : n+m = succ(predn+m) ifn>0
n+m = m ifn=0 2In WHILE we also have these conditionals but as statements.
2
where succ n denotes the successor of n (which in binary tree encoding terms is cons nil n) and pred n denotes the predecessor of n (which in binary tree encoding terms is tl n). Note that the input is a list of two numbers so hd X andhd tl Xcorrespondtonandm,respectively.
The semantics of F-programs is given by a function [•]F : F-Program → D → D⊥
defined formally as follows:
[in X out E where f(X)= B]F v = F[E] B v where the expression semantics function F[•] has type:
F[•] : F-expression → F-expression → D → D⊥
First of all, compared to the expression semantics of WHILE, we note that there is an extra second argument of type F-expression, B. This is used to “carry around” (or “memorise” , “pass along”) the body of the function definition such that it can be used whenever we find a call to function f. We also note that there is no store argument. This is obvious considering that the language F is a functional language so there is no assignment and thus there are no variables to assign to. But there is variable X which receives its value from the program call (used as input variable) or as formal parameter of function f (if used as formal parameter of f). The value of X is the last argument v of F[•].
Analogously to WHILE, we thus define:
F[X]Bv
F [nil] B v F[consEF]Bv
F[hdE]Bv
= v
= nil
= ⟨F[E]Bv.F[F]Bv⟩
d ifF[E]Bv =⟨d.e⟩ = nil otherwise
e ifF[E]Bv =⟨d.e⟩ = nil otherwise
F[B]Bd ifF[E]Bv=d∈D F[f(E)] B v = ⊥ otherwise
The semantics of if E then F else G is as usual: first evaluate E. If E evaluates to nil evaluate G else evaluate F .
The questions start on the next page. 3
F[tlE]Bv Function application is defined as:
Questions
1. The (semantics of) language F uses the binary tree data type D we already know from WHILE. Consider the following elements in D:
(a) ⟨⟨nil.nil⟩.⟨⟨nil.nil⟩.⟨⟨nil.nil⟩.⟨⟨nil.nil⟩.nil⟩⟩⟩⟩
(b) ⟨⟨⟨nil.nil⟩.⟨nil.nil⟩⟩.⟨⟨nil.nil⟩.nil⟩⟩
(c) ⟨⟨nil.nil⟩.⟨⟨⟨nil.nil⟩.nil⟩.⟨⟨nil.nil⟩.⟨⟨⟨nil.nil⟩.nil⟩.⟨nil.nil⟩⟩⟩⟩⟩ (d) ⟨⟨nil.nil⟩.⟨⟨nil.nil⟩.⟨⟨nil.nil⟩.⟨⟨nil.⟨nil.nil⟩⟩.⟨nil.nil⟩⟩⟩⟩⟩
According to our encoding of datatypes in D, decide for each tree (a)–(d) whether it encodes
i a list of numbers; if it does give the corresponding list.
ii a list of lists of numbers; if it does give the corresponding list.
Note that an empty list can always be considered a list of numbers and a list of lists of numbers. [20 marks]
2. Describe what the following F-program p computes for arbitrary input:
in X out cons nil f(X)
where f(X) = if X
then cons nil f(tl X)
else nil
Your description should explain the result for any input d ∈ D and should refer to d. Your explanation must not narrate what or how the program exe- cutes but describe the function it implements. [10 marks]
3. Let us encode F-programs as data by the following encoding that uses lists (which we already know how to encode in D):
input X outputEwhere f(X)=B = X = nil = cons E F = hd E = tl E = if E then F else G = f(E ) =
[E,B]
[var]
[ quote, nil ] [cons,E,F] [hd,E] [tl,E] [if,E,F,G] [ appf, E ]
For instance, the data representation of the program p in Question 2 is as follows:
4
[
[cons,[quote,nil],[appf,[var]]] ,
[if,[var],[cons,[quote,nil],[appf,[tl,[var]]]],
[quote,nil]
] ]
Give the data representation of the F-program add given in the description of F on page 2. [10 marks]
4. InthelectureswehaveintroducedWHILE-programsasnotionofcomputabil- ity (in other words, WHILE-programs were chosen as “effective procedures”). Would F-programs be a good alternative choice for “effective procedures”? Give reasons for your answer but no formal proof is required. [12 marks]
5. The concatenation of lists (where A::R denotes a list with first element A and rest list R like in Haskell) is defined as follows:
concat[[],M] = M
concat[A :: R, M] = A :: concat[R, M]
So, for instance concat [[1, 2, 3], [4, 5]] = [1, 2, 3, 4, 5].
(a) Write a single WHILE-program that implements concat and submit the source code in a file called concat.while. You may call as macro any WHILE-program published on Canvas. You can use ex- tended WHILE-syntax but your program must run correctly in hwhile.
[12 marks]
(b) Write a single F-program that implements concat and submit it in a
file called concat.F. [10 marks]
6. An F-interpreter intF written in WHILE is a program for which the follow-
ing holds:
for all F-programs p and input d∈ D.
Implement the F-interpreter from above in hwhile. Since hwhile does not have syntax sugar for special atom appf, you need to use something else instead in your code (also for the auxiliary atoms needed for the interpreter), so use @while to encode appf. Get inspiration by looking at the code for the WHILE self-interpreter. Test your interpreter but don’t submit the test data. Marking will also use testing so please make sure your program runs
5
[intF]WHILE[ p, d ] = [p]Fd
without syntax errror. If there are certain features that you cannot implement then leave those out but still submit a working program. Add comments where indicated to help the marker understand what you’re doing. This may be important if your code is not working correctly.
Submit your interpreter together with all macros as source code, i.e. WHILE programs. Make sure the main program, i.e. the interpreter, is called intF and submit it in a file intF.while.
Make sure you include programs called as macros that are not already pub- lished on our Canvas site. If your program is incomplete or does not run for syntactic reasons, it will automatically receive 0 marks! [26 marks]
6