University of Sussex Informatics
Spring 2023
Limits of Computation
Assignment 1 (Deadline 2.03.2023, 4pm)
You need to submit this coursework electronically at the correct E- submission point. You must submit a zipped directory that contains two files with the exact names as described below:
1. a pdf file questions.pdf containing the answers to Ques- tions 1–4 . Please make sure that all answers for Questions 1–4 are in this single document. In case you use Word, please ensure that you convert your file into a pdf document before submis- sion1 .
2. arunnableWHILEfileSTEPn.whilethatcontainstheanswers to Question 5 and is an extension of the file STEPn.while on Canvas.
3. Any other files in your directory will be ignored, so include no other programs or files. For marking your assignment it is essen- tial that you follow the above rules.
Please use a standard zip program to zip the directory. If you work on a Unix machine or a Mac use the (normally) pre-installed zip program. If you use a Windows machine, use WinZip or 7-Zip. Please do not use other compression programs or formats as this might give you 0 marks as the markers may be unable to unzip.
Please do not write your name anywhere, but it is advisable to include your candidate number as comment in each submitted file.
Please make sure you check after submission that you actually have submitted the correct zipped directory of 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.
1In Word, this works usually by using the printing menu and then saving as pdf instead of sending to a printer.
程序代写 CS代考 加QQ: 749389476
Below you find FIVE questions. You must answer all of them. They cover the material of Lectures 1 to 7.
1. Alistoflistsofnumbersisalistsuchthatallitselementsarelistsofnumbers. Consider the following examples:
• [[3,5],[],[1,1,1]] is a list of list of numbers;
• [[[3,5]]],[],[1]] is not a list of list of numbers due to the first
• [2,[1]] is not a list of list of numbers due to the first element, but note that the tree that encodes this list also encodes [[0,0],[1]] which is a list of list of numbers.
Note that an empty list can always be considered a list of numbers and a list of lists of numbers.
Answer for EACH of the given trees (a)–(d) BOTH of the following ques- tions:
i Does it encode a list of numbers? If it does which is the corresponding list of numbers?
ii Does it encode a list of lists of numbers? If it does which is the corre- sponding list of lists of numbers?
UseourencodingofdatatypesinDasexplainedinthelectures. [18marks]
(a) ⟨⟨nil.nil⟩.⟨⟨nil.⟨nil.nil⟩⟩.⟨⟨nil.⟨nil.nil⟩⟩.nil⟩⟩⟩
(b) ⟨nil.⟨⟨nil.nil⟩.⟨⟨⟨nil.⟨nil.nil⟩⟩.nil⟩.nil⟩⟩⟩
(c) ⟨⟨⟨nil.nil⟩.⟨⟨nil.⟨nil.nil⟩⟩.nil⟩⟩.⟨⟨nil.⟨nil.⟨nil.nil⟩⟩⟩.nil⟩⟩ (d) ⟨⟨nil.nil⟩.⟨⟨nil.nil⟩.⟨⟨⟨⟨nil.nil⟩.nil⟩.nil⟩.nil⟩⟩⟩
2. Let stores σ1 and σ2 be defined as follows:
σ1 = {X : ⟨nil.⟨nil.nil⟩⟩,Y : ⟨⟨nil.nil⟩.nil⟩}
σ2 = {X : nil,Y : [2,1,1]}
Provide a single command C ∈ ⟨command ⟩ in core WHILE-syntax (accord-
ing to the BNF-grammar of Lecture 4) such that the following holds:
C ⊢ σ1 → σ2
You must not define a statement-list, C must be one single command. Please
make sure you use correct core WHILE-syntax. [14 marks] 2
程序代写 CS代考 加微信: cstutorcs
prog read L {
X := hd L;
R := tl L;
while R {
if X = hd R
{ R:=nil;Flag:=true}
else{ R:=tlR } };
if Flag {}
else { New := cons X New };
Flag := false;
Figure 1: WHILE-program prog
3. Let prog be the WHILE-program given in Fig. 1.
(a) State whether the syntax of this program is core or extended WHILE-
syntax. [2 marks]
(b) Explain prog’s semantics, i.e. explain which tree program prog in Figure 1 returns as output for any given input d ∈ D. In other words, state what [prog]WHILE(d) is for any d ∈ D. Do not describe the code in the program. Do not narrate how the interpreter executes the program and do not repeat a generic definition of the semantic function. Rather provide the concrete definition of function [prog]WHILE. [20 marks]
4. This question is about problems and decidability.
(a) Is the following “problem” a problem in our sense? Explain your an- swer!
How can I improve my marks in Limits of Computation?
(b) Is the following “problem” a problem in our sense? Explain your an-
According to the Met Office’s data, will the temperature at midday in Brighton (Preston Manor) in 7 days’ time be higher than 12 degrees Celsius?
(c) Consider the following problem:
Given an arbitrary large finite, non-empty, set M of arbitrarily large natural numbers, is there a non-empty subset N ⊂ M such that the sum of all the numbers in N is equal to the sum of all the numbers in M \ N?
Is this problem decidable or not? Explain your answer.
[16 marks]
5. WenowextendourWHILE-languagewithfurtherfeaturesregardingexpres- sions. We introduce anonymous function application on trees and a map function for lists of trees. Those concepts are well known from functional programming languages. The language extending WHILE with those two expressions shall be called WHILEFun.
The syntax of the two new expressions is given in Fig. 2 as extension of the BNF grammar for expressions from Lecture 3.
⟨expression ⟩ ::= . . . | λ⟨variable⟩.⟨expression⟩ (⟨expression⟩) |
map λ⟨variable⟩.⟨expression⟩ (⟨expression⟩) Figure 2: WHILEFun extensions of WHILE
The meaning of the lambda application λX.E1 (E2) is as follows: first eval- uate E2 to a value d ∈ D. The result of the lambda application expression then is obtained by evaluating E1 with the value for variable X set to be d.
The meaning of the map function application map λX.E1 (E2) is as follows: first evaluate E2 to a value l = [d1,…,dn] where di ∈ D for all 1 ≤ i ≤ n. Wehavel = []forn = 0. Notethatitisalwayspossibletoviewl like that, since every tree can be interpreted as encoding of a list. The result of the map function application is then [e1, . . . , en] where each ei (for 1 ≤ i ≤ n) is obtained by evaluating E1 with the value for variable X set to be di, respectively. We denote the semantics of an expression E ∈ ⟨expression⟩ as function E[E] : Store → D.
Code Help, Add WeChat: cstutorcs
Below you can find some examples for the specific store σ1 = {Y : [0, 1, 2]}.
E[λX.hd X (Y)]σ1 = 0
E [λY.tl Y (Y)]σ1 = [1, 2]
E[λX.cons nil X (cons nil nil)]σ1 = 2
E[λX.cons X X (nil)]σ1 = ⟨nil.nil⟩
E[λX.consYX(Y)]σ1 =⟨[0,1,2].[0,1,2]⟩
E [map λX.cons nil X (cons nil cons (cons nil nil) nil)]σ1 = [1, 2] E[mapλX.hdX (Y)]σ1 =[0,0,0]
E[mapλY.tlY (Y)]σ1 =[0,0,1]
E[mapλX.tlY (Y)]σ1 =[[1,2],[1,2],[1,2]]
E[map λY.hd Y ([])]σ1 = []
We now extend “programs-as-data” for language WHILEFun to include the new expressions from above. The equations defining the encodings are as follows:
λ X.E1 (E2) = [4, varnumX, E1, E2] map λ X.E1 (E2) = [8, varnumX, E1, E2]
where 4 and 8 are guaranteed not to clash with the encodings of any atoms already in use for other WHILE-syntax by hwhile (see the encodings given in Lecture 6).
We would like to extend the self-interpreter u.while for WHILE (discussed in Lecture 7 and available from our Canvas site) so that it can also interpret WHILEFun programs in abstract syntax.
Due to the architecture of the self-interpreter you only need to extend the step macro STEPn. You will need a few auxiliary atoms: please use the numbers 14, 24, 34, and 44 (more should not be needed in any case) since they are guaranteed not to clash with the encodings of already used atoms.
(a) Extend the STEPn macro such that it can interpret also the lambda application expressions (as specified above).
[11 marks]
(b) Extend the STEPn macro such that it can interpret also the map appli- cation expression (as specified above). [19 marks]
You may use any extension feature that hwhile supports, and you may call as macro any program published on our Canvas site on page WHILE (Programs). No other macros may be used or defined for this question.
Test your program using hwhile before you submit. Supply comments for the code you add to make it easier to spot bugs. Submit the answer to both, 5(a) and 5(b), in a single file called STEPn.while that extends the one provided on Canvas (for the original WHILE-language). Use the name STEPn.while for the file and STEPn for the macro so that it runs in hwhile. IMPORTANT: Double check that you don’t just submit the original STEPn.while for WHILE without extension for WHILEFun, as this amounts to not having answered the question.
Don’t submit any of the auxiliary programs you call. You are not allowed to use any own macros anyway. Also, don’t submit a program that does not run as it will receive 0 marks. Ensure your program is syntactically correct so it runs.