명제 변환기 모나드(Predicate Transformer Monads)의 분류학: 모나딕 프로그램 명세 기법

요약

본 논문은 모나딕 프로그램에 대한 검증 프레임워크 기반이 되는 '명제 변환기 모나드'의 분류학을 제시합니다. 특히 비결정성 및 비종료성을 다루기 위해 가장 강한 후건 조건(strongest postcondition) 모나드를 소개하고, 이를 기본 모나드로 일반화하여 화살표 변환기를 사용함을 설명합니다.

핵심 포인트

• 명제 변환기 모나드는 모나딕 프로그램 검증의 기반이 됩니다.
• 가장 강한 후건 조건 모나드가 비결정성/비종료성을 포괄합니다.
• 모나드 변환기의 한계를 극복하기 위해 화살표(arrows)와 화살표 변환기를 사용합니다.
• 명제 변환기 수준에서도 언더/오버 근사 트리플 간의 관계가 성립함을 증명했습니다.