Abstração Metalinguística

Lucas Vieira

Interpretador Metacircular

O Interpretador Metacircular é um programa composto de duas funções que se chamam mutuamente: eval e apply.

Este programa implementa um interpretador de um subset da linguagem Lisp, usando a própria linguagem Lisp.

Special Forms

Um interpretador pode ter várias formas especiais que ele poderia implementar. Nós nos conteremos às formas mais básicas, como listadas a seguir.

Números

\(3 \longmapsto 3\)

Átomos quotados

'foo \(\implies\) (quote foo) \(\longmapsto\) foo

Expressões lambda

(lambda (x) (+ x y)) \(\longmapsto\) (closure ((x) (+ x y)) #<env>)

Condicional

(cond (p1 e1) (p2 e2) ...)

Função Eval

A função eval realiza o trabalho de interpretação de um certo form, verificando se trata-se de um dos casos especiais citados. Se não, eval trata como a aplicação de um procedimento a vários operandos.

(define evaluator-eval
  (lambda (exp env)
    (cond ((number? exp) exp)
          ((symbol? exp) (lookup exp env))
          ((eq? (car exp) 'quote) (cadr exp))
          ((eq? (car exp) 'lambda)
           (list 'closure (cdr exp) env))
          ((eq? (car exp) 'cond)
           (evcond (cdr exp) env))
          (else (evaluator-apply (evaluator-eval (car exp) env)
				 (evlist (cdr exp) env))))))

Função Apply

A função apply é responsável pela aplicação de um procedimento sobre um conjunto de operandos. Caso a operação seja primitiva, o sistema se encarrega dela. Caso não seja, a função faz o trabalho de ligar os parâmetros formais aos operandos, criando um novo environment, e por fim interpretando o corpo da clausura neste novo environment.

(define evaluator-apply
  (lambda (proc args)
    (cond ((primitive? proc)
           (apply-primop proc args))
          ((eq? (car proc) 'closure)
           (evaluator-eval (cadadr proc)
			   (bind (caadr proc)
				 args
				 (caddr proc))))
          (else (evaluator-error "Not a procedure")))))

Funções auxiliares

Precisamos definir:

  • evcond;
  • evlist;
  • lookup;
  • bind.

Evlist e Evcond

(define evlist
  (lambda (l env)
    (cond ((eq? l '()) '())
          (else
           (cons (evaluator-eval (car l) env)
                 (evlist (cdr l) env))))))

(define evcond
  (lambda (clauses env)
    (cond ((eq? clauses '()) '())
          ((eq? (caar clauses) 'else)
           (evaluator-eval (cadar clauses) env))
          ((false? (evaluator-eval (caar clauses) env))
           (evcond (cdr clauses) env))
          (else
           (evaluator-eval (cadar clauses) env)))))

Bind

(define bind
  (lambda (vars vals env)
    (cons (pair-up vars vals)
          env)))

(define pair-up
  (lambda (vars vals)
    (cond
     ((eq? vars '())
      (cond ((eq? vals '()) '())
            (else (evaluator-error "Too many arguments"))))
     ((eq? vals '()) (evaluator-error "Too few arguments"))
     (else
      (cons (cons (car vars)
                  (car vals))
            (pair-up (cdr vars)
                     (cdr vals)))))))

Lookup

(define lookup
  (lambda (sym env)
    (cond ((eq? env '()) (evaluator-error "Unbound variable"))
          (else
           ((lambda (vcell)
              (cond ((eq? vcell '())
                     (lookup sym
                             (cdr env)))
                    (else (cdr vcell))))
            (assq sym (car env)))))))

(define assq
  (lambda (sym alist)
    (cond ((eq? alist '()) '())
          ((eq? sym (car alist))
           (car alist))
          (else
           (assq sym (cdr alist))))))

Outras funções auxiliares

Primitive? e Apply-primop

Estas funções dizem respeito a implementações internas que não necessariamente fazem parte do interpretador, e ficam a cargo do ambiente em que foram implementadas.

Aqui, recorremos a uma lista de operadores considerados primitivos, e à função eval do interpretador-hospedeiro.

(define *primitive-operators*
  '(+ - * / = > < >= <=))

(define primitive? procedure?)

(define apply-primop
  (lambda (proc args)
    (apply proc args)))

Error

Função de erro. Apenas mostrará o erro na tela.

(define evaluator-error
  (lambda (message)
    (display message)
    (display "\n")
    nil))

Environment inicial

Tomamos emprestados os operadores primitivos da linguagem e colocamo-os no environment zero.

(define <e0>
  (bind *primitive-operators*
	(eval (cons 'list *primitive-operators*))
	'()))