Digest #117 2020-09-04
Contributions
Author:
M. Anton Ertl
Change Log:
Problem:
The definition of the term "execution token" does not match its usage in FIND.
Solution:
Change the wording of the definition of the term to match the usage.
Proposal:
In Section 2.1, change:
execution token: A value that identifies the execution semantics of a definition.
into
execution token: A value that identifies code that can be
EXECUTEd, e.g., for the interpretation semantics of a word.
Author:
Peter Knaggs
Problem:
The Reference Implementation does not mention a licence to use the code.
Solution:
In the E.1 Introduction to Annex E (Reference Implementations)
Remove the conjunctive clause of the last sentence.
, but it must exhibit the same behavior as the reference implementation given here
Add the following paragraph:
We give permission to use these implementations. We encourage you to improve on them as some of them are limited, system-specific and/or may contains bugs. They are distributed in the hope that they will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Replies
Concerning the first argument: I have realized that a system is not allowed to break contiguous of the data space on changing the compilation word list (that was created via WORDLIST at least). So, it can only may take place for code space only, but it doesn't make much sense. So, the first argument can be discarded.
proposal - Wording: declare undefined interpretation semantics for locals
I think we should remove the execute of locals entirely, and state compilation semantics is to append this.
E.g. trying to tick a local and execute it fails, e.g. in Gforth:
: test { a b c } ['] a execute b + c * ;
*terminal*:1:22: warning: a is compile-only ok
1 2 3 test .
*the terminal*:2:7: error: Stack underflow
1 2 3 >>>test<<< .
Backtrace:
*terminal*:1:34 0 $7F4559C5A5E0 +
or Vfx:
: test {: a b c :} ['] a execute b + c * ; ok
1 2 3 test ok
. 6
Err# -4 ERR: Data stack underflow.
Executing a local simply doesn't work.
CS-DROP "Request for Discussion"
Change History
2020-09-03 Describe behaviour of orig forward references that are resolved multiple times or not at all
2019-08-22 CS-DROP again should drop both, control-flow dest and orig item. Propsal extended to included CS-PICK modification
2018-08-20 CS-DROP now operates only on control-flow dest items, typical use example has simpler control-flow structure
2017-07-27 First version
Problem
Forth-94 and Forth-2012 provide explicit access to the control-flow stack by means of the words CS-PICK and CS-ROLL in the Programming-Tools extension wordset (TOOLS EXT). These words allow to copy and rearrange control flow (orig and dest) items.
Control structures (BEGIN IF AHEAD WHILE ...) put control-flow dest resp. orig items onto the control-flow stack. orig items always go along with a yet unresolved forward branch. dest items mark backward branch targets.
There is however no way to remove an item from the control-flow stack without actually resolving it. This limits the abilty to define more complex control structures within the standard's scope.
In its Forth-94 and Forth-2012 version CS-PICK has only defined behaviour when copying dest items to the top of the control flow stack:
15.6.2.1015 CS-PICK “c-s-pick” TOOLS EXT
Interpretation: Interpretation semantics for this word are undefined.
Execution: ( C: dest_u ... orig_0|dest_0 –– dest_u ... orig_0|dest_0 dest_u) ( S: u – – )Remove u. Copy dest_u to the top of the control-flow stack. An ambiguous condition exists if there are less than u+1 items, each of which shall be an orig or dest, on the control-flow stack before CS-PICK is executed.
If the control-flow stack is implemented using the data stack, u shall be the topmost item on the data stack.
See: A.15.6.2.1015 CS-PICK.
u has to index a dest item (dest_u in the above standard text). Trying to copy an orig item with CS-PICK results in an ambigous condition as this would violate the type compatibility with the dest_u input parameter:
4.1.2 Ambiguous conditions
A system shall document the system action taken upon each of the general or specific ambiguous conditions identified in this standard. See 3.4.4 Possible actions on an ambiguous condition.
The following general ambiguous conditions could occur because of a combination of factors:
[...]
– argument type incompatible with specified input parameter, e.g., passing a flag to a word expecting an n (3.1 Data types);
CS-DROPping orig items
So, with this Forth-94 and Forth-2012 behaviour of CS-PICK (trying to copy an orig item is an ambigous condition) it seems to
be reasonable to deal with orig items only by resolving them e.g. by THEN or ELSE.
Simply dropping an orig item leaves an unresolved forward branch which actually is malformed code and eventually will crash when executed.
If however CS-PICK could also copy orig items in a defined way, multiple identical orig items could exist in the control flow stack and dropping them later would be perfectly reasonable. The programmer would take care that exactly one of these orig items will be resolved and all other items dropped at the best convenience of her program.
CS-DROPping dest items
An addition, there are situations where control-flow dest items have been generated or duplicated by CS-PICK and then need no further resolution and thus should be simply removed. As dest items designate branch targets, dropping them when not needed is of no further significance.
Solution
A control-flow stack operator - CS-DROP - to discard the top most control flow item can be defined to supply the missing functionality.
Combined with the duplication capability of CS-PICK and the re-arrangement capability of CS-ROLL this would allow to do arbitrary control flow stack changes of its top items (down to the first colon-sys, do-sys, case-sys, or of-sys).
Being able to CS-DROP both orig and dest items from the control flow stack calls for tightening the definition of CS-PICK to allow copying dest and also orig items. This would eliminate the ambigous condition of CS-PICK operating on orig items.
Proposal
Revise the word CS-PICK in the Tools Extension wordset (TOOLS EXT) so that it can copy both orig and dest items (replace 15.6.2.1015 with the following paragraph):
15.6.2.1015 CS-PICK “c-s-pick” TOOLS EXT
Interpretation: Interpretation semantics for this word are undefined.
Execution:
( C: orig_u|dest_u ... orig_0|dest_0 –– orig_u|dest_u ... orig_0|dest_0 orig_u|dest_u) ( S: u –– )
Remove u. Copy orig_u|dest_u to the top of the control-flow stack. An ambiguous condition
exists if there are less than u+1 items, each of which shall be an orig or dest, on the
control-flow stack before CS-PICK is executed.
If the control-flow stack is implemented using the data stack, u shall be the topmost item
on the data stack.
See: A.15.6.2.1015 CS-PICK.
Add the word CS-DROP to the Tools Extension wordset (TOOLS EXT).
CS-DROP "c-s-drop" TOOLS EXT
Interpretation: Interpretation semantics for this word are undefined.
Execution: ( C: orig|dest -- )
Remove the top item dest from the control-flow stack.
An ambiguous condition exists if the top control-flow stack item
is not a dest, an orig, or if the control-flow stack is empty.
Add the following ambiguous conditions to section 4.1.2 Ambiguous conditions
- resolving an already resolved orig forward reference (6.1.1310 ELSE,
6.1.2270 THEN, 6.1.2140 REPEAT)
- at the end of the current definition unresolved orig forward reverences still
exist (6.1.0460 ;, 6.1.1700 IF, 6.1.1310 ELSE)
Typical Use
Typical use of CS-DROP would be in defining elaborated control structures.
As an example for the use of CS-DROP we create a simple control structure that allows to branch multiple times to an enclosing BEGIN. A corresponding END drops the BEGIN-generated control-flow dest item:
: END ( C: dest -- ) \ Compilation
( -- ) \ Run-time
CS-DROP ; IMMEDIATE
: ?{ ( C: dest –– dest orig dest) \ Compilation
( f -- ) \ Run-time
POSTPONE IF 1 CS-PICK ; IMMEDIATE
: }* ( C: orig dest -- )
POSTPONE AGAIN POSTPONE THEN ; IMMEDIATE
This can for example be used to define the Collatz function:
: even? ( u -- f ) 1 AND 0= ;
: collatz ( u -- )
BEGIN
DUP .
DUP even? ?{ 2 / }*
DUP 1 <> ?{ 3 * 1+ }*
END
DROP ;
19 collatz ( 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 ok )
Remarks
Several Forth-94 and Forth-2012 systems already define CS-DROP or the same functionality under a different name. It is already common practice so it is only consequent to standardize its use.
Neither Forth-94 nor Forth-2012 specify the size of orig or dest items. They are even not required to have identical sizes. Different sizes would complicate the implementation of CS-ROLL (and the proposed revised CS-PICK). Most systems therefore implement orig and dest items the same size. The implementation of the proposed revised CS-PICK should thus be straight forward in most systems (and in no case more complicated than CS-ROLL).
Reference implementation
As standard systems are
free to choose an appropriate representation for control-flow dest and orig stack items and also
free to choose the data stack as control-flow stack or a separate stack for this purpose
a standard definition for CS-DROP cannot be provided.
An estimation for dest items only would be the following definitions that however compile code in the dictionary.
: CS-DROP ( C: dest -- ) POSTPONE TRUE POSTPONE UNTIL ;
: CS-DROP ( C: dest -- ) POSTPONE AHEAD 1 CS-ROLL POSTPONE AGAIN POSTPONE THEN ;
CS-DROP can easily implemented in a system specific way if system knowledge about the control-flow stack implementation is available.
As an example SwiftForth uses a single cell on the data stack as control-flow items. A SwiftForth definition for CS-DROP, which also takes compiler security into account would be:
: CS-DROP ( C: orig|dest -- ) DROP -BAL ;
Win32Forth uses two cells on the data stack as control-flow items including one cell for compiler security, so a defintion for CS-DROP in Win32Forth would be:
: CS-DROP ( C: orig|dest -- ) 1 ?PAIRS DROP ;
Testing
The following test assures that CS-DROP actually removes the top most dest item from the control-flow stack:
t{ 99 :NONAME BEGIN [ CS-DROP ] ; DROP -> 99 }t
The following test assures that CS-PICK can copy orig items and CS-DROP can discard them:
t{ 99 :NONAME IF [ 1 CS-PICK CS-DROP ] THEN ; DROP -> 99 }t
Experience
CS-DROP is already available in the following systems:
- gForth version 0.7.9 (not in 0.7.3)
- VFX version 4.7.2
- PFE version 0.33.71
- DXForth version 4.30
Similar functionality with a different name is supported by:
- FLT version 1.3.2 as (delete-cs-item)
CS-DROP is not (yet) supported in:
- SwiftForth version 3.6.3, sample definition given above
- Win32Forth version 6.15.04, sample definition given above
The Gforth 0.7.9 implementation of CS-PICK includes a check that actually only dest items are copied (by means of the check ?NON-ORIG). Its CS-DROP implementation does not check for dest items.
There are numerous discussions on comp.lang.forth (e.g. [3][4]) about control structure implementation using control-flow stack manipulations. Among the non standard system specific words mentioned in this context CS-DROP is widely accepted.
There seems to be a prior similar proposal probably by Guido U. Draheim as the PFE Forth documentation [2] suggests.
Discussion
Fall 2019
It was requested to extend the proposal to also handle the cases of unresolved or multiple resolved orig forward references. The proposal is extended by adding appropriate ambiguous conditions.
Fall 2018
In its 2018 (12–14 September) meeting in Edinburgh the Forth standards committee discussed the (2018-08-20 revised) CS-DROP proposal with the following outcome:
CS-DROP
Allowing CS-DROP to drop an orig was discussed, this would require allowing CS-PICK to pick an orig. Referred to author for further consideration.
Fall 2017
The initial version of the proposal was presented at the fall 2017 standards meeting. It proposed CS-DROP to drop both dest and orig items. Concerns were raised that using CS-DROP with control-flow orig items would lead to unresolved branch origins that eventually will result in run time errors when executed. Every orig created (e.g. by IF AHEAD ELSE WHILE) should be resolved exactly once (e.g. by THEN ELSE REPEAT).
The standardized behaviour of CS-PICK (15.6.2.1015) in both Forth-92 and Forth-2012 does not allow to copy control-flow orig stack items but requires a control-flow destination item dest-u to be copied. Although not explicitly stated we assume that copying orig items is an ambigous condition. Thus control-flow orig items cannot be copied within the Forth94 and Forth2012 standard scope, only control-flow dest items can. For this it is reasonable to restrict the to be standardized CS-DROP to also only drop control-flow dest items.
References
[1] http://dxforth.netbay.com.au/cfsext.html
[2] http://forth.sourceforge.net/word/cs-drop/
[3] https://groups.google.com/forum/#!topic/comp.lang.forth/64GKthsYVFs
[4] https://groups.google.com/forum/#!msg/comp.lang.forth/QCrKjzxodj0/RpPpq8Jp0AoJ
Author
Ulrich Hoffmann uho@xlerb.de
It would be good if CS-PICK and CS-DROP also mention the ambiguous conditions. Also, the references should mainly include CS-PICK for the resolved-twice ambiguous condition, and CS-DROP for the unresolved ambiguous condition.
proposal - XML Forth Standard - migration from LaTeX to DocBook
extreme verbosity,
At the first glance, verbosity can be slightly reduced. E.g., the fragment:
\<compile\>
<stack type="C">
\<pre\>colon-sys_1</pre>
\<post\>colon-sys_2</post>
</stack>
\<para\>
Append the run-time semantics below to the current
definition.
Whether or not the current definition is rendered
findable in the dictionary by the compilation of
<word word="core:DOES" /> is implementation defined.
Consume \<param\>colon-sys_1</param> and produce
\<param\>colon-sys_2</param>. Append the initiation
semantics given below to the current definition.
</para>
Can be expressed as:
<compiling cs="colon-sys_1 -- colon-sys_2">
\<p\>
Append the run-time semantics below to the current definition.
Whether or not the current definition is rendered
findable in the dictionary by the compilation of
<w id="COREto"/> is implementation defined.
Consume \<d\>colon-sys_1</d> and produce
\<d\>colon-sys_2</d>. Append the initiation
semantics given below to the current definition.
</p>
The idea: use shorter names for frequent elements, and use attributes.
The attributes ds, rs, cs, fs — for the data stack, return stack, control-flow, and floating-point stack correspondingly.
p — the same as in HTML for paragraph. The <w id="DOESto"/> element can be also written as \<w\>DOES></w>.
I don't sure concerning supporting such XML attributes in the DocBook format, but in any case it can be easily transformed into the required form.
the need to escape > and < (probably also &); this is especially noticable in the testing section of the example.
Testing can be expressed less verbosely too, e.g.:
\<testing\>
\<test\>
: DOES1 DOES> @ 1 + ;
CREATE CR1
</test>
\<test\>CR1 \<result\>HERE</result></test>
</testing>
But I don't see much sense to use XML markup for T{ ... -> ... }T construct, when we don't use XML markup for other Forth constructs. What is a rationale?
I could say, if we use classic Forth code for colon-definitions, let's use the classic code for testcases too. For plain text XML nodes we can use CDATA sections to avoid escaping of the special characters:
\<testing\><![CDATA[
T{ : DOES1 DOES> @ 1 + ; -> }T
T{ CREATE CR1 -> }T
T{ CR1 -> HERE }T
]]></testing>
How does this format cope with showing changes?
If you mean showing diff between versions — there are several approaches
- git diff that shows changes in the source code (as plain text);
- something like xmldiff that takes into account XML format and structure (NB: git can use an external diff utility);
- something like html-differ that compares HTML files (the results of rendering);
- some own special tool (i.e. XSLT transformations) that takes into account some special things and renders result in XHTML.
It would be good if CS-PICK and CS-DROP also mention the ambiguous conditions. Also, the references should mainly include CS-PICK for the resolved-twice ambiguous condition, and CS-DROP for the unresolved ambiguous condition.
The problem I see with this is that CS-PICK and CS-DROP would never know what eventually happens with on orig. Their work does not impose the issue with the orig. In the end it is the words (ELSE THEN...) that resolve the orig that cause the problem. Are they used multiple times on the same orig or not at all. Not CS-PICK or CS-DROP to decide.
What would be a good property for CS-PICK and CS-DROP to formulate?
Isn't the Forth way to chain execution tokens to put them in colon definitions? Why do we need req-sequence?
A recognizer can be always created as a colon definition (or a noname, or a quotation).
My view is that this req-sequence is an optional helper, that can be implemented in a portable way, and may be provided by a system. This helper is useful when the new recognizer is just a kind of composition of several other recognizers. Certainly, it can be standardized, as optional word (a kind of standard library level).
Passed to editor
Yes, THEN or ";" may notice these problems, but it's the CS-PICK or CS-DROP that cause it. A programmer should consider this when using CS-PICK and CS-DROP, while a system would notice it at, e.g., THEN and maybe ";".
Do you consider using the "execution token" term in all other places? Or only in the glossary for FIND?
What is a rationale to change this term instead of making correction in FIND?
It seems to me, the "execution token" term is excellent as identifier of execution semantics.
- A "code that can be EXECUTEd" is actually some definition.
definition: A Forth execution procedure compiled into the dictionary.
One anonymous definition can perform interpretation semantics for other named definition.
- The wording "can be
EXECUTEd" seems to be far from the language of standard.
I have raised a new proposal to include licensing text.
Author:
Peter Knaggs
Problem:
The Reference Implementation does not mention a licence to use the code.
Solution:
In the E.1 Introduction to Annex E (Reference Implementations)
Remove the conjunctive clause of the last sentence.
, but it must exhibit the same behavior as the reference implementation given here
Add the following paragraph:
We give permission to use these implementations under the creative commons (CC0 1.0) [1]. We encourage you to improve on them as some of them are limited, system-specific and/or may contains bugs. They are distributed in the hope that they will be useful.
Author:
Peter Knaggs
Problem:
The Reference Implementation does not mention a licence to use the code.
Solution:
In the E.1 Introduction to Annex E (Reference Implementations)
Remove the conjunctive clause of the last sentence.
, but it must exhibit the same behavior as the reference implementation given here
Add the following paragraph:
We give permission to use these implementations under CC0 1.0 [1]. We encourage you to improve on them as some of them are limited, system-specific and/or may contains bugs. They are distributed in the hope that they will be useful.
proposal - Traverse-wordlist does not find unnamed/unfinished definitions
a hash table that contains each name only once
Yes, I see. A hash table may contain nt for the most recently created word among the words with the same name.
requestClarification - Reference implementation does not seem to cope with changes to the stack
Closed as withdrawn.
referenceImplementation - Case-sensitivity independent implementation
We accepted your improved reference implementation 10/0/0.
Yes, it's exactly because I consider all the places where xt occurs that I think it's inadequate to restrict xt to only refer to execution semantics. On the producer side, ' ['], NAME>INTERPRET, NAME>COMPILE come into my mind from the top of my head. On the consumer side, EXECUTE and COMPILE, should not be limited to performing execution semantics. With a restricted xt, you would have to work around that by revising at least all the producers.
xt will continue to be an identifier of execution semantics. With the new wording we can also identify other semantics, and actually the standard has done that all along; it's just that the definition of the term "execution token" did not fit with that usage. This proposal is proposing to fix that.
The wording of the new definition has been hashed out in the committee meeting and I will post a new version of the proposal with the new wording soon.
Author:
M. Anton Ertl
Change Log:
2020-09-03 Hashed out the new wording in a committee meeting.
Problem:
The definition of the term "execution token" does not match its usage in FIND, ', ['], NAME>INTERPRET, NAME>COMPILE.
Solution:
Change the wording of the definition of the term to match the usage.
Proposal:
In Section 2.1, change:
execution token: A value that identifies the execution semantics of a definition.
into
execution token: A value that identifies executable code.
proposal - Traverse-wordlist does not find unnamed/unfinished definitions
Author:
M. Anton Ertl
Change Log:
2020-09-03 Shadowed words are now guaranteed to be visited (consensus of committee discussion)
Problem:
Does TRAVERSE-WORDLIST find unfinished or nameless definitions?
Solution:
It does not.
Proposal:
In TRAVERSE-WORDLIST, change
Execute xt once for every word in the wordlist wid,
into
Execute xt once for every named word that can be found in the word list wid,
Insert, before "TRAVERSE-WORDLIST may visit ..."
Every word that used to be findable in the wordlist but no longer is (because another word with the same name has been defined in the wordlist) is returned by TRAVERSE-WORDLIST.
Discussion
This is a wording change. The use of "can be found" refers to "shall not be findable" in ":" and "allow it to be found" in ";". As a result, TRAVERSE-WORDLIST would no longer visit shadowed words. To address that, the inserted sentence guarantees shadowed entries are visited. The committee discussed whether it is guaranteed that shadowed words are visited, and reached consensus that the old wording already gives that guarantee.
I adapted the suggested term changes of wrt to the Recognizer-A-Proposal to the latest D-Proposal:
| Term in proposal D | Term suggested | comment |
| ------------------------- | ---------------------------------- | ------------------------------------- |
| recognizer stack | recognizer-order | similar to search-order |
| data type id | recognizer information token (rit) | explicit and consistent |
| RECOGNIZE | RECOGNIZE | |
| RECTYPE: | RECOGNIZER | similar to WORDLIST, no defining word |
| RECTYPE-NULL | UNRECOGNIZED | better english |
| REC-SOMETYPE | recognize-xxx | better english |
| RECTYPE-SOMETYPE | xxx-recognized | better english |
The items to be discussed mentioned in the preamble at the beginning of Recognizer RfD rephrase 2020 remain valid.