De acuerdo con la página de Wikipedia sobre asignación única estática (SSA) , SSA es utilizada por proyectos grandes y conocidos como LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey y V8, mientras que la página de proyectos utiliza un estilo de paso continuo. (CPS) es un poco deficiente en comparación.
Tengo la noción de que CPS es preferido por los compiladores e intérpretes que implementan principalmente lenguajes funcionales, particularmente, Haskell y Scheme parecen tener fuertes inclinaciones hacia el estilo CPS debido a las restricciones en la mutación o la necesidad de un soporte de continuación de primera clase (supongo que Smalltalk posiblemente también necesitaría esto). La literatura principal que he encontrado que usa CPS parece ser la que está trabajando principalmente en Scheme o está relacionada con Scheme en algún aspecto.
¿Hay alguna razón en particular por la cual SSA se usa en la industria además del impulso de adopción? SSA y CPS tienen una relación cercana; eso significa que sería fácil establecerlo en términos de otro, pero tal vez la representación de la información sería menos compacta o menos eficiente para CPS.
fuente
Respuestas:
Me imagino que muchos implementadores de compiladores para lenguajes imperativos típicos simplemente no estaban tan familiarizados con CPS y las técnicas de compilación basadas en CPS. En la comunidad de programación funcional, tanto CPS como la compilación basada en CPS son técnicas muy conocidas, esta última del trabajo de Guy Steele. Sin embargo, incluso en la comunidad FP, la mayoría de los compiladores no utilizan técnicas basadas en CPS para la compilación a menos que el lenguaje mismo es compatible con los operadores de control como
call/cc. Se usa algo más parecido a la Forma Administrativa Normal (ANF) (a veces también conocida como Forma Normal Monádica que está íntimamente relacionada por razones que se aclararán) que tiene una relación aún más estrecha con la SSA que la CPS .Si no recuerdo mal, la forma administrativa normal toma su nombre del hecho de que la compilación basada en CPS puede conducir a beta-redexes en el código intermedio que no correspondían a nada en el código fuente. Estos se denominaron "redexes administrativos". Esto podría reducirse en tiempo de compilación, pero hubo una buena cantidad de investigación sobre cómo realizar una transformación CPS que generaría código sin los redexes administrativos en primer lugar. El objetivo entonces era producir resultados en una forma normal donde se redujeran todas las redexes "administrativas", y este fue el origen de la Forma Administrativa Normal. No tardó mucho en darse cuenta de que no había muchos beneficios al ver esto como un (n optimización de un) proceso de dos pasos: transformación CPS, reducción de los cambios administrativos. En particular, La forma administrativa normal se parece bastante al estilo monádico como se practica (a mano) más notablemente en Haskell. La transformación CPS puede entenderse como una conversión al estilo monádico en el que simplemente estás usando la mónada CPS (por lo que hay realmente múltiples formas de "convertir" al estilo monádico correspondiente a diferentes órdenes de evaluación). Sin embargo, en general, podría estar usando una mónada bastante diferente, por lo que la conversión al estilo monádico y, por lo tanto, a la forma administrativa normal no está realmente relacionada con CPS en particular.
Sin embargo, hubo algunos beneficios para CPS versus ANF. En particular, había ciertas optimizaciones que podía hacer en CPS con solo optimizaciones estándar, como la reducción beta, que requerían (aparentemente) reglas ad-hoc para ANF. Desde la perspectiva monádica, estas reglas corresponden a conversiones de conmutación. El resultado es que ahora hay una teoría que puede explicar qué reglas deben agregarse y por qué. Un artículo reciente ofrece una descripción (nueva y bastante clara) de esto (desde una perspectiva lógica) y su sección de trabajo relacionada sirve como una breve pero decente encuesta y referencias a la literatura sobre los temas que menciono.
El problema con CPS está vinculado a uno de sus principales beneficios. La transformación CPS le permite implementar operadores de control como
call/cc, pero esto significa que cada llamada de función no local en el código intermedio CPS debe tratarse como efectos de control potencialmente efectivos. Si su lenguaje incluye operadores de control, entonces esto es exactamente como debería ser (aunque incluso entonces la mayoría de las funciones probablemente no estén haciendo ninguna travesura de control). Si su lenguaje no incluye operadores de control, existen invariantes globales sobre el uso de continuaciones que no son evidentes localmente. Esto significa que hay optimizaciones que son poco sólidas para realizar en el código general de CPS que sería adecuado para este uso particularmente bien comportado de CPS. Una forma en que esto se manifiesta es enEl cambio en la precisión de los datos y el análisis del flujo de control . (La transformación de CPS ayuda de alguna manera, duele en otras, aunque las formas en que ayuda se deben principalmente a la duplicación en lugar del aspecto de CPS en sí). 1 Por supuesto, podría agregar reglas y ajustar análisis para compensar esto (es decir, explotar los invariantes globales), pero luego ha derrotado parcialmente uno de los principales beneficios de la compilación basada en CPS, que es que muchas (aparentemente) optimizaciones ad hoc de propósito especial se convierten en casos especiales de optimización de propósito general (particularmente reducción beta )En última instancia, a menos que su lenguaje tenga operadores de control, generalmente no hay muchas razones para usar un esquema de compilación basado en CPS. Una vez que compensa los problemas que mencioné anteriormente, generalmente ha eliminado los beneficios de la compilación basada en CPS y ha producido algo equivalente a no usar CPS. En ese momento, CPS solo está haciendo un código intermedio de aspecto complicado para no obtener muchos beneficios. Un argumento para la compilación basada en CPS de 2007 aborda algunos de estos problemas y presenta algunos otros beneficios utilizando una forma diferente de conversión de CPS. Las cosas que saca el papel están cubiertas en parte por el artículo (2017) que mencioné antes.
1 ¿La equivalencia entre SSA y CPS no lo hace más o menos imposible? No. Una de las primeras cosas que el documento que presenta esta equivalencia es que la equivalencia no funciona para un código CPS arbitrario , pero sí funciona para la salida de una transformación CPS (que definen) para un lenguaje sin operadores de control.
fuente
No soy un experto en compiladores, así que tome lo que digo con un grano de sal, espero que un verdadero experto en compiladores intervenga. Me dijeron que:
Ambos conspiran para hacer que el código compilado por CPS-transform sea relativamente lento.
fuente
call/cc, entonces, por ejemplo, las continuaciones se usarán con una disciplina de pila: no se necesitará recolector de basura, y las continuaciones corresponderán, más o menos, a los bordes del flujo de control gráfico para que no haya ningún salto adicional. No necesita implementar las continuaciones utilizando alguna implementación de propósito general de funciones de orden superior.