Forth: The local variable question
I fairly frequently see people who are taking an interest in Forth struggle with the idea of programming without local variables. I struggled with it when I started writing Forth! I feel like there's an unspoken assumption for people coming to Forth from other languages, and if I were to speak it aloud, it would sound something like “temporary data should go on the stack”.
Because... functions should be re-entrant by default! They should clean up after themselves! Global variables are bad and must be avoided at all costs! Functions should be “pure” and take all of their inputs as parameters, avoiding hidden dependencies!
All of these ideas of what “good code” looks like are wrong in Forth.
It is actually extremely common for Forth words to rely on implicit context, which is globally accessible through other Forth words. This is often how you build DSLs!
canvas API. It's based on PostScript, as are most vector drawing APIs, and PostScript, as you may know, is a Forth-like postfix language for printed graphics. The
canvas API has a bunch of implicit state. When you draw a rectangle, for example, you pass in just the position and size. If you want to specify properties like the fill colour, stroke colour, stroke width, line cap style, and on and on and on, you call setter methods before calling the draw function. If you want to preserve the previous canvas state and return to it when you're done, you can explicitly push it onto a stack.
This is one secret sauce to writing small Forth words – you build little vocabularies that all work with some kernel of shared state.
Let's implement Bresenham's line algorithm
I had the idea to implement an algorithm where juggling all of the state on the stack would be a nightmare, to show an example of what this looks like in practice. I've always found Bresenham's line-drawing algorithm kind of awkward – most implementations in C switch between several nearly-identical code blocks depending on how steep the line is. But the core idea is actually very simple, and the awkward near-duplication of the standard C implementation does not have to be reproduced in Forth.
First we will define a simple textual canvas vocabulary:
80 CONSTANT SCREEN-W 24 CONSTANT SCREEN-H CREATE SCREEN SCREEN-W SCREEN-H * ALLOT CREATE SCREEN-BRUSH KEY + C, : SET-BRUSH ( -- ) KEY SCREEN-BRUSH C! ; : FILL-SCREEN ( -- ) SCREEN-W SCREEN-H * SCREEN + SCREEN DO I SCREEN-BRUSH C@ SWAP C! LOOP ; : SCREEN-XY ( x y -- ptr ) SCREEN-W * + SCREEN + ; : PLOT-XY ( x y -- ) SCREEN-XY SCREEN-BRUSH C@ SWAP C! ; : PRINT-ROW ( y -- ) 0 SWAP SCREEN-XY SCREEN-W TYPE ; : PRINT-SCREEN SCREEN-H 0 DO I PRINT-ROW CR LOOP ;
This is ANS Forth – my personal Forths have all been lowercase, I don't usually like all the shouting.
This creates a buffer called
SCREEN that is 80 columns wide by 24 rows tall. It also defines the concept of a brush, which is just an ASCII character that is put into this buffer by
PLOT-XY. Our line-drawing routine will use
PLOT-XY to put “pixels” on the “screen” without caring about what they look like. Kind of a canvassy idea.
Now let's clear the screen:
SET-BRUSH + FILL-SCREEN SET-BRUSH $
I use the
+ character for “off” and the
$ character for “on” because they were about the same width in the variable-width font that my browser picked when plugging this code into jsForth. The trick where
SET-BRUSH reads the next character in the code directly is cute but brittle; it only works interactively and will break weirdly in a
: definition. WAForth can't handle it at all, it pops up a dialog box asking for you to type a character. Feel free to use
43 SCREEN-BRUSH C! to draw with
36 SCREEN-BRUSH C! to draw with
$ if you want to follow along in WAForth. Define little helper words for them even, like
BRUSH-$. It's not a big problem, don't overthink it, but do make yourself comfortable.
An aside: How to draw a line
So let's talk for a minute about how Bresenham's line-drawing algorithm works. The Wikipedia article has a bunch of math and symbols but at its core it's really very simple. Start with a specific kind of line, that slopes upwards and to the right, but not steeper than 45 degrees.
- Start at the bottom-left side of the line. Draw that pixel.
- Move your X coordinate one to the right. Now you need to decide if the Y coordinate needs to move up one or stay where it is.
- To do that, you keep track of a subpixel fraction; ie. you start in the middle of a pixel (0.5), and increment it by the amount that the line has risen over the last pixel: (y2-y1)/(x2-x1) or dy/dx.
- If the fraction is >1, move Y up one pixel and subtract 1 from the fraction; the fraction value is now somewhere within the bottom half of the next highest pixel.
- Now draw the next pixel and go back to step 2 until you end up at the top-right end of the line.
This is very simple! We then layer on just a few simple tricks:
- Instead of always moving along the X axis, for lines that are taller than they are long, we need to move along the Y axis. To do this we simply always move in the direction of the longer side, and run the decision logic along the shorter axis. This way the slope is never steeper than 45 degrees.
- If, for example, the line slopes down instead of up, when we decide whether to move along the Y axis, we need to move down one pixel instead of up. We can handle this by simply incrementing instead of decrementing along the appropriate axis.
- In the olden days, floating point numbers were very slow and integers were fast. Since the “error” value (really a fractional pixel location, but everyone calls it “error”) always has the same denominator, and we don't do anything more complicated than adding more fractions with the same denominator to it, we can just keep the denominator implicit and store the numerator in an integer. We choose
2 * dx(when x is the long axis) as the denominator so that we can easily start exactly on a half pixel (ie. our starting value is
dx/2dx, and we increment by
2 * dyevery step). It doesn't actually make a huge amount of difference what you use for a starting value though, as long as it's smaller than your implicit denominator then you'll end up with a line that starts and ends where you expect.
That's it! That's the whole thing.
Now back to writing Forth
So, first off, let's define the state that we'll need. Starting and ending X and Y coordinates, the current X and Y coordinates, and the fractional “error” value. Definitely need to remember all that.
VARIABLE LINE-X1 VARIABLE LINE-Y1 VARIABLE LINE-X2 VARIABLE LINE-Y2 VARIABLE LINE-X VARIABLE LINE-Y VARIABLE LINE-ERR
Now we can start defining helper words. Let's write a couple of words to figure out the length of the line along each axis:
: LINE-DX ( -- dx ) LINE-X2 @ LINE-X1 @ - ; : LINE-DY ( -- dy ) LINE-Y2 @ LINE-Y1 @ - ;
No sweat; just take
x2 - x1 or
y2 - y1. How about some words to decide which axis is longer, and what direction each axis is moving in?
: X-LONGER? ( -- f ) LINE-DX ABS LINE-DY ABS > ; : LINE-LEFT? ( -- f ) LINE-DX 0 < ; : LINE-UP? ( -- f ) LINE-DY 0 < ;
Even if you're not well-practiced reading postfix, I hope it's pretty clear what these are doing.
Now let's define some words for incrementing or decrementing, depending on which direction the line is going:
: LINE-XINC ( x -- x ) LINE-LEFT? IF 1- ELSE 1+ THEN ; : LINE-YINC ( y -- y ) LINE-UP? IF 1- ELSE 1+ THEN ; : LINE-INC ( x|y x? -- x|y ) IF LINE-XINC ELSE LINE-YINC THEN ;
LINE-INC is our first and only word to take two values on the stack – the top is a boolean that determines if we're talking about the X or Y axis. We will soon use it in conjunction with
X-LONGER? to abstract away incrementing the “long”
vs. “short” axis.
: LINE-LONG ( -- p ) X-LONGER? IF LINE-X ELSE LINE-Y THEN ; : LINE-SHORT ( -- p ) X-LONGER? 0= IF LINE-X ELSE LINE-Y THEN ; : LINE-LONG-INC! ( -- ) LINE-LONG @ X-LONGER? LINE-INC LINE-LONG ! ; : LINE-SHORT-INC! ( -- ) LINE-SHORT @ X-LONGER? 0= LINE-INC LINE-SHORT ! ;
LINE-LONG-INC! is a little tricky, so let's walk through it:
LINE-LONGreturns a pointer to either the
@fetches the current coordinate along the long axis.
X-LONGER?pushes “true” onto the stack if X is the long axis (and thus the X coordinate is what's on the stack)
LINE-XINCif X is long, or
LINE-YINCif Y is long. This increments or decrements the value, depending on the direction of the line. The new coordinate is the one value left on the stack.
LINE-LONG !fetches the appropriate pointer again and stores the new value.
LINE-SHORT-INC! is basically the same, except with an
0= in there as a “logical not” for
X-LONGER?. (It didn't quite seem worthwhile to define
Y-LONGER? on its own.)
Now let's define some useful words for the error / fractional pixel calculation:
: LINE-LONG-LEN ( -- l ) X-LONGER? IF LINE-DX ELSE LINE-DY THEN ABS ; : LINE-SHORT-LEN ( -- l ) X-LONGER? IF LINE-DY ELSE LINE-DX THEN ABS ; : LINE-LONG-ERR ( -- err ) LINE-LONG-LEN 2 * ; : LINE-SHORT-ERR ( -- err ) LINE-SHORT-LEN 2 * ; : LINE-INIT-ERR! ( -- ) LINE-LONG-LEN LINE-ERR ! ; : LINE-ERR-ACC ( -- err ) LINE-ERR @ LINE-SHORT-ERR + ;
LINE-INIT-ERR! defines the initial error value as half a pixel (with
LINE-LONG-ERR being the implicit denominator).
LINE-ERR-ACC fetches the current error and adds the appropriate fraction along the short axis, leaving the new value on the stack.
: LINE-ERR-INC! ( err -- err ) DUP LINE-LONG-ERR >= IF LINE-LONG-ERR - LINE-SHORT-INC! THEN ; : LINE-ERR-ACC! ( -- ) LINE-ERR-ACC LINE-ERR-INC! LINE-ERR ! ; : LINE-STEP ( -- ) LINE-LONG-INC! LINE-ERR-ACC! ;
LINE-ERR-INC! takes the incremented error value, determines if we've overflown the fraction into the next pixel, and if so, decrements the error value and increments the coordinate along the short axis. The updated error value is left on the stack. This is the only place in the algorithm where I chose to use a stack-manipulation word. I could have gotten by without it by just calling
LINE-ERR-ACC a couple of times, but it would have made the definition longer and arguably harder to follow.
LINE-ERR-ACC! handles accumulating the error, incrementing the short axis if necessary, and storing the new error. Finally,
LINE-STEP puts all the core logic together – increment along the long axis, then decide whether we need to increment along the short axis.
All that's left is to run it in a loop:
: PLOT-LINE-STEP ( -- ) LINE-X @ LINE-Y @ PLOT-XY ; : DO-LINE ( -- ) LINE-INIT-ERR! LINE-LONG-LEN 0 DO PLOT-LINE-STEP LINE-STEP LOOP PLOT-LINE-STEP ; : LINE ( x1 y1 x2 y2 -- ) LINE-Y2 ! LINE-X2 ! DUP LINE-Y ! LINE-Y1 ! DUP LINE-X ! LINE-X1 ! DO-LINE ;
The final definition of
LINE takes four values on the stack and immediately puts them into variables that are used by all the other words.
IMO, this is what Forth enthusiasts mean when they say things like “write lots of small definitions”, or “the stack shouldn't need to be very deep”, or “you don't need local variables”. There are 24 one line function definitions up there. No individual definition is particularly complicated or hard to read. We do virtually no stack manipulation.
Let's see it in action!
0 0 0 15 LINE 0 0 15 15 LINE 30 15 0 0 LINE 60 15 0 0 LINE 79 7 0 0 LINE 79 7 60 15 LINE 0 15 60 15 LINE PRINT-SCREEN
$$$$$$++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ $$$$$$$$$$$$$$$$$+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ $+$+$$+$$$$++++++$$$$$$$$$$$$+++++++++++++++++++++++++++++++++++++++++++++++++++ $++$++$$+++$$$$++++++++++++++$$$$$$$$$$$++++++++++++++++++++++++++++++++++++++++ $+++$+++$$+++++$$$$+++++++++++++++++++++$$$$$$$$$$$+++++++++++++++++++++++++++++ $++++$++++$$+++++++$$$$++++++++++++++++++++++++++++$$$$$$$$$$$$+++++++++++++++++ $+++++$+++++$$+++++++++$$$$++++++++++++++++++++++++++++++++++++$$$$$$$$$$$++++++ $++++++$++++++$$+++++++++++$$$$+++++++++++++++++++++++++++++++++++++++++++$$$$$$ $+++++++$+++++++$$+++++++++++++$$$$+++++++++++++++++++++++++++++++++++++++++$$++ $++++++++$++++++++$$+++++++++++++++$$$$+++++++++++++++++++++++++++++++++++$$++++ $+++++++++$+++++++++$$+++++++++++++++++$$$$++++++++++++++++++++++++++++$$$++++++ $++++++++++$++++++++++$$+++++++++++++++++++$$$$++++++++++++++++++++++$$+++++++++ $+++++++++++$+++++++++++$$+++++++++++++++++++++$$$$+++++++++++++++$$$+++++++++++ $++++++++++++$++++++++++++$$+++++++++++++++++++++++$$$$+++++++++$$++++++++++++++ $+++++++++++++$+++++++++++++$$+++++++++++++++++++++++++$$$$+++$$++++++++++++++++ $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Now, there is plenty to criticize about this code. It does all kinds of redundant recalculation that in any sane C implementation would have been stashed away into a local, for example. But that's fixable with a little more effort; I might do another blog post where I apply some of Forth's fun metaprogramming tricks to that problem.