OK, I've gone about implementing this on my own from the Wikipedia article,
and I have a few salient points about your implementation.
To preface, the general issue I took with doLine was that it was doing too
much work in one word. As you said, the code is "rather C-like". But I
think it's a bit of a chicken-or-the-egg problem because of all the
variables you need for Bresenham's algorithm.
One "feature" of this algorithm is how much state you have to keep around:
dx, dy, sx, sy, err, x0, x1, y0, y1, intermediate variables... You
naturally start using locals, but pretty soon you have to cram too much
into one word since, well, locals are hard to factor out. They are "local"
after all, so the one big word is where you have access to your variables
for modification (already looking like a C-based program...). It's hard to
justify factoring out a helper word like
```
:: doLine ( ax ay bx by code -- codeout )
bx ax - abs :> dx
by ay - abs :> dy
dx dy - :> err
ax :> cx
ay :> cy
ax ay bx by cx cy dx dy err code some-helper-word ;
```
because `some-helper-word` still has to take about a million variables in
from the stack, resigning it to a locals-laden implementation. It doesn't
really simplify anything. Plus, the loop has to destructively update these
locals at some point, so even with helper words you'll have to do something
like
```
var1 var2 var3 helper-word var1! var2! var3!
```
It's just not very useful.
But what to do? After implementing it myself, I have a few general ideas:
1. To cut down on all these variables, store your state in its own tuple.
This is a Factor-ism that doesn't crop up often, but is a pretty natural
way to ease up on complex parameter passing and stack shuffling.
2. As I suspected, `with-return` helps with what you're trying to
accomplish, while alleviating the need to worry about the extra `continue`
parameter.
3. This is not really part of your formulation, but it came up in the
version I was trying to write. If you ever find yourself attempting to
build a sequence, but the logic doesn't fit into a ready-made combinator
(like `map` or `follow` or `produce`), the `make` vocabulary is perfect:
http://docs.factorcode.org/content/article-namespaces-make.html As an added
bonus, it works via side-effect, which helps eliminate stack shuffling.
4. As the stack shuffling gets tighter, start trying to tease out words
from the "big" definitions. Factoring out what you can, locals ideally
become the artifact of only a couple small words, rather than the crux of
one huge word.
---
Consider this a sort of spoiler alert. :) In case you want to see how I did
it with these points in mind, here's a walk-through of my version. The
full code is available at http://paste.factorcode.org/paste?id=3021 if
you'd prefer to try understanding it on your own (I find that sometimes
reading code is more edifying than having it explained).
To keep the state in its own tuple, I actually defined two classes:
```
TUPLE: point x y ;
C: <point> point
TUPLE: bresenham-state
{ p point }
{ q point }
{ dx integer }
{ dy integer }
{ sx integer }
{ sy integer }
{ error integer } ;
```
This lets me initialize the state of the algorithm and manage it all in one
instance of an object. To update the state, just update the slots of a
`bresenham-state` instance. (I know `p` and `q` are conventional names for
quotations, but I think they serve well as names of points here.)
I use the following code to initialize the algorithm's state. Notice how I
factor out operations into small words. Mind you, there are about a
million ways to do this, all about equally understandable, so this is
really the least important part of the program:
```
: delta ( p q quot: ( point -- coord ) -- delta )
bi@ - abs ; inline
: initialize-deltas ( state -- state )
[ ] [ p>> ] [ q>> ] tri
[ [ x>> ] delta >>dx ]
[ [ y>> ] delta >>dy ] 2bi ;
: step ( p q quot: ( point -- coord ) -- step )
bi@ < 1 -1 ? ; inline
: initialize-steps ( state -- state )
[ ] [ p>> ] [ q>> ] tri
[ [ x>> ] step >>sx ]
[ [ y>> ] step >>sy ] 2bi ;
: initialize-error ( state -- state )
[ ] [ dx>> ] [ dy>> ] tri - >>error ;
: <bresenham-state> ( p q -- state )
\ bresenham-state new
swap >>q
swap >>p
initialize-deltas
initialize-steps
initialize-error ;
```
Words (currently, anyway:
https://github.com/slavapestov/factor/issues/758#issuecomment-16514324)
have to be defined in Factor bottom-up, but for the purposes of this
narrative, I'll explain my implementation of the algorithm in a top-down
fashion.
Starting with the main loop of the algorithm, notice how I use
`with-return` to exit early. Also notice the lack of clutter from assorted
variable-juggling, because I have the state packaged up into one
parameter. I don't even need to have return values from the other words
I'm calling, because they'll be destructive on the state. And you'll see
I'm easily breaking the problem down into calls to other words. Aside: the
name `?move-x` can be read as "maybe move x", by convention.
```
:: bresenham's-algorithm ( state -- )
[
[ t ] [
state plot
state done? [ return ] when
state ?move-x
state done? [ state plot return ] when
state ?move-y
] while
] with-return ;
```
The `done?` check looks to see if the current point (p) matches the end
point (q). Because I'm representing points as tuples, calling `=` on them
will compare their respective slots' values. Points only have the `x` slot
and the `y` slot, so `point0 point1 =` effectively works like the "x0 = x1
and y0 = y1" pseudocode.
```
: done? ( state -- ? ) [ p>> ] [ q>> ] bi = ;
```
`?move-x` and `?move-y` are the "meat" of the algorithm. They happen to
use locals, but only so we can conveniently extract the right parts of the
state. Since we're using tuple slots to store the state (look ma, no
variables!), we can just use words like change-x, change-y, and
change-error. Not only does it read pretty well, but it will modify the
tuple we're pointing to ("the stack" is a stack of pointers) without us
worrying about returning any fancy values on the stack or using
destructive! local! variables!.
```
:: ?move-x ( state -- )
state error>> 2 *
state dy>> neg > [
state p>> [ state sx>> + ] change-x drop
state [ state dy>> - ] change-error drop
] when ;
:: ?move-y ( state -- )
state error>> 2 *
state dx>> < [
state p>> [ state sy>> + ] change-y drop
state [ state dx>> + ] change-error drop
] when ;
```
Finally, though I have the freedom to define `plot` however I want, my
thought was to collect the points of the line into one sequence. This is
where `make` comes in. The final two words I define are:
```
: plot ( state -- ) p>> clone , ;
: draw-line ( from to -- points )
<bresenham-state> [ bresenham's-algorithm ] { } make ;
```
Note that I have to clone the `p>>`, because I'm destructively updating the
point's coordinates as I loop. If I didn't `clone`, then `draw-line` would
return an array of references to the same point tuple in memory---so each
element of the sequence would have the same coordinates!
So, with the clone, I get:
```
IN: scratchpad 1 1 <point> 11 5 <point> draw-line .
{
T{ point { x 1 } { y 1 } }
T{ point { x 2 } { y 2 } }
T{ point { x 3 } { y 2 } }
T{ point { x 4 } { y 3 } }
T{ point { x 5 } { y 3 } }
T{ point { x 6 } { y 3 } }
T{ point { x 7 } { y 4 } }
T{ point { x 8 } { y 4 } }
T{ point { x 9 } { y 5 } }
T{ point { x 10 } { y 5 } }
T{ point { x 11 } { y 5 } }
}
```
Without the clone, I'd get:
```
IN: scratchpad 1 1 <point> 11 5 <point> draw-line .
{
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
T{ point { x 11 } { y 5 } }
}
```
because each element would be a pointer to the same tuple. :)
Now, if you want to play with my code as a base, I leave you with this
challenge / suggested improvement: instead of having a static `plot` word,
modify it so that a user can pass in their own quotation to do whatever
plotting they want---draw a pixel on the screen, set an array coordinate,
print a message, send commands to a robot, whatever. Essentially, turn the
`bresenham's-algorithm` word into a combinator that acts on each point
along the line. Then my `make`-based definition could be something like
```
<bresenham-state> [ [ clone , ] each-point ] { } make
```
and your code to set grid cells could be something like
```
<bresenham-state> <grid> '[ _ set-cell ] each-point
```
and so on.
Hope that helps,
--Alex Vondrak
------------------------------------------------------------------------------
This SF.net email is sponsored by Windows:
Build for Windows Store.
http://p.sf.net/sfu/windows-dev2dev
_______________________________________________
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
