LISP 모드 일치

Zenn에서 LISP의 보도가 매우 적기 때문에 초보자의 송풍 보도를 유수 투고로 삼고 싶습니다. LISP(Scheeme)의 집행 방법과 기본 문법은 이미 익혔습니다.
Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig (1992)
이 책의 챕터5에서는 원조 챗봇의'ELIZA'가 Common Lisp로 작성됐고, 설치된 해설에 등장하는 패턴 매칭 처리(5.2 Pattern Matching)가 첫 번째 기호 처리 프로그래밍 애플리케이션의 예(편견)인 만큼 Scheme로 다시 쓰면서 풀었다.

실행 예

GNU Guile3.0.4 및 Gauche0.9.6을 통해 확인. 처리 시스템의 고유한 디스플레이를 생략하는 등.

> (load "./pattern-matching.scm")
> (pat-match '(i need a ?X) '(i need a vacation))
((?X . vacation))
> (sublis (pat-match '(i need a ?X) '(i need a vacation))
          '(what would it mean to you if you got a ?X ?))
(what would it mean to you if you got a vacation ?)
> (pat-match '(i need a ?X) '(i really need a vacation))
#f
> (pat-match '(this is easy) '(this is easy))
((#t . #t))
> (pat-match '(?X is ?X) '((2 + 2) is 4))
#f
> (pat-match '(?X is ?X) '((2 + 2) is (2 + 2)))
((?X 2 + 2))
> (pat-match '(?P need . ?X) '(i need a long vacation))
((?X a long vacation) (?P . i))

함수를 구성하는 정의

변수 검사

여기에 머리에 있는 기호(기호)를 변수로 간주하기 때문에 먼저 기호가 변수인지 검사하는 함수를 정의합니다.

(define (variable? x)
  (and (symbol? x)
       (equal? (string-ref (symbol->string x) 0) #\?)))

?는 기호를 문자열로 변환하는 함수이고, symbol->string는 위치 정보string-ref를 통해 문자열의 한 문자를 가져오는 함수이며, 0는 문자#\?를 나타내는 함수이다.

상수 정의

?를 연상 목록의 초기 값으로 정의하고 이 연상 목록은 일치하는 데 실패했을 때의 반환 값의 상수fail를 성공적으로 일치하는 변수와 값의 집합(변수 제약)을 저장한다.

(define fail #f)
(define no-bindings '((#t . #t)))

또한 연상 목록은 다른 프로그래밍 언어가 말하는 사전형과 연상 배열에 해당하며 보통 점대(내부는 제어 단위 구조)를 통해 키와 값 집합을 목록으로 하는 것을 말한다.

변수 제약조건 유틸리티 함수

함수((#t . #t))는 연상 목록에서 변수 제약을 추출하고, 함수get-binding는 변수 제약에서 값을 추출하며, 함수binding-val는 변수 제약을 연상 목록에 추가한다.

(define (get-binding var bindings) (assq var bindings))

(define (binding-val binding) (cdr binding))

(define (extend-bindings var val bindings)
  (cons (cons var val)
        (if (equal? bindings no-bindings) '() bindings)))

변수 구속조건 확인

변수가 나타날 때의 처리: 제약 값이 없으면 연상 목록에 새로운 변수를 추가합니다. 제약 값이 있으면 현재 대응하는 값과 비교하고 같으면 연상 목록을 직접 되돌려주고 다르면'일치 실패'로 되돌려줍니다extend-bindings.

(define (match-variable var input bindings)
  (let ((binding (get-binding var bindings)))
    (cond ((not binding) (extend-bindings var input bindings))
          ((equal? input (binding-val binding)) bindings)
          (else fail))))

패턴 일치 처리 바디

첫 번째 파라미터로 도안을 표시하고 두 번째 파라미터를 일치 처리하는 대상을 지정하며 세 번째 파라미터에 변수가 결합된 집합을 저장하는 연상 목록을 지정한다.

(define (pat-match pattern input . r)
  (let ((bindings (if (null? r) no-bindings (car r))))
    (cond ((eq? bindings fail) fail)
          ((variable? pattern)
           (match-variable pattern input bindings))
          ((equal? pattern input) bindings)
          ((and (pair? pattern) (pair? input))
           (pat-match (cdr pattern) (cdr input)
                      (pat-match (car pattern) (car input)
                                 bindings)))
          (else fail))))

처리 주체로서 첫 번째 파라미터와 두 번째 파라미터는 첫 번째 호출할 때와 마찬가지로 목록의 상황fail이고 첫 번째 파라미터와 두 번째 파라미터가 각 목록의 같은 위치의 요소의 일치 처리라고 가정하는 두 가지 처리.첫 번째 파라미터와 두 번째 파라미터 중의 모든 시작 요소를 추출하여 자신을 호출하여 후자의 일치 처리를 하고 연상 목록에서 결과를 받는 변수의 속박을 받는 동시에 각 목록에 남은 패턴의 일치 처리를 하기 위해 자신을 호출한다.

프로그램 코드 한 세트

※ Common Lisp(and (pair? pattern) (pair? input))에 해당하는 것은 (왜) 발견되지 않았기 때문에 실행례에 적절한 자제품을 사용했습니다.
pattern-matching.scm

;;;;
;;;; Pattern Matching example
;;;; ported from Section 5.2 at https://github.com/norvig/paip-lisp
;;;;

(define (variable? x)
  (and (symbol? x)
       (equal? (string-ref (symbol->string x) 0) #\?)))

(define (sublis al L)
  (if (null? L) '()
      (cons (let ((r (assq (car L) al)))
              (if r (cdr r) (car L)))
            (sublis al (cdr L)))))

(define fail #f)
(define no-bindings '((#t . #t)))

(define (get-binding var bindings) (assq var bindings))

(define (binding-val binding) (cdr binding))

(define (extend-bindings var val bindings)
  (cons (cons var val)
        (if (equal? bindings no-bindings) '() bindings)))

(define (match-variable var input bindings)
  (let ((binding (get-binding var bindings)))
    (cond ((not binding) (extend-bindings var input bindings))
          ((equal? input (binding-val binding)) bindings)
          (else fail))))

(define (pat-match pattern input . r)
  (let ((bindings (if (null? r) no-bindings (car r))))
    (cond ((eq? bindings fail) fail)
          ((variable? pattern)
           (match-variable pattern input bindings))
          ((equal? pattern input) bindings)
          ((and (pair? pattern) (pair? input))
           (pat-match (cdr pattern) (cdr input)
                      (pat-match (car pattern) (car input)
                                 bindings)))
          (else fail))))

총결산

처리 변수 제약과 목록 요소의 순서 처리로 인해 이번 예는 실질적으로'언어 처리'의 일종이라고 할 수 있다. 책에서는 더욱 발전된 처리를 사용하여chatbot(위조 대화 프로그램)을 구성한다.

시험을 준비하다

문장의 보충

댓글이 없는 것은 고의(^^;)입니다.코드가 우선이기 때문에 예견성이 좋지만, 아래에서 위로 & 증량식으로 생각하면 어떨까...

책에서 Chapter11은 더욱 발전하여 Proog 해석기를 실현했다. 이전 글와 마찬가지로 다른 프로그래밍 언어도 Proloog 해석기를 실현할 수 없습니까? 매크로를 사용하는 곳이 엄격합니까?

역사를 갱신하다

2020-11-10: 초판 공개