Due: The intermediate progress report is due at 24:00 on Tue
13-Nov-2007. The final hand in is due at 09:00 on Mon
Hand in: email your solution (as a plain text file) to
- The intermediate progress report this should include your
testing jig and test cases that allow you to automatically test
your interpreter, and a rough interpreter showing the essential
structure and core routines.
- The final hand in should include a fully working interpreter
including all required functionality, along with your test suite
and testing jig. It should make me proud.
Teamwork is encouraged. Please work in teams of up to three (3)
people. The teams for this assignment must be disjoint from the
teams of previous assignments. (This means that no two people who
were previously on the same team can be on the same team.) Just
turn in one (1) solution set, with the entire team listed at the
top, sorted by how much each person contributed. (The order will
not affect grades; it will be used only for my own consistency
checking of scores at the end of the course.)
Hints: Start early! Don't be afraid to ask for
NUIM/CS351 Assignment 3
The objective of this assignment is to implement, from scratch, an
interpreter for a simple but full-fledged and usable Turing-complete
Here this will be a simplified language which combines some of the
least pleasant features of Dartmouth BASIC, COBOL and
FORTRAN IV. To avoid the need for parsing, we define an
s-expression syntax for BASICK programs.
- BASICK program
- a sorted list of numbered statements
- numbered statement
- a line number consed onto an
- a BASICK variable is any Scheme symbol, however by convention we
use one-letter symbols, or symbols consisting of one letter
followed by one digit. BASICK variables can only hold numbers.
Scalar numbers. Numbers are the only datatype supported by
BASICK. There are no arrays or structures, only numbers.
- variable or number
- either a variable or a number
- a list whose first element is a keyword and whose
remaining elements depend on the keyword. Valid keywords and
their corresponding statement syntax are:
- statement syntax:
= variable-or-number), this assigns the given
number to the given (BASICK) variable
- statement syntax: (read variable), this
reads a number for the input stream and assigns it to
the given variable. If the stream is empty variable
is given a value of -1.
- statement syntax: (add variable-or-number
to variable), this adds the appropriate value to
the given variable.
- statement syntax: (subtract variable-or-number
from variable), this subtracts the appropriate
value from the given variable.
- statement syntax: (multiply variable
by variable-or-number), this
multiplies variable by the given value.
- statement syntax: (divide variable
by variable-or-number), this
divides variable by the given value.
- statement syntax: (goto line-number), this
transfers control to the numbered statement with the
given line number.
- statement syntax: (if condition
goto line-number), this conditionally transfers
control to the numbered statement with the given line
syntax: (return variable-or-number), this
terminates the BASICK program, returning the given value.
- syntax: (rem whatever ...), this statement
is a comment ("rem" stands for "remark") and does nothing.
- line number
- any non-negative integer
- the syntax for a condition is: (variable-or-number
.gt. variable-or-number) or
.eq. variable-or-number), which have the truth value
one might expect. Like in FORTRAN, .gt. stands for greater than,
.eq. stands for equals, and .lt. stands for less than.
- input stream
- a list of numbers used as input to the program.
You are to implement two functions.
- run, runs a BASICK program. Invoked
as (run BASICK-program input-stream)
- ren, invoked as (ren BASICK-program
low incr), this renumbers the statement
numbers in the given BASICK program to start at low and
be numbered sequentially with an increment of incr.
This involves not only renumbering the statements but also
making the corresponding changes to the targets of
any goto or if statements.
Here are some sample programs and the results of running them.
'((10 read n)
(12 rem got a number now find its factorial)
(20 let i = 1)
(25 let a = 1)
(100 if (i .gt. n) goto 200)
(110 multiply a by i)
(120 add 1 to i)
(130 goto 100)
(200 return a)))
(run basick-factorial '(3)) ; evaluates to 6
(ren basick-factorial 1000 5)
;; evaluates to
((1000 read n)
(1005 rem got a number now find its factorial)
(1010 let i = 1)
(1015 let a = 1)
(1020 if (i .gt. n) goto 1040)
(1025 multiply a by i)
(1030 add 1 to i)
(1035 goto 1020)
(1040 return a))
'((10 let n = 0)
(12 rem n counts the numbers read)
(15 let t = 0)
(17 rem t hold the sum of those numbers)
(20 read x)
(22 if (x .eq. -1) goto 70)
(27 add x to t)
(28 add 1 to n)
(40 goto 20)
(70 rem time to calculate the average or mean)
(71 let r = t)
(73 divide r by n)
(77 return r)))
(run basick-mean '(20 20 20 20 30)) ; evaluates to 22
'((10 rem calculate a square root)
(12 rem newtons method would be faster but i feel lazy)
(18 rem x is the thing whose sqrt we want)
(20 read x)
(21 rem e is the error tolerance)
(23 let e = 0.0001)
(24 rem do some pointless input validation)
(25 if (x .gt. 0) goto 28)
(26 return -9999)
(28 rem z holds an estimate of the sqrt of x)
(30 let z = 1)
(31 rem calc s = abs (z * z - x) terminate if below epsilon)
(32 let s = z)
(35 multiply s by z)
(40 subtract x from s)
(42 if (s .gt. 0) goto 46)
(44 multiply s by -1)
(46 if (s .gt. e) goto 50)
(48 return z)
(50 rem not accurate enough)
(51 rem calc z1 = x / z and then z2 = average of z and z1)
(52 rem z2 will be the new estimate)
(54 let z1 = x)
(55 divide z1 by z)
(58 let z2 = z1)
(62 add z to z2)
(65 divide z2 by 2)
(70 let z = z2)
(80 goto 31)))
(run basick-sqrt '(4.0)) ; evaluates to approx 2.0000001
You will want to define some auxiliary functions. It is important to
think clearly about how you are representing the BASICK "store", i.e.,
the mapping from variables to their values, and what state the
interpreter needs to keep track of. It is also a good idea to break
the interpreter up into small functions, and perhaps consider some
- In the absence of explicit control constructs, execution in a BASICK
program proceeds sequentially by line number.
- It "is an error" for a BASICK program to fall off the end, i.e., you
do not need to worry about that case.
- It "is an error" for a BASICK variable to be used unless it is
first assigned an initial value by a let statement.
- There is a reasonably subtle problem with the BASICK SQRT program.
For extra credit, identify and explain the bug.
- All material handed in should be properly formatted and indented.
Lines should be broken at appropriate points. (Anything not
conforming to this policy will be returned for re-submission.)
- Updates to this page are versioned, currently $Revision: 1.11 $