Oiseau

Oiseauはラムダ計算、またはコンビネータ論理に基づくプログラミング言語です。
Oiseauの特徴は以下の通りです。

マクロ定義: コンビネータはマクロとして実装されています
ベータ簡約
正格(strict)または非正格(nonstrict)な式の評価
T[]変換

使用方法

node.js

npmよりダウンロードできます。

npm install -g oiseau

コマンドラインより"oiseau"とタイプすることでREPLを実行できます。

$ oiseau
Oiseau Ver. 1.0.0
> SKK
^a.a

リファレンス

式の要素

変数

変数は小文字のラテンアルファベット、またはそれに続く数字からなります。
例えば、xやx27は有効な変数名です。

マクロ

マクロは大文字のラテンアルファベット、またはそれに続く数字からなります。
マクロ名には[と]に囲まれた、[,],=を除く文字でも構成できます。
例えば、S、S27や[Cons]は有効なマクロ名です。

表示式

表示式は与えられた文字列をログに出力する副作用を持つ恒等関数です。
表示式は<、>を除く任意の文字、>の列からなります。
副作用は式を評価するときのみ使用され、ベータ簡約では無視されます。

<Hello, world>

ブロック式

式の列を(,)で囲むことで評価の順序を変えることができます。

式の種類

ラムダ式

ラムダ式は^、変数名のリスト、.、式のリストからなります。

^xyz.xz(yz)

^の代わりにギリシャ文字のλも使用できます。

マクロ定義

マクロはラムダ式の前にマクロ名と=または:=を置くことで定義できます。
マクロ名に空白を含まなければ、囲む[,]は省略できます。
マクロは再定義できません。

True = ^xy.x
[this is false] = ^xy.y

チャーチ数

自然数はチャーチ数として認識されます。
例えば、数字2は^ab.a(ab)として解釈されます。

式の評価

ベータ簡約

単純に式を入力することで、式をベータ簡約することができます。

> SKK
^a.a

正格な評価

式を評価したいときは、式の前に`を追加します。
下記の例は、"Hello, world."をログに追加します。

> `<Hello, world.>I
Hello, world.
^ab.a

非正格な評価

`の代わりに``を使用することで、非正格な評価ができます。

T[]変換

式をSKIコンビネータに変換したいときは、式の前に"@"を追加します。 SKIコンビネータはログに出力されます。

> @SKK
I
^ab.a

定義済みマクロ

下記のマクロは定義済みです。

S = ^xyz.xz(yz)
K = ^xy.z
I = ^x.x
T = ^xy.x
F = ^xy.y
Cons = ^cdf.fcd
Car = ^p.pT
Cdr = ^p.pF
Isnil = ^x.x(^abc.F)T

Oiseauの文法

input:
    macro |
    evaluation

macro:
    macro-definition-name macro-eq expression-list

macro-definition-name:
    <characters except "=", "[", "]", or space> |
    "[" <characters except "=", "[", or "]"> "]"

macro-eq:
    "=" | ":="

evalation:
    expression-list "==" expression-list |
    "``" expression-list |
    "`" expression-list |
    "@" expression-list

expression-list:
    "(" expression-list ")" |
    lambda-clause |
    variable-name |
    macro-name |
    "<" <characters except ">"> ">" |
    "[[" list "]]" |
    number

lambda-clause:
    lambda-mark variable-list "." expression-list

lambda-mark:
    "^" | "λ"

variable-list:
    variable-name variable-list |
    variable-name

variable-name:
    "a" .. "z" ("0" .. "9")*

macro-name:
    "A" .. "Z" (("0" .. "9")+ | "*"+)? |
    "[" <characters except "=", "[", or "]"> "]"

list:
    lambda-clause list |
    lambda-clause "|" lambda-clause |
    lambda-caluse

number:
    ("0" .. "9")+