functional-programming lisp scheme sicp

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