Como definir un lenguaje con conjunto de primitivas extensible

Consideren el siguiente conjunto de primitivas, para operaciones sobre números y booleanos.

;;; primitives
(define *primitives*
  `((+       ,+)
    (-       ,-)
    (*       ,*)
    (/       ,/)
    (=       ,=)
    (<       ,<)
    (>       ,>)
    (zero?   ,zero?)
    (not     ,not)
    (and     ,(lambda args (apply (lambda (x y) (and x y)) args)))
    (or      ,(lambda args (apply (lambda (x y) (or x y)) args)))
    ))

La definición usa operadores especiales de quoting/unquoting, que solamente permiten construir listas en forma mas conveniente.

Para entender lo que crea esto, simplemente se puede ver el valor de *primitives*:

> *primitives*
(list
 (list '+ (lambda args ...))
 (list '- (lambda args ...))
 (list '* (lambda args ...))
 (list '/ (lambda args ...))
 (list '= (lambda args ...))
 (list '< (lambda args ...))
 (list '> (lambda args ...))
 (list 'zero? (lambda args ...))
 (list 'not (lambda args ...))
 (list 'and (lambda args ...))
 (list 'or (lambda args ...)))

O sea, *primitives* es lo que se llama una lista de asociacion (a-list), es decir una lista plana que contiene listas de dos elementos. Lo pueden ver como la representacion de un map. Aqui nos permite asociar a un simbolo (como '+) una lambda que aplica la funcion primitiva correspondiente (el + de Scheme).

La función básica para hacer lookup en este map es assq. assq retorna el par correspondiente.

> (assq '+ *primitives*)
(list '+ (lambda args ...))

Si queremos obtener la lambda asociada, tenemos que extraer el segundo elemento del par:

> (cadr (assq '+ *primitives*))
(lambda args ...)

Fijese que las lambdas estan definidas usando la sintaxis:

(lambda args ...)

en vez de:

(lambda (args) ...)

La diferencia es que en este último caso (el caso conocido), para llamar la función, hay que dar un solo parametro. En el primer caso, uno puede invocar la función con un numero variable de argumentos. Esos argumentos se entregan al cuerpo de la función en un lista. O sea:

> ((lambda args (length args)) 1 2 3)
3
> ((lambda (args) (length args)) '(1 2 3))
3

Luego, podemos aplicar esa lambda usando la funcion apply de Scheme. apply toma una lambda y una lista de argumentos y aplica la funcion con estos argumentos.

Ejemplos:

> (apply (cadr (assq '+ *primitives*)) '(4 5))
9
> (apply (cadr (assq '+ *primitives*)) '(4 5 6 7)) 
22
> (apply (cadr (assq '< *primitives*)) '(4 5))
true
> (apply (cadr (assq 'not *primitives*)) '(#t))
false
> (apply (cadr (assq 'and *primitives*)) '(#t #t))
true

(Detalle: nuestra implementación de and y or no es óptima porque siempre evaluará sus argumentos. Como solucionaría esto?)

Esto es muy conveniente, porque asi podemos facilmente extender nuestro lenguaje con otras primitivas, por ejemplo para output:

    ;; primitives for output
    (write   ,(lambda args (apply write args)))
    (printf  ,(lambda args (apply printf args)))
    (newline ,(lambda args (apply newline args)))

Ejemplo:

> (apply (cadr (assq 'write *primitives*)) '("hola"))
"hola"

Es mas, podemos introducir listas en el lenguaje introduciendo las pocas primitivas necesarias para manipular listas:

    
    ;; primitives for supporting lists
    (car     ,(lambda args (apply car  args)))
    (cdr     ,(lambda args (apply cdr  args)))
    (cons    ,(lambda args (apply cons args)))
    (list    ,(lambda args args))
    (null?   ,(lambda args (apply null? args)))

Ejemplo:

> (apply (cadr (assq 'cdr *primitives*)) '((1 2 3 4)))
(list 2 3 4)

Defina *primitives* en la zona de definiciones de DrScheme y prueba los distintos ejemplos.

Ahora, como se integra eso en la definición de su lenguaje, y su implementación?

Para que la definición de su lenguaje sea realmente extensible usando ese mecanismo, tiene que definir una expresion para aplicacion de primitiva:

<expr> ::= .... | <prim-app>
<prim-app> ::= (<id> <expr>*)

El parser tiene que encargarse de ver si el primer símbolo en una lista es una primitiva (usando assq, que retorna false si no encuentra la llave buscada). De ser asi, tiene que crear un nodo prim-app.

La evaluación de un prim-app la hace, obviamente, el interprete. El interprete se encarga de aplicar la primitiva usando apply, exactamente como hemos visto en los ejemplos anteriores. (Claramente, para que esto funcione, los valores del lenguaje tienen que ser representados en el interprete por los valores mismos de Scheme. Sino, tendrían que explicitamente desenvolver cada valor antes de pasarlo a un primitiva Scheme usando apply.)