Graut - Revision history

Psmay: /* Extract specs */

2015-03-31T16:13:57Z

Extract specs

Psmay: /* Built-in functions */

2015-03-31T16:09:56Z

Built-in functions

Psmay: /* Key context */

2015-02-11T16:11:58Z

Key context

Psmay: /* Serialization */

2015-02-10T22:00:52Z

Serialization

Psmay: /* Serialization */

2015-02-10T21:16:28Z

Serialization

Psmay: /* Key context */

2015-02-10T21:13:43Z

Key context

New page

'''Graut''' is a specification for a preprocessor and templating engine. It accidentally resembles a very poor clone of Lisp, but the scope is much different.

==Synopsis==

A Graut source consists of plain text interleaved with function calls. Each function call begins with <code>#(</code>, ends with <code>)</code>, and contains a series of elements.

Specifically, a function call consists of the ''sigil'' <code>#</code> followed by a ''list'' containing elements. An ''element'' is one of these things:

* A ''list'', which starts with <code>(</code>, ends with <code>)</code>, and contains zero or more elements that are usually (but, depending on the element, not necessarily) separated by whitespace.
* An ''atom'', which is a string in one of a few forms:
** An unquoted string, which is one or more consecutive characters in <code>[!%&*+,./:;=?^|~A-Za-z0-9_-]</code> or at or above U+80.
** Monoquoted strings, <code>'...'</code> or <code>"..."</code>, with JSON-esque backslash escapes, which also interpolate function calls as with the top level. (<code>\#</code> will prevent <code>#</code> from starting a call.)
** Triquoted strings, <code><nowiki>'''...'''</nowiki></code> or <code>"""..."""</code>, with no escapes, which do not interpolate.
** Shallow heredocs, <code><SOMETOKEN<...>SOMETOKEN></code>, with no escapes and a selectable close token. (The token has the same specification as an unquoted string.)
** Deep heredocs, <code><<SOMETOKEN<...>SOMETOKEN>></code>, similar to shallow heredocs, but also allowing inline function calls <code>#(...)</code> in the same manner as at the top level.
* A ''function call'', <code>#(...)</code>, consisting of the sigil <code>#</code> followed directly by a list expression.
* An ''inlined list'', <code>@(...)</code>, consisting of the sigil <code>@</code> followed directly by a list expression.
* A ''variable expansion'', <code>$"..."</code>, consisting of the sigil <code>$</code> followed directly by a name (a key).
* An ''nonce'', <code>$</code>, consisting of the sigil <code>$</code> not followed directly by an expression (e.g. followed by a space or a <code>)</code>).

In truth, these comprise only the most common interpretation of a given abstract syntax tree.

===Abstract syntax trees===

The syntax tree of a Graut document consists entirely of the following node types:

* A ''text node'' represents a string zero or more characters. Text nodes for fragments of monoquoted strings have already had backslash escapes processed; otherwise the text is exactly as read from source.
* A ''frame node'' contains a mix of text nodes and <code>#(...)</code> subtrees (which are sigil nodes). String literals, as well as the top level of the document, become frame nodes. Literal strings (unquoted atoms, triquoted strings, shallow heredocs) contain exactly one text node (even for an empty string) and nothing else. The frame node contains information about the open quote mark or heredoc token, if any.
* A ''list node'' consists of zero or more items bounded by <code>(</code> and <code>)</code>.
* A ''sigil node'' is one of the characters <code>$@#</code> as either a nullary or prefix unary operator. Specifically, it is unary if followed, without intervening space, by a ''topic'', which is string, a list, or another sigil; it is nullary otherwise. If unary, the node contains the topic.
** Note that <code>$</code> represents a ''nonce'' constant. Nonces are used in Graut to model impure functions. Each instance of <code>$</code> is assigned its own fixed, ineffable value. This binding is modeled as happening at the beginning of each run.

Not all possibilities are legal in all situations.

===Evaluation contexts===

The meaning of a tree depends on the ''context'' in which it is evaluated. In most situations, a tree is not evaluated unless and until its evaluated value is needed (i.e., ''lazy evaluation'' is in effect).

====Value context====

The top level of a document is evaluated in the ''value'' context.

Values that are ''intermediate'' have some internal meaning that cannot be properly expressed in output without conversion. It is an error to attempt to output such a value directly, and all valid usages convert them to some other form.

In this context, nodes have these meanings:

* A frame node evaluates to the string value it represents.
* A text node evaluates to the concatenated string-context values of its children.
* A list node evaluates to a list value that is the value-context value of each of the elements of the node's tree-context evaluation.
...

====String context====

* A frame node or a text node evaluates to its value-context value.
* A list node evaluates to the concatenated string-context values of its elements.
* A sigil node evaluates to the string-context value of its value-context value.

====Key context====

A key is an internal serialized form for string and list values so that they may be used as variable names, namespaces, hash keys, etc.

A string value is directly representable; a list value is directly representable when all of its elements are either string values or values of other directly representable lists. No other values can be represented directly.

* A frame node or text node is represented as its string-context value.
* A list node is represented as a list value whose elements have been converted to representable values.
* A sigil node is represented by the representation that applied its value-context value.

Key values are normalized so that any two directly representable values have exactly the same representation; it is, however, possible for distinct values to share a representation if they are not directly representable (i.e., if they are or contain data other than strings and lists). They also have a deterministic ordering, though this ordering is only for canonicalization purposes and may not necessarily be coherent to the contained information.

=====Serialization=====

The concept discussed at [[Cifl/Protocifl/Name-encoded_trees Name-encoded trees]] is one possibility for a byte-string representation. That encoding is designed specifically for S-expressions with a list at the root and only byte strings and other lists as elements.

A special meta-representation could be used for typed information. To serialize a list like

(hello #(int 12) fizz #(false) (a "" () b c))

First, we would evaluate the function calls. The resulting values aren't directly representable in source except as calls to a (possibly internal-only) deserialize routine:

("hello"
#( $((SYSTEM number) deserialize-internal) "12" "1" )
"fizz"
#( $((SYSTEM boolean) deserialize-internal) "false" )
("a" "" () "b" "c")
)

The problem is that these results are also function calls (aside from the fact that it's a tad verbose). Instead, let's say the (fictional) sigil `¢` represents an internal deserialization for a given type. Then, we have

("hello"
¢((SYSTEM number) "12" "1")
"fizz"
¢((SYSTEM boolean) "false")
("a" "" () "b" "c")
)

To serialize this, we'll use the a modified treename encoding with the alphabet:

* Any byte (0x00 .. 0xFF)
* A byte string terminator, ‡
* A descent indicator, ↓
* An ascent indicator, ↑
* An abbreviation for ↑↓, ↕
* A construction indicator, €

(Note that ‡↓↑↕€ here represent abstract non-byte symbols, not Unicode values.)

The serialization follows:

<nowiki>
# The root
( "hello" ¢ ( ( SYSTEM number ) "12" "1" ) "fizz" ¢ ( ( SYSTEM boolean ) "false" ) ( "a" "" ( ) "b" "c" ) )
# Convert byte strings to terminated form
( hello‡ ¢ ( ( SYSTEM‡ number‡ ) 12‡ 1‡ ) fizz‡ ¢ ( ( SYSTEM‡ boolean‡ ) false‡ ) ( a‡ ‡ ( ) b‡ c‡ ) )
# Convert ascents and descents
↓ hello‡ ¢ ↓ ↓ SYSTEM‡ number‡ ↑ 12‡ 1‡ ↑ fizz‡ ¢ ↓ ↓ SYSTEM‡ boolean‡ ↑ false‡ ↑ ↓ a‡ ‡ ↓ ↑ b‡ c‡ ↑ ↑
# Convert the construction indicator
↓ hello‡ € ↓ ↓ SYSTEM‡ number‡ ↑ 12‡ 1‡ ↑ fizz‡ € ↓ ↓ SYSTEM‡ boolean‡ ↑ false‡ ↑ ↓ a‡ ‡ ↓ ↑ b‡ c‡ ↑ ↑
# The same displayed without spaces
↓hello‡€↓↓SYSTEM‡number‡↑12‡1‡↑fizz‡€↓↓SYSTEM‡boolean‡↑false‡↑↓a‡‡↓↑b‡c‡↑↑</nowiki>

Then, the compression, which is also slightly modified:

<nowiki>
# (changes are called out with angle brackets)

# Replace €↓↓ with €
# (constructor implicitly starts with two descents)
↓hello‡<€↓↓>SYSTEM‡number‡↑12‡1‡↑fizz‡<€↓↓>SYSTEM‡boolean‡↑false‡↑↓a‡‡↓↑b‡c‡↑↑
↓hello‡<€ >SYSTEM‡number‡↑12‡1‡↑fizz‡<€ >SYSTEM‡boolean‡↑false‡↑↓a‡‡↓↑b‡c‡↑↑
↓hello‡€SYSTEM‡number‡↑12‡1‡↑fizz‡€SYSTEM‡boolean‡↑false‡↑↓a‡‡↓↑b‡c‡↑↑

# Wherever ‡ follows a byte and precedes [↑↓€], omit it as implicit.
# (Note that it must actually follow a byte—this doesn't apply with an empty string.)
↓hello<‡>€SYSTEM‡number<‡>↑12‡1<‡>↑fizz<‡>€SYSTEM‡boolean<‡>↑false<‡>↑↓a‡‡↓↑b‡c<‡>↑↑
↓hello< >€SYSTEM‡number< >↑12‡1< >↑fizz< >€SYSTEM‡boolean< >↑false< >↑↓a‡‡↓↑b‡c< >↑↑
↓hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↑↓a‡‡↓↑b‡c↑↑

# Remove initial ↓ and final ↑+
# (root is implicitly a list and is implicitly closed at any depth at the end)
<↓>hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↑↓a‡‡↓↑b‡c<↑↑>
< >hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↑↓a‡‡↓↑b‡c< >
hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↑↓a‡‡↓↑b‡c

# Replace ↑↓ with ↕
hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false<↑↓>a‡‡↓↑b‡c
hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false<↕ >a‡‡↓↑b‡c
hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↕a‡‡↓↑b‡c</nowiki>

This representation can be encoded as a list of integers by assigning values to all elements of the alphabet:

* A byte as its numeric value (0 .. 255)
* ‡ as 256
* ↓ as 257
* ↑ as 258
* ↕ as 259
* € as 260

Naturally, decompression reverses compression:

* Replace all ↕ with ↑↓.
* Add a ↓ at the beginning.
* Add a ↑ at the end.
** This is needed for the following step to work in all cases.
* Insert a ‡ after any byte value that is followed by ↑, ↓, or €.
* Replace all € with €↓↓.
* Finally, add an additional ↑ at the end for each remaining open list.

====List-requiring context====

List-requiring context accepts a list, a variable bound to a list, a function call evaluating to a list, or inlined elements ultimately consisting of a single element that is a list. Function calls are only evaluated where a @ is expanded; otherwise, everything is left alone.

* A list node is replaced by a list node consisting of the list-element-context values of its elements, with any ''intermediate subseq'' elements expanded.
* A unary $ is replaced by its value-context value, which is then evaluated.
* A unary # is replaced by its value-context value, which is then evaluated.
* A unary @ is replaced by its list-element-context value, which is then evaluated.
* All other input is illegal.

====List-element context====

This allows recursive expansion of @.

* For a unary @, its topic is evaluated in list-requiring context. If the resulting list contains exactly one element, evaluate to that element; otherwise, evaluate to an ''intermediate subseq'' containing all elements.
* Otherwise, a node evaluates to itself.

====Resolved context====

Note that bound names are lexically scoped. Expressions may need to be annotated with their scope of origin.

* Anything other than unary $ evaluates as itself.
* A unary $ is replaced by the resolved tree of its topic evaluated in key context (error if no such key), which is then evaluated.

===Sigils as used in expressions===

====<code>#</code> (Function call sigil)====

#''list''
// i.e.
#(''function-indicator'' ''param'' ''param'' ...)
#() -> #($(SYSTEM nop))

A function call sigil evaluates to the result of a function evaluated with zero or more parameters.

The first element of the list indicates which function to use. Theoretically, the first element should evaluate to a lambda function, but for notational convenience some other things are accepted. The rules are these:

* If the list is empty, it is replaced with a list containing the single element <code>$(SYSTEM nop)</code>.
* If the first list element evaluates to a lambda function, that function is used.
* If the first list element is a literal atom ''<code>a</code>'' such that <code>#(lookup ''a'' #(func (fullname) #(is-function $fullname)))</code> returns a non-empty name, the expansion of that name is used.
** Note that this applies only to literal string values; not to other expressions that evaluate to a string.
* Otherwise, the first list element is interpreted as a key ''<code>k</code>'' and the function indicated by <code>$''k''</code> is used; if this variable does not exist or is not a lambda function, an error occurs.

The list expression need not be literal (except within interpolated text, where <code>#(</code> is used as a lexical cue).

If the list expression is a (potentially infinite-length) stream, only as many elements are read as necessary to fill the function's formal parameters.

A function will, by default, allow more parameters to be passed than there are formal parameters to catch them. Some syntax should be introduced to catch the rest (the tail of the parameter list).

====<code>$</code> (Variable expand sigil)====

$''key''

Evaluates to the value of the variable with the given key as it exists in the current scope.

"Variable" here indicates that the named value need not remain the same between calls; a variable or parameter is read-only after being set for the first time, like a <code>final</code> variable in Java.

====<code>$</code> (Nonce sigil)====

$

Unfollowed by an expression, <code>$</code> evaluates to a new (previously unused) nonce value.

A ''nonce'' is a value whose only purpose is to be distinct from any previously generated nonces within this run. Other than supporting a test for equality, it is fully opaque and its internal representation is implementation-dependent (for example, a monotonic counter or a UUID generator could be used). Nonces have no meaningful order; particularly, an older one is not guaranteed to be less than or greater than a newer one.

Functions in Graut are modeled, and allowed to be memoized, as ''pure functions''; i.e., for any given set of (normalized) argument values, the same result is returned. Expecting a nonce as a parameter allows a function to return a different value for the same parameters, which is useful for activities with inherent state or other side effects, such as random number generation. For example, the function call <code>#($notSoRandom 0 10)</code> would have to return the same result every time, but a call like <code>#($random $ 0 10)</code> could return a different value every evaluation.

After it is generated, a nonce can be treated as a constant value. Consider the following:

#(def result #(* #($random $ 0 10) #($random $ 0 10)))
#(cat "first time: " $result " second time: " $result)

Even if the value of <code>$result</code> is always lazily expanded, as long as memoization is in place the same number will be printed in both places. Unlike a function call, the evaluation of <code>$</code> is always strict, so specific values are immediately inserted. One might imagine the definition in the above to be processed as something like the following:

#(def result #(* #($random ''ineffable-a'' 0 10) #($random ''ineffable-b'' 0 10)))
#(* #($random ''ineffable-a'' 0 10) #($random ''ineffable-b'' 0 10))

Then, the other call would expand to:

#(cat "first time: "
#(* #($random ''ineffable-a'' 0 10) #($random ''ineffable-b'' 0 10))
" second time: "
#(* #($random ''ineffable-a'' 0 10) #($random ''ineffable-b'' 0 10))
)

So, even though <code>$random</code> is (theoretically) being called anew every time <code>$result</code> is expanded, the same nonces are being used every time, and the same result is yielded.

(This is liable to lean most heavily on memoization. Implementations that support long-running programs will need to give some attention to avoiding memory leaks by figuring out when to discard stashed results.)

Care must be taken to ensure that <code>$</code> appears in places where it makes sense. No matter what the depth, each <code>$</code> is only ever given one value; in particular, a <code>$</code> appearing in the body of a function will have the same value each time that function is called. For distinct values on each call, the function should accept a nonce as a parameter.

A single nonce can be used to generate an arbitrarily long stream of nonces using the <code>#(nonces ''nonce'')</code> function; for example, given some single nonce you may wish to make multiple calls with distinct nonces.

// Let our input nonce be in $nonce
#(def nn #(take 3 #(nonces $nonce)))
#(def n1 #(element 0 $nn))
#(def n2 #(element 1 $nn))
#(def n3 #(element 2 $nn))
#(cat #($random $n1 0 10) #($random $n2 0 10) #($random $n3 0 10))

// Or, more idiomatically
#(
#(func (n1 n2 n3)
#(cat #($random $n1 0 10) #($random $n2 0 10) #($random $n3 0 10))
)
@#(nonces $nonce)
)

For any given <code>$nonce</code>, <code>#(nonces $nonce)</code> shall return exactly the same sequence of nonces each time it is called. The sequence is an infinitely long stream that is generated and memoized as necessary.

====<code>@</code> (Inlined elements sigil)====

@''list''
// i.e.
@(''elem'' ''elem'' ...) -> ''elem'' ''elem'' ...

An item with a <code>@</code> sigil is treated as a list whose elements are to be inlined.

<nowiki>
(A B @(C D E) F G) -> (A B C D E F G)</nowiki>

It is an error for the subject of a <code>@</code> to evaluate to anything other than a list.

In actuality, any list containing a <code>@</code> is treated as a notation for a call to <code>$(SYSTEM flatten)</code>. Any list containing at least one <code>@</code> item is implicitly converted using the following idiom:

If a list contains at least one <code>@</code> item, each non-<code>@</code> item in the list is converted to a <code>@</code> item by wrapping it in a list first:

<nowiki>
(A B @(C D E) F G) -> (@(A) @(B) @(C D E) @(F) @(G))
... or, since the elements don't technically need to be individual ...
(A B @(C D E) F G) -> (@(A B) @(C D E) @(F G))</nowiki>

Any list consisting ''only'' of <code>@</code> items can then be converted to a <code>$(SYSTEM flatten)</code> call by removing the <code>@</code> sigils and using the resulting items as arguments.

<nowiki>
(@(A) @(B) @(C D E) @(F) @(G)) -> #($(SYSTEM flatten) (A) (B) (C D E) (F) (G))
... or ...
(@(A B) @(C D E) @(F G)) -> #($(SYSTEM flatten) (A B) (C D E) (F G))</nowiki>

This effort would be entirely unnecessary if <code>@</code> worked only on literal lists, but it can be used on any list expression.

<nowiki>
( P Q @$r S @(T U)) ->
(@(P Q) @$r @(S) @(T U)) ->
#($(SYSTEM flatten) (P Q) $r (S) (T U))</nowiki>

Naturally, <code>@</code> can only be used within a list. In particular, it cannot be used as the subject of another sigil, but a list containing it can. For example, <code>#@(A B C)</code> doesn't make sense, but <code>#(A B C)</code> (or, equivalently, <code>#(@(A B C))</code>).

Optimizations apply for degenerate cases.
* Literal lists can be inlined as part of the parsing process.
* Whenever the expression <code>(@''item'')</code> is valid, it is exactly equivalent to <code>''item''</code>. (A call to <code>$(SYSTEM flatten)</code> is unnecessary, though it may still be necessary to validate that <code>''item''</code> evaluates to a list.)

Note that inlining a stream (which is potentially infinite-length) will cause the containing list to become a stream itself and will not force strict evaluation.

==Built-in functions==

See [[Graut/Standard library]].

@@ Line 70: / Line 70: @@
 =====Serialization=====
-The concept discussed at [[Cifl/Protocifl/Name-encoded_trees|Name-encoded trees]] is one possibility for a byte-string representation. That encoding is designed specifically for S-expressions with a list at the root and only byte strings and other lists as elements.
+See [[Graut/Serialized S-expressions]].
 ====List-requiring context====

@@ Line 260: / Line 260: @@
 #(extract (a? b*) ())			#(def a ())#(def b ())
 </nowiki>
 ==Built-in functions==
 See [[Graut/Standard library]].

@@ Line 70: / Line 70: @@
 =====Serialization=====
-The concept discussed at [[Cifl/Protocifl/Name-encoded_trees Name-encoded trees]] is one possibility for a byte-string representation. That encoding is designed specifically for S-expressions with a list at the root and only byte strings and other lists as elements.
+The concept discussed at [[Cifl/Protocifl/Name-encoded_trees|Name-encoded trees]] is one possibility for a byte-string representation. That encoding is designed specifically for S-expressions with a list at the root and only byte strings and other lists as elements.
 A special meta-representation could be used for typed information. To serialize a list like
@@ Line 150: / Line 150: @@
 hello€SYSTEM‡number↑12‡1↑fizz€SYSTEM‡boolean↑false↕a‡‡↓↑b‡c</nowiki>
-This representation can be encoded as a list of integers by assigning values to all elements of the alphabet:
+To encode exclusively with characters in the set [A-Za-z0-9_], this algorithm is provided:
 * A byte as its numeric value (0 .. 255)
-* ‡ as 256
+* ‡ as 357 (i.e., 260 + 'a')
-* ↓ as 257
+* ↓ as 358
-* ↑ as 258
+* ↑ as 359
-* ↕ as 259
+* ↕ as 360
-* € as 260
+* € as 361
 Naturally, decompression reverses compression:

@@ Line 74: / Line 74: @@
 A special meta-representation could be used for typed information. To serialize a list like
-  (hello #(int 12) fizz #(false) (a "" () b c))
+ <nowiki>
 First, we would evaluate the function calls. The resulting values aren't directly representable in source except as calls to a (possibly internal-only) deserialize routine:
    ("hello"
    	#( $((SYSTEM number) deserialize-internal) "12" "1" )
@@ Line 83: / Line 85: @@
 	#( $((SYSTEM boolean) deserialize-internal) "false" )
 	("a" "" () "b" "c")
+   )</nowiki>
 The problem is that these results are also function calls (aside from the fact that it's a tad verbose). Instead, let's say the (fictional) sigil `¢` represents an internal deserialization for a given type. Then, we have
    ("hello"
    	¢((SYSTEM number) "12" "1")
@@ Line 92: / Line 95: @@
    	¢((SYSTEM boolean) "false")
 	("a" "" () "b" "c")
+   )</nowiki>
 To serialize this, we'll use the a modified treename encoding with the alphabet: