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

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

Re: RfD Recognizer, 3rd version

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

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: RfD Recognizer, 3rd version trans <transfire@gmail.com> - 2016-09-26 20:33 -0700
    Re: RfD Recognizer, 3rd version Paul Rubin <no.email@nospam.invalid> - 2016-09-26 21:39 -0700
      Re: RfD Recognizer, 3rd version tabcomputing@gmail.com - 2016-09-26 22:45 -0700
        Re: RfD Recognizer, 3rd version Paul Rubin <no.email@nospam.invalid> - 2016-09-26 22:55 -0700
          Re: RfD Recognizer, 3rd version Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-09-27 03:38 -0500
            Re: RfD Recognizer, 3rd version anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-27 12:42 +0000
            Re: RfD Recognizer, 3rd version Bernd Paysan <bernd@net2o.de> - 2016-09-27 13:23 +0000
            Re: RfD Recognizer, 3rd version trans <transfire@gmail.com> - 2016-09-27 19:09 -0700
              Re: RfD Recognizer, 3rd version JennyB <jennybrien@googlemail.com> - 2016-09-28 00:07 -0700
                Re: RfD Recognizer, 3rd version anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-30 12:34 +0000
              Re: RfD Recognizer, 3rd version albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-28 10:03 +0200
                Re: RfD Recognizer, 3rd version ruvim.pinka@gmail.com - 2016-09-28 02:39 -0700
                  Re: RfD Recognizer, 3rd version albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-28 13:22 +0200
              Re: RfD Recognizer, 3rd version anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-09-28 11:41 +0000
        Re: RfD Recognizer, 3rd version albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-09-27 15:15 +0200

#51353 — Re: RfD Recognizer, 3rd version

Could someone explain how recognizers work in laymen terms?

[toc] | [next] | [standalone]

#51356

trans <transfire@gmail.com> writes:
> Could someone explain how recognizers work in laymen terms?

After parsing a word, pass it to a series of user-supplied functions
(plus some default ones) until one of them decides that it knows how to
handle the word.  This contrasts with the traditional system of having
special hair built into the text interpreter to handle things like
numeric literals, char constants in 'x' notation, etc.

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

#51359

On Tuesday, September 27, 2016 at 12:39:46 AM UTC-4, Paul Rubin wrote:
> trans <transfire@gmail.com> writes:
> > Could someone explain how recognizers work in laymen terms?
> 
> After parsing a word, pass it to a series of user-supplied functions
> (plus some default ones) until one of them decides that it knows how to
> handle the word.  This contrasts with the traditional system of having
> special hair built into the text interpreter to handle things like
> numeric literals, char constants in 'x' notation, etc.

Thanks, that helps. So it still goes word by word. But isn't that going to be rather slow? Every word has to run thru 1 to N functions to find a match, usually N. And the what does it do when it finds a match? Does it put words on the stack? e.g. does `"foo` => `s" foo`? Or I guess actually it just process it as if it were `"s foo`?

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

#51360

tabcomputing@gmail.com writes:
> Thanks, that helps. So it still goes word by word. But isn't that
> going to be rather slow? Every word has to run thru 1 to N functions
> to find a match, usually N. 

Usually 1.  The first thing is look up the word in the dictionary.  If
not, see if it's an integer literal, etc.  That's what the text
interpreter does now.

> And the what does it do when it finds a match?

It runs a user-supplied function.  You could read the spec.  Disclosure:
I've looked at the spec but not really studied it yet, so I don't
understand all of it.

See: http://amforth.sourceforge.net/Recognizers.html

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

#51366

Paul Rubin <no.email@nospam.invalid> wrote:
> tabcomputing@gmail.com writes:
>> Thanks, that helps. So it still goes word by word. But isn't that
>> going to be rather slow? Every word has to run thru 1 to N functions
>> to find a match, usually N. 
> 
> Usually 1.  The first thing is look up the word in the dictionary.  If
> not, see if it's an integer literal, etc.  That's what the text
> interpreter does now.

I think the proposal is to allow recognizers to be run before
dictionary search.  The dictionary search itself can be a recognizer,
and can appear anywhere in the recognizer stack.

Andrew.

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

#51381

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Paul Rubin <no.email@nospam.invalid> wrote:
>> tabcomputing@gmail.com writes:
>>> Thanks, that helps. So it still goes word by word. But isn't that
>>> going to be rather slow? Every word has to run thru 1 to N functions
>>> to find a match, usually N. 
>> 
>> Usually 1.  The first thing is look up the word in the dictionary.  If
>> not, see if it's an integer literal, etc.  That's what the text
>> interpreter does now.
>
>I think the proposal is to allow recognizers to be run before
>dictionary search.

What is allowed does not mean that it usually happens.  The usual case
is that the recognizer for dictionary search is first, numbers second,
floats third, etc.  If you use the usual recognizers and the usual
order, you will run as many recognizers as you run now.

If you add a "->value" recognizer at the end, and have a lot of
occurences of "->value" in your code, you will see more recognizers
being tried, on average, than now.  I don't expect that to be a
performance issue, but if you really need to get the last drop of
performance out of text interpretation, you can reorder
non-conflicting recognizers (e.g., "->value" does not conflict with
the number recognizer for BASEs in the standard range) in the order
that produces the best performance (based on how often the recognizers
match and how fast they fail).

- 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]

#51383

Am Tue, 27 Sep 2016 03:38:37 -0500 schrieb Andrew Haley:
> I think the proposal is to allow recognizers to be run before dictionary
> search.  The dictionary search itself can be a recognizer,
> and can appear anywhere in the recognizer stack.

Yes, of course users can change the default recognizer stack to fit any 
of their needs, and if they add slow recognizers on the top of the stack, 
the whole search can become pretty slow.

Comparing gforth-0.7.3 vs. current git Gforth on loading cross.fs however 
shows a measurable difference in favor of gforth-current (32ms vs. 36ms 
user time). Something else became better... and in fact, we have tuned 
our hash function.

If you think that the simple loop through the recognizer stack is too 
expensive, it's certainly possible to compile a tuned search function on 
every SET-RECOGNIZERS (possibly giving it a unique name derived from a 
hash over the xts, and using that name if it is already available), and 
that should eliminate the dynamic overhead. But we have that sort of 
overhead already for the loop through the search order. In fact, treating 
the search order as recognizer stack and using a similar precompilation 
scheme on SET-ORDER could tune that, too.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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

#51414

On Tuesday, September 27, 2016 at 4:38:42 AM UTC-4, Andrew Haley wrote:
> Paul Rubin <no.email@nospam.invalid> wrote:
> > tabcomputing@gmail.com writes:
> >> Thanks, that helps. So it still goes word by word. But isn't that
> >> going to be rather slow? Every word has to run thru 1 to N functions
> >> to find a match, usually N. 
> > 
> > Usually 1.  The first thing is look up the word in the dictionary.  If
> > not, see if it's an integer literal, etc.  That's what the text
> > interpreter does now.
> 
> I think the proposal is to allow recognizers to be run before
> dictionary search.  The dictionary search itself can be a recognizer,
> and can appear anywhere in the recognizer stack.

In fact I realized today that a string recognizer that could handle spaces (e.g. `"foo bar"`, would *have* to come before the dictionary recognizer, otherwise things could turn into a hot mess., e.g. if someone defined a word `"foo`.

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

#51418

Perhaps there should be a way of associating a recognizer with the CURRENT wordlist,  by analogy with TO FORTH-RECOGNIZER, so that it is active when the wordlist is in the search order. That would produce the same effect as defining recognizers with prefixes: INTERPRET would check each wordlist and its recognizer before moving on to the next. You could attach a recognizer to an empty wordlist, as so have it wherever you needed it in the search order.

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

#51476

JennyB <jennybrien@googlemail.com> writes:
>Perhaps there should be a way of associating a recognizer with the CURRENT =
>wordlist,  by analogy with TO FORTH-RECOGNIZER, so that it is active when t=
>he wordlist is in the search order. That would produce the same effect as d=
>efining recognizers with prefixes: INTERPRET would check each wordlist and =
>its recognizer before moving on to the next. You could attach a recognizer =
>to an empty wordlist, as so have it wherever you needed it in the search or=
>der.

What would be the use case of such a scheme?

Among the use cases for recognizers that I know of, such an
association is not needed:

1) For typical literals, I don't see a particular need to associate
them with wordlists.  You might want to have a literal for some data
that is only dealt with in a particular wordlist, then the association
would save you from having to remove both the wordlist from the search
order and the recognizer from the recognizer stack.  But that is not a
common pattern for using recognizers yet, so maybe we should wait if
it establishes itself before thinking about adding such a feature.

2) For stuff like dot-parsers ("a.b") and TO-replacement ("->v"), the
lookup of a and v happens in the search order anyway, so no need to
associate these recognizers with wordlists.

- 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]

#51421

In article <bb4789a1-e1c7-49cd-be30-dd1fbb79ebd6@googlegroups.com>,
trans  <transfire@gmail.com> wrote:
>On Tuesday, September 27, 2016 at 4:38:42 AM UTC-4, Andrew Haley wrote:
>> Paul Rubin <no.email@nospam.invalid> wrote:
>> > tabcomputing@gmail.com writes:
>> >> Thanks, that helps. So it still goes word by word. But isn't that
>> >> going to be rather slow? Every word has to run thru 1 to N functions
>> >> to find a match, usually N.
>> >
>> > Usually 1.  The first thing is look up the word in the dictionary.  If
>> > not, see if it's an integer literal, etc.  That's what the text
>> > interpreter does now.
>>
>> I think the proposal is to allow recognizers to be run before
>> dictionary search.  The dictionary search itself can be a recognizer,
>> and can appear anywhere in the recognizer stack.
>
>In fact I realized today that a string recognizer that could handle
>spaces (e.g. `"foo bar"`, would *have* to come before the dictionary
>recognizer, otherwise things could turn into a hot mess., e.g. if
>someone defined a word `"foo`.
>

That is not true. Look into the implementation of strings in ciforth,
i.e. the source of the word `` " ''
The regular rules apply, it is later in the search order than
"foo so "foo is found first.
But it is essential that the prefix is allowed to parse for itself,
i.e. increment the parse pointer >IN (or whatever has a similar
function)

If string recognizer means a "string recognizer in the sense of the
20xx standard" you may be right though. That might be an argument
against it.

Groetjes Albert
-- 
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]

#51424

On Wednesday, September 28, 2016 at 10:54:21 AM UTC+3, Albert van der Horst wrote:

> >
> >In fact I realized today that a string recognizer that could handle
> >spaces (e.g. `"foo bar"`, would *have* to come before the dictionary
> >recognizer, otherwise things could turn into a hot mess., e.g. if
> >someone defined a word `"foo`.
> >
> 
> That is not true. Look into the implementation of strings in ciforth,
> i.e. the source of the word `` " ''
> The regular rules apply, it is later in the search order than
> "foo so "foo is found first.

The both cases have an issue of shadowing.

Either `"*` words or `"foo *" strings will be shadowed.

So with this strings literals either names that start with
quote mark (`"`) or strings that start with existent words
having name `"*` will be inaccessible.

Perhaps the names that start with quote mark (i.e. in form `"*`)
should become reserved. Or such names should not be used when
recognizer for such string literals is in the scope.

--
Ruvim

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

#51432

In article <13bd0549-26fa-49ab-a1bc-9209713396a9@googlegroups.com>,
 <ruvim.pinka@gmail.com> wrote:
>On Wednesday, September 28, 2016 at 10:54:21 AM UTC+3, Albert van der Horst wrote:
>
>> >
>> >In fact I realized today that a string recognizer that could handle
>> >spaces (e.g. `"foo bar"`, would *have* to come before the dictionary
>> >recognizer, otherwise things could turn into a hot mess., e.g. if
>> >someone defined a word `"foo`.
>> >
>>
>> That is not true. Look into the implementation of strings in ciforth,
>> i.e. the source of the word `` " ''
>> The regular rules apply, it is later in the search order than
>> "foo so "foo is found first.
>
>The both cases have an issue of shadowing.
>
>Either `"*` words or `"foo *" strings will be shadowed.
>
>So with this strings literals either names that start with
>quote mark (`"`) or strings that start with existent words
>having name `"*` will be inaccessible.

If you have a prefix " and a normal word "foo that takes precedence
then of course:
"foo aap noot"
is not recognized as a string of three words.
Instead "foo is found and executed/compiled.

That is what the poor computer was ordered to do.

("Do what I mean, not what I say!")

>
>Perhaps the names that start with quote mark (i.e. in form `"*`)
>should become reserved. Or such names should not be used when
>recognizer for such string literals is in the scope.

That would destroy the notion that " is not special, but
just another prefix in the life of a bicycle repair man.

>
>--
>Ruvim

Groetjes Albert
-- 
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]

#51435

trans <transfire@gmail.com> writes:
>In fact I realized today that a string recognizer that could handle spaces (e.g. `"foo bar"`, would *have* to come before the dictionary recognizer, otherwise things could turn into a hot mess., e.g. if someone defined a word `"foo`.

That's the usual conflict in Forth.  Somebody can define a word `10`
that will shadow the integer `10`, but nobody does.  A more serious
problem is words like `add` when the BASE is HEX; that has classically
been worked around by writing the number as `0add`, and in modern days
as `$add`; and of course you don't define words that look like that.

Similarly, if you define a word in a world with a string recognizer,
you will not name it `"foo`.  And if you design a new recognizer, you
will avoid using a pattern that conflicts with existing words.

- 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]

#51380

In article <7cf7cab7-4593-48e7-a088-218458d61003@googlegroups.com>,
 <tabcomputing@gmail.com> wrote:
>On Tuesday, September 27, 2016 at 12:39:46 AM UTC-4, Paul Rubin wrote:
>> trans <transfire@gmail.com> writes:
>> > Could someone explain how recognizers work in laymen terms?
>>=20
>> After parsing a word, pass it to a series of user-supplied functions
>> (plus some default ones) until one of them decides that it knows how to
>> handle the word.  This contrasts with the traditional system of having
>> special hair built into the text interpreter to handle things like
>> numeric literals, char constants in 'x' notation, etc.
>
>Thanks, that helps. So it still goes word by word. But isn't that going to =
>be rather slow? Every word has to run thru 1 to N functions to find a match=
>, usually N. And the what does it do when it finds a match? Does it put wor=
>ds on the stack? e.g. does `"foo` =3D> `s" foo`? Or I guess actually it jus=
>t process it as if it were `"s foo`?

Thank you for asking.
If you're at all concerned about the speed of compilation (I don't)
you should use a hash table for the dictionary.
This works like this. Read a word and derive a random number from it.
It is unlikely that there is an other dictionary word with the same
number. So if you've a mechanism to find the dictionary entry based on
that random number, you've approximately an O(1) process, meaning
that all words are found equally fast. This is called hashing.
You must have a provision for random words being the same. (collisions.)
But that is about it. There is no looping over anything so this can
be quite fast.

Enter prefixes. If you implement recognizers with prefixes in the way
I do, the next thing after a failed search is to try a string consisting
of the first letter of the word. That is of course about as fast as the
first search. A basic ciforth system has only one char recognizers.
The library contains one two character prefix  ("0x").
In that case a search for two letter prefixes is to be added.

So concerning speed of recognizers:
1. I don't care
2. If paid for, I will show you a damned fast dictionary lookup.

A simple implementation of prefixes has the advantage that a
user can put them in a wordlist and put that wordlist in the
search order or not. This advantage is lost in hashing, but it is
not part of the recognizers as standardised anyway.
In example may help. Suppose I don't load the floating point
wordset. fp numbers are not recognized. Now I load the fp wordset
in its own wordlist, but I don't put that wordlist
in the search orde. fp numbers are still not recognized.
Now I put it in the search order. fp numbers are recognized.

Groetjes Albert
-- 
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] | [standalone]

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

csiph-web