2
\$\begingroup\$

I recently asked for a review of a stack based language I made in Rust. I made a lot of changes since then and a lot has changed. Hopefully I haven't gone backwards in progress.

Most notably:

  1. I refactored the code into a lexer and parser. In other words: there is a module for taking in a string and converting it into a vector of tokens. This vector of tokens is then executed.

  2. I have added a better REPL that live updates each line. As you are writing code in the console the output is displayed in the bottom right corner.

The only thing I didn't do from the answer was implement more than one data type than a float. See my comment on the answer for more details. However, there is now a Float structure for that AST.

src/ast/mod.rs

//! This module contains functions and structures related to the AST of the im-
//! astack language. Most notably, it converts between "string" *tokens* and e-
//! num representation.

use std::str::FromStr;
use std::fmt;
use std::ops::Add;
use std::ops::Sub;
use std::ops::Mul;
use std::ops::Div;


/// Wrapper for `f64`. 
///
/// *Note* This is needed for `strum` to operate correctly as `From<&'a str>`
/// needs to be implemented, which is impossible with a bare `f64`.
#[derive(Debug)]
pub struct Float(pub f64);

impl Clone for Float {
    fn clone(&self) -> Float { Float(self.0) }
}

impl PartialEq for Float {
    fn eq(&self, other: &Float) -> bool {
        self.0 == other.0
    }
}

impl<'a> From<&'a str> for Float {
    #[inline]
    fn from(s: &'a str) -> Self {
        Float(s.parse::<f64>().unwrap_or(0.0).to_owned())
    }
}

impl fmt::Display for Float {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl Into<usize> for Float {
    #[inline]
    fn into(self) -> usize {
        self.0 as usize
    }
}

impl Add for Float {
    type Output = Float;

    #[inline]
    fn add(self, other: Float) -> Float {
        Float(self.0 + other.0)
    }
}


impl Sub for Float {
    type Output = Float;

    #[inline]
    fn sub(self, other: Float) -> Float {
        Float(self.0 - other.0)
    }
}

impl Mul for Float {
    type Output = Float;

    #[inline]
    fn mul(self, other: Float) -> Float {
        Float(self.0 * other.0)
    }
}

impl Div for Float {
    type Output = Float;

    #[inline]
    fn div(self, other: Float) -> Float {
        Float(self.0 / other.0)
    }
}


#[derive(EnumString)]
pub enum Token {
    #[strum(serialize="+")]
    Add,
    #[strum(serialize="-")]
    Sub,
    #[strum(serialize="*")]
    Mul,
    #[strum(serialize="/")]
    Div,
    #[strum(serialize="dup")]
    Dup,
    #[strum(serialize="swp")]
    Swp,
    #[strum(serialize="jnz")]
    Jnz,
    #[strum(serialize="print")]
    Print,
    #[strum(default="true")]
    Number(Float)
}

impl Into<Float> for Token {
    /// Convets Token into Float.
    ///
    /// *Note* It tries the best it can, even though it doesn't make sense to 
    /// convert Token::Add to a float, it defaults this (as well as every other
    /// operator to Float(0.0).
    fn into(self) -> Float {
        match self {
            Token::Number(Float(x)) => Float(x),
            _                       => Float(0.0)
        }
    }
}

/// Compiles a vector of stringy tokens into the a vector of `Token`s.
/// 
/// *Note* It tires the best it can, if the token can't be parsed, convert it
/// to a `Float(0.0)` as default.
pub fn compile_program(tokens: &[&str]) -> Vec<Token> {
    let mut ast = Vec::new();
    for tok in tokens {
        let res = match Token::from_str(tok) {
            Ok(good_tok) => good_tok,
            _            => Token::Number(Float(0.0))
        };
        ast.push(res);
    }
    ast
}

src/words/mod.rs

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

use ast::Float;

/// Represents and "environment" for a programming language. In this small lan-
/// guage it is simply a "stack" that stores numbers and an "output vector" th-
/// at captures what the output would be.
pub struct Env {
    pub stack: Vec<Float>,
    pub output: Vec<Float>
}

impl Env {

    /// Helper function for pushing onto the environment's stack.
    #[inline(always)]
    pub fn push(&mut self, item: Float) {
        self.stack.push(item);
    }

    /// Helper function for pushing onto the environment's stack.
    #[inline(always)]
    pub fn pop(&mut self) -> Float {
        self.stack.pop().unwrap_or(Float(0.0))
    }

    /// Extracts two values off the top of a stack.
    #[inline(always)]
    pub fn get_ops(&mut self) -> (Float, Float) {
        (self.pop(), self.pop())
    }

    /// Parses a numerical value to a float.
    ///
    /// # Arguments
    ///
    /// `token` - The value to be converted to a float.
    ///
    /// *Note* - If `parse_number` is **not** given a number, it will still return
    /// `0.0`.
    #[inline(always)]
    pub fn push_number(&mut self, number: Float) {
        self.push(number);
    }

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

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

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

    /// Pops the top two elements off the stack and divides them.
    ///
    /// *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(&mut self) {
        let (a, b) = self.get_ops();
        if b.0 == 0.0 {
            self.push(Float(0.0));
        } else {
            self.push(a / b);
        }
    }

    /// Pops the top element off the stack and pushes two copies of it on the stack.
    ///
    /// *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(&mut self) {
        let to_dup = self.pop();
        let copy = to_dup.clone();
        self.push(to_dup);
        self.push(copy);
    }

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

    /// 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.
    ///
    /// * `reg` - The the current location of the register.
    ///
    #[inline(always)]
    pub fn jnz(&mut self, reg: &mut usize) {
        let (cond, jump) = self.get_ops();
        if cond.0 != 0.0 {
            *reg = jump.into();
        }
    }

    /// Prints the top value of a particular stack.
    ///
    /// *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(&mut self) {
        let popped = self.pop();
        self.output.push(popped);
    }
}

src/bin/imastack.rs

//! This the REPL for the imastack language. The output of the current line is
//! displayed at the bottom of the screen.
extern crate imastack;
extern crate ncurses;

use std::process;

/// Simple REPL for the imastack langauge.
fn main() {
    ncurses::initscr();
    ncurses::raw();
    ncurses::noecho();
    ncurses::keypad(ncurses::stdscr(), true);

    let mut code: Vec<String> = Vec::new();
    code.push(String::from(" "));
    let mut current_line: usize = 0;
    let mut current_col: usize = 0;
    loop {
        ncurses::mv(current_line as i32, current_col as i32);
        let ch = ncurses::getch();
        match ch {
            ncurses::KEY_ENTER => {
                code.push(String::from(" "));
                current_line += 1;
                current_col = 0;
            },
            // Also enter key...
            10 => {
                code.push(String::from(" "));
                current_line += 1;
                current_col = 0;
            },
            ncurses::KEY_UP => {
                match current_line {
                    0 => { },
                    _ => current_line -= 1,
                };
                current_col = 0;
            },
            ncurses::KEY_DOWN => {
                if current_line == code.len() {
                } else {
                    current_line += 1;
                }
                current_col = 0;
            },
            // Exit with Tab key.
            9 => process::exit(0),
            character => {
                code[current_line].push(character as u8 as char);
                ncurses::addch(character as u64);
                current_col += 1;
            }
        };
        let env = imastack::eval(&code[current_line].as_str());
        let mut footer = String::new();
        for num in env.output {
            footer.push_str(&num.to_string());
            footer.push(' ');
        }
        ncurses::mv(ncurses::LINES() - 1, 0);
        ncurses::clrtoeol();
        ncurses::mvprintw(ncurses::LINES() - 1,
                          ncurses::COLS() - footer.len() as i32,
                          &mut footer.to_string());
    }
}

src/lib.rs

extern crate strum;
#[macro_use]
extern crate strum_macros;

pub mod ast;
pub mod words;

use ast::Token;
use words::Env;

/// 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: &[Token], 
                   env: &mut Env) {
    // Analogous to the role of a "register" for a Turing machine.
    let mut reg: usize = 0;
    while let Some(tok) = tokens.get(reg) {
        match tok {
            Token::Add       => env.add(),
            Token::Sub       => env.sub(),
            Token::Mul       => env.mul(),
            Token::Div       => env.div(),
            Token::Dup       => env.dup(),
            Token::Swp       => env.swp(),
            Token::Jnz       => env.jnz(&mut reg),
            Token::Print     => env.print_float(),
            Token::Number(x) => env.push_number(x.clone()),
        }
        reg += 1;
    }
}

/// 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: &str) -> Env {
    let tokens: Vec<&str> = code.split(' ').collect();
    let mut env = Env {
        stack: Vec::new(),
        output: Vec::new(),
    };
    let ast = ast::compile_program(tokens.as_slice());
    execute_program(ast.as_slice(), &mut env);
    env
}

tests/integration_test.rs

extern crate imastack;
use imastack::ast::Float;

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

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

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

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

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

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

}

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

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

The Github is here. You can start the REPL with:

cargo run --bin imastack

and you can exit the REPL by pressing the Tab key.

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

Some basic comments.

  1. I'd pull the Float struct out into its own file - it makes the src/ast/mod.rs longer than it needs to be.

  2. I think you can derive Clone and PartialEq on Float, rather than implementing them manually.

  3. Consider deriving Copy on Float, since it's trivially copyable - that will allow you to remove some explicit calls to clone.

  4. Error handling seems "lax". In particular parsing and evaluation just default rather than error. Maybe that's OK here, but I try to avoid it. You probably want your own Result type. Once you use it in many places the code doesn't get any uglier, as most places rather than return the default you can just use the ? operator.

pub fn compile_program(tokens: &[&str]) -> Vec<Token> {
    let mut ast = Vec::new();
    for tok in tokens {
        let res = match Token::from_str(tok) {
            Ok(good_tok) => good_tok,
            _            => Token::Number(Float(0.0))
        };
        ast.push(res);
    }
    ast
}

would become

pub fn compile_program(tokens: &[&str]) -> Result<Vec<Token>> {
    let mut ast = Vec::new();
    for tok in tokens {
        ast.push(Token::from_str(tok)?);
    }
    ast
}

Which can be made even neater using map and collect - I think you can do:

pub fn compile_program(tokens: &[&str]) -> Result<Vec<Token>> {
    tokens.map(Token::from_str).collect()
}
  1. The AST parsing code could probably do with some unit tests.
\$\endgroup\$
  • \$\begingroup\$ Thanks! I have nearly implemented all your suggestions. One thing about the "lax" error handling: I don't intend on programming in this language. I can add a strict_compile_program function though! I'm working on evolving programs with genetic algorithms. They start off pretty dumb and need a lot of help. Having the programs error a lot at the beginning could easily kill of the entire population. \$\endgroup\$ – Dair Dec 14 '18 at 22:36

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.