HaskellでIotaを実装する

Question

Iotaは、1つのコンビネータしか使用しない、ばかげた小さな「プログラミング言語」です。どのように動作するかを理解することに興味がありますが、私が慣れ親しんでいる言語で実装されていることを確認すると役に立ちます。

Schemeで書かれたIotaプログラミング言語の実装が見つかりました。私はハスケルにそれを翻訳するのに少し問題があった。むしろ単純ですが、私はHaskellとSchemeの両方に対して比較的新しいものです。

Haskellに相当するIOTA実装をどのように記述しますか？

(let iota() 
    (if (eq? #\* (read-char)) ((iota)(iota)) 
     (lambda (c) ((c (lambda (x) (lambda (y) (lambda (z) ((x z)(y z)))))) 
      (lambda (x) (lambda (y) x)))))) 

Answer 1

私は自分自身にこのようなもののいくつかを教えてきたので、私は確かN.M.として

...私は次の権利を取得願っていますハスケルがタイプされているという事実は、この質問に非常に重要です。どのような式が形成されるのかを制限します。特に、ラムダ計算の最も基本的なタイプのシステムでは、自己適用が禁止されています。チューリングの完全性は、言語の特別な機能（fix :: (a -> a) -> a演算子または再帰型のいずれか）として、基本タイプシステムの先頭のにを追加します。

これは、Haskellでこれを実装することはできませんが、そのような実装では1つの演算子しか持たないことを意味しません。

アプローチ＃1：second example one-point combinatory logic basis from hereを実装し、fix機能を追加します。

iota' :: ((t1 -> t2 -> t1) 
      -> ((t5 -> t4 -> t3) -> (t5 -> t4) -> t5 -> t3) 
      -> (t6 -> t7 -> t6) 
      -> t) 
     -> t 
iota' x = x k s k 
    where k x y = x 
      s x y z = x z (y z) 

fix :: (a -> a) -> a 
fix f = let result = f result in result 

今、あなたはiota'とfixの面で任意のプログラムを書くことができます。これがどのように機能するかを説明するのはちょっと複雑です。 （EDIT：ノートこのiota'は、元の質問でλx.x S Kと同じでないこと、それはまた、チューリング完全さλx.x K S K、だそれはiota'プログラムはiotaプログラムとは異なることになるだろうされる場合である私がしました。

：型なしラムダ計算のdenotationsは、この再帰型を使用してHaskellのに埋め込むことができます：それはtypechecksが、あなたはk = iota (iota (iota iota))を試してみて、s = iota (iota (iota (iota iota)))あなたは型エラーを取得するとき）

はアプローチ＃2; Haskellではiota = λx.x S K定義を試みました。

newtype D = In { out :: D -> D } 

Dは、基本的には、要素がD〜Dの機能であるタイプです。 In :: (D -> D) -> DD -> D関数をプレーンDに変換するには、out :: D -> (D -> D)を変換する必要があります。したがって、x :: Dがある場合は、out x x :: Dで自己申告することができます。

はそれを与える、今は書くことができます。

iota :: D 
iota = In $ \x -> out (out x s) k 
    where k = In $ \x -> In $ \y -> x 
      s = In $ \x -> In $ \y -> In $ \z -> out (out x z) (out y z) 

これはInとoutからいくつかの「ノイズ」が必要です。ハスケルはまだDをDに適用することを禁じていますが、Inとoutを使用してこれを回避することができます。実際にはDというタイプの値では役に立ちませんが、同じパターンの周りに有用なタイプを設計することはできます。

---

EDIT：イオタは、基本的λx.x S K、K = λx.λy.x及びS = λx.λy.λz.x z (y z)あります。すなわち、iotaは2つの引数をとり、それをSとKに適用します。最初の引数を返す関数を渡すことによってSを取得し、2番目の引数を返す関数を渡すことによってKを取得します。したがって、iotaを使用して "return first argument"と "return second argument" iと一緒にSとKを書くことができます。しかしS and K are enough to get Turing completenessなので、あなたはTuringの完璧さをお買い得だ。必要なセレクタ関数をiotaで書くことができますので、iotaはTuringの完全性のために十分です。

これにより、SK計算を理解することの問題が軽減されます。