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:

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

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 (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`, this assigns the given number to the given (BASICK) variable*variable*=*variable-or-number*) - read
- statement syntax:
`(read`, this reads a number for the*variable*)*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`, this adds the appropriate value to the given*variable-or-number*to*variable*)*variable*. - subtract
- statement syntax:
`(subtract`, this subtracts the appropriate value from the given*variable-or-number*from*variable*)*variable*. - multiply
- statement syntax:
`(multiply`, this multiplies*variable*by*variable-or-number*)*variable*by the given value. - divide
- statement syntax:
`(divide`, this divides*variable*by*variable-or-number*)*variable*by the given value. - goto
- statement syntax:
`(goto`, this transfers control to the*line-number*)*numbered statement*with the given line number. - if
- statement syntax:
`(if`, this conditionally transfers control to the*condition*goto*line-number*)*numbered statement*with the given line number. - return
- statement
syntax:
`(return`, this terminates the BASICK program, returning the given value.*variable-or-number*) - rem
- syntax:
`(rem`, this statement is a comment ("rem" stands for "remark") and does nothing.*whatever ...*)

- line number
- any non-negative integer
- condition
- the syntax for a condition is:
`(`or*variable-or-number*.gt.*variable-or-number*)`(`or*variable-or-number*.lt.*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.*variable-or-number*.eq.*variable-or-number*) - input stream
- a list of numbers used as input to the program.

`run`, runs a BASICK program. Invoked as`(run`*BASICK-program**input-stream*)`ren`, invoked as`(ren`, this renumbers the statement numbers in the given BASICK program to start at*BASICK-program**low**incr*)*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.

(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

- 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 $