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

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

Recognizers & EVALUATE recursion

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

Contents

  Recognizers & EVALUATE recursion Alex <alex@rivadpm.com> - 2017-04-07 14:59 +0100
    Re: Recognizers & EVALUATE recursion Matthias Trute <matthias.trute@gmail.com> - 2017-04-07 08:12 -0700
      Re: Recognizers & EVALUATE recursion Alex <alex@rivadpm.com> - 2017-04-09 22:39 +0100
    Re: Recognizers & EVALUATE recursion anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-04-08 14:17 +0000
      Re: Recognizers & EVALUATE recursion Alex <alex@rivadpm.com> - 2017-04-09 22:37 +0100

#56811 — Recognizers & EVALUATE recursion

Using EVALUATE or allowing an implicit use of EVALUATE in the execution 
path of a recognizer may cause problems. In my Forth (edited for clarity):

: interpreter ( -- )
     begin parse-name dup
     while default-recognize execute
     repeat 2drop ;

: evaluate ( addr len -- )
     ['] interpreter execute-parsing ;

A recognizer using EVALUATE re-drives the interpreter, and hence the 
recognizer is potentially recursed into.

Not every parse will cause issues, but there are certain pathological 
cases where the recogniser may infinitely recurse. In my case it was an 
EVALUATE for :NAME causing an EVALUATE for :NAME ... and so on.

-- 
Alex

[toc] | [next] | [standalone]

#56812

> A recognizer using EVALUATE re-drives the interpreter, and hence the 
> recognizer is potentially recursed into.

I cannot see a problem here. All relevant data is passed to/from
the recognizing modules via the stack and all other actions like
writing to the dictionary or performing XT actions happen at other
places.

> Not every parse will cause issues, but there are certain pathological 
> cases where the recogniser may infinitely recurse. In my case it was an 
> EVALUATE for :NAME causing an EVALUATE for :NAME ... and so on.

If I may offer a guess, it looks like execute-parsing has a bug with
the SOURCE and >IN handling. My execute-parsing is the following

\ execute-parsing
\ ( addr len XT -- )
\ execute XT with addr/len as SOURCE
\

variable xp-addr
variable xp-len

: xp-source xp-addr @ xp-len @ ;

: execute-parsing ( addr len XT -- )
  xp-addr @ xp-len @ 2>r \ make it nestable 
  >r                     \ save XT temporarily
  xp-len ! xp-addr !     \ prepare new source
  r>                     \ get back the XT
  ['] source defer@ >in @ 2>r \ save and switch source
  ['] xp-source is SOURCE
  0 >IN !
  catch      \ DO IT
  2r> >in ! is source    \ restore old source
  2r> xp-len ! xp-addr ! \ restore nested information
  throw                  \ re-throw exception, if any
;

(SOURCE being a deferred word in the USER area), nestable but
not suitable for multitasking due to the variables (should
be USER's as well). Good enough for me.

Matthias

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

#56949

On 4/7/2017 16:12, Matthias Trute wrote:
>> A recognizer using EVALUATE re-drives the interpreter, and hence the
>> recognizer is potentially recursed into.
> 
> I cannot see a problem here. All relevant data is passed to/from
> the recognizing modules via the stack and all other actions like
> writing to the dictionary or performing XT actions happen at other
> places.
> 
>> Not every parse will cause issues, but there are certain pathological
>> cases where the recogniser may infinitely recurse. In my case it was an
>> EVALUATE for :NAME causing an EVALUATE for :NAME ... and so on.
> 
> If I may offer a guess, it looks like execute-parsing has a bug with
> the SOURCE and >IN handling. My execute-parsing is the following

Mine is OK and works correctly. I should have said that debugging 
recursion is potentially difficult, and it took me some time to identify 
EVALUATE as the culprit.

-- 
Alex

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

#56864

Alex <alex@rivadpm.com> writes:
>Using EVALUATE or allowing an implicit use of EVALUATE in the execution 
>path of a recognizer may cause problems. In my Forth (edited for clarity):
>
>: interpreter ( -- )
>     begin parse-name dup
>     while default-recognize execute
>     repeat 2drop ;
>
>: evaluate ( addr len -- )
>     ['] interpreter execute-parsing ;
>
>A recognizer using EVALUATE re-drives the interpreter, and hence the 
>recognizer is potentially recursed into.
>
>Not every parse will cause issues, but there are certain pathological 
>cases where the recogniser may infinitely recurse. In my case it was an 
>EVALUATE for :NAME causing an EVALUATE for :NAME ... and so on.

Recursion is just like loops: You have to make at least a little bit
of progress before recursing, or you will get an endless recursion (at
least with recursion that usually shows up as a return stack overflow
rather than just a hanging program).

In general EVALUATE looks like a much too coarse tool for the
implementation of a recognizer: it can do many things out of your
control, based on stuff like STATE, BASE, the search order, and the
contents of the individual wordlists.  A slightly less coarse approach
is to call the recognizer stack again (at least STATE should not
influence that), but of course the issue of requiring progress
remains.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

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

#56948

On 4/8/2017 15:17, Anton Ertl wrote:
> Alex <alex@rivadpm.com> writes:
>> Using EVALUATE or allowing an implicit use of EVALUATE in the
>> execution path of a recognizer may cause problems. In my Forth
>> (edited for clarity):
>> 
>> : interpreter ( -- ) begin parse-name dup while default-recognize
>> execute repeat 2drop ;
>> 
>> : evaluate ( addr len -- ) ['] interpreter execute-parsing ;
>> 
>> A recognizer using EVALUATE re-drives the interpreter, and hence
>> the recognizer is potentially recursed into.
>> 
>> Not every parse will cause issues, but there are certain
>> pathological cases where the recogniser may infinitely recurse. In
>> my case it was an EVALUATE for :NAME causing an EVALUATE for :NAME
>> ... and so on.
> 
> Recursion is just like loops: You have to make at least a little bit 
> of progress before recursing, or you will get an endless recursion
> (at least with recursion that usually shows up as a return stack
> overflow rather than just a hanging program).

Yes. I documented this because it initially caught me by surprise, and
stack overflow is pretty disastrous in outcome & difficult to debug in
my system. It took a little while to realize that EVALUATE was the culprit.

> 
> In general EVALUATE looks like a much too coarse tool for the 
> implementation of a recognizer: it can do many things out of your 
> control, based on stuff like STATE, BASE, the search order, and the 
> contents of the individual wordlists.

They are known and in the user's control, since the evaluation is being 
done while the word is being recognized, not later.

> A slightly less coarse approach is to call the recognizer stack again
> (at least STATE should not influence that), but of course the issue
> of requiring progress remains.

The intent is to explore the feasibility of words of the form ([ ] is 
meta) w1:[w2[:w3]].p as object w1 [with public object w2 [etc]] 
supporting public symbol p.

-- 
Alex

[toc] | [prev] | [standalone]

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

csiph-web