학습 Pilog - 7: 절단 및 부정

Prolog Crash Course의 마지막 부분에 오신 것을 환영합니다. 오늘 우리는 컷과 부정에 대해 이야기할 것입니다.

이 게시물은 this tutorial을 기반으로 합니다.


"컷"이란 무엇입니까?



이전 게시물에서 우리는 Prolog의 역추적 동작에 대한 몇 가지 예를 보았습니다. 일부 예에서는 전체 검색 트리를 이동하는 데 많은 단계가 필요했습니다. 예를 들어 합법적인 솔루션이 하나만 있고 더 이상 검색할 필요가 없다는 것을 알고 있는 경우에는 비효율적일 수 있습니다.

잘라내기 연산자T는 효율성을 높이기 위해 역추적 동작을 제어하도록 설계되었습니다. 예를 들어 보겠습니다.


술어maxi/3를 정의합니다. 처음 두 인수는 숫자 범위를 정의하고 세 번째 인수는 이 두 인수의 최대값과 같습니다. 즉, 이 팩트는 T를 반환해야 합니다.

: (? (maxi 5 1 5))
-> T


반면 이들은 NIL:

: (? (maxi 2 3 2))
-> NIL
: (? (maxi 2 3 5))
-> NIL


물론 최대값을 쿼리할 수도 있습니다.

: (? (maxi 2 3 @Max))
 @Max=3
-> NIL



이제 정의합시다 maxi . 두 숫자 @X@Y 를 비교하려고 합니다. 이를 위해 PicoLisp 함수를 호출할 수 있습니다. 해당 조항은 세 부분으로 구성됩니다.
  • CAR의 ^ 기호,
  • CDDR의 PicoLisp 프로그램 본문,
  • 결과가 CADR에서 통합되는 변수입니다.

  • (be maxi (@X @Y @Y)
       (^ @ (<= @X @Y)) )  
    
    (be maxi (@X @Y @X)
       (^ @ (> @X @Y)) )
    


    우리는 그 결과에 대해 별로 신경 쓰지 않습니다. 이것이 변수@가 익명인 이유입니다.


    프롤로그는 첫 번째 if @X <= @Y 와 if @X>@Y 의 두 가지 경우를 테스트합니다. 문제는 어디에 있습니까?

    우리의 정의가 잘못된 것은 아니지만 비효율적입니다. 첫 번째 절이 이미 T 를 반환하는 경우 실제로 두 번째 조건을 테스트할 필요가 없습니다. 첫 번째와 두 번째 절은 상호 배타적입니다. 이 경우 절단 연산자가 유용합니다.


    다음 표기법을 사용하여 첫 번째 절이 T로 평가되면 Prolog에게 중지하도록 지시할 수 있습니다.

    (be maxi (@X @Y @Y)
       (^ @ (<= @X @Y))
       T)
    


    절단 기호T를 제거해도 프로그램 출력 자체에는 영향이 없기 때문에 이러한 유형의 절단을 녹색 절단이라고 합니다.

    반면에 레드 컷은 프로그램 변경을 유발하는 컷입니다. 이러한 절단은 위험할 수 있으며 잘 테스트해야 합니다.


    실패로서의 부정



    형식 논리에는 two kinds of negations이 있습니다. 강한 부정은 진술이 거짓으로 입증될 수 있는 경우에만 진술이 거짓으로 간주됨을 의미합니다. 반면에 약한 부정은 명제가 참임을 증명할 수 없으면 거짓으로 간주되는 것을 의미합니다. 후자는 실패로 부정이라고도합니다.

    (Prolog에서는 **negation as failure* 연산자로 구현되어 \+ )*로 쓸 수 있습니다.


    왜 필요한가요? "Mary는 곤충을 제외한 모든 동물을 좋아합니다"와 같은 "제외"문을 설명하기 위해 이를 구현할 수 있습니다. Pilog에서는 잘라내기 연산자와 내장 조건자를 사용하여 구현할 수 있습니다(fail).

    # Mary likes all animals except insects.
    (be likes (Mary @X)
       (insect @X)
       T
       (fail) )
    
    (be likes (Mary @X)
       (animal @X) )
    


    여기서 동물은:

    (be animal (@X) (insect @X))
    (be animal (@X) (pet @X))
    (be animal (@X) (cattle @X))
    
    (be insect (Spider))
    (be pet (Cat))
    (be pet (Dog))
    (be cattle (Cow))
    


    테스트해 봅시다:

    : (? (likes Mary Cat))
    -> T
    
    : (? (likes Mary Spider))
    -> NIL
    



    축하합니다. 이 게시물로 Pilog 소개를 마쳤습니다. 다음 게시물에서는 PicoLisp에 내장하고 데이터베이스 쿼리에 사용하는 방법을 살펴보겠습니다.


    출처


  • http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pageid=lpn-htmlch10
  • 좋은 웹페이지 즐겨찾기