태그 보관물: lambda-calculus

lambda-calculus

Lambda 미적분학은 순전히 구문 론적입니까? 의해 생성

나는 Lambda 미적분학에 대해 몇 주 동안 읽었지만 기존의 수학 함수와 실질적으로 다른 것을 보지 못했으며 그것이 단지 표기법의 문제인지 또는 새로운 것이 있는지 알고 싶습니다. 모든 수학 함수에 적용되지 않는 람다 미적분학 공리에 의해 생성 된 속성 또는 규칙. 예를 들어, 나는 그것을 읽었습니다.

“익명 함수가있을 수 있습니다” : Lambda 함수는 익명이 아니며 모두 람다라고합니다. 수학적 표기법에서 이름이 중요하지 않은 경우 다른 함수에 동일한 변수를 사용하는 것이 허용됩니다. 예를 들어, Galois Connection의 두 기능을 종종 *라고합니다.

“함수는 함수를 입력으로 받아 들일 수 있습니다” : 새로운 기능은 아닙니다.

“함수는 블랙 박스입니다” : 입력과 출력만으로도 수학 함수에 대한 유효한 설명입니다 …

이것은 토론이나 의견이있는 질문처럼 보일 수 있지만이 질문에 대한 “올바른”답변이 있어야한다고 생각합니다. 람다 미적분학이 수학 함수로 작업하기위한 표기법 또는 구문 표기법인지 또는 람다와 일반 함수 사이에 실질적 또는 의미 론적 차이가 있는지 알고 싶습니다.



답변

아이러니하게도, 제목은 제자리에 있지만 “람다 미적분학은 단지 표기법”이라는 의미가 아닙니다.

Lambda 항 은 함수가 아닙니다 1 . 그것들은 구문 조각, 즉 페이지의 심볼 모음입니다. 우리는 이러한 기호 모음을 조작하는 규칙이 있습니다. 가장 크게 베타를 줄입니다. 여러 수 있습니다 별개의 람다 조건 에 해당 같은 기능을. 2

귀하의 요점을 직접 해결하겠습니다.

첫째, 람다는 재사용되는 이름이 아닙니다. 그것은 매우 혼란 스러울뿐만 아니라 (또는 )는 쓰지 않습니다. 가 함수의 이름 인 경우 우리는 를 쓰는 것처럼 할 것입니다 . 에서 우리가 대체 할 수 같은 제조 람다 용어와 (이 람다 용어에 의해 정의 된 경우) 의미 , 기능을하지 나타낼 수있는 표현이며 함수를 선언하는 선언 (이름 :

λ(x)

(λ x)

λ

f(x)

f(x)

f

(λy.y)(x)

(λy.y)

λ

또는 다른 것). 어쨌든 용어 / 표기법에 과부하가 걸리면 문맥을 통해 명확하게 표현할 수있는 방식으로 (하나의 희망) 이루어지며, 람다 용어에는 해당되지 않습니다.

다음 요점은 괜찮지 만 다소 관련이 없습니다. 이것은 Team Lambda 약관 및 팀 기능이있는 경쟁이 아니며 오직 하나만 이길 수 있습니다. 람다 용어의 주요 적용은 특정 종류의 기능을 연구하고 이해하는 것입니다. 다항식은 함수를 자주 식별하지 않지만 함수는 아닙니다. 다항식을 공부한다고해서 모든 함수가 다항식이어야한다고 생각하는 것은 아니며, 다항식이 공부할 가치가있는 “새로운”무언가를해야하는 경우도 아닙니다.

집합 이론 함수는 블랙 박스가 아니지만 입력-출력 관계에 의해 완전히 정의됩니다. (그들은 말 그대로 있습니다 자신의 입력 – 출력 관계.) 람다 용어도없는 블랙 박스 그리고 그들은이되어 있지 자신의 입력 – 출력 관계에 의해 정의. 앞에서 언급했듯이 동일한 입출력 관계를 생성하는 고유 한 람다 항을 가질 수 있습니다. 이것은 또한 람다 항이 함수가 될 수는 없지만 함수를 유도 할 수 는 있다는 사실을 강조합니다 . 2

실제로 다항식과 람다 항의 유사점은 매우 유사하므로 다항식과 그 함수가 구별하는 기능을 이해하지 못할 수 있으므로 조금 더 자세히 설명하겠습니다. 3 일반적으로 다항식이 도입 될 때 (일반적으로 실제 계수가있는 경우) 특정 유형의 실제 함수로 취급됩니다. 이제 LFSR ( linear-feedback shift register) 이론을 고려하십시오 . 그것은 대한 (단 변량) 다항식의 이론 이지만, 우리가 이것을 함수 로 생각하면 최대 함수가 있습니다. 그러나 보다 무한한 수의 다항식이 있습니다. 4

F2

F2F2

4

F2

이를 보는 한 가지 방법은 이러한 다항식을 함수 이외의 다른 것으로 해석 할 수 있다는 것입니다 . 실제로 대수도 마찬가지입니다. 의 LFSR을 위해, 우리는 일반적으로 우리가 함수로 표현 될 수 원하는 경우, 비트 스트림에 대한 작업으로 다항식을 해석 , 비록 그러한 기능의 대부분은 LFSR 해석의 이미지에 있지 않을 것입니다.

F2F2

F2

2N2N

이것은 람다 용어에도 적용되며, 둘 다 함수 이외의 것으로 해석 할 수 있습니다. 그것들은 또한 일반적으로 셀 수 없을 정도로 무한한 함수들보다 훨씬 다루기 쉬운 객체입니다. 그것들은 임의의 함수보다 훨씬 더 계산적입니다. 다항식 (적어도 계산 가능하게 표현 가능한 계수 포함) 및 람다 항을 조작하는 프로그램을 작성할 수 있습니다. 실제로, 형식화되지 않은 람다 항은 계산 가능한 함수의 원래 모델 중 하나입니다. 이러한보다 상징적 / 구문 적 계산적 / 계산적 관점은 람다 미적분학의보다 의미론적인 해석보다 특히 유형화되지 않은 람다 미적분학에 대해 더 강조된다 . 타이핑람다 용어는 훨씬 더 관리하기 쉬운 것으로 일반적으로 (항상 그런 것은 아니지만) 설정된 이론 함수로 쉽게 해석 될 수 있지만 일반적으로 형식화되지 않은 람다 미적분보다 함수 이외의 더 광범위한 클래스로 해석 될 수도 있습니다. 그들은 또한 자신의 풍부한 문법 이론과이 논리에 매우 깊은 연결을 .

1 문제가 다른 방향으로 진행될 수 있습니다. 함수가 무엇인지에 대한 오해가있을 수 있습니다.

2 이것은 실제로 간단하지 않습니다. 를 들어 형식화되지 않은 람다 계산법, 정말 순진 같은 임의의 람다 용어 해석하는 의미가 없습니다 세트 이론적 기능을 . 해석의 영역이 무엇인지 명확히하려고 할 때 이것을 볼 수 있습니다. 나는 세트의 요소로 람다 용어를 해석 할 경우 , 나는 또한에 함수로 해석 할 수 있도록하려면 및에 I 기능 응용 프로그램으로 응용 프로그램을 해석하고자하기 때문이다. 싱글 톤 세트에만 해당되는 (또는 약화)로 끝납니다 . 유형화되지 않은 람다 미적분학에 필요한 것은 반사성 객체입니다.

D

D

D

DDD

, 세트 범주의 경우 사소한 반사성 개체가 없습니다. 이야기는 입력 된 람다 용어와 는 약간 다르지만 여전히 사소하지 않을 수 있습니다.

3 이 구별이 명확하다면, 비유는 상당히 유익해야합니다.

4 이 문제는 복소수, 실수, 유리수 또는 정수와 같이 특징이 0 인 필드에서는 발생하지 않으므로 여전히 존재하기는하지만 구분이 명확하지 않습니다.


답변

변수의 개념에 대해 생각하십시오. 기본과 같은 오래된 언어에서는 동적 할당이 없었으며 각 변수마다 하나의 이름이 필요했습니다. (이것은 배열이 있었기 때문에 완벽하게 정확하지는 않지만 아이디어는 …입니다) 많은 문제에서 프로그램이 정의하는 이름의 수에 제한되지 않고 원하는만큼 많은 변수를 할당 할 수 있어야합니다.

Lambda 함수를 사용하면 함수 이름에 대한 동일한 제한을 제거하여 프로그램이 필요한만큼의 함수를 정의하고 다른 변수와 동일한 복잡한 데이터 구조에 “저장”할 수 있습니다. 이것은 일반적인 명명 된 함수로 할 수있는 것이 아닙니다.


답변