2
\$\begingroup\$

I made a small stack-oriented language in Rust. It tries to run anything it is given. To elaborate: Division by zero gives zero. If there is nothing on the stack and a request is made that involves popping off the stack, instead of just throwing an error, it acts as if 0.0 is always available on the stack. Currently it just supports a few small basic arithmetical operations, swapping the stack, duplicating the stack, printing and a jump command. It is a smaller version of the simpleStack language. The tests are currently more like sanity checks. Here is the code:

src/lib.rs

mod words;

/// Given a list of commands, execute the commands.
///
/// # Arguments
///
/// * `tokens` - A slice of tokens to be executed.
/// * `stack` - The stack to keep the current state of the program.
fn execute_program(tokens: &[&str], 
                   stack: &mut Vec<f64>,
                   output: &mut Vec<f64>) -> Vec<f64> {
    // Analogous to the role of a "register" for a Turing machine.
    let mut reg: usize = 0;
    loop {
        let tok = tokens.get(reg);
        match tok {
            Some(&"+")     => words::add(stack),
            Some(&"-")     => words::sub(stack),
            Some(&"*")     => words::mul(stack),
            Some(&"/")     => words::div(stack),
            Some(&"dup")   => words::dup(stack),
            Some(&"swp")   => words::swp(stack),
            Some(&"jnz")   => words::jnz(stack, &mut reg),
            Some(&"print") => words::print_float(stack, output),
            Some(_)        => words::parse_number(tok.unwrap(), stack),
            None           => break
        }
        reg += 1;
    }
    output.to_vec()
}

/// Evaluates a string of code.
/// 
/// # Arguments
///
/// * `code` - The string of code to be executed.
///
/// *Note* The value returned is the "output" of the code. Output is not done
/// through stdout for easier debugging.
pub fn eval(code: String) -> Vec<f64> {
    let tokens: Vec<&str> = code.split(' ').collect();
    let mut stack: Vec<f64> = Vec::new();
    let mut output: Vec<f64> = Vec::new();
    execute_program(tokens.as_slice(), &mut stack, &mut output)
}

src/words.rs

//! The `word` module contains the verbs and nouns that create a program. Verbs
//! are functions (regardless of airity) and nouns are data.

/// Extracts two values off the top of a stack.
///
/// # Arguments
///
/// * `$stack` - stack to be mutated.
macro_rules! get_ops {
    ($stack:expr) => {
        ($stack.pop().unwrap_or(0.0),
        $stack.pop().unwrap_or(0.0))
    }
}

/// Parses a numerical value to a float.
///
/// # Arguments
///
/// `token` - The value to be converted to a float.
/// `stack` - The stack to push the token onto.
///
/// *Note* - If `parse_number` is **not** given a number, it will still return
/// `0.0`.
#[inline(always)]
pub fn parse_number(token: &str, stack: &mut Vec<f64>) {
    let number = token.parse::<f64>().unwrap_or(0.0);
    stack.push(number);
}

/// Pops the top two elements off the stack and adds them.
///
/// # Arguments
///
/// * `stack` - The stack to pop from and push onto.
///
/// *Note* - If no number is available to pop from the stack, a default value 
/// of `0.0` is used.
#[inline(always)]
pub fn add(stack: &mut Vec<f64>) {
    let (a, b) = get_ops!(stack);
    stack.push(a + b);
}

/// Pops the top two elements off the stack and subtracts them.
///
/// # Arguments
///
/// * `stack` - The stack to pop from and push onto.
///
/// *Note* - If no number is available to pop from the stack, a default value
/// of `0.0` is used.
#[inline(always)]
pub fn sub(stack: &mut Vec<f64>) {
    let (a, b) = get_ops!(stack);
    stack.push(a - b);
}

/// Pops the top two elements off the stack and multiplies them.
///
/// # Arguments
///
/// * `stack` - The stack to pop from and push onto.
///
/// *Note* - If no number is available to pop from the stack, a default value
/// of `0.0` is used.
#[inline(always)]
pub fn mul(stack: &mut Vec<f64>) {
    let (a, b) = get_ops!(stack);
    stack.push(a * b);
}

/// Pops the top two elements off the stack and divides them.
///
/// # Arguments
///
/// * `stack` - The stack to pop from and push onto.
///
/// *Note* - If no number is available to pop from the stack, a default value
/// of `0.0` is used. If division by `0.0` occurs, then a value of `0.0` pushed
/// to `stack` instead.
#[inline(always)]
pub fn div(stack: &mut Vec<f64>) {
    let (a, b) = get_ops!(stack);
    if b == 0.0 {
        stack.push(0.0);
    } else {
        stack.push(a / b);
    }
}

/// Pops the top element off the stack and pushes two copies of it on the stack.
///
/// # Arguments
///
/// * `stack` - The stack to pop from and push onto.
///
/// *Note* - If no number is available to pop from the stack, a default value
/// of `0.0` is used, thus `0.0` is pushed on to the stack twice.
#[inline(always)]
pub fn dup(stack: &mut Vec<f64>) {
    let to_dup = stack.pop().unwrap_or(0.0);
    stack.push(to_dup);
    stack.push(to_dup);
}

/// Pops the top two elements off the stack and swaps their values.
///
/// # Arguments
///
/// * `stack` - The stack to pop from and push onto.
///
/// *Note* - If no number is available to pop from the stack, a default value
/// of `0.0` is used.
#[inline(always)]
pub fn swp(stack: &mut Vec<f64>) {
    let (first, second) = get_ops!(stack);
    stack.push(second);
    stack.push(first);
}

/// Pops off two values off the stack. If the first value is not zero, take the
/// value of the second value and jump to that location in code.
///
/// # Arguments
///
/// * `reg` - The the current location of the register.
/// * `stack` - The stack to pop from and push onto.
///
#[inline(always)]
pub fn jnz(stack: &mut Vec<f64>, reg: &mut usize) {
    let (cond, jump) = get_ops!(stack);
    if cond != 0.0 {
        *reg = jump as usize;
    }
}

/// Prints the top value of a particular stack.
///
/// # Arguments
///
/// * `stack` - The stack to pop from.
/// * `output` - The output vector to push onto.
///
/// *Note* - Does not "print" to stdout, instead it prints to the `output` par-
/// ameter. This is for better debugging and test.
#[inline(always)]
pub fn print_float(stack: &mut Vec<f64>, output: &mut Vec<f64>) {
    output.push(stack.pop().unwrap_or(0.0))
}

src/bin/imastack.rs

extern crate imastack;

use std::io;
use std::io::Write;

/// Simple REPL for the imastack langauge.
fn main() {
    loop {
        let mut code = String::new();
        print!("> ");
        io::stdout().flush().unwrap();
        io::stdin().read_line(&mut code)
            .expect("Failed to read line");
        let output = imastack::eval(code.trim().to_string());
        for num in output {
            print!("{} ", num);
        }
        println!()
    }
}

Cargo.toml

[package]
name = "imastack"
version = "0.1.0"
authors = ["Christopher Sumnicht <csumnicht@berkeley.edu>"]

tests/integration_test.rs

extern crate imastack;

#[test]
fn basic_add() {
    assert_eq!(
        imastack::eval("1 2 + print".to_string()),
        vec![3.0]);
}

#[test]
fn basic_sub() {
    assert_eq!(
        imastack::eval("1 2 - print".to_string()),
        vec![1.0]);
}

#[test]
fn basic_mul() {
    assert_eq!(
        imastack::eval("3 3 * print".to_string()),
        vec![9.0]);
}

#[test]
fn basic_div() {
    assert_eq!(
        imastack::eval("3 6 / print".to_string()),
        vec![2.0]);
}

#[test]
fn div_by_zero_is_zero() {
    assert_eq!(
        imastack::eval("0 1 / print".to_string()),
        vec![0.0]);
}

#[test]
fn basic_swp() {
    assert_eq!(
        imastack::eval("1 2 swp print print".to_string()),
        vec![2.0, 1.0]);

}

#[test]
fn basic_dup() {
    assert_eq!(
        imastack::eval("1 dup print print".to_string()),
        vec![1.0, 1.0]);
}

#[test]
fn basic_jnz() {
    assert_eq!(
        imastack::eval("1 4 jnz 0 1 print".to_string()),
        vec![1.0]);
}

Here is the Cargo project on Github. A basic REPL can be launched with cargo run --bin imastack.

\$\endgroup\$
2
\$\begingroup\$

Fundamental design

First I'm going to address some issues I see with the design of your interpreter. These aren't problems with the code per say, just things I suggest to assist in maintainability, extensibility, etc.

Stack design

Right now, you're using a Vec<f64>. This is fine if you only want to represent floating-point numbers, but if you'd like to extend it to support more types, I suggest you use a vector of an enum type: Vec<Value>. This way, you can use Value to wrap any type you want (or even Invalid).

Tokens

Currently, you're parsing the tokens from strings and directly using that to execute an operation on the stack. You may consider using a Token enum and implementing From<&str> for it, so you can document those all together.

I'd also recommend using an explicit operator, like push, to signal adding a value to the stack. This way you can reject certain inputs more easily.

REPL

If you allowed the user to enter values and operators one by one, and apply them immediately, you can show the user the current value at the top of the stack in real time.

Code

lib.rs

This code is essentially just a for loop, with one gotcha. We need to be able to change the position in code.

let mut reg: usize = 0;
loop {
    let tok = tokens.get(reg);
    match tok {
        Some(&"+")     => words::add(stack),
        Some(&"-")     => words::sub(stack),
        Some(&"*")     => words::mul(stack),
        Some(&"/")     => words::div(stack),
        Some(&"dup")   => words::dup(stack),
        Some(&"swp")   => words::swp(stack),
        Some(&"jnz")   => words::jnz(stack, &mut reg),
        Some(&"print") => words::print_float(stack, output),
        Some(_)        => words::parse_number(tok.unwrap(), stack),
        None           => break
    }
    reg += 1;
}

You can instead use a while let loop to save yourself from writing a bunch of Somes:

let mut reg: usize = 0;
while let Some(tok) = tokens.get(reg) {
    match tok {
        &"+"     => words::add(stack),
        &"-"     => words::sub(stack),
        &"*"     => words::mul(stack),
        &"/"     => words::div(stack),
        &"dup"   => words::dup(stack),
        &"swp"   => words::swp(stack),
        &"jnz"   => words::jnz(stack, &mut reg),
        &"print" => words::print_float(stack, output),
        _        => words::parse_number(tok, stack),
    }

    reg += 1;
}

Also, I'm pretty sure you want to skip the increment after a jump, so you probably want to account for that somehow.

I'm not sure why you're passing in the output vector as a reference and then cloning it, I assume it's because you want to enable multiple lines of code acting on the same stack.

You probably should be passing an &str to fn eval, it's just more idiomatic.

words.rs

I'd recommend passing the stack reference as the first parameter in fn parse_number. It's good to have consistent ordering.

I'd also say implementing get_ops as an inline function would be better than using such a trivial macro.

One thing you could do is create a NewType wrapping a vector like Stack(Vec<f64>). You could then implement all of these functions as methods of that struct:

struct Stack(Vec<f64>);

impl Stack {
    // helpful alias
    #[inline(always])
    pub fn push(&mut self, item: f64) {
        self.0.push(item);
    }

    // helpful alias
    #[inline(always])
    pub fn pop(&mut self) -> f64 {
        self.0.pop().unwrap_or(0.0)
    }

    // same as get_ops
    #[inline(always])
    pub fn pop2(&mut self) -> (f64, f64) {
        (self.pop(), self.pop())
    }

    pub fn parse_number(&mut self, token: &str) {
        let number: f64 = token.parse().unwrap_or(0.0);
        self.push(number);
    }

    pub fn swp(&mut self) {
        let (first, second) = self.pop2();
        self.push(first);
        self.push(second);
    }

    ...
}

I'm pretty sure fn swp has the wrong order. You pop out element TOP then TOP - 1. You push TOP - 1 then TOP, which leaves them in the same order they were in at the start. I flipped them in the above example.

I'm not sure why you care about dividing by 0. The rust f64 type has NaN and Infinity for that very reason, though maybe it's just a usability thing.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hi! Thanks for the response! Just to clarify something: I am planning on doing some work related genetic algorithms. So the only float thing is by design. Limited output and hard to fail is what I am looking for. I do not intend to program in this language myself, ha. Nevertheless, I will keep the Value idea in mind for later languages! Also, the test passes for swp so idk what is going on with swp. Definitely changed to use struct-impl design! Thanks! \$\endgroup\$ – Dair Nov 6 '18 at 21:17
  • \$\begingroup\$ @Dair I think your test is wrong as well, actually. I assume if you run 1 2 print print your output vector should be [2, 1], since 2 is popped and output, then 1 is popped and output. 1 2 swp print print should result in an output vector of [1, 2] \$\endgroup\$ – PitaJ Nov 6 '18 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.