Project 2

CSC 4101 – Programming Languages

 

Due April 6th, 2006

 

Implement an interpreter for a subset of the FORTH programming language which is defined below.

Basics:

FORTH relies heavily on explicit use of the stack data structure and reverse Polish notation called postfix notation because the operator is placed after its operands, as opposed to the more common infix notation where the operator is placed between its operands. The rationale for postfix notation is that it is closer to the machine language the computer will eventually use, and should therefore be faster to execute. For example, one could get the result of the mathematical expression (25 * 10 + 50) this way:

--> 25 10 * 50 + .
300 ok

This command line first puts the numbers 25 and 10 on the implied stack; the word * multiplies the two numbers on the top of the stack and replaces them with their product; then the number 50 is placed on the stack, and the word + adds it to the previous product; finally, the . command prints the result to the user's terminal.

Another Example: To calculate ((12+13)*9 + (7*8))/3 we would type:

--> 12 13 + 9 * 7 8 * + 3 / .

93 ok

Stack Operations:

Since all calculations depend heavily on the stack, there are a whole load of Forth commands for moving numbers around on the stack.

·       DUP will copy the number on top of the stack and leave that copy on the stack.

·       DROP will take the number off the top of the stack and throw it away.

·       SWAP will swap the two numbers on the top of the stack.

Function Definitions:

Even the language's structural features are stack-based. For example:

--> : Square DUP * ;

The colon at the start marks the start of a function definition. 'Square' is the name we have chosen to give the function. The semicolon marks the end of the definition. The rest is just the sequence of actions that should be carried out by the function. We can then use the word as if it was a standard FORTH word:

--> 4 Square .

This will display the result 16.

--> : FLOOR5 ( n -- n' ) DUP 6 < IF DROP 5 ELSE 1 - THEN ;

This is a code which defines a new function called FLOOR5 using the following commands: DUP simply duplicates the number on the stack; < compares the two numbers on the stack and replaces them with a true-or-false value; IF takes a true-or-false value and chooses to execute commands immediately after it or to skip to the ELSE; DROP discards the value on the stack; and THEN ends the conditional. The text in parentheses is a comment, advising that this word expects a number on the stack and will return a possibly changed number. The net result is a function that performs similarly to this function written in the Python programming language:

def floor5(v):
  if v < 6:
    return 5
  else:
    return v - 1

and similarly to this function written in the C programming language:

int floor5(int v) { return v < 6 ? 5 : v - 1; }

 

Conditions:

FORTH has all the usual IF/THEN/ELSE structures that you get in any programming language, but they have an odd 'flavour'. For example, the syntax of IF is:

<condition> IF

<action-if-true>
ELSE
<action-if-false>
THEN

Note that the condition comes before the IF, rather than after it as in most other languages. Also, THEN marks the end of the if statement, rather than the action to be carried out if the condition is true. An example of an if statement is as follows:

 

 

0 = IF

." Top of stack is zero"

ELSE
." Top of stack is not zero"

THEN

Here, '0 =' compares the top of the stack with zero. If the result of this is true, the message 'Top of stack is zero' is displayed using the function ." otherwise the message 'Top of stack is not zero' is displayed.

Interpreter

At the screen prompt, the user interacts directly with the FORTH system, typing sequences of words which are then read and executed by the FORTH system. This is the central value of the FORTH system: FORTH is a very simple way to translate text into computer behavior.

The interpreter uses spaces (some systems accept other whitespace characters, also) to separate "words." When it finds a word, it tries to look the word up in the dictionary and execute the word's code. If that fails, it then tries to convert it into a number and push it onto the stack. If that fails, then it prints the word followed by an error message ( e.g. "not in dictionary" ), and awaits further user input.

 

Here is an example of the interpreter at work: 

 
--> 2 3 +
ok
--> .
5 ok
 
--> 2 3 4 + * .
14 ok
 
--> 1 if 2 else 3 then .
2 ok
 
--> : square dup * ;
(square) ok
--> 4 square .
16 ok
 

 

 

 

 

More resources on FORTH programming language:

 

·       http://mysite.verizon.net/murphywong/inching.htm

·       http://www.softsynth.com/pforth/pf_tut.htm

 

 

Some Remarks:

·       Whenever a new word is defined, your interpreter prints a list of the defined words.

·       Your interpreter does not require any special keyword for a recursive word. (This kind of interpreter is easier to write in Scheme.)

Teamwork: You are strongly encouraged to do this assignment with a team of two. When you submit your assignment, indicate the composition of your team (names and email addresses) in your README file.

If you cannot find a partner and would like one, send an email to kosar@lsu.edu and I will try to find one for you. Teams of more than two members are not permitted. You are free to do the assignment alone if you prefer so.

Testing and Submitting Your Program:

Before submitting your code:

1)    Create a folder with your last name.

2)    Copy all of the source code, and test files into this folder

3)    Create a README file that:

To submit your program, make sure that everything that you want to submit is located in the directory with your last name. Zip (or tar) that directory and send it as a single file to the TA (gschof1@lsu.edu) and CC to the Professor (kosar@lsu.edu). As the subject line, put “Project 1 by your name (& your partner’s name)”.