🙋 The Little Man Stack Machine
Firth: A High Level Stack Oriented Language
A design goal of the LMSM is to provide just enough infrastructure such that a small, high-level programming language can be built for it relatively easily. Because of the stack instructions that the LMSM adds to the LMC, a stack-oriented programming language makes the most sense.
Stack languages are not popular today, but in the past there was a lot of interest in them, and they provide an interesting, alternative way to think about programming.
The programming language for the LSMS is called "Firth", which is, to an extent, based on the Forth programming language. Similar to Forth, Firth mainly uses a Reverse Polish notation style of syntax, and the concept of an implicit stack.
It is recommended that a Firth compiler is provided with implementations of the LMSM, to show how a high-level programming language can compile down to LMSM assembly.
An Example Firth Program: Squaring A Number
Before we delve into the details of Firth, let's look at an example program, based on the
assembly program we looked at on the LMSM Assembly page. The Firth program
that would compile down to this assembly looks like this:
get square() . def square() dup * end
This program probably looks a little strange to you, so let's go through it line by line.
The first line,
get, gets an integer from the user and pushes it onto the top of the value stack.
The second line,
square(), invokes the function
square. Note that the argument to
square function is passed implicitly, on the value stack. A little crazy but
this is how Forth and many stack-based programming languages work.
The third line,
., prints the top of the stack out.
Next comes the definition of the function
square(). Its body consists of a single line:
These two "words" are the Firth way of saying "Duplicate the top of the value stack and then replace the top two
values of the value stack with the result of multiplying them together."
This is the "Reverse Polish notation" nature of Firth. In a more traditional programming language, this calculation would look something like this:
def square(x) x * x end
In this code the multiplication operator uses Infix notation. Firth, instead, uses the RPN style, where you "push" values onto a stack and then apply operations to them.
Note that there is no explicit
return in the definition of the
function. There is actually support for the
return keyword in Firth, but it isn't necessary here:
the square value is computed by the body of the function and left on the value stack, so when the function returns
the return value is where it should be.
Kind of a hack, but it works, and this program will do what we want: ask the user for a number and then print the square of it.
So that's a quick introduction to the Firth programming language. Now let's look at all the elements of the language in more detail.
Elements Of The Firth Programming Langauge
The Firth programming language consists of a set of elements. Calling them "expressions" or "statements" in the traditional sense of those terms is a little misleading since values are stored on a stack, so we will stick with the term "element".
Firth supports the following "basic" elements:
Firth supports the following elements to operate on the value stack:
|Pop The Top Of The Stack||
|Duplicate Top Of Stack||
|Swap The Top Two Elements On The Stack||
|Drop The Top Element Of The Stack||
The difference between
drop is that
pop leaves the top value
of the stack in the accumulator, whereas
drop does not.
Firth supports the following elements for IO:
Firth supports two conditional statements:
positive?. These elements
consume the top of the stack. If the condition is true of the top of the stack, they execute the elements in
their body, which is terminated by an
If the condition is not true, the elements will execute an optional
else block, if it is included,
otherwise they will do nothing.
Here is a simple "inverter" example Firth program that asks the user for some input and then prints
1 if the user enter
get zero? 1 else 0 end .
The Loop Element
Firth supports a simple loop that starts with the
do keyword and ends with the
keyword. A loop can be exited with the
Here is an example of a loop that runs until the user enters a zero value:
do get zero? stop end loop
Firth supports global variables. They can be declared using the
Variables can be set by appending an exclamation point to their name. This will consume the top of the stack
and set the variable to the value. The following program declares a variable
x, saves user input
into it, multiplies the variable by itself and then prints the result:
var x get x! x x * .
Variables must be declared first in Firth programs, and are global. They cannot be declared within functions, loops or conditionals.
Functions can be declared using the
def keyword, followed by a function name. All function names
must end in the characters
(). Note that you cannot declare parameters for a function: they
are passed implicitly on the stack.
The implementation of the function consists of a series of elements, followed by the keyword
def square() dup * end
Functions can return to a caller by using the
return element. The
is optional: a function will implicitly return when its body completes.
Note that functions in Firth can call themselves recursively.
LMSM assembly can be included in a Firth program by using the
asm keyword, followed by the
Here is some Firth code that uses raw assembly to print out the value stored in the accumulator:
get pop asm OUT end
Below is a recursive implementation of the fibonacci algorithm in Firth:
get fib() . def fib() dup zero? return end dup 1 - zero? return end dup 2 - fib() swap 1 - fib() + end