Re: [Factor-talk] Threaded Code?

[Levi Pearson]

https://concatenative.org/wiki/view/Factor/Non-optimizing%20compiler

Apparently the JIT for the interactive non-optimizing compiler generates
subroutine threaded code with some inlining.

I wouldn't call it a compiler optimization; maybe an interpreter
optimization or a simple compiling technique. I think you hear about it a
lot with respect to Forth and its family because of the proportion of Forth
users who implemented the language or at least learned how it was
implemented, although often modern Forth implementations have optimizing
compilers. But the earliest academic reference I've seen for threaded code
was in reference to a Fortran compiler for the PDP-11:
http://home.claranet.nl/users/mhx/Forth_Bell.pdf

I'm pretty sure that 1971 article was more of a description of a technique
already widely in practice (i.e. a description of "folklore") rather than a
new invention, so it's definitely been around a whlie.

I wrote a simple threaded code interpreter in C as an exercise to
understand them better a while back; including some conditionally-compiled
debug code and a fairly small complement of core Forth words and an outer
interpreter loop, it's still well under 1k lines of source.

--Levi

On Tue, Jan 31, 2017 at 3:23 PM, Björn Lindqvist  wrote:

> Probably not! I've never heard of that technique. From skimming that
> Wikipedia article it seem to be a compiler optimization invented a
> long time ago. We have an instruction called ##dispatch, used for
> method dispatching, but it is not nearly as dynamic as the method
> described. Probably for the best because on modern processors jumping
> to addresses kept in memory or in registers is very bad for
> performance.
>
>
> 2017-01-31 21:11 GMT+01:00 Alexander Ilin :
> > Hello!
> >
> >   Does Factor use threaded code in any way?
> >   https://en.wikipedia.org/wiki/Threaded_code
> >
>
--
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot___
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk

Re: [Factor-talk] Bresenham Linedraw: unbalanced conditionals

[Levi Pearson]

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