Mutual recursion in FORTH
Harold
two words A (which calls B) and B (which calls A).
Standard FORTH doesn't provide for forward references. So if I compile
A before B, then I can't compile the reference to B in the usual way.
RECURSE is of no help, since it can only compile a call to the word
currently being compiled.
One solution is to defer the resolution of B to run time e.g.
0 VALUE TICKB
: A TICKB EXECUTE ;
: B A ;
' B TO TICKB
But this adds overhead to the call. So I thought it might be it
possible to resolve B at compile time e.g.
0 VALUE REFB
: NOP ;
: A [ HERE TO REFB ] NOP ;
: B A ;
' B REFB !
This works on a traditional compiler, which compiles an execution
token for NOP that I can override later when I know the address of B.
But I believe an optimizing compiler is free to compile nothing for
NOP, so this won't work in that case.
Is there a portable way to implement mutual recursion with no
additional call overhead?
Hugh Aguilar
> Is there a portable way to implement mutual recursion with no
> additional call overhead?
No, there isn't. Forth is a single-pass compiler. What you are
referring to as "traditional" compilers are multi-pass. There are
actually good reasons for the decision to go with a single-pass
compiler. The downside is a minor speed penalty in mutual recursion,
but it is so minor that it shouldn't be a concern.
In my novice package I provided this code:
: xxx
true abort" *** uninitialized vector ***" ;
: defer ( -- ) \ stream: name
create ['] xxx ,
does>
@ execute ;
: is ( xt -- ) \ stream: name
state @ if postpone ['] else ' then
postpone >body postpone ! ;
immediate
This is actually the only CREATE DOES> word that I have in the
package. In this case, the comma'd in data after the CREATE is
volatile (it gets modified by IS), so it can't be a constant.
It would be possible to get rid of the state smartness by having an IS
(for interpretive mode) and an [IS] for inside of colon words. This
isn't a big deal because it is extremely unlikely that anybody will
ever tick IS and execute the xt. It is up to you though. There is no
standardization on words like this.
Harold
> On Jun 11, 1:09 pm, Harold <hzrab...@gmail.com> wrote:
>
> > Is there a portable way to implement mutual recursion with no
> > additional call overhead?
>
> No, there isn't. Forth is a single-pass compiler. What you are
> referring to as "traditional" compilers are multi-pass.
By "traditional compiler", I meant a traditional one-pass FORTH
compiler, one that always compiles an execution token for every non-
immediate word in the input stream. As distinct from an optimizing
FORTH compiler that does in-lining and redundant code elimination.
Is there any way to force an optimizing compiler to compile an
execution token for NOP (in the example I provided)?
Hugh Aguilar
Define NOP like this:
: nop
true abort" *** uninitialized vector ***" ;
This is all highly non-standard, as ANS-Forth allows several possible
threading schemes. If it is subroutine threaded, then your ! is going
to wipe out the CALL instruction. Anything that you come up with is
going to be compiler-specific. It is not worthwhile.
I recommend spending your time writing applications. Compiler tweaking
is a waste of time.
MarkWills
Would vectored execution not be a good candidate here? Sure, you add
some overhead due to the indirection, but you gain in terms of code
clarity. I would caution against over optimising and worrying too much
about the call overhead. If the code in question is not in a critical
section of your code, or on a regularly traversed code-path, then I'd
say you're good!
I can't speak for other systems, but on my system (which is classical
ITC) it would be possible to compile a dummy word into your A and B
words, and later patch the words, similar to your example. However,
this is only possible because it is a very simple compiler, compiling
XTs.
Regards
Mark
Harold
>
> I recommend spending your time writing applications. Compiler tweaking
> is a waste of time.
Jeez, that's the fun part about FORTH.
A compiler is simple enough that anyone can have their own.
What other language can make this claim?
<TROLL>
When I want to write applications, I use C. There's so much more
functionality available
ready to go in the standard C runtime library than in the standard
FORTH dictionary.
</TROLL>
It has been claimed (don't know if it's true or not) that there are
more FORTH
compiler implementations than actual applications written in FORTH.
foxchip
> I've been thinking about the best way to do mutual recursion between
> two words A (which calls B) and B (which calls A).
> Is there a portable way to implement mutual recursion with no
> additional call overhead?
There was a recent discussion of how with separated
headers fall-through and tail-recursion do that. It
looks pretty simple too.
: A
: B A ;
Which I would read as, "Define A as B and define B as A."
With tail-recursion it would compile the same thing as
BEGIN AGAIN
except that it has two entry points; A and B.
You can put real code into it otherwise it
is just an infinite loop.
: A ...
: B .... A ;
Which I would read as, "Define A as ... B
and define B as .... A."
... or .... can have code to exit the loop.
r> drop exit \ works with a real return stack
People have been doing this from about the
midpoint in current Forth history, but it isn't
standard. ANS has a syntax problem and immediacy
problem with it. It is portable but not standard.
The "A ;" part can put tail-recursion optimization
into standard compilation. It is the fall-through
of A into B by simply not using semicolon that
the standard does not support. But it remains
portable because of the extreme simplicity involved.
It doesn't have the forward reference problem
either.
Perhaps a word that removes the code compiled by
a semicolon could make it standard. Such as
: A ... ; -; \ -; removes code compiled by ;
: B .... A ;
Where -; resets the dictionary pointer back to
the semicolon compiled previously. But I don't
know if it is possible to write a portable
definition of this -; I doubt it. But that is
different than using it in a portable or
standard way.
Best Wishes
Hugh Aguilar
> When I want to write applications, I use C. There's so much more
> functionality available
> ready to go in the standard C runtime library than in the standard
> FORTH dictionary.
I'm not very good at learning things. I have found that it is almost
always easier for me to write code myself, rather than dig through the
documentation and find some existing code that does what I want (or,
more likely, something *similar* to what I want). This is a big part
of why I gave up on Factor. They have too much emphasis on being
*idiomatic* and using the extensive library that is provided with the
system. I'm just not good at learning all that stuff and remembering
it for any period of time. I get annoyed when I write a program that
works perfectly well, but then everybody complains that it is not
idiomatic. There is no good definition of "idiomatic" though. To a
large extent, this is just a way for people to put down other
programmers --- somewhat similar to the way that the Klan puts down
people by calling them "un-American" while refusing to provide a
definition of what "American" exactly entails.
I have worked as a C programmer. C is actually fairly easy for me,
because it has a pretty minimal library. Your statement "so much more
functionality available" made me laugh. Is this the same C library
that I'm familiar with? I don't remember there being a whole lot there
--- as compared to what you get with Factor or Common Lisp or
whatever. C is pretty similar to Forth in its thinness. My complaint
about C is that it is hard to work with. For example, I rely a lot on
passing vectors (pointer to functions, also known as execution tokens
(xt)) around. You can see examples of this in my list.4th program:
http://www.forth.org/novice.html
When I was writing C software I would do this, but it is a major
hassle to write a data type for a pointer to a function. I remember
that my coworkers were amazed that I did this. I was pretty much the
only one there who ever did.
I may go back to Factor again. Factor really does have "so much more
functionality available" than C, once you learn all that stuff. It is
also easier to use, having automatic garbage-collection and dynamic
OOP and so forth. I may tackle Lisp instead though. I was initially
attracted to Factor because it is supposedly Forth-like, but it has
drifted a long way from Forth over time. If I am going to delve into a
language that isn't very Forth-like, it might as well be Lisp, in
which I have a chance at finding employment.
ron
> : A
> : B A ;
That works on Reva as well. But a more "normal" way to do this would
be:
defer a
: b a ;
: real_b ... ;
' real_b is b
(or something similar on your Forth)
Mutual recursion is generally a good thing to avoid unless you keep in
mind you are doing it and plan for the consequences (e.g. the infinite
loop above, etc).
Harold
> On Jun 11, 3:57 pm, Harold <hzrab...@gmail.com> wrote:
>
> > When I want to write applications, I use C. There's so much more
> > functionality available ready to go in the standard C
> > runtime library than in the standard FORTH dictionary.
>
> Your statement "so much more
> functionality available" made me laugh. Is this the same C library
> that I'm familiar with? I don't remember there being a whole lot there
> --- as compared to what you get with Factor or Common Lisp or
> whatever.
I count 928 functions in GNU libc 2.3.4. FORTH DPANS94 defines 369
words
Hugh Aguilar
> The "A ;" part can put tail-recursion optimization
> into standard compilation. It is the fall-through
> of A into B by simply not using semicolon that
> the standard does not support. But it remains
> portable because of the extreme simplicity involved.
> It doesn't have the forward reference problem
> either.
>
> Perhaps a word that removes the code compiled by
> a semicolon could make it standard. Such as
>
> : A ... ; -; \ -; removes code compiled by ;
> : B .... A ;
>
> Where -; resets the dictionary pointer back to
> the semicolon compiled previously. But I don't
> know if it is possible to write a portable
> definition of this -; I doubt it. But that is
> different than using it in a portable or
> standard way.
Anything involving fall-through is going to be non-standard. Fall-
through only works on systems in which code and headers are in
separate blocks of memory. This isn't guaranteed by the ANS-Forth
standard --- it isn't even common.
I still say that you are investing an awful lot of time and effort in
a project that will *always* be non-standard, and which has no
practical value --- the speed boost is going to be somewhere between
negligible and non-existent for most programs.
John Passaniti
> I still say that you are investing an awful lot of time
> and effort in a project that will *always* be non-standard,
> and which has no practical value --- the speed boost is
> going to be somewhere between negligible and non-existent
> for most programs.
Part of what makes Hugh so much fun in comp.lang.forth is that he
doesn't seem to realize that the newsgroup existed before he
subscribed. Lacking that historical context, he boldly does extremely
silly things, like chastise Jeff Fox for work that will "always be non-
standard." That's just too funny.
Bernd Paysan
> I count 928 functions in GNU libc 2.3.4. FORTH DPANS94 defines 369
> words
Apples vs. oranges? I get 1883 words in Gforth, and that's only the base
image, not including libraries. Of course this includes factors and
variables mainly used internally by other words ("don't bury your tools").
Maybe you look into the C standard and see how many functions libc really
has to provide vs. those it actually does provide.
--
Bernd Paysan
"If you want it done right, you have to do it yourself!"
http://www.jwdt.com/~paysan/