functional programming - Esquema: Procedimientos que devuelven otro procedimiento interno.
functional-programming lisp (3)
Esto es del libro SICP con el que estoy seguro que muchos de ustedes están familiarizados. Este es un ejemplo temprano en el libro, pero siento un concepto extremadamente importante que todavía no puedo entender. Aquí está:
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1 - CONS" m))))
dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))
Así que aquí entiendo que car
y cdr
se están definiendo dentro del alcance de los cons
, y entiendo que mapean algún argumento z
a 1 y 0 respectivamente (el argumento z
es algunos cons
). Pero digamos que llamo (cons 3 4)
... ¿cómo se evalúan los argumentos 3 y 4, cuando ingresamos de inmediato en este dispatch
procedimiento interno que toma un argumento m
que aún no hemos especificado? Y, quizás lo más importante, ¿cuál es el punto de devolver el dispatch
? Realmente no entiendo esa parte en absoluto. Cualquier ayuda es apreciada, gracias!
El código en la pregunta muestra cómo redefinir el procedimiento primitivo cons
que crea una cons-cell (un par de dos elementos: el automóvil y el CDR), utilizando solo closures y despacho de mensajes.
El procedimiento de dispatch
actúa como un selector para los argumentos pasados a los cons
: x
e y
. Si se recibe el mensaje 0
, entonces se devuelve el primer argumento de cons
(el car
de la celda). Del mismo modo, si se recibe 1
, se devuelve el segundo argumento de cons
(el cdr
de la celda). Ambos argumentos se almacenan dentro del cierre definido implícitamente para el procedimiento de dispatch
, un cierre que captura y
y se devuelve como el producto de invocar esta implementación procesal de cons
.
Las siguientes redefiniciones de car
y cdr
basan en esto: car
se implementa como un procedimiento que pasa de 0
a un cierre como se muestra en la definición anterior, y cdr
se implementa como un procedimiento que pasa de 1
al cierre, en cada caso finalmente valor original que se pasó como x
e y
respectivamente.
La parte realmente buena de este ejemplo es que muestra que la celda de contras, la unidad de datos más básica en un sistema Lisp, se puede definir como un procedimiento , por lo que la distinción entre datos y procedimiento se ve borrosa.
Este es el "cierre / objeto isomorfismo", básicamente.
La función externa (contras) es un constructor de clase. Devuelve un objeto, que es una función de un argumento, donde el argumento es equivalente al nombre de un método. En este caso, los métodos son captadores, por lo que se evalúan a los valores. Podrías haber almacenado más procedimientos en el objeto devuelto por el constructor.
En este caso, los números fueron elegidos como nombres de métodos y procedimientos azucarados definidos fuera del propio objeto. Podrías haber usado símbolos:
(define (cons x y)
(lambda (method)
(cond ((eq? method ''car) x)
((eq? method ''cdr) y)
(else (error "unknown method")))))
En cuyo caso, lo que tiene se parece más a OO:
# (define p (cons 1 2))
# (p ''car)
1
# (p ''cdr)
2
Este es uno de los ejemplos más raros (y posiblemente uno de los más maravillosos) de explotar funciones de primera clase en Scheme. Algo similar está también en el Little Schemer, que es donde lo vi por primera vez, y recuerdo que me rascé la cabeza durante días. Déjame ver si puedo explicarlo de una manera que tenga sentido, pero me disculpo si no está claro.
Supongo que entiende que los primitivos cons
, car
y cdr
ya están implementados en Scheme, pero solo para recordarle: cons
construye un par, car
selecciona el primer componente del par y lo devuelve, y cdr
selecciona el segundo componente y lo devuelve Aquí hay un ejemplo simple de usar estas funciones:
> (cons 1 2)
(1 . 2)
> (car (cons 1 2))
1
> (cdr (cons 1 2))
2
La versión de cons
, car
y cdr
que has pegado debe comportarse exactamente de la misma manera. Intentaré mostrarte cómo.
En primer lugar, car
y cdr
no están definidos dentro del alcance de los cons
. En su fragmento de código, los tres ( cons
, car
y cdr
) se definen en el nivel superior. La función de dispatch
es la única que se define dentro de los cons
.
La función cons
toma dos argumentos y devuelve una función de un argumento. Lo importante de esto es que esos dos argumentos son visibles para el dispatch
función interna, que es lo que se está devolviendo. Llegaré a eso en un momento.
Como dije en mi recordatorio, los cons
construyen un par. Esta versión de cons
debería hacer lo mismo, ¡pero en cambio está devolviendo una función! Está bien, no nos importa cómo se implementa o se distribuye el par en la memoria, siempre y cuando podamos obtener los componentes primero y segundo.
Así que con este nuevo par basado en funciones, necesitamos poder llamar a car
y pasar el par como argumento, y obtener el primer componente. En la definición de car
, este argumento se llama z
. Si tuviera que ejecutar la misma sesión REPL que tenía anteriormente con estas nuevas funciones cons
, car
y cdr
, el argumento z
en car
se vinculará al par basado en funciones, que es lo que devuelve, que es el dispatch
. Es confuso, pero solo piénsalo bien y lo verás.
Según la implementación del car
, parece ser que toma una función de un argumento y lo aplica al número 0
. Así que es aplicar el dispatch
a 0
, y como puede ver en la definición de dispatch
, eso es lo que queremos. El cond
interior compara m
con 0
y 1
y devuelve x
o y
. En este caso, devuelve x
, que es el primer argumento de los cons
, en otras palabras, ¡el primer componente del par! Así que el car
selecciona el primer componente, tal como lo hace la primitiva normal en Esquema.
Si sigue esta misma lógica para cdr
, verá que se comporta casi de la misma manera, pero devuelve el segundo argumento a cons
, y
, que es el segundo componente del par.
Hay un par de cosas que podrían ayudarlo a entender esto mejor. Una de ellas es volver a la descripción del modelo de sustitución de la evaluación en el Capítulo 1. Si sigue ese modelo de sustitución de forma cuidadosa y meticulosa para ver un ejemplo muy simple de uso de estas funciones, verá que funcionan.
Otra forma, que es menos tediosa, es intentar jugar con la función de dispatch
directamente en el REPL. A continuación, la variable p
se define para referirse a la función de dispatch
devuelta por cons
.
> (define p (cons 1 2))
#<function> ;; what the REPL prints here will be implementation specific
> (p 0)
1
> (p 1)
2