JavaScriptラムダ計算

こんにちは この記事では、ラムダ計算をもう一度見てみたいと思います。 この問題の理論的な側面はすでにHaberで何度も議論されているので、例えばJavaScriptでラムダ計算が実際にどのように見えるかを見てみましょう（ブラウザで直接実行できるように）。



だから、主なアイデア：すべてが機能です。 したがって、言語機能の非常に狭い範囲に制限します。式は、1つの引数を持つ匿名関数（ x => expr



）、または関数呼び出し（ f (x)



）のいずれかになります。 つまり、すべてのコードは次のようになります。

 id = x => x double = f => x => f (f (x))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

関数の結果は他の関数になるため、結果を解釈する方法が必要です。 これは、JavaScriptの重要な機能が役立つ唯一の場所です。

基本的なこと

通常どおり、条件分岐から始めましょう。 2つの定数を導入します。

 True = t => f => t False = t => f => f
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらは2つの引数を持つ関数であり、 True



は最初の引数を返し、 False



は2番目の引数を返します。 つまり、次のステートメントは真です。

 console.assert(1 == True (1) (2)) console.assert(2 == False (1) (2))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらの定数は論理的な真実と偽りを表し、 If



関数を記述できます。

 If = b => t => f => b (t) (f) console.assert(1 == If (True) (1) (2)) console.assert(2 == If (False) (1) (2))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すでに従来のif



ように見えますが、構文的には少し異なっています。 条件分岐を使用すると、標準のブール演算子を簡単に実装できます。

 Not = x => If (x) (False) (True) And = x => y => If (x) (y) (False) Or = x => y => If (x) (True) (y)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次のステップは、最初の「データ構造」、つまりペアを導入することです。 定義は次のとおりです。

 Pair = x => y => (f => f (x) (y)) Fst = p => p (True) Snd = p => p (False) p = Pair (1) (2) console.assert(1 == Fst (p)) console.assert(2 == Snd (p))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

少し奇妙に見えますが、理にかなっています。 この場合、ペアは自身の内部に2つの値をカプセル化する関数であり、呼び出されたときにそれらをパラメーターに渡すことができます。 同様に、任意の長さのタプルを記述できます。

 Triplet = x => y => z => (f => f (x) (y) (z)) Pentuplet = x => y => z => u => v => (f => f (x) (y) (z) (u) (v))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一般的に、同様の武器を使用して、 Byte



を8つの論理値のタプル、 Int



を4 Byte



タプルとして既に定義し、それらにマシン算術を実装できますが、これはルーチンであり、喜びをもたらすことはありません。 自然数を記述するより美しい方法があります- 教会の算数。

算術

教会の算術は、2つの引数の関数としてゼロを持つ自然数のセットを記述します。

 Zero = s => z => z One = s => z => s (z) Two = s => z => s (s (z)) Three = s => z => s (s (s (z)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初の引数は関数であり、2番目の引数は関数がn



回適用されるものです。 実際、それらを構築するには、ゼロと+1



関数のみが必要です。

 Succ = n => (s => z => s (n (s) (z)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Succ



は、左側にある別s



呼び出しを既存の呼び出しチェーンにスローし、それによって次の自然数を返します。 この機能が複雑に思える場合、別の方法があります。 彼の仕事の結果はまったく同じになりますが、ここでs



のスローは右側で行われます。

 Succ = n => (s => z => n (s) (s (z)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、教会番号を使い慣れたint



に変換する方法を説明する価値があります。これは、関数x => x + 1



をゼロn



回ゼロに適用したものです。

 toInt = n => n (x => x + 1) (0) console.assert(0 == toInt (Zero)) console.assert(1 == toInt (One)) console.assert(2 == toInt (Two))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

同様に、加算、乗算などの演算が定義されています：

 Add = n => m => m (Succ) (n) Mul = n => m => m (Add (n)) (Zero) Pow = n => p => p (Mul (n)) (One) //⇈ = n => m => m (Pow (n)) (One)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このようにして、 矢印表記を実装し続けることができますが、これには意味がありません。この時点で、数値を扱う原則は明確になっているはずです。



次のステップは減算です。 登場したばかりの伝統に従って、その実装は次のようになります。

 Sub = n => m => m (Pred) (n)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、Pred関数の実装は問題のままです。 幸いなことに、 Kleeneは私たちのためにそれを思いつきました。

 Pred = n => Fst (n (p => Pair (Snd (p)) (Succ (Snd (p)))) (Pair (Zero) (Zero)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

歴史によれば、この考えは歯科医を訪れたときに彼に伝わり、麻酔は今よりも強かったということです。 これについては議論しませんが、ここで何が起こっているのかを説明します。 前の数値を取得するには、次のようにペア(n-1, n)



します：関数(x, y) -> (y, y+1)



n



回ペア(0, 0)



し、結果から左のコンポーネントを抽出します。 その結果、ゼロより前の数値もゼロになることに気付くのは簡単です。 これは不確実性からあなたを救い、他の多くの利点を提供します。



完全を期すために、比較演算の実装を示します。

 IsZero = n => n (_ => False) (True) Lte = n => m => IsZero (Sub (n) (m)) Lt = n => m => Lte (Succ (n)) (m) Eq = n => m => And (Lte (n) (m)) (Lte (m) (n)) Max = n => m => If (Lte (n) (m)) (m) (n) Min = n => m => If (Lte (n) (m)) (n) (m)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リスト

リストは、自然数とほぼ同じ方法でエンコードされます-これらも2つの引数の関数です。

 Nil = f => x => x L1 = f => x => f (a0) (x) L2 = f => x => f (a0) (f (a1) (x)) L3 = f => x => f (a0) (f (a1) (f (a2) (x))) //...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

False



、 Zero



およびNil



は同じ関数であることに注意してください。



リストの機能操作に精通している場合は、おそらくこの構造が正しい折りたたみを説明していることにすでに気付いているでしょう。 したがって、簡単に実装されます。

 Foldr = f => z => l => l (f) (z)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、永続リストの標準操作を実装します。先頭に追加して、リストの「先頭」と「末尾」を取得します。

 Append = a => l => (f => x => f (a) (l (f) (x))) Head = l => l (a => _ => a) () list = Append (1) (Append (2) (Nil)) console.assert(1 == Head (list))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

説明の最後にある空の括弧は、空のリストの先頭です。 正しいプログラムでは、この値は決して使用すべきではないため、構文的に最小の値を選択しました。 一般的に、これらの括弧内に記述できるものはすべて。 記事の後半では、まったく同じ理由で空のブラケットを使用する別の場所があります。



リストの末尾を取得する機能は、以前の自然数を取得する機能をほぼ完全に繰り返します。 同じ理由で、空のリストの末尾は空のリストになります。

 Tail = l => Fst ( l (a => p => Pair (Snd (p)) (Append (a) (Snd (p)))) (Pair (Nil) (Nil)) ) console.assert(2 == Head (Tail (list)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

使用例として、 map



関数と他のいくつかの実装を示しmap



。

 Map = m => l => (f => x => l (a => f (m (a))) (x)) Length = l => Foldr (_ => Succ) (Zero) (l) IsEmpty = l => IsZero (Length (l)) //      JavaScript toList = l => Foldr (x => y => [x].concat(y)) ([]) (l) toIntList = l => toList (Map (toInt) (l)) function arraysEqual(a,b) { return !(a < b) && !(b < a); } //   
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Map



はリストの各要素を、関数f



を呼び出した結果で置き換えます。

Length



とIsEmpty



は、それ自体をIsEmpty



ています。 toList



およびtoIntList



は、テストおよびコンソールでのtoIntList



リストに役立ちます。

再帰

この時点で、関数のみを使用した作業は、「通常の」プログラミングと疑わしく似ています。 すべてを台無しにするときです。 関数の宣言と呼び出しのみに限定しているため、構文糖衣はまったくありません。つまり、多くの単純なことを複雑な方法で記述する必要があります。



たとえば、 OnNonEmpty : fun => list => result



関数を作成したいOnNonEmpty : fun => list => result



、リストlist



fun



関数が空でない場合にのみ呼び出します。 試してみましょう：

 OnNonEmpty = f => l => If (IsEmpty (l)) (Nil) (f (l))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

間違いありませんか？ f



が空のリストで停止しない場合、 OnNonEmpty



は停止しますが、停止する必要があります。 実際、JavaScriptは計算の適用可能な順序を提供します。つまり、関数へのすべての引数は、呼び出される前に評価され、遅延はありません。 また、 If



ステートメントは、条件に応じて1つのブランチのみを計算する必要があります。 したがって、関数を書き直す必要があり、これからさらに美しくなることはありません。

 OnNonEmpty = f => l => (If (IsEmpty (l)) (_ => Nil) (_ => f (l))) ()
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

If



は、条件に応じて、計算が必要な関数を返します。 そして、計算が行われた後にのみ、このようにして怠weを保証できます。



2番目の問題は再帰です。 関数内では、その正式な引数にのみアクセスできます。 これは、関数が名前でそれ自体を参照できないことを意味します。



しかし、解決策があります。これは悪名高い「Fixed Point Combinator」です。 通常、これらの単語の後に、 結合子Yの説明が示されますが、適用順序については適切ではありません。 代わりに、 この素晴らしい記事で精巧にスパイされたコンビネータZ



を使用します 。

 Z = f => (x => f (y => x (x) (y))) (x => f (y => x (x) (y)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンビネータは、1つのプロパティZ (f) == f (Z (f))



に基づいて選択される関数です。つまり、 Z(f)



はx == f (x)



ような値x



です。 したがって、「固定小数点」という用語。 しかし、奇跡によって、コンビネーターは方程式を解くことができると考える必要はありません。代わりに、無限再帰呼び出しZ(f) = f (f (f (f ( ... ))))



です。



コンビネータの「主なプロパティ」は、すばらしい「副作用」、つまり再帰を実装する機能を提供します。 たとえば、次のエントリ：

 MyFun = Z (myFun => ...)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

書くことと同等：

 MyFun = (myFun => ...) MyFun //      
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、匿名関数の最初の正式なパラメーターがMyFun



関数MyFun



と実際に一致することを意味し、その中で実際の再帰呼び出しを行うことができます。 除算の残りの部分を検索する例を試してみましょう。

 Rem = Z (rem => n => m => ( If (Lt (n) (m)) (_ => n) (_ => rem (Sub (n) (m)) (m)) ) ()) console.assert(1 == toInt (Rem (Three) (Two))) console.assert(0 == toInt (Rem (Three) (One)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その後、最初の有用なアルゴリズムであるユークリッドアルゴリズムを実装できます 。 面白いが、彼は部門の残りを見つけることほど難しくはなかった。

 Gcd = Z (gcd => n => m => ( If (IsZero (m)) (_ => n) (_ => gcd (m) (Rem (n) (m))) ) ())
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

シーケンス

最後に触れたデータ構造は、「無限リスト」またはシーケンスです。 関数型プログラミングは、そのようなオブジェクトを操作できることで有名であり、それらを無視することはできません。



シーケンスは次のように宣言されます。

 Seq = head => tail => Pair (head) (tail) SeqHead = seq => Fst (seq) SeqTail = seq => (Snd (seq)) ()
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンストラクター内のシーケンスの末尾は、新しいシーケンスを計算する関数であり、完成した結果ではありません。 このアプローチは、無限の長さのテールを生成する機能を提供します。



テストのために、最初のn



要素を取得する関数を作成します。

 SeqTake = Z (take => n => seq => ( If (IsZero (n)) (_ => Nil) (_ => Append (SeqHead (seq)) (take (Pred (n)) (SeqTail (seq)))) ) ())
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

練習したい場合は、再帰なしでSeqTake



を実装してSeqTake



。 可能です、保証します。



今、いくつかのシーケンスの例を挙げる価値があります。 自然数にしてみましょう-まだ実装されているものだけで作業する必要があります：

 Nat = (Z (natFrom => n => Seq (n) (_ => natFrom (Succ (n))))) (Zero) console.assert(arraysEqual([0, 1, 2], toIntList (SeqTake (Three) (Nat))))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、 n



始まる自然数のシーケンスを返す補助関数natFrom (n)



を使用します。 Nat



はnatFrom (Zero)



結果です。



最後の2つの関数はほとんど残っておらず、このテキストにあるものの中で最もかさばっています。 1つ目は、シーケンスフィルタリング機能です。 送信された述部を満たすすべての要素を、送信されたシーケンスで見つけます。

 SeqFilter = Z (filter => cond => seq => ( If (cond (SeqHead (seq))) (_ => Seq (SeqHead (seq)) (_ => filter (cond) (SeqTail (seq)))) (_ => filter (cond) (SeqTail (seq))) ) ())
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

head要素が述語を実行しない場合、 SeqFilter



はフィルタリングされたテールを返します。 それ以外の場合は、現在のヘッドと同じフィルタリングされたテールのシーケンスになります。



2番目は素数のシーケンスです。 私のパフォーマンスにおけるエラトステネスのふるいの別のバージョン：

 Primes = (Z (sieve => nums => Seq (SeqHead (nums)) (_ => sieve (SeqFilter (p => Not (IsZero (Rem (p) (SeqHead (nums))))) (SeqTail (nums))) ))) (SeqTail (SeqTail (Nat)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この機能は、記事の集大成と呼ぶことができます。 動作の原理は、擬似コードで理解しやすくなります。

 sieve (nums) { p = head (nums) rest = tail (nums) return append (p, sieve (filter (n -> n % p != 0, rest))) } primes = sieve [2, 3, 4, ...]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

テストは次のとおりです。

 Ten = Mul (Two) (Add (Two) (Three)) // s => z => s (s (s (s (s (s (s (s (s (s (z)))))))))) console.assert(arraysEqual([2, 3, 5, 7, 11, 13, 17, 19, 23, 29], toIntList (SeqTake (Ten) (Primes))))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

あなたのことは知りませんが、純粋な機能だけを使ってそのようなことを書くことができるのは今でも驚きです！

おわりに

その結果、JavaScript言語を例として使用して、LISPに奇妙な紹介をしました。 抽象的な数学的アイデアが実際にプログラミングの現実に非常に近いことを示すことができたと思います。 そして、そのような見方をすれば、ラムダ計算は学術的なもののように見えなくなります。



もちろん、ここに記事のすべてのコードを含むGithubへのリンクがあります。



よろしくお願いします！