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!

Perhaps you are familiar with the JavaScript 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 + and 36 SCREEN-BRUSH C! to draw with $ if you want to follow along in WAForth. Define little helper words for them even, like BRUSH-+ and 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.

  1. Start at the bottom-left side of the line. Draw that pixel.
  2. 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.
  3. 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.
  4. 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.
  5. 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:

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

$$$$$$++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
$$$$$$$$$$$$$$$$$+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
$+$+$$+$$$$++++++$$$$$$$$$$$$+++++++++++++++++++++++++++++++++++++++++++++++++++
$++$++$$+++$$$$++++++++++++++$$$$$$$$$$$++++++++++++++++++++++++++++++++++++++++
$+++$+++$$+++++$$$$+++++++++++++++++++++$$$$$$$$$$$+++++++++++++++++++++++++++++
$++++$++++$$+++++++$$$$++++++++++++++++++++++++++++$$$$$$$$$$$$+++++++++++++++++
$+++++$+++++$$+++++++++$$$$++++++++++++++++++++++++++++++++++++$$$$$$$$$$$++++++
$++++++$++++++$$+++++++++++$$$$+++++++++++++++++++++++++++++++++++++++++++$$$$$$
$+++++++$+++++++$$+++++++++++++$$$$+++++++++++++++++++++++++++++++++++++++++$$++
$++++++++$++++++++$$+++++++++++++++$$$$+++++++++++++++++++++++++++++++++++$$++++
$+++++++++$+++++++++$$+++++++++++++++++$$$$++++++++++++++++++++++++++++$$$++++++
$++++++++++$++++++++++$$+++++++++++++++++++$$$$++++++++++++++++++++++$$+++++++++
$+++++++++++$+++++++++++$$+++++++++++++++++++++$$$$+++++++++++++++$$$+++++++++++
$++++++++++++$++++++++++++$$+++++++++++++++++++++++$$$$+++++++++$$++++++++++++++
$+++++++++++++$+++++++++++++$$+++++++++++++++++++++++++$$$$+++$$++++++++++++++++
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Lovely!

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.

#forth #essays #code