handout #16

CSE341—Programming Languages

Programming Assignment #8 (Scheme)

due 11 pm Friday, 5/29/09

As I mentioned in lecture, every student is granted a fourth late day that can be used for assignments 7, 8, and 9. You still can’t use more than two late days for any given assignment.

In this assignment you will implement a significant subset of the BASIC programming language as described in the 1964 Dartmouth report available here:

http://www.bitsavers.org/pdf/dartmouth/BASIC_Oct64.pdf

Your solution will build on the parsing procedures of assignment 7 and you will be provided with a set of utilities called hw8-support.scm that has code for handling the top-level user interaction and a procedure called tokenize that will convert user input into lists of tokens. Your solution should be called hw8.scm and should include the following procedure calls:

(include "hw7.scm")

(include "hw8-support.scm")

A solution to hw7 will be emailed to all students once the final deadline has passed.

The primary task for this assignment is to write a procedure called run-program. It will be passed a list of BASIC instructions to execute. Each value in the list will have three parts: a line number, the original text of the line (something your code will ignore), and a list of tokens for the input line. For example, the following BASIC program:

10 LET X = 203.4 * 37.7

20 PRINT X

30 LET X = X/2

40 IF X>200 THEN 20

50 END

Would be represented in list form as follows:

((10 " LET X = 203.4 * 37.7" (LET X = 203.4 * 37.7))

(20 " PRINT X" (PRINT X))

(30 " LET X = X/2" (LET X = X / 2))

(40 " IF X>200 THEN 20" (IF X > 200 THEN 20))

(50 " END" (END)))

Variable names in BASIC are very limited. They can be one letter long or one letter followed by one digit. The hw8-support file includes a predicate variable? that can be used to test whether something is a legal variable name.

This writeup lists various error conditions that you must handle in your code. Unless otherwise specified, your error string must include the line number on which the error occurred, as in:

LINE 30: VARIABLE MUST BE FOLLOWED BY =

You are not required to handle every potential error, although you can include extra error cases if you want to. You will want to call the parse-test and parse-expression procedures of assignment 7, but do so, you should instead call the procedures try-parse-test and try-parse-expression that are provided in hw8-support. These versions take an extra parameter that specifies the line number so that if an error occurs, it will be reported with the line number, as in:

LINE 55: ILLEGAL EXPRESSION

Your run-program procedure should properly implement the following BASIC commands:

1. (5 points) REM. The REM command is for comments (short for REMarks). The general form is:

REM <text>

A REM command does nothing.

2. (5 points) END. The END command terminates a program. The general form is:

END

Your program should terminate execution when it encounters this command. The BASIC language description indicates that this must be the last line of a BASIC program. We will not enforce this rule (partly because we are not implementing the STOP command).

3. (15 points) LET. The LET command assigns a value to a variable. The general form is:

LET <variable> = <expression>

The expression will always have a numeric result. The expression might include references to other variables. The LET command can be used to define a new variable or to reassign a variable that was previously assigned a value. You should make sure that the variable is a legal variable name in BASIC. The hw8-support file includes a predicate called variable? that can be used for this purpose. You should call the try-parse-expression function to parse the expression.

4. (5 points) INPUT. The INPUT command reads a number from the user and stores it in a variable. The general form is:

INPUT <variable>

This command wasn’t part of the original BASIC specification, but it is obviously very useful. You should call Scheme’s read procedure to read the number (it takes no arguments, as in (read)). You should make sure that the input you get is either an integer or a real. If it is, you should assign the given variable that value. Otherwise you should call the error procedure with an appropriate message. You should also call error if the variable is not a legal BASIC variable name (as noted earlier, the support file has a predicate called variable? that can be used for this purpose).

5. (10 points) PRINT. The PRINT command prints a sequence of expressions and strings separated by commas. The general form is:

PRINT (<expression> | <string>) {"," (<expression> | <string>)}

Commas will be represented with the token comma, as in (PRINT “x =” comma 7.8). Each String should be displayed and each expression should be evaluated and displayed (the display procedure works for both strings and numbers). Values should be separated by a space and each PRINT command should produce a complete line of output (the newline procedure goes to a new line of output). You should not display a trailing space on the line. The expressions are guaranteed to be numeric, although they might refer to variables. You should make an appropriate call on error if a comma or an expression is missing. You should call try-parse-expression to parse the expressions.

6. (10 points) GOTO. The GOTO command transfers control to another part of the program. The general form is:

GOTO <line number>

A GOTO command transfers control to the given line number. The line number will be a simple integer (not an expression). If the line number does not exist, you should call the error procedure with an appropriate message.

7. (5 points) IF. The IF command is for conditionally transferring control. The general form is:

IF <test> THEN <line number>

The test will be of the form described in the homework 7 grammar. The line number will be a simple integer. If the test evaluates to #t, control should be transferred to the given line number. Otherwise it should proceed to the next statement, as usual. If the program attempts to transfer to a line number that does not exist, you should call the error procedure with an appropriate message. You should call try-parse-test to parse the test.

8. (10 points) GOSUB/RETURN. The GOSUB command transfers control to a subroutine (a section of code that is terminated with a RETURN command). The general form is:

GOSUB <line number>

The GOSUB command is similar to GOTO in that it transfers control to another part of the program. But in the case of GOSUB, a subsequent call on RETURN will return the program to the statement after the call on GOSUB. The basic form of the RETURN command is:

RETURN

BASIC supports only a single subroutine execution at any given time. Your program should call the error procedure with an appropriate message if the program attempts to execute two GOSUB commands in a row without a call on RETURN in between. Your program should also call the error procedure with an appropriate message if the program attempts to execute a RETURN command when there is no active subroutine execution. Your program should also call the error procedure with an appropriate message if the program reaches an END while a subroutine execution is active (i.e., without having encountered a RETURN statement) or if a call on GOSUB is the last line of a program.

9. (30 points) FOR/NEXT. The FOR command is used for looping. The general form is:

FOR <variable> = <expression> TO <expression>

The expressions represent the starting and ending values for the loop. The expressions have to be numerical, but they need not be integers. Each FOR command should be paired with a corresponding NEXT command using the same variable name:

NEXT <variable>

When the NEXT command is encountered, you examine the value obtained by incrementing the loop variable (adding 1 to it). If that value is less than or equal to the final value for the loop, then you set the variable to that value and go back to the top of the loop. If the value after incrementing would be larger than the final value, then you leave the variable unchanged and transfer control to the statement that comes after the NEXT command.

For example, consider the following loop:

100 FOR X = 0.5 TO 5

110 PRINT X

120 NEXT X

130 PRINT X

The loop produces the following output:

0.5

1.5

2.5

3.5

4.5

4.5

Notice that the loop stops when X becomes 4.5 because incrementing it again would cause it to be greater than the final value of 5. Also notice that X has the value 4.5 after the loop.

The BASIC standard says that if the starting value for a loop is greater than the ending value, then the body of the loop should be skipped and afterwards the variable should be one less than the starting value. For example:

10 FOR X = 5 to 3

20 PRINT X

30 NEXT X

40 PRINT X

The body of the loop is not execute (the PRINT in line 20) and after the loop the value of X is reported to be 4 (one less than the starting value).

Loops can be nested, as in:

100 FOR X = 1 TO 3

110 FOR Y = 1 TO X

120 PRINT X, Y, X + Y

130 NEXT Y

140 NEXT X

Loops are required to be properly nested. For example, in the code above you would not be allowed to switch the order of lines 130 and 140 because then we would encounter the NEXT command for the outer loop before encountering the NEXT command for the inner loop.

The BASIC specification describes a loop in terms of the FOR command that begins the loop, the NEXT command that ends the loop and the body of commands that appear in between. The nesting requirement says that if one FOR/NEXT loop is going to appear in the body of another, then the nested loop must appear in its entirety in the body of the outer loop (i.e., the FOR command, the body of the inner loop and the NEXT command).

There are some unusual cases that can arise if a programmer calls GOTO or GOSUB inside of a loop. In general, a programmer should not escape a loop with a GOTO command. A call on GOSUB can be okay, although there are some odd cases (for example, what if the GOSUB code includes a NEXT command for the original loop?). In general, we aren’t going to worry about many of these subtle errors.

You should call try-parse-expression to parse the two expressions. Your code must call the error procedure with an appropriate message for the following errors:

· FOR not followed by a legal variable name

· the variable name not followed by =

· the first expression not followed by TO

· extraneous tokens after the second expression

· improperly nested loops (including using the same variable in both an inner and outer loop)

· a next without a corresponding for

· reaching the END command without completing all loops (this will include catching the case where there is a for without a corresponding next)

10. (5 points) Program execution should proceed sequentially from the first line of the program until it encounters an END command. It should produce this message when the program finishes executing:

PROGRAM TERMINATED

If it executes all statements of the program without executing an END command, your program should call the error procedure with an appropriate message using the line number of the last line of the program.

The first token after the line number indicates the kind of command to execute (REM, END, LET, IF, etc.). If your program encounters an illegal token, it should call the error procedure with an appropriate message.

Other than the specific error handling described in this writeup, you may assume in writing your code that the program you are provided is a legal program.

It is helpful to be able to declare a small number of global variables, although you don’t want to overuse the technique. You are allowed to declare up to 7 global variables in writing your solution (Stuart’s has 5 globals).

The starter code provided in hw8-support.scm gives the following command options to the user (most of which come from the BASIC specification):

· LIST: show a listing of the current program

· NEW erases the current program

· OLD allows you to read in a previously saved program

· RENAME allows you to change the name of the current program file (only takes effect for future calls on SAVE or UNSAVE)

· RENUMBER renumbers the lines of the current program in increments of 10

· RUN: run the current program

· SAVE: save the current program in program.bas

· STOP: exits the BASIC interpreter

· UNSAVE: restore a program from program.bas

For the commands that involve specifying a file name (NEW, OLD, RENAME), you can either type the command and hit enter or you can type the command followed by the file name.

In addition to the commands, the user can enter lines of the program, which will all begin with a line number. They can be entered in any order. The user can also replace a line. To delete a line, the user should type the line number followed by enter.