Rust based Simple Stack Machine • October 24, 2022

It really wasn't easy to get a Rust development setup on my NixOS.

So here's just a litte insight into my NixOS Rust setup and my first study inspired Rust project - a Rust based Simple Stack Machine.

Initial Rust setup

The official Rust on NixOS documentation wasn't directly helpful for getting started without Rust experience. It provides some very complex setup options.

Using cargo and rustc as global packages did not work properly. So I decided to install rustup as a global package.

I think rustup as a package in home-manager would work just as well.

New Project: Rust based Simple Stack Machine

We had just discussed how deterministic stack machines work in the "Automata Theory" module when I was looking for a project to learn how to use Rust.

The deterministic stack machine

Implementing the deterministic stack machine with syntactical analysis was not too hard. I started using a struct as custom stack consisting of a list: [char; 100] and an index value to store the last relevant character position (theoretical current stack height) of the list.

Since I had written blanks at every position to initialize the list list: [' '; 100], it made sense to keep an extra index for this at that moment.

I later found out that Vec<char> is the data type I was looking for.

At start the DetSMConfig struct is filled with an empty initial stack and the input word.

struct DetSMConfig {
    remainder_word: Vec<char>,
    stack: MyStack,
}

Within the stack machine logic this configuration is edited in a loop for every character that's left in the remainder_word variable. After processing 1 character of the remainder_word in a method called step it returns a struct containing the edited DetSMConfig as well as state variables containing whether the parsing was successful up to the last character processed.

To decide whether a forward step by the stack machine was successful or not I created the DetSMStepState struct.

struct DetSMStepState {
    step_succeeded: bool,
    last_step: bool,
    cfg: DetSMConfig,
}
The non-deterministic stack machine

Since I had actually planned more time for the development and was finished much faster than expected, I then also wanted to implement a non-deterministic stack machine :)

Since the non-deterministic stack machine was only briefly mentioned at the university, I had to come up with my own concept for its development.

A non-deterministic stack machine is a bit more complex than a deterministic one because, unlike the deterministic one, there is a logical decision tree. With the assumption of a lookahead=1, it can happen during the syntactical analysis that it is only later clear which would have been the correct stack symbol for a previously processed character.

Therefore, the basic idea is to track every step / every decision in order to be able to reverse a decision made at some point before if necessary.

To accomplish this, I introduced a config_path variable into the stack machine, containing a vector of NonDetSMConfig.

struct NonDetSMConfig {
    remainder_word: Vec<char>,
    stack: Vec<char>,
    next_stack_symbol_id: usize,
}

I decided to replace my list based stack implementation with Vec<char> as stack to get rid of the stack limit, which was based on a fixed array size.

I also added next_stack_symbol_id which defaults to 0. It increases when going back from a previous config step. The stack machine is then called again with that modified stack machine configuration. If there are multiple decision options for a stack symbol, the one with the next_stack_symbol_id will be chosen. In case of an error the next_stack_symbol_id increases as long as there are no more options in the current step. Then the algorithm goes back to the previous configuration in the config_path and the procedure starts again until there are no more previous configurations. That would be the point of the final failure.

If once stack and remainder_word are both empty at the same time, the syntactical analysis was successful.

Some months later ...

... without any Rust development in the meantime my IDE was not happy on startup:


On the console I got errors as well:

cargo --version
error: command failed: 'cargo': No such file or directory (os error 2)

After checking the rust-toolchain and that everything was up-to-date the solution was too easy. rm -rf ~/.rustup

Running cargo build after deleting that folder works without any problems. Thanks to the rustup-wrapper, required project dependencies were also automatically reinstalled.

Repository

Take a look at the current project repository if you are still interested after reading that article :)