RfD: Quotations --------------- Change history -------------- 28Jul2015 Alex McDonald v1 initial draft 04Aug2015 Alex McDonald v2 update added & extended "Rationale", "Discussion" formalised "Specification" corrected "Implementation" added "References" 01Jul2016 Anton Ertl v3 various non-substantive changes throughout removed revised definition of RECURSE revised the stack effect to have quotation-sys colon-sys revised the specification wording added tests Quotations ========== The essence of quotations is to provide nested colon definitions, in which the inner definition(s) are nameless. The expression : foo ... [: some words ;] ... ; is equivalent to :noname some words ; Constant #temp# : foo ... #temp# ... ; A simple quotation is an anonymous colon definition that is defined inside a colon definition or quotation. Rationale --------- There is no situation where quotations cannot be implemented by existing Forth words. Specifcially, :NONAME and : provide all the features proposed for quotations. Their advantage is as a syntactic "sugar" that permits a nameless definition in close proximity to its use; and that it avoids generating one-use names only for the purpose of refering to the definition inside another word. One example use of quotations is to provide a solution to the use of CATCH in a form close to other languages' TRY ... EXCEPT blocks. : hex. ( u -- ) base @ >r [: hex u. ;] catch r> base ! throw ; The advantage of using CATCH here is that the BASE is restored even if there is an exception (e.g., a user interrupt) during the "U.". Moreover, return-address manipulation has often been used as a way to split a definition into several parts, e.g,: : foo bar list> bla blub ; where LIST> is a return-address manipulating word and executes the BLA BLUB part of the word possibly several times. This demonstrates that introducing a helper definition is unattractive to these programmers; with quotations this code could be written without helper word as : foo bar [: bla blub ;] map-list ; The advantages of this variant are: 1) Implementating quotations puts less restrictions on the Forth system than implementing manipulable return-addresses (which would restrict tail-call elimination and inlining). 2) It is immediately visible to the reader that there is a separate definition containing BLA BLUB. Experience ---------- Under the term "Phrases", quotations have been in MacForth since at least 1987. They are documented in the infamous "missing chapter" of the MacForth manual. Implementations exist in (at least) VFX, Gforth and iForth, and in the iForth case appear to have some significant use and history. The Gforth development version from 2016-06-28 contains 70 occurences of ";]". Interactions ------------ Quotations change the "current definition" that a number of words (in particular, RECURSE, DOES> and locals) refer to, so we have to look at the interactions of these words and locals. In these interactions there is a conflict between interface simplicity and implementation simplicity; disallowing all combinations of quotations and these words would give most freedom to implementors to choose the simplest implementation; but it would make for an interface full of blind alleys: If you choose one feature, you cannot choose any of the others; and if you use one feature, and then find you need another one, you have to back out of using the first one. Moreover, all these restrictions would have to be specified in the standard. This is not desirable, so here we propose to make all these words work for quotations as well as they work for standalone definitions; this is relatively cheap to implement. RECURSE RECURSE inside a quotation calls the quotation directly surrounding the RECURSE, not the containing colon definition. DOES> A DOES> part inside a quotation ends with the terminating ";]" Using DOES> is actually a useful example of using quotations. E.g., contains two helper words (DOFIELD and DOZEROFIELD) in the following code: : dofield ( -- ) does> ( name execution: addr1 -- addr2 ) @ + ; : dozerofield ( -- ) immediate does> ( name execution: -- ) drop ; : field ( align1 offset1 align size "name" -- align2 offset2 ) \ name execution: addr1 -- addr2 2 pick >r \ this uglyness is just for optimizing with dozerofield create-field r> if \ offset<>0 dofield else dozerofield then ; Quotations allow to write this more compactly as: : field ( align1 offset1 align size "name" -- align2 offset2 ) \ name execution: addr1 -- addr2 2 pick >r \ this uglyness is just for optimizing with dozerofield create-field r> if \ offset<>0 [: does> ( addr1 -- addr2 ) @ + ;] else immediate [: does> ( -- ) drop ;] then execute ; The second RfD proposed to allow RECURSE after DOES> in general (currently it is ambiguous), but this is not common practice yet, so the present version removed this part of the proposal in order to focus on the quotations proper. Locals A quotation may not be able to access the locals of the outer word because it has no knowledge of when it might be executed and hence whether outer locals are still alive. It does permit defining and accessing its own locals. Note that this means that both the quotation and the containing definition may define locals. : foo ... [: {: a b :} a b + ;] ... ; \ unambiguous : bar {: a b :} ... [: a b + ;] ... ; \ ambiguous : bla {: a ;} ... [: {: b ;} ... b ... ;] ... a ... ; \ unambiguous The present proposal does not propose that a quotation can access the locals of a containing definition, because the implementation would be relatively complex, impose a run-time overhead, and the lifetime of the locals would be restricted (unless we are willing to accept further complexity). While there are a number of people who are very keen to have such a feature, it is not clear how much it would be used. System implementors are encouraged to provide support for accessing outer locals on an experimental basis so that programmers can explore the usefulness of this feature, possibly resulting in a proposal for this feature in the future. Syntax ------ The following notations have been seen in the wild, oldest first. :| ... |; :[ ... ]: [: ... ;] The notation [: ;] appears to have popular support. Specification ------------- New system-compilation type quotation-sys with an implementation-dependent size on the stack. This type contains the data that needs to be saved for the enclosing colon definition and restored after the end of the quotation. [Note: we use it in combination with colon-sys, because DOES> uses colon-sys during compilation.] [: bracket-colon Interpretation: Interpretation semantics for this word are undefined. Compilation: ( -- quotation-sys colon-sys ) suspends compiling to the current definition, starts a new nested definition with executeion token xt, and compilation continues with this nested definition. Locals may be defined in the nested definition. An ambiguous condition exists if a name is used that satisfies the following constraints: 1) It is not the name of a currently visible local of the current quotation. 2) It is the name of a local that was visible right before the start of the present quotation or any of the containing quotations. ;] semi-bracket Interpretation: Interpretation semantics for this word are undefined. Compilation: ( c: quotation-sys colon-sys -- ) Ends the current nested definition, and resumes compilation to the previous (containing) current definition. It appends the following run-time to the (containing) current definition: run-time: ( -- xt ) xt is the execution token of the nested definition. Todo ---- The stack effects allow the following: : foo [: ." a" ; : bar ." b " ;] ; foo execute \ prints "a" bar \ prints "b" This actually works in Gforth. Do we want to make this a standard program or not? In either case, we need some wording to make our intent clear. Implementation -------------- It is not possible to define quotations in ISO Forth. The following is an outline definition, where SAVE-DEFINITION-STATE and RESTORE- DEFINITION-STATE require carnal knowledge of the system and are left to the implementor. : [: ( c: -- quotation-sys colon-sys ) postpone ahead save-definition-state :noname ; immediate : ;] ( c: quotation-sys colon-sys -- ) ( s: -- xt ) postpone ; >r restore-definition-state postpone then r> postpone literal ; immediate Compliance Tests ---------------- \ works on Gforth: T{ : q1 [: 1 ;] ; q1 execute -> 1 }T T{ : q2 [: [: 2 ;] ;] ; q2 execute execute -> 2 }T T{ : q3 {: a :} [: {: a b :} b a ;] ; 1 2 3 q3 execute -> 2 1 }T T{ : q4 [: dup if dup 1- recurse then ;] ; 3 q4 execute .s -> 3 2 1 0 }T T{ : q5 [: does> drop 4 ;] 5 swap ; create x q5 execute x -> 5 4 }T References ---------- Stephen Pelc wrote this; see http://newsgroups.derkeiler.com/Archive/Comp/comp.lang.forth/2012-07/msg00791.html I (Alex McDonald) have taken it and modified it as a proposed RfD, and have removed the discussion of closures. http://www.forth200x.org/ I (Anton Ertl) have taken it and revised it. The following notes on quotations and closures incorporate material from several people, including Anton Ertl, Andrew Haley, Marcel Hendrix, Ward Mcfarland, Bernd Paysan, and Elizabeth Rather. If you have been left out and want acknowledgement, please let me know. Additional contributors; Hugh Aguilar and Gerry Jackson. [Note] The phrase "ambiguous condition" has a specific meaning in Forth standards. An ambiguous condition is "a circumstance for which this standard does not prescribe a specific behavior". The RfD process also states: "If you want to leave something open to the system implementor, make that explicit, e.g., by making it an ambiguous condition."