cálculo con reflejo

23

Estoy buscando un cálculo simple que admita el razonamiento sobre la reflexión , a saber, la introspección y la manipulación de programas en ejecución.

¿Existe una extensión de cálculo tipo que permita convertir los términos en una forma que pueda ser manipulada sintácticamente y luego evaluada? $\lambda$ $\lambda$

Me imagino que el cálculo tiene dos términos adicionales principales:

: toma y produce una representación de modificable a la manipulación sintáctica. $\mathtt{reflect}\ v$ $v$ $v$
: toma una representación sintáctica de un término y lo evalúa. $\mathtt{eval}\ v$

Para apoyar la reflexión, se requiere una representación sintáctica de los términos. Se vería algo así como:

se representaría como un término , donde es la versión reflejada de , $\lambda x.e$ $(\mathsf{LAM}\ R(e))$ $R(e)$ $e$
se representaría como término , y $e\ e'$ $(\mathsf{APP}\ R(e)\ R(e'))$
se representaría como . $x$ $(\mathsf{VAR}\ x)$

Con esta representación, la coincidencia de patrones podría usarse para manipular términos.

Pero nos encontramos con un problema. y deben codificarse como términos, al igual que la coincidencia de patrones. Tratar con esto parece ser sencillo, agregando , y , pero ¿tendré que agregar otros términos para respaldar la manipulación de estos? $\mathtt{reflect}$ $\mathtt{eval}$ $\mathsf{REFLECT}$ $\mathsf{EVAL}$ $\mathsf{MATCH}$

Hay opciones de diseño que deben hacerse. ¿Qué debe hacer la función aludida anteriormente con el cuerpo de y ? ¿Debería transformar el cuerpo o no? $R(-)$ $\mathtt{reflect}$ $\mathtt{eval}$ $R(-)$

Como no estoy tan interesado en estudiar la reflexión misma, el cálculo serviría como vehículo para otras investigaciones, no quiero reinventar la rueda.

¿Hay algún cálculo existente que coincida con lo que acabo de describir?

Por lo que puedo decir, los cálculos como MetaML, sugeridos en un comentario, son muy útiles, pero no incluyen la capacidad de emparejar patrones y deconstruir fragmentos de código que ya se han construido.

Una cosa que me gustaría poder hacer es lo siguiente:

$\mathtt{let}\ x=\lambda y.y\ \mathtt{in}\ \mathtt{reflect}\ x \to (\mathsf{LAM}\ (\mathsf{VAR}\ y)\ (\mathsf{VAR}\ y))$

Y luego realice una coincidencia de patrones en el resultado para construir una expresión completamente diferente.

Ciertamente, esta no es una extensión conservadora del cálculo y es probable que la metateoría sea fea, pero este es el punto para mi aplicación. Quiero separar las abstracciones . $\lambda$ $\lambda$

logic lambda-calculus semantics reflection Dave Clarke
fuente

MetaML es un lenguaje reflexivo escrito con el operador de horquillado que realiza su REFLECT y desmarca el EVAL. La escritura es básica, pero puede ver el fragmento heredado del modal S4 en trabajos como este documento que pueden ayudarlo.

ex0du5

@ ex0du5: Gracias, pero esto no llega lo suficientemente lejos, por lo que puedo decir. Claro, puedo construir código en varias fases, pero parece que no puedo separar los términos. (Leeré más detenidamente, para ver si me perdí algo.)

Dave Clarke

Esquema (sin la mutabilidad y otras complicaciones)?

Gilles 'SO- deja de ser malvado'

@Gilles: Scheme es un lenguaje de programación, no un cálculo. Además, no creo que pueda hacer lo que quiero.

Dave Clarke

@DaveClarke Un lenguaje de programación es un cálculo con muchas verrugas. Un núcleo de Scheme parece adecuado a primera vista, pero no he pensado lo suficiente en sus requisitos para estar seguro. ¿Qué crees que no funcionaría? (Acércate a chatear si quieres)

Gilles 'SO- deja de ser malvado'

15

Jean Louis Krivine introdujo un cálculo abstracto que extiende la "Máquina Krivine" de una manera muy trivial (tenga en cuenta que la máquina Krivine ya admite la instrucción call / cc de lisp):

Introduce un operador de "cita" en este artículo definido de la siguiente manera: si es un término , tenga en cuenta la imagen de mediante alguna biyección de términos lambda a números naturales. Nota el número iglesia que corresponde a . Krivine define el operador por la regla de evaluación: $\phi$ $\lambda$ $n_\phi$ $\phi$ $\pi: \Lambda \rightarrow \mathbb{N}$ $\overline{n}$ $n\in\mathbb{N}$ $\chi$

χ ϕ \to ϕ \bar{n_{ϕ}}

$\chi\ \phi \rightarrow \phi\ \overline{n_\phi}$ Creo que la magia de Kleene mostrará que esto es suficiente para hacer lo que desea: es decir, definir una cita y evaluar operadores, si

es computable.

π

$\pi$

Tenga en cuenta que Krivine es muy difícil de leer (¡por favor, no se enoje si lee esto, Jean-Louis!), Y algunos investigadores han realizado el acto caritativo de tratar de extraer el contenido técnico de una manera más legible. Puede intentar echar un vistazo a estas notas de Christophe Raffali.

¡Espero que esto ayude!

Se me ocurre que hay otra referencia que puede ser relevante para sus intereses: el Cálculo de Patrón Puro de Jay y Kesner formaliza una variante del cálculo que extiende la abstracción simple sobre una variable a una abstracción sobre un patrón que representa un cálculo de patrón sí mismo. Esto es fenomenalmente expresivo y, en particular, le permite a uno deconstruir una aplicación en sí: si no me equivoco, el término: $\lambda$

(λ (x y) . x) ((λ x . x x) (λ y . y))

$(\lambda (x\ y). x)((\lambda x.x\ x)\ (\lambda y.y))$

se reduce a . Una vez más, creo que esto es más que suficiente para implementar los operadores de cotización y evaluación . $\lambda x.x\ x$

cody
fuente

Me gustaría votar esta respuesta aparentemente razonable, pero no tengo idea de si incluso comienza a responder la pregunta.

Raphael

@Raphael lee los artículos y descubre :) En verdad, esta es solo una respuesta parcial: los artículos de hecho formalizan una característica importante del lisp que no se encuentra en el cálculo lambda: el operador COTIZACIÓN. Sin embargo, no hay un estudio metateórico extenso, simplemente lo presentan como un medio para expresar una especie de computación extraña no transparente para realizar axiomas complicados de la teoría de conjuntos.

cody

1

Si no recuerdo mal, en PPC, no puedes emparejar patrones en redexes, la razón que dieron es por el bien de la confluencia. Además, en PPC, la coincidencia de patrones es estricta en la coincidencia, por lo que

se normalizará inmediatamente a

, entonces el intento de emparejarlo con el patrón

fallará.

(λ x . x x) (λ y . y)

$(\lambda x . x\ x)\ (\lambda y . y)$

λ y . y

$\lambda y . y$

(x y)

$(x\ y)$

día

1

La única cita que conozco es la de Lisp. Pero, como recuerdo, solo cambia lo que se cita en un objeto sintáctico. La "función"

toma su argumento sin evaluar. Se supone que la función

toma el valor de su argumento (lo evalúa) y lo convierte de nuevo en alguna expresión sintáctica que evalúa (cómo ?) a ese valor. Entonces, si el formalismo de Krivine trata con el LISP

, no nos acercamos a lo que se sugiere en la pregunta.

q u o t e

$\mathtt{quote}$

r e f l e c t

$\mathtt{reflect}$

q u o t e

$\mathtt{quote}$

babou

8

Hacerlo es muy difícil, si no imposible, sin renunciar a la confluencia. Es decir, sospecho que tienes razón sobre una meta-teoría peluda. Por otro lado, es posible diseñar un cálculo combinador que pueda expresar todas las funciones computables de duración, y que tenga la capacidad total de inspeccionar sus términos: ver Jay y Give-Wilson .

Sin embargo, creo que tener esta habilidad hace algunas cosas malas a su teoría de la ecuación. En particular, tenderá a ser capaz de demostrar que dos valores son iguales si son iguales hasta las equivalencias alfa.

Todavía no he leído el documento de Krivine vinculado a Cody, pero debo tener en cuenta que en la lógica clásica esencialmente solo tienes dos cosas: verdadero y falso. Todo es equivalente a uno de esos. Es decir, tiende a tener una teoría de la ecuación colapsada de todos modos.

Philip JF
fuente

1

Tenga en cuenta que el cálculo de Krivine no es un cálculo de proposiciones, sino más bien de realizadores para estas, que tienen una teoría de la ecuación altamente no trivial.

cody

5

En la teoría de los lenguajes de programación, la característica de la que habla suele denominarse "cita". Por ejemplo, John Longley escribió sobre esto en algunos de sus trabajos, vea este documento .

Si solo busca consideraciones teóricas (en oposición a una implementación realmente útil), puede simplificar las cosas al indicar que quote(o reflectcomo lo llama) se mapea en el tipo de enterosnat al devolver un código Gödel de su argumento. Luego puede descomponer el número tal como lo haría con un árbol de sintaxis abstracta. Además, no es necesario evalporque eso se puede implementar en el idioma, es esencialmente un intérprete para el idioma.

Para un modelo concreto que tenga estas características, puede considerar el primer álgebra combinatoria de Kleene: interprete todo como un número (piense en ellos como códigos de Gödel) y defina la aplicación de Kleene para que signifique donde es el - La función parcial. Esto le dará un modelo de cálculo (con mapas parciales) en el cual es simplemente la función de identidad. No es necesario agregar más funciones al idioma. $n \star m$ $\varphi_n(m)$ $\varphi_n$ $n$ $\lambda$ quote

Si me dices lo que buscas, podría darte referencias más específicas.

Por cierto, aquí hay un problema abierto:

Enriquezca el cálculo (con o sin tipo) con el cual es una congruencia de tal manera que preserva la regla . $\lambda$ quote $\xi$

La regla $\xi$

\frac{e_{1} \equiv e_{2}}{λ x . e_{1} \equiv λ x . e_{2}}

$\frac{e_1 \equiv e_2}{\lambda x \,.\, e_1 \equiv \lambda x \,.\, e_2}$

λ

$\lambda$

λ

$\lambda$ quotequote

\frac{e_{1} \equiv e_{2}}{q u o t e e_{1} \equiv q u o t e e_{2}},

$\frac{e_1 \equiv e_2}{\mathtt{quote}\,e_1 \equiv \mathtt{quote}\,e_2},$ so for instance we see that it must be the case that

q u o t e ((λ x . x) y) \equiv q u o t e y .

$\mathtt{quote}\,((\lambda x \,.\,x) y) \equiv \mathtt{quote}\, y.$ So somehow this quote is supposed to calculate "very canonical" Gödel codes – but even assuming we have a typed

λ

$\lambda$ -calculus without recursion this seems to be hard to do.

Andrej Bauer
fuente

Of course there is a

β

$\beta$ -conversion there. I suppose I should have said that quote must be a congruence for all the rules of

λ

$\lambda$ -calculus, but in particular that the

ξ

$\xi$ -rule is difficult to preserve.

Andrej Bauer

The

ξ

$\xi$ -rule and the

β

$\beta$ -rule are independent of each other. Please do not confuse the equational theory with particular algorithmic incarnations of it.

Andrej Bauer

The following paper shows some problems with the (ξ) equation: The Lambda Calculus is Algebraic, Peter Selinger. Interesting, something new I wasn't aware! Cool.

Transfinite Numbers

4

Here is an alternative answer, instead of using my nominal approach which is still experimental there is some more established approach that goes back to the paper:

LEAP: A language with eval and polymorphism
Frank Pfenning and Peter Lee
https://www.cs.cmu.edu/~fp/papers/tapsoft89.pdf

The paper starts with:

This then led us to the question, first posed by Reynolds, of whether strongly typed languages admit metacircular interpreters. Conventional wisdom seemed to indicate that the answer was "No". Our answer is "Almost".

Please note that LEAP is much stronger than what the OP wants. First of all it is typed. And second it asks for metacircularity, which means for example that eval can execute its own definition. In Prolog you get metacircularity for solve/1:

solve(true).
solve((A,B)) :- solve(A), solve(B).
solve(H) :- clause(H,B), solve(B).

If you add the following clause to solve/1:

solve(clause(H,B)) :- clause(H,B).

And if you see to it that clause/2 also returns the clauses of solve/1. You can then call solve(solve(...)) and see how solve executes itself.

Questions of self representatio still spurr some research, see for example:

Self representation in Girards System U
Matt Brown, Jens Palsberg
http://compilers.cs.ucla.edu/popl15/popl15-full.pdf

Transfinite Numbers
fuente

3

The problem is identified in vincinity of proof assistants such as Coq and Isabelle/HOL. It goes under the acronym HOAS. There are some claims around λ-Prolog that through the new ∇ quantifier such things can be done. But I couldn't get a grip yet of this claim. I guess the main insight I got so far is that there is no definite approach, there are a couple of possible approaches.

My own take, not yet finished, is inspired by a recent paper by Paulson on proving Gödels incompletness. I would use the object-level binders in connection with some data structure that has the meta-level names. Basically a similar yet distinct data structure as the one from the OP, and with Church coding since I am interested in dependent types:

datatype Expr = var Name                 /* written as n */
              | app Expr Expr            /* written as s t */
              | abs Name Expr Expr       /* written as λn:s.t */

The meta level expressions can be distinguished from the object level expressions in that we use the variable names n, m, .. etc.. to denote names. Whereas we use the variable names x, y, .. etc.. on the object level. The interpretation of a meta term in the object logic would then work as follows. Lets write [t]σ for the interpretation of the nominal term t in the nominal context σ, which should give an object term. We would then have:

 [n]σ = lookup σ n
 [s t]σ = [s]σ [t]σ
 [λn:s.t]σ = λx:[s]σ.[t]σ,n:x

The above would define what the OP calls an EVAL function. Small difference to Paulson, σ is only a finite list and not a functional. In my opinion it would be only possible to introduce an EVAL function and not a REFLECT function. Since on the object level you might have some equality so that different lambda expressions are the same. What you have to do would be to use eval to reason possibly also about reflection if you feel the need.

You would need to go to extremes like Prolog where nothing is expanded, if you want to tear down the wall between nominal and non-nominal. But as the λ-Prolog system example shows, in the higher-order case there are luring additional problems which can for example only be overcome in logical way by introducing new means such as a ∇ quantifier!

Transfinite Numbers
fuente

cálculo con reflejo

Respuestas: