ブラウザよりも高速アクセス！
81 関係: 型付きラムダ計算、型理論、可算集合、参照透過性、同値関係、合流性、定数、不動点、不動点コンビネータ、並列計算、並行計算、一階述語論理、引数、形式体系、ペアノの公理、チャーチ・ロッサーの定理、チャーチ＝チューリングのテーゼ、チューリングマシン、バッカス・ナウア記法、ラムダ・キューブ、ラッセルのパラドックス、プログラミング言語、プロセス計算、デリゲート (プログラミング)、データ型、ド・ブラン・インデックス、命令型プログラミング、アルゴリズム、アロンゾ・チャーチ、オブジェクト指向プログラミング、カリーのパラドックス、カリー化、カリー＝ハワード同型対応、カントールの対角線論法、ゲーデル数、コンビネータ論理、スティーヴン・コール・クリーネ、タプル、再帰、再帰的定義、B,C,K,Wシステム、C Sharp、C++、CCS、C言語、Communicating Sequential Processes、第一級オブジェクト、第一級関数、純LISP、真理値、...、結合法則、無名再帰、Eiffel、階乗、領域理論、順序対、項書き換え、計算、計算可能関数、計算可能性理論、計算モデル、計算機プログラムの構造と解釈、評価戦略、高階関数、述語論理、関数、関数型言語、自由変数と束縛変数、自然数、Haskell、LISP、ML (プログラミング言語)、Pascal、SKIコンビネータ計算、Smalltalk、System F、Unlambda、束縛 (情報工学)、決定可能性、文脈自由文法、数学的帰納法。 インデックスを展開 (31 もっと) »
型付きラムダ計算
型付きラムダ計算（typed lambda calculus）とは、無名の関数の抽象表現にラムダ (\lambda) というシンボルを用いる型付き形式手法である。型付きラムダ計算は基礎的なプログラミング言語でもあり、MLやHaskellなどの型付き関数型言語の基盤であり、さらには型付き命令型プログラミング言語の間接的な基盤とも言える。また、カリー・ハワード同型対応によって数理論理学と証明論とも密接に関連しており、圏論のクラスの内部言語と見なすこともできる。例えば単純な型付きラムダ計算はデカルト閉圏 (CCC) の言語である。 ある観点から見れば、型付きラムダ計算は型を持たないラムダ計算を改良したものと言えるが、別の観点からは、より根本的な理論と見ることもでき、型を持たないラムダ計算の方が型が1つしかない特殊ケースと見ることができる。 様々な型付きラムダ計算がこれまで研究されてきた。単純型付きラムダ計算はいくつかの基本型（または型変数）と関数型 \sigma\to\tau から成る。System T はこれを拡張し、自然数型と高階原始再帰を加えたものである。この系ではペアノ算術において全ての再帰する可能性のある関数が定義可能である。System F は、全ての型に対して全称量化を施すことでポリモーフィズムを実現している。これを論理学的に見れば、二階述語論理に属する全ての関数を記述できることを意味する。依存型のあるラムダ計算は直観主義的型理論の基盤であり、calculus of constructions や logical framework (LF) の基盤である。Berardi の成果に基づき Barendregt が提案したラムダ・キューブは、純粋な型付きラムダ計算（単純型付きラムダ計算、System F、LF、calculus of constructions など）の関係を体系化したものである。 一部の型付きラムダ計算には「派生型」の記法が導入されている。すなわち、A が B の派生型であるとき、型が A である全ての項は型が B でもある。派生型のある型付きラムダ計算は単に普通の型付きラムダ計算に結合型 (conjunctive type) と F^\leq (F-sub) を加えたものである。 以上の体系はすべて（型のないラムダ計算以外）、「強く正規化 (strongly normalizing)」する。すなわち、全ての計算は停止する。結果としてそれらは論理として一貫しており、uninhabited types がある。しかし、強く正規化しない型付きラムダ計算も存在する。全ての型の型 (Type: Type) を持つ依存型付きラムダ計算は Girard's paradox により正規化しない。この系は最も単純な純粋型システムでもあり、ラムダ・キューブを一般化した形式手法である。明示的な再帰コンビネータを持つ系（Gordon Plotkin の PCF など）も正規化しないが、論理体系として解釈されることを意図していない。実際、PCF (Programming language for Computable Functions) は型付き関数型プログラミング言語であり、型はプログラムが正しく動作することを保証する目的で使われているが、必ずしも停止を保証しない。 型付きラムダ計算はプログラミング言語の新たな型システムの設計で重要な役割を演じている。型付け可能性は一般にプログラミングの好ましい属性を捉え、例えば、プログラムがメモリアクセス違反を起こさないようにするといったことが考えられる。 プログラミングにおいて、強い型付けのプログラミング言語のルーチン（関数、プロシージャ、メソッド）は、型付きラムダ計算と密接に関連している。Eiffelには "inline agent" の記法があり、型付きラムダ式を直接定義して操作できる。例えば、agent (p: PERSON): STRING do Result.
新しい！!: ラムダ計算と型付きラムダ計算 · 続きを見る »
型理論
型理論（かたりろん、Type theory）は、数理論理学の一分野であり、「型」の階層を構築し、それぞれの型に数学的（あるいはそれ以外の）実体を割り当てるものである。階型理論（かいけいりろん、Theory of Types）とも。ある型のオブジェクトはその前提となる型のオブジェクトから構築される。この場合の「型」とは形而上的な意味での「型」である。バートランド・ラッセルは、彼が発見したラッセルのパラドックスにより素朴集合論の問題が明らかにされたことを受けて、型理論を構築した。型理論の詳細はホワイトヘッドとラッセルの 『プリンキピア・マテマティカ』にある。 型理論は、プログラミング言語の理論における型システムのベースにもなっている。「型システム」と「型理論」の語はほぼ同義として扱われることもあるが、ここでは、この記事では数理論理学の範囲を説明し、プログラミング言語の理論については型システムの記事で説明する。.
可算集合
可算集合（かさんしゅうごう、countable set 又は denumerable set）もしくは可付番集合とは、おおまかには、自然数全体と同じ程度多くの元を持つ集合のことである。各々の元に 1, 2, 3, … と番号を付けることのできる、すなわち元を全て数え上げることのできる無限集合と表現してもよい。 有限集合も、数え上げることができる集合という意味で、可算集合の一種とみなすことがある。そのため、はっきりと区別を付ける必要がある場合には、冒頭の意味での集合を可算無限集合と呼び、可算無限集合と有限集合を合わせて高々可算の集合と呼ぶ。可算でない無限集合を非可算集合という。非可算集合は可算集合よりも「多く」の元を持ち、全ての元に番号を付けることができない。そのような集合の存在は、カントールによって初めて示された。.
新しい！!: ラムダ計算と可算集合 · 続きを見る »
参照透過性
参照透過性（さんしょうとうかせい、Referential transparency）は、計算機言語の概念の一種である。ある式が参照透過であるとは、その式をその式の値に置き換えてもプログラムの振る舞いが変わらない(言い換えれば、同じ入力に対して同じ作用と同じ出力とを持つプログラムになる)ことを言う。具体的には変数の値は最初に定義した値と常に同じであり、関数は同じ変数を引数として与えられれば同じ値を返すということになる。当然変数に値を割り当てなおす演算である代入 (Assignment) を行う式は存在しない。このように参照透過性が成り立っている場合、ある式の値、例えば関数値、変数値についてどこに記憶されている値を参照しているかということは考慮する必要がない、即ち参照について透過的であるといえる。 参照透過性が成り立つ言語は式の値がプログラムのテキストから定まるという特徴から宣言型言語 (Declarative language) と呼ばれたり、関数の数学的性質が保たれるという特徴から純粋関数型言語 (Pure functional language) と呼ばれたりする。一方変数の値の変更が認められているような参照透過的でない言語を手続き型言語と呼ぶ。ただ、手続き型言語は機械語プログラミングとの繋がりという歴史的な事情により手続きが式でなく命令列で表現されたことから命令型言語と呼ばれることもあり、そのような場合との対比で単に式（例えば関数や変数の組み合わせ）でプログラムが表現されているだけの言語、あるいは高階関数の仕組みを備えた言語をひっくるめて、代入が可能であるかないかを問わず、関数型言語と呼ぶことも多い。結局現状では単に関数型言語という場合は参照透過的な言語（即ち純粋関数型言語）とそうでない関数型言語を両方とも含むということになっている。 また以上に関連して分散処理を記述する場合に、あるデータがどのノード上にあるかを意識せず透過的にアクセスできるという性質も参照透過性と呼ばれる。.
新しい！!: ラムダ計算と参照透過性 · 続きを見る »
同値関係
数学において、同値関係（どうちかんけい、equivalence relation）は反射的、対称的かつ推移的な二項関係を言う。これらの性質の帰結として、与えられた集合において、一つの同値関係はその集合を同値類に分割（類別）する。 同値関係にあることを表す記法は文献によって様々に用いられるけれども、与えられた集合上の同値関係 に関して二元 が同値であることを "" や "" で表すのがもっともよく用いられる記法である。 に関して同値であることを明示する場合には、"" や "" あるいは "" などと書かれる。.
新しい！!: ラムダ計算と同値関係 · 続きを見る »
合流性
合流性（confluence）は項書き換えシステムなどの特性で、項を複数の方法で書き換え可能な場合に、その複数の方法で書き換えた結果は適切に書き換えてやれば合流するという性質のことである。合流性はチャーチ・ロッサー性と呼ばれる特性と等価である。合流性を持つシステムは書き換え規則の適用順序によらない一貫性を持ち、遅延評価、並行評価、部分評価などの柔軟な評価方法が可能になる。.
定数
数学における定数（ていすう、じょうすう、constant; 常数）あるいは定項 (constant term) は、二つの異なる意味を示し得る。そのひとつは固定 (fix) され、矛盾なく定義された数（またはもっとほかの数学的対象）であり、この意味で言う定数であることをはっきりさせるために「数学定数」（あるいは「物理定数」もそうだが）という語を用いることもある。もう一つの意味は、定数函数またはその（これらはふつうたがいに同一視される）を指し示すもので、この意味での「定数」は扱う問題における主変数に依存しない変数という形で表されるのが普通である。後者の意味での例として、は、与えられた函数の原始函数をすべて得るために特定の原始函数に加えられる、任意の（積分変数に依存しないという意味での）定数函数を言う。 例えば、一般の二次函数はふつう を定数（あるいはパラメタ）として のようにあらわされる。ここに変数 は考えている函数の引数のプレースホルダとなるものである。より明示的に のように書けば がこの函数の引数であることが明瞭で、しかも暗黙の裡に が定数であることを提示できる。この例では、定数 はこの多項式の係数と呼ばれる。 の項は を含まないからと呼ばれ（これを の係数と考えることができる）、多項式において次数が零の任意の項または式は定数である。.
不動点
不動点を三つ持つ関数 数学において写像の不動点（ふどうてん）あるいは固定点（こていてん、fixed point, fixpoint）とは、その写像によって自分自身に写される点のことである。.
不動点コンビネータ
不動点コンビネータ（ふどうてんコンビネータ、fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、fixed-point operator）、パラドキシカル結合子（paradoxical combinator）などとも呼ばれる。ここで関数fの不動点とは、f(x).
新しい！!: ラムダ計算と不動点コンビネータ · 続きを見る »
並列計算
並列計算（へいれつけいさん、parallel computing）は、コンピュータにおいて複数のプロセッサで1つのタスクを動作させること。並列コンピューティングや並列処理とも呼ばれる。問題を解く過程はより小さなタスクに分割できることが多い、という事実を利用して処理効率の向上を図る手法である。また、このために設計されたコンピュータを並列コンピュータという。ディープ・ブルーなどが有名。 関連する概念に並行計算（へいこうけいさん）があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクをスレッドなどをもちいて複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。 特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータやサーバ、スーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。.
新しい！!: ラムダ計算と並列計算 · 続きを見る »
並行計算
並行計算（へいこうけいさん、concurrent computing）とは、コンピュータプログラムにおいて複数の相互作用を及ぼす計算タスクの（同時）並行的実行を指す。.
新しい！!: ラムダ計算と並行計算 · 続きを見る »
一階述語論理
一階述語論理（いっかいじゅつごろんり、first-order predicate logic）とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理（にかいじゅつごろんり、second-order predicate logic）と呼ぶ。それにさらなる一般化を加えた述語論理を高階述語論理（こうかいじゅつごろんり、higher-order predicate logic）という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細は「二階述語論理」「高階述語論理」を参照。.
新しい！!: ラムダ計算と一階述語論理 · 続きを見る »
引数
引数（ひきすう）は、数学における関数やコンピュータプログラムにおける手続きにおいて、その外部と値をやりとりするための特別な変数、あるいはその変数の値のことである。 数学や最適化問題に関するそれ（「パラメータ」とカタカナで表現されることが多い）については「媒介変数」の記事を参照のこと。以下は専らコンピュータプログラミングに関して説明する。 関数・サブルーチン・メソッド等を定義する時に、外部から値を渡される特別な変数として指定されるのが仮引数。関数（等）を呼出す式において、仮引数に対応する式（あるいはその値）が実引数である。実行時には、実引数の値を仮引数が受け取る。 「引数」を「いんすう」と読む読み方もあるが、術語としては変則的に湯桶読みして「ひきすう」としている。数学分野で因数との取違えを防ぐためといった理由もある。.
形式体系
形式体系（けいしきたいけい、Formal System）は、数学のモデルに基づいた任意の well-defined な抽象思考体系と定義される。エウクレイデスの『原論』は史上初の形式体系とされることが多く、形式体系の特徴をよく表している。その論理的基盤による体系の命題と帰結の関係（論理包含）は、他の抽象モデルを何らかの基盤とする体系から形式体系を区別するものである。形式体系は大きな理論や分野（例えばユークリッド幾何学）の基盤またはそのものとなることが多く、現代数学では証明論やモデル理論などと同義に扱われる。ただし形式体系は必ずしも数学的である必然性はなく、例えばスピノザの『エチカ』はエウクレイデスの『原論』の形式を模倣した哲学（倫理学）書である。 形式体系には形式言語があり、その形式言語は基本的な記号（シンボル）で構成される。形式言語の文（式）は公理群を出発点として、所定の構成規則（推論規則）に従って発展する。従って形式体系は基本的な記号群の有限の組み合わせを通して構築された任意個の数式で構成され、その組み合わせは公理群と構成規則群から作り出される。 数学における形式体系は以下の要素から構成される.
新しい！!: ラムダ計算と形式体系 · 続きを見る »
ペアノの公理
ペアノの公理（ペアノのこうり、Peano axioms） とは、自然数全体を公理化したものである。1891年に、ジュゼッペ・ペアノによって定義された。.
新しい！!: ラムダ計算とペアノの公理 · 続きを見る »
チャーチ・ロッサーの定理
チャーチ・ロッサーの定理（チャーチ・ロッサーのていり、Church–Rosser theorem）は、同じラムダ式から始まる二個の異なる簡約がある場合、それぞれの簡約から一連の簡約を行うことで到達可能な式があることを述べる定理である。詳しくは合流性を参照。 Category:数学基礎論の定理 Category:ラムダ計算 Category:数学に関する記事.
新しい！!: ラムダ計算とチャーチ・ロッサーの定理 · 続きを見る »
チャーチ＝チューリングのテーゼ
チャーチ＝チューリングのテーゼ (Church-Turing thesis) もしくはチャーチのテーゼ (Church's thesis) とは、「計算できる関数」という直観的な概念を、帰納的関数と呼ばれる数論的関数のクラスと同一視しようという主張である。テーゼの代わりに提唱（ていしょう）あるいは定立（ていりつ）の語が用いられることもある。このクラスはチューリング・マシンで実行できるプログラムのクラス、ラムダ記法で定義できる関数のクラスとも一致する。よって簡単にはテーゼは、計算が可能な関数とは、その計算を実行できるような有限のアルゴリズムが存在するような関数、よっておおよそコンピュータで実行できる関数と同じだと主張する。.
新しい！!: ラムダ計算とチャーチ＝チューリングのテーゼ · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: ラムダ計算とチューリングマシン · 続きを見る »
バッカス・ナウア記法
バッカス・ナウア記法（Backus-Naur form）とは、文脈自由文法を定義するのに用いられるメタ言語のことで、一般にBNFやBN記法と略される。現在はこのBNFを拡張したEBNF (Extended BNF) が一般的に使われている。EBNFでは正規表現を用いてより簡単に記述でき、プロトコル規定言語であるASN.1や、XMLの構文定義にも利用されている。 ジョン・バッカスとピーター・ナウアがALGOL 60 の文法定義のために考案。当初は文脈自由文法の本来の定義に則り or（|）以外の定義はなく、繰り返しは再帰を利用して表現されている。*、?等を含む正規表現はBNFを拡張したEBNFによって導入された。パーサジェネレータを使用して構文解析器を生成する際に、構文を定義するためにも使う。 ISO/IEC 14977:1996においてEBNFの標準が定義されているが、EBNFにもいろいろな亜種や変種がある。例えば、RFC2234にはABNFという変種が定義されている。しかし、ABNFは標準のEBNFとかなり異なる部分がある。.
新しい！!: ラムダ計算とバッカス・ナウア記法 · 続きを見る »
ラムダ・キューブ
型理論において、ラムダ・キューブ (Lambda cube) とは、8つの異なる型付きラムダ計算の関係を表した図である。これらの計算体系がそれぞれ型と値の間にどのような依存関係を認めるかを整理したもので、単純型付きラムダ計算からCalculus of Constructions (CoC) を導くフレームワークになっている。数学者ヘンク・バレンドレフトによって1991年に提唱された。 ラムダ・キューブの原点は単純型付きラムダ計算に相当し，それぞれの座標軸には次の依存関係が対応付けられている.
新しい！!: ラムダ計算とラムダ・キューブ · 続きを見る »
ラッセルのパラドックス
ラッセルのパラドックス（Russell's paradox）とは、素朴集合論において矛盾を導くパラドックスである。バートランド・ラッセルからゴットロープ・フレーゲへの1902年6月16日付けの書簡における、フレーゲの『算術の基本法則』における矛盾を指摘する記述に表れる。これは1903年に出版されたフレーゲの『算術の基本法則』第II巻（Grundgesetze der Arithmetik II）の後書きに収録されている。同じパラドックスはツェルメロが1年先に発見していたが、彼はその発見を公開せず、ヒルベルトやフッサールなどのゲッティンゲン大学の同僚たちだけに知られているだけだった。 ラッセルが型理論（階型理論）を生み出した目的にはこの種のパラドックスを解消するということも含まれていた。.
新しい！!: ラムダ計算とラッセルのパラドックス · 続きを見る »
プログラミング言語
プログラミング言語（プログラミングげんご、programming language）とは、コンピュータプログラムを記述するための形式言語である。なお、コンピュータ以外にもプログラマブルなものがあることを考慮するならば、この記事で扱っている内容については、「コンピュータプログラミング言語」（computer programming language）に限定されている。.
新しい！!: ラムダ計算とプログラミング言語 · 続きを見る »
プロセス計算
プロセス計算（プロセスけいさん、Process calculus）またはプロセス代数（プロセスだいすう、Process algebras）は、計算機科学において並行システムを形式的にモデリングする各種手法の総称。プロセス計算は、独立エージェントやプロセスの集まりにおける相互作用/通信/同期を抽象的に記述するツールである。また、プロセス記述を操作・分析可能にする代数学的規則も提供し、プロセス間の等価性について（双模倣性を使った）形式的推論を可能とする。主な具体例としては、CSP、CCS、ACP があるJ.C.M. Baeten:, Rapport CSR 04-02, Vakgroep Informatica, Technische Universiteit Eindhoven, 2004年。近年ではこれら以外に π計算(英語)、アンビエント計算、PEPA などもある。.
新しい！!: ラムダ計算とプロセス計算 · 続きを見る »
デリゲート (プログラミング)
デリゲート (delegate、デレゲート) とは、C#、Visual Basic.NETなどの、.NET Frameworkのプログラミング言語にある機能である。.
新しい！!: ラムダ計算とデリゲート (プログラミング) · 続きを見る »
データ型
データ型（データがた、）とは、（コンピュータにおける）データ（値）の種類に関する分類である。データタイプとも。 具体的にいうと、たとえば 0, 1, 2, -42 といったような値は整数型であり、"foo", "Hello" といったような値は文字列型である。プログラミングなどにおいて、まずデータオブジェクトや関数などの「値」について、またさらに、それらに関連付け（束縛）される変数や定数、リテラル、それらを組合せる演算子、さらにそれらからなる式といった構文上の要素の型が、データ型の議論の対象となる。.
新しい！!: ラムダ計算とデータ型 · 続きを見る »
ド・ブラン・インデックス
ド・ブラン・インデックス(英:De Bruijn Index)とは、ラムダ計算において、名前を使わずに引数（束縛変数）を参照するための記法である。オランダ人数学者ニコラース・ホーバート・ド・ブランによって発明された。.
新しい！!: ラムダ計算とド・ブラン・インデックス · 続きを見る »
命令型プログラミング
命令型プログラミング（めいれいがたプログラミング、Imperative Programming）とは、計算機科学において宣言型プログラミングの対となる概念であり、計算をプログラム状態を変化させる文の列で記述するプログラミングパラダイムの一種。自然言語の命令法がなすべき行動への指令を表現するのとよく似た方法で、命令型プログラムはコンピュータが実行すべき命令列で構成される。命令型プログラミングに従ったプログラミング言語を命令型（プログラミング）言語と呼ぶ。一般に命令型プログラミングは、手続き型プログラミングと同義として扱われる。 命令型プログラミングは、宣言型プログラミング（関数型や論理型言語など）と対照的である。Haskellなどの関数型プログラミング言語では、プログラムは文の並びではないし、命令型言語が持つような広域状態を持たない。Prologのような論理プログラミング言語では、命令型言語のように計算の「方法」をプログラムとして記述するのではなく、計算すべき「事物」を定義する。.
新しい！!: ラムダ計算と命令型プログラミング · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: ラムダ計算とアルゴリズム · 続きを見る »
アロンゾ・チャーチ
アロンゾ・チャーチ（Alonzo Church, 1903年6月14日 - 1995年8月11日）はアメリカの論理学者、数学者。ラムダ計算の創案者、「チャーチ＝チューリングのテーゼ」の提唱者として知られる。.
新しい！!: ラムダ計算とアロンゾ・チャーチ · 続きを見る »
オブジェクト指向プログラミング
ブジェクト指向プログラミング（オブジェクトしこうプログラミング、）は、コンピュータ・プログラミングのパラダイムのひとつで、オブジェクト指向の概念や手法を取り入れたものである。プログラムを、データとその振舞が結び付けられたオブジェクトの集まりとして構成する、などといった特徴がある。このパラダイムを指向しているプログラミング言語がオブジェクト指向プログラミング言語である。.
新しい！!: ラムダ計算とオブジェクト指向プログラミング · 続きを見る »
カリーのパラドックス
リーのパラドックス（Curry's paradox）は、素朴集合論や素朴論理学で見られるパラドックスであり、自己言及文といくつかの一見問題ない論理的推論規則から任意の文が派生されることを示す。名称の由来は論理学者のハスケル・カリーから。 ドイツの数学者マルティン・フーゴー・レープ（Martin Hugo Löb）の名をとって レープのパラドックスとも呼ばれている。.
新しい！!: ラムダ計算とカリーのパラドックス · 続きを見る »
カリー化
リー化 (currying, カリー化された.
新しい！!: ラムダ計算とカリー化 · 続きを見る »
カリー＝ハワード同型対応
リー＝ハワード同型対応（カリー＝ハワードどうけいたいおう、Curry-Howard correspondence）とは、プログラミング言語理論と証明論において、計算機プログラムと証明との間の直接的な対応関係のことである。「プログラム＝証明」(proofs-as-programs)・「型＝命題」(formulae-as-types)などとしても知られる。これはアメリカの数学者ハスケル・カリーと論理学者ウィリアム・アルヴィン・ハワードにより最初に発見された形式論理の体系とある種の計算の体系との構文論的なアナロジーを一般化した概念である。通常はこの論理と計算の関連性はカリーとハワードに帰属される。しかしながら、このアイデアはブラウワー、ハイティング、コルモゴロフらが定式化した直観主義論理の操作的解釈の一種と関係している。 At the very beginning, the Curry–Howard correspondence is.
新しい！!: ラムダ計算とカリー＝ハワード同型対応 · 続きを見る »
カントールの対角線論法
ントールの対角線論法（カントールのたいかくせんろんぽう）は、数学における証明テクニック（背理法）の一つ。1891年にゲオルク・カントールによって非可算濃度を持つ集合の存在を示した論文の中で用いられたのが最初だとされている。 その後対角線論法は、数学基礎論や計算機科学において写像やアルゴリズム等が存在しない事を示す為の代表的な手法の一つとなり、例えばゲーデルの不完全性定理、停止性問題の決定不能性、時間階層定理といった重要な定理の証明で使われている。.
新しい！!: ラムダ計算とカントールの対角線論法 · 続きを見る »
ゲーデル数
ーデル数（ゲーデルすう、Gödel number）は、数理論理学において何らかの形式言語のそれぞれの記号や整論理式に一意に割り振られる自然数である。クルト・ゲーデルが不完全性定理の証明に用いたことから、このように呼ばれている。また、ゲーデル数を割り振ることをゲーデル数化（Gödel numbering）と呼ぶ。 ゲーデル数のアイデアを暗に使っている例としては、コンピュータにおけるエンコードが挙げられる。 コンピュータでは何でも0と1で表し、「apple」のような文字列も0と1による数字で表す。 ゲーデル数化とは、このように文字列に数字を対応させる事を指す。 ゲーデル数化は、数式におけるシンボルに数を割り当てる符号化の一種でもあり、それによって生成された自然数の列が文字列を表現する。この自然数の列をさらに1つの自然数で表現することもでき、自然数についての形式的算術理論を適用可能となる。 ゲーデルの論文が発表された1931年以来、ゲーデル数はより広範囲な様々な数学的オブジェクトに自然数を割り振るのに使われるようになっていった。.
新しい！!: ラムダ計算とゲーデル数 · 続きを見る »
コンビネータ論理
ンビネータ論理(Combinatory Logic、組み合わせ論理)は、（Моисей Эльевич Шейнфинкель、Moses Ilyich Schönfinkel）とハスケル・カリー（Haskell Brooks Curry）によって、記号論理での変数を消去するために導入された記法である。最近では、計算機科学において計算の理論的モデルで利用されてきている。また、関数型プログラミング言語の理論（意味論など）や実装にも応用がある。 コンビネータ論理は、コンビネータまたは引数のみからなる関数適用によって結果が定義されている高階関数、コンビネータに基づいている。.
新しい！!: ラムダ計算とコンビネータ論理 · 続きを見る »
スティーヴン・コール・クリーネ
ティーヴン・コール・クリーネ（Stephen Cole Kleene, 1909年1月5日 - 1994年1月25日）は、アメリカの数学者。ウィスコンシン大学マディソン校に勤め、その業績は計算機科学の理論的な基礎を築くのに貢献した。クリーネは、正規表現の発明や、アロンゾ・チャーチ、クルト・ゲーデル、アラン・チューリング、エミール・ポストらと共に帰納的関数論という数理論理学の一分野を創始したことで知られる。クリーネ代数、クリーネ閉包、クリーネの再帰定理、クリーネ不動点定理の由来になっている。クリーネはまたライツェン・エヒベルトゥス・ヤン・ブラウワーが創始した数学的直観主義に貢献した。 クリーネは自分の姓をクレーニ（（IPA））と発音していた。英語圏ではクリーニ（）、クリーン（）などと誤読されることが多く、日本ではクリーネの表記が一般的になってしまっている。 その数理論理学における傑出した業績は、英語圏の論理学者の間に、"Cleanliness is next to godliness"「清潔さは信心深さに次ぐ」をもじって"Kleeneliness is next to Gödeliness"という格言があることにも表れている。.
新しい！!: ラムダ計算とスティーヴン・コール・クリーネ · 続きを見る »
タプル
タプルまたはチュープル（tuple）とは、複数の構成要素からなる組を総称する一般概念。 数学や計算機科学などでは通常、順序付けられた対象の並びを表すために用いられる。個別的には、n 個でできた組を英語で「n-tuple」と書き、日本語に訳す場合は通常「n 組」としている。タプルの概念そのものも組と呼ばれる場合がある。なお、 n-tuple は数学のタプルを意味するほか、同様に double、triple などの拡張として倍数詞の表現にも利用される（詳細は「倍#西洋数学における n 倍を表す表現」を参照）。.
再帰
再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。定義において、再帰があらわれているものを再帰的定義という。 主に英語のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳（回帰#物理学及び再帰性を参照のこと）や、reflexiveの訳として「再帰」が使われることがある。数学的帰納法との原理的な共通性から、recursionの訳として数学では「帰納」を使うことがある。.
再帰的定義
再帰的定義（Recursive Definition）は、再帰的な定義、すなわち、あるものを定義するにあたってそれ自身を定義に含むものを言う。無限後退を避けるため、定義に含まれる「それ自身」はよく定義されていなければならない。同義語として帰納的定義（Inductive Definition）がある。.
新しい！!: ラムダ計算と再帰的定義 · 続きを見る »
B,C,K,Wシステム
B, C, K, Wシステムは、基本的な4つの定数記号 B, C, K, W からなるコンビネータ論理の変種である。この体系はハスケル・カリーの博士論文Grundlagen der kombinatorischen Logikによるもので、その結論部分はCurry 1930において示された。.
新しい！!: ラムダ計算とB,C,K,Wシステム · 続きを見る »
C Sharp
C#（シーシャープ）は、アンダース・ヘルスバーグが設計（デザイン）したプログラミング言語であり、構文（syntax）は（名前にもある通り）C言語や、C言語風に構文が設計されたC++やJavaなどの影響があるが、構文以外についてはヘルスバーグが以前の所属であるBorlandで設計したDelphiからの影響がある。 Microsoftによる謳い文句としては、マルチパラダイムプログラミング言語、強い型付け、命令型、宣言型、手続き型、関数型、ジェネリック、オブジェクト指向の要素を持つ、などといった点が強調されている。 CLIといった周辺も含め、Microsoftのフレームワーク「.NET Framework」の一部である他、VJ++で「非互換なJava」をJavaに持ち込もうとしたような以前のMicrosoftとは異なり、その多くの仕様を積極的に公開し標準化機構に託して自由な利用を許す（ECMA-334、ISO/IEC 23270:2003、JIS X 3015）など、同社の姿勢の変化があらわれている一面でもある（実際に「Mono」という、フリーソフトウェアの定義に合致したライセンスの、コミュニティによる実装がある）。.
新しい！!: ラムダ計算とC Sharp · 続きを見る »
C++
C++（シープラスプラス）は、汎用プログラミング言語の一つである。日本語では略してシープラプラ、シープラなどとも呼ばれる。.
CCS
*CCS, ccs.
C言語
C言語（シーげんご）は、1972年にAT&Tベル研究所のデニス・リッチーが主体となって開発したプログラミング言語である。英語圏では単に C と呼んでおり、日本でも文書や文脈によっては同様に C と呼ぶことがある。.
Communicating Sequential Processes
Communicating Sequential Processes（CSP）とは、並行性に関するプロセス計算の理論のひとつである.
新しい！!: ラムダ計算とCommunicating Sequential Processes · 続きを見る »
第一級オブジェクト
一級オブジェクト（ファーストクラスオブジェクト、first-class object）は、あるプログラミング言語において、たとえば生成、代入、演算、（引数・戻り値としての）受け渡しといったその言語における基本的な操作を制限なしに使用できる対象のことである。ここで「オブジェクト」とは広く対象物・客体を意味し、必ずしもオブジェクト指向プログラミングにおけるオブジェクトを意味しない。第一級オブジェクトは「第一級データ型に属す」という。 この言葉は1960年代にChristopher Stracheyによって「functions as first-class citizens」という文脈で初めて使われた。 言語によって異なるが、第一級オブジェクトは概ね次のような性質をもつ。.
新しい！!: ラムダ計算と第一級オブジェクト · 続きを見る »
第一級関数
計算機科学において、第一級関数（だいいっきゅうかんすう、first-class function、ファーストクラスファンクション）, by Michael Lee Scott, section 11.2 "Functional Programming".
新しい！!: ラムダ計算と第一級関数 · 続きを見る »
純LISP
純LISP（じゅんりすぷ、pure LISP）とは、コンピュータ・プログラミング言語 LISP のうち、ごく基本的な要素だけからなる方言の一種。1960年のジョン・マッカーシーの論文「Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I」で示された。基本的な関数とプリミティブのみしかないが、その言語のインタプリタをその言語で記述できるという性質を持っている。なお、論文とほぼ同時期に発表された、最初の LISP の実装である LISP I は約90個の組み込み関数があり、純LISPではない。.
新しい！!: ラムダ計算と純LISP · 続きを見る »
真理値
真理値 (しんりち、truth value) は、命題論理などの命題の真偽を示す値である。英語のTrueとFalseから、真に対してT、偽に対してFという記号をあてることもある。論理値 (logical value) も同じ。真と偽という値をとることから真偽値ともいうが、非古典論理などで多値論理における「真らしさ」の値も（真と偽以外の値にもなる）真理値である。 コンピュータプログラミング言語などのデータ型では、真理値のような型として真理値型（真偽値型、ブーリアン型などとも）があるものがある。関係演算子の結果などがブーリアン型であり、さらに論理演算子などで組み合わせることができ、それをif文などの制御構造や、条件演算子などで使用できる。.
結合法則
数学、殊に代数学における結合法則（けつごうほうそく、associative law) 、結合則、結合律あるいは演算の結合性（けつごうせい、associativity）は二項演算に対して考えられる性質の一つ。ひとつの数式にその演算の演算子が2個以上並んでいる時、その演算子について、左右どちらの側が優先されるかに関わらず結果が同じになるような演算は結合的 (associative) である。.
新しい！!: ラムダ計算と結合法則 · 続きを見る »
無名再帰
無名再帰(むめいさいき、anonymous recursion, nameless recursion)とは、無名関数において再帰を行うことである。無名関数は名前を持たないため自己を呼び出すために特別の工夫が必要である。.
新しい！!: ラムダ計算と無名再帰 · 続きを見る »
Eiffel
Eiffel（アイフェル、エッフェル）は頑健なソフトウェアの生産に注力したオブジェクト指向プログラミング言語である。.
新しい！!: ラムダ計算とEiffel · 続きを見る »
階乗
数学において非負整数 の階乗（かいじょう、factorial） は、1 から までのすべての整数の積である。例えば、 である。空積の規約のもと と定義する。 階乗は数学の様々な場面に出現するが、特に組合せ論、代数学、解析学などが著しい。階乗の最も基本的な出自は 個の相異なる対象を一列に並べる方法（対象の置換）の総数が 通りであるという事実である。この事実は少なくとも12世紀にはインドの学者によって知られていた。は1677年にへの応用として階乗を記述した。再帰的な手法による記述の後、Stedman は（独自の言葉を用いて）階乗に関しての記述を与えている: 感嘆符(!)を用いた、この "" という表記は1808年にによって発明された。 階乗の定義は、最も重要な性質を残したまま、非整数を引数とする函数に拡張することができる。そうすれば解析学における著しい手法などの進んだ数学を利用できるようになる。.
領域理論
域理論 （りょういきりろん、domain theory）は、領域 (domain) と呼ばれる特別な種類の半順序集合を研究する数学の分野であり、順序理論の一分野である。 計算機科学の表示的意味論（denotational semantics）を構築するために用いられる。 領域理論は、近似と収束という直観的概念を極めて一般的な枠組で形式化し、位相空間と密接な関係をもつ。 表示的意味論に対する他の重要なアプローチとしては距離空間を用いるものがある。.
新しい！!: ラムダ計算と領域理論 · 続きを見る »
順序対
数学における順序対（じゅんじょつい、ordered pair）は、座標 (coordinate) や射影 (projection) とも呼ばれるふたつの成分 (entry) を持つ対象を総称するものである。順序対では常に、第一成分（第一座標、左射影）と第二成分（第二座標、右射影）の対によって対象が一意に決定される。第一座標が a で第二座標が b であるような順序対は通常、(a, b) で表される。「順序」対という呼称は、a.
項書き換え
項書き換え（こうかきかえ、term rewriting）とは、数学・計算機科学・論理学において、式（数式、論理式）の項を別の項に置換する手法を総称する用語である。項書き換え系（term rewriting system、TRS）とは、項の集合とその置換規則から構成される。 項書き換えは非決定論的になることがありうる。ある規則で書き換え可能な項が他の規則でも書き換え可能な場合がありえて、その場合は複数の規則が適用可能と言うことになる。項書き換え系では、項書き換えのためのアルゴリズムは提供されず、書き換え規則の集合のみが提供される。しかし、適当なアルゴリズムと組み合わせれば、項書き換え系はプログラムのような働きをし、実際いくつかの宣言型プログラミング言語は項書き換えに基づいている。.
新しい！!: ラムダ計算と項書き換え · 続きを見る »
計算
計算（けいさん）とは、与えられた情報をもとに、命題に従って演繹することである。 これは人間が無意識のレベルで行っている判断（→判断力）や、動物一般が行っている思考を、計算という形で意識化する手法ともいえ、その意味では「ものを考えること」一般が「計算」の一種だとみなすことも可能である。計算に使用される手続きはアルゴリズムと呼ばれる。対人関係において、戦略をアルゴリズムとして状況を有利に運ぶことも時に「計算」と表現される。 もっとも一般的かつ義務教育の範疇で最初に習うものは、算術（算数）における四則演算を、演算記号に示されたアルゴリズム通りに処理するものである。こういった「計算」は日常生活から専門的分野まで幅広く行われており、これを専門に処理する装置や機械も、人類の歴史において数多く開発され利用されている。.
計算可能関数
計算可能関数（けいさんかのうかんすう、Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。.
新しい！!: ラムダ計算と計算可能関数 · 続きを見る »
計算可能性理論
計算可能性理論（けいさんかのうせいりろん、computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。.
新しい！!: ラムダ計算と計算可能性理論 · 続きを見る »
計算モデル
計算モデル（model of computation）とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。 また、抽象機械（abstract machine）と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。 計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。 計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。 計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。 典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。 ハードウェアとして実装されていない（実装する予定のない）マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。.
新しい！!: ラムダ計算と計算モデル · 続きを見る »
計算機プログラムの構造と解釈
『計算機プログラムの構造と解釈』（Structure and Interpretation of Computer Programs。原題の略称SICPがよく使われる）は、1985年にMIT出版から刊行された、計算機科学分野の古典的な教科書。著者はマサチューセッツ工科大学 (MIT) の教授ハル・アベルソンとジェラルド・ジェイ・サスマン、ジェラルドの妻ジュリー・サスマン。かつてMITコンピュータ科学科の6.001として知られるプログラミングの入門講義で使われていた。第2版（ハードカバー版 ISBN 0-262-01153-0、ペーパーバック版 ISBN 0-262-51087-1）が1996年に刊行された。計算機科学の古典として広く認められている。 表紙に魔術師が描かれているため魔術師本（Wizard Book）としても知られ、まれに表紙の色をとって紫本（Purple Book）とも呼ばれる。 プログラミング言語LISPの方言Schemeが用いられ、抽象化、再帰、インタプリタ、メタ言語的抽象といった計算機科学の概念の真髄が説明されている。 第二版の和田英一による日本語訳（ISBN 978-4894711631）がピアソン桐原から2000年2月に発売された。、和田はHTML版を公開した。。。その後2014年5月に翔泳社より再版されている。.
新しい！!: ラムダ計算と計算機プログラムの構造と解釈 · 続きを見る »
評価戦略
評価戦略（ひょうかせんりゃく、evaluation strategy）とは、プログラミング言語や、ラムダ計算のような式から成る計算模型において、如何なる手順で、評価すなわち式から値を得るか、という（通常決定的な）規則群である。.
新しい！!: ラムダ計算と評価戦略 · 続きを見る »
高階関数
階関数（こうかいかんすう、higher-order function）とは、第一級関数をサポートしているプログラミング言語において、関数（手続き）を引数にしたり、あるいは関数（手続き）を戻り値とするような関数のことである。.
新しい！!: ラムダ計算と高階関数 · 続きを見る »
述語論理
述語論理（じゅつごろんり、）とは、数理論理学における記号的形式体系群を指す用語で、一階述語論理、二階述語論理、、無限論理などが含まれる。これらの形式体系の特徴は、論理式に含まれる変数を量化できる点である。一般的な量化子として、存在量化子 ∃ と全称量化子 ∀ がある。変数は議論領域の要素、関係、関数などである。例えば、関数記号に対する存在量化は「ある関数が存在する」という修飾として解釈される。述語論理の基礎は、ゴットロープ・フレーゲとチャールズ・サンダース・パースがそれぞれ独自に生み出し発展させた。 述語論理と言った場合、一階述語論理を指すこともある。述語論理の公理化された形態を述語計算 (predicate calculus) と呼び、述語論理は非形式的でより直観的なものとする見方もある。 様相作用素と量化子を併用する論理も述語論理の一種とされる。これについては様相論理を参照。.
新しい！!: ラムダ計算と述語論理 · 続きを見る »
関数
関数（かんすう）、函数.
関数型言語
関数型言語（かんすうがたげんご、functional language）は、以下に述べる関数型プログラミングを基本スタイルとして推奨する機能を持つプログラミング言語、関数型プログラミング言語の略称である。.
新しい！!: ラムダ計算と関数型言語 · 続きを見る »
自由変数と束縛変数
数学や形式言語に関連する分野（数理論理学と計算機科学）において、自由変数（または自由変項、free variable）は数式や論理式で置換が行われる場所を指示する記法である。この考え方はプレースホルダーやワイルドカードにも関連する。 変数x は、例えば次のように書くと 束縛変数（または束縛変項、bound variable）になる。 あるいは これらの命題では、x の代わりに別の文字を使っても論理的には全く変化しない。しかし、複雑な命題で同じ文字を別の意味で再利用すると混乱が生じる。すなわち、自由変数が束縛されると、ある意味ではその後の数式の構成をサポートする作業に関与しなくなる。 プログラミングにおいては、自由変数とは関数の中で参照される局所変数や引数以外の変数を意味する。.
新しい！!: ラムダ計算と自由変数と束縛変数 · 続きを見る »
自然数
自然数（しぜんすう、natural number）とは、個数、もしくは順番を表す一群の数のことである。集合論においては、自然数は物の個数を数える基数のうちで有限のものであると考えることもできるし、物の並べ方を示す順序数のうちで有限のものであると考えることもできる。 自然数を 1, 2, 3, … とする流儀と、0, 1, 2, 3, … とする流儀があり、前者は数論などでよく使われ、後者は集合論、論理学などでよく使われる（詳しくは自然数の歴史と零の地位の節を参照）。いずれにしても、0 を自然数に含めるかどうかが問題になるときは、その旨を明記する必要がある。自然数の代わりに非負整数または正整数と言い換えることによりこの問題を避けることもある。 数学の基礎付けにおいては、自然数の間の加法についての形式的な逆元を考えることによって整数を定義する。正の整数ないしは負でない整数を自然数と同一視し、自然数を整数の一部として取扱うことができる。自然数と同様に整数の全体も可算無限集合である。 なお、文脈によっては、その一群に属する個々の数（例えば 3 や 18）を指して自然数ということもある。.
Haskell
Haskell（ハスケル）は非正格な評価を特徴とする純粋関数型プログラミング言語である。名称は数学者であり論理学者であるハスケル・カリーに由来する。.
新しい！!: ラムダ計算とHaskell · 続きを見る »
LISP
LISPは、プログラミング言語である。 によって記述される。-->前置記法などが特徴である。 1958年にはじめて設計されたLISPは、現在広範囲に使用されている高水準プログラミング言語の中でもFORTRANに次いで2番目に古い。ただし、FORTRANと同様に、現在のLISPは初期のものから非常に大きく変化している。 これまでに多数の方言が存在してきたが、今日最も広く知られるLISP方言は、Common LispとSchemeである。 元々、LISPは、アロンゾ・チャーチのラムダ計算表記法に影響を受け、コンピュータープログラムのための実用的かつ数学的な表記法として作られた。そして、すぐに人工知能研究に好まれるプログラミング言語になった。最初期のプログラミング言語として、LISPは計算機科学にて、木構造、ガベージコレクション、動的型付け、条件分岐、高階関数、再帰、セルフホスティング、コンパイラを含む多くのアイディアを切り開いた。 LISPの名前は、「list processor」に由来している。リストはLISPの主要なデータ構造であり、LISPソースコードはそれ自体がリストからできている。その結果、LISPプログラムはソースコードをデータとして操作することができ、プログラマーは、マクロ・システムで新しい構文やLISP埋め込みの新しいDSLを作成できる。 コードとデータの互換性は、LISPにそのすぐに認識できる構文を与える。すべてのプログラム・コードはS式または入れ子のリストとして書かれる。関数呼び出しまたは構文は先頭が関数または演算子の名前で、その続きが引数であるリストとして書かれる。具体的には、3つの引数を取る関数fは、(f arg1 arg2 arg3)として呼び出される。.
新しい！!: ラムダ計算とLISP · 続きを見る »
ML (プログラミング言語)
ML（えむえる、Meta-Language）は、関数型言語のひとつである。現代風の関数型言語としては歴史が古いほうで、型推論機能などを持つが、デフォルトの評価戦略は遅延評価ではなく先行評価で、書き換えが可能なレコード型を持つなど、いわゆる「純粋関数型」でない特徴や機能を持つ。.
新しい！!: ラムダ計算とML (プログラミング言語) · 続きを見る »
Pascal
Pascal（パスカル）は、ニクラウス・ヴィルトの設計（デザイン）によるコンピュータ・プログラミング言語である。ALGOL（直接的にはその一派生である、ヴィルトが関与したALGOL W）などの影響があるが、個人の設計であることに由来する簡素だがよく整った言語仕様（構文と意味）を持つ。用途の中に教育を意識しており、構造化された制御構造など、その当時「良きプログラミングの慣習」と考えられていたことの影響もある。一方で批判者からは、あくまでも教育用に過ぎない言語だ、といったような評もあることにはあったが、PascalコンパイラをPascalで書ける（いわゆる言語処理系のブートストラップ）ことをはじめ、Pascalで書かれた#実用プログラム例は多くある。名前は、哲学者・数学者・科学者で、機械式計算機を製作するなど技術者でもあったブレーズ・パスカルにあやかったものである。.
新しい！!: ラムダ計算とPascal · 続きを見る »
SKIコンビネータ計算
SKIコンビネータ計算は型無しラムダ計算を単純化した、ひとつの計算モデルである。このモデルは、ある種のプログラミング言語と考えることができるが、人間によるソースコードの記述には適さない（難解プログラミング言語には時折採用される）。その代わり、このモデルは非常に単純なチューリング完全な言語であるため、アルゴリズムの数学理論においては重要である。また関数型言語を実行する抽象機械のモデルとして使っている例もある。 ラムダ計算におけるあらゆる演算は、SKIにおいて3つの定数記号S, KおよびI（これらをコンビネータと呼ぶ）および変数記号によって表現できる。2引数の関数適用演算のみを持つ形式言語の構文木と考えれば、定数記号と変数記号を葉とする二分木と捉えることもできる。 実際には、 I はモデルを簡単にするために導入されたものであり、SKIシステムを展開するにはSとKの2つで十分である。.
新しい！!: ラムダ計算とSKIコンビネータ計算 · 続きを見る »
Smalltalk
Smalltalk（スモールトーク）は、Simula のオブジェクト（およびクラス）、LISPの徹底した動的性、LOGO のタートル操作や描画機能に、アラン・ケイの「メッセージング」というアイデアを組み合わせて作られたクラスベースの純粋オブジェクト指向プログラミング言語、および、それによって記述構築された統合化プログラミング環境の呼称。 Smalltalk で一語であり、「Small Talk」「SmallTalk」などは誤りである。 大規模な開発実績としてはCargill Lynx Projectがあり、国産製品の開発実績としてはMCFrameがある。.
新しい！!: ラムダ計算とSmalltalk · 続きを見る »
System F
System Fは型付きラムダ計算の一体系で，単純型付きラムダ計算に型についての全称量化を導入したものである．2階ラムダ計算や（ジラール–レイノルズ）多相ラムダ計算としても知られる．プログラミング言語におけるパラメータ多相を形式化するもので，MLやHaskellのような関数型言語の理論的な背景となっている．System Fは論理学者のジャン＝イヴ・ジラールおよび計算機科学者のジョン・C・レイノルズによって独立に発見された． 単純型付きラムダ計算では，関数についての変数とその束縛が存在するが，System Fでは型についての変数とその束縛が追加されている．例えば恒等関数は任意の型AについてA \to Aの形の型を持ちうるが，System Fではこのことが次の判断が成り立つことによって表されている: ここで，\alphaは型変数である．また，小文字の\lambdaが通常の値レベルの抽象を表しているのに対して，大文字の\Lambdaを型レベルの抽象を表すために使用している． 項書換え系として見ると，System Fは強正規化性を持つ．しかしながらSystem Fにおける型推論は決定不能である．またSystem Fはカリー＝ハワード同型の下で，全称量化のみを用いる2階直観主義論理の断片に対応する．System Fは依存型などを含んだより強力なラムダ計算とともに，ラムダ・キューブの一角であるとみなすこともできる．.
新しい！!: ラムダ計算とSystem F · 続きを見る »
Unlambda
Unlambda（アンラムダ）はコンビネータ論理とラムダ計算に基づく、仕様の小さな、ほぼ純粋な関数型言語のプログラミング言語である。デビッド・マドレ(David Madore)によって設計された。.
新しい！!: ラムダ計算とUnlambda · 続きを見る »
束縛 (情報工学)
束縛またはバインディング（Binding）は一般に、参照 (情報工学) の集合である。コンピュータ関連で「束縛」という語が使われるものはいくつかあり、それぞれ具体的な内容は異なるので、以下いくつかの例を示す。.
新しい！!: ラムダ計算と束縛 (情報工学) · 続きを見る »
決定可能性
決定可能（けっていかのう、decidable）は、論理学において、論理式の集合のメンバーシップの決定をする実効的（effectiveな）方法が存在することを指す。決定可能性（けっていかのうせい、decidability）は、そのような属性を指す。命題論理のような形式体系は、論理的に妥当な論理式（または定理）の集合のメンバーシップを実効的に決定できるなら、決定可能である。ある決まった論理体系における理論（論理的帰結で閉じている論理式の集合）は、任意の論理式がその理論に含まれるか否かを決定する実効的方法があれば、決定可能である。.
新しい！!: ラムダ計算と決定可能性 · 続きを見る »
文脈自由文法
文脈自由文法（ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG）は、形式言語の理論（特に、生成文法）において全生成規則が以下のようである形式文法である。 ここで V は非終端記号であり、w は終端記号と非終端記号の（0個を含む）任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できる、という所から来ている（「文脈無用」という訳の提案もある）。文脈自由文法によって生成される形式言語を文脈自由言語という。.
新しい！!: ラムダ計算と文脈自由文法 · 続きを見る »
数学的帰納法
数学的帰納法（すうがくてききのうほう、mathematical induction）は自然数に関する命題 が全ての自然数 に対して成り立っている事を証明するための、次のような証明手法である自然数の定義は を含む流儀とそうでない流儀があるが、ここでは後者を採用した。。.
新しい！!: ラムダ計算と数学的帰納法 · 続きを見る »
