Ocamlでラムダ計算をしたい

Question

Ocamlを初めて使うものです。
Ocamlでラムダ計算をしたいのですが、まだ構文などがよくわかっていなくつまづいています。簡単な例をあげるので、どのように記述するか教えていただけますでしょうか？

例）
L = λx. x+1の時、
L(L 3) = L ((λx. x + 1) 3) → L (3 + 1) → (λx. x + 1) (3 + 1) ,→ (3 + 1) + 1

D = λf.λx.f(f x)の時、
D L 3 = ((λf . λx. f (f x)) L) 3 → (λx.L(L x)) 3 →
L(L 3) →∗(3 + 1) + 1

C = λf . λg. λx. f (g x)の時、
C L L 3 → (λg. λx. L(g x)) L 3 → (λx. L(L x)) 3 →
L(L 3) →∗(3 + 1) + 1

これらをみて自分で他の問題も実装してみたいです。よろしくお願いします。

Comments

[ozwk]

わからないなりに適当にでもかけると思いますので書いてみてください

Answer 1

ご質問の「ラムダ計算がしたい」という文の意図が当方でうまくつかめておりませんが、「C L L 3などの結果を計算するプログラムを書きたい」ということでしょうか。

(* L *)
let f1 x = x + 1

(* L (L 3) *)
let v1 = f1 (f1 3)

(* D *)
let f2 f x = f (f x)

(* D L 3 *)
let v2 = f2 f1 3

(* C *)
let f3 f g x = f (g x)

(* C L L 3 *)
let v3 = f3 f1 f1 3

上のf3は以下のf4と同じです。

(* C *)
let f4 = fun f -> fun g -> fun x -> f (g x)

もしくは「評価器をつくりたい」ということであれば、以下が参考になるかと思います。

TaPL 7 章 型なしラムダ計算の1ステップ評価の OCaml による実装

もうすでに解決済みかもしれませんが、お役に立てれば幸いです。