Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #30533 > unrolled thread

BEGIN with multiple AGAINs?

Back to article view | Back to comp.lang.forth

Contents

  BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-21 13:44 -0700
    Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-05-21 17:11 -0400
    Re: BEGIN with multiple AGAINs? mhx@iae.nl - 2014-05-21 14:31 -0700
      Re: BEGIN with multiple AGAINs? mhx@iae.nl - 2014-05-21 15:07 -0700
    Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-21 14:51 -0700
    Re: BEGIN with multiple AGAINs? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-05-21 21:59 +0000
    Re: BEGIN with multiple AGAINs? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2014-05-22 00:09 +0100
    Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-21 22:31 -0700
      Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-05-22 01:58 -0400
        Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-22 08:02 -0700
          Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-05-22 11:31 -0400
            Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-22 11:03 -0700
              Re: BEGIN with multiple AGAINs? forthisit@gmail.com - 2014-05-22 11:13 -0700
                Re: BEGIN with multiple AGAINs? forthisit@gmail.com - 2014-05-22 11:15 -0700
          Re: BEGIN with multiple AGAINs? forthisit@gmail.com - 2014-05-22 08:57 -0700
    Re: BEGIN with multiple AGAINs? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-05-22 13:47 +0000
    Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-22 11:27 -0700
      Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-22 11:38 -0700
      Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-05-22 14:47 -0400
        Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-22 12:22 -0700
    Re: BEGIN with multiple AGAINs? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-05-23 02:44 -0500
      Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-23 02:06 -0700
        Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-05-23 05:47 -0400
      Re: BEGIN with multiple AGAINs? "Elizabeth D. Rather" <erather@forth.com> - 2014-05-24 13:04 -1000
        Re: BEGIN with multiple AGAINs? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-05-25 15:06 -0500
          Re: BEGIN with multiple AGAINs? "Elizabeth D. Rather" <erather@forth.com> - 2014-05-25 16:37 -1000
            Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-05-25 23:56 -0400
            Re: BEGIN with multiple AGAINs? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-05-26 04:02 -0500
              Re: BEGIN with multiple AGAINs? "Elizabeth D. Rather" <erather@forth.com> - 2014-05-26 07:44 -1000
    Re: BEGIN with multiple AGAINs? "Clyde W. Phillips Jr." <cwpjr02@gmail.com> - 2014-05-23 12:39 -0700
    Re: BEGIN with multiple AGAINs? "Clyde W. Phillips Jr." <cwpjr02@gmail.com> - 2014-05-23 16:49 -0700
      Re: BEGIN with multiple AGAINs? Coos Haak <chforth@hccnet.nl> - 2014-05-24 02:00 +0200
    Re: BEGIN with multiple AGAINs? "Clyde W. Phillips Jr." <cwpjr02@gmail.com> - 2014-05-23 17:00 -0700
    Re: BEGIN with multiple AGAINs? "Clyde W. Phillips Jr." <cwpjr02@gmail.com> - 2014-05-23 21:29 -0700
      Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-24 08:10 -0700
        Re: BEGIN with multiple AGAINs? "Clyde W. Phillips Jr." <cwpjr02@gmail.com> - 2014-05-24 13:55 -0700
          Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-05-24 18:41 -0400
    Re: BEGIN with multiple AGAINs? Bee <forth@calcentral.com> - 2014-05-24 17:09 -0700
      Re: BEGIN with multiple AGAINs? "Clyde W. Phillips Jr." <cwpjr02@gmail.com> - 2014-05-24 18:05 -0700
        Re: BEGIN with multiple AGAINs? "Clyde W. Phillips Jr." <cwpjr02@gmail.com> - 2014-05-24 18:09 -0700
          Re: BEGIN with multiple AGAINs? ForthFreak <forthfreak@gmail.com> - 2014-05-25 02:03 -0700
            Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-05-25 05:18 -0400
              Re: BEGIN with multiple AGAINs? ForthFreak <forthfreak@gmail.com> - 2014-05-25 03:01 -0700
                Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-25 14:10 -0700
                  Re: BEGIN with multiple AGAINs? "Clyde W. Phillips Jr." <cwpjr02@gmail.com> - 2014-05-25 15:19 -0700
    Re: BEGIN with multiple AGAINs? Bee <forth@calcentral.com> - 2014-05-25 10:13 -0700
      Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-05-25 15:22 -0700
        Re: BEGIN with multiple AGAINs? BruceMcF <agila61@netscape.net> - 2014-06-12 13:11 -0700
          Re: BEGIN with multiple AGAINs? David J <skamolex@gmail.com> - 2014-06-12 19:06 -0700
    Re: BEGIN with multiple AGAINs? BruceMcF <agila61@netscape.net> - 2014-06-12 12:36 -0700
      Re: BEGIN with multiple AGAINs? BruceMcF <agila61@netscape.net> - 2014-06-12 19:50 -0700
        Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-06-13 01:02 -0400
          Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-13 04:16 -0400
            Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-06-13 05:22 -0400
              Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-14 00:33 -0400
                Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-06-14 01:15 -0400
                Re: BEGIN with multiple AGAINs? bruce.mcfarling@gmail.com - 2014-06-13 23:45 -0700
                  Re: BEGIN with multiple AGAINs? bruce.mcfarling@gmail.com - 2014-06-14 00:00 -0700
            Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-06-13 05:26 -0400
              Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-14 00:32 -0400
            Re: BEGIN with multiple AGAINs? "Alex McDonald" <blog@rivadpm.com> - 2014-06-13 12:27 +0100
              Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-14 00:35 -0400
                Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-06-14 01:22 -0400
                  Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-15 08:23 -0400
                    Re: BEGIN with multiple AGAINs? BruceMcF <agila61@netscape.net> - 2014-06-15 11:57 -0700
                    Re: BEGIN with multiple AGAINs? "Elizabeth D. Rather" <erather@forth.com> - 2014-06-15 09:13 -1000
                Re: BEGIN with multiple AGAINs? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-06-14 04:32 -0500
                  Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-15 08:23 -0400
                    Re: BEGIN with multiple AGAINs? "Alex McDonald" <blog@rivadpm.com> - 2014-06-15 19:20 +0100
                Re: BEGIN with multiple AGAINs? "Alex McDonald" <blog@rivadpm.com> - 2014-06-14 23:19 +0100
                  Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-15 08:36 -0400
                    Re: BEGIN with multiple AGAINs? "Alex McDonald" <blog@rivadpm.com> - 2014-06-15 19:18 +0100
                      Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-26 18:34 -0400
                        Re: BEGIN with multiple AGAINs? bruce.mcfarling@gmail.com - 2014-06-26 16:04 -0700
                    Re: BEGIN with multiple AGAINs? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-06-15 19:27 +0000
                Re: BEGIN with multiple AGAINs? Mark Wills <markwills1970@gmail.com> - 2014-06-16 01:45 -0700
            Re: BEGIN with multiple AGAINs? BruceMcF <agila61@netscape.net> - 2014-06-13 09:14 -0700
              Re: BEGIN with multiple AGAINs? november.nihal@gmail.com - 2014-06-13 09:44 -0700
              Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-14 00:32 -0400
                Re: BEGIN with multiple AGAINs? bruce.mcfarling@gmail.com - 2014-06-13 23:25 -0700
          Re: BEGIN with multiple AGAINs? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-06-13 03:13 -0500
          Re: BEGIN with multiple AGAINs? BruceMcF <agila61@netscape.net> - 2014-06-13 08:38 -0700
            Re: BEGIN with multiple AGAINs? rickman <gnuarm@gmail.com> - 2014-06-13 13:29 -0400
              Re: BEGIN with multiple AGAINs? BruceMcF <agila61@netscape.net> - 2014-06-13 11:49 -0700
                Re: BEGIN with multiple AGAINs? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-14 00:41 -0400
                  Re: BEGIN with multiple AGAINs? Elizabeth D Rather <erather@forth.com> - 2014-06-13 19:08 -1000
        Re: BEGIN with multiple AGAINs? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2014-06-13 21:27 +0100
    Re: BEGIN with multiple AGAINs? BruceMcF <agila61@netscape.net> - 2014-06-28 14:00 -0700

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#31482

on 13/06/2014 09:15:59, "Rod Pemberton" wrote:
> On Fri, 13 Jun 2014 01:02:40 -0400, rickman <gnuarm@gmail.com> wrote:
>> On 6/12/2014 10:50 PM, BruceMcF wrote:
>>> On Thursday, June 12, 2014 3:36:06 PM UTC-4, BruceMcF wrote:
> 
>>>> CREATE op-sequence ' op-a , ' op-b , ' op-c , ' op-d , ' FALSE ,
>>>>
>>>> : run-machine ( a -- ) \ address of a structure with an op-sequence
>>>>     >R BEGIN
>>>>        R@ REPEAT DUP CELL+ SWAP @ EXECUTE 0= UNTIL DROP
>>>>     AGAIN ;
>>>
>>> Sadly I wasn't drinking when I wrote that ... that is, of course:
>>>
>>> : run-machine ( a -- ) \ address of a structure with an op-sequence
>>>     >R BEGIN
>>>        R@ BEGIN DUP CELL+ SWAP @ EXECUTE 0= UNTIL DROP
>>>     AGAIN ;
>>
>> : run-list ( a -- ) \ address of a structure with an op-sequence
>>      BEGIN DUP @ EXECUTE WHILE CELL+ AGAIN DROP ;
>>
> 
> Isn't it time for a RECURSE LEAVE or EXIT ?
> (untested, probably bad coding style jumping out of an IF ...)
> 
> DUP @ IF EXECUTE CELL+ RECURSE THEN ;
> 

That would require tail-call elimination for RECURSE THEN ; otherwise the
return stack would grow uncontrollably. Neither solution appears to
support >R R@ and R>.

>> I'm assuming 0= UNTIL or WHILE is evaluating the value left by the
>> call to EXECUTE.  Does the inner loop exit when reaching the end of
>> the list?
> 
> No, he was drunk. He meant to test for FALSE after @ before the
> EXECUTE.
> 
> 
> Rod Pemberton
> 

[toc] | [prev] | [next] | [standalone]

#31511

On Fri, 13 Jun 2014 07:27:00 -0400, Alex McDonald <blog@rivadpm.com> wrote:
> on 13/06/2014 09:15:59, "Rod Pemberton" wrote:

>> Isn't it time for a RECURSE LEAVE or EXIT ?
>> (untested, probably bad coding style jumping out of an IF ...)
>>
>> DUP @ IF EXECUTE CELL+ RECURSE THEN ;
>>
>
> That would require tail-call elimination for RECURSE THEN ;
> otherwise the return stack would grow uncontrollably.

Why do you say that?

IF and THEN don't put anything on the return stack, or shouldn't.
AFAIK, only ENTER/DOCOL does save a return stack value.  So, I don't
recognize an inherent flaw in my usage above "that would require
tail-call elimination".  I.e., if your statement is true, it must be
true of all Forths, in general, yes?

So, where does ANS say RECURSE has negative side effects? (stack overflow)

Doesn't your RECURSE DROP the stacked return address from ENTER/DOCOL?
Are you saying that me doing so in mine is incorrect?

This is mine.  It drops the stacked return address for ENTER/DOCOL.
It has no stack overflow.  It will RECURSE forever.  That's the
purpose of RECURSE, correct?  IMO, there is no point in using RECURSE
to nest repeatedly, say for a large sort or recursive algorithm, just
to overflow the return stack, especially when that is something fixable.
So, what's wrong with it, i.e., my (non-stack overflow) RECURSE ?

: RECURSE COMPILE R> COMPILE DROP LATESTXT @ +ofsCFA , ; IMMEDIATE

The XT is the start of my dictionary header which is not the
CFA hence +ofsCFA.  So, RECURSE compiles R> DROP and the XT of
the current word.

As you pointed out, if RECURSE does *NOT* DROP the stacked XT,
then you get a stack overflow.  AIUI, this should be true for all
Forths, whether interpreted or compiled, with or without an IF THEN,
i.e., not specifically due to my use above in the untested and
non-working example.

IMO, RECURSE is _useless_ if it doesn't DROP the ENTER/DOCOL return
stack address.  It will overflow, eventually, depending on stack size.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#31517

On 6/14/2014 12:35 AM, Rod Pemberton wrote:
> On Fri, 13 Jun 2014 07:27:00 -0400, Alex McDonald <blog@rivadpm.com> wrote:
>> on 13/06/2014 09:15:59, "Rod Pemberton" wrote:
>
>>> Isn't it time for a RECURSE LEAVE or EXIT ?
>>> (untested, probably bad coding style jumping out of an IF ...)
>>>
>>> DUP @ IF EXECUTE CELL+ RECURSE THEN ;
>>>
>>
>> That would require tail-call elimination for RECURSE THEN ;
>> otherwise the return stack would grow uncontrollably.
>
> Why do you say that?
>
> IF and THEN don't put anything on the return stack, or shouldn't.

RECURSE is a call so it pushes an address onto the return stack.  Do you 
really not know that?  That is why he says it should use tail call 
recursion to make it into a jump instead.


> Doesn't your RECURSE DROP the stacked return address from ENTER/DOCOL?
> Are you saying that me doing so in mine is incorrect?
>
> This is mine.  It drops the stacked return address for ENTER/DOCOL.
> It has no stack overflow.  It will RECURSE forever.  That's the
> purpose of RECURSE, correct?  IMO, there is no point in using RECURSE
> to nest repeatedly, say for a large sort or recursive algorithm, just
> to overflow the return stack, especially when that is something fixable.
> So, what's wrong with it, i.e., my (non-stack overflow) RECURSE ?
>
> : RECURSE COMPILE R> COMPILE DROP LATESTXT @ +ofsCFA , ; IMMEDIATE
>
> The XT is the start of my dictionary header which is not the
> CFA hence +ofsCFA.  So, RECURSE compiles R> DROP and the XT of
> the current word.
>
> As you pointed out, if RECURSE does *NOT* DROP the stacked XT,
> then you get a stack overflow.  AIUI, this should be true for all
> Forths, whether interpreted or compiled, with or without an IF THEN,
> i.e., not specifically due to my use above in the untested and
> non-working example.
>
> IMO, RECURSE is _useless_ if it doesn't DROP the ENTER/DOCOL return
> stack address.  It will overflow, eventually, depending on stack size.

If RECURSE drops the value normally pushed onto the return stack then 
you would only be able to use it at the *END* of a word.  What if the 
use was in the middle?

: EXAMPLE earlystuff  IF RECURSE THEN laststuff ;

I can't believe you are really discussing this.  In any other language 
RECURSE would just be a call to the routine being compiled.  If it is 
not treated in a similar manner in Forth it becomes very difficult to use.

-- 

Rick

[toc] | [prev] | [next] | [standalone]

#31551

On Sat, 14 Jun 2014 01:22:22 -0400, rickman <gnuarm@gmail.com> wrote:
> On 6/14/2014 12:35 AM, Rod Pemberton wrote:
>> On Fri, 13 Jun 2014 07:27:00 -0400, Alex McDonald <blog@rivadpm.com>  
>> wrote:
>>> on 13/06/2014 09:15:59, "Rod Pemberton" wrote:

>>>> Isn't it time for a RECURSE LEAVE or EXIT ?
>>>> (untested, probably bad coding style jumping out of an IF ...)
>>>>
>>>> DUP @ IF EXECUTE CELL+ RECURSE THEN ;
>>>>
>>>
>>> That would require tail-call elimination for RECURSE THEN ;
>>> otherwise the return stack would grow uncontrollably.
>>
>> Why do you say that?
>>
>> IF and THEN don't put anything on the return stack, or shouldn't.
>
> RECURSE is a call so it pushes an address onto the return stack.

If you had read my post definition of RECURSE, you'd know or suspect
you didn't need to state that.

> Do you really not know that?

I do know that.  In fact, I said so.  It was the line that followed
the one above, which you snipped.  It's still the second line here:

RP> IF and THEN don't put anything on the return stack, or shouldn't.
RP> AFAIK, only ENTER/DOCOL does save a return stack value.

ENTER (or DOCOL) is what "pushes an address onto the return stack",
not RECURSE.  ENTER (or DOCOL) is what is stored in the CFA that
allows nesting of all high-level Forth words in an ITC Forth.

> That is why he says it should use tail call recursion to make
> it into a jump instead.

He said the return stack would grow uncontrollably here,
which it does with a (correctly) implemented RECURSE.

He responded afterwards by saying Andrew's example was correct,
but it demonstrates the exact same issue for the exact same
reason: RECURSE can overflow the return stack.

So, I see no bearing of your explanation here as to the issue at hand,
since his statement makes no sense.  The issue he cited is with Forth's
existing RECURSE, not my use of RECURSE, nor my incorrectly implemented
version of it.

>> IMO, RECURSE is _useless_ if it doesn't DROP the ENTER/DOCOL return
>> stack address.  It will overflow, eventually, depending on stack size.
>
> If RECURSE drops the value normally pushed onto the return stack then  
> you would only be able to use it at the *END* of a word.  What if the  
> use was in the middle?
>
> : EXAMPLE earlystuff  IF RECURSE THEN laststuff ;
>

Mine doesn't work there.  No, I hadn't re-tested it in a while.

> I can't believe you are really discussing this.

Well, you can go back to the non-Forth microprocessor threads, if you
don't like this one.  No one is forcing you to respond to me.

But, I think the issue of overflowing a stack with recursion isn't
inconsequential.  It's a serious hazard.

> In any other language RECURSE would just be a call to the routine
> being compiled.

It just seemed really flawed to me to allow a RECURSE that can't
actually RECURSE, i.e., call the same word forever.  In fact,
I added (and removed) the R> DROP to the definition multiple times.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#31560

On Sunday, June 15, 2014 8:23:31 AM UTC-4, Rod Pemberton wrote:
> It just seemed really flawed to me to allow a RECURSE that can't 
> actually RECURSE, i.e., call the same word forever.  In fact,
> I added (and removed) the R> DROP to the definition multiple times.

Except RECURSE having the ability to "call the same word forever" has ALWAYS been a special case of tail-call recursion. Real world recursion that is not tail-call recursion has NEVER been able to call the same word forever, since it always has to save the return from call information somewhere.

If you have word that branches to the word it is located in, rather than calling the word as specified in the ANS Standard, then it can only be used to provide the ANS Forth RECURSE in the tail-call case, when it is at the end of the definition immediately preceding exit. The only obvious word that can be allowed to follow it in a definition is THEN as THEN simply resolves a branch and does not compile any additional process itself.

RECURSE is defined to: "Append the execution semantics of the current definition to the current definition."

You seem to be hung up on the fact that the definition does not explicitly denote the usage of return stack space when performing the execution semantics appended by RECURSE ... but as will be obvious to people competent to read the standard with an eye to implementing an ANS Standard Forth, RECURSE is an IMMEDIATE word, and it does not consume that return stack space when it executes, that return stack space is consumed when the execution semantics it has appended to the word have been performed. It would therefore be false to specify any return stack usage in the RECURSE definition beyond that implied by the semantics that occur when the word executes its own execution semantics.

In an implementation where the name_field address of the current word is held in a variable LATEST and the general factor for going from name_field address to xt for a compiled definition is NT>XT then a definition of RECURSE may be:

: RECURSE ( -- ) LATEST @ NT>XT COMPILE, ; IMMEDIATE COMPILE-ONLY

[toc] | [prev] | [next] | [standalone]

#31563

On 6/15/14 2:23 AM, Rod Pemberton wrote:
> But, I think the issue of overflowing a stack with recursion isn't
> inconsequential.  It's a serious hazard.
>
>> In any other language RECURSE would just be a call to the routine
>> being compiled.
>
> It just seemed really flawed to me to allow a RECURSE that can't
> actually RECURSE, i.e., call the same word forever.  In fact,
> I added (and removed) the R> DROP to the definition multiple times.

The thing is, as others have pointed out, RECURSE isn't intended to be a 
substitute form of loop. If you want to loop forever, BEGIN ... AGAIN is 
the appropriate structure.

RECURSE is intended to repeat over some finite set of conditions. The 
first instance I can remember (long ago) was a recursive graphic area 
fill that Chuck wrote. An area to be filled is not infinite, it has 
boundaries. It was necessary to configure that system with an unusually 
large return stack *and* data stack, since data was also added in every 
pass. The process eventually unwound leaving stacks as they were when 
the FILL word was called, and the area filled.

Other uses I have seen are similar.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#31524

Rod Pemberton <dont_use_email@xnothavet.cqm> wrote:
> On Fri, 13 Jun 2014 07:27:00 -0400, Alex McDonald <blog@rivadpm.com> wrote:
>> on 13/06/2014 09:15:59, "Rod Pemberton" wrote:
>
>>> Isn't it time for a RECURSE LEAVE or EXIT ?
>>> (untested, probably bad coding style jumping out of an IF ...)
>>>
>>> DUP @ IF EXECUTE CELL+ RECURSE THEN ;
>>>
>>
>> That would require tail-call elimination for RECURSE THEN ;
>> otherwise the return stack would grow uncontrollably.
>
> Why do you say that?
>
> IF and THEN don't put anything on the return stack, or shouldn't.
> AFAIK, only ENTER/DOCOL does save a return stack value.  So, I don't
> recognize an inherent flaw in my usage above "that would require
> tail-call elimination".  I.e., if your statement is true, it must be
> true of all Forths, in general, yes?
>
> So, where does ANS say RECURSE has negative side effects? (stack overflow)
>
> Doesn't your RECURSE DROP the stacked return address from ENTER/DOCOL?
> Are you saying that me doing so in mine is incorrect?

Try this:

: factorial   ?dup 0= if 1  else dup 1- recurse *  then ;  ok
5 factorial . 120  ok

Andrew.

[toc] | [prev] | [next] | [standalone]

#31552

On Sat, 14 Jun 2014 05:32:08 -0400, Andrew Haley  
<andrew29@littlepinkcloud.invalid> wrote:

> Try this:
>
> : factorial   ?dup 0= if 1  else dup 1- recurse *  then ;  ok
> 5 factorial . 120  ok
>

So, Forth requires that RECURSE be broken, i.e., potentially overflows.

I should've guessed that any attempt I made to fix Forth, i.e., make
it safer and more useful would be a waste of my time.  Not be able
to call the same word forever with RECURSE definately eliminates most,
if not all, of it's serious use, IMO.  It's difficult to control the
level to which a recursive word will nest.  It's very likely to
overflow many of the situations where one would use it, such as
sorting, and even your example above with a sufficiently large value.

Eventually, I would've noticed that my RECURSE didn't work correctly,
since it doesn't pass my own test for it, and the R> DROP probably
causes Hayes core to fail too.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#31559

on 15/06/2014 13:23:48, "Rod Pemberton" wrote:
> On Sat, 14 Jun 2014 05:32:08 -0400, Andrew Haley
> <andrew29@littlepinkcloud.invalid> wrote:
> 
>> Try this:
>>
>> : factorial   ?dup 0= if 1  else dup 1- recurse *  then ;  ok
>> 5 factorial . 120  ok
>>
> 
> So, Forth requires that RECURSE be broken, i.e., potentially
> overflows.

Recursion requires that there be a way to recurse. Recursion is not
looping, for which there are other language constructs.

[toc] | [prev] | [next] | [standalone]

#31546

on 14/06/2014 05:35:57, "Rod Pemberton" wrote:
> On Fri, 13 Jun 2014 07:27:00 -0400, Alex McDonald <blog@rivadpm.com>
> > wrote:
>> on 13/06/2014 09:15:59, "Rod Pemberton" wrote:
> wrote:
> 
>>> Isn't it time for a RECURSE LEAVE or EXIT ?
>>> (untested, probably bad coding style jumping out of an IF ...)
>>>
>>> DUP @ IF EXECUTE CELL+ RECURSE THEN ;
>>>
>>
>> That would require tail-call elimination for RECURSE THEN ;
>> otherwise the return stack would grow uncontrollably.
> 
> Why do you say that?
> 
> IF and THEN don't put anything on the return stack, or shouldn't.
> AFAIK, only ENTER/DOCOL does save a return stack value.  So, I don't
> recognize an inherent flaw in my usage above "that would require
> tail-call elimination".  I.e., if your statement is true, it must be
> true of all Forths, in general, yes?
> 
> So, where does ANS say RECURSE has negative side effects? (stack
> overflow)
> 
> Doesn't your RECURSE DROP the stacked return address from ENTER/DOCOL?
> Are you saying that me doing so in mine is incorrect?
> 
> This is mine.  It drops the stacked return address for ENTER/DOCOL.
> It has no stack overflow.  It will RECURSE forever.  That's the
> purpose of RECURSE, correct?  IMO, there is no point in using RECURSE
> to nest repeatedly, say for a large sort or recursive algorithm, just
> to overflow the return stack, especially when that is something
> fixable. So, what's wrong with it, i.e., my (non-stack overflow)
> RECURSE ?
> 
>: RECURSE COMPILE R> COMPILE DROP LATESTXT @ +ofsCFA , ; IMMEDIATE
> 
> The XT is the start of my dictionary header which is not the
> CFA hence +ofsCFA.  So, RECURSE compiles R> DROP and the XT of
> the current word.
> 
> As you pointed out, if RECURSE does *NOT* DROP the stacked XT,
> then you get a stack overflow.  AIUI, this should be true for all
> Forths, whether interpreted or compiled, with or without an IF THEN,
> i.e., not specifically due to my use above in the untested and
> non-working example.
> 
> IMO, RECURSE is _useless_ if it doesn't DROP the ENTER/DOCOL return
> stack address. It will overflow, eventually, depending on stack size.
> 

Andrew's factorial example demonstrates why having a jump rather than a
call is not correct. In general, a recursive call can only be eliminated
and replaced with a jump if it is followed by an immediate exit without
side effects.


> 
> Rod Pemberton
> 

[toc] | [prev] | [next] | [standalone]

#31553

On Sat, 14 Jun 2014 18:19:21 -0400, Alex McDonald <blog@rivadpm.com> wrote:

> Andrew's factorial example demonstrates why having a jump rather
> than a call is not correct.

What!

Andrew's example has the *exact* same issue with RECURSE for which
you cited me for.  If you use a large factorial value in his example,
RECURSE will overflow the stack with numbers to be multiplied long
before the multiplication of the values can occur.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#31558

on 15/06/2014 13:36:11, "Rod Pemberton" wrote:
> On Sat, 14 Jun 2014 18:19:21 -0400, Alex McDonald <blog@rivadpm.com>
> wrote:
> 
>> Andrew's factorial example demonstrates why having a jump rather
>> than a call is not correct.
> 
> What!

Tail-call elimination turns a call into a jump.

> 
> Andrew's example has the *exact* same issue with RECURSE for which
> you cited me for.  If you use a large factorial value in his example,
> RECURSE will overflow the stack with numbers to be multiplied long
> before the multiplication of the values can occur.
> 

No, I cited you for stack overflow unless it was possible to eliminate
the tail-call. You were offering RECURSE as an alternative to BEGIN ...
AGAIN, which does not have the problem. Andrew was demonstrating that
your implementation of RECURSE was broken.

> 
> Rod Pemberton
> 

[toc] | [prev] | [next] | [standalone]

#31902

On Sun, 15 Jun 2014 14:18:20 -0400, Alex McDonald <blog@rivadpm.com> wrote:
> on 15/06/2014 13:36:11, "Rod Pemberton" wrote:
>> On Sat, 14 Jun 2014 18:19:21 -0400, Alex McDonald <blog@rivadpm.com>
>> wrote:

>>> Andrew's factorial example demonstrates why having a jump rather
>>> than a call is not correct.
>>
>> What!
>
> Tail-call elimination turns a call into a jump.
>>
>> Andrew's example has the *exact* same issue with RECURSE for which
>> you cited me for.  If you use a large factorial value in his example,
>> RECURSE will overflow the stack with numbers to be multiplied long
>> before the multiplication of the values can occur.
>>
>
> No, I cited you for stack overflow unless it was possible to eliminate
> the tail-call. You were offering RECURSE as an alternative to BEGIN ...
> AGAIN, which does not have the problem.

... "the problem" ...

Which problem?

1) the problem with my incorrectly implemented RECURSE looping forever?
2) the problem of stack overflow when using any correctly implemented
RECURSE instead of BEGIN ... AGAIN ?

> Andrew was demonstrating that your implementation of RECURSE was broken.

You still haven't clarified if your "[citing me] for stack overflow unless
it was possible to eliminate the tail-call" was a result of:

1) using a correctly implemented RECURSE
2) using a broken RECURSE

I.e., it appears to me, that you cited me for the effects which occur
when using a correctly implemented RECURSE, but touted Andrew's example
as being correct which fails the exact same way when using a correctly
implemented RECURSE: return stack growth from recursion.

AM> "That would require tail-call elimination for RECURSE THEN ;
AM> otherwise the return stack would grow uncontrollably."

That's what happens with a correctly implemented RECURSE.  It's what  
happens
in Andrew's example too.  Why am I being cited for it?

It's not what happens with my (former) incorrectly implemented RECURSE.
That removes the stacked return address, so the return stack didn't grow
any.  I.e., it doesn't fail by having "the return stack grow  
uncontrollably,"
yet, is is incorrectly implemented.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#31909

On Thursday, June 26, 2014 6:34:47 PM UTC-4, Rod Pemberton wrote:
> It's not what happens with my (former) incorrectly implemented RECURSE. 
> That removes the stacked return address, so the return stack didn't grow
> any.  I.e., it doesn't fail by having "the return stack grow uncontrollably,"

> yet, is is incorrectly implemented.

Precisely, because it fails by failing to perform recursion. It solves the problem that any general purpose recursive call encounters when it is used incorrectly by refusing to perform a recursive call.

The only recursive call that is not required to store its return information somewhere is a tail recursive call, which returns only to exit from the calling routine, making the return to the calling routine redundant.

So all you have to do is to re-specify your broken definition of a general-purpose recursive call to be a tail recursive call, only use it where tail recursion is appropriate, and then instead of being a broken general recursion word, its an efficient tail-recursion word. EG, ``EXIT>SELF''.

[toc] | [prev] | [next] | [standalone]

#31564

In article <op.xhhxaogj6zenlw@localhost>,
Rod Pemberton <dont_use_email@xnothavet.cqm> wrote:
>On Sat, 14 Jun 2014 18:19:21 -0400, Alex McDonald <blog@rivadpm.com> wrote:
>
>> Andrew's factorial example demonstrates why having a jump rather
>> than a call is not correct.
>
>What!
>
>Andrew's example has the *exact* same issue with RECURSE for which
>you cited me for.  If you use a large factorial value in his example,
>RECURSE will overflow the stack with numbers to be multiplied long
>before the multiplication of the values can occur.

Let's see how many stack entries are needed for faculties.
I have 64k for the terminal input and the return stack in my Forth.
So I can have a maximum of about 8000 32 bit return values.
(Leaving  32 kbyte available for buffering one line.)

lina64be -e

AMDX86 ciforth beta $RCSfile: ci86.gnr,v $ $Revision: 5.112 $
...
 OK
WANT -scripting-
 OK
1 8000 1 DO I . I * DUP . DUP 0< IF LEAVE THEN CR LOOP
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
21 -4249290049419214848  OK


Then there is gforth with options to reserve a stupendous
size for the return stack.

>
>
>Rod Pemberton
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#31587

On Saturday, 14 June 2014 05:35:55 UTC+1, Rod Pemberton  wrote:
> Doesn't your RECURSE DROP the stacked return address from 
> ENTER/DOCOL?

Of course. That wouldn't be recursion. 
> 
> Are you saying that me doing so in mine is incorrect?
> 
Yep! (Sorry!)
> 
> This is mine.  It drops the stacked return address for 
> ENTER/DOCOL.
> 

It shouldn't do that. 

> It has no stack overflow.  It will RECURSE forever.  That's the
> purpose of RECURSE, correct?  

No. Incorrect.

Consider:

: thang  a b if recurse then c d ;

In your version of RECURSE c and d would never be executed.
That ain't recursion. It's a branch! You need to retain the return
stack frame so that execution can eventually resume with c and d.

> 
> : RECURSE COMPILE R> COMPILE DROP LATESTXT @ +ofsCFA , ; IMMEDIATE
> 
: RECURSE ( -- ) LATEST @ >CFA , ; IMMEDIATE

> 
> As you pointed out, if RECURSE does *NOT* DROP the stacked XT,
> then you get a stack overflow.  
> 
It certainly is possible, yes. But only if your nesting goes too
deep. In which case you need to find another way of doing it, or
perhaps make the return stack deeper by moving it somewhere else.
Possible to do in most Forth systems.

> 
> IMO, RECURSE is _useless_ if it doesn't DROP the ENTER/DOCOL return
> stack address.  It will overflow, eventually, depending on stack size.
> 
IMO a RECURSE that does not return is not recursion. It's an 
incorrectly named branch.

[toc] | [prev] | [next] | [standalone]

#31489

On Friday, June 13, 2014 4:16:03 AM UTC-4, Rod Pemberton wrote:
> Isn't it time for a RECURSE LEAVE or EXIT ? 
>   (untested, probably bad coding style jumping out of an IF ...)

>   DUP @ IF EXECUTE CELL+ RECURSE THEN ;

    Note that this doesn't work with the structure as defined, which is terminated by an xt of FALSE, so it would be:

>   DUP @ EXECUTE IF CELL+ RECURSE THEN ;

   ... and the IF ... RECURSE THEN would be a fairly silly definition in any event, consuming levels of the return stack for no gain in simplicity or code space. Even sillier in this context since, for at least one FISH target, there is only 4K RAM total, and so there could well be a much more parsimonious return stack than desktop oriented people like myself are accustomed to, making the recurse version less re-usable than the BEGIN...UNTIL version or the BEGIN...WHILE...REPEAT version.

>> I'm assuming 0= UNTIL or WHILE is evaluating the value left by the 
>> call to EXECUTE.  Does the inner loop exit when reaching the end of 
>> the list? 

> No, he was drunk.  He meant to test for FALSE after @ before the EXECUTE.

You'll note that that the state machine structure is terminated with the xt for FALSE, so its null-return terminated rather than null terminated.

If you'd been paying closer attention, you'd also have caught that I was saying I was NOT drunk, but that if I was it would have been a clearer reason for writing ``REPEAT ... UNTIL'' instead of ``BEGIN ... UNTIL''.

[toc] | [prev] | [next] | [standalone]

#31490

( ----------------------------------------------------- )

: test1 ( -- flg ) ." a " 9 random 7 > if true else false then ;
: test2 ( -- flg ) ." b " 9 random 7 > if true else false then ;
: test3 ( -- flg ) ." c " 9 random 7 > if true else false then ;
: test4 ( -- flg ) ." d " 9 random 7 > if true else false then ;
: test5 ( -- flg ) ." e " 9 random 7 > if true else false then ;

: test6
	test1 if abort else
	test2 if abort else
	test3 if abort else
	test4 if abort else
	test5 if abort
	then then then then then
	;

: test7
	begin
		['] test6 catch if ." *** Caught"  cr then
	again ;

( ----------------------------------------------------- )

Create  op-seq{
	      0 , ( this holds the index to be performed )
	' test1 ,
	' test2 ,
	' test3 ,
	' test4 ,
	' test5 ,


: } cells + ;

: test8
	1 op-seq{ 0 } ! ( initialise)
	begin
		op-seq{ op-seq{ 0 } @ } @ execute if
			." *** Caught" cr
			1 op-seq{ 0 } !
		else
			op-seq{ 0 } @ 1+ dup 5 > if drop 1 then op-seq{ 0 } !
		then
	again ;

( ----------------------------------------------------- )


1. If you change the "abort" to a 'n throw' you can identify the point at which it failed. I know the original poster didn't ask this but I thought it might be useful.I wanted to see it fail and repeat but you can take the "caught message" out and hopefully it does what you want. 

2. test7 or test8 to see it working, but you will have to close the screen/window/process to exit as its a begin..again loop.

[toc] | [prev] | [next] | [standalone]

#31508

On Fri, 13 Jun 2014 12:14:13 -0400, BruceMcF <agila61@netscape.net> wrote:

> You'll note that that the state machine structure is terminated with the  
> xt for FALSE, so its null-return terminated rather than null terminated.
>

What if an EXECUTEd XT doesn't return a status flag?  I'd expect to be
able to use DUP or SWAP or other words without having to redefine them
to return a status flag.  Isn't it a presumption on your part that a
user won't use words not defined to return a status flag?  I.e., wouldn't
the safe design be to *NOT* check for a condition after EXECUTE, but
*TO* check for the end-of-list prior to EXECUTE ?

> If you'd been paying closer attention, [...]

True, I did misread that.  I had your drinking states reversed.

> [...] you'd also have caught that I was saying I was NOT drunk, [...]

No, you still said you were drinking, perhaps not drunk.  Maybe, you
need to reread it too.  What you actually said was this:

BF> [ not drinking - incorrect ]
BF>
BF> Sadly I wasn't drinking when I wrote that ...
BF>
BF> [ drinking now - corrected ]


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#31520

On Saturday, June 14, 2014 12:32:07 AM UTC-4, Rod Pemberton wrote:
> No, you still said you were drinking, perhaps not drunk.
>  Maybe, you need to reread it too.  What you actually said
> was this:
 
> BF> [ not drinking - incorrect ] 
> BF>
> BF> Sadly I wasn't drinking when I wrote that ...
> BF>
> BF> [ drinking now - corrected ]

Saying I wasn't drinking at Time A says absolutely nothing about whether or not I drank after Time A. You are inferring beyond the scope of the information at hand.

[toc] | [prev] | [next] | [standalone]

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

Back to top | Article view | comp.lang.forth

csiph-web