Syntax Extensions for FTL (Function Template Library)
Sergei Egorov <segorov@malgil.com>
The purpose of this SRFI is to propose a shortcut notation for construction of specialized versions of FTL algorithms (See FTL SRFI for details).
FTL Syntax is not extendable. Although implementors can provide
reacher sets of algorithms/interfaces, there is no way for a user
of this SRFI to change the behavior of template-define.
Scheme Template Library (see FTL SRFI) offers a regular set of "building blocks" for construction of sequence-related algorithms. Although, in simple cases, writing a correct expression yielding the required procedure is straightforward, complex cases may need much more attention to detail. This SRFI proposes a radical solution: use the regularity of FTL notation to generate specialization expressions from user-supplied names of specialized procedures.
As an example, instead of writing an explicit specialization for string-to-vector converter:
(define string->vector (%v->%mv v=string mv=vector))
SRFI-102 allows you to write:
(template-define string->vector)
Here, template-define is a macro that finds the
suitable specialization expression automatically, by "parsing"
the user-supplied name (string->vector). The
name is treated as a string in the context-free language,
defined by the set of previously introduced interfaces and
algorithms (their symbolic names, to be exact.) If FTL's naming
conventions are followed, the "mental printf" used to check
that a specialization expression is correct can be turned
into an automatic method of finding the expression that
fits the given name. If the name itself is too long for
normal use, a two-argument form of template-define
can be used, allowing one to specify the preferred name
to be used in the program together with an artificial
name used to produce the specialization expression:
(template-define filter list-remove-if-not->list) ;; expands to ;; (define filter (%g-remove-%t->%o g=list t=if-not o=list)) (template-define string-filter-ci->list string-remove-not-char-ci->list) ;; expands to ;; (define string-filter-ci->list ;; (%g-remove-%t->%o g=string (t=not-%t t=char-ci) o=list))
Since FTL is extendable, there should be a way to extend the
grammar used by template-define to include new
productions corresponding to newly introduced interfaces and
algorithms. This is done by using two special syntax forms
define-ftl-interface and
define-ftl-algorithm. When used at the
top level of a Scheme program, they expand to the
regular define form, extending the grammar
used by template-define with productions,
corresponding to the identifiers being defined:
(define-ftl-interface e=point (e-interface point=?)) ;; expands to ;; (define e=point (e-interface point=?)) (define-ftl-algorithm %z->%q (lambda (z q) ...)) ;; expands to ;; (define %z->%q (lambda (z q) ...))
Unlike regular define forms they expand to,
all three FTL syntax forms can fail to expand (produce
syntax errors) for reasons not immediately related to
the structure and number of their arguments. The system
keeps track of all the productions being added to the
grammar and returns a syntax error when such an addition
would make the grammar unsuitable for the purposes
of template-define's expression builder.
The grammar should always produce a finite number
of parse trees given a finite input; it should not
contain empty productions or identity productions
(this outlaws interface names like e=
and e=e). The template-define
form produces a syntax error if there are no
candidate expressions, more than one "best" candidate
expression, or candidate expressions are incompatible
[TODO: an example and an explanation of what it
means to be incompatible].
To be continued...
Below you will see how to construct subsets of R5RS, SRFI-1, SRFI-13, and SRFI-43 using the proposed method. Some of the resulting definitions differ from the originals in some details; those are marked with '*' comment (differ in guarantees) or '1' comment (single-input variant). Places where SRFI-13 argument conventions are inconsistent with those of SRFI-1 (sequence and predicate swapped) are marked with '?'. Note that the generated procedures always use subranges to specify parts of strings and vectors; cases when this affects argument convections are marked with 'r'.
(template-define list) (template-define cons* list*) (template-define make-list) (template-define list-tabulate) (template-define list-copy list->list) (template-define iota list-iota) (template-define list= list-mismatch) ;* (template-define list-ref) (template-define list-tail) (template-define take list-take->list) (template-define drop list-tail) (template-define split-at list-take->list+tail) (template-define last list-last) (template-define length list-length) (template-define append list-append->list) (template-define concatenate list->list/list-splicing) (template-define reverse list->reverse-list) (template-define append-reverse list->reverse-list) (template-define count list-filter-map->count) (template-define fold list-fold) ;1 (template-define fold-right reverse-list-fold) ;1 (template-define map list-map->list) (template-define for-each list-for-each) ;1 (template-define append-map list-map1->list/list-splicing) ;1 (template-define map-in-order list-map->list) (template-define filter-map list-filter-map->list) (template-define filter list-remove-if-not->list) (template-define partition list-partition-if->list+list) (template-define remove list-remove-if->list) (template-define find list-find-if) (template-define find-tail list-member-if) (template-define take-while list-take-if->list) (template-define drop-while list-drop-if) (template-define span list-take-if->list+tail) (template-define break list-take-if-not->list+tail) (template-define any list-ormap) (template-define every list-andmap) (template-define list-index list-position-if) ;1 (template-define member list-member-l) ;* (template-define memq list-member-q) (template-define memv list-member-v) (template-define delete list-remove-l->list) ;* (template-define string-null?) (template-define string-any string-ormap) ;* (template-define string-every string-andmap) ;* (template-define make-string) (template-define string) (template-define string-tabulate) (template-define string->list) (template-define list->string) (template-define reverse-list->string) (template-define string-length) (template-define string-ref) (template-define string-copy) (template-define substring) (template-define string-copy! string->string!) ;r (template-define string-take string-take->string) (template-define string-set!) (template-define string-fill!) (template-define string<? string-char<?) (template-define string<=? string-char<=?) (template-define string>? string-char>?) (template-define string>=? string-char>=?) (template-define string=? string-char=?) (template-define string-ci<? string-char-ci<?) (template-define string-ci<=? string-char-ci<=?) (template-define string-ci>? string-char-ci>?) (template-define string-ci>=? string-char-ci>=?) (template-define string-ci=? string-char-ci=?) (template-define string-prefix-length string-mismatch-char) ;* (template-define string-prefix-length-ci string-mismatch-char-ci) ;* (template-define string-index string-position-if) ;? (template-define string-skip string-position-if-not) ;? (template-define string-count string-filter-map->count) ;? (template-define string-upcase string-upcase->string) (template-define string-downcase string-downcase->string) (template-define string-reverse reverse-string->string) (template-define string-reverse!) (template-define string-append) (template-define string-concatenate list->string/string-splicing) (template-define string-concatenate-reverse reverse-list->string/string-splicing) ;* (template-define string-map string-map1->string) (template-define string-map!) (template-define string-fold) (template-define string-fold-right reverse-string-fold) (template-define string-for-each) (template-define string-replace string->string!) ;*r (template-define string-filter string-remove-if-not->string) ;? (template-define string-delete string-remove-if->string) ;? (template-define vector-null?) (template-define vector) (template-define make-vector) (template-define vector-tabulate) (template-define vector-copy) (template-define vector-iota) (template-define vector= vector-mismatch) ;* (template-define vector-ref) (template-define vector-last) (template-define vector-take vector-take->vector) (template-define vector-length) (template-define vector-copy! vector->vector!) ;r (template-define vector-append) (template-define vector-concatenate vector->vector/vector-splicing) (template-define vector-concatenate* list->vector/vector-splicing) (template-define vector-reverse vector->reverse-vector) (template-define vector-reverse!) (template-define vector-append-reverse vector->reverse-vector) (template-define vector-count vector-filter-map->count) (template-define vector-fold) ;1 (template-define vector-fold-right reverse-vector-fold) ;1 (template-define vector-map vector-map->vector) (template-define vector-map-left vector-map->vector) (template-define vector-map!) (template-define vector-map-left! vector-map!) (template-define vector-for-each) (template-define vector-append-map vector-map1->vector/vector-splicing) ;1 (template-define vector-filter-map vector-filter-map->vector) (template-define vector-filter vector-remove-if-not->vector) (template-define vector-partition vector-partition-if->vector+vector) (template-define vector-remove vector-remove-if->vector) (template-define vector-find vector-find-if) (template-define vector-take-while vector-take-if->vector) (template-define vector-any vector-ormap) (template-define vector-every vector-andmap) (template-define vector-index vector-position-if) ;1 (template-define vector-skip vector-position-if-not) ;1 (template-define vector-delete vector-remove-if->vector) ;? (template-define vector-set!) (template-define vector-fill!) (template-define vector->string) (template-define string->vector) (template-define vector->list) (template-define list->vector)
Reference implementation (not really). TODO: explanation of how it meets the reference implementation requirement.
Copyright © Sergei Egorov (2004). All Rights Reserved.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Scheme Request For Implementation process or editors, except as needed for the purpose of developing SRFIs in which case the procedures for copyrights defined in the SRFI process must be followed, or as required to translate it into languages other than English.
The limited permissions granted above are perpetual and will not be revoked by the authors or their successors or assigns.
This document and the information contained herein is provided on an "AS IS" basis and THE AUTHOR AND THE SRFI EDITORS DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Last modified: Sat Oct 9 17:43:25 EDT 1999