ちょっと草植えときますね型言語 Grass

　　　　_, ._
　　（　・ω・）　んも〜
　　○=｛=｝〇,
　 　|:::::::::＼, ', ´
､､､､し ､､､((（.＠）ｗｖｗｗＷＷｗｖｗｗＷｗｗｖｗｗｗｗＷＷＷｗｗＷｗ

ｗＷＷＷＷＷＷｗｗｗｗＷｗｗｖｗＷＷｗＷｗｗｖｗＷＷＷ

作ってみたｗｗｗｗｗ
とりあえず公開ｗｗｗｗｗｗｗっうぇ

日本語版はてきとーです．きっと英語版のほうが詳しいです．

実装

インタプリタ

• Interpreter written in Standard ML (accept US-ASCII only) by UENO Katsuhiro
• Interpreter written in Ruby by UENO Katsuhiro
• Interpreter written in ニコスクリプト
• Interpreter written in Prolog by zick
• Interpreter written in Java by tobi
• Interpreter written in Scheme by Higepon(Taro Minowa)
• Interpreter written in Python by NISHIO Hirokazu

コンパイラ

• Compiler from Grass to Scheme written in Scheme (accept US-ASCII only) by UENO Katsuhiro

開発環境

• grass.el for Emacsen, including an interpreter written in Emacs Lisp, by irie

Grass実装したら教えれ．

なにこれｗｗｗｗｗｗｗ

草を植えるための関数型プログラミング言語です．

型無しラムダ計算がベースになってます．

BrainF*ckとかあの辺の言語の仲間です．たぶん．

サンプルｗｗｗｗｗｗｗ

無限に草植えときますねｗＷＷｗｗｗｗＷＷｗｗ

ＹコンビネータｗｗＷＷｗｗＷｗｗｖちょｗｗＷＷＷｗＷＷＷｗｖおまｗＷＷｗＷｗｖ

ｗｗｗｗｖｗｖｗｗＷＷｗｖｗｗＷｗｗｖｗｗｗｗＷＷＷｗｗＷｗｗＷＷＷＷＷＷｗｗｗｗＷｗ
ｗｖｗＷＷｗＷｗｗｖｗＷＷＷｗｗｗｗｗＷｗｗｗｗｗｗＷＷｗＷＷＷｗＷＷＷＷＷＷｗＷ
ＷＷＷＷＷＷＷｗｗｗＷｗｗＷＷＷＷＷＷＷＷＷＷｗＷｗｗｗｗｗＷＷＷＷＷＷＷＷ
ＷＷＷｗｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷ
ｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗＷ
ＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷＷ
ＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗＷｗｗＷＷＷＷＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ　　　　　　　　　　　　　ｗｗｗｗｗｗｗｗＷＷｗｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ　　　　　　　 　 は　　 ｗｗｗｗｗＷＷＷＷＷＷＷＷＷＷ
ＷＷＷＷＷｗＷｗｗｗＷＷＷＷ　　　　わ　　　い　　 ＷＷＷＷＷＷＷｗｗｗＷｗｗＷＷ
ＷＷＷＷＷＷＷＷＷＷｗｗｗｗ　　　　ろ　　　は　　  ｗＷｗｗｗｗｗｗｗＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷＷＷｗｗｗｗ　　　　す　　　い　　　ｗｗｗＷｗｗＷＷＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷＷｗｗｗｗｗ　　　　 わ　　　　　　　ｗｗｗｗＷｗｗＷＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷＷＷＷＷＷ　　　　ろ　　　　　　　ＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗ
ｗｗｗｗｗＷｗｗＷＷＷＷＷＷＷ　　　 す　　　　　　　ＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗ
ｗｗｗｗｗｗｗＷｗｗｗｗｗｗｗｗｗ　　　　　　　　　　　　 ｗｗｗｗｗｗＷＷＷＷＷＷＷＷＷ
ＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ｗｗｗｗｗｗＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷｗｗｗｗｗｗｗｗｗＷＷＷｗｗＷＷＷＷｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷＷＷｗｗＷＷＷＷＷＷｗｗｗｗＷＷＷＷＷＷＷｗｗＷＷＷ
ＷＷＷＷＷｗｗｗｗＷＷＷＷＷＷＷＷＷｗｗＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗ
ｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗ
ｗｗｗｗｗＷｗｗｗＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷｗｗＷＷＷＷｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗＷＷＷＷＷｗｗＷＷＷＷＷＷｗｗｗｗｗｗｗＷＷＷＷ
ＷＷＷｗｗＷＷＷＷＷＷＷＷｗｗｗｗｗｗＷＷＷＷＷＷＷＷＷｗｗＷＷＷＷＷＷＷＷ
ＷＷｗｗｗｗｗｗＷＷＷＷＷＷＷＷＷＷＷｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

せつめいｗｗｗｗｗｗｗ

使う文字はＷ，ｗ，ｖの3つだけ．それ以外の文字は無視ね．最初のｗより前の文字も全ての無視．

Grassはラムダ計算がベースになっている言語なので，関数定義と関数適用の2つの操作しかありません．関数定義や関数適用はｖで区切って書きます．ｖで区切ったもののうち，ｗから始まるのが関数定義で，Ｗから始まるのが関数適用です．関数適用が続く場合はｖで区切らなくてもおｋ．

Program :
    wwwwwWW ... wwWw v wwWWwW ... wWw v WWWwwwWw ... wwWWw v wW ...
    <---Function--->   <--Function-->   <--Applications-->

Ｗとｗがペアになって1つの関数適用を表します．Ｗの数が呼び出す関数を指していて，ｗの数がその関数に与える引数を指しています．

Applications :
     WWWWWwwwwww WWWWWWwwwwwww ... WWWWwwww WW ...
    |<-5-><-6-->|<-6--><--7-->|   |  4  4  |
    |           |             |   |        |
    |  (5, 6)   |  (6, 7)     |   | (4, 4) |
    |   apply   |   apply     |   |  apply |

関数定義では，引数の数を表すｗの列に，関数の本体が続きます．関数の本体に書けるのは関数適用だけです．

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はスタックマシンの一種です（SECDマシンに似てます）． 値が入るスタックがあり，関数適用の結果がこのスタックに積まれていきます．スタックの中の値にはスタックの一番上から順番に1, 2, …と番号が振られていて，この番号でスタックから値を取り出すことができます．関数適用のＷとｗの数は，この番号を表しています．

Value Stack :

   1: value1    top of stack
   2: value2                          (1, 2) apply
   3: value3                           ^  ^
   ...                                 |  引数は2に入ってる．
   N: valueN                           |
 -------------- bottom of stack      関数は1に入ってる．

Grassプログラムの実行は以下のルールで行います．

1. プログラムの実行が始まる前にスタックをプリミティブで初期化します．
2. プログラムや関数本体の実行は，先頭から，左から右の順で行います．
3. 関数定義に当たったら，現在のスタックとその関数定義からクロージャを作り，スタックにプッシュします．
4. 関数適用に当たったら，スタックから関数と引数を取ってきて，関数を呼び出し，返り値をスタックにプッシュします．関数本体の実行は，クロージャに保存されていたスタックを使って行います．引数は，関数本体が実行される前に，スタックにプッシュされます．
5. 関数の終わりに当たったら，スタックの一番上の値を返り値として取り出して，呼び出し元に戻ります．
6. プログラムの終わりに当たったら，スタックの一番上の値を関数として取り出し，その関数自身を引数としてその関数を呼び出します．この関数の実行が終わったら終了です．

形式的定義ｗｗｗｗｗｗｗ

厳密なのは英語で書いた．

文法

使う文字はＷ，ｗ，ｖの3つで，全角でも半角でもおｋ．その他の文字は無視．

プログラムは最初のｗから始まる．それより前にある文字は全て無視．

文法は以下の通り．progがプログラム全体．

• app ::= W⁺ w⁺
• abs ::= w⁺ app^*
• prog ::= abs | prog v abs | prog v app*

操作的意味論

上の文法はもうちょっと見やすいカタチ（抽象構文）にまとめることができて，

• I ::= App(n, n) | Abs(n, C)
• C ::= ε | I :: C

ここでnはｗとかＷとかの数を表す整数ね．

意味論の定義には草植えてるような構文の代わりにこっちを使う．

Grassの抽象機械は，実行するコードC，環境E，リターン先を覚えておくスタックDを持っていて，ある時点での機械の状態を (C, E, D) と書くことにする．また，実行が1ステップ進んで機械の状態が変わることを (C, E, D) → (C', E', D') と書く．→の繰り返しを→^*と書く．

→を以下のように定義する．

• (App(m, n) :: C, E, D) → (Cm, (Cn, En) :: Em, (C, E) :: D) where E = (C₁, E₁) :: (C₂, E₂) :: … :: (C_i, E_i) :: E' (i = m, n)
• (Abs(n, C') :: C, E, D) → (C, (C', E) :: E, D) if n = 1
• (Abs(n, C') :: C, E, D) → (C, (Abs(n - 1, C')::ε, E) :: E, D) if n > 1
• (ε, f :: E, (C', E') :: D) → (C', f :: E', D)

Grassプログラムの実行はこの機械の上でこんな感じに行う．

• (C₀, E₀, D₀) →^* (ε, f :: ε, ε)

ここで，C₀は実行しようとしているプログラム， E₀は初期環境（プリミティブ参照）， D₀はコレ↓

• D₀ = (App(1, 1)::ε, ε) :: (ε, ε) :: ε

プリミティブｗｗｗｗｗｗｗ

初期環境E₀はこんな感じ．

• E₀ = Out :: Succ :: w :: In :: ε

各プリミティブの説明は以下の通り．

w

文字"w"（コード119）． 普通はOutやSuccの引数として使う． 関数として呼び出こともできて，引数が同じ文字ならtrue（λx.λy.x），そうでなければfalse（λx.λy.y）を返す．

Out

文字を表示する関数．引数をそのまま返す．

In

文字を入力する関数．入力された文字を返す．EOFなら引数をそのまま返す．

Succ

次の文字を返す関数．ただし255の次は0．

ラムダ計算からGrassに至るまでｗｗｗｗｗｗｗ

型無しラムダ計算を

• e ::= x | λx.e | e e

CPS変換して，

• t ::= x | λx.r
• c ::= k | μx.e
• e ::= r c | x x c | c t
• r ::= δk.e

逆CPS変換して，

• e ::= x | λx.r | x x
• r ::= e | let x = e in r

lambda liftingとか使って全ての関数をトップレベルに集めて，

• e ::= x | x x
• m ::= e | let x = e in m
• f ::= λx.f | λx.m
• r ::= e | let x = f in r | let x = e in r

de Bruijn Index化して，

• n ::= • | n ↑
• e ::= n | n n
• m ::= e | let e in m
• f ::= λf | λm
• r ::= e | let f in r | let e in r

あとは草を生やすだけｗｗｗｗｗ

リンクｗｗｗｗｗｗｗ

Grass関係．

• Grassコミュ in mixi

関数型言語のなかま．

• Unlambda
• Iota and Jot (Internet Archive)
• Lazy K

履歴とかｗｗｗｗｗｗｗ

• 2007-10-04: 日本語で書いた．