Cognition: a nova linguagem antisyntax que redefine a metaprogramação

• Cognition é um projeto de pesquisa de linguagem que adota uma antisyntax totalmente pós-fixada (postfix) para evitar o problema de leitura antecipada (read-ahead) presente em Lisp e em linguagens concatenativas
• Seus mecanismos centrais — delimiter, ignore, singlet, falias, crank e metacrank — permitem que o programa altere as próprias regras de tokenização e o ciclo de execução
• O bootstrap começa em um estado em que todos os caracteres são lidos como tokens únicos e, por conta própria, migra para um ambiente que usa espaço e quebra de linha como delimitadores
• crank e metacrank controlam quando os tokens são avaliados e quando ficam acumulados, permitindo definir dentro de um sistema pós-fixado uma sintaxe prefixada como comentários #, escape \, quote [ e macro (
• Um dialeto de Brainfuck também é implementado não por um parser separado, mas por meio de palavras do Cognition e regras de tokenização, mostrando um caminho para transformar a própria gramática em código e automatizá-la

---

Onde o Cognition vê problemas na sintaxe tradicional

• Lisp oferece metaprogramação poderosa com s-expressions e sistema de macros, mas ainda sofre a influência de uma sintaxe fixa
  • Um parêntese à esquerda sinaliza que é preciso continuar lendo até aparecer o parêntese à direita, então é difícil — ou em algumas implementações impossível — mudar o papel dos parênteses dentro da própria linguagem
  • Se você quiser mudar depois a forma como tokens já lidos foram delimitados, será necessário muito processamento de strings
• O processo de olhar a entrada atual e decidir que é preciso ler mais adiante é a syntax; no momento em que se assume leitura antecipada por padrão, fica-se preso a certas formas sintáticas
• Para evitar isso, o Cognition usa uma antisyntax completamente pós-fixada
  • Ele se parece com linguagens concatenativas, mas considera que mesmo linguagens concatenativas comuns têm problemas de leitura antecipada por causa de colchetes ou caracteres de quote de string
  • O sistema de macros do Racket é distinguido por usar pré-processamento, e não mudanças dinâmicas de sintaxe durante a execução

O projeto e a ideia básica

• Cognition é um projeto de pesquisa ativo desenvolvido ao longo de alguns meses junto com Matthew Hinton
• O repositório da implementação é cognition-rust, e ele também inclui um artigo sobre a linguagem
• Ter familiaridade com parsing, tokenização e gramática ajuda na compreensão
• A explicação parte do código de “baremetal cognition” e acompanha sua evolução para uma sintaxe parecida com a de Stem

Baremetal Cognition e tokenização

• À primeira vista, o baremetal Cognition lembra Brainfuck, mas permite metaprogramação muito mais forte
• O código de bootstrap, extremamente pequeno, usa inclusive espaços e quebras de linha de forma significativa e, no estado inicial, cada caractere individual é lido como token
• Cognition tem um projeto baseado em pilha, mas usa o termo container em um sentido mais geral que stack
• No ambiente padrão, nenhuma palavra é executada automaticamente, exceto as falias especiais

• delimiter, ignore, singlet

  • delimiter permite ao tokenizador saber onde termina um token e onde começa o próximo
  • A lista de delimitadores de um único caractere pode ser modificada e lida dentro do próprio código Cognition
  • Caracteres ignore são pulados no início da etapa de coleta de tokens de cada ciclo read-eval-print loop
  • O estado padrão é: todos os caracteres são delimitadores e não há caracteres ignore
  • As listas de delimiter, singlet e ignore podem mudar de comportamento por meio de flags de whitelist/blacklist
  • A configuração padrão é: nenhum delimiter em blacklist, nenhum singlet em whitelist e nenhum caractere ignore em whitelist
  • singlet é uma terceira categoria de tokenização: ele inclui a si mesmo no token e então encerra a coleta do token

• falias

  • falias é a lista de palavras executadas assim que entram no container
  • A falias padrão f não é empilhada no container; ela executa a palavra no topo do container
  • No exemplo, quando f executa d, d transforma a lista de delimitadores no valor em string da palavra
  • Depois disso, segue um bootstrap que torna gradualmente caracteres como l, g, t e d em não-delimitadores e muda espaço e quebra de linha para delimiter e ignore

O ambiente de execução criado pelo bootstrap

• O bootstrap inicial altera as regras de delimiter e ignore e acaba criando um ambiente em que espaço e quebra de linha são delimitadores de token e são ignorados no início da coleta de tokens
• Depois disso, lê 1 e crank, e f executa crank, entrando em um ambiente de crank 1
• O ponto central desse processo é que o modo de tokenização pode ser alterado durante a execução
  • Mudanças em delimiter, singlet e ignore podem ser automatizadas por programa
  • Como o sistema é pós-fixado e não há leitura antecipada, não é preciso fazer parsing prévio de um ou mais tokens antes de avaliar uma expressão
• falias permite executar certas palavras sem depender de palavras prefixadas nem de execução automática das palavras básicas

crank e metacrank

• crank é o mecanismo que determina em que ritmo os tokens sobre a stack serão executados
• A palavra crank recebe um número como argumento e, a partir daí, executa o topo da stack a cada n-ésima palavra que entrar no container
  • O 1 crank no fim do bootstrap cria um ambiente em que todos os tokens são avaliados
  • Em um estado 5 crank, palavras podem se acumular até a chegada do quinto token
• O código de exemplo usa unglue, swap, quote, prepose e def para criar uma palavra chamada 2crank
  • unglue obtém o valor de uma palavra e também pode obter o ponteiro de função de builtins como crank
  • prepose é parecido com compose do Stem, mas anexa na frente e coloca em VMACRO
  • def define 2crank para colocar 2 na stack e chamar o builtin crank

• Containers e macro no Cognition

  • Em Stem, palavras podem ser colocadas diretamente na stack, mas em Cognition palavras ainda não avaliadas ficam dentro de um container
  • Esse design permite que palavras como compose tratem, com uma API consistente, tanto containers de uma única palavra quanto outros containers
  • A macro do Cognition é diferente do quote do Stem
  • Quando uma macro é avaliada, ela ignora o crank e todos os elementos internos são avaliados
  • Se uma macro ligada a uma palavra for avaliada, a macro inteira será executada independentemente do crank, e o cranker será incrementado apenas uma vez
  • Macros são úteis para código independente de crank e para expansões voltadas à otimização

• metacrank

  • n m metacrank define uma avaliação de período m para o elemento que está n posições abaixo no topo da stack
  • crank equivale a 0 m metacrank
  • Só um metacrank pode ser avaliado por token, e metacranks mais baixos têm prioridade
  • metacrank e crank se aplicam não só aos tokens do arquivo, mas também ao processo recursivo de avaliação de definições de palavras
  • metacrank permite manipulação direta da sintaxe, como “quero executar este token depois de ler n tokens”
  • Depois de programar uma palavra prefixada, ela pode ser removida com undef quando não for mais necessária
  • Também é possível criar um caractere prefixado que pare depois de um número específico de tokens, em vez de depender de um caractere de término específico
  • Dá para colocar entrada do usuário em um programa matemático e passar sua saída para um sistema gramatical como o metacrank

Evolução para um dialeto de Stem

• Depois do bootstrap, o Cognition constrói gradualmente, de dentro da própria linguagem, uma sintaxe próxima da Stem v2
• Primeiro, f é removido da lista de falias e apenas ing permanece
  • Como colocar f diretamente na stack o executaria, cria-se ff e depois a string é dividida ao meio para obter dois f
  • Em seguida, f é definido como uma palavra vazia correspondente a false

• Comentários com #

  • O caractere # é o primeiro exemplo de código que se comporta como um prefixo real
  • Esse caractere de comentário funciona como um prefixo que descarta o texto até a quebra de linha, criando uma sintaxe em que o parser lê adiante
  • A implementação combina geti, getd, gets, crankbase, halt, VMACRO cast, singlet, delim e outros
  • geti, getd e gets obtêm como string, respectivamente, ignore, delimiter e singlet
  • halt zera todos os metacranks
  • VMACRO cast converte o container no topo da stack em macro
  • A definição de # altera as regras de tokenização, agenda uma chamada futura de # para a palavra que será tokenizada adiante, descarta o comentário e depois retorna ao crank e aos metacranks originais

• escape, quote e macro

  • \ é definido como um caractere de escape que permite colocar na stack até palavras que seriam avaliadas
  • Depois é adicionada a definição de quote com [, e então esse próprio quote é usado para redefinir [ de forma melhor, permitindo quote recursivo
  • Por causa do def pós-fixado, é possível usar a definição anterior para criar a nova
  • Esse padrão é uma forma comum de desenvolvimento no Cognition de baixo nível
  • ( é definido como delimitador de macro
  • As macros são feitas para expansão automática, e entende-se que é mais eficiente ligar a uma palavra uma macro já expandida
  • Funcionalmente, a avaliação ocorre da mesma forma
  • expand expande recursivamente, com unglue, as definições de palavras dentro de quote ou macro
  • Primeiro define-se um expand básico e depois ele próprio é usado para redefini-lo, cobrindo casos mais gerais

Dialeto de Brainfuck

• Cognition define um dialeto de Brainfuck em cima do dialeto de Stem já evoluído
• O exemplo de execução é ../crank -s 2 bootstrap.cog helloworld.bf brainfuck.cog
• brainfuck.cog não é um parser de Brainfuck no sentido tradicional
  • Ele define palavras de Brainfuck
  • Ele tokeniza Brainfuck
  • Ele executa tudo no ambiente nativo do Cognition
• Esse exemplo mostra que a gramática do Cognition permite definir gramáticas alternativas com facilidade
• Em vez de ler símbolos e decidir a ação com base neles, o Cognition usa metacrank para definir os próprios caracteres prefixados como palavras, incorporando a gramática às definições das palavras

A ideia de “dialect dialect”

• É possível imaginar uma palavra como mkprefix
  • Por exemplo, uma palavra que receba duas palavras de entrada, [ e ], junto com alguma operação, e defina automaticamente [ para aplicar essa operação até encontrar ]
• Isso é possível porque tanto metacrank quanto def são palavras comuns
• Como até d, i e s são palavras, dá para criar dialetos mais abstratos que automatizem o processo de implementação da gramática
• Isso ainda não existe na biblioteca padrão, mas há itens discutidos com Matthew Hinton como possibilidades para a biblioteca padrão
  • uma metaword que gere e invoque automaticamente palavras abstratas
  • busca por um word-generator que abstraia automaticamente a wordlist atual
  • um modo de orientar um framework de abstração para resolver problemas

A possibilidade de tratar gramática como código

• Em Cognition, processamento de strings equivale a um pós-processamento do tokenizador, o que dá bastante peso semântico às operações sobre strings
• Entre as aplicações potenciais estão Symbolic AI, pesquisa sobre sintaxe e gramática, e experimentos com linguagem e metalanguage
• Também aparecem ideias como um programa que leia arquivos de configuração, um shell baseado em Cognition e até um sistema operacional baseado em Cognition
• O ponto principal é que o Cognition torna possível fazer “syntax as code”
  • A gramática pode ser programada dinamicamente
  • A própria geração de gramática pode ser automatizada
• Conceitos como Metastack e cd não foram abordados e ficam como temas possíveis para um texto futuro

[GN⁺]

Opiniões do Hacker News

• Ainda não me convenceram de que essa abordagem é melhor do que a configuração da camada de reader do Racket
  Por exemplo, no Racket, é possível criar uma implementação embutida de Datalog que usa a sintaxe do Datalog e ainda assim interoperar com outros módulos Racket, sem mudar o modelo de dados básico
  É uma forma de fazer metaprogramação sem ficar preso a S-expressions, mas tratando tudo em um nível mais alto
  Esse tipo de bootstrap de sintaxe é legal e tem valor como pesquisa, mas não sei se é fundamentalmente melhor que a abordagem do Racket
  Macros de Lisp, Scheme e Racket normalmente operam sobre ASTs, mas Rhombus opera sobre algo chamado "shrubbery", que é parecido com uma AST mas adia algumas decisões de parsing, dando um pouco de flexibilidade para extensão de sintaxe
  Referências: https://docs.racket-lang.org/guide/hash-reader.html, https://docs.racket-lang.org/datalog/datalog.html, artigo do Rhombus https://doi.org/10.1145/3580417
  • Também não tenho certeza de que seja melhor do que a readtable do Common Lisp, e acho o #lang do Racket mais fácil de usar do que a readtable do CL
    Só a readtable já é poderosa o suficiente para implementar um compilador C: https://github.com/vsedach/Vacietis
  • Ao ver Brainfuck sendo usado como exemplo básico, não sei bem se a intenção é que eu leve isso a sério
    Pessoalmente, caí na gargalhada na parte em que aparece "metacrank"
  • A afirmação de que macros Lisp operam sobre ASTs não se aplica ao Lisp
    Em Emacs Lisp, Common Lisp e ISLISP, macros simplesmente recebem algum dado e retornam algum dado; não existe um conceito como AST
    Ao chamar (foo-macro ...), ... pode ser qualquer dado arbitrário
    Por exemplo, (defmacro rev (&rest items) (reverse items)) apenas recebe a lista de argumentos de origem da chamada da macro e a inverte
    Pode ser usado como (rev 1 2 3 4 +) ou (rev (rev 10 n -) (+ a 20 b) (rev 30 a *) list), e o que é realmente passado são listas, números e símbolos
    Não é texto nem AST; mesmo passando dados calculados para eval, funciona da mesma forma
    O reader do Lisp basicamente lê a camada de dados, isto é, expressões simbólicas, e EVAL, macros e outros recursos recebem principalmente dados
    O compilador pode criar internamente uma representação de AST, mas isso é liberdade de implementação; a linguagem Lisp normalmente é definida sobre uma sintaxe de dados, não uma sintaxe textual
    Um interpretador Lisp é um "List Processor" que, durante a execução, processa S-expressions, não texto, e COMPILE também recebe S-expressions, não texto
    Racket e Scheme têm sistemas de macros separados
• Como conselho ao autor, o texto poderia ficar muito mais sólido se colocasse o ponto mais importante primeiro
  São mais de 300 palavras até o projeto real, Cognition, ser mencionado; a discussão sobre Lisp é boa, mas fico em dúvida se é a parte mais importante do projeto
  Ao ler um texto informativo, fico o tempo todo pensando "isso vale meu tempo?", então o documento precisa dizer desde o início do que se trata
  Algo como "Cognition é uma nova linguagem que explora sintaxe modificável pelo usuário" teria sido suficiente, mas mesmo depois dos quatro primeiros parágrafos ainda era difícil decidir se valia continuar lendo
  • A chance de eu usar essa linguagem é baixa e, mesmo que eu a use, vou obter as informações na documentação, não neste texto
    Se tempo é dinheiro, então o tempo gasto lendo este texto pode ser considerado desperdício
    Em vez de esperar que todo conteúdo da internet seja moldado ao gosto pessoal, acho melhor se adaptar aos formatos que já existem
    Texto não é um meio que precise ser consumido apenas sequencialmente, como vídeo; dá para passar os olhos, procurar partes interessantes e descartar se não houver, ou voltar ao início e ler se houver
    Formas variadas de escrita são melhores porque obrigam a filtrar conscientemente a informação consumida; consumir tudo passivamente deixa a mente preguiçosa
    Dito isso, eu concordaria se fosse um vídeo
    Em vídeo, é preciso decidir antes se vale investir tempo, e 2x ou pular 5–10 segundos ajuda um pouco, mas não resolve o problema
  • A ordem me pareceu bastante razoável
    Primeiro explica o problema e depois apresenta a solução
    Bastaram algumas frases para eu perceber que era uma solução quixotesca para um "problema" com o qual 99,999% das pessoas — incluindo eu, que já ouvi falar de Lisp mas nunca o usei fora de arquivos de configuração do Emacs — não se importariam, mas continuei lendo mesmo assim
  • A parte sobre Lisp não é o elemento mais importante do projeto, mas claramente serve para mostrar o tipo de problema que o projeto tenta resolver
    Sem esse trecho, o conteúdo posterior teria sido mais difícil de entender
  • Tenho interesse no conceito, mas a primeira frase parece justificar a necessidade como uma reação à sintaxe de S-expressions do Lisp, então fiquei preocupado em perder o contexto
    Se você não conhece esse pano de fundo, pode perder o contexto do texto inteiro, e também fica difícil julgar se isso é um espantalho
    Por isso, tudo parece existir para uma necessidade muito estreita, enquanto o título é bem mais geral e soa como um conceito bastante interessante
  • Acho que o texto atual está perfeitamente ok
    Nas duas primeiras frases, fica claro qual é o problema que se tenta resolver, e isso é muito mais útil para eu avaliar meu interesse do que a introdução proposta
• É um texto interessante, e espero que os autores não liguem para o sarcasmo daqui e continuem com seus rituais de magia negra
  Ainda assim, pessoalmente, quando olho para a escada da pureza em programação, algo como Forth é o limite de pureza filosófica que consigo aguentar
  • Como autor deste texto, não ligo para o sarcasmo; na verdade acho bem engraçado e acolho isso
    Pretendo continuar tratando de ainda mais magia negra daqui para frente
• Metaprogramação e programação são a mesma coisa
  Só que quase todas as linguagens, incluindo todos os Lisps, lidam mal com citação e, curiosamente, m4 é uma exceção

Lisp contorna esse problema com macros, permitindo lidar com sentenças da metalinguagem expressas como sentenças da linguagem-objeto sem levar em conta a citação
Esse problema surge porque, tanto na linguagem-objeto quanto na metalinguagem, o espaço em branco é tratado como o fim de um átomo, sem distinguir uma da outra
A abordagem do Cognition, uma antissintaxe totalmente pós-fixa, se parece com linguagens de programação concatenativas, mas linguagens pós-fixas são o dual das linguagens prefixas e sofrem do mesmo problema
É preciso definir de antemão a aridade de todos os símbolos e não usar funções de ordem superior, ou então ter um par de delimitadores capaz de serializar a árvore
Depender de uma pilha implícita de aridade zero é parecido com fazer uma lobotomia para curar depressão

• Obrigado pelo feedback, mas, se você ainda não leu o texto inteiro, seria bom ler
  Nós também não sabemos até que ponto criamos algo novo, e, se você acha que dá para fazer em Lisp o que estamos fazendo, fique à vontade para provar que estamos errados
• Fiquei curioso por um exemplo de como a citação difere entre Lisp e m4
  A afirmação em si é interessante, mas precisa de algo mais concreto
• A analogia com a pilha implícita é vistosa, mas a pilha implícita existe desde os tempos dos primeiros computadores e calculadoras
  Assim como uma lobotomia reduz capacidades de processamento de ordem superior, voltar ao modo mais primitivo de calcular strings de comandos também pode ser visto de forma parecida
  https://www.hpmuseum.org/rpnvers.htm
• Acho realmente bonito que um programa em Cognition possa definir e redefinir estruturas sintáticas durante a execução, e entrar e sair delas
  Gosto especialmente do fato de esse mecanismo ser muito pequeno
  Não sou especialista em linguagens, então não sei se há novidade nisso, mas, ao longo da leitura, senti a alegria dos autores ao descobrir uma nova cadeia de montanhas de possibilidades a cada colina vencida
  Se entendi direito, a ideia é que com Cognition seria possível criar uma máquina que pensa de verdade
  Sem que o programa precise ser interrompido e reiniciado com novos comandos, ele pode escrever e executar novas sub-rotinas por conta própria com base em novas entradas
  Ou seja, significa que o programa pode aprender e se adaptar criando novas abstrações e se conectando a novas APIs
  Para mim, isso é mais interessante do que redes neurais maiores ou novas técnicas de aprendizado
• A premissa não é verdadeira
  Common Lisp tem reader macros, que permitem alterar a sintaxe como quiser, e há até compiladores Fortran que leem sintaxe Fortran usando reader macros
  Common Lisp tem reader macros em tempo de leitura, macros e compiler macros em tempo de compilação, e todas essas linguagens de macro são Common Lisp
  Metaprogramação não tem muita relação com macros ou sintaxe; ela se refere à capacidade de manipular a semântica e os significados de tipos, interfaces, classes, métodos etc.
  Se o próprio CL não for poderoso o bastante, existe para isso o CLOS, isto é, o Common Lisp Metaobject Protocol
  • O que está sendo mencionado aqui são as reader macros de CL
    Com reader macros de CL é possível usar outro tokenizer, mas é preciso sinalizar a troca de tokenizer com uma expressão dentro da read table
    Em Cognition, parece que chamar uma função altera o tokenizer no contexto do chamador
• Parece um exemplo prático de bootstrap de uma máquina mínima para transformá-la em um interpretador de uma linguagem de alto nível
  O motivo pelo qual aprendemos que esse tipo de coisa é importante com máquinas de Turing ou cálculo lambda era mostrar que linguagens de alto nível são equivalentes às linguagens fundamentais, e portanto o que se conclui sobre as primeiras pode ser aplicado às segundas
  O primeiro e único exemplo que me vem à cabeça é o problema da parada
  Em escala prática, se provarmos que a linguagem básica não tem vazamentos de memória, podemos dizer que a linguagem derivada também não terá vazamentos?
  Fico curioso para saber quais são as vantagens desse tipo de bootstrapping
  Se a resposta for simplesmente, como escalar o Everest, "porque está lá", também respeito
• Na parte em que o espaço depois de df, o espaço na linha 3 e a quebra de linha são importantes, já virou um "obrigado, mas passo" para mim
  Os três espaços em branco no fim da linha anterior indicam sarcasmo e podem ser interpretados literalmente em lugares onde não é fácil distinguir espaços finais
  • O ponto desse experimento parece ser: Forth tem um único caractere que não pode ser redefinido, isto é, o espaço; o que acontece se essa restrição for removida?
    A parte de bootstrap mencionada na verdade é o trecho que informa ao leitor que espaço e quebra de linha devem ser tratados como delimitadores
    Ou seja, você está reclamando que o espaço tem significado justamente na seção em que ele é declarado como delimitador
    Claro, você tem o direito de pensar assim, mas fico curioso se havia uma maneira melhor de fazer isso
  • Esses caracteres de espaço são a forma de transformar espaços, que antes não eram diferentes de quaisquer outros caracteres, em espaços de fato
    Não consigo pensar em uma forma de fazer isso sem que, em algum momento, um espaço literal ganhe significado desse jeito
• Falam da "armadilha de ter alguma forma de sintaxe", mas sintaxe fornece estrutura
  Você acha que consegue ler uma frase como "sentence this without you syntax read can" sem sintaxe?
  Embora Cognition use uma antissintaxe totalmente pós-fixa, pós-fixa também é sintaxe
  Basta perguntar a um falante de alemão sobre verbos no fim da frase
  Mesmo no primeiro exemplo, a ordem de operandos e operadores é importante, e isso é justamente sintaxe
  Isso parece uma tentativa de criar uma linguagem absurdamente compacta, e me lembra muito APL
  Uma dica para os autores: vocês não eliminaram a sintaxe; apenas a tornaram difícil para humanos lerem e entenderem, e legibilidade e compreensibilidade são fatores importantes em programação
• Foi um pouco difícil de ler
  Parecia que as regras mudavam constantemente sob meus pés, com regras e palavras sendo introduzidas e depois redefinidas de forma arbitrária
  No geral, há uma vibe meio Numberwang, o que parece ser uma das razões pelas quais isso soa como sátira
  Outro grande motivo é que a etapa de bootstrapping foi escrita de um jeito ridiculamente cômico, mas isso parece intencional
  Claramente há algo profundo ali, mas vou ter que reler depois de tomar um café mais forte
  • Há muita coisa a explicar, e também acho que talvez a forma atual de explicação não tenha sido a ideal
    Sou o autor do texto, e o problema é que há realmente muito conteúdo a transmitir
    Eu e Matthew passamos 3 semanas trocando ideias por várias horas todos os dias sobre o design dessa linguagem, e também há muito contexto que precisa ser preenchido para pessoas que não me conhecem de fato