Lisp에서의 진리 오라클: 타입 이론, 커리-하워드 동형 사상, call/cc에 대한 기묘한 이야기

이 글에서는 Lisp에서 임의의 수학적 명제의 참/거짓을 판별하는 프로그램인 "진리 오라클"을 작성하려는 시도를 다룹니다. 저자는 커리-하워드 동형 사상을 소개하여 논리적 증명이 형식화된 함수형 프로그래밍의 표현식에 어떻게 대응하는지 설명합니다. Racket의 call/cc 함수(피어스 법칙과 동형)를 사용하여 배중률과 동형인 프로그램을 구현하려고 시도하지만, 실험 결과는 예상 밖입니다. 오라클은 불가능한 타입 값에 접근하려고 할 때만 참을 반환하고, 그 외에는 항상 거짓을 반환합니다. 이는 고전 논리와 구성적 논리의 차이점과 call/cc 함수의 비표준 제어 흐름 메커니즘을 보여줍니다. 마지막으로 저자는 "악마와의 거래"라는 은유를 사용하여 이 기묘한 행동을 설명하고 call/cc 함수 뒤에 숨겨진 시간 여행과 같은 메커니즘을 제시합니다.