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 19-Nov-2007.

Hand in: email your solution (as a plain text file) to barak+cs351@cs.nuim.ie

Turn in:

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 help!

NUIM/CS351 Assignment 3

BASICK Interpreter

The objective of this assignment is to implement, from scratch, an interpreter for a simple but full-fledged and usable Turing-complete programming language.

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.

Definitions

BASICK program
a sorted list of numbered statements
numbered statement
a line number consed onto an (unnumbered) statement
variable
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
statement
a list whose first element is a keyword and whose remaining elements depend on the keyword. Valid keywords and their corresponding statement syntax are:
let
statement syntax: (let variable = variable-or-number), this assigns the given number to the given (BASICK) variable
read
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.
add
statement syntax: (add variable-or-number to variable), this adds the appropriate value to the given variable.
subtract
statement syntax: (subtract variable-or-number from variable), this subtracts the appropriate value from the given variable.
multiply
statement syntax: (multiply variable by variable-or-number), this multiplies variable by the given value.
divide
statement syntax: (divide variable by variable-or-number), this divides variable by the given value.
goto
statement syntax: (goto line-number), this transfers control to the numbered statement with the given line number.
if
statement syntax: (if condition goto line-number), this conditionally transfers control to the numbered statement with the given line number.
return
statement syntax: (return variable-or-number), this terminates the BASICK program, returning the given value.
rem
syntax: (rem whatever ...), this statement is a comment ("rem" stands for "remark") and does nothing.
line number
any non-negative integer
condition
the syntax for a condition is: (variable-or-number .gt. variable-or-number) or (variable-or-number .lt. variable-or-number) or (variable-or-number .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.

Assignment

You are to implement two functions.
  1. run, runs a BASICK program. Invoked as (run BASICK-program input-stream)
  2. 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.

Examples

Here are some sample programs and the results of running them. 
  (define basick-factorial
      '((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))

  (define basick-mean
     '((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

  (define basick-sqrt
    '((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

Hints

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 table-driven strategy.

Notes