Russ-Forth Core
All of the infrastructure shown above is fine and dandy, but by itself it doesn’t do anything. To add some capability requires seeding the run-time environment with some core words. As I alluded to earlier, the core way to define words is to write them as Ruby module methods which are then mixed in at start time.
Before I start, I should make it clear that the implementation methods must adhere to a certain standard:
- All core words deal with an implicit
@stackproperty
That is, RForth works off of a single globally accessible stack defined in the Russforth class which will be accessible to the core words once they’re mixed in at run-time. If I were creating a stack-based language in something like Clojure (something more extensive than I showed earlier) than I would make the implementation quite different. That said, while allowing access to a shared property feels a little nasty, there are some advantages for clarity and ease of testing.
One potential problem with dealing in a global stack, and this is a problem even in many stack-based languages, is that it’s not immediately clear just by reading the code what the stack effects might be. Therefore, while discussing the implementations herein I’ll use a variant of the stack effect annotations available in the Factor programming language. For example, the stack effect [x -- x x] means that a word takes a stack and duplicates the top element and pushes it back onto the stack. Another example is [x y -- y x] that refers to the action of popping the first two elements off of the stack and pushing them back on in reverse order. The general form of the annotation is [<before> -- <after>]. When reading stack effect annotations remember that the top of the stack is always the rightmost element of both the <before> and <after> segments.
Enough already – let’s begin with the fun stuff.
A quick example – “pop”
To start I’ll show a very simple stack operator named “.” that does one simple thing – it pops the top element from the stack and prints it out. The word lives in a module devoted to stack operations and for my purpose is the only word there:
1 module Verbs
2 module StackOps
3 # [x -- ]
4 def dot
5 @s_out.print( @stack.pop )
6 end
7 end
8 end
The . word works as follows:
1 1 2 .
Or graphically:
1 | 2 | | 1 |
2 | 1 | -> | |
3 +---+ +---+
As the element 2 is popped off of the stack it’s printed. The implementation of . is trivial, but I wanted to start with it just to show the layout of the implementation modules, the use of @stack, and how I’ll show examples.
Arithmetic
Every good (and bad) programming language need mathematical operators and RForth is no exception. All of the RForth math words live in the same module:
1 module Math
2 module Arithmetic
I won’t belabor the implementations too much, as you can probably infer what they do just by reading them. For example, here are the implementations for plus and mult:
1 # [a b -- c]
2 def plus
3 @stack << (@stack.pop + @stack.pop)
4 end
5
6 # [a b -- c]
7 def mult
8 @stack << (@stack.pop * @stack.pop)
9 end
The implementations for subtract and divide are only slightly more involved
1 # [r l -- m]
2 def subtract
3 left = @stack.pop
4 right = @stack.pop
5 @stack << left - right
6 end
7
8 # [d n -- q]
9 def divide
10 numerator = @stack.pop
11 denominator = @stack.pop
12 @stack << numerator / denominator
13 end
For the sake of completeness I’ll just show the code for a one more word below:
1 # [a -- b]
2 def abs
3 @stack << (@stack.pop.abs)
4 end
5 end
6 end
There’s not much to show here, but I’ll eventually make use of these mathematical words later. Slightly more interesting words are implemented next.
Comparators
The set of comparison operators live in a common module:
1 module Verbs
2 module Comparators
For my purposes I’ll need a relatively small set of comparators, starting with an equality word:
1 # [a b -- true|false]
2 def eq
3 a = @stack.pop
4 b = @stack.pop
5
6 @stack << (a == b)
7 end
As previously shown, the eq method is aliased to the = word and works as follows:
1 1 2 =
Or graphically:
1 | 2 | | false |
2 | 1 | -> | |
3 +---+ +-------+
You’ll notice that the values 1 and 2 were consumed from the stack by =. This is common in Forth-like languages as it’s expected that most operations will use the stack as a scratchpad for computation, wiping and writing constantly as they go. There are some Forth-like languages that also provide variable declarations for lexical-based use and reference, but those will not be used in RForth. The implementation for <> is very similar, as you might expect:
1 # [a b -- true|false]
2 def noteq
3 a = @stack.pop
4 b = @stack.pop
5
6 @stack << (a != b)
7 end
Likewise, for logical comparisons:
1 # [a b -- true|false]
2 def gt
3 rhs = @stack.pop
4 lhs = @stack.pop
5
6 @stack << (lhs > rhs)
7 end
8
9 # [a b -- true|false]
10 def lt
11 rhs = @stack.pop
12 lhs = @stack.pop
13
14 @stack << (lhs < rhs)
15 end
16 end
17 end
And that’s all for comparators for now.
I/O
Before I dig into the meatier words, I want to take a few moments to show the implementation of a few useful words related to I/O, all implemented in a common module:
1 module Verbs
2 module Io
The simplest I/O word is one that prints an arbitrary character:
1 def emit
2 @s_out.print( @stack.last.chr )
3 end
Which can both be used to implement a word named .S that can be used to inspect the state of the stack:
1 def dot_s
2 @s_out.print( "#{@stack}>\n" )
3 end
4 end
5 end
The .S word prints a little hat on the top end of the stack to show the direction that the elements will be popped off.
Now that I’ve gotten these out of the way, I’ll now dive into the more interesting topic of stack shuffling.
Shufflers
An interesting set of core words implemented in RForth are the “stack shufflers.” In a nutshell, shufflers take elements off the stack and (perhaps) put them back on in various different configurations. All of the shufflers will reside in a common module:
1 module Verbs
2 module Shufflers
The easiest possible shuffler is called drop that takes a stack and just pops the top, throwing it away:
1 # [a -- ]
2 def drop
3 @stack.pop
4 end
The drop word works as follows:
1 1 2 drop
Or graphically:
1 | 2 | | 1 |
2 | 1 | -> | |
3 +---+ +---+
The nice thing about Ruby arrays is that they can be treated just like stacks, so the use of Array#pop is pretty clear. Likewise, the << (append to end) operator is analogous to a stack push, so a word named dup that just duplicates the top element is implemented in a straight-forward way:
1 # [a -- a a]
2 def dup
3 @stack << @stack.last
4 end
The dup word works as follows:
1 1 dup
Or graphically:
1 | 1 | | 1 |
2 | | -> | 1 |
3 +---+ +---+
One other nicety that Ruby provides is the array literal notation [...] which allows me to define the swap word via array concatenation:
1 # [a b -- b a]
2 def swap
3 @stack += [@stack.pop, @stack.pop]
4 end
Since the last element in the @stack refers to the top element, I was able to use the sequencing of the #pop operation to build a temporary array with the swapped order in place.
The swap word works as follows:
1 1 2 swap
Or graphically:
1 | 2 | | 1 |
2 | 1 | -> | 2 |
3 +---+ +---+
I can use a similar technique as swap for the implementation of rot (rotate) below:
1 #[a b c -- b c a]
2 def rot
3 top = @stack.pop
4 mid = @stack.pop
5 lst = @stack.pop
6 @stack += [mid, top, lst]
7 end
8 end
9 end
The rot word works as follows:
1 1 2 3 rot
Or graphically:
1 | 3 | | 1 |
2 | 2 | | 3 |
3 | 1 | -> | 2 |
4 +---+ +---+
A word analogous to rot is called over that takes the element under the top, duplicates it, and then pushes it back onto the stack:
1 # [a b -- a b a]
2 def over
3 top = @stack.pop
4 und = @stack.pop
5 @stack += [und, top, und]
6 end
The over word works as follows:
1 1 2 over
Or graphically:
1 | | | 1 |
2 | 2 | | 2 |
3 | 1 | -> | 1 |
4 +---+ +---+
And that’s all for now. I’ll show more later when I get into user-defined words and combinators.
Combinators
The final set of core words that I’ll talk about are the combinators. In short, combinators are a set of words that incorporate the use of other words to perform some operation. All of the combinators are implemented in a common module:
1 module Verbs
2 module Combinators
The first combinator word that I’ll talk about is named apply that takes a Proc and just calls it for its stack effects:
1 # [... [...] -- ...]
2 def apply
3 op = @stack.pop
4 op.call
5 end
The apply word works as follows:
1 1 2 [ + ]
Or graphically:
1 | [ + ] | | 3 |
2 | 2 | | |
3 | 1 | -> | |
4 +--------+ +---+
A more involved variant of apply is called dip that takes a Proc and an element on the stack and then applies that Proc to the rest of the stack, finally pushing the saved element back onto the stack:
1 # [... a [ ... ] -- ... a]
2 def dip
3 op = @stack.pop
4 stash = @stack.pop
5 op.call
6 @stack << stash
7 end
The dip word is an interesting little piece of business because of the way that it uses the stash variable to hold a piece of data for later pushing. As an added bonus, it together with ., dup, and swap forms a primitive base for implementing control flow structures, (Spiewak 2008) but I’ll only touch on that tangentially.
Industrial-strength Forth implementations provide a stashing mechanism in the language itself via something known as the “return stack.” The return stack is a structure used implicitly by Forth run-times as a place to store and retrieve the maze of pointers within and between nested words (Noble 1992). However, while the return stack is an internal run-time structure, Forth programmers happily use it as needed as a place to store values temporarily (as they need to be gone before a word finishes execution). To push values onto the return stack, Forth implementations (often) provide a set of operators >r and r> to push and pop values from the return stack. Therefore, to implement dip in a “real Forth” would look like the following:
1 : dip swap >r execute r> ;
You would read this implementation as: 1. swap the top two main stack elements 2. store the top of the main stack onto the return stack 3. execute the quotation on the top of the main stack 4. push the top of the return stack onto the main stack
As you’ve probably already noticed, RussForth does not have a return stack as it wasn’t necessarily needed. However, adding something analogous to a return stack wouldn’t be too difficult, but I leave that as an exercise to the reader.
The implementation of dip is not too complicated, but it could use some illustration to really help explain what’s happening. First, let me say that you might instinctively think to type the following:
1 5 10 2 * dip
To mean “perform multiplication on 5 and 10, storing 2 back onto the stack.” The problem is that the default action of the read phase was to push words onto the stack by default, but dip requires a Proc as one of its arguments. However, if you recall, the way to push a Proc was to use the quotation form, which means that the code should be written as:
1 5 10 2 [ * ] dip
Now that the * word is encapsulated within a Proc residing at the top of the stack, dip can grab a hold of it and invoke the #call method on it.
Graphically, the stack prior to the execution of dip looks as follows:
1 | [ * ] |
2 | 2 |
3 | 10 |
4 | 5 |
5 +-------+
Before dip calls the Proc implementing the quotation, the stack will look like:
1 | 10 |
2 | 5 |
3 +-------+
Where, internally dip will hold onto the 2 after which it will be pushed back onto the stack after the quotation is executed:
1 | 2 |
2 | 50 |
3 +-------+
This is pretty cool because it illustrates in a simple way the use of quotations in RForth and how they’re used by combinators to do some snazzy stuff. However, this installment is not about combinators, so while I’m tempted to continue, I’d like to take a step back and talk a little bit about building up a language.
core.rf
Now that I’ve put in place some core functions I can start to build a core library using them. This section will not present a fully fleshed out core, but I’ll go over some interesting examples to give a feel for the kinds of things that comprise a Forth-like run-time.
Before I start I want to point out that earlier I showed the implementation of an immediate word \\ that ate character until it found a newline. This is of course an implementation of a comment word:
1 \\ This is a comment
2 10 \\ The stack should now have 10
3 .S \\= The print out should be [10]>
The last comment line above is how I will display execution results such as I/O print outs and the like.
That out of the way, the first thing that I’d like to create is a simple utility to print out a newline. If you recall I implemented an emit word that I could use to implement just such a user-defined utility:
1 : cr 10 emit ;
So now, if we wanted to use this in a program to print a message it’s as simple as:
1 72 emit 105 emit 33 emit cr
2 \\= Hi!
A more useful Forth word is one called nip that is used to pop the element immediately under the top of the stack:
1 : nip swap drop ;
The nip word works as follows:
1 1 2 nip
Or graphically:
1 | 2 | | 2 |
2 | 1 | -> | |
3 +---+ +---+
Another useful word is known as tuck that stashes a copy of the top of the stack under the next element down:
1 : tuck swap over ;
The tuck word works as follows:
1 1 2 tuck
Or graphically:
1 | | | 2 |
2 | 2 | | 1 |
3 | 1 | -> | 2 |
4 +---+ +---+
A couple of arithmetical operators that might be useful are implemented below:
1 : inc 1 + ;
2 : dec 1 - ;
Perhaps it’s obvious what these words do, but just in case it’s not, observe the following:
1 2 inc inc
Or graphically:
1 | 2 | -> | 4 |
2 +---+ +---+
Followed by:
1 dec
Gives:
1 | 4 | -> | 3 |
2 +---+ +---+
This is pretty straight-forward, but I’m leading up to something more interesting than the implementation of a core library. In the next section I’ll expand on this thread of thought and show how the manner in which Forth programs are constructed can inform the construction of programs in any other language.