8

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

私は、Scheme で書かれた Iota プログラミング言語の実装を見つけました。Haskellに翻訳するのに少し苦労しました。かなり単純ですが、私は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))))))
4

1 に答える 1

13

私はこのことのいくつかを自分自身に教えてきたので、次のことを正しく理解できることを願っています...

nm が言及しているように、Haskell が型付けされているという事実は、この質問にとって非常に重要です。型システムは、形成できる式を制限します。特に、ラムダ計算の最も基本的な型システムは、自己適用を禁止します。これにより、最終的に非チューリング完全言語が得られます。チューリングの完全性は、言語の追加機能 (演算子または再帰型のいずれか)として、基本型システムの上に追加されます。fix :: (a -> a) -> a

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

アプローチ #1: here から 2 番目の例の 1 点組み合わせ論理基礎を実装し、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。これがどのように機能するかを説明するのは少し複雑です。（編集：これは元の質問iota'の と同じではないことに注意してください。これは、チューリング完全でもあります。プログラムがプログラムとは異なる場合です。Haskellで定義を試しました;それ型チェックを行いますが、試行すると型エラーが発生します。)λx.x S Kλx.x K S Kiota'iotaiota = λx.x S Kk = iota (iota (iota iota))s = iota (iota (iota (iota iota)))

アプローチ #2:型指定されていないラムダ計算の表示は、この再帰型を使用して Haskell に埋め込むことができます。

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

DDは基本的に からまでの関数を要素とする型ですD。関数をプレーンにIn :: (D -> D) -> D変換し、その逆を行う必要があります。したがって、 がある場合は、 を実行して自己適用できます。D -> DDout :: D -> (D -> D)x :: Dout 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これには、 andからの「ノイズ」が必要outです。Haskell は、 aDに aを適用することを依然として禁止していますが、 andをD使用してこれを回避できます。type の値で実際に役立つことは何もできませんが、同じパターンで有用な型を設計することはできます。InoutD

編集: iota は基本的λx.x S Kに 、 where K = λx.λy.x、S = λx.λy.λz.x z (y z). つまり、iota は 2 つの引数の関数を取り、それを S と K に適用します。つまり、最初の引数を返す関数を渡すと S が得られ、2 番目の引数を返す関数を渡すと K が得られます。 S と K は iota で書けます。しかし、チューリング完全性を得るには S と K で十分なので、おまけにチューリング完全性も得られます。必要なセレクター関数を iota で記述できることが判明したため、Turing の完全性には iota で十分です。

したがって、これにより、イオタを理解するという問題が SK 計算を理解することに軽減されます。

于 2012-08-14T23:16:07.270 に答える