¿Es posible una variante Lisp completa de tipo estático?

¿Es posible una variante Lisp completa de tipo estático? ¿Tiene sentido que exista algo como esto? Creo que una de las virtudes de un lenguaje Lisp es la simplicidad de su definición. ¿La escritura estática comprometería este principio fundamental?

Sí, es muy posible, aunque un sistema de tipo de estilo HM estándar suele ser la elección incorrecta para la mayoría de los códigos Lisp / Scheme idiomáticos. Vea Typed Racket para un lenguaje reciente que es un "Full Lisp" (más como Scheme, en realidad) con escritura estática.

Si todo lo que quisiera fuera un lenguaje de tipado estático que se pareciera a Lisp, podría hacerlo con bastante facilidad, definiendo un árbol de sintaxis abstracto que represente su lenguaje y luego mapeando ese AST a expresiones S. Sin embargo, no creo que llamaría Lisp al resultado.

Si desea algo que realmente tenga características Lisp-y además de la sintaxis, es posible hacerlo con un lenguaje escrito estáticamente. Sin embargo, hay muchas características de Lisp de las que es difícil obtener una escritura estática muy útil. Para ilustrar, echemos un vistazo a la estructura de la lista en sí, llamada contras , que forma el bloque de construcción principal de Lisp.

Llamar a los contras una lista, aunque (1 2 3)parece una, es un nombre poco apropiado. Por ejemplo, no es en absoluto comparable a una lista escrita estáticamente, como la lista de C ++ std::listo Haskell. Se trata de listas enlazadas unidimensionales en las que todas las celdas son del mismo tipo. Lisp felizmente lo permite (1 "abc" #\d 'foo). Además, incluso si amplía sus listas de tipo estático para cubrir listas de listas, el tipo de estos objetos requiere que cada elemento de la lista sea una sublista. ¿Cómo representarías ((1 2) 3 4)en ellos?

Lisp conses forma un árbol binario, con hojas (átomos) y ramas (conses). Además, las hojas de un árbol así pueden contener cualquier tipo Lisp atómico (no contras). La flexibilidad de esta estructura es lo que hace que Lisp sea tan bueno en el manejo de cálculos simbólicos, AST y en la transformación del código Lisp en sí.

Entonces, ¿cómo modelaría esa estructura en un lenguaje de tipado estático? Probémoslo en Haskell, que tiene un sistema de tipo estático extremadamente potente y preciso:

type Symbol = String
data Atom = ASymbol Symbol | AInt Int | AString String | Nil
data Cons = CCons Cons Cons 
            | CAtom Atom

Su primer problema será el alcance del tipo Atom. Claramente, no hemos elegido un tipo de Atom con la suficiente flexibilidad para cubrir todos los tipos de objetos que queremos lanzar en contra. En lugar de intentar extender la estructura de datos de Atom como se enumera anteriormente (que puede ver claramente que es frágil), digamos que teníamos una clase de tipos mágicos Atomicque distinguía todos los tipos que queríamos hacer atómicos. Entonces podríamos intentar:

class Atomic a where ?????
data Atomic a => Cons a = CCons Cons Cons 
                          | CAtom a

Pero esto no funcionará porque requiere que todos los átomos del árbol sean del mismo tipo. Queremos que puedan diferir de una hoja a otra. Un mejor enfoque requiere el uso de cuantificadores existenciales de Haskell :

class Atomic a where ?????
data Cons = CCons Cons Cons 
            | forall a. Atomic a => CAtom a 

Pero ahora llega al meollo del asunto. ¿Qué se puede hacer con los átomos en este tipo de estructura? ¿Qué estructura tienen en común con la que se podría modelar Atomic a? ¿Qué nivel de seguridad de tipo tiene garantizado con un tipo de este tipo? Tenga en cuenta que no hemos agregado ninguna función a nuestra clase de tipos, y hay una buena razón: los átomos no comparten nada en común en Lisp. Su supertipo en Lisp simplemente se llama t(es decir, top).

Para poder usarlos, tendrías que idear mecanismos para convertir dinámicamente el valor de un átomo en algo que realmente puedas usar. ¡Y en ese punto, básicamente ha implementado un subsistema escrito dinámicamente dentro de su lenguaje escrito estáticamente! (Uno no puede dejar de notar un posible corolario de la Décima Regla de Programación de Greenspun ).

Tenga en cuenta que Haskell proporciona soporte para un subsistema dinámico con un Objtipo, usado junto con un Dynamictipo y una clase Typeable para reemplazar nuestra Atomicclase, que permite que los valores arbitrarios se almacenen con sus tipos y la coerción explícita de esos tipos. Ese es el tipo de sistema que necesitaría usar para trabajar con estructuras de contras de Lisp en toda su generalidad.

Lo que también puede hacer es ir al otro lado e incrustar un subsistema de tipo estático dentro de un lenguaje esencialmente de tipo dinámico. Esto le permite el beneficio de la verificación de tipo estática para las partes de su programa que pueden aprovechar los requisitos de tipo más estrictos. Este parece ser el enfoque adoptado en la forma limitada de verificación de tipo precisa de CMUCL , por ejemplo.

Finalmente, existe la posibilidad de tener dos subsistemas separados, de tipo dinámico y estático, que usan programación de estilo de contrato para ayudar a navegar la transición entre los dos. De esa manera, el lenguaje puede adaptarse a los usos de Lisp donde la verificación de tipos estáticos sería más un obstáculo que una ayuda, así como los usos donde la verificación de tipos estáticos sería ventajosa. Este es el enfoque adoptado por Typed Racket , como verá en los comentarios que siguen.

Mi respuesta, sin un alto grado de confianza, probablemente sea . Si observa un lenguaje como SML, por ejemplo, y lo compara con Lisp, el núcleo funcional de cada uno es casi idéntico. Como resultado, no parece que tenga muchos problemas para aplicar algún tipo de tipado estático al núcleo de Lisp (aplicación de funciones y valores primitivos).

Sin embargo, su pregunta dice completa , y donde veo que surgen algunos de los problemas es el enfoque de código como datos. Los tipos existen a un nivel más abstracto que las expresiones. Lisp no tiene esta distinción: todo tiene una estructura "plana". Si consideramos alguna expresión E: T (donde T es una representación de su tipo), y luego consideramos que esta expresión es un dato simple, ¿cuál es exactamente el tipo de T aquí? ¡Bueno, es una especie! Un tipo es un tipo de orden superior, así que sigamos adelante y digamos algo sobre eso en nuestro código:

E : T :: K

Puede que veas a dónde voy con esto. Estoy seguro de que al separar la información del tipo del código sería posible evitar este tipo de autorreferencialidad de los tipos, sin embargo, eso haría que los tipos no fueran muy "lisos" en su sabor. Probablemente hay muchas formas de evitar esto, aunque no es obvio para mí cuál sería la mejor.

EDITAR: Oh, así que con un poco de búsqueda en Google, encontré Qi , que parece ser muy similar a Lisp, excepto que está escrito de forma estática. Quizás sea un buen lugar para comenzar a ver dónde hicieron cambios para que la escritura estática esté allí.

Dylan: Ampliación del sistema de tipos de Dylan para una mejor inferencia de tipos y detección de errores