Proposal: Recognizer

Informal

This page is dedicated to discussing this specific proposal

ContributeContributions

BerndPaysanavatar of BerndPaysan RecognizerProposal2020-07-20 20:36:30

Forth Recognizer -- Request For Discussion

  • Author: Matthias Trute
  • Version: 4
  • Date: 2 August 2018
  • Status: Final (Committee Supported Proposal)

Change history

  1. 2014-10-03 Version 1 - initial version.
  2. 2015-05-17 Version 2 - extend rationale, added ' and [']
  3. 2015-12-01 Version 3 - separate use cases, minor changes for nested recognizer stacks. New POSTPONE action.
  4. 2018-07-24 Version 4 - Clarifications, Fixing typos, added test cases

Change history, details

  1. 2016-09-18 Added more test cases
  2. 2016-09-25 Clarify that >IN is unchanged for an REC-FAIL (RECTYPE-NULL) result.
  3. 2016-10-21 simpler reference implementation
  4. 2016-11-05 first attempt to rename keywords and concept names
  5. 2017-05-15 discussion of LOCATE
  6. 2017-08-08 move example recognizers to discussion/rationale section.
  7. 2017-09-12 renamed keywords in XY.6.1 as suggested by the Forth 200x committee
  8. 2017-12-06 changed wording from "recognizer stack" to "recognizer sequence".
  9. 2017-12-10 created Recognizer EXT section with recognizer sequence management words.
  10. 2018-04-09 expanded EXT section with RECTYPE* words
  11. 2018-05-11 add comments about recognizable?
  12. 2018-07-23 finalized
  13. 2018-07-24 small bugfixes
  14. 2018-08-02 split document into proposal and comments

Problem

The Forth compiler can be extended easily. The Forth interpreter however has a fixed set of capabilities as outlined in section 3.4 of the standard text: Words from the dictionary and some number formats.

It's not possible to use the Forth text interpreter in an application or system extension context. Most interpreters in existing systems use a number of hooks to extent the interpreter. That makes it possible to use a loadable library to implement new data types to be handled like the built-in ones. An example are the floating point numbers. They have their own parsing and data handling words including a stack of their own.

Furthermore applications need to use system provided and system specific words or have to re-invent the wheel to get numbers with a sign or hex numbers with the $ prefix. The building blocks (FIND, COMPILE,, >NUMBER etc) are available but there is a gap between them and what the Forth interpreter already does.

To actually handle data in the Forth context, the processing actions need to be STATE aware. It would be nice if the Forth text interpreter, that maintains STATE, is able to do the data processing without exposing STATE to the data handling methods. These different methods need to be registered somehow.

Solution

The monolithic design of the Forth interpreter is factored into three major blocks: First the interpreter. It maintains STATE and organizes the work. Second the actual data parsing. It is called from the interpreter and analyses strings (sub-strings of SOURCE) if they match the criteria for a certain data type. These parsing words are grouped to achieve an order of invocation. The result of the parsing words is handed over to the interpreter with data specific handling methods. There are three different methods for each data type depending on STATE and to POSTPONE the data.

The combination of a parsing word and the set of data handling words to deal with the data is called a recognizer. There is no strict 1:1 relation between the parsing words and the data handling sets. A data handling set for e.g. single cell numbers can be used by different parsing words.

Whenever the Forth text interpreter is mentioned, the standard words EVALUATE (CORE), ' (tick, CORE), INCLUDE-FILE (FILE), INCLUDED (FILE), LOAD (BLOCK) and THRU (BLOCK) are expected to act likewise. This proposal is not about to change these words, but to provide the tools to do so. As long as the standard feature set is used, a complete replacement with recognizers is possible.

This proposal is about the building blocks.

Proposal

XY. The optional Recognizer word set

XY.1 Introduction

The recognizer concept consists of two elements: parsing words that return data type information that identify the parsed data and provide methods to perform the various semantics of the data: interpret, compile and postpone. A parsing word can return different data type information. A particular data type information can be used by different parsing words.

A system provided data type information is called RECTYPE-NULL. It is used if no other one is applicable. This token is associated with the system error actions if used in step e) of the text interpreter (see Appendix). It is used to achieve the action d) of the section 3.4 text interpreter.

A recognizing word within the recognizer concept has the stack effect

REC-SOMETYPE ( addr len -- i*x RECTYPE-SOMETYPE | RECTYPE-NULL )

This recognizing word must not change the string. When it is called from the interpreter, it may access SOURCE and, if applicable, even change >IN. If >IN is not used, any string may serve as input, otherwise "addr/len" is assumed to be a substring of the buffer SOURCE.

"ix" is the result of the recognizing action of the string "addr/len". RECTYPE-SOMETYPE is the data type id that the interpreter uses to execute the interpret, compile or postpone actions for the data `ix`.

All three actions are called with the "i*x" data as left from the recognizing word and are generally expected to consume it. They can have additional stack effects, depending on what RECTYPE-SOMETYPE-METHOD actually does.

RECTYPE-SOMETYPE-METHOD ( ... i*x -- j*y )

The data "i*x" doesn't have to be on the data stack, it can be at different places, if applicable. E.g. floating point numbers have a stack of their own. In this case, the data stack contains the RECTYPE-SOMETYPE information only.

XY.2 Additional terms and notations

Data type id A cell sized number. It identifies the data type and a method set to perform the data processing in the text interpreter. The actual numeric value is system specific.

Recognizer A string parsing word that returns a data type id together with the parsed data if successful. The string parsing word is assumed to run within the Forth interpreter and can access SOURCE and >IN.

Recognizer Sequence An ordered set of recognizers. It is identified with a cell sized numeric id.

XY.3 Additional usage requirements

XY.3.1 Data type id

A data type id is a single cell value that identifies a certain data type. Append table the following table to table 3.1

Symbol Data type Size on Stack
dt data type id 1 cell

XY.4 Additional documentation requirements

XY.4.1 System documentation

XY.4.1.1 Implementation-defined options

No additional options.

XY.4.1.2 Ambiguous conditions
  • Change of the content of the parsed string during parsing.

XY.4.2 Program documentation

No additional dependencies.

XY.5 Compliance and labeling

The phrase "Providing the Recognizer word set" shall be appended to the label of any standard system that provides all of the Recognizer word set.

XY.6 Glossary

XY.6.1 Recognizer Words

FORTH-RECOGNIZER ( -- rec-seq-id ) RECOGNIZER
A system VALUE with a recognizer sequence id.

It is VALUE that can be changed with TO to assign a new recognizer set. This change has immediate effect.

This recognizer set shall be used in all system level words like EVALUATE, LOAD etc.

RECOGNIZE ( addr len rec-seq-id -- i*x RECTYPE-DATATYPE | RECTYPE-NULL ) RECOGNIZER \

Apply the string at "addr/len" to the elements of the recognizer set identified by rec-seq-id. Terminate the iteration if either a parsing word returns a data type id that is different from RECTYPE-NULL or the set is exhausted. In this case return RECTYPE-NULL.

"i*x" is the result of the parsing word. It represents the data from the string. It may be on other locations than the data stack. In this case the stack diagram should be read accordingly.

RECTYPE>COMP ( RECTYPE-DATATYPE -- XT-COMPILE ) RECOGNIZER \

Return the execution token for the compilation action from the recognizer date type id.

RECTYPE>INT ( RECTYPE-DATATYPE -- XT-INTERPRET ) RECOGNIZER
Return the execution token for the interpretation action from the recognizer data type id.

RECTYPE>POST ( RECTYPE-DATATYPE -- XT-POSTPONE ) RECOGNIZER
Return the execution token for the postpone action from the recognizer data type id.

RECTYPE-NULL ( -- RECTYPE-NULL ) RECOGNIZER
The null data type id. It is to be used if no other data type id is applicable but one is needed. Its associated methods perform system specific error actions. The actual numeric value is system dependent.

RECTYPE: ( XT-INTERPRET XT-COMPILE XT-POSTPONE "name" -- ) RECOGNIZER
Skip leading space delimiters. Parse name delimited by a space. Create a data type id under the name name and associate the three execution tokens.

The words for XT-INTERPRET, XT-COMPILE and XT-POSTPONE are called with the parsed data i*x that e.g. RECOGNIZE has returned.

The word behind XT-INTERPRET shall have the stack effect ( ... i*x -- j*y ). The words behind XT-COMPILE and XT-POSTPONE shall consume i*x.

The execution time of name leaves a cell sized token on the data stack that can be applied to the RECTYPE>* words.

YZ.6.2 Recognizer Extension Words

A Forth system that uses recognizers in the core has words for numbers and dictionary look-ups. They shall be named as shown in the table:

Name Stack effect
`REC-NUM` `( addr len -- n RECTYPE-NUM | d RECTYPE-DNUM | RECTYPE-NULL )`
`REC-FLOAT` `( addr len -- RECTYPE-FLOAT | RECTYPE-NULL ) (F: -- f | )`
`REC-FIND` `( addr len -- XT +/-1 RECTYPE-XT | RECTYPE-NULL )`
`REC-NT` `( addr len -- NT RECTYPE-NT | RECTYPE-NULL )`

The recognizer type names, if available, shall be as shown in the table below:

Name Stack items Comment
`RECTYPE-NUM` `( -- n RECTYPE-NUM)` single cell number
`RECTYPE-DNUM` `( -- d RECTYPE-DNUM)` double cell number
`RECTYPE-FLOAT` `( -- RECTYPE-FLOAT)` `(F: -- f )` floating point number ,
`RECTYPE-XT` `( -- XT +/-1 RECTYPE-XT)` word from the dictionary matching `FIND`
`RECTYPE-NT` `( -- NT RECTYPE-NT)` word from the dictionary with name token NT

The following words deal with changing and creating recognizer sequences.

GET-RECOGNIZER ( rec-seq-id -- rec-n .. rec-1 n ) RECOGNIZER EXT
Copy the recognizer sequence rec-1 .. rec-n to the data stack. The element rec-1 is the first in the sequence.

The source is unchanged.

SET-RECOGNIZER ( rec-n .. rec-1 n rec-seq-id -- ) RECOGNIZER EXT \

Replace the recognizer sequence identified by `rec-seq-id` with a new set of `n` recognizers `rec-x`.

If the capacity of the destination sequence is too small to hold all new elements, an ambiguous situation arises.

NEW-RECOGNIZER-SEQUENCE ( size .. rec-seq-id ) RECOGNIZER EXT
Create a new, empty recognizer sequence with at least `size` elements.
### XY.7 Reference Implementation ### Basic recognizer sequence module. It is implemented as a separate stack.
: STACK ( size -- stack-id )
    1+ ( size ) CELLS HERE SWAP ALLOT
    0 OVER ! \ empty stack
;

: SET-STACK ( item-n .. item-1 n stack-id -- )
  2DUP ! CELL+ SWAP CELLS BOUNDS
  ?DO I ! CELL +LOOP ;

: GET-STACK ( stack-id -- item-n .. item-1 n )
   DUP @ >R R@ CELLS + R@ BEGIN
     ?DUP
   WHILE
     1- OVER @ ROT CELL - ROT
   REPEAT
   DROP R> ;

The recognizer sequence uses the stack module. Hence the stack-id becomes the rec-seq-id.

: NEW-RECOGNIZER-SEQUENCE STACK ;
: SET-RECOGNIZER SET-STACK ;
: GET-RECOGNIZER GET-STACK ;

\ create the default recognizer sequence
4 NEW-RECOGNIZER-SEQUENCE VALUE FORTH-RECOGNIZER

\ create a simple 3 element structure
: RECTYPE: ( XT-INTERPRET XT-COMPILE XT-POSTPONE "<spaces>name" -- )
   CREATE SWAP ROT , , ,
;

\ decode the data structure created by RECTYPE:
: RECTYPE>POST ( RECTYPE-TOKEN -- XT-POSTPONE ) CELL+ CELL+ @ ;
: RECTYPE>COMP ( RECTYPE-TOKEN -- XT-COMPILE  )       CELL+ @ ;
: RECTYPE>INT  ( RECTYPE-TOKEN -- XT-INTERPRET)             @ ;

\ the null token
:NONAME -1 ABORT" FAILED" ; DUP DUP RECTYPE: RECTYPE-NULL

\ depends on the stack implementation
: RECOGNIZE   ( addr len rec-seq-id -- i*x RECTYPE-SOMETYPE | RECTYPE-NULL )
    DUP >R @
    BEGIN
      DUP
    WHILE
      DUP CELLS R@ + @
      2OVER 2>R SWAP 1- >R
      EXECUTE DUP RECTYPE-NULL <> IF
        2R> 2DROP 2R> 2DROP EXIT
      THEN
      DROP R> 2R> ROT
    REPEAT
    DROP 2DROP R> DROP RECTYPE-NULL
;

A.XY Informal Appendix

A.XY.1 Text Interpreter

The Forth text interpreter can be changed into a generic tool that is capable to deal with any data type. It maintains STATE and calls the data processing methods according to it. The example is a full replacement if all necessary recognizers are available.

The algorithm of the Forth text interpreter as described in section 3.4 is modified. All subsections of 3.4 apply unchanged. Change the steps b) and c) from section 3.4 to make them optional, they can be performed with recognizers. Replace the step d) with the following steps d) to f)

  1. For each element of the recognizer sequence provided by FORTH-RECOGNIZER, starting with the top element, call its parsing method with the sub-string "name" from step a).

    Every parsing method returns an information token and the parsed data from the analyzed sub-string if successful. Otherwise it returns the system provided failure token RECTYPE-NULL and no further data.

    Continue with the next element in the recognizer set until either all are used or the information token returned from the parsing word is not the system provided failure token RECTYPE-NULL.

  2. Use the information token and do one of the following

    1. if interpreting execute the interpret method associated with the information token.
    2. if compiling execute the compile method associated with the information token.
  3. Continue with a)

: INTERPRET
  BEGIN
      PARSE-NAME DUP
  WHILE
      FORTH-RECOGNIZER RECOGNIZE
      STATE @ IF RECTYPE>COMP ELSE RECTYPE>INT THEN
      EXECUTE
      ?STACK  \ simple housekeeping
  REPEAT 2DROP
;

A.XY.2 POSTPONE

POSTPONE compiles the data returned by RECOGNIZE (i*x) into the dictionary as literal(s) and appends the compilation action of the RECTYPE-TOKEN data type id. Later at run-time the i*x data is read back and the compilation action is performed like it would have been called directly at compile time.

: POSTPONE ( "name" -- )
  PARSE-NAME FORTH-RECOGNIZER RECOGNIZE DUP >R
  RECTYPE>POST EXECUTE R> RECTYPE>COMP COMPILE, ;

This implementation assumes a system that uses recognizers only.

A.XY.3 Test Cases

The test cases assume a stack to implement the recognizer set.

T{ 4 NEW-RECOGNIZER-SEQUENCE constant RS -> }T

T{ :NONAME 1 ;  :NONAME 2 ;  :NONAME 3  ; RECTYPE: rectype-1 -> }T
T{ :NONAME 10 ; :NONAME 20 ; :NONAME 30 ; RECTYPE: rectype-2 -> }T

T{ : rec-1 NIP 1 = IF rectype-1 ELSE RECTYPE-NULL THEN ; -> }T
T{ : rec-2 NIP 2 = IF rectype-2 ELSE RECTYPE-NULL THEN ; -> }T

T{ rectype-1 RECTYPE>INT  EXECUTE -> 1 }T
T{ rectype-1 RECTYPE>COMP EXECUTE -> 2 }T
T{ rectype-1 RECTYPE>POST EXECUTE -> 3 }T

\ testing RECOGNIZE
T{         0 RS SET-RECOGNIZER -> }T
T{ S" 1"     RS RECOGNIZE   -> RECTYPE-NULL }T
T{ ' rec-1 1 RS SET-STACK -> }T
T{ S" 1"     RS RECOGNIZE   -> rectype-1 }T
T{ S" 10"    RS RECOGNIZE   -> RECTYPE-NULL }T
T{ ' rec-2 ' rec-1 2 RS SET-STACK -> }T
T{ S" 10"    RS RECOGNIZE   -> rectype-2 }T

The dictionary lookup has the following test cases

T{ S" DUP" REC-FIND  -> ' DUP -1 RECTYPE-XT }T
T{ S" UNKOWN WORD" REC-FIND -> RECTYPE-NULL }T

The number recognizer has the following checks

VARIABLE OLD-BASE BASE @ OLD-BASE !

T{ : S-1234 S" 1234" ; -> }T
T{ : D-1234 S" 1234." ; -> }T
T{ : S-UNKNOWN S" unknown word" ; -> }T
T{ : S-DUP  S" DUP" ; -> }T

T{ S-1234 FORTH-RECOGNIZER RECOGNIZE -> 1234  RECTYPE-NUM   }T
T{ D-1234 FORTH-RECOGNIZER RECOGNIZE -> 1234. RECTYPE-DNUM  }T
T{ S-DUP  FORTH-RECOGNIZER RECOGNIZE -> ' DUP -1 RECTYPE-XT }T
T{ S-UNKNOWN FORTH-RECOGNIZER RECOGNIZE  -> RECTYPE-NULL }T
T{ S" %-10010110" REC-NUM -> -150 RECTYPE-NUM }T
T{ S" %10010110"  REC-NUM ->  150 RECTYPE-NUM }T
T{ S" 'Z'"    REC-NUM -> char Z RECTYPE-NUM }T
T{ S" ABCXYZ" REC-NUM -> RECTYPE-NULL }T

\ check whether BASE is unchanged
T{ BASE @ OLD-BASE @ = -> -1 }T

Floating point numbers are handled likewise

T{ : S-1234e5 S" 1234e5" ; -> }T
T{ S-1234e5 REC-FLOAT -> 1234e5 RECTYPE-FLOAT }
T{ S-1234e5 FORTH-RECOGNIZER RECOGNIZE -> 1234e5 RECTYPE-FLOAT }T

Experience

First ideas to dynamically extend the Forth text interpreter were published in 2005 at comp.lang.forth by Josh Fuller and J Thomas: Additional Recognizers?

A specific solution to deal with number prefixes was roughly sketched by Anton Ertl at comp.lang.forth in 2007 with https://groups.google.com/forum/#!msg/comp.lang.forth/r7Vp3w1xNus/Wre1BaKeCvcJ

There are a number of specific solutions that can at least partly be seen as recognizers in various Forth's:

  • prefix-detection in ciforth
  • W32Forth uses its "chain" concept to achieve similar effects.
  • various commercial Forth's seem to have ways to extent the interpreter.
  • FICL, a system close to Forth, has parse-steps since approx 2001.

A first generic recognizer concept was implemented in amforth version 4.3 (May 2011). The design presented in this RFD is implemented with version 5.3 (May 2014). gforth has recognizers since 2012, the ones described here since June 2014.

Existing recognizers cover a wide range of data formats like floating point numbers and strings. Others mimic the back-tick syntax used in many Unix shells to execute OS sub-process. A recognizer is used to implement OO notations.

Most of the small words that constitute a recognizer don't need a name actually since only their execution tokens are used. For the major words a naming convention is suggested: REC-<name> for the parsing word, and RECTYPE-<name> for the data type word created with RECTYPE: for the data type "name".

Acknowledgments

The following people did major or minor contributions, in no particular order.

  • Bernd Paysan
  • Jenny Brien
  • Andrew Haley
  • Alex McDonald
  • Anton Ertl
  • Forth 200x Committee

BerndPaysanavatar of BerndPaysan

There are a number of discussions going on elsewhere, and I want to make sure the discussion is going to be here. So for a start, I just took Matthias' version D proposal.

Ideas discussed:

  • Bikeshedding the names again (we already did that).
  • Revert the postpone action to version A
  • Introduce RECOGNIZER-SEQUENCE: word, which creates a new recognizer that actually consists of a sequence of those.

Please feel free to introduce these ideas here.

Reply New Version