Assignment 3

You can start with:

cargo new rforth

The goal for this assignment is simple:² implement a forth interpreter.

Forth is a low-level stack-oriented PL. The beauty of forth its simplicity. For a quick tutorial on forth, I recommend this very nice blog post.

Remark. I'm going to leave a lot of getting familiar with forth to you. If you need some assistance with understanding forth, please reach out on Piazza or by email.

Building a forth interpreter in Rust is made quite a bit easier by the high-level abstractions Rust provides. For example, we can create a very clear abstract representation of a machine configuration (to be updated when evaluating a program).

type Program = Vec<Command>;
type Dict = HashMap <String, Program>;
type Stack = Vec<i32>;

enum State {
    Compiled,
    Interpreted,
}

struct Config {
    dict: Dict,
    stack: Stack,
    state: State,
    compiled: Program,
    compiled_word: Option<String>,
}

#[derive(Clone)]
enum Command {
    Push(i32),
    Drop,
    Swap,
    Print,
    PrintStack,
    Add,
    Sub,
    Mul,
    Div,
    Mod,
}

impl Config {
    fn new() -> Config {
        Config {
            state: State::Interpreted,
            compiled: Vec::new(),
            compiled_word: None,
            stack: Vec::new(),
            dict: HashMap::from([
                (String::from("drop"), vec![Command::Drop]),
                (String::from("swap"), vec![Command::Swap]),
                (String::from("."), vec![Command::Print]),
                (String::from(".s"), vec![Command::PrintStack]),
                (String::from("+"), vec![Command::Add]),
                (String::from("-"), vec![Command::Sub]),
                (String::from("*"), vec![Command::Mul]),
                (String::from("/"), vec![Command::Div]),
                (String::from("mod"), vec![Command::Mod]),
            ])
        }
    }
}

At the core of a forth interpreter is a function the evaluates the program associated with a word, updating the machine configuration as necessary. The interpreter keeps track of a dictionary of words that store programs in a basic command langauge (in this case, with a grand total of 11 words). It's possible to define new words and add them to this dictionary (more on that later). For now, we're focused on implementing the part of the interpreter which runs programs that manipulate elements on the stack.

We can define the semantics of the stack-manipulation part of this language according to the following small-step rules. In these rules \(S\) is the stack and \(P\) is a program (associated with a word).

The print command has the side affect of printing \(n\), the element dropped from the stack, and the stack-print command has the side effect of printing the entire stack.

Stuck configurations account are error states.

For this part, you should implement a method for machine configurations called eval_word which, given a word of type String, looks it up in the dictionary and evaluates its associated program according to the above semantics, updating the stack as necessary.

In the main function, you should implement a REPL that allows you to type in lines of multiple words that will be evaluated when you press enter. Here is an example interaction

NathanM@crc-dot1x-nat-10-239-74-67 rforth % cargo run
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/rforth`
Type `bye' to exit
>> 1 2 . .
2
1
>> 1 2 . . .
2
1
stack underflow
>> 1 2 + 10 * .
30
>> bye

Alternatively, you can use ANSI escape codes to have an interaction closer to what is done by gforth and the easy forth tutorial, in which output is given on the same line as user input.

NathanM@crc-dot1x-nat-10-239-74-67 rforth % cargo run
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/rforth`
Type `bye' to exit
1 2 . . 2 1 ok
1 2 . . . 2 1 stack underflow
1 2 + 10 * .  30 ok
.s <0> ok
1 2 3 4 . 4 ok
.s <3> 1 2 3 ok
bye

This REPL should:

• Read user input at stdin, and separate that input into words by whitespace.
• Evaluate each word using eval_word until the end of the line, or until the first word causes an error (e.g. a stack underflow or an undefined word). In particular, words after a failed evaluation in a line should not be evaluated.

To get full credit for this assignment, you're only required to implement a stack calculator according to the semantics previously given. That said, forth is no fun if you can't define you're own words. Take a look at the gforth manual on Colon Definitions and implement these in your interpreter.

In rough terms, the word : should put the interpreter into the Compiled state, in which words are looked up in the dictionary and their associated programs are added to a concatenated into a compiled program which will be assigned a word (the first words after the :). The word ; then puts the interpreter back into the Interpreted state and writes the new word to the dictionary.

Colon definitions are nice, but they still leave a lot to be desired. We can't yet do general computation. Take a look at the gforth manual on Conditional Execution and implement this in your interpreter.