[답장} 람다 계산법에 대하여
Sugwoo Byun
반갑습니다. 아마도 컴퓨터를 전공하시는 분 같은데, 람다 계산법은
프로그래밍 언어의 기초 학문으로서 매우 중요한 역할을 합니다.
원래 람다 계산법은 수학의 foundation을 연구하면서 개발된
이론으로서 수학에서도 중요한 역할을 하는 것으로 알고 있고
외국에서는 수학을 전공하는 분들 중에서 람다 계산법을
연구하는 사랍들이 많습니다. 우리나라의 수학과에서는 별
관심을 갖지 않는 것 같읍니다.
람다 계산법은 1930년대 후반 미국의 수학자 Church에 의해서
개발된 이론입니다. 그 당시 mathematical logic 분야에 학문이
많은 발전을 하면서 Church는 computability에 대한 그의 아이디어를
검증하기 위한 이론적 도구로서 사용하였던 것 같읍니다. Church의
유명한 Church's Thesis에 따라 모든 computable function은 람다
계산법이나 Turing Machine 등으로 표현될 수 있다고 인식되고 있습니다.
Church, Rosser, Kleene, Turing 등의 공적으로 computability에 대한
연구는 획기적인 발전을 하였으며, 오늘날의 컴퓨터를 탄생시키게 되는
중요한 역할을 하였습니다 (현재, 컴퓨터 과학 분야에서 수여하는 상 중에서
가장 권위있는 상은 ACM의 Turing Award로서, Turing에게 많은 공적을 돌리고
있지만, Church의 공적 또한 Turing에 절대 못지 않다고 저는 생각하고
있습니다.)
람다 계산법은 일종의 매우 간단한 구문적 체계를 갖는 이론적 프로그래밍
언어라고 생각하셔도 좋습니다. 컴퓨터에서 프로그래밍 할 수 있는 모든
함수 (혹은 알고리즘)은 람다 계산법으로 표현될 수 있으까요. 프로그래밍
언어 관련 많은 문제들이 람다 계산법을 이용하여 표현될 수 있읍니다.
상대적으로 현재 사용되고 있는 프로그래밍 언어들의 구문은 매우 복잡하므로,
프로그래밍과 관련한 새로운 아이디어들을 그러한 프로그래밍 언어에서
실험하는 대신, 구문적 구조가 간단한 람다 계산법을 통하여 실험해 볼 수
있습니다. 이러한 이유로 현재 프로그래밍 언어 분야에서는 람다 계산법이
`표준 이론'으로서 받아들여 지고 있으며 널리 사용되고 있는 실정입니다.
람다 계산법의 이러한 특징을 잘 반영하여 개발된 언어들이 SML, Haskell
등과 같은 함수 언어 (functional programming) 입니다.
너무 프로그래밍 언어와 관련된 이야기만을 하는 것 같군요.
mathematical logic에서 논의대는 대부분의 문제들이 람다계산법을
이용하여 설명되고 있습니다. 예를 들어, syntax, semantics, theories 등등.
현재 람다 계산법과 관련하여 가장 좋은 평가를 받고있는 책은
H.P. Barendregt, "The Lambda Calculus: Its Syntax and Semantics",
North-Holland, 1984.
입니다. Barendregt의 책의 내용은 방대하면서도 여러 중요한 내용들을
정확하고 간결하게 쓴 것으로 좋은 평을 받고 있습니다.
람다 계산법은 원래 type-free이었지만, type에 대한 중요성이 날고
늘어나고 연구도 많이 진척되어 typed-lambda calculus에 대한 자료도
많이 찾아 볼 수 있습니다. 제가 알기로는 Barendregt가 typed lambda calculus
에 대하여 책을 써서 출판되었는 데, 아마도 Oxford University Press 일
것으로 짐작하고 있습니다. 기타 학술회의 proceedings 에서도 많은
논문을 찾아 볼 수 있습니다. 예를 들어, Login In Computer Science (IEEE),
Principles Of Programming Languges (IEEE), Typed Lambda Calculus,
Computer Science Logic (Springer-Verlag의 Lecture Notes in Computer
Science) 등등 입니다.
제가 가지고 있는 자료가 있으니, 관심이 있는 분은 연락주시기
바랍니다.
-------------------------------------------------------------
변 석우
부산시 남구 대연동 경성대학교 정보과학부 (우편번호 : 608-736)
E-mail: swb...@csd.kyungsung.ac.kr, Tel: 051-620-4675, Fax: 051-627-4115