Cognition: un nuevo lenguaje antisyntax que redefine la metaprogramación

• Cognition es un proyecto de investigación de lenguajes que adopta una antisyntax completamente posfija para evitar el problema de lectura anticipada (read-ahead) de Lisp y los lenguajes concatenativos
• Sus mecanismos centrales, delimiter, ignore, singlet, falias, crank y metacrank, permiten que los programas cambien sus propias reglas de tokenización y sus ciclos de ejecución
• El bootstrap empieza en un estado donde todos los caracteres se leen como un solo token y por sí mismo migra a un entorno donde el espacio y el salto de línea se usan como delimitadores
• crank y metacrank controlan cuándo se evalúan los tokens y cuándo se acumulan, lo que permite definir dentro de un sistema posfijo una sintaxis de prefijo como comentarios #, escape \\, quote [ y macro (
• Incluso un dialecto de Brainfuck se implementa no con un parser separado sino con palabras de Cognition y reglas de tokenización, mostrando una dirección donde la propia gramática se convierte en código y se automatiza

---

Qué objeta Cognition de las sintaxis existentes

• Lisp ofrece una metaprogramación poderosa con s-expressions y su sistema de macros, pero aun así sigue afectado por una sintaxis fija
  • Un paréntesis izquierdo es la señal de que hay que seguir leyendo hasta encontrar el derecho, así que cambiar el rol de los paréntesis dentro del propio lenguaje es difícil o, en algunas implementaciones, imposible
  • Si se quiere cambiar después la forma de separar tokens ya leídos, hace falta mucho procesamiento de strings
• El proceso de mirar la entrada actual y tener que leer más hacia adelante es syntax; en el momento en que se asume lectura anticipada por defecto, uno queda atado a ciertas formas sintácticas
• Para evitarlo, Cognition usa una antisyntax completamente posfija
  • Se parece a los lenguajes concatenativos, pero considera que incluso los lenguajes concatenativos comunes tienen problemas de lectura anticipada por los corchetes o los caracteres de quote para strings
  • El sistema de macros de Racket se distingue porque usa preprocesamiento, no cambios dinámicos de sintaxis durante la ejecución

El proyecto y la idea base

• Cognition es un proyecto de investigación activo desarrollado durante varios meses junto con Matthew Hinton
• El repositorio de implementación está en cognition-rust, y ahí también hay un paper sobre el lenguaje
• Para entenderlo ayuda tener base en parsing, tokenización y gramáticas
• La explicación sigue el recorrido desde el código de “baremetal cognition” hasta una evolución hacia una sintaxis parecida a Stem

Baremetal Cognition y tokenización

• A simple vista, baremetal Cognition se parece a Brainfuck, pero permite una metaprogramación más potente
• Su código de bootstrap, muy pequeño, usa incluso espacios y saltos de línea con significado, y en el estado inicial cada carácter individual se lee como un token
• Cognition es básicamente un diseño basado en pila, pero usa el término container en un sentido más general que stack
• En el entorno base, salvo un falias especial, ninguna palabra se ejecuta automáticamente

• delimiter, ignore, singlet

  • delimiter permite que el tokenizador sepa dónde termina un token y dónde empieza el siguiente
  • La lista de delimitadores de un solo carácter puede modificarse y leerse desde el propio código de Cognition
  • Los caracteres ignore se omiten en la etapa inicial de recolección de tokens de cada read-eval-print loop
  • El valor por defecto es que todos los caracteres son delimitadores y no hay caracteres ignore
  • Las listas delimiter, singlet e ignore pueden cambiar su comportamiento con flags de whitelist/blacklist
  • La configuración por defecto es: sin delimitadores en blacklist, sin singlets en whitelist y sin caracteres ignore en whitelist
  • singlet es una tercera categoría de tokenización: incluye el carácter en sí dentro del token y luego termina la recolección

• falias

  • falias es una lista de palabras que se ejecutan apenas se apilan en un container
  • El falias base f no se acumula en el container, sino que ejecuta la palabra que está arriba del container
  • En el ejemplo, cuando f ejecuta d, d cambia la lista de delimitadores al valor string de una palabra
  • Después sigue un bootstrap que va convirtiendo paso a paso caracteres como l, g, t y d en no-delimitadores, y cambia espacio y salto de línea para que sean delimitadores e ignore

El entorno de ejecución que crea el bootstrap

• El bootstrap inicial cambia las reglas de delimiter e ignore hasta llegar a un entorno donde espacio y salto de línea son delimitadores de token y además se ignoran al inicio de la lectura del token
• Luego lee 1 y crank, y f ejecuta crank para entrar en un entorno de crank 1
• Lo clave del proceso es que la forma de tokenizar puede cambiarse durante la ejecución
  • Los cambios a delimiter, singlet e ignore pueden automatizarse con programas
  • Al ser un sistema posfijo y sin lectura anticipada, no hace falta parsear por adelantado uno o más tokens antes de evaluar una expresión
• falias permite ejecutar ciertas palabras incluso sin palabras de prefijo ni ejecución automática de palabras base

crank y metacrank

• crank es el mecanismo que decide con qué ciclo se ejecutan los tokens apilados
• La palabra crank toma un número como argumento y, a partir de ahí, ejecuta el tope de la stack en cada enésima palabra que entre al container
  • El 1 crank del final del bootstrap crea un entorno donde se evalúan todos los tokens
  • En un estado 5 crank, las palabras pueden acumularse hasta que entra el quinto token
• El código de ejemplo usa unglue, swap, quote, prepose y def para crear una palabra llamada 2crank
  • unglue obtiene el valor de una palabra, e incluso puede obtener el function pointer de un builtin como crank
  • prepose se parece a compose de Stem, pero adjunta por delante y coloca el resultado en VMACRO
  • def define 2crank para que ponga 2 en la stack y llame al builtin crank

• Los container y las macros en Cognition

  • En Stem, una palabra puede ponerse directamente en la stack, pero en Cognition una palabra no evaluada entra en un container
  • Gracias a este diseño, una palabra como compose puede tratar de forma consistente containers de una sola palabra y otros containers con la misma API
  • La macro de Cognition no es igual al quote de Stem
  • Cuando se evalúa una macro, ignora crank y se evalúan todos sus elementos internos
  • Si se evalúa una macro enlazada a una palabra, se ejecuta la macro completa sin depender de crank y el cranker solo se incrementa una vez
  • Las macros sirven tanto para código independiente de crank como para expansiones con fines de optimización

• metacrank

  • n m metacrank configura una evaluación con período m sobre el elemento que está n posiciones por debajo en la stack
  • crank equivale a 0 m metacrank
  • Solo puede evaluarse un metacrank por token, y el metacrank más bajo tiene prioridad
  • metacrank y crank se aplican no solo a los tokens del archivo, sino también al proceso recursivo de evaluar definiciones de palabras
  • metacrank permite una manipulación directa de la gramática, como “quiero ejecutar este token después de leer n tokens”
  • Después de programar una palabra de prefijo, se la puede undef si deja de hacer falta
  • También se pueden crear caracteres de prefijo que se detengan no por un carácter de cierre específico, sino después de cierta cantidad de tokens
  • Se puede meter entrada del usuario en un programa matemático y pasar su salida a un sistema gramatical como metacrank

Evolución hacia un dialecto de Stem

• Después del bootstrap, Cognition construye gradualmente desde dentro del propio lenguaje una sintaxis cercana a Stem v2
• Primero elimina f de la lista de falias y deja solo ing
  • Como poner f directamente en la stack lo ejecutaría, se crea ff y luego se parte ese string por la mitad para obtener dos f
  • Después f se define como una palabra vacía equivalente a false

• Comentarios con #

  • El carácter # es el primer ejemplo de código que se comporta como un verdadero prefijo
  • Este carácter de comentario actúa como un prefijo que descarta el texto hasta antes del newline, creando una gramática donde el parser mira hacia adelante
  • La implementación combina geti, getd, gets, crankbase, halt, VMACRO cast, singlet, delim y otros
  • geti, getd y gets obtienen respectivamente ignore, delimiter y singlet como strings
  • halt pone todos los metacranks en 0
  • VMACRO cast convierte el container del tope de la stack en una macro
  • La definición de # cambia primero las reglas de tokenización, luego invoca # sobre palabras que se tokenizarán en el futuro, descarta ese comentario y finalmente vuelve al crank y metacrank originales

• escape, quote y macro

  • \\ se define como un carácter de escape que permite poner en la stack incluso palabras que serían evaluadas
  • Después se agrega la definición de quote [ y luego esa misma quote se usa para redefinir [ con una versión mejor que permite quote recursivo
  • Gracias a def posfijo, es posible usar una definición previa para construir una nueva
  • Ese patrón es una forma de desarrollo frecuente en Cognition de bajo nivel
  • ( se define como bracket de macro
  • Las macros se hacen para expandirse automáticamente, y se considera más eficiente enlazar a una palabra una macro ya expandida
  • En términos funcionales, se evalúan de la misma manera
  • expand expande recursivamente con unglue las definiciones de palabras dentro de un quote o una macro
  • Primero se define un expand básico y luego se redefine usando el propio expand para cubrir casos más generales

Dialecto de Brainfuck

• Sobre el dialecto de Stem ya desarrollado, Cognition define un dialecto de Brainfuck
• El ejemplo de ejecución es ../crank -s 2 bootstrap.cog helloworld.bf brainfuck.cog
• brainfuck.cog no es un parser de Brainfuck en el sentido convencional
  • Define palabras de Brainfuck
  • Tokeniza Brainfuck
  • Lo ejecuta en un entorno nativo de Cognition
• Este ejemplo muestra que con la gramática de Cognition se pueden definir con facilidad gramáticas alternativas
• En vez de leer símbolos y decidir acciones según cada símbolo, Cognition define como palabras los propios caracteres de prefijo que usan metacrank, metiendo la gramática dentro de las definiciones de palabras

La idea de dialect dialect

• Se puede imaginar una palabra como mkprefix
  • Por ejemplo, una palabra que reciba las dos palabras de entrada [ y ] y alguna operación, y defina automáticamente que [ aplique esa operación hasta encontrar ]
• Esta idea es posible porque tanto metacrank como def son palabras normales
• Como incluso d, i y s son palabras, se puede crear un dialecto más abstracto que automatice el proceso de implementar gramáticas
• Todavía no está implementado en la librería estándar, pero sí hay ideas discutidas con Matthew Hinton sobre posibles bibliotecas estándar
  • una metaword que genere y llame automáticamente palabras abstractas
  • una búsqueda de word-generator que abstraiga automáticamente la wordlist actual
  • una forma de indicar marcos de abstracción para resolver problemas

La posibilidad de tratar la gramática como código

• En Cognition, el procesamiento de strings equivale a posprocesamiento del tokenizador, así que las operaciones sobre strings tienen un significado fuerte
• Como posibles áreas de aplicación se mencionan la IA simbólica, la investigación de sintaxis y gramáticas, y los experimentos de prototipado con lenguaje y metalenguaje
• También aparecen ideas como programas que lean archivos de configuración, un shell basado en Cognition o incluso un sistema operativo basado en Cognition
• La idea central es que Cognition hace posible “syntax as code”
  • la gramática puede programarse dinámicamente
  • la propia generación de gramáticas puede automatizarse
• No se abordaron conceptos como Metastack y cd, que quedan como posibles temas para un texto posterior

[GN⁺]

Opiniones de Hacker News

• Todavía no me convence que este enfoque sea mejor que la configuración de capas de reader de Racket.
  Por ejemplo, en Racket se puede crear una implementación integrada de Datalog que use la sintaxis de Datalog y aun así interopere con otros módulos de Racket, sin cambiar el modelo de datos básico.
  Es una forma de hacer metaprogramación sin quedar atrapado en las expresiones S, pero procesándola a un nivel más alto.
  Este tipo de bootstrapping de sintaxis es genial y valioso como investigación, pero no sé si sea fundamentalmente mejor que el enfoque de Racket.
  Las macros de Lisp, Scheme y Racket normalmente operan sobre un AST, pero Rhombus opera sobre "shrubbery", algo parecido a un AST que difiere algunas decisiones de parsing para más adelante, lo que da cierta flexibilidad para extender la sintaxis.
  Referencias: https://docs.racket-lang.org/guide/hash-reader.html, https://docs.racket-lang.org/datalog/datalog.html, paper de Rhombus https://doi.org/10.1145/3580417
  • Tampoco estoy seguro de que sea mejor que las readtables de Common Lisp, y creo que el #lang de Racket es más cómodo de usar que las readtables de CL.
    Solo con readtables ya son lo bastante potentes como para implementar un compilador de C: https://github.com/vsedach/Vacietis
  • Al ver que usan Brainfuck como ejemplo básico, no sé si la intención es que uno se lo tome en serio.
    Personalmente, me largué a reír en la parte donde aparece "metacrank".
  • Decir que las macros de Lisp operan sobre un AST no aplica a Lisp.
    En Emacs Lisp, Common Lisp e ISLISP, las macros simplemente reciben datos y devuelven datos; no existe un concepto como AST.
    Cuando se llama a (foo-macro ...), ... puede ser cualquier dato arbitrario.
    Por ejemplo, (defmacro rev (&rest items) (reverse items)) solo toma la lista de argumentos fuente de la llamada a la macro y la invierte.
    Se puede usar como (rev 1 2 3 4 +) o (rev (rev 10 n -) (+ a 20 b) (rev 30 a *) list), y lo que realmente se pasa son listas, números y símbolos.
    No es texto ni un AST, y funciona de la misma manera aunque se pasen a eval datos calculados.
    El reader de Lisp básicamente lee una capa de datos, las expresiones simbólicas, y EVAL, las macros y otras funciones reciben principalmente datos.
    El compilador puede construir internamente una representación AST, pero eso queda a criterio de la implementación; el lenguaje Lisp normalmente se define sobre una sintaxis de datos, no sobre una sintaxis textual.
    Un intérprete Lisp es un "List Processor" que procesa expresiones S en tiempo de ejecución, no texto, y COMPILE también recibe expresiones S, no texto.
    Racket y Scheme tienen sistemas de macros separados.
• Como consejo para el autor, el texto podría quedar mucho más sólido si pusiera lo más importante primero.
  Pasan más de 300 palabras antes de que se mencione Cognition, el proyecto real, y la discusión sobre Lisp está bien, pero me pregunto si es la parte más importante del proyecto.
  Al leer un texto informativo, uno está evaluando constantemente: "¿vale la pena dedicarle mi tiempo?", así que el documento debería decir desde el principio de qué trata.
  Algo como "Cognition es un nuevo lenguaje que explora sintaxis modificable por el usuario" habría bastado, pero incluso después de los primeros cuatro párrafos me costaba decidir si valía la pena seguir leyendo.
  • Es poco probable que vaya a usar este lenguaje y, aunque lo hiciera, obtendría la información de la documentación, no de este artículo.
    Si el tiempo es dinero, podría decirse que el tiempo que pasé leyendo este artículo fue desperdiciado.
    En vez de esperar que todo el contenido de internet se adapte a los gustos personales, creo que conviene más adaptarse a los formatos existentes.
    El texto no es un medio que deba consumirse solo de forma secuencial como el video, así que se puede leer en diagonal para encontrar partes interesantes y descartarlo si no las hay, o volver al inicio y leerlo si las hay.
    La variedad de estilos de escritura es mejor porque obliga a filtrar conscientemente la información que uno consume; si solo se consume pasivamente, la mente se vuelve perezosa.
    Eso sí, si hubiera sido un video, habría estado de acuerdo.
    En un video hay que decidir antes de verlo si invertir tiempo, y aunque verlo a 2x o saltar 5 a 10 segundos ayuda un poco, no resuelve el problema.
  • El orden me pareció bastante razonable.
    Primero explica el problema y después presenta la solución.
    Con solo leer unas frases ya se nota que es una solución quijotesca a un "problema" que al 99.999%, incluidos quienes como yo han oído hablar de Lisp pero nunca lo han usado fuera de archivos de configuración de Emacs, no le importa; aun así, simplemente seguí leyendo.
  • La parte sobre Lisp no es el elemento más importante del proyecto, pero claramente cumple la función de mostrar el tipo de problema que el proyecto intenta resolver.
    Sin esa sección, lo que viene después habría sido más difícil de entender.
  • Me interesa el concepto, pero me preocupó perder el contexto porque la primera frase parece justificar la necesidad como una reacción a la sintaxis de expresiones S de Lisp.
    Si uno no conoce ese trasfondo, puede perder el contexto de todo el texto, y también es difícil saber si se trata de un argumento de hombre de paja.
    Por eso todo se siente como si existiera para una necesidad muy estrecha, mientras que el título suena mucho más general y como un concepto bastante interesante.
  • Creo que el texto actual está perfectamente bien.
    En las dos primeras frases ya queda claro cuál es el problema que intenta resolver, y eso me resulta mucho más útil para medir mi interés que la introducción propuesta.
• Es un texto interesante, y espero que los autores no le presten atención al sarcasmo de aquí y sigan con sus rituales de magia oscura.
  Dicho eso, en lo personal, cuando miro hacia arriba en la escalera de la pureza de la programación, Forth es más o menos el límite de pureza filosófica que puedo soportar.
  • Como autor de este texto, no me molesta el sarcasmo; de hecho, me parece bastante gracioso y lo agradezco.
    Vamos a seguir cubriendo más magia oscura en el futuro.
• La metaprogramación y la programación son lo mismo.
  Lo que pasa es que casi todos los lenguajes, incluidos todos los Lisp, manejan mal la cita, y curiosamente m4 es la excepción.

Lisp esquiva este problema con macros, permitiendo tratar sentencias del metalenguaje expresadas como sentencias del lenguaje objeto sin tener en cuenta las comillas
Este problema surge porque tanto en el lenguaje objeto como en el metalenguaje se trata el espacio como el fin de un átomo, sin distinguir entre ambos
El enfoque de Cognition, una antisintaxis totalmente posfija, se parece a los lenguajes de programación concatenativos, pero los lenguajes posfijos son el dual de los lenguajes prefijos y sufren el mismo problema
O bien hay que fijar de antemano la aridad de todos los símbolos y no usar funciones de orden superior, o se necesita un par de delimitadores que permita serializar el árbol
Depender de una pila implícita de aridad 0 es parecido a hacer una lobotomía para curar la depresión

• Se agradece el feedback, pero si todavía no leíste todo el artículo, convendría hacerlo
  Ni nosotros sabemos hasta qué punto lo que hicimos es nuevo, y si crees que se puede hacer en Lisp lo que hacemos nosotros, eres bienvenido a demostrar que estamos equivocados
• Me gustaría ver un ejemplo de cómo difiere la cita en Lisp y en m4
  La afirmación en sí es interesante, pero hace falta algo más concreto
• La analogía sobre la pila implícita es vistosa, pero las pilas implícitas existen desde la época de las primeras computadoras y calculadoras
  Así como una lobotomía reduce las capacidades de procesamiento de orden superior, volver a la forma más primitiva de cálculo con cadenas de comandos puede verse como algo similar
  https://www.hpmuseum.org/rpnvers.htm
• Me parece realmente hermoso que un programa en Cognition pueda definir y redefinir estructuras sintácticas durante la ejecución, y entrar y salir de ellas
  Me gusta especialmente que el mecanismo sea tan pequeño
  No soy experto en lenguajes, así que no sé si hay algo novedoso, pero mientras leía el artículo sentía la alegría de los autores al descubrir una nueva cordillera de posibilidades cada vez que superaban una colina
  Si lo entendí bien, la idea es que con Cognition se puede construir de verdad una máquina pensante
  Sin que el programa se detenga y se reinicie con nuevas instrucciones, puede escribir y ejecutar por sí mismo nuevas subrutinas a partir de nueva entrada
  Es decir, el programa puede aprender y adaptarse creando nuevas abstracciones y conectándose a nuevas API
  Para mí esto es más interesante que redes neuronales más grandes o nuevas técnicas de aprendizaje
• La premisa no es cierta
  Common Lisp tiene reader macros, así que puedes cambiar la sintaxis como quieras, e incluso hay compiladores de Fortran que leen sintaxis de Fortran mediante reader macros
  Common Lisp tiene reader macros en tiempo de lectura, macros, y compiler macros en tiempo de compilación, y todos esos lenguajes de macros son Common Lisp
  La metaprogramación no tiene mucho que ver con macros o sintaxis, sino con la semántica de tipos, interfaces, clases, métodos, etc., y con la capacidad de manipular su significado
  Si CL por sí mismo no fuera lo bastante potente para eso, existe CLOS, es decir, el Common Lisp Metaobject Protocol
  • Aquí se habla de las reader macros de CL
    Con las reader macros de CL se puede usar otro tokenizador, pero hay que indicar el cambio de tokenizador mediante una expresión dentro de la read table
    En Cognition, parece que al llamar a una función cambia el tokenizador del contexto del llamador
• Parece un ejemplo práctico de bootstrappear una máquina mínima hasta convertirla en un intérprete de un lenguaje de alto nivel
  La razón por la que aprendimos que hacer algo así con una máquina de Turing o el cálculo lambda era importante es que mostraba que un lenguaje de alto nivel es equivalente a un lenguaje base, y por lo tanto lo razonado sobre el primero también puede aplicarse al segundo
  El primer y único ejemplo que se me ocurre es el problema de la detención
  A escala práctica, si se demuestra que el lenguaje base no tiene fugas de memoria, ¿se puede decir que el lenguaje derivado tampoco las tendrá?
  Me pregunto qué ventajas tiene este tipo de bootstrapping
  Si la respuesta es simplemente, como al escalar el Everest, "porque está ahí", también lo respeto
• En la parte donde dicen que importan el espacio después de df, el espacio de la línea 3 y el salto de línea, pasé directamente a "gracias, pero no"
  Los tres espacios al final de la línea anterior indican sarcasmo, y donde no sea fácil distinguir los espacios finales, puede interpretarse literalmente
  • El punto de este experimento parece ser que Forth tiene un carácter que no se puede redefinir, el espacio, y ver qué pasa si se elimina esa restricción
    La parte de bootstrap mencionada es, en realidad, el momento en que se le indica al lector que trate los espacios y saltos de línea como delimitadores
    Es decir, la queja sería que el espacio tiene significado en la sección donde se lo declara como delimitador
    Por supuesto tienes derecho a pensarlo así, pero me pregunto si había una mejor forma de hacerlo
  • Esos caracteres de espacio son la forma de convertir en un espacio como tal un espacio que antes no era diferente de cualquier otro carácter
    No se me ocurre cómo hacerlo sin que, al menos una vez, un espacio literal tenga significado de esa manera
• Hablan de la "trampa de tener alguna forma de sintaxis", pero la sintaxis aporta estructura
  ¿De verdad crees que sin sintaxis se podría leer una oración como "oración esta sin tú sintaxis leer puedes"?
  Cognition dice usar una antisintaxis totalmente posfija, pero lo posfijo también es sintaxis
  Basta preguntarle a un hablante de alemán por los verbos que van al final de la oración
  Incluso en el primer ejemplo, el orden de los operandos y los operadores importa, y eso es precisamente sintaxis
  Esto parece un intento de crear un lenguaje absurdamente comprimido, y recuerda mucho a APL
  Como pista para los autores: no eliminaron la sintaxis, solo la hicieron difícil de leer y entender para humanos, y la legibilidad y comprensibilidad son factores importantes en programación
• Fue algo difícil de leer
  Se siente como si las reglas bajo tus pies cambiaran constantemente, como si se introdujeran reglas y palabras y luego se redefinieran a voluntad
  En conjunto tiene un aire muy Numberwang, y esa parece ser una de las razones por las que se percibe como sátira
  Otra razón importante es que la etapa de bootstrapping está escrita de forma ridículamente exagerada, aunque eso parece intencional
  Claramente hay algo profundo ahí, pero tendré que volver a leerlo después de tomar un café más fuerte
  • Hay mucho que explicar, y también siento que la forma actual de explicarlo no fue la óptima
    Soy uno de los autores de este artículo, y el problema es que hay muchísimo contenido que transmitir
    Matthew y yo estuvimos intercambiando ideas varias horas al día durante 3 semanas sobre el diseño de este lenguaje, y también hay mucho contexto que hay que completar para personas que no me conocen realmente