JavaScript
TypeScript
ラムダ計算

関数こそ、数値、オブジェクト、配列……そういうあらゆる垣根を乗り越え語り合える、共通の言語なのだ!

More than 3 years have passed since last update.

本テキストはJavaScriptでnumberstringnewifforも配列もプロパティへのアクセスもまったく使わず、ただ1引数の関数の定義と呼び出しを自在に組み合わせることで真偽値をはじめ数値やリストといったあらゆるデータ型を作り出し、それらの値を使って計算を行う手法を紹介するものです。紹介するソースコードはラムダ計算やチャーチエンコーディングと呼ばれているものをJavaScript/TypeScriptで実装したもので、計算の結果を人間に読みやすいよう入出力するためだけに限って関数以外の機能も使いますが、入出力以外のソースコードはすべて関数定義および関数適用のみからできています。まさに純粋のなかの純粋な関数プログラミング、究極のシンプルプログラミングとでも言えるものです。

本テキストでは説明にJavaScript/TypeScriptを使って説明はしていますが、特にこれらの言語に馴染みがなくても理解のためには問題ないと思います。オブジェクト指向言語とはいってもクラスやオブジェクトといった概念はほとんど登場しないので、オブジェクト指向が苦手な皆様にも大変お勧めの記事となっています。ただし、本テキストで解説されている知識はほぼ純粋に理論的背景に対する関心に基づくものであり、残念ながら 実用性はほとんどゼロ であることをご了承の上で閲覧頂くようお願い申し上げます(でもTupleEitherなんかはたぶん実用上もそれなりに役に立つと思いますよ!)。

お勧めの読者層
  • 『関数』っていうのを聞いたことある人
  • 順次、反復、分岐の3要素がプログラミング言語の言語仕様には必要だと信じている人
  • プログラミング言語の言語仕様はシンプルなほど美しいと思ってる人
  • staticおじさん
そもそもなぜJavaScriptで?

本テキストで扱う『ラムダ計算』は紙の上でやってもいいのですが、手計算すると非常に間違えやすく面倒です。ラムダ計算はある種のプログラミング言語であるとも理解できますので、専用のコンパイラやインタプリタなら幾つかありますが、JavaScriptならブラウザで誰でもすぐに実行を試せますし、必要ならデバッガで処理の途中の状態を覗き見ることができます。JavaScriptは関数を第一級の対象として比較的扱いやすい言語であるという理由もあります。さらに、TypeScriptを使うと静的な型注釈を書けるので、説明をしやすいのです。

また、単純なラムダ計算の記法はとても可読性が低く、それによる学習効率の低下があまりに大きいのではないかと思います。既存のプログラミング言語のフレームワーク上で適切な関数名や適切な型注釈を用いることで、とても理解しやすい形でラムダ計算を学ぶことができるのではないかと考えています。

オブジェクトなんか、なくていいっ……!リテラルもいらないっ……!関数っ……!書かせてくれよっ……!ごく普通の定義……適用……!

はじめに今回使う材料について説明しておきます。使うものは基本的に次の3種類です。

関数の定義

function NAME ( ARG ){ return EXPR ; }

この定義は NAME(ARG) を式 EXPR に置き換えることを示します。関数名の NAME は省略されることもあり、その場合は無名関数となります。いくつか簡単なルールを決めておきます。

  • かならず1引数の関数とします。
  • 返り値もvoidではなく必ず何かあるものとします。
  • ひとつの関数内にステートメントはひとつだけです。セミコロンで区切って複数書くことは必要ないのでしません。
  • functionreturn というキーワードが冗長なので、代わりに ARG => EXPR という TypeScript のシンタックスシュガー(アロー関数式)を使うこともあります。ARG => EXPR もコンパイル後は function(ARG){ return EXPR; } という形式になるので意味はまったく同じです。

関数適用

FUNC(EXPR)

関数のあとに括弧と、その括弧のなかに任意の式を書けば関数の適用です。FUNCEXPRは関数名や引数のときもありますし、関数適用の式やfunction式であることもあります。

優先順位の括弧

( EXPR )

関数適用の優先順位を示すための括弧も使うときがあります。関数適用の括弧と非常に紛らわしいので、心の目を鍛えてください。とくに、アロー関数式と一緒によく使います。次のアロー関数式、

x => y(z)

は『引数 x をとり、y(z) を返す無名関数』を意味しており、あえて優先順位を示す括弧を付け加えると

x => (y(z))

となります。次のような

(x => y)(z)

という『引数 x をとり y を返す無名関数に、z を適用する』という意味ではないことに注意してください。言い換えれば、前者の式の場合は優先順位の括弧を省略できますが、後者の式の場合は明示的な優先順位の括弧が必要になります。他にも、長めの式の途中で改行したいときに全体を優先順位の括弧で囲むことで、ひとつの大きな式であることを示すためにも使います。

これで必要なものは揃いました。あとはコメントや型注釈くらいは自由に使いますが、プログラムの振る舞いに関するものはこれですべてです。最初に述べたとおり、booleannumberstringも一切使わず、全部自力で定義していきます。でもこれから記述していくコードはすべてJavaScript/TypeScriptのサブセットなので、ブラウザなどで実際に実行して試すことができます。

さあ、いけっ……!もう一度漕ぎ出せっ……!勝負の大海へっ……!

さて、いよいよ関数だけからなる青き清浄なる世界の構築を始めるときがきましたが、まず何をしたらいいでしょうか。関数以外の既存のあらゆるデータ型、あらゆるオブジェクトは存在しません(使用禁止)ので、まだ文字列はおろか整数や真偽値もありません。関数は使えますが、まだひとつも関数が定義されていないので呼び出せる関数もありません。となれば、なんでもいいのでまず何か新たな関数を定義してみるのが良さそうです。仮に f という名前でひとつ関数を定義してみましょう。

function f(x){
    return ????? ;
}

さて、return文に何か式を書かないと関数の定義は完成しませんが、いったい何を書いたらいいでしょうか?おそらく真っ先に思いつくのは、たった今受け取ったばかりの引数 x をそのまま返すことでしょう。そうすると、この関数は値を同じ値に移す 恒等関数 となります。値をそのまま返すだけではあまり役に立ちそうにないと思うかもしれませんが、実はこの関数もとても大事な関数です。世界で最もシンプルな関数、関数の中の関数とでもいえるようなすごい関数です。fなんていういい加減な名前ではあまりにかわいそうなので、もう少し良い名前を付けてあげましょう。ここではこの関数をunitと呼ぶことにします(恒等関数はふつうidentity functionですけど、ここでいうunitとは単位集合の意味だと考えるといいと思います)。

function unit(x){
    return x ;
}

つまり、unit(x) というような式があったら、 x へと書き換えることができます。

unit(x) = x

ちなみに、この関数に型注釈をつけるとどうなるでしょうか。引数の型や返り値の型は?まだ何も型は定義されていませんから、具体的な型を指定することはできません。型変数を導入してxの型を示すとよいでしょう。TypeScriptでは次のように関数名のあとに <T> とすると、型変数 T を新たに導入することができます。unit は引数をそのまま返しますから、返り値も T になります。

function unit<T>(x: T): T {
    return x ;
}

型変数の実際の型は、その関数が使われたときに決定されます。たとえば、unit(10) という式における unit の型は unit(x: number): number ですし、unit("a") なら unit(x: string): string と引数の値によって自動的に選択されることになります。もしnumberstring があれば、の話ですが。我々の世界にはまだそれすらありません。

ソースコードを理解しやすくするために、今後はなるべく型注釈もつけることにしましょう。こうした定義や計算を行っていると、この式の値は何を表しているのかわからなくなってくることがよくあります。なにしろすべて関数ですから、instanceofで調べるだとかいうこともまったく不可能です(ポジティブに考えれば、instanceofで型を調べる必要がまったくないともいえます)。TypeScript形式で型注釈をつけていきますが、とりあえず関数の型注釈の書き方だけわかれば、その他のTypeScriptについての知識はなくても大丈夫です。なにしろ関数しか出てきませんからね。

値は返す……!値は返すが……まだその時の指定まではしていない。そのことをどうか諸君らも思い出していただきたい……!つまり……bottomがその気になれば、値の受け渡しは∞年後ということも可能だろう……ということ……!

これで最初の関数 unit が手に入りました。でも、この関数はそのまま値を帰すだけですから、これだけではなにか役に立つ計算はできそうにありません。何かほかに関数の定義はできないでしょうか。先ほどのように f を考えます。fが定義され、x があるのですから、f(x) というように適用することができます。これをfの返り値として返したらどうなるでしょうか。

function f(x) {
    return f(x) ;
}

この関数はいつも自分自身を呼び出しているので、f(x) はそのまま f(x) に書き換わります。つまり、決して関数呼び出しが終わることはありません。

f(x) = f(x) = f(x) = f(x) = f(x) = ...

このコードを実際に実行すると、現実にはリソースは有限ですからスタックオーバーフローでエラーになるでしょう。絶対にエラーになる関数なんて定義して何の役にたつのかと思うでしょうけれど、ひとまず型注釈を付けてその正体を探ってみましょう。

引数は適当に型変数 T を導入して表すとして、問題はこの関数の返り値です。f(x) を返すのですから、そのfの返り値の型を知らなければなりません。そしてそのff(x)を返すのですから……と考えていくと、ひたすら巡回していくばかりで、いつまでたってもf(x)が何を返すのかさっぱりわかりません。こういう場合は『もし仮に〇〇だったら』と考えるといいです。たとえば、f(x)は引数の型と同じTを返すとしたらどうでしょうか。仮に f(x)T としたら、 f の返り値は T なんですから、f(x)T になるという仮定と矛盾しません。なので、次のように型注釈をつけることができます。

function f<T>(x: T): T {
    return f(x) ;
}

でも、実は新たにもうひとつの型変数 S を導入して考えてみると、また別の側面が見えてきます。もし f(x)T だとは限らず、S を返すとしたらどうでしょうか。f(x)Sだと仮定すると、fの返り値はSですから、f(x)Sだという仮定に矛盾しません。したがって、次のようにも型注釈をつけることができるのです。

function f<T,S>(x: T): S {
    return f(x) ;
}

どこからもS型の値は受け取っていないのに、なぜかつじつまがあってしまいました。Sなんて持っていないくせに、この関数fはもし呼び出されたらどこからSを持ってきて返すつもり気なのでしょうか。でも大丈夫です。この関数の呼び出しは決して終わらないので、Sを返す期限は決して訪れないのです。T でも Sでもどちらでもつじつまはあいますが、Sとしておいたほうが柔軟なのでそうしておきます。

この関数は呼び出すとかならずエラーになってしまいますが、見かたを変えれば意図的にエラーを起こすことに使えるといえます。なにしろ throw すら使用禁止ですから、プログラムを途中で止めたいときに何かエラーをわざと起こす方法があったほうがいいのです。この関数を bottom と呼ぶことにしましょう。

function bottom<T,S>(x: T): S {
    return bottom(x);
}

この関数は呼び出すと絶対にエラーになるというのも変ですが、一番奇妙なところは、どんな型の値でもコード上は作り出せてコンパイルが通ってしまうということでしょう。たとえはあるクラスのコンストラクタがプライベートになっていて絶対にインスタンスを作成する方法がなかったとしても、この関数を使えばコード上はそのクラスの型の引数などに返り値を代入することができてしまうのです。『どんな型の値にもなれる』『参照するとエラーになる』ということからわかるかもしれませんが、この関数の値は要するにundefinedに相当していると考えることができます。

変でいい、変でなきゃダメだ……狂ってなきゃ、逸脱してなきゃオブジェクトは殺せない……!

さらに別の f の定義を考えてみましょう。fを定義しようとすると、そのときにすでにfを使うことができるので、こんな定義も可能なのではないでしょうか。

function f<T>(x: T): ?????? {
    return f;
}

この関数は何を適用してもその関数がまた返ってきますから、たとえば x という値があったとすると、次のように何回でも連続して適用し続けることができます。まるで可変長引数の関数のようです。

f(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x).....

ということはこの関数の型は限りなく長くなってしまうので、そのままではうまく型注釈をつけることができません。でも、次のように型の別名を使って再帰的に定義すれば型注釈をつけることはできます。interface は型に別名をつけるもので、 『 F<T>(x: T): F<T> の別名だ』というように読みます。

interface F<T> {
    (x: T): F<T>;
}

function f<T>(x: T) : F<T> {
    return f;
}

この関数は何か使い道があるのかどうか、自分もよくわかりません。値を返すことができない以上、fがなんらかの副作用を持っていなければ意味がなさそうにも思います。何かいい使い道が思いついたら、何かもっと適切な名前をつけてあげようと思います。⇒『型システム入門』では『空腹関数』(Hungry function)という名前で呼ばれていました。

もうひとつ奇妙な関数をみつけました。引数xをとり、xxを適用するというものです。

function g(x) {
    return x(x);
}

この関数の型はどうなるでしょうか?というか、この引数xが関数なのかどうかもわかりませんから、本当に関数適用しちゃっていいのでしょうか?でもこの世界には関数しかないから、やっぱりxは関数のはずで……?とにかく型注釈を付けてみます。少々頭を捻ると、次のような型注釈ができることがわかります。

interface W {
    <S>(x: W): S;
}

function g<S>(x: W): S {
    return x(x);
}

この関数の型もまた再帰していて、相当に奇妙に思えます。ちょっとびっくりですが、この関数については使い道をみつけました。というか、いろんな関数を実装していて、ある関数の定義の一部にこの変な関数が現れることに気付きました。大人の自乗で詳しい説明は省きますが、たぶん何か名前が付いている関数だと思います。不勉強でまだ良くわからないのですが、もしこの関数が何なのか知っているひとがいたら教えてください。⇒奴の身元が割れました!こいつは U Combinator っていうそうです。alucky0707 さんありがとうございます。⇒もう一個表現見つけました。SKIコンビネータ計算でいう SII がコレと同じようです。

trueじゃなきゃfalse……この仕組みはこの世の姿そのもの……。基本も基本、大原則だっ……!

さて、ここまで幾つか関数を定義してみましたが、どうにも何か計算したりデータ型を定義できそうな要素は見えてこないと思います。でもさっきまでの作業は純粋な関数の世界に慣れるためのほんのウォーミングアップに過ぎません。一番簡単なものから練習していかないと、すぐ躓いてしまいますからね。これでウォーミングアップは終わりましたので、ここから遂に我々が普段毎日のようにお世話になっているものを我々の純粋な世界にも作り出します。

ウォーミングアップは終わりましたが、これまでと同じように f にどんな定義ができそうなのかを考えていきます。そういえば unitを定義したので、unitを返す関数を定義してみたらどうでしょうか。fの引数の型とunitの引数の型は同じでなければダメということはないので、新たにSを導入して型注釈も付け加えておきましょう。

function f<T,S>(x: T): (y: S)=>S {
    return unit;
}

ここで、(y: S)=>S というのは S をとって Sを返す関数の型です。したがって、この関数は、 Tをとって、SをとってSを返す関数、というように型注釈を読むことができます。unitの定義をこの関数のなかに展開してみたらどうなるでしょうか。

function f<T,S>(x: T): (y: S)=>S {
    return function(y: S): S {
        return y ;
    };
}

この関数で、return文のところではxyというふたつの引数を参照できることがわかると思います。これはつまり 2引数の関数 であると考えればいいでしょう。この定義では、そのうちyの方をそのまま返しているというわけです。これで新たな突破口が見えてきたことだと思います。もし f を呼び出す側から見れば、次のようにふたつ引数をとり2番めに渡したほうの引数を返す関数のようにも見えます。

f(x)(y) = y

ここでもうひとつ別の定義に気がつくかもしれません。ふたつ引数をとって、最初の引数のほうを返すような定義もできるのではないでしょうか。この関数をgとして定義してみます。最初の方の引数の型は T ですので、g全体は S ではなく T を返すことにも注意して型注釈を付け加えます。

function g<T,S>(x: T): (y: S)=>T {
    return function(y: S): T {
        return x;
    };
}

こんどの関数gは、次のように最初の方の引数を返すわけです。

g(x)(y) = x

さてここで、ある関数 c が実は f または g のどちらかであるとしましょう。どちらであるかはわかりません。fg も2引数と考えますから、 cも同じように2引数だと考えられます。cxyを与えた式 c(x)(y) はどんな値を返すのでしょうか?もし cf なら

c(x)(y) = x

となりますし、cg なら

c(x)(y) = y

となります。これってまさに 条件分岐 そのものではないですか!c(x)(y) を見かけたら、c ? x : y とか if(c){ x }else{ y } だと思えばいいのです。つまり、cboolean型の値であり、このfgfalsetrue に相当するモノなのです!

こんな素晴らしい物を見つけたのに fg なんていう名前じゃかわいそうですから、もっと良い名前を付けてあげましょう。でもtruefalseはJavaScriptの予約語で衝突してしまいますから、仕方ないので$true$falseと呼ぶことにします。funcion式をネストすると見づらくなるので、代わりにラムダ式を使っています。

function $true<T,S>(t: T): (f: S) => T {
    return f => t;
}
function $false<T,S>(t: T): (f: S) => S {
    return f => f;
}

もちろんこの $true$false は普通のnumberの値なんかに対しても使えます。

var c = $false;

console.log(c(10)(20)); // c ? 10 : 20 と考える。20が出力される

なんと、boolean型やif文や三項演算子がもとから存在しなくても、条件分岐はできるのです。

この$true$falseはデータ型としても扱えますから、関数の引数として渡したり、返り値として返したりすることももちろんできます。たとえば、$true$falseに、$false$trueに入れ替えるような関数notは次のように定義できるのです。

function not<T>(x: (t: (t: T) => (f: T) => T) => (f: (t: T) => (f: T) => T) => (t: T) => (f: T) => T): (t: T) => (f: T) => T {
    return x($false)($true);
}

なんだか型注釈がとんでもない長さになってしまいましたが、これは型のエイリアスを用意すれば次のように定義できるので安心してください。

interface Bool {
    <T>(t: T): (f: T) => T;
}

function not(x: Bool): Bool {
    return x($false)($true);
}

この関数を使うと、以下の様な式の展開ができます。

not($true) = $false
not($false) = $true

これはまさに $true$false という値をもつようなデータ型 Bool を定義したことにほかなりません。これで、我々が普段使っているようなプリミティブ型も、関数さえあればまったくの無の世界から作り出せることがおわかりになったことだと思います。

練習試合
  • ifというキーワードがあったほうがやっぱり読みやすい、というひともいるかもしれません。そんなひとのために $if(c)(x)(y) と書けるような関数$ifを定義してみましょう。
  • 論理和 or、論理積 and も定義してみましょう。

オブジェクト、コンストラクタ、プロパティに頼るプログラミングはやめだ……そういうノータリンな振る舞いはもうやめ……。自分の頭で考え、定義するべくして定義する……!

真偽値をうまく定義できて、ようやく少しプログラミングらしくなってきました。これまではボトムアップ方式で、なんか作ってみた⇒できたのは〇〇だった!という感じでしたが、今度は考え方を変えて、トップダウン式に〇〇を作りたい⇒こういう関数を定義すれば実現できる!というように考えて行きたいと思います。次は、複数の値を組み合わせたデータ型を考えてみましょう。これは構造体だとかに似たもので、複数の値をまとめてひとつの値のように扱えるようにするデータ型です。これを タプル と呼ぶことにしましょう。タプルはリストとはちょっと違います。リストは可変長で要素がすべて同じ型ですが、タプルは固定長なのと引き換えにそれぞれの要素が異なる型を取ることができます。

一番簡単なタプルは、ふたつの何かの値を組にしたものです。これを定義することが今回の目標ですが、でもいったい何ができればタプルを定義できたことになるのでしょうか?タプルとして最低限必要な操作は次のふたつです。

  • ふたつの値からタプルを作る操作
  • タプルからふたつの値を取り出す操作

ふたつの値からタプルを作る操作は、引数をふたつとってタプルを返すような関数でいいでしょうが、タプルからふたつの値を取り出す操作はどうしましょうか?関数の返り値で、ふたつの値を返すことはできません。このようなときは、いわゆるコールバック関数を使えばいいでしょう。そのコールバック関数がふたつの値を受け取るようにすればいいのです。もっとも簡単には、タプル自体がコールバック関数を受け取る関数で、タプルにコールバック関数を渡すとそこにふたつのタプルの要素を渡してきてくれるように定義する方法があります。たとえば tuple(x)(y) というようにタプルを作り、ここからふたつの値を取り出してそれぞれ引数aと引数bして受け取り、関数 faを(つまりxを)渡したいとします。次のようなコードを書ける関数 tuple を定義したいのです。

tuple(x)(y)(a => b => f(a) )
            ^
            このaがxと同じ、bがyと同じ

この関数の型は次のようになります。

function tuple<T,S,U>(x: T): (y: S) => (h: (a: T)=>(b: S)=>U) => U {
    return ????? ;
}

またもややけにいかめしい型注釈になってしまいましたが、またあとで別名を付けて読みやすく整理しましょう。h: (a: T)=>(b: S)=>U がコールバック関数の型です。つまり、tuple は最初の値、ふたつめの値、コールバック関数の3つの引数を与えると、最初の値とふたつめの値をコールバック関数に渡してきてくれる関数です。この関数は全部で3つ引数をとるのですから、ひとまずアロー関数式で受け取る関数を書きます。

function tuple<T,S,U>(x: T): (y: S) => (h: (a: T)=>(b: S)=>U) => U {
    return y => h => ????? ;
}

これで、最初の引数 x、ふたつめの引数 y 、コールバック関数 h が参照できるようになりました。あとはコールバック関数hxyを渡すように書けば完成です。また、型注釈の (h: (a: T)=>(b: S)=>U) => U という部分はまさにタプルそのものの型を意味していますから、これに Tuple という別名を付けてあげましょう。コードは次のようになります。

interface Tuple<T,S> {
    <U>(h: (a: T)=>(b: S)=>U): U;    
}

function tuple<T,S>(x: T): (y: S) => Tuple<T,S> {
    return y => h => h(x)(y);
}

型注釈もこれでだいぶ読みやすくをなりました。(x: T): (y: S) => Tuple<S,T> という部分は、x: Ty: S という引数を取ると タプル Tuple<S,T> を返す、と読むことができます。

fst と snd

これでタプルは完成なのですが、コールバック関数があると少々直感的にわかりづらいところがありますので、タプルからどちらか一方の値を取り出すという操作をもうすこし直感的に書ける関数 fstsnd を用意しましょう。fst はタプルから最初の値だけを返り値で返し、snd はふたつめの値だけを返り値で返します。これらの関数を使うと、次のように式変形できます。

fst( tuple(x)(y) ) = x
snd( tuple(x)(y) ) = y

これらの関数 fstsnd を定義してみましょう。fstはタプル Tuple<T,S> から最初の値をとりだすので、その型はfst<T,S>(t: Tuple<T,S>): T となります。snd も同様に考えます。

function fst<T,S>(t: Tuple<T,S>): T {
    return ????? ;
}

function snd<T,S>(t: Tuple<T,S>): S {
    return ????? ;
}

さて、本体はどのように定義しましょうか。タプルは関数になっていて、fstなら2引数の関数を渡すと最初の値を返すようなコールバック関数を渡せばいいのでした。そういえば、そのような関数がすでに登場していたことを覚えていますか?実は $true$false がまさにそのような関数なのです。

$true(x)(y) = x
$false(x)(y) = y

$true$false を使えば、fstsnd を簡単に定義することができます!

function fst<T,S>(t: Tuple<T,S>): T {
    return t($true) ;
}

function snd<T,S>(t: Tuple<T,S>): S {
    return t($false) ;
}

念のため、手動で計算して確かめてみましょう。

  fst( tuple                (x)(y) ) 
= fst( (a=>b=>h => h(a)(b)) (x)(y) )        (tupleを展開)
= fst( (   b=>h => h(x)(b))    (y) )        (xを適用)
= fst( (      h => h(x)(y))        )        (yを適用)
=      (      h => h(x)(y)) ($true)         (fstを展開)
=              $true(x)(y)                  ($trueを適用)
=      (m => n => m)(x)(y)                  ($trueを展開)
=      (     n => x)   (y)                  (xを適用)
=                 x                         (yを適用)

これで、tuple(x)(y) というようにして作ったタプルから fst を使って x という値が取り出せることが確認できました!

『オブジェクト』としてのタプル

tuplefstsndじゃ抽象的すぎて実際に何のデータを扱っているのかよくわからない!というのはあります。そのようなときは、それぞれの関数に別名を定義してやればいいのです。たとえば、次のようなname: stringage: numberというふたつのプロパティをもったオブジェクトを表現したいとします。

{ name: "Yuzuko", age: 16 }

このようなときは、次のようにタプルと同じような関数をそれぞれに対応した名前や型で用意してあげます。usertupleに対応している関数ですが、tupleと違ってstringnumberという組み合わせでしか渡せないように特殊化された関数です。

interface User {
    <T>(t: (name: string)=>(age: number)=>T): T;    
}

function user(name: string): (age: number) => User {
    return age => tuple(name)(age);
}

このuserはデータ型の「コンストラクタ」に相当します。この「コンストラクタ」を使えば、つぎのように User の「オブジェクト」を作ることができます。

user("Yuzuko")(16)

この「オブジェクト」からはfstsndでもそれぞれのデータを取り出せます(もちろんuser("Yuzuko")(16)($true)のように $true$falseを適用しても取り出せます!)が、別名でそれぞれのオブジェクトのプロパティ名に合わせた関数 nameage を用意しておけば読みやすくなります。

function name(u: User): string {
    return fst(u);
}

function age(u: User): number {
    return snd(u);
}

name( user("Yuzuko")(16) )    // "Yuzuko"
age( user("Yukari")(16) )     // 16

JavaScriptで普通に書けば

new User("Yuzuko", 16).name   // "Yuzuko"
new User("Yukari", 16).age    // 16

のようになるでしょうが、new が要らなくなってただの関数になったり、ドット演算子によるプロパティアクセスもただの関数適用になっただけで、読みやすさとしては大差ないように思います。もちろんこの辺りは数値型や文字列型が定義できてからの話になりますが。

このタプルは2要素ですが、タプルとタプルを組み合わせれば、もっと要素の数が多いデータ型を表現することができます。Tuple<T,Tuple<S,U>>は2要素のタプルが入れ子になったものですが、これを3要素のタプルとして扱うこともできるでしょう。もしくは先ほどの定義をさらに拡張して、3要素のタプルを定義するのもいいでしょう。

これでなんと、関数だけで「オブジェクト」に相当するものも定義できてしまいました!関数最高や!オブジェクトなんて最初からいらんかったんや!

練習試合
  • 3要素のタプル型 Tuple3 を定義してみましょう。

 世間というものは、とどのつまり肝心なことは何一つ答えたりしない……!

真偽値やタプルが定義できたことですし、そろそろ数の計算をしてみたいとは思うところではないでしょうか。ここで残念なお知らせなのですが、 筆者がそろそろ書くのに疲れてきた ので、数やリストなどのもっと複雑な型や、繰り返しなどの制御構造をどうやって定義するのか知りたいというかたが万が一いらっしゃいましたら、申し訳ありませんが以下の参考文献とソースコードを御覧になるか、筆者の気力回復を気長に待っていただくようお願いします。今回自分が実装したコードは、以下のgithubリポジトリで参照できます。

今回自分が実装したライブラリのコードでは、自然数の定義とともに加算、減算、乗算といった基本的な演算ができるようになっていますし(除算はめんどくさくて実装してないです)、計算結果を文字列として表示する機能も中途半端ながら一応実装しています。これらのコードは主にChurch encoding - Wikipediaで紹介されている"Church numerals"を参考に書きましたので、このソースコードの理解をしたければそちらを参考にするのも良いと思います。ほかにもEither(共用体みたいなもの)、二分木のような再帰的な型をもつデータ型も定義しています。

入出力部分の言い訳

関数で定義されたデータ型で入力し、関数で定義されたデータ型で出力するだけなら他にはなにも要らないのですが、このシステムには「リテラル」に相当するものがないので、$true$false のような単純な値以外のデータを記述するのは少々面倒ですし、関数で定義されたデータ型はデバッガで覗こうとしてもとても人間には読めるものではありません(なにしろ関数ですから)。しかたないので、最低限の機能だけ使って、文字列オブジェクトと関数で定義されたデータ型を相互に変換するコードを加えました。

以下の関数 interactive は、関数fと文字列xを引数に取り、xを関数で定義された文字列のデータ型Strに変換してから、fに適用し、結果を再びJavaScriptの文字列にデコーディングしてコンソールに出力します。この interactive が関数だけで定義されたソースコードを実行するための環境で、fがアプリケーションのコードに相当します。この関数が低レベルな入出力をすべて担当しているので、interactiveと入力の文字列以外のすべてのソースコードは関数のみでできています。ちなみに、churchunchurchという関数はそれぞれnumberを関数だけで定義された自然数型Naturalに、Naturalnumberに変換する関数です。これであとは純粋に関数だけで構成されたこの世界の構築を進めれば、どんな計算も関数だけで可能になるはずです。

function interactive(f: (s: Str)=>Str, x: string): void {
    function church(n: number): Natural {
        return f => x => n ? church (n-1) (f) (f(x)) : x;
    }
    function unchurch(n: Natural): number {
        return n(x=>x+1)(0);
    }
    console.log(
            decode("")(x=>y=>x+y)(n=>String.fromCharCode(unchurch(n)))
        (f(   
            encode(i=>church(x.charCodeAt(unchurch(i))))(church(x.length))
        ))
    );
}
もうちょっと具体的なアプリケーション

たとえば、アルファベットを一文字づつずらして暗号化するシーザー暗号を文字列に対して適用するコードは次のようになります(このコードの詳しい説明は省きます)。

interactive(x=>concat6 
    (x)                     // plain text
    (char(_0)(_3)(_2))      // " "
    (char(_0)(_6)(_1))      // "="
    (char(_0)(_6)(_2))      // ">"
    (char(_0)(_3)(_2))      // " "
    (map(succ)(x))          // encrypted text
, "Hello,World");

これを実行すると、標準出力に次のように出力されます。

Hello,World => Ifmmp-Xpsme 

参考文献

参考になりそうな記事を幾つか挙げておきます。

筆者用メモ