opciones - programa en haskell

Prueba de las proyecciones de Futamura en Haskell.

Question

Leí la excelente publicación del blog de Dan Piponi sobre Las tres proyecciones del doctor Futamura . Hacia el final del artículo, tiene un apéndice con una prueba de las proyecciones de Futamura en Haskell. Sin embargo, me parece que su artículo carece de información sobre los idiomas involucrados. ¿Cuáles deben ser los idiomas de origen, destino y objeto del especialista para que funcionen las proyecciones de Futamura? Por ejemplo, ¿funcionarían las proyecciones de Futamura si escribiera un especializador de Haskell a LLVM en Haskell? Sería útil que escribieras un programa de Haskell para demostrar esto, como lo hizo Dan Piponi en su artículo.

Answer 1

Sí, las proyecciones de Futamura funcionarán solo si los lenguajes fuente y objeto del especialista son los mismos. Esto se debe a que el especialista solo se puede aplicar a sí mismo si está escrito en el mismo idioma que puede leer. Sin embargo, el idioma de destino del especialista es independiente de los otros dos. Esto tiene importantes consecuencias que discutiré más adelante en esta respuesta.

Para probar mi hipótesis, presentaré una nueva notación para describir programas basados ​​en diagramas de lápidas . Un diagrama de lápida (o diagrama T) es una representación pictórica de compiladores y otros metaprograms relacionados. Se utilizan para ilustrar y razonar sobre la transformación de un programa de un idioma de origen (a la izquierda de T) a un idioma de destino (a la derecha de T) como se implementa en un lenguaje de objetos (parte inferior de T). Ampliemos la idea de los diagramas en T para que funcionen con todos los programas:

α → β : ℒ -- A program is a function from α to β as implemented in language ℒ.

En el caso de los metaprogramas, α y β son en sí mismos programas:

(α → β : 𝒮) × α → β : 𝒪 -- An interpreter for language 𝒮 as implemented in 𝒪.
(α → β : 𝒮) → (α → β : 𝒯) : 𝒯 -- A compiler from 𝒮 to 𝒯 as implemented in 𝒯.
(ι × α → β : 𝒮) × ι → (α → β : 𝒯) : 𝒮 -- A self-hosting specializer from 𝒮 to 𝒯.
(ι × α → β : 𝒮) → (ι → (α → β : 𝒯) : 𝒯) : 𝒯 -- A compiler compiler from 𝒮 to 𝒯.

Esta notación se puede convertir directamente en definiciones de tipo en Haskell. Armados con esto, ahora podemos escribir una prueba de las proyecciones de Futamura en Haskell con respecto a los idiomas:

{-# LANGUAGE RankNTypes #-}

module Futamura where

newtype Program a b language = Program { runProgram :: a -> b }

type Interpreter source object = forall a b.       Program (Program a b source, a) b object
type Compiler    source target = forall a b.       Program (Program a b source) (Program a b target) target
type Specializer source target = forall input a b. Program (Program (input, a) b source, input) (Program a b target) source
type Partializer source target = forall input a b. Program (Program (input, a) b source) (Program input (Program a b target) target) target

projection1 :: Specializer object target -> Interpreter source object -> Program a b source -> Program a b target
projection1 specializer interpreter program = runProgram specializer (interpreter, program)

projection2 :: Specializer object target -> Interpreter source object -> Compiler source target
projection2 specializer interpreter = runProgram specializer (specializer, interpreter)

projection3 :: Specializer source target -> Partializer source target
projection3 specializer = runProgram specializer (specializer, specializer)

Utilizamos la extensión de lenguaje RankNTypes para ocultar la maquinaria de nivel de tipo, lo que nos permite concentrarnos en los idiomas involucrados. También es necesario aplicar un especializador a sí mismo.

En el programa anterior, la segunda proyección es de particular interés. Nos dice que, dado un haskell auto-hosting del especialista en LLVM, podemos aplicarlo a cualquier intérprete escrito en Haskell para algún idioma de origen get para obtener un compilador de 𝒮 to LLVM. Esto significa que podemos escribir un intérprete en un lenguaje de alto nivel y usarlo para generar un compilador que apunte a un lenguaje de bajo nivel. Si el especialista es bueno, entonces el compilador generado también sería decentemente bueno.

Otro detalle digno de mención es que un especialista en auto hosting es muy similar a un compilador de auto hosting. Si su compilador ya realiza una evaluación parcial, no debería ser demasiado trabajo convertirlo en un especialista. Esto significa que implementar las proyecciones de Futamura es mucho más fácil y mucho más gratificante de lo que se creía originalmente. Todavía no lo he probado, así que tómalo con un grano de sal.