どのタイプのラムダ計算がゆるい例の例になりますか？

Question

ラムダ計算でタイプがどのように機能するかについて、より良いグリップを得ようとしています。確かに、多くのタイプ理論のものが私の頭の上にあります。 LISPは動的に型付けされた言語であり、それは未熟なラムダ計算にほぼ対応するでしょうか？それとも、私が気づいていない「動的にタイプされたラムダ微積分」がありますか？

Answer 1

LISPは動的に型付けされた言語であり、それは未熟なラムダ計算にほぼ対応するでしょうか？

はい、しかし大まかにだけです。 「純粋な」Untyped Lambda計算では、すべてが関数としてコード化されています。 （人気のある「教会のエンコード」とあまり人気のない「スコットエンコード」についてグーグルでグーグルできます。）LISPには、原子や数などの非機能データがあります。これは、「定数で拡張されていないラムダ微積分が拡張されていない」とカウントされます。

もう1つの重要な違いがあります 評価の順序. 。 Lambda-Calculus用語を減らすためのルールは、非常に非決定論的です。 （定理があります。教会ロッサー定理があります。これは、物事が終了する限り、評価の順序は重要ではないとゆるく言っています。）実際には、ラムダの用語は通常、左端の最大の「通常の順序」削減を使用して減少します。 どれか 削減戦略は終了します。これは、ベータ削減を行う前に常に通常の形式の引数を評価するLISPとは大きく異なります。この評価順序は「値による呼び出し」と呼ばれます。

要約すると、LISPはに対応します 定数で拡張された、型のない、価値のない価値のあるラムダ計算.

Answer 2

ジョン・マッカーシーはリスプを紹介しました 彼の1960年4月の論文「象徴的な表現の再帰機能と機械によるそれらの計算、パートI」. 。次の段落は6ページからのものです。

e。関数とフォーム。数学的な論理以外では、「関数」という単語を不正確に使用し、yなどのフォームに適用することが通常の数学では普通です² + x。後で関数の式で計算するため、関数とフォームの区別と、この区別を表現する表記が必要です。この区別とそれを説明するための表記法は、私たちが些細なことで逸脱しているため、教会によって与えられます[3]。
...
3. A.教会、ラムダ融合の微積分（プリンストン大学出版局、プリンストン、ニュージャージー州、1941年）。

Lambda-Calculusに関するウィキペディアの記事 教会の出版物の歴史があります。マッカーシーが参照した1941年の論文は タイプしました Wikipediaの記事の紹介と矛盾して、Lambda-Calculus。

lambda LISPのキーワードは、類推によってのみラムダカルクルスを指すと理解できます。リスプラムダの表現は一種です 匿名関数.

Answer 3

Lispは「ラムダ計算」ではなく、「ラムダ計算」が何であるかわかりません。

Lambda Calculiを型で識別したい場合は、Lispはもちろん独自のシステムです。スキーム前の任意のLISPの「Lambda」キーワードは確かに大げさであり、スキームの後、それを言う余地もあります。 「Func」を使用するだけで、もっと謙虚だったでしょう。 LISPは主に「ラムダ計算」ではなく、リストプロセッサです。

また、私はこれについてかなり広範な記事を書きました。なぜ「機能的なプログラミング」という用語が意味がなく、「タイプシステム」ではなく「ラムダ計算」を話すことがそう言わない理由を実証しようとします。

http://blog.nihilarchitect.net/archives/289/on-function-programming/

また、LISPでは、すべての機能が有効であることに留意してください 単一の引数 そして、することしかできません リスト 彼らの議論として。