6 Glossary

6.1.2120 RECURSE CORE

Interpretation:

Interpretation semantics for this word are undefined.

Compilation:

( -- )

Append the execution semantics of the current definition to the current definition. An ambiguous condition exists if RECURSE appears in a definition after DOES>.

See:

Rationale:

Typical use: : X ... RECURSE ... ;

This is Forth's recursion operator; in some implementations it is called MYSELF. The usual example is the coding of the factorial function.

: FACTORIAL ( +n1 -- +n2)
   DUP 2 < IF DROP 1 EXIT THEN
   DUP 1- RECURSE *
;

n2 = n1(n1-1)(n1-2)...(2)(1), the product of n1 with all positive integers less than itself (as a special case, zero factorial equals one). While beloved of computer scientists, recursion makes unusually heavy use of both stacks and should therefore be used with caution. See alternate definition in A.6.1.2140 REPEAT.

Testing:

T{ : GI6 ( N -- 0,1,..N ) 
     DUP IF DUP >R 1- RECURSE R> THEN ; -> }T
T{ 0 GI6 -> 0 }T
T{ 1 GI6 -> 0 1 }T
T{ 2 GI6 -> 0 1 2 }T
T{ 3 GI6 -> 0 1 2 3 }T
T{ 4 GI6 -> 0 1 2 3 4 }T

DECIMAL
T{ :NONAME ( n -- 0, 1, .., n ) 
     DUP IF DUP >R 1- RECURSE R> THEN 
   ; 
   CONSTANT rn1 -> }T
T{ 0 rn1 EXECUTE -> 0 }T
T{ 4 rn1 EXECUTE -> 0 1 2 3 4 }T

:NONAME ( n -- n1 )
   1- DUP
   CASE 0 OF EXIT ENDOF
     1 OF 11 SWAP RECURSE ENDOF
     2 OF 22 SWAP RECURSE ENDOF
     3 OF 33 SWAP RECURSE ENDOF
     DROP ABS RECURSE EXIT
   ENDCASE
; CONSTANT rn2

T{  1 rn2 EXECUTE -> 0 }T
T{  2 rn2 EXECUTE -> 11 0 }T
T{  4 rn2 EXECUTE -> 33 22 11 0 }T
T{ 25 rn2 EXECUTE -> 33 22 11 0 }T

ContributeContributions

enochavatar of enoch [9] proposal: recurse' to complement recurseComment2015-12-03 23:46:08

recurse' is just like recurse but returns an XT instead of calling. It is being implemented in amforth-shadow and is mainly used by words to reschedule themselves for execution after a desired delay. A trivial example:

: every-1000ms
  ." do something" cr
  1000 0 recurse' enlist  if  ." enlist error" cr  then
;

I hope what "enlist" does can easily be guessed. If not visit my github repository :-)

Thanks, Enoch.

AntonErtlavatar of AntonErtl

Gforth has RECURSIVE, which can be used for this purpose; e.g., your example would become:

: every-1000ms recursive \ <-- makes EVERY-1000ms visible
  ." do something" cr
  1000 0 ['] every-1000ms enlist  if  ." enlist error" cr  then
;

enochavatar of enoch

recurse (and therefore its absent recurse' counterpart) does have a right to exist, cf. :noname and [: quotations ;] I don't like Gforth recursive declaration... it should be called "revealed" or something similar, if at all ...

ruvavatar of ruv

IMO, recurse' is not good enough name due to use of tick (it is better to avoid special chars in names for regular words). I can suggest the name itself for such word.

enochavatar of enoch

The use of tick ', sharp #, etc. is encouraged by the Forth Programmer’s Handbook -- Table 15: Naming conventions. We should minimize the number of names to remember thus, I would have no problem if recurse is renamed itself and completed by itself', but that's not an option for historical reasons.

ruvavatar of ruv

In the light of recognizers it is better to leave the special characters for various literals and the like.

ruvavatar of ruv

Also, itself is not directly connected with recursion — it can be returned as result or compiled into another definition.

: tt  ... if  ... lit, itself compile, ... then ... ;

It is one real usage case.

Reply New Version

Blackiceavatar of Blackice [125] Why RECURSE is needed?Request for clarification2020-01-09 21:15:01

: FACTORIAL ( +n1 -- +n2 ) DUP 2 < IF DROP 1 EXIT THEN DUP 1- FACTORIAL * ; After the execution of the ":" the word FACTORIAL is defined in the vocabulary and available for FIND. Even as incomplete definition, nothing prevents to compile the call to itself. Why special word is needed?

AntonErtlavatar of AntonErtl

See the specification of : :

The current definition shall not be findable in the dictionary until it is ended

So your FACTORIAL does not work in standard Forth. That's why Forth has RECURSE.

Why are colon definitions only visible later? 1) If you make an error, resulting in an incomplete definition, this protects you from calling it. 2) You can define words with the same name, and extended behaviour that calls a previous word with the same name.

massungavatar of massung

There is a reason why it's not findable in the dictionary, and it's a feature: it allows you to extend existing words in the dictionary be referencing the old behavior without having to know the original code. For example:

: dup ." Duplicating " dup . cr dup ;

I don't need to know how DUP is implemented, but I just extended it so that future uses of DUP will output to the console that it was called. Additionally, it doesn't affect the original behavior, which other code is using; it only impacts new uses, meaning there's no chance of damaging existing, working code.

PeterKnaggsavatar of PeterKnaggs

Your assumption is invalid. Although the dictionary entry for FACTORIAL is indeed defined when : (colon) is executed, the definition is "smudged" so that it is not available to FIND and friends. Thus using FACTORIAL will execute a previous definition of FACTORIAL rather than starting the current definition again. The when ; (semi-colon) is executed it removes the smudge from the dictionary entry, making the new definition of FACTORIAL viable. Thus to direct execution back to the start of the current definition you must use RECURSE.

ruvavatar of ruv

It is important to add that creating and "smudging" a dictionary entry by Colon ":" is only one of several possible ways of implementing the requirements. All these details, such as a dictionary entry and smudging, are under the hood and not available for a standard program.

GeraldWodniavatar of GeraldWodni

This his been discussed by the TC and we deem the replies above by Anton Ertl and Peter Knaggs to clarify the question.

As to smudging: this is not used in the standard any more.

Closed
Reply New Version

JohanKotlinskiavatar of JohanKotlinski [288] Tail call eliminationComment2023-02-21 06:27:11

Wouldn't it be nice if the standard guaranteed tail call elimination, like in Scheme and other languages?

AntonErtlavatar of AntonErtl

Advantages

Programs could use tail-recursion instead of loops.

Concerning the performance advantage of tail-call elimination, there is no need to standardize tail-call elimination for individual systems to reap this benefit. Also, the standard does not specify any performance guarantees.

Disadvantages

Backtraces would not contain all calls in a call chain. Forth systems that do not perform tail-call elimination now would have to be rewritten (unless this feature was made optional, but then the advantage would vanish).

Existing practice

Many Forth systems do not perform tail-call elimination.

Several Forth systems, in particular SwiftForth and colorForth perform tail-call elimination, although I don't know of any guarantees. AFAIK colorForth programs are written to perform tail-recursion instead of loops, but I doubt that there is any SwiftForth-specific program that requires this feature (well, maybe some return-address manipulating programs that were written to take the return-stack behaviour of SwiftForth in consideration; but such programs are non-standard either way). Recursion seems to be not very popular among Forth programmers.

I expect that the committee sees things like I discussed them above, so I am closing this comment. If you want consideration from the whole committee, please reopen it.

Closed

StephenPelcavatar of StephenPelc

Guaranteeing tail call elimination would be a disaster. Any word that manipulates the return stack cannot be eliminated. Identifying such words automagically is non-trivial.

: jmp >r ;

: (.")  r> count  2dup + >r  type  ;

Now introduce a word further up that adjusts the return stack.

: (.")  ((")) type  ;

Stephen

AntonErtlavatar of AntonErtl

A program that performs return-address manipulation like your examples is not a standard program. So any guarantees the standard might give would not apply to these programs.

Nonetheless, I expect that you have legacy return-address manipulating programs that expect no tail-call elimination. Automatically covering both these legacy programs and hypothetical standard programs that require tail-call elimination would be a challenge (depending on how the guarantee was specified). But it would be possible to cover both with a manual switch.

BTW, the use of return-address manipulation for implementing locals results in VFX 5.11 being slower than lxf by more than a factor of four on sendmore.fth. I understand why you want to support legacy programs that use such techniques, but it's unclear why you still use it internally.

ruvavatar of ruv

Programs could use tail-recursion instead of loops.

Yes, and it's the only advantage on the source code level.

I employed a kind of loop, which just jumps to the begin of the word. It can be used in any place where exit can be used, and semantically it's equivalent to tail-recursion recurse exit. Such a loop can be easily implemented (with some limitations — even in a standard program), and it does not break anything.

A practical result is that in some cases definitions become shorter.

An example: a word that returns the next value (a string) from the current SQL query, having multiple result sets.

: next-value ( -- sd.value | 0 0 )
  res if
    row if
      next-col? if
        get-value
        exit
      then
    then
    next-row? if itself-again then
  then
  next-result? if itself-again then
  0.
;

NB: the word next-value is defined in a local namespace, so names are so short. Obviously, recurse exit can be used in place of itself-again.

But it would be possible to cover both with a manual switch.

SP-Forth/4 has such a switch, which turn on tail call elimination. By default it's turned off, since in some cases incorrect code is still produced.

Of course tail call elimination cannot be required by the standard since it's difficult to implement, and sometimes it's even impossible to implement without changing the format of generated code (e.g. in case of generating asmjs).

AntonErtlavatar of AntonErtl

Standard Forth cannot be implemented to generate asm.js as is, because asm.js does not support run-time code generation (at least that's what a student reported who was interested in a project with that topic). Should we destandardize POSTPONE, COMPILE, etc. because of that? Of course, you can still implement a Forth interpreter in asm.js and such an interpreter can support tail-call elimination.

In any case, hypothetical implementations are a weak reason for non-standardization. If you have a particular asm.js-based implementation in mind, please provide a pointer.

JohanKotlinskiavatar of JohanKotlinski

Hi, sorry for being unclear! I certainly did not mean that there should be a general guarantee of tail-call elimination.

What I meant, RECURSE ; and RECURSE EXIT could guarantee tail-call elimination.

I realize that it is a bold proposal. But it would make RECURSE way more useful, to allow recursive code without stack-overflow.

Reply New Version