Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

4장. 메타언어적 추상화

기본적인 Meta circular / Analyzing / Lazy / Ambiguous / Query를 단계적으로 제공해주면서 연습문제로 코드에 대한 이해 및 활용 그리고 수정할 기회를 줌.

우리는 당면한 문제에 특히 적합한 [용어]를 사용하여 문제를 다른 방식으로 설명하고 (따라서 사고할 수 있도록) 복잡한 문제를 처리하는 능력을 향상시킬 수 있습니다

"우리가 지금 사용하고 있는 언어(Scheme)를 사용해서, 또 다른 언어의 규칙과 의미를 정의하거나 해석하는 것" 프로그래밍 언어를 직접 정의하고 확장하는 추상화 기법이다.

  • MCE(Meta-Circular Evaluator) - https://en.wikipedia.org/wiki/Meta-circular_evaluator

    • Meta: "자기 자신을 대상으로 한"
    • Circular: "순환 구조의"
    • 자기 자신과 같은 언어로 작성되어, 자기 구조를 그대로 참조/사용하는 평가기.

  • eval

    • MetaCircular Evaluator
      • eval -> ( eval -> apply ) -> apply
      • 구문 분석을 위해 eval, apply 반복
    • Analyzing Evaluator
      • eval -> ( analyze ) -> call -> appy
      • analy를 통한 구문분석 후 apply로 평가
      • eval 횟수 감소 및 프로시져를 풀어씀으로써 계산 최적화
    • Lazy Evaluator
      • eval -> ( eval -> apply -> delay-it ) -> force-it
      • 지연 평가
      • 'thunk태그로 감싸고, 필요할때 평가
      • 불필요한 계산 건너뛸 수 있고, 메모이제이션을 이용한 최적화
    • Amb Evaluator
      • eval -> ( eval -> amb-apply )-> try-next-choice/fail
      • 비결정적(non-deterministic)
      • amb: Ambiguous choice
      • (amb)활용
      • 오버헤드가 있으나, 선언적으로 문제를 정의함으로써 풀 수 있음.
      • 제약조건 순서에 따라 연산 속도가 달라 질 수 있음.

    • Query system

meval / analyzingeval / leval 비교

#| 4_27 (define count 0) (define (id x) (set! count (+ count 1)) x) (define w (id (id 10)))

;; meval 매번 funcall eval때마다, expr로 저장된 프로시져의 expr을 순회하면서 special form / operator / arguments들에 대해 매번 eval을 실행.

#0=((w id count...) 10 (procedure (x) ((set! count (+ count 1)) x) #0#) 2 ... )

;; analyzingeval 매번 funcall eval때마다, lambda로 저장된 프로시져에 env가 들어오며 이미 env를 어디에 적용될지 맵핑된 lambda함수들이 한번에 apply 실행. #0=((w id count...) 10 (procedure (x) #procedure:... #0#) 2 ... )

#procedure:...은 symbol리스트가 아닌 함수가 컴파일된것. (lambda (env) (make-procedure '(x) (lambda (env) ((lambda (env) (set-variable-value! 'count (execute-application (lookup-variable-value '+ env) (list (lookup-variable-value 'count env) 1)) env) 'ok) env) ((lambda (env) (lookup-variable-value 'x env)) env)) env))

;; leval ;; - force-it-non-memoizing & force-it-memoizing #0=(((w id count ...) (thunk (id 10) #0#) (procedure (x) ((set! count (+ count 1)) x) #0#) 1 ... )

여기서 w를 호출하면

;; - force-it-non-memoizing #0=(((w id count ...) (thunk (id 10) #0#) (procedure (x) ((set! count (+ count 1)) x) #0#) 2 ... )

;; - force-it-memoizing #0=(((w id count ...) (evaluated-thunk 10) (procedure (x) ((set! count (+ count 1)) x) #0#) 2 ... )

여기서 한번 더 w를 호출하면

;; - force-it-non-memoizing #0=(((w id count ...) (thunk (id 10) #0#) (procedure (x) ((set! count (+ count 1)) x) #0#) 3 ... )

;; - force-it-memoizing #0=(((w id count ...) (evaluated-thunk 10) (procedure (x) ((set! count (+ count 1)) x) #0#) 2 ... ) |#

- delay
  - delay-it
    - ('thunk exp env)
- deref
  - force-it
    - ('thunk exp env) => ('evaluated-thunk result)

TODO

4.1 lisp로 lisp 인터프리터 만들기.

저자가 작성한 eval / apply / env / frame 설명 연습문제로 let / let* / letrec 확장을 볼 수 있다. halt problem

4.2 normal-order evaluation

  • 3장에서 상태를 덮어쓰기 때문에 생겨나는 여러 복잡한 문제를 피하기 위해 스트림 데이터(lazy sequence)를 사용.
  • Scheme(혹은 Racket)은 스트림 프로그램을 짜기에 번거로운 점이 있다 4.3 nondeterministic computing 4.4 logic-programming - prolog같은 논리형 프로그래밍

(list? '()) ;;=> #t (pair? '()) ;;=> #f

인터프리터와 컴파일러

  • 인터프리터: 표현식을 직접 실행
  • 컴파일러: 고수준 표현식을 더 낮은 수준(예: 가상 머신 코드, 기계어)으로 변환하고 그것을 실행
    • 단순한 인터프리터 대비 컴파일은 중복 평가 제거, 공통 하위 표현식 최적화 등이 가능.

Eval & Apply

4.1은 Eval과 Apply로 시작하게 된다.

코드가 길고 car/cdr/cadr/caddr ... 난리도 아니다. 다음을 정의하고 시작하자 (define first car) (define rest cdr) (define second cadr) (define third caddr)


;; ============================================================================
;; EVAL
;; ============================================================================

(define (eval exp env)
  (cond ((self-evaluating? exp)
         exp)
        ((variable? exp)
         (lookup-variable-value exp env))
        ((quoted? exp)
         (text-of-quotation exp))
        ((assignment? exp)
         (eval-assignment exp env))
        ((definition? exp)
         (eval-definition exp env))
        ((if? exp)
         (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp) (lambda-body exp) env))
        ((begin? exp)
         (eval-sequence (begin-actions exp) env))
        ((cond? exp)
         (eval (cond->if exp) env) )
        ((application? exp)
         (apply (eval (operator exp) env) (list-of-values (operands exp) env)))
        (else
         (error "Unknown expresslon type -- EVAL" exp))))

(define (self-evaluating? exp) nil)
(define (variable? exp) nil)
(define (quoted? exp) nil)
(define (assignment? exp) nil)
(define (definition? exp) nil)
(define (if? exp) nil)
(define (lambda? exp) nil)
(define (begin? exp) nil)
(define (cond? exp) nil)
(define (application? exp) nil)

(define (lookup-variable-value exp env)nil)
(define (text-of-quotation exp) nil)

(define (eval-assignment exp env) nil)
(define (eval-definition exp env) nil)
(define (eval-if exp env) nil)
(define (eval-sequence exps env) nil)

(define (make-procedure exp1 exp2 env) nil)
(define (lambda-parameters exp) nil)
(define (lambda-body exp) nil)
(define (begin-actions exp) nil)
(define (cond->if exp) nil)
(define (operator exp) nil)
(define (list-of-values exps env) nil)
(define (operands exp) nil)

;; ============================================================================
;; APPLY
;; ============================================================================

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
          (procedure-body procedure)
          (extend-environment (procedure-parameters procedure) arguments (procedure-environment procedure))))
        (else
         (error "Unknown procedure type -- APPLY" procedure))))

(define (primitive-procedure? procedure) nil)
(define (compound-procedure? procedure) nil)
(define (apply-primitive-procedure procedure arguments) nil)
(define (procedure-body procedure) nil)
(define (extend-environment parameters arguments env) nil)
(define (procedure-parameters procedure) nil)
(define (procedure-environment procedure) nil)

4.1

(eval environment expression) (apply function function-arguments)

  1. 언어를 처리하는 기법

4.1 메타써큘러 실행기

4.1.1 언어 실행기의 알짜배기 eval / apply

Exercise 4.6 ** 문제자체는 쉽지만 Let을 다룬다.

4.1.2 식을 나타내는 방법 eval

(define (self-evaluating? exp) (or (number? exp) (string? exp))) (define (variable? exp) (symbol? exp)) (define (quoted? exp) (tagged-list? exp 'quote)) (define (assignment? exp) (tagged-list? exp 'set!)) (define (definition? exp) (tagged-list? exp 'define)) (define (if? exp) (tagged-list? exp 'if)) (define (lambda? exp) (tagged-list? exp 'lambda)) (define (begin? exp) (tagged-list? exp 'begin)) (define (cond? exp) (tagged-list? exp 'cond)) (define (application? exp) (pair? exp))

4.1.3 언어 실행기에서 쓰는 데이터 구조 평가기evaluator를 구현할 때는 프로그램의 외부 문법(external syntax)만 정의하는 것이 아니라 프로그램 실행 과정에서 평가기가 내부적으로 다루는 데이터 구조도 정의해야 함

참과 거짓 (define (true? x) (eq? x true)) (define (false? x) (not (true? x)))

내장 함수 ( primitive-procedure // aka built-in-function )

(apply-primitive-procedure (primitive-procedure?

환경(env) (lookup-variable-value (extend-environment (define-variable! (set-variable-value!

eval을 테스트하기 껄끄럽기에 연습문제 4.01 ~ 4.14는 4.1.4 Running the Evaluator as a Program 까지 읽고 풀기.

  • 개념
    • frame
      • ((symbol-a symbol-b ...) value-a (primitive func-b) ...)
      • 변수/함수이름 리스트 + 변수/함수들...
      • 연습문제 4.11에서
        • '((변수/함수이름 변수/함수) ...) 식으로 바꿈
        • '((symbol-a value-a) (symbol-b (primitive func-b)) ...)
    • environment
      • (frame-a frame-b)
      • 프레임 리스트
      • (cons new-frame env)
      • (cons 'b '(a)) => (b a) 새로운 frame이 앞에오는 구조

4.1.4 언어 실행기를 보통 프로그램처럼 돌려보기

set-car! set-cdr!

(define (setup-environment) (let ((initial-env (extend-environment (primitive-procedure-names) (primitive-procedure-objects) the-empty-environment))) (define-variable! 'true true initial-env) (define-variable! 'false false initial-env) initial-env))

연습 4.13 ** 문제 make-unbound! 함수를 만들어 env에서 지울 수 있도록 만들자. first-frame에서만 지우면 되는가?

4.1.5 Data as Programs 프로그램도 데이터처럼

6 => factorial => 720 The factorial program, viewed as an abstract machine. 6 => evaluator => 720 evaluator as a very special machine

evaluator is seen to be a universal machine.

  • A Universal Turing machine, often just called a universal machine, is an abstract computational device that can simulate other computational devices.
  • UTM https://en.wikipedia.org/wiki/Universal_Turing_machine

단순하고 자명한 것에서 복잡한것이 나오게 된다.

GEB( Gödel, Escher, Bach: an Eternal Golden Braid ) 괴델, 에셔, 바흐: 영원한 황금 노끈 https://de.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach

recursion theory ( Computability theory ) "무엇이 계산 가능하고, 무엇이 절대 계산 불가능한가?" https://en.wikipedia.org/wiki/Computability_theory

연습 4.15 ** Halting Problem

4.1.6 안쪽 정의(internal definition)

c언어의 전방선언과 비슷한 느낌.

선언과 할당을 동시에 할때 생기는 문제 let을 써서(frame 을 하나 더 써서) 풀어보고 선언 먼저 '*unassigned*로 공간을 만들어주고 그 다음 할당.

연습문제 4.17 - frame을 쓰지 않고 풀어보고

연습문제 4.19 ** Sequential Scope Simultaneous Scope lazy evaluation 연습문제 4.21 ** Z combinator - lambda calculus

4.1.7 문법 분석과 실행 과정을 떼어놓기

  • eval시 analyze과정을 넣어 최적화

4.2 Scheme 바꿔보기 - 제때 계산법

4.2.1 식의 값을 구하는 차례 - 정의대로 계산법과 인자 먼저 계산법

lazy evaluation <=> eager evaluation

(define (try a b) (if (= a 0) 1 b))

(try 0 (/ 1 0)) ;=> 1 // lazy evaluation ;!> /: division by zero // eager evaluation

4.2.2 제때 계산법을 따르는 실행기

  • frame
    • ((symbol-a symbol-b ...) value-a (primitive func-b) ...)

(define (actual-value exp env) (force-it (eval exp env)))

(define (force-it obj) thunk면 계산해서 캐쉬에 넣기 ) (define (delay-it exp env) (list 'thunk exp env))

(thunk exp env) (evaluated-thunk exp env)

연습문제 4.30 ** (define (f a (b lazy) c (d lazy-memo)) ...) 구현

4.2.3 제때셈 리스트와 스트림

연습문제 4_34 ** lazy pair / lazy list의 출력방식 수정

4.3 Scheme 바꿔보기 - 비결정적 계산

Nondeterministic Computing

amb ( Ambiguous )

(define (an-integer-starting-from n) (amb n (an-integer-starting-from (+ n 1))))

(define (an-element-of items) (require (not (null? items))) (amb (car items) (an-element-of (cdr items))))

(define (require p) (if (not p) (amb)))

  • Teach Yourself Scheme in Fixnum Days - 14 Nondeterminism

    • McCarthy’s nondeterministic operator amb

  • A BASIS FOR A MATHEMATICAL THEORY OF COMPUTATION∗ by JOHN McCARTHY

    • https://www-formal.stanford.edu/jmc/basis1/basis1.html

  • 3.5.2에서 나온 스트림 프로시져 integers-starting-from 와는 다름

    • n으로 시작하는 정수 리스트

  • amb의 an-integer-starting-from

    • 정수 하나

4.3.1 amb와 찾기 4.36 **

4.3.2 비결정적 프로그램 짜기 multiple-dwelling 4.39 ** 4.43 ** Lorna의 아빠 찾기 4.44 ** 8-queen

4.3.3 amb 실행기 구현

4.1.7절에서 만든 문법을 분석하는 해석기를 고치자 ( analyzingmceval => ambeval)

4.4 논리로 프로그램 짜기

https://www.slideshare.net/slideshow/sicp-44-logic-programming/1552206

3.5 스트림도 보고 오는게 좋음

4.4.1 연역식 정보 찾기 - 쿼리짜는 연습 rule

4.4.2 쿼리 시스템의 동작 방식

  • 데이터베이스 fact와 rule을 매치시키기 위한 방법으로 amb활용이나 스트림 활용 할 수 있음

  • 여기선 스트림 활용.

  • query system: pattern matching + unification

    • pattern matching
      • 단순비교, 쿼리가 데이터베이스의 fact와 일치하는지 확인.
      • 단방향 매칭
    • unification
      • 쿼리와 rule, rule과 fact, 또는 rule과 rule 간의 일치를 처리하는 데 사용.
      • 양방향 매칭
(simple-query query-pattern frame-stream)
  |
  v
[frame-stream] ==> stream-flatmap
                        |
                        v
                    (per frame)
                  stream-append-delayed
                  |                     \
                  v                      v
             find-assertions         delay (apply-rules)
                  |                      |
                  v                      v
             fetch-assertions        fetch-rules
                  |                      |
               (per datum)             (per rule)
             check-an-assertion       apply-a-rule
                  |                      |
                  v                      v
             pattern-match           unify-match
                  |                      |
                  v                      v
             extend-if-consistent    extend-if-possible
                  |                      |
                  v                      v
             [frame-stream]          [frame-stream]
                  |                      /
                  v                     v
                  stream-append-delayed
                        |
                        v
                  stream-flatmap    ===========>   [result-frame-stream]

;; (pattern-match {패턴} {데이터} {프레임(사전역활)})
;;=> {새로운 프레임}

(pattern-match '((? x) (? y) (? x)) '(a b a) '())
;;=> (((? y) . b)
;;    ((? x) . a))

(pattern-match '((? x) (? y) (? x)) '(a b a) '(((? y) . a)))
;;=> failed

(pattern-match '((? x) (? y) (? x)) '(a b a) '(((? y) . b)))
;;=> (((? x) . a)
;;    ((? y) . b))

;; (unify-match {패턴1} {패턴2} {프레임(사전역활)})
;;=> {새로운 프레임}

(unify-match '((? x) (? x)) '((a (? y) c) (a b (? z))) '())
;;=> (((? z) . c)
;;    ((? y) . b)
;;    ((? x) a (? y) c))

(unify-match '((? x) (? x)) '(((? y) a (? w)) (b (? v) (? z))) '())
;;=> (((? w) ? z)
;;    ((? v) . a)
;;    ((? y) . b)
;;    ((? x) (? y) a (? w)))
  • unifier
    • 상수변수패턴1: (?x a ?y)
    • 상수변수패턴2: (?y ?z a)
    • frame()
      • => ?x => a ?y => a? z => a

4.4.3 논리 프로그래밍은 수학 논리를 따르는가?

  • 4.4.3에 나오지만 4.4.4를 보고 푸는게 좋음
    • 연습문제 4.67 **
    • 연습문제 4.68 **

연습문제 4.69 **

4.4.4 쿼리 시스템 만들기

4.4.4.1 드라이버 루프와 쿼리 값 찍어내기(instantiation)

(define (instantiate exp frame unbound-var-handler)
  (define (copy exp)
    (cond ((var? exp)
           (let ((binding (binding-in-frame exp frame)))
             (if binding
                 (copy (binding-value binding))
                 (unbound-var-handler exp frame))))
          ((pair? exp)
           (cons (copy (car exp)) (copy (cdr exp))))
          (else exp)))
  (copy exp))

;; (query-syntax-process '(hello world ?x ?y))
;;=> (hello world (? x) (? y))

;; (expand-question-mark '?x)
;;=> (? x)

4.4.4.2 실행기(evaluator)

(define (qeval query frame-stream)
  (let ((qproc (get (type query) 'qeval)))
    (if qproc
        (qproc (contents query) frame-stream)
        (simple-query query frame-stream)))):


(define (simple-query query-pattern frame-stream)
  (stream-flatmap (lambda (frame)
                    (stream-append-delayed (find-assertions query-pattern frame)
                                           (delay (apply-rules query-pattern frame))))
                  frame-stream))

4.4.4.3 패턴 매칭으로 참말 찾아내기 4.4.4.4 규칙과 동일화 4.4.4.5 데이터베이스의 관리 4.4.4.6 스트림 연산 4.4.4.7 쿼리의 문법을 처리하는 프로시저 4.4.4.8 일람표와 정의

4.01 cons left right 4.02 application? 위치 4.03 data-directed style 4.04 and? or? 추가