🙋 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 SQUARE 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 the 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: dup *. 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 square() 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".

Basic Elements

Firth supports the following "basic" elements:

Stack Elements

Firth supports the following elements to operate on the value stack:

The difference between pop and drop is that pop leaves the top value of the stack in the accumulator, whereas drop does not.

I/O

Firth supports the following elements for IO:

Conditional Elements

Firth supports two conditional statements: zero? and 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 end keyword.

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 enter0 and 1 otherwise.

  get
  zero?
    1
  else
    0
  end
  .
    

The Loop Element

Firth supports a simple loop that starts with the do keyword and ends with the loop keyword. A loop can be exited with the stop keyword.

Here is an example of a loop that runs until the user enters a zero value:

  do
    get
    zero?
      stop
    end
  loop
    

Global Variables

Firth supports global variables. They can be declared using the var keyword:

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

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 end:

  def square()
    dup *
  end
    

Functions can return to a caller by using the return element. The return element is optional: a function will implicitly return when its body completes.

Note that functions in Firth can call themselves recursively.

Inline Assembly

LMSM assembly can be included in a Firth program by using the asm keyword, followed by the end keyword.

Here is some Firth code that uses raw assembly to print out the value stored in the accumulator:

  get
  pop
  asm
    OUT
  end
    

Fibbonacci.firth

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