プログラミング言語として最低の体裁は備えているが、これ以上は小さくできないようなモノを考えてます。とはいえ、「これ以上小さくできない」はかなり主観的な判断になります。ここでは、「実在する通常のプログラミング言語に類似の構文」の範囲で考えます。シェファーのストロークとかコンビネータのようなエキゾチックな演算は持ち出しません。
次のエントリーと関連しますが、いちおう独立です。
制御構造
if-then-elseとwhileの2つがあれば十分でしょう。if-thenは、「else 何もしない」で代用。あっ、そうだ、順次実行は;（セミコロン）。
論理式
if文もwhile文も条件判断部分で論理式を使うので、論理式の構文は必要です。これも、論理演算&&（AND）、||（OR）、!（NOT）、それと定数true, falseがあれば十分。
現状のプログラミング言語のAND、ORは、「P && Q ≡ Q && P」が成立しなかったりするのですが、そのへんはまー、あんまり気にしない方向で。
実行文
なにはなくても「何もしない」が必須。これはskipとしておきます。「何もしない」なら「何も書かない」というのもあるけど明示的に書いたほうがわかりやすい。それと、プログラムを自己破綻させるhang。
- if-thenは、if (P) then S else skip
- 論理式Pでガードされた文Sは、 if (P) then S else hang
型
論理式があるから、Boolean型は必要。実行文は値を返さないからVoid型。Void型はただひとつの値（undefinedにしましょう）を持つとします。skip、hangなどの文も一種の関数だとみなすと、その型はVoid→Void（Void引数、Void戻り値）となります。順次結合「;」は、(Void→Void),(Void→Void) → (Void→Void) の“関数”になりますね、if-then-else/whileなら、Boolean, (Void→Void) → (Void→Void)。
この極小言語は強く型付けすることにします。
変数と代入文
普通。
定義能力
常識的な手続き／関数定義はできるとしましょう。新しい型を作り出す能力はないとします。ただし、任意の型を受け入れる能力はアリにします（後述、ライブラリのところ）。
まとめ
- 型：Boolean, Void（値はundefined）
- 論理式：&&, ||, !, true, false
- 文： skip, hang
- 変数と代入文： 普通
- 制御構造：;, if-then-else, while
- 手続き／関数定義：普通
ライブラリ
整数も文字列もないし、入出力も使えないのか？ -- そういうのは全部ライブラリでサポートってことにしましょう。ライブラリとは：
- 型
- 型付け（typing）された手続き／関数
の集まりです。例えば：
- 型：Natural
- 手続き／関数：zero:Void→Natural, isZero:Natural→Boolean, succ:Natural→Natural, pred:Natural→Natural
というライブラリが与えられて、名前の印象のとおりの機能を提供するなら、自然数の足し算は次のように定義できます（構文はJavaScript風）。再帰（recursion）と繰り返し（repetition）の2種類を。
function sum_rec(n:Natural, m:Natural):Natural {
if(isZero(n)) {
return m;
} else {
return succ(sum_rec(pred(n), m));
}
}function sum_rep(n:Natural, m:Natural):Natural {
var k:Natural = n;
var r:Natural = m;
while (!isZero(k)) {
k = pred(k);
r = succ(r);
}
return r;
}
何がおもしろい
プログラミング言語をうんと小さくするのは、ライブラリのほうにフォーカスしたいからなんです（僕の動機は）。ライブラリが使いやすくリッチだったら言語能力が貧弱でもなんとかなるような気がします。その「気がします」という感覚を確かめてみたいんです。
それと、これくらい単純だと、ブール代数とクリーネ代数の算術的計算*1だけで意味論が作れるし、ホーア式での検証も（がんばれば）できなくもないですね。ようするにオモチャとしては遊びやすいシロモノだってことです。
*1:より正確にはHorn論理式の範囲の計算
