Important
이 포스팅은 Lambda Calculus 를 알고있다는 전제 하에 작성되었습니다.
Lambda Calculus에 관심이 있고, 이전에 Lambda Diagram 을 탐구한 적도 있어서, Lambda Calculus의 시각화에 관심이 있었다.
아래 영상을 보던 도중, Lambda Calculus를 2차원 모자이크의 형태로 시각화할 수 없겠느냐는 생각을 하게 되었다.
Lambda Treemap
Lambda Calculus에는 세 가지 문법이 있다.
- Variable - 변수
- Abstraction - 추상화
- Application - 적용
그리고 각 문법은 이진 트리에 적용될 수 있다.
- 각 변수, 추상화, 적용은 하나의 노드를 나타낸다.
- 변수는 leaf 노드이다.
- 추상화는 노드이되, 추상화임을 나타내는 표시를 한다.
- 적용은 lhs가 적용 대상 함수, rhs가 적용되는 변수(인자)이다.
 |  |  |
 |
Binary treemap(이진 트리맵)은 이진 트리의 또 다른 하나의 표현 방법으로, 역시 이를 사용해 lambda calculus를 시각화할 수 있다.
가장 먼저, 변수는 단순한 색을 가진 직사각형으로 표현된다.
두 번째, 추상화는 람다 항을 둘러싸는 색을 가진 테두리로 표현된다.
세 번째, 적용은 람다 항을 노드로 갖는 이진 트리맵의 형태로 표현된다.
Church Numeral
다음으로, Church numeral 표현은 다음과 같다.
 |  |  |
Beta Reduction
적용을 실제로 하는 방법은, 추상화의 테두리 색에 해당하는 직사각형(변수)들을 전부 인자 트리맵으로 교체하는 것이다.
또한, 적용 과정에서 식의 위상이 바뀌며 종횡 위상이 뒤바뀔 수 있다.
직접 체험해 보기
바이브 코딩으로 람다 트리맵의 자동 생성과 애니메이션을 구현했다.
https://ywbird.github.io/slop-lambda-treemap/[↗]
부록
부록 A: 제작 스케치들
부록 B: 디자인 과정
Lambda Diagram에서는 각 변수가 세로선, 적용이 가로선, 추상화(변수 선언)가 최상단의 수평선으로 그려진다.
그러나 직사각형을 기반으로 시각화할 때는 필연적으로 직사각형이 점점 작아질 것이고, Lambda Diagram처럼 추상화(변수 선언)로부터 선을 잇는 등의 연결로는 모호해지고, 헷갈릴 가능성이 높아진다고 생각했다. 그래서 이 프로젝트에서는 각 변수를 색상으로 정의하고, 직사각형의 주위에 테두리를 이용해 그것을 표시하기로 했다.
또한 처음에는 각 적용을 아래와 같이 한 뭉탱이를 기준으로 가로와 세로로 교차하여 나열할 생각이었다.
그러나 문제는 여러 가지 식이 한 가지 형태로 모자이크가 생성될 수 있다는 것이다.
또한, 한가지 식이 여러 가지 형태로 모자이크가 생성될 수도 있었다.
그래서 모든 적용을 가로, 세로를 번갈아 가며 그리기로 하였다.
그리고 난 이 시점에서 직사각형의 분할법을 찾아보다가, 내가 여태 자연스레 만든 것이 Binary Treemap이라는 사실을 알아버렸다.
부록 C: Lambda Diagram에 대한 추가적 분석
tromp의 Lambda Diagram[↗] 은 사실 이진 트리이다.
예시로 church numeral 3을 보자.
References & Related
- Excalidraw file with most of diagrams in this article
- This Mosaic is Prime[↗] by 3cycle(2swap)
- Lambda Diagrams[↗] by tromp
- A circuit-like notation for lambda calculus[↗] by csvoss
- Treemapping[↗]