無駄と文化

実用的ブログ

λ計算

型無しラムダ計算学習用ステップ評価器 skiMogul を作っている話

みなさま ラムダ計算 をご存知でしょうか。 ラムダ計算はある種の関数型プログラミング言語の体系で、変数と関数, そして関数適用というミニマルな構成要素だけでチューリング完全な表現力を持っています。 この記事では、ラムダ計算の中でも特に単純な 型無…

ラムダ式に含まれる全ての部分式に一意かつ列挙可能なタグを付与する方法

ラムダ式に含まれる全ての部分式に一意かつ列挙可能なタグを付与する方法について考察する。 導入 例として次のラムダ式について考える。 ````ABC``DEF`GH この式を二分木で書くと以下のようになる。 graph TB; a1((app))---a2((app)) a2((app))---a3((app))…

JavaScript で割り算の商と余りを求める

JavaScript で整数同士の割り算をして商と余りを求める方法について解説します。 まず2つの整数 m, n を受け取って商と余りの組を返す関数 div を定義しましょう。 const div = (f=>(u=>u(u))(x=>f(y=>x(x)(y))))(g=>m=>n=>m>=n?(b=>b?1+g(m-n)(n)(1):g(m-n)…

不動点コンビネータで無名再帰を作る流れをおさらい

どうも、趣味で関数型言語を書いている者です。 長らく関数型言語やってなかったら無名再帰を忘れかけていたので、おさらいがてら不動点コンビネータで無名再帰を作る流れを書き下します。 以下、Haskell の文法で書かれたコードをもとに説明していきます。 …

Haskell でλ計算のインタプリタを作っていこう ~ その3. プリティプリンタ

引き続き Mogul という名前のλ計算インタプリタを作っていこうと思います。 前回、パーザを書いたのでソースコードから抽象構文木を生成することができるようになりました。さっそく抽象構文木をいじくり回して何かしらの処理を実装したいところですが、今回…

Haskellでλ計算のインタプリタを作っていこう ~ その2. パーザ

引き続き Mogul という名前のλ計算インタプリタを作っていこうと思います。 前回、λ式を表現するデータ型を定義したので、今回はパーザを書きます。ソースコードを読ませて抽象構文木を生成するところまでです。 ソースコード全体は GitHub に置いておきます…

Haskell でλ計算のインタプリタを作っていこう ~ その1. データ型

Haskell ネタです。 先日の記事で宣言したとおり、λ計算のインタプリタを作っていこうと思います。 ソースコード全体は GitHub に置いておきます。 github.com プロジェクト名は Mogul (モーグル) 。 なので作っていくインタプリタの名前も Mogul です。 全…

λ計算のインタプリタを作ろうとしている話

先月、八耐に参加してから 長年個人プロジェクトとして取り組み続けてきた『λ計算インタプリタを作りたい』という欲が再燃しています。 欲が燃えているのは結構なことなので、実際に作ろうと思います。その宣言のための記事です。 作ろうとしているもの λ計…

八耐 in 東京 に参加してきました。

福岡で働いていた頃からの友人である 岩本くんに声を掛けてもらったので 八時間耐久作品制作会(仮) in 東京 に参加してきました。 ふり返りつつレポートしてみます。

Lazy_K で九九表のすべてのマスの和

前回の記事で [九九表のすべてのマスの和を求める問題] をいろいろな言語で書きました。 記事の最後でそのうち Lazy_K でも書きます的な事を宣言しておいたんですが、この度そのコードが完成しましたのでご報告します。