[SOLVED] CS interpreter mips Limits of Computation

Limits of Computation
3 The WHILE-language Bernhard Reus
1
Last time
we discussed what problems are
discussed that our first objective is to show that at least one of those problems cannot be computed
defined what computable means in terms of effective procedures
but did not commit to any specific kind of effective procedures
2

WHILE-programs as Effective Procedures
THIS TIME
in this lecture we
define a particular version of effective procedure: WHILE-programs
and how we use WHILEs data type
program
a WHILE-program
3
WHILE
Identify: effective procedure = WHILE-program
The WHILE language has just the right mix of expressive powerandsimplicity. [N.Jones]
WHILE-programs can be interpreted on any sufficiently rich machine model
but, just like Alan Turing once did, we can define how to interpret WHILE-programs on paper (next time).
Later we will use an interpreter.
4

WHILE
WHILE-programs will be much more easily understandable, and easier to write as well, than Turing machine programs (or RAM / MIPS machine programs) which we will see much later in the term.
The idea is that this allows you to relate the concepts presented here to your perspective as programmers (and Computer Science students).
5
Data type: binary tree
Our WHILE-language is untyped.
Our WHILE-language has binary trees as only built-in datatype.
allowing us to easily encode other data, including programs (!), as data values
similar to LISP trees (or lists in other functional languages!)
6

BinaryTrees
_._ is constructor
atom nil at leaf
7
BinaryTrees formally
8

Other data types?
We can encode easily other types, for instance, booleans
natural numbers
lists
How?
9
Data in List Form
LISP S-expressions
JSON
XML
10

Lists
11
terminator
Example
terminator
12
we use to denote encodings
spine
spine

Booleans and Numbers
we use to denote encodings
13
Examples
1
3
2
terminator
14
spine

Trees as Lists
Any tree can be interpreted as a list (of something).Why?
There is always a spine & terminator!
= [1,1,1]
15
WHILE Syntax
16

3.2. WHILE-SYNTAX CHAPTER 3. WHILE BNF Grammar for WHILE
Expressions
Statement (lists)
Programs
(variable expression) (atom nil) (construct tree) (left subtree) (right subtree) (right subtree)
(block of commands) (empty block)
(single command list) (list of commands)
(else-case)
(assignment) (while loop) (if-then) (if-then-else)
3.2. WHILE-SYNTAX
hex pressioni ::= hvariablei
BN
esy
Th
n abo
duce
any b
hexpressioni
hblocki
hstatement-listi
helseblocki hcommandi
h programi
::= hvariablei
| nil
| cons hexpressioni hexpressioni | hd hex pressioni
| tl hexpressioni
| ( hex pressioni )
::= {hstatement-listi} | { }
::= hcommandi
| hcommandi;hstatement-listi
::= else hblocki
::= hvariablei := hexpressioni
| while hexpressioni hblocki
| if hexpressioni hblocki
| if hexpressioni hblocki helseblocki
::= hnamei read hvariablei hblocki
write hvariablei
Fig. 3.2: BNF grammar for WHILE
3.2.5 Layout Conventions and Brackets
17
In order to make WHILE programs readable, and avoid too many brackets, we use the following conventions throughout:
The command (body) of a program is indented with respect to read and write. The body of a while loop is often written below the while E { part and in-
dented accordingly.
Every assignment command is always written on a new line with the semicolon
atFthe e:nd aEnd hxas thpe samre iendenstatiosn ais tohe otnher csommands in the same block.
Examples in Section 3.4 use this convention.
ntax
for command blocks. Parenthesis are usually given in the concrete writeup of pro- grams in order to allow for a unique parsing of the linear of a an expression as string.
defi
nitio
ve
does
not
int
ro
CHAPTER 3. WHILE The expression language of WHILE uses prefix notation of operators and thus makes
reading of expressions unique without the use of any brackets For instance
identifier
cons hd hd X cons Y nil
(variable expression) (atom nil) (construct tree) (left subtree) (right subtree) (right subtree)
(block of commands) (empty block)
(single command list) (list of commands)
(else-case)
(assignment) (while loop) (if-then) (if-then-else)
with no parenthesis can be uniquely parsed as
| nil
cons (hd (hd X)) (cons Y nil)
| cons hexpressioni hexpressioni | hd hexpressioni
| tl hexpressioni | ( hex pressioni )
hblocki ::= {hstatement-listi} | { }
34
hstatement-listi ::= hcommandi
| hcommandi;hstatement-listi
helseblocki ::= else hblocki
18
hcommandi ::= hvariablei := hexpressioni | while hexpressioni hblocki
| if hexpressioni hblocki
| if hexpressioni hblocki helseblocki
rackets for expressions, just

BNF: Statement (Blocks)
19
BNF: Programs
identifier
this is where the magic happens main
one input one output
20

END
2008-21. Bernhard Reus, University of Sussex
Next time:
the semantics and extensions of WHILE
21