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

요약

순수 $\lambda$-calculus에서 추가적인 재귀 구조나 비순수 캐시 없이도 순환 그래프와 메모이제이션을 구현하는 새로운 운영 의미론을 제안합니다. 테이블링 기법을 약한 헤드 축약에 적용하여 순수성을 유지하면서도 동적 계획법과 그래프 변환을 자동으로 수행할 수 있음을 보여줍니다.

핵심 포인트

• 추가 재귀 구조 없이 순수 $\lambda$-calculus 내에서 순환 그래프 표현 가능
• 테이블링 기법을 통한 자동적인 동적 계획법 및 하위 문제 공유 구현
• 비생산적 루프를 판별하여 유한한 시간 내에 $\bot$ 반환 가능
• $\lambda$-calculus를 그래프 계산을 위한 DSL로 확장