I nominate this post for inclusion in some extended tutorial documentation
somewhere, so it can get wider distribution to people trying to learn
Factor. Very nice!
On Jul 4, 2013 10:16 AM, "Alex Vondrak" <ajvond...@gmail.com> wrote:
> 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
>
>
------------------------------------------------------------------------------
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
