sicp 패턴 일치 - 화합물?

Question

나는 SICP의 비디오 강연을보고있다. 현재 나는 4A Pattern Matching과 Rule Based Substitution을 사용 중이다.

지금까지 Matcher와 Instantiator가 쉽다는 것을 알았습니다. 그러나 나는 머리를 단순화 자로 가져갈 수 없다.

(define (simplifier the-rules) 
    (define (simplify-exp exp) 
    (try-rules (if (compound? exp) 
        (map simplify-exp exp) 
        exp))) 
    (define (try-rules exp) 
    (define (scan rules) 
     (if (null? rules) 
      exp 
      (let ((dict (match (pattern (car rules)) 
         exp 
         (empty-dictionary)))) 
      (if (eq? dict 'failed) 
       (scan (cdr rules)) 
       (simplify-exp (instantiate (skeleton (car rules)) dict)))))) 
    (scan the-rules)) 
    simplify-exp) 

나는 pair?의 관점에서 compound? 정의이 주제에 여기에 또 다른 질문을 보았다. 그런데 try-rules에 무슨 simplify-exp 먹이?

Answer 1

알아 냈어. 규칙은 약속대로 모든 노드에 적용될 것입니다. 투표를 삭제하면 질문을 삭제할 수 있습니다. 그러나 어떻게 작동하게 만들 었는지에 대한 설명을 추가 할 것입니다.

일부 코드가 변경되었습니다. 원래 코드는 다른 의미를 염두에두고 작성된 것 같습니다. 나는 내 자신의 결정을 내린 논평을 덧붙였다.

#lang racket 
;matcher 
(define (match pat exp dict) 
    (cond ((eq? dict 'failed) 'failed) 
     ;matched 
     ((and (null? pat) (null? exp)) dict) 
     ;so far matched, but no more 
     ((or (null? pat) (null? exp)) 'failed) 
     ((atom? pat) 
     (if (atom? exp) 
      (if (eq? pat exp) 
       dict 
       'failed) 
      'failed)) 
     ((pat-const? pat) 
     (if (constant? exp) 
      (extend-dict pat exp dict) 
      'failed)) 
     ((pat-variable? pat) 
     (if (variable? exp) 
      (extend-dict pat exp dict) 
      'failed)) 
     ((pat-exp? pat) 
      (extend-dict pat exp dict)) 
     ((atom? exp) 'failed) 
     (else 
     (match (cdr pat) 
       (cdr exp) 
       (match (car pat) (car exp) dict))))) 
(define (pat-const? pat) 
    (eq? (car pat) '?c)) 
(define (pat-variable? pat) 
    (eq? (car pat) '?v)) 
(define (pat-exp? pat) 
    (eq? (car pat) '?)) 
(define constant? number?) 
(define variable? symbol?) 
;instantiator 
(define (instantiate skeleton dict) 
    (define (loop s) 
    (cond ((atom? s) s) 
      ;we cant run past the nil line 
      ((null? s) '()) 
      ((skeleton-evaluation? s) (evaluate s dict)) 
      (else 
      (cons (loop (car s)) (loop (cdr s)))))) 
    (loop skeleton)) 

(define (skeleton-evaluation? s) 
    (eq? (car s) ':)) 
;made it simpler, no environment constant, sorry 
(define (evaluate s dict) 
    (let ((data (lookup (cadr s) dict))) 
    (if (null? data) 
     (display "error in rules. mismatch") 
     (cadr data)))) 
;simplifier 
(define (simplifier rules) 
    (define (simplify-exp exp) 
    (try-rules (if (list? exp) 
        (map simplify-exp exp) 
        exp))) 
    (define (try-rules exp) 
    (define (scan rule) 
     (if (null? rule) 
      exp 
      (let ((dict (match (pattern (car rule)) exp (empty-dict)))) 
       (if (eq? dict 'failed) 
        (scan (cdr rule)) 
        (simplify-exp (instantiate (skeleton (car rule)) dict)))))) 
    (scan rules)) 
    simplify-exp) 

(define pattern car) 
(define skeleton cadr) 

;dictionary 
(define (empty-dict) 
    '()) 
(define (extend-dict pat exp dict) 
    (let ((v (lookup (cadr pat) dict))) 
    (if (null? v) 
     (cons (list (cadr pat) exp) dict) 
     (if (eq? (cadr v) exp) 
      dict 
      'failed)))) 
(define (lookup s dict) 
    (cond ((null? dict) '()) 
     ((eq? (caar dict) s) (car dict)) 
     (else (lookup s (cdr dict))))) 


;extend racket 
(define (atom? a) 
    (and (not (null? a)) (not (pair? a)))) 

그리고? 그거 알아? 작동합니다 :)