I need help in this question, I am trying so hard for last few days but i am not able to complete it, please help me, i will be very much thankful. I really need help in this.

This is reverse.while file:

(* reverse.while

Reverse a list X (encoded in the usual way) as seen in Lecture 3.

(c) 2008-16 Bernhard Reus

*) reverse read X { Y:= nil; while X { Y:= cons hd X Y; X:= tl X } } write Y

This is U.while file:

(* u.while

The universal program for WHILE (i.e. the self-interpreter)

This program takes as input a list [p,d] where

p is a WHILE program encoded as list d is a value in WHILE-data

and interprets the program p with input d so the output is [|p|](d)

(c) 2008-16 Bernhard Reus Get the Limits book: https://www.springer.com/gb/book/9783319278872

*)

u read PD { P := hd PD; // P = [X,B,Y] D := hd tl PD; // D is input value) X := hd P; // X is input var name Y := hd tl tl P; // Y is output var name B := hd tl P; // B is program code block CSt := B; // Cst is code stack, initialised with the program DSt := nil; // DSt is data stack for intermediate results

bind := [X,D]; St := [bind]; // initialise store with binding for X state := [ CSt, DSt, St ]; // wrap state for STEP macro while CSt { state := state; // execute the STEP macro while there is code to execute CSt := hd state }; St := hd tl tl state; // get final store arg := [ Y, St ]; // wrap arguments for lookup Out := arg // lookup output vars value } write Out

This is stepn.while file:

(* STEPn.while

This is the STEP macro for the universal WHILE program (self-interpreter) ie. the STEPn.while program published on our Canvas site:

It takes as input a list [ CSt, DSt, St ] where

* we may assume that CSt only contains correctly encoded program statements and expressions (so no error handling needed) * CSt is the command stack (for program traversal) * DSt is the data stack (intermediate results) * St is the program store (memory) for variables Output is a new state [ CSt1, DSt1, St1] according to th interpretation of the topmost element of CSt.

(c) 2018-21 Bernhard Reus

This needs to be tested with the self interpreter u.while from Canvas and the macros update.while, lookup.while, and reverse.while also from Canvas

*)

STEPn read state { // retrieve individual arguments from list CSt := hd state; DSt:= hd tl state; St:= hd tl tl state; C:= hd CSt; // current command encoding on top of Command stack d:= hd C; // is nil if C is a do_marker, otherwise not if d { // top level command executed that is of shape [op,arg1,...] cur_op := d; // type of current command arg := hd tl C; arg2 := hd tl tl C; switch cur_op { case @quote: DSt:= cons arg DSt; CSt:= tl CSt case @var: V := [arg, St]; DSt := cons V DSt; CSt:= tl CSt case @hd: CSt:= cons arg cons @doHd (tl CSt) case @tl: CSt:= cons arg cons @doTl (tl CSt) case @cons: CSt := cons arg2 cons arg cons @doCons (tl CSt) case @:=: CSt := cons arg2 cons @doAsgn cons arg (tl CSt) case @while: CSt:= cons arg cons @doWhile CSt case @if: CSt:= cons arg cons @doIf CSt } // end switch } else { // do_marker to be executed arg:= hd DSt; switch C { case @doHd: DSt:= cons (hd arg) (tl DSt); CSt:= tl CSt case @doTl: DSt:= cons (tl arg) (tl DSt); CSt:= tl CSt case @doCons: arg2:= hd tl DSt; DSt := cons (cons arg arg2) (tl tl DSt); CSt:= tl CSt case @doAsgn: X := hd tl CSt; St:= [X,arg,St]; DSt:= tl DSt; CSt:= tl tl CSt case @doWhile: if arg { wc:= hd tl CSt; CSt:= tl CSt; B:= hd tl tl wc; // block to be added to current commands // add the commands of B in right order onto tl Stack; B := B; // reverse to get the right order while B { CSt:= cons (hd B) CSt; B:= tl B } } else { CSt := tl tl CSt } ; DSt := tl DSt case @doIf: ifc:= hd tl CSt; if arg { B:= hd tl tl ifc // then block to be added to current commands } else { B:= hd tl tl tl ifc // else block to be added to current commands }; CSt:= tl tl CSt; // add the commands of B in right order onto tl Stack; B := B; // reverse to get the right order while B { CSt := cons (hd B) CSt; B := tl B }; DSt := tl DSt } // end switch }; // end else do_smth case newState := [ CSt, DSt, St ] } write newState

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 WHILE++ programs in abstract syntax. Due to the architecture of the self- interpreter program you only need to change the implementation of the step macro STEPn.while (which will be released on our Canvas site just after the last seminar at the end of Week 4). Note that you just have to add the required additional code for the iterator. Submit the answer to this question in a separate text file STEPL.while. One must be able to successfully run the universal program u as interpreter for WHILE++ changing its STEPn.while macro call to a STEPL.while macro call. 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 STEPL 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 STEPL.while program you may use macro calls to any program published on the Canvas site but if you do so, please don't include them in your submission. You must not call any self-defined programs. Add some comments to the code you add to help the marker understand what you are doing. [22 marks] 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 WHILE++ programs in abstract syntax. Due to the architecture of the self- interpreter program you only need to change the implementation of the step macro STEPn.while (which will be released on our Canvas site just after the last seminar at the end of Week 4). Note that you just have to add the required additional code for the iterator. Submit the answer to this question in a separate text file STEPL.while. One must be able to successfully run the universal program u as interpreter for WHILE++ changing its STEPn.while macro call to a STEPL.while macro call. 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 STEPL 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 STEPL.while program you may use macro calls to any program published on the Canvas site but if you do so, please don't include them in your submission. You must not call any self-defined programs. Add some comments to the code you add to help the marker understand what you are doing. [22 marks]