Functional Programming in Lean

Introduction🔗

Lean은 종속 타입 이론에 기반한 대화형 정리 증명기다. Microsoft Research에서 처음 개발되었으며, 현재는 Lean FRO에서 개발한다. 종속 타입 이론은 프로그램과 증명의 세계를 하나로 묶으므로 Lean은 프로그래밍 언어이기도 하다. Lean은 이 두 가지 성격을 중요하게 여기며 범용 프로그래밍 언어로 사용하기에 적합하도록 설계되었다. 심지어 Lean 자체로 구현되어 있다. 이 책은 Lean으로 프로그램을 작성하는 방법을 다룬다.

프로그래밍 언어로서 Lean은 종속 타입을 갖춘 엄격한 순수 함수형 언어다. Lean으로 프로그래밍을 배우는 일의 큰 부분은 이러한 각 속성이 프로그램 작성 방식에 어떤 영향을 주는지, 그리고 함수형 프로그래머처럼 생각하는 법을 익히는 것이다. 엄격성은 Lean의 함수 호출이 대부분의 언어와 비슷하게 동작한다는 뜻이다. 즉 함수 본문이 실행되기 전에 인수가 완전히 계산된다. 순수성은 프로그램의 타입이 명시하지 않는 한 Lean 프로그램이 메모리 위치 수정, 이메일 전송, 파일 삭제 같은 부수 효과를 가질 수 없다는 뜻이다. 함수가 다른 값과 마찬가지로 일급 값이고 실행 모델이 수학적 표현식의 평가에서 영감을 받았다는 의미에서 Lean은 함수형 언어다. Lean의 가장 특이한 기능인 종속 타입은 타입을 언어의 일급 부분으로 만들어 타입이 프로그램을 포함하고 프로그램이 타입을 계산할 수 있게 한다.

이 책은 Lean을 배우려는 프로그래머를 위한 것이며, 함수형 프로그래밍 언어를 사용해 본 적이 없어도 된다. Haskell, OCaml, F# 같은 함수형 언어에 익숙할 필요는 없다. 반면 대부분의 프로그래밍 언어에 공통적인 반복문, 함수, 자료 구조 같은 개념은 알고 있다고 가정한다. 이 책은 함수형 프로그래밍을 처음 배우는 좋은 책이지만, 프로그래밍 전반을 처음 배우는 책으로는 적합하지 않다.

Lean을 증명 보조기로 사용하는 수학자도 언젠가는 맞춤형 증명 자동화 도구를 작성해야 할 가능성이 높다. 이 책은 그들을 위한 책이기도 하다. 이러한 도구가 정교해질수록 함수형 언어의 프로그램과 비슷해지지만, 대부분의 수학자는 Python과 Mathematica 같은 언어로 훈련받는다. 이 책은 그 간극을 메워 더 많은 수학자가 유지 보수하기 쉽고 이해하기 쉬운 증명 자동화 도구를 작성하도록 돕는다.

이 책은 처음부터 끝까지 선형으로 읽도록 구성했다. 개념을 한 번에 하나씩 소개하며, 뒤의 절에서는 앞의 절을 익혔다고 가정한다. 뒤의 장에서 앞서 짧게 다룬 주제를 깊이 있게 설명하는 경우도 있다. 책의 일부 절에는 연습문제가 있다. 절의 이해를 굳히려면 연습문제를 풀어 보는 것이 좋다. 책을 읽으면서 Lean을 탐색하고 배운 내용을 창의적으로 활용할 새로운 방법을 찾는 것도 유익하다.

Getting Lean🔗

Lean으로 작성한 프로그램을 쓰고 실행하기 전에 자신의 컴퓨터에 Lean을 설치해야 한다. Lean 도구는 다음으로 구성된다.

  • elanrustup이나 ghcup처럼 Lean 컴파일러 툴체인을 관리한다.

  • lakecargo, make, Gradle처럼 Lean 패키지와 의존성을 빌드한다.

  • lean은 개별 Lean 파일의 타입을 검사하고 컴파일하며 현재 작성 중인 파일에 대한 정보를 프로그래머 도구에 제공한다. 보통 사용자가 직접 실행하기보다 다른 도구가 lean을 호출한다.

  • Visual Studio Code나 Emacs 같은 편집기 플러그인은 lean과 통신하고 그 정보를 편리하게 표시한다.

최신 Lean 설치 방법은 Lean 매뉴얼을 참고하라.

Typographical Conventions🔗

Lean에 입력으로 제공하는 코드 예제는 다음과 같이 표시한다.

def add1 (n : Nat) : Nat := n + 1#eval add1 7

위의 마지막 줄(#eval로 시작하는 줄)은 Lean에 답을 계산하라고 지시하는 명령이다. Lean의 응답은 다음과 같이 표시한다.

8

Lean이 반환하는 오류 메시지는 다음과 같이 표시한다.

Application type mismatch: The argument
  "seven"
has type
  String
but is expected to have type
  Nat
in the application
  add1 "seven"

경고는 다음과 같이 표시한다.

declaration uses `sorry`

Unicode🔗

관용적인 Lean 코드는 ASCII에 속하지 않는 다양한 유니코드 문자를 사용한다. 예를 들어 이 책의 첫 장에는 α, β 같은 그리스 문자와 화살표 가 나온다. 덕분에 Lean 코드는 일반적인 수학 표기와 더 비슷해진다.

기본 Lean 설정에서는 Visual Studio Code와 Emacs 모두 백슬래시(\) 뒤에 이름을 입력해 이러한 문자를 쓸 수 있다. 예를 들어 α를 입력하려면 \alpha를 입력하라. Visual Studio Code에서 문자를 입력하는 방법을 알려면 해당 문자 위에 마우스를 올리고 도구 설명을 확인하라. Emacs에서는 해당 문자에 포인트를 둔 채 C-c C-k를 사용하라.

Release history🔗

October, 2025🔗

책을 최신 안정 Lean 릴리스(버전 4.23.0)에 맞게 갱신했으며 함수형 귀납법과 grind 전술을 설명한다.

August, 2025🔗

책에서 코드를 복사해 붙여 넣을 때 발생하는 문제를 해결한 유지 보수 릴리스다.

July, 2025🔗

Lean 4.21에 맞게 책을 갱신했다.

June, 2025🔗

Verso를 사용해 책의 형식을 다시 지정했다.

April, 2025🔗

책을 광범위하게 갱신했으며 이제 Lean 4.18을 설명한다.

January, 2024🔗

예제 프로그램의 회귀를 수정한 작은 버그 수정 릴리스다.

October, 2023🔗

첫 유지 보수 릴리스에서 여러 작은 문제를 수정하고 최신 Lean 릴리스에 맞게 본문을 갱신했다.

May, 2023🔗

이제 책이 완성되었다! 4월 사전 릴리스와 비교해 많은 세부 사항을 개선하고 사소한 오류를 수정했다.

April, 2023🔗

이 릴리스에는 전술로 증명을 작성하는 막간과 성능·비용 모델의 논의를 종료성과 프로그램 동치의 증명과 결합한 마지막 장을 추가했다. 최종 릴리스 전의 마지막 릴리스다.

March, 2023🔗

이 릴리스에는 종속 타입과 인덱스된 패밀리로 프로그래밍하는 장을 추가했다.

January, 2023🔗

이 릴리스에는 do 표기에서 사용할 수 있는 명령형 기능을 설명하는 모나드 변환기 장을 추가했다.

December, 2022🔗

이 릴리스에는 구조체와 타입 클래스를 더 자세히 설명하는 애플리커티브 펑터 장을 추가했다. 모나드 설명도 개선했다. 2022년 12월 릴리스는 겨울 휴일 때문에 2023년 1월로 연기되었다.

November, 2022🔗

이 릴리스에는 모나드로 프로그래밍하는 장을 추가했다. 또한 강제 변환 절의 JSON 사용 예제를 완전한 코드가 포함되도록 갱신했다.

October, 2022🔗

이 릴리스에서 타입 클래스 장을 완성했다. 또한 개념을 조금만 알고 있어도 표준 라이브러리 타입 클래스를 이해하는 데 도움이 되므로, 타입 클래스 장 바로 앞에 명제·증명·전술을 소개하는 짧은 막간을 추가했다.

September, 2022🔗

이 릴리스에는 연산자 오버로딩을 위한 Lean의 메커니즘이자 코드를 조직하고 라이브러리를 구조화하는 중요한 수단인 타입 클래스 장의 전반부를 추가했다. 또한 Lean 스트림 API의 변경을 반영하도록 두 번째 장을 갱신했다.

August, 2022🔗

세 번째 공개 릴리스에는 Lean의 부수 효과 모델과 함께 프로그램을 컴파일하고 실행하는 방법을 설명하는 두 번째 장을 추가했다.

July, 2022🔗

두 번째 공개 릴리스에서 첫 장을 완성했다.

June, 2022🔗

소개와 첫 장의 일부로 이루어진 첫 공개 릴리스다.

About the Author🔗

David Thrane Christiansen은 20년 동안 함수형 언어를, 10년 동안 종속 타입을 사용해 왔다. Daniel P. Friedman과 함께 종속 타입 이론의 핵심 아이디어를 소개하는 The Little Typer를 썼다. 코펜하겐 IT 대학교에서 박사 학위를 받았다. 학업 중 Idris 언어의 첫 버전에 크게 기여했다. 학계를 떠난 뒤 오리건주 포틀랜드의 Galois와 덴마크 코펜하겐의 Deon Digital에서 소프트웨어 개발자로 일했으며 Haskell Foundation의 사무총장을 지냈다. 집필 당시에는 Lean Focused Research Organization에서 Lean 전업 개발자로 근무하고 있다.

License🔗

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

이 책의 원본은 David Thrane Christiansen이 Microsoft Corporation과의 계약으로 작성했으며, Microsoft는 이를 Creative Commons Attribution 4.0 International License로 아낌없이 공개했다. 현재 버전은 최신 Lean 버전의 변경을 반영하도록 저자가 원본에서 수정했다. 변경 사항의 자세한 기록은 책의 소스 코드 저장소에서 확인할 수 있다.