[PLT] 코리화의 전생현세(5): 동적 작용역

정보

본고는 시리즈의 다섯 번째 편입니다. 지난 편에서 우리는 컴파일러와 해석기, 추상적인 문법 트리와 S 표현식의 관계를 소개했고 아주 간단한 원 순환 해석기를 쓸 계획입니다.이 해석기를 쓰면 한편으로는 Racket 언어를 익힐 수 있고, 다른 한편으로는 실현의 측면에서 어떤 고급 개념을 이해할 수 있다.

개관

(쓸데없는 말은 그만하고 본론으로 들어가고 한 마디가 맞지 않으면 코드를 붙인다. 이 코드는 Racket으로 동적 작용역Lisp 사투리를 가진 해석기를 실현했다. 우리는 Racket의 패턴을 match에 일치시키지 않고 일반적인 교수법에 따라 S표현식을 기호, 자체값 표현식, 목록(함수 정의, 함수 호출) 3가지로 나눈다.
만약 기호라면, 우리는 '환경' 에서 기호의 값을 찾아야 한다.만약 자구치 표현식이라면, 우리는 직접 그것을 되돌려 줄 것이다.(이곳의 자구치 표현식은 숫자만 함수 정의가 있다면 하나의 데이터 구조로 매개 변수와 함수체를 저장합니다. 함수 호출이라면, 우리는 먼저 '확장' 호출할 때의 '환경' 을 실참하여 함수체가 이 환경에서 값을 구하도록 합니다.

#lang racket

; tool

(struct function 
  (param body))

(define (create-frame)
  (make-hash))

(define (extend-frame frame key value)
  (hash-set! frame key value))

(define (extend-env env frame)
  (cons frame env))

(define (get-symbol-value env key)
  (let lookup-env
    ((env env))
    (if (null? env)
        (error 'get-symbol-value "failed to find symbol")
        (let ((head-frame (car env)))
          (if (hash-has-key? head-frame key)
              (hash-ref head-frame key '())
              (lookup-env (cdr env)))))))

(define (handle-decision-tree tree exp)
  (if (null? tree)
      (error 'handle-decision-tree "failed to make decision")
      (let* ((head (car tree))
             (predicator (car head))
             (decision (cadr head)))
        (if (predicator exp)
            (if (not (list? decision))
                (decision exp)
                (handle-decision-tree decision exp))
            (handle-decision-tree (cdr tree) exp)))))

; env

(define *env* `(,(create-frame)))

; main

(define (eval-exp exp)
  (handle-decision-tree 
   `((,is-symbol? ,eval-symbol)
     (,is-self-eval-exp? ,eval-self-eval-exp)
     (,is-list?
      ((,is-lambda? ,eval-lambda)
       (,is-function-call-list? ,eval-function-call-list))))
   exp))

(define (is-symbol? exp)
  (display "is-symbol?
")
  (symbol? exp))

(define (eval-symbol exp)
  (display "eval-symbol
")
  (get-symbol-value *env* exp))

(define (is-self-eval-exp? exp)
  (display "is-self-eval-exp?
")
  (number? exp))

(define (eval-self-eval-exp exp)
  (display "eval-self-eval-exp
")
  exp)

(define (is-list? exp)
  (display "is-list?
")
  (list? exp))

(define (is-lambda? exp)
  (display "is-lambda?
")
  (eq? (car exp) 'lambda))

(define (eval-lambda exp)
  (display "eval-lambda
")
  (let ((param (caadr exp))
        (body (caddr exp)))
    (function param body)))

(define (is-function-call-list? exp)
  (display "is-function-call-list?
")
  #t)

(define (eval-function-call-list exp)
  (display "eval-function-call-list
")
  (let* ((fn (eval-exp (car exp)))
         (arg (eval-exp (cadr exp)))
         
         (body (function-body fn))
         (param (function-param fn))
         
         (frame (create-frame)))
    
    (extend-frame frame param arg)
    
    (let* ((env *env*)
           (value '()))
      (set! *env* (extend-env *env* frame))
      (set! value (eval-exp body))
      (set! *env* env)
      value)))

테스트

(display (eval-exp '1))

(display "

")
(display (eval-exp '(lambda (x) x)))

(display "

")
(display (eval-exp '((lambda (x) x) 
                     1)))

(display "

")
(display (eval-exp '((lambda (x)
                       ((lambda (y) x)
                        2))
                     1)))

(display "

")
(display (eval-exp '((lambda (x)
                       ((lambda (f)
                          ((lambda (x)
                             (f 3))
                           2))
                        (lambda (z) x)))
                     1)))

명사 해석

오늘 이 글에서 많은'귀에 익으면 자세히 알 수 있다'는 개념 명사를 언급했는데, 다음은 코드를 통해 그것들을 설명한다.

컨디션

(define *env* `(,(create-frame)))

환경은 프레임(frame)의 목록이며, 여기서'`'는 반인용(quasi-quotation)이며, 반인용은 하나의 템플릿으로 목록을 구축하기 편리하다.

`(,(create-frame))
<=> (list (create-frame))

(create-frame) 프레임을 만들고 목록에 넣으면 현재 요소가 하나밖에 없습니다.이 프레임의 목록은 환경입니다.
우리는 여기에 전역 변수 *env* 를 정의했는데, 어떤 함수도 호출하고 되돌려주면 *env* 에 영향을 미친다.

프레임

프레임은 키 값이 맞는 집합으로 기호와 값의 映射 관계를 나타내는데 우리는 귀속(binding)이라고 부른다.

(define (create-frame)
  (make-hash))

(define (extend-frame frame key value)
  (hash-set! frame key value))

구체적으로 실현하는 과정에서, 우리는 키 값 쌍을 저장하기 위해 해시표를 사용했다.프레임은 확장할 수 있습니다. extend-frame 함수는 새로운 키 값으로 기존 프레임을 확장합니다.

환경의 확장

(define (extend-env env frame)
  (cons frame env))

우리는 환경이 프레임의 목록이고 환경은 새로운 프레임으로 확장할 수 있다는 것을 알았다.이렇게 하면 환경에 여러 개의 프레임을 포함할 수 있고 새로운 프레임은 목록 헤더에 놓여 있다.

값을 구하다

하나의 기호에 대해 값을 구하는 것은 환경에서 이 기호에 대응하는 값을 찾는 것이다.이 기호와 값의 매핑 관계는 환경의 서로 다른 프레임에 나타날 수 있으며, 우리는 목록 헤더에서 첫 번째 매핑 관계를 시작할 수 있다.즉, 우리는 뒤에 추가된 프레임이 이전의 귀속 (binding) 관계를 덮어썼다고 생각한다.
구체적으로 다음과 같이 우리는 귀속적인 사용lookup-env을 통해 찾았다.

(define (get-symbol-value env key)
  (let lookup-env
    ((env env))
    (if (null? env)
        (error 'get-symbol-value "failed to find symbol")
        (let ((head-frame (car env)))
          (if (hash-has-key? head-frame key)
              (hash-ref head-frame key '())
              (lookup-env (cdr env)))))))

함수.

함수는 하나의 데이터 구조이고,

(struct function 
  (param body))

이 구조의 모든 실례는 하나의 구체적인 함수를 나타내는데 그 중에서 두 개의 필드를 포함하고 param는 매개 변수 목록을 나타내고 body는 함수체를 나타낸다.
우리가 함수 정의 표현식을 만났을 때, 우리는 이렇게 함수 (데이터 구조) 를 정의했다.

(define (eval-lambda exp)
  (display "eval-lambda
")
  (let ((param (caadr exp))
        (body (caddr exp)))
    (function param body)))

우리가 하나의 함수를 표현식으로 호출할 때 (1) 우리는 param와 body 필드를 추출하여 (2) 새로운 프레임을 만들었다. 그 중에서 값에 대한 매핑 관계를 저장했다. (3) 새로운 프레임으로 전역 환경을 확장했다. (4) 전역 환경에서 값을 구하는 함수체(5) 함수를 되돌린 후에 원래의 환경을 회복한다.
여기에 한 프레임의 추가와 삭제 작업이 있습니다. 함수 호출에 또 다른 함수 호출이 있으면 프레임이 삭제되기 전에 한 프레임을 추가합니다.실제로 이것은 창고에 들어가는 탄창 작업이다.
따라서 우리는 환경의 구체적인 실현 형식은 목록이라고 말하지만 데이터 구조상 하나의 창고를 구성한다.프레임은 이 경우에도 스택 프레임(stack frame)이 됩니다.

(define (eval-function-call-list exp)
  (display "eval-function-call-list
")
  (let* ((fn (eval-exp (car exp)))
         (arg (eval-exp (cadr exp)))
         
         (body (function-body fn))
         (param (function-param fn))
         
         (frame (create-frame)))
    
    (extend-frame frame param arg)
    
    (let* ((env *env*)
           (value '()))
      (set! *env* (extend-env *env* frame))
      (set! value (eval-exp body))
      (set! *env* env)
      value)))

값을 구하는 과정

이제 우리는 관련 개념에 대해 모두 해석을 하였으니 전체 값을 구하는 과정을 살펴보자.
우리가 (eval-exp '1)를 만났을 때 1는 숫자라는 것을 발견할 수 있다. 우리는 그것이 자구치 표현식이라고 단정하고 직접 그것을 되돌려준다. 그러므로 (eval-exp '1)의 값은 1이다.
우리가 (eval-exp '(lambda (x) x))를 만났을 때 이것은 함수 정의 표현식이라는 것을 알 수 있다. 우리는 함수에 대한 매개 변수 목록param => (x)과 함수체body => x를 가져와 그것들을 저장하는 구조인function을 만들었다.
우리가 (display (eval-exp '((lambda (x) x) 1)))를 만났을 때 우리는 이것이 함수 호출 표현식이라는 것을 발견했다. (실제로 다른 유형의 표현식이 아니면 함수 호출이라고 생각했을 때) 먼저 함수 대상을 얻은 다음에 함수 대상에 저장된 매개 변수 목록과 함수체를 얻어 확장 중인 환경에서 값을 구하는 함수체이다. 이때 환경x => 1이기 때문에 body => x => 1, 결과는 1이다.
같은 이치로 우리는 다른 테스트 용례를 분석할 수 있다.

동적 역할 영역

마지막 테스트 용례를 보도록 하겠습니다.

(eval-exp '((lambda (x)
              ((lambda (f)
                 ((lambda (x)
                    (f 3))
                  2))
               (lambda (z) x)))
            1))

먼저x => 1, 그리고f => (lambda (z) x), f가 호출되기 전에(f 3)의 값을 덮어썼고x, 이때 값을 구하는 함수체x => 2의 함수체를 얻었다f.
우리는 (f 3) => 2 함수체 중의 f => (lambda (z) x)가 x 호출된 환경에서 값을 구하는 것을 보았고, f는 서로 다른 위치에서 호출되었고, f는 다를 수 있다.

((lambda (x)
   (f 3))
 ?)

우리는 x 임의의 값을 줄 수 있다.
이렇게 하면 이롭기도 하고 해롭기도 하다. 실현이 간단하기 때문에 많은 오래된 언어가 동적 작용 영역이다. 그러나 위에서 말한 불확실성을 가져올 수 있다. 라이브러리의 디자이너는 모든 호출된 장면을 예측할 수 없기 때문에 문제가 발생하기 쉽다.
나중에 Scheme에서부터 사람들은 어법작용역(정태작용역)의 개념을 제기하여 x 중의 f => (lambda (z) x)가 시종x에 정의된 곳의 f과 같게 했다. 그러면 상술한 문제를 피할 수 있다. 우리가 x => 1의 값을 확정하고 싶을 때 x에 정의된 곳을 찾아서 코드를 보면 된다.(코드를 보고 텍스트를 분석하기 때문에'어법적'이라고 부른다.

다음 문장

본고에서 우리는 간단한 동적 작용역을 가진Lisp사투리를 실현했다. 다음은 이를 바탕으로 어법 작용역을 지원하도록 수정할 것이다. 우리는 어법 환경과 폐쇄의 개념을 도입할 것이니 지켜봐 주십시오.

참고 자료

The Racket Reference SICP: 4.1 메타 사이클 값 탐지기 An Introduction to Scheme and its Implementation