Informatics
Limits of Computation
Assignment 1 (Deadline 3.03.2022, 4pm)
You need to submit this coursework electronically at the correct E- submission point. You must submit a zipped directory that contains three files with the exact names as described below:
1. a pdf file questions.pdf containing the answers to Ques- tions 1–3 . Please make sure that all answers for Questions 1–3 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. a (ASCII, i.e. simple text) file called progasdata.txt that contains the answer to Question 4.
3. a runnable WHILE file STEPn.while that contains the answer to Question 5.
4. 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.
Spring 2022
WHILE01 – Extending WHILE with Binary Numbers
For the following questions, we enrich our core WHILE-language with a unary operator & that interprets lists as binary numbers and returns their integer value, and an addition operator adder for binary numbers (given as lists). The extended language shall be called WHILE01.
The syntax of our expressions is defined below adding two cases to the core WHILE-language expressions from Lecture 3, Slide 17.
hexpression i ::= . . . | &hexpressioni |
+hexpressionihexpressioni
/* WHILE-expressions */
/* binary to integer conversion */ /* binary number addition */
The semantics of the &E operation is as follows: first evaluate E to a list ` (recall that this is always possible). Then interpret any list ` = [a0, a1, . . . an] as the integer value of the binary number [(an)[(an 1) . . . [(a0) where [(nil) = 0 and [(d) = 1 if d 6= nil. Here are some examples
WHILE expression
&[h nil.nil i, nil, nil, h nil.nil i] &[h nil.nil i, nil]
&[h nil.nil i]
binary integer
1001 9 01 1 1 1 0 0 &[] 0
&[0, 4, 3, 2, 1]
&[nil, h nil.nil i, h h nil.nil i.nil i] &[[[]], h nil.nil i, [], [1, 2, 3]]
11110 30 110 6 1011 11
The semantics of the + E1 E2 operation is as follows: first evaluate E1 and E2 to lists`1 =[a0,a1,…,an]and`2 =[b0,b1,…bm],respectively(recallthatthis is always possible). Then return an encoding (as list) of the binary number that corresponds to the binary addition of `1 and `2. Here are some examples:
binary expr.
+ [h nil.nil i, nil, nil, h nil.nil i] [1, 0, 1] + [h nil.nil i, nil] [1]
+ [nil, [nil], h nil.nil i] [h nil.nil i, h nil.nil i] + [nil] [0,4,3,2,1]
+ [[1], [2]] []
binary number addition
1001+101 = 1110 01+1 = 10 110+11 = 1001 0+11110 = 11110 11+0 = 11
result list
[0, 1, 1, 1] [0, 1]
[1, 0, 0, 1] [0,1,1,1,1] [1, 1]
We also extend “programs-as-data” to include the above expressions. The corre- sponding rules for the encoding (see the encodings given in Lecture 6 on Slide 18)
look as follows
p& Eq = [&, pEq]
p+ E1 E2q = [+, pE1q, pE2q]
where & and + appearing on the right hand side are different new atoms, respec- tively. In order to be able to deal with this in hwhile (our WHILE interpreter) that does not recognise @& and @+, let us fix the encoding of & to be number 4, and + to be number 6. So in program-as-data representation of WHILE01-programs you must use 4 to represent the & construct, and 6 to represent the + construct. So for instance:
encodes for hwhile the WHILE01-expression:
& + (cons nil cons (cons nil nil) nil) (cons cons nil nil nil) and if you’d evaluate this expression you would get as result the number 3.
Finally, Figure 1 shows a a sample program in WHILE01.
sample read L { X:= hdL; Y:= hdtlL; Z:= +XY; Z:= &Z; while Z {
Z := tl Z;
Res := cons nil cons nil Res
Figure 1: WHILE01-program sample
Below you find FIVE questions. You must answer all of them. They cover the material of Lectures 1 to 7.
1. WHILE01 uses the same datatype of binary trees as WHILE does. Consider the following trees in D:
(a) hhhnil.nili.nili.hhnil.nili.hhhnil.nili.nili.hnil.niliiii (b) hhhnil.nili.nili.hhhhnil.nili.nili.hnil.nilii.hnil.niliii (c) hhnil.nili.hhnil.nili.hhnil.hnil.nilii.hnil.niliiii
(d) hhhnil.nili.hhnil.hnil.nilii.hnil.niliii.hhnil.nili.nilii
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?
Use our encoding of datatypes in D as explained in the lectures. Note that an empty list can always be considered a list of numbers and a list of lists of numbers. [20 marks]
2. Let prog be the extended WHILE-program in Figure 2. Explain which tree program prog in Figure 2 returns as output for any given input d 2 D. In other words, state what [prog]WHILE(d) is for any d 2 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. [18 marks]
3. This question is about problems and decidability.
(a) Is the following “problem” a problem in our sense? Explain your an- swer!
Given the chess position after 8 moves in the 5th game of the FIDE chess world championship match in December 2021 (what that position is exactly does not matter), can white al- ways win?
(b) Is the following “problem” a problem in our sense? Explain your an- swer!
Given any stock listed on the London Stock Exchange today, will its closing price on 14.02.2090 be higher than today’s opening price?
Code Help
prog read L {
Y:= hd tl L;
X:=
F:= false;
if A=hd B { F:= true };
B:= tl B };
if F { Z:= cons A Z };
X:= tl X }
Figure 2: WHILE-program prog (c) Consider the following problem:
Given any legal chess position (using the official chess rules) where white is to move next, can white always win (after ar- bitrarily many moves), independently of how black moves?
Explain briefly whether you think this problem is decidable or not and why.
[18 marks]
4. Translate the program sample in Figure 1 into program-as-data notation that can be fed to hwhile, so that you can use it to test the answer for the next question. Submit your answer as a text file named progasdata.txt. This file must only contain text (no Word documents here!) representing the program as WHILE01-data. Make sure you follow the specification of WHILE01-programs-as-data format as given further above. [18 marks]
5. Wewouldliketoextendtheself-interpreteru.whileforWHILE(discussed in Lecture 7 and available from our Canvas site) so that it can also interpret WHILE01-programs in abstract syntax. Due to the architecture of the self- interpreter you only need to change the implementation of the step macro
程序代写 CS代考 加微信: cstutorcs
STEPn.while (which will be released on our Canvas site). Note that you just have to add the required additional code for the additional con- structs. Submit the answer to this question, i.e. the updated macro, as file STEPn.while (make sure you have included your code and don’t submit just the file from canvas).
One must be able to successfully run the universal program u as interpreter for WHILE01 when using your submitted STEPn.while macro. This is how we will test your answer and you should test yours in this way before submitting. You won’t get marks if your macro is syntactically incorrect. Also make sure you test that your code does not lead to non-termination. This often happens when one does not clear the command stack properly.
In your STEPn.while program you may use macro calls to any program published on the Canvas site but if you do so, please don’t include those pro- grams in your submission. You must not call any other programs. Add some comments to the code where appropriate so you help the marker understand
what you are doing.
[26 marks]
Computer Science Tutoring