proposal - Recognizer

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.

"i*x" 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 i*x.

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

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 "<spaces>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:

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

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
<dd>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.

: 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> ;

: 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
;

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

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

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

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

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

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

referenceImplementation - Case-sensitivity independent implementation

I LOVE this implementation not because of its case sensitivity awareness. You can define any parsing words in addition to [IF] [THEN] [ELSE] thus to avoid them in commentaries, string literals, etc.

: S" '"' PARSE 2DROP ; IMMEDIATE : .( ')' PARSE 2DROP ; IMMEDIATE

You got the idea. It must be in the standard.

proposal - Recognizer

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.