1
In 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.
hprogrami ::= in X out hexpressioni where f(X) = hexpressioni
hexpressioni ::= X
nil |
cons hexpressioni hexpressioni |
hd hexpressioni |
tl hexpressioni |
if hexpressioni then hexpressioni else hexpressioni |
f(hexpressioni)
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
are f(f(X)) and f(cons f(hd X) f(f(X))).
As an example, here is the WHILE-program add from our lectures written as Fprogram. As usual, the two inputs are wrapped up in a single list:
in X out f(X) where f(X) =
if hd X
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 (pred n + m) if n > 0
n + m = m if n = 0
2
In 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 pnq) and pred n denotes the predecessor of n (which in binary tree
encoding terms is tl pnq). Note that the input is a list of two numbers so hd X
and hd tl X correspond to n and m, 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]] B v = v
F[[nil]] B v = nil
F[[cons E F]] B v = h F[[E]] B v.F[[F]] B v i
F[[hd E]] B v =
d if F[[E]] B v = h d.e i
nil otherwise
F[[tl E]] B v =
e if F[[E]] B v = h d.e i
nil otherwise
Function application is defined as:
F[[f(E)]] B v =
F[[B]] B d if F[[E]] B v = d ∈ D
⊥ 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
Questions
- The (semantics of) language F uses the binary tree data type D we already
know from WHILE. Consider the following elements in D:
(a) h h nil.nili.h h nil.nili.h h nil.nili.h h nil.nili.nili i i i
(b) h h h nil.nili.h nil.nili i.h h nil.nili.nili i
(c) h h nil.nili.h h h nil.nili.nili.h h nil.nili.h h h nil.nili.nili.h nil.nili i i i i
(d) h h nil.nili.h h nil.nili.h h nil.nili.h h nil.h nil.nili i.h nil.nili i i i i
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] - 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 executes but describe the function it implements. [10 marks] - Let us encode F-programs as data by the following encoding that uses lists
(which we already know how to encode in D):
pinput X output E where f(X)= Bq = [ pEq, pBq ]
pXq = [ var ]
pnilq = [ quote, nil ]
pcons E Fq = [ cons, pEq, pFq ]
phd Eq = [ hd, pEq ]
ptl Eq = [ tl, pEq ]
pif E then F else Gq = [ if, pEq, pFq, pGq ]
pf(E)q = [ appf, pEq ]
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]
In the lectures we have introduced WHILE-programs as notion of computability (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]
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 extended 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]
An F-interpreter intF written in WHILE is a program for which the following holds:
[[intF]]WHILE[ ppq, d ] = [[p]]F
d
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
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 published 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