Tearing Away the Scaffolding

[The seventh in a series of posts on the evolution of TransForth]

At this point we have a reasonably complete Forth that’s pretty fun to play with. Like I said in the first post though, we don’t just want to build a Forth in F#. Stopping here wouldn’t be in keeping with “Forth Tradition” which is to become intimate with the hardware. The point of starting this series in a high level, succinct language is to understand and get everything functioning, but then to move much lower.

 

We have a working system with unit tests in place, it’s time to start moving more of the system to Forth itself and eventually to assembly language and even a tiny bit of direct machine code. Think of what we have now as scaffolding. We can do an incremental migration; all the while with a working, tested system at each step.

 

Already a good portion of our words are defined in Forth itself with a only small set of primitives defined in F#. In this post we’ll migrate all the stack-related words. We did some nifty trimming a few posts back when we redefined DUP, SWAP, OVER and ROT in terms of PICK and ROLL. Now we’re going to go even further and define even PICK and ROLL in terms of simpler primitives. We’ll also redo DROP, DEPTH and CLEAR as well as the return stack words ( >R, R> and R@ ), the loop counts (I, J and K) and even the print-stack word ( .S).

 

The basic strategy will be to move the stacks to memory and then to define everything in terms of low-level memory manipulation.

 

Memory Layout

 

So far, memory has been used exclusively by the dictionary. Now we’re going to need to throw into the mix a pair of stacks and I’d like to reserve a portion for “system variables.” A common layout is to grow the dictionary up from low memory and the stacks down from high memory.

 

 

This partitions our little simulated memory store nicely. Similar to the way we’ve handled the dictionary, each stack will be maintained by a simple index register; indicating the top of the stack (which really grows down in the diagram). Popping the stack will simply mean retrieving the value to which the index points and then incrementing the index. Pushing will mean decrementing the index and storing there.

 

There will be no safely checks for stacks or the dictionary overrunning their partitions. Danger is all part of the fun! (we'll add back stack underflow checks later)

 

Memory-mapped Registers

 

We’re going to use the “System” area for a set of memory mapped registers among other things. These registers will represent the stack and the dictionary pointers with designated cells representing each. This will make them easy to manipulate with ! and @ without having to add new primitive words.

 

let s = 0 // data stack

let r = 1 // return stack

let h = 2 // dictionary pointer

 

Initialize the registers per our memory layout:

 

mem.[h] <- 0x0400

mem.[s] <- 0x2FFF

mem.[r] <- 0x3FFF

 

Appending to the dictionary will be based on this register value instead of the mutable we were using before:

 

let append v = mem.[mem.[h]] <- v; mem.[h] <- mem.[h] + 1

 

We’ll add Forth psudo-constants too for these memory mapped register locations:

 

: S 0 ;

: R 1 ;

: H 2 ;

 

And we can go ahead and get rid of our F# definition (define "HERE" (fun () -> push h) ) and instead go with:

 

: HERE H @ ;

 

Moving the Stacks

 

Our current implementation of the stacks is based on F# Lists and pattern matching:

 

letmutable stack = []

let underflow () = failwith "Stack empty"

let push value = stack <- value :: stack

let pop () = match stack with h :: t -> stack <- t; h | _ -> underflow ()

letmutable rstack = []

let rpush value = rstack <- value :: rstack

let rpop () = match rstack with h :: t -> rstack <- t; h | _ -> underflow ()

 

As nice as this is, we’re going to ditch it in favor of a lower-level approach that will be more accessible from within Forth. We could implement the stacks entirely in Forth, but we still have some F# code playing around with them, so for now we’ll do the following.

 

We define functions for pushing and popping relative to a particular given register:

 

let push' reg value = mem.[reg] <- mem.[reg] - 1; mem.[mem.[reg]] <- value

let pop' reg () = mem.[reg] <- mem.[reg] + 1; mem.[mem.[reg] - 1]

 

Then redefine our existing functions in terms of these:

 

let push = push' s

let pop = pop' s

let rpush = push' r

let rpop = pop' r

 

Now Comes the Fun Part!

 

We get to tear away a bunch of F# and replace it with Forth. First a couple of standard words to address both ends of the stack:

 

: S0 12287 ; \ bottom of the stack

: SP@ S @ ; \ current top of stack

 

Starting with the easy ones, our F# definitions of DEPTH, CLEAR and DROP are:

 

define "DEPTH" (fun () -> stack.Length |> push)

define "CLEAR" (fun () -> stack <- [])

define "DROP" (fun () -> stack <- match stack with _ :: t -> t |_->underflow())

Easy enough. Replace with:

 

: DEPTH ( -- n) S0 SP@ - 1- ;

: CLEAR ( --) S0 S ! ;

: DROP ( a -- ) SP@ 1+ S ! ;

I’m not going to go into great detail about each of these. Hopefully the original F# code makes the intent clear and parsing the (I assume unfamiliar) Forth code is part of the fun.

 

Next, let’s switch to the return stack. We had the basic “push”, “pop” and “peek” equivalents and had several “counter” words used to access loop indices being stored on the return stack:

 

define ">R" (fun () -> pop () |> rpush)

define "R>" (fun () -> rpop () |> push)

define "R@" (fun () -> push rstack.Head)

let counter name offset = define name (fun ()-> List.nth rstack offset |> push)

counter "I" 1

counter "J" 3

counter "K" 5

 

A bit tedious, but not too bad to redo in Forth:

 

: >R R @ DUP DUP 1- R ! @ R @ ! ! ;

: R> R @ 1+ @ R @ @ R @ 1+ ! R @ 1+ R ! ;

: R@ R @ 1+ @ ;

: COUNTER 2* 3 + R @ + @ ;

: I 0 COUNTER ;

: J 1 COUNTER ;

: K 2 COUNTER ;

 

Part of the difficulty here was to be very careful of the state of the return stack. We have to remember that it’s being actively used while walking these definitions. For example, we could factor all the “R @ 1+” to a separate word (say FOO), but then a new return address would have been pushed and messes things up before calling FOO.

Next, PICK and ROLL are very interesting. Remember that they were the basis of the other stack manipulation words (DUP, SWAP, OVER and ROT):

define "PICK" (fun () -> pop () |> List.nth stack |> push)

define "ROLL" (fun () ->

    let i = ref (pop ())

    match List.partition (fun _ -> i := !i - 1; !i >= 0) stack with

    | (h, v :: t) -> stack <- v :: h @ t | _ -> underflow ())

By moving these last two to Forth, we have no more F# definitions at all for doing stack manipulation! PICK is easy, but ROLL takes quite some work; having to remember the nth value (using the return stack for temporary storage), walk along shifting all the values, and finally restore the nth value to the top:

 

: PICK SP@ + 1+ @ ;

: ROLL SP@ 1+ + DUP @ >R BEGIN DUP >R 1- DUP @ R> ! DUP SP@ 2+ = UNTIL DROP R> SP@ 1+ ! ;

 

I doubt this definition of ROLL is ideal, but it will do until we can redefine it once more in assembly. The biggest difficulty with ROLL is that we can’t use things like SWAP in the definition without a circular dependency and so have to do some tricky shuffling. I’ll step through an example of how it works in a moment.

 

Finally, we may as well redefine printing of the stack while we can. This:

define ".S" (fun () -> stack |> List.rev |> List.iter print)

 

Becomes the following, and we’re done!

 

: .S SP@ 1- S0 1- 2DUP < IF DO I @ . -1 +LOOP THEN ;

 

Visualizing Stepping Through Code

 

I have no idea how most Forth devs visualize things as they work, but below is what I do.

 

In general it’s a bad idea to build up lots of stuff on the stack. In fact, “stack juggling” is a telltale sign that you’re doing it wrong. Sometimes though it’s unavoidable (as in our definition of ROLL with the circular dependency constraint). I must admit I broke a sweat coming up with the above definition.

 

Let’s play “human computer” and step through an execution of the phrase “1 2 3 2 ROLL” – lifting out the 1, resulting in 2 3 1 on the stack. Splaying out the process into a table with stack states and fragments of executed code. Addresses are shown as circled values to which they point.

 

Step	Data Stack >	Executed	< Return Stack	Comment
0	1 2 3 2	ROLL		ROLL expands
1	1 2 3 ❶	SP@ 1+ +		Addr of Nth value
2	1 2 3 ❶ 1	DUP @		Get Nth value
3	1 2 3 ❶	>R	1	Move to temp
4	1 2 3 ❶	BEGIN	1	Loop: shift values
5	1 2 3 ❶	DUP >R	❶ 1	“To” addr
6	1 2 3 ❷	1-	❶ 1	“From” addr
7	1 2 3 ❷ 2	DUP @	❶ 1	Value
8	1 2 3 ❷ 2 ❶	R>	1	To addr
9	2 2 3 ❷	!	1	Store
10	2 2 3 ❷ 0	DUP SP@ 2+ =	1	TOS yet?
11	2 2 3 ❷	UNTIL	1	Continue until TOS
12	2 2 3 ❷	DUP >R	❷ 1	Repeat step 5
13	2 2 3 ❸	1-	❷ 1	Repeat step 6
14	2 2 3 ❸ 3	DUP @	❷ 1	Repeat step 7
15	2 2 3 ❸ 3 ❷	R>	1	Repeat step 8
16	2 3 3 ❸	!	1	Repeat step 9
17	2 3 3 ❸ -1	DUP SP@ 2+ =	1	Repeat step 10
18	2 3 3 ❸	UNTIL	1	Reached TOS, done
19	2 3 3	DROP	1	Can’t swap!
20	2 3 3 1	R>	1	Restore temp
21	2 3 3 1 ❸	SP@ 1+		Recalculate addr
22	2 3 1	!		Done

 

Notice at the very end there (step 19), we had the address we wanted sitting on the stack but had to throw it away and recalculate after slipping in the temp value because we’re not able to use SWAP.

 

Tests

 

No new tests this time, but all of the 120 or so added earlier still pass.

 

Next>

Comments

• Anonymous
  March 15, 2011
  This series is awesome, thanks for publishing it!
• Anonymous
  May 28, 2011
  @Dan Very glad you like it!