Horn 절 유도에 적용된 Big-step 및 small-step 유도

Big-step 및 small-step 유도(derivations)의 개념은 프로그래밍 언어의 운영 의미론 (operational semantics)에서 익숙한 것입니다. 이러한 개념들은 Horn 절 (Horn clause) 유도의 더 일반적인 환경에도 적용 가능합니다. 본 논문에서는 Horn 절에 대한 big-step 유도와 두 가지 버전의 small-step 유도 간의 동등성을 증명합니다. 이러한 유도 전략들을 위한 인터프리터 (interpreters)를 전문화함으로써, 어떠한 Horn 절 집합이라도 주어진 (big-step 또는 small-step) Horn 절 인터프리터의 동작을 상속받는, 증명 가능한 동등한 절 집합으로 변환될 수 있습니다. 이 변환의 특수한 사례로서, Horn 절로 직접 표현된 모든 프로그래밍 언어의 big-step 의미론은 동등한 small-step 의미론으로 변환될 수 있습니다. 다양한 프로그래밍 언어를 이용한 실험 결과가 보고됩니다.