¿Cuál es la diferencia entre las estrategias de reducción y las estrategias de evaluación?

Del artículo de estrategia de evaluación en Wikipedia:

La noción de estrategia de reducción en el cálculo lambda es similar pero distinta.

Del artículo de estrategia de reducción en Wikipedia:

Es similar pero sutilmente diferente de la noción de estrategia de evaluación en informática.

¿Cuál es la sutil distinción entre estrategias de evaluación y estrategias de reducción que sugieren estos dos artículos? ¿Son solo dos conceptos similares de diferentes dominios?

Una estrategia de reducción es una función en Lambda que selecciona una redex (expresión reducible) de todas las redex posibles, dependiendo de lo que defina como redex.

Informalmente, una estrategia de evaluación es el orden en que un lenguaje evalúa sus argumentos. Una estrategia de paso de parámetros es lo que el lenguaje pasa a la función.

Para comprender la conexión entre estos, estudie el artículo de Plotkin sobre Llamada por nombre, llamada por valor y el cálculo lambda. Él explica claramente que desea elegir AXIOMAS distintos según el orden de evaluación que desee. Para el nombre Cb desea el antiguo axioma beta y para el valor cb desea un axioma del valor beta. Si haces eso, todos los metateoremas funcionan igual para ambos sabores. Más tarde demostré (con muchos colaboradores) que esta idea generaliza a todo lo que el mundo de PL ha estudiado.

Todo es técnico, no un poema que se pueda interpretar. Solo lee sobre esto.

- Matthias Felleisen

PD: Diré que creo que a las personas les será más fácil entender el artículo de Plotkin de la Parte I en nuestro libro Redex. Pero sí, es 3 veces más largo.

El artículo de Wikipedia "Estrategia de reducción" se extrae completamente de una edición particular realizada por una IP anónima al artículo "Estrategia de evaluación".

La opinión que representa no es consensuada, en el sentido de que sospecho que relativamente pocas personas del campo darán esta respuesta espontáneamente si les preguntas "¿distinguirías los nombres 'estrategia de reducción' y 'estrategia de evaluación'?". Solo lo escuché de Matthias Felleisen, que es inflexible sobre la importancia de esta distinción, y supongo que este punto de vista es compartido por otros que tuvieron la oportunidad de tomarse el tiempo para discutir estos puntos en detalle con él.

Mi comprensión actual de este punto (pero aún no he estudiado los detalles técnicos con toda su justicia) se trata de lo siguiente: se trata de si utiliza la semántica de "gran paso" versus "pequeño paso": esta distinción es estándar y se entiende por todos en el campo. La semántica de pasos pequeños define un paso atómico de reducción, y el resultado es en general aún reducible. La semántica de pasos grandes define un paso de reducción "grande" que va desde el programa inicial hasta su valor (o algún tipo de "respuesta" más rico si su idioma tiene otros efectos observables que devolver un valor, por ejemplo, entrada / salida o estado mutable).

Si define una relación de paso grande y de paso pequeño, puede verificar que la semántica de paso grande esté incluida en el cierre transitivo de la relación de paso pequeño, y que la relación de paso pequeño no se reduzca a otros términos atascados que los alcanzados por la relación de gran paso, o divergen si se define la reducción de gran paso. Esta es la relación de coherencia esperada entre ambos.

Creo que la redacción del artículo puede describirse más o menos , en términos modernos, como "la estrategia de evaluación es la relación de gran paso", "la estrategia de reducción es la relación de pequeño paso". Tenga en cuenta que la discusión realizada en el artículo "Estrategia de reducción" trata principalmente de artículos e investigaciones (y, lo que es más importante, puntos de vista elocuentes formados durante su lectura y escritura) entre 1973 y 1991, en un momento en que esas nociones nacieron, y probablemente no tan bien entendido como lo son hoy. (Kahn enfatizó la semántica de grandes pasos en 1987, y uno de los trabajos más importantes sobre la semántica de pequeños pasos es Wright y Felleisen, 1992)

Para el lado más obstinado de por qué Felleisen insiste en la importancia de esta diferencia (es decir, por qué puede haber más que solo "pequeño paso versus gran paso, meh"), mi comprensión actual es la siguiente: El punto que se está haciendo es que la semántica de pequeños pasos debe verse como un detalle de implementación. losLa semántica, según este argumento, es la función abstracta que asigna cada programa a su valor / respuesta, y el resto son dispositivos de implementación diseñados para aproximarlo (o razonar sobre la equivalencia inducida por esta semántica). Cuando decimos gran paso hoy, pensamos en un sistema de reglas de inferencia de naturaleza sintáctica, pero la "estrategia de reducción" que se está discutiendo anteriormente es, de hecho, su abstracción como un mapeo. (No creo que esto le dé más expresividad o fuerza a la noción en la práctica, pero la hace más abstracta).

Así que creo que lo que dicen esta página de Wikipedia y Matthias Felleisen es algo así como: "Defina su evaluación de la forma que desee, pero al final lo que importa es cómo se asignan sus programas a sus valores / respuestas / comportamientos, y esto es lo que debería llamarse 'semántica operativa' y sobre la que se debe razonar ".

Tenga en cuenta que esta posición va en cierta medida en contra de la distinción actual (que creo que es bastante consensuada, pero puede ser un sesgo cultural de mi parte) entre "semántica operativa" y "semántica denotacional", donde la primera se considera de naturaleza más sintáctica (definido como una relación de reducción), y este último se caracteriza típicamente por el hecho de que los programas computacionalmente equivalentes tienen exactamente la misma denotación (por lo que la denotación es ajena al mecanismo de cálculo real). Según esta última opinión, lo que se propone como una "estrategia de evaluación" o "semántica operativa" en los artículos y mi explicación anterior preferiría verse como una semántica denotacional, pero es cierto que es más concreta que la mayoría: valores / respuestas / los comportamientos están más cerca de los objetos sintácticos que muchos dominios semánticos.

Referencias: para comprender este punto de vista, probablemente sea útil volver a su fuente proclamada, que es el artículo de Gordon Plotkin en 1973. También puede tener buena suerte probando uno de los últimos artículos citados en Wikipedia; Encontré, por ejemplo, que "Parameter-Passing and the Lambda Calculus", de Crank y Felleisen, 1991, ofreció una visión muy clara de su posición al respecto en las primeras páginas.