_, ._ （ ・ω・） んも〜 ○=｛=｝〇, |:::::::::＼, ', ´ ､､､､し ､､､((（.＠）ｗｖｗｗＷＷｗｖｗｗＷｗｗｖｗｗｗｗＷＷＷｗｗＷｗ
ｗＷＷＷＷＷＷｗｗｗｗＷｗｗｖｗＷＷｗＷｗｗｖｗＷＷＷ
作ってみたｗｗｗｗｗ
とりあえず公開ｗｗｗｗｗｗｗっうぇ
つ 日本語
If you write another implementation of Grass, please let me know.
Grass is a functional grass-planting programming language. Syntax and semantics of Grass are defined based on (A-normalized, lambda lifted, and De Bruijn indexed) untyped lambda calculus and SECD machine [Landin 1964] respectively so that Grass is Turing-complete.
Grass was first proposed by Katsuhiro Ueno at the 39th IPSJ Jouho-Kagaku Wakate no Kai (symposium for young researcher of information science) in 2006 to introduce how to define a programming language in formal way.
Grass is a kind of esoteric programming language typified by BrainF*ck, but Grass has unique characteristics which any other esoteric ones don't have. For example:
Print "w" to standard output.
wWWwwww
Calculate 1 + 1 and print the result by the number of "w". This example consists of 3 functions. First one is 1 represented by lambda term (Church integer). Second one is addition operator of Church integer. Last one is main function. This program is equivalent to (λi.(λmnfx.m f (n f x)) i i OUT w) (λfx.f x).
wwWWwv wwwwWWWwwWwwWWWWWWwwwwWwwv wWWwwwWwwwwWwwwwwwWwwwwwwwww
ＹコンビネータｗｗＷＷｗｗＷｗｗｖちょｗｗＷＷＷｗＷＷＷｗｖおまｗＷＷｗＷｗｖ
無限ループ自重ｗＷｗ
ｗｗｗｗｖｗｖｗｗＷＷｗｖｗｗＷｗｗｖｗｗｗｗＷＷＷｗｗＷｗｗＷＷＷＷＷＷｗｗｗｗＷｗ ｗｖｗＷＷｗＷｗｗｖｗＷＷＷｗｗｗｗｗＷｗｗｗｗｗｗＷＷｗＷＷＷｗＷＷＷＷＷＷｗＷ ＷＷＷＷＷＷＷｗｗｗＷｗｗＷＷＷＷＷＷＷＷＷＷｗＷｗｗｗｗｗＷＷＷＷＷＷＷＷ ＷＷＷｗｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷ ｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗＷ ＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷＷ ＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗＷｗｗＷＷＷＷＷＷＷＷＷＷＷ ＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷｗｗｗｗ ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ ｗｗｗｗｗｗｗｗＷＷｗｗｗｗｗｗｗ ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ は ｗｗｗｗｗＷＷＷＷＷＷＷＷＷＷ ＷＷＷＷＷｗＷｗｗｗＷＷＷＷ わ い ＷＷＷＷＷＷＷｗｗｗＷｗｗＷＷ ＷＷＷＷＷＷＷＷＷＷｗｗｗｗ ろ は ｗＷｗｗｗｗｗｗｗＷＷＷＷＷＷＷ ＷＷＷＷＷＷＷＷＷＷｗｗｗｗ す い ｗｗｗＷｗｗＷＷＷＷＷＷＷＷＷ ＷＷＷＷＷＷＷＷＷｗｗｗｗｗ わ ｗｗｗｗＷｗｗＷＷＷＷＷＷＷＷ ＷＷＷＷＷＷＷＷＷＷＷＷＷ ろ ＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗ ｗｗｗｗｗＷｗｗＷＷＷＷＷＷＷ す ＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗ ｗｗｗｗｗｗｗＷｗｗｗｗｗｗｗｗｗ ｗｗｗｗｗｗＷＷＷＷＷＷＷＷＷ ＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ ｗｗｗｗｗｗＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷｗｗｗｗｗｗｗｗｗＷＷＷｗｗＷＷＷＷｗｗｗ ｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷＷＷｗｗＷＷＷＷＷＷｗｗｗｗＷＷＷＷＷＷＷｗｗＷＷＷ ＷＷＷＷＷｗｗｗｗＷＷＷＷＷＷＷＷＷｗｗＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗ ｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗ ｗｗｗｗｗＷｗｗｗＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷｗｗＷＷＷＷｗｗｗｗｗｗ ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷＷＷｗｗＷＷＷＷＷＷｗｗｗｗｗｗｗＷＷＷＷ ＷＷＷｗｗＷＷＷＷＷＷＷＷｗｗｗｗｗｗＷＷＷＷＷＷＷＷＷｗｗＷＷＷＷＷＷＷＷ ＷＷｗｗｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
A Grass program is written by using only "W", "w" and "v". Any other characters are ignored as comment. "W" and "v" appearing before first "w" are also ignored.
A Grass program consists of a list of top-level instructions separated by "v". The top-level instruction is either a function definition or a function application list. Every function definition starts with "w", and every function application list starts with "W".
Program : wwwwwWW ... wwWw v wwWWwW ... wWw v WWWwwwWw ... wwWWw v wW ... <---Function---> <--Function--> <--Applications-->
A function application list is a list of pairs of "W" sequence and "w" sequence. Every pair of "W" sequence and "w" sequence in a function application list denotes one function application, where the number of "W" is index of function and the number of "w" is index of argument.
Applications : WWWWWwwwwww WWWWWWwwwwwww ... WWWWwwww WW ... |<-5-><-6-->|<-6--><--7-->| | 4 4 | | | | | | | (5, 6) | (6, 7) | | (4, 4) | | apply | apply | | apply |
A function definition consists of a pair of arity and a function application list. The length of first "w" sequence of a function denotes arity of the function. What follows the arity is the function application list, that is, the function body. Note that only application may appear in function body; nested function is not allowed.
Function : wwwwww WWWWWwwwwww WWWWWWwwwwwww ... WWWWwwww v <-6-->|<--- Applications (function body) --->| | | | | | 6 args| (5, 6) | (6, 7) | | (4, 4) |end of | apply | apply | | apply |function
Grass interpreter is a kind of stack-based machine (similar to SECD machine). Grass interpreter maintains a stack of values (called as environment in formal definition) during evaluation. Any values calculated by Grass program are pushed to this stack. Unlike any other popular stack-based machines, in Grass, once a value is pushed to the stack, the value is never popped; the stack of Grass interpreter grows only. Every value in the stack is indexed by sequentially ascending positive integer from the top of the stack to the bottom. In other words, index N indicates N-th value from top of the stack. Each index of the function application pair indicates this index.
Value Stack : 1: value1 top of stack 2: value2 (1, 2) apply 3: value3 ^ ^ ... | argument is 2nd value from top. N: valueN | -------------- bottom of stack function is 1st value from top.
Evaluation of a Grass program is performed as follows:
Only "W", "w", and "v" are used for a Grass program. Fullwidth version of these characters ("Ｗ" (U+FF37), "ｗ" (U+FF57), and "ｖ" (U+FF56)) are also accepted so that they are identical to non-fullwidth version characters. Any other characters may appear in a Grass program but they are ignored.
First character of a Grass program must be "w". Both "W" and "v" appearing before first "w" are ignored like any other characters than "W", "w", and "v".
The syntax of Grass is defined by the following BNF notation. X^{+} means repeat of X more than 1 time, and X^{*} means repeat of X more than 0 time.
app denotes function application, and abs denotes function abstraction. Valid Grass program, ranged over by prog, is a list of app and abs separated by "v".
To make the definition accurate, first we define abstract syntax of Grass as follows:
where n is an positive integer, and ε and :: are general list constructor denoting nil and cons, respectively. Intuitively, I ranges over the set of instructions and C ranges over the set of instruction list.
Correspondence between concrete syntax defined in previous section and the abstract syntax is trivially defined as follows:
Additionally we define semantic object (ranged over f), environment (ranged over E), and suspended computation (ranged over D). D plays the same role as the dump of the SECD machine in Landin, so in what follows we call them dumps.
The operational semantics of Grass is defined through a set of rules to transform a machine configuration. A machine configuration is a triple (C, E, D) consisting of a code block C, an environment E, and a dump D. We write
if (C, E, D) is transformed to (C', E', D'). The reflexive transitive closure of → is denoted by →^{*}.
Here is the set of transformation rules.
The top-level evaluation relation is defined as follows.
where E_{0} is initial environment defined in Primitives section, C_{0} is Grass program intended to be evaluated, and D_{0} is the initial dump such that
If (C_{0}, E_{0}, D_{0}) ↛^{*} (ε, f :: ε, ε), then evaluation is stuck or never terminated.
We define initial environment E_{0} for current version of Grass as follows. In future version, more primitives may be defined in the initial environment.
where Out, Succ, w, and In are primitives.
Primitives may have special behaviour and some side-effects. Although they cannot be described in pure lambda-calculus, we assume that every primitive is somehow encoded in the same manner as ordinary semantic object and behaves like ordinary function in the operational semantics. How to implement primitives are out of this document.
A value denoting an "w" character (code 119). Usually, a character is used as an argument for Out and Succ primitive, or is a return value of In primitive.
A character also performs as a function which returns equality between 2 characters; it takes an argument, and returns true of Church Boolean (λx.λy.x) if the argument is a character and is equivalent to the applied character, otherwise returns false of Church Boolean (λx.λy.y).
Take a character as argument, print it to standard output, and return the given character. If the argument is not a character, evaluation will be aborted.
Take an arbitrary value as argument, read a character from standard input, and return it. If input reaches end of file, return the argument.
Take a character (code n) as argument and return its next character (code n+1) if n < 254. if n = 255, return a null character (code 0). If the argument is not a character, evaluation will be aborted.
（あとで書く）
Start from untyped lambda calculus.
Perform CPS Transformation.
Perform Inverse CPS Transformation.
Perform Lambda Lifting so that all functions are to be at top-level.
Translate every variable name into de Bruijn Index.
Plant grasses over this calculus. That's all.
Web pages related to Grass.
Other functional esoteric programming languages.