In this thesis, we propose AFLOG - a functional logic language, employing narrowing. With narrowing, AFLOG supports equality partially, without losing the efficiency. With this partial equality relation, most data types such as stack and queue can be easily expressed and as equational programming is allowed in AFLOG, the clarity and the understandability of a program are much improved.
In implementing AFLOG with narrowing, two important mechanisms - the tree pattern matching and the backtracking mechanism in the reduction procedure are improved. In the tree pattern matching, the restriction called left-sequentiality is removed. In the backtracking mechanism of the reduction procedure, the structure sharing concept prevalently used in resolution procedure is employed and two different proof procedures - resolution and reduction are merged into the same mechanism.
본 논문에서는 narrowing을 이용하여 함수 논리 언어인 AFLOG를 설계및 구현하였다. AFLOG는 narrowing을 이용하여 equality를 부분적으로 포함하고 있는데, 이때 AFLOG 언어의 성능이 크게 떨어지지 않을뿐더러 대부분의 Abstract data type과 equational programming을 허용하고있다.
그리고 narrowing을 이용하여 AFLOG를 구현하는 과정에서, 중요한 부분인 트리 패턴 매칭 기법과 backtracking 기법을 개선하였다. 트리 패턴 매칭 기법에서는 left-sequentiality라는 제한을 제거하였으며, reduction 과정에서 발생하는 backtracking을 structure sharing 기법을 이용하여 처리함으로써 resolution과 reduction의 서로 다른 두가지 rule을 동일한 기법으로 머지 (merge)시켰다.
