순수 $\lambda$-Calculus에서의 순환 그래프와 메모이제이션 (Memoization)

요약

순수 $\lambda$-Calculus에서 추가적인 확장 없이 테이블링(tabling)을 적용하여 메모이제이션과 순환 그래프를 구현하는 새로운 연산 의미론을 제안합니다. 이 방식은 순수성을 유지하면서도 동적 계획법과 그래프 계산을 자동으로 수행할 수 있는 인터프리터를 구현합니다.

핵심 포인트

• 추가적인 재귀 구조 없이 순수 $\lambda$-Calculus 내에서 메모이제이션 구현
• 테이블링 기법을 통한 자동적인 동적 계획법 및 하위 문제 공유
• 순환적(cyclic) 그래프 생성을 통한 그래프 계산 DSL로서의 역할 수행
• 생산적이지 않은 루프를 판별하여 $\Omega$에 대해 $\bot$ 반환 가능