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

    _, ._
  ( ・ω・) んも〜
  ○={=}〇,
   |:::::::::\, ', ´
、、、、し 、、、(((.@)wvwwWWwvwwWwwvwwwwWWWwwWw

wWWWWWWwwwwWwwvwWWwWwwvwWWW

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

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

実装

インタプリタ

コンパイラ

開発環境

Grass実装したら教えれ.

なにこれwwwwwww

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

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

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

サンプルwwwwwww

無限に草植えときますねwWWwwwwWWww

YコンビネータwwWWwwWwwvちょwwWWWwWWWwvおまwWWwWwv

wwwwvwvwwWWwvwwWwwvwwwwWWWwwWwwWWWWWWwwwwWw
wvwWWwWwwvwWWWwwwwwWwwwwwwWWwWWWwWWWWWWwW
WWWWWWWwwwWwwWWWWWWWWWWwWwwwwwWWWWWWWW
WWWwwwwwWWWWWWWWWWWWwwwwWWWWWWWWWWWWW
wwwWWWWWWWWWWWWWWwwwWWWWWWWWWWWWWWWwW
WWWWWWWWWWWWWWWWWwwwWwwwwwwwwwwwwwwWWWW
WWWWWWWWWWWWWWWwwwwwwwwWwwWWWWWWWWWWW
WWWWWWWWWWWWWwwwwwwwwwwwwwwwwwwwwwwwwWwwww
wwwwwwwwwwwwwwwww             wwwwwwwwWWwwwwwww
wwwwwwwwwwwwwwwww          は   wwwwwWWWWWWWWWW
WWWWWwWwwwWWWW    わ   い   WWWWWWWwwwWwwWW
WWWWWWWWWWwwww    ろ   は    wWwwwwwwwWWWWWWW
WWWWWWWWWWwwww    す   い   wwwWwwWWWWWWWWW
WWWWWWWWWwwwww     わ       wwwwWwwWWWWWWWW
WWWWWWWWWWWWW    ろ       WWWWWWWWWwwwwww
wwwwwWwwWWWWWWW    す       WWWWWWWWWwwwwww
wwwwwwwWwwwwwwwww             wwwwwwWWWWWWWWW
WWWWWWWWwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwWwwwwwwwwwwwwwwWWwwwwwwwwwWWWwwWWWWwww
wwwwwwwwwwwwWWWWWwwWWWWWWwwwwWWWWWWWwwWWW
WWWWWwwwwWWWWWWWWWwwWWWWWWWWWWwwwwwwwww
wwwwWWWWWWWWWWWWWWWWWWWWWWWWWWWWwwwwww
wwwwwWwwwWWwwwwwwwwwwwwwwwwwwWWWwwWWWWwwwwww
wwwwwwwwwwwwwwwwwwWWWWWwwWWWWWWwwwwwwwWWWW
WWWwwWWWWWWWWwwwwwwWWWWWWWWWwwWWWWWWWW
WWwwwwwwWWWWWWWWWWWwwwwwwwwwwwwwwwwwwwwwww

せつめいwwwwwww

使う文字はW,w,vの3つだけ.それ以外の文字は無視ね.最初のwより前の文字も全ての無視.

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

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

Wとwがペアになって1つの関数適用を表します.Wの数が呼び出す関数を指していて,wの数がその関数に与える引数を指しています.

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

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

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, …と番号が振られていて,この番号でスタックから値を取り出すことができます.関数適用のWとwの数は,この番号を表しています.

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. プログラムの終わりに当たったら,スタックの一番上の値を関数として取り出し,その関数自身を引数としてその関数を呼び出します.この関数の実行が終わったら終了です.

形式的定義wwwwwww

厳密なのは英語で書いた

文法

使う文字はW,w,vの3つで,全角でも半角でもおk.その他の文字は無視.

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

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

操作的意味論

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

ここでnはwとかWとかの数を表す整数ね.

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

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

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

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

ここで,C0は実行しようとしているプログラム, E0は初期環境(プリミティブ参照), D0はコレ↓

プリミティブwwwwwww

初期環境E0はこんな感じ.

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

w
文字"w"(コード119). 普通はOutやSuccの引数として使う. 関数として呼び出こともできて,引数が同じ文字ならtrue(λx.λy.x),そうでなければfalse(λx.λy.y)を返す.
Out
文字を表示する関数.引数をそのまま返す.
In
文字を入力する関数.入力された文字を返す.EOFなら引数をそのまま返す.
Succ
次の文字を返す関数.ただし255の次は0.

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

型無しラムダ計算を

CPS変換して,

逆CPS変換して,

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

de Bruijn Index化して,

あとは草を生やすだけwwwww

Grass関係.

関数型言語のなかま.

履歴とかwwwwwww


© 2006, 2007 UENO Katsuhiro.
stylesheet prints mail address here.