Linguagem de programação em que toda expressão faz sentido

Por recomendação, estou reeditando isso no Stack Overflow .

Recentemente, estive pensando sobre a questão seguinte.

Considere o código para um "Olá, mundo!" programa:

main()
{
    printf("Hello World");

}

Agora, quase qualquer alteração nesse código o tornará completamente inútil; na verdade, quase todas as alterações impedirão a compilação do código. Por exemplo:

main(5
{
    printf("Hello World");

}

Agora para a pergunta real. Existe uma linguagem de programação em que toda combinação possível de símbolos - ou seja, toda expressão - faz sentido? Tentei pensar em algum tipo de solução e criei duas:

1. Postfix com um número limitado de variáveis. Basicamente, todas as variáveis ​​já estão definidas antes de você escrever qualquer código e precisar trabalhar apenas com elas. Teoricamente, é possível executar um número arbitrário de operações, formando uma cadeia de muitos programas simples, cada um deles fornecendo resultados a outros. O código pode ser escrito como uma série de caracteres na notação postfix;

2. "Postfix" com uma pilha de variáveis. Variáveis ​​são armazenadas em uma pilha; toda operação pega duas variáveis ​​do topo e coloca o resultado em seu lugar. O programa termina quando atinge a última operação ou variável.

Pessoalmente, eu odeio os dois. Não são apenas limitados, são deselegantes. Eles nem são soluções reais, mais como soluções alternativas, essencialmente "terceirizando" alguns trabalhos para um processo externo.

Alguém tem outra idéia de como resolver esse problema?

O Redcode, a linguagem assembly por trás das codewars, foi explicitamente escrito para ter muito poucas instruções de interrupção, porque o código geralmente é mutilado antes de finalmente ser liberado, e quanto mais oportunidades ele tiver que parar, menos interessante é o jogo.

Você vê muito poucas linguagens na prática porque não queremos apenas que um programa seja executado, queremos que ele seja executado da maneira que esperamos. Se você pode digitar um erro de digitação e alterar a forma como o programa foi executado, ele deve estar razoavelmente próximo do comportamento esperado original, ou os programadores devem sentir frustração.

Há alguma precedência para essas coisas usando linguagens naturais em vez de linguagens formais, mas não é o que eu chamaria de um campo grande quando você o compara ao uso de linguagens formais. Se você estiver interessado em tais linguagens de programação, a comunidade de processamento de linguagem natural é onde eu procuraria.

Outro campo que você pode olhar é a genética. Há notavelmente poucas seqüências genéticas que são simplesmente inválidas. Muitos deles que não são muito eficazes em reproduções, mas muito poucos inválidos.

A idéia de uma máquina de Turing universal usa exatamente essa "linguagem de programação": uma codificação de máquinas de Turing como números naturais, representados, por exemplo, em binário, de modo que todo número natural denota uma máquina de Turing, ou seja, programa. Nesta linguagem, toda seqüência de zeros e uns é um programa.

Se você está preocupado que alguns números possam codificar programas inválidos, isso pode ser evitado da seguinte maneira. Imagine escrever todas as seqüências de caracteres no conjunto de caracteres da sua linguagem de programação (digamos, Java), em ordem lexicográfica, começando com as de comprimento um, depois duas, depois três, ... Em seguida, crie uma nova linguagem de programação deixando o número representa o$n$$n$ ésima string na lista que é um programa Java válido. Na nova linguagem de programação, os programas são apenas números naturais e todo número natural é um programa válido.

Tenho certeza de que também existem linguagens de programação esotérica em que toda string é um programa; no entanto, se você está apenas pedindo uma lista dessas, acho que sua pergunta está fora de tópico aqui.

Estender uma linguagem de programação para que toda expressão faça sentido é sempre possível, mas não interessante. Por exemplo, você pode apenas atribuir o significado "não fazer nada" a qualquer expressão que o idioma original rejeite.

Projetar uma linguagem de programação em que cada expressão faça sentido da maneira que você pode executá-la não é particularmente útil. Uma boa linguagem de programação não é apenas aquela em que um macaco pode digitar em um teclado e escrever um programa válido, mas uma linguagem em que um programador pode escrever facilmente o programa que pretendia escrever. Escrever programas válidos não é a parte difícil da programação: a parte difícil é escrever um programa que executa o que era esperado dele. Rejeitar programas obviamente incorretos é muito útil nesse sentido.

Outra maneira de resolver isso é definir totalmente a semântica de todas as entradas possíveis, incluindo a especificação de qual erro de tempo de compilação, tempo de carregamento ou tempo de execução deve ser gerado para cada entrada, se houver. Ou seja, “abortar o programa após a impressão Syntax error at line 42no fluxo de erro padrão” faz parte da semântica definida do idioma. Toda expressão "faz sentido", pois tem um significado definido. Esse é um significado útil? Talvez - afinal, se o programa estiver obviamente errado, rejeitá-lo é útil.

Confira Jot , uma linguagem completa de Turing baseada na lógica combinatória, em que cada sequência de 0s e 1s (incluindo uma sequência vazia) é um programa válido.

Um bom exemplo é o espaço em branco . No idioma apropriado, qualquer combinação de operadores é válida. Os operadores são espaço, tabulação e nova linha (especificamente "\ n"). Todos os outros caracteres são considerados comentários .

Esta resposta e, de fato, sua pergunta (assim como toda a página da web) são exemplos de programas em branco válidos (embora eles não façam nada de particularmente interessante).

Gostaria de abordar a idéia que muitos pôsteres deram, de que essa linguagem seria "inútil". Talvez fosse inútil para os humanos escreverem manualmente, com a intenção de resolver alguma tarefa em particular. No entanto, apesar de ser um caso de uso majoritário para linguagens de programação, esse certamente não é o único caso de uso. Vários casos de uso vêm à mente onde esse idioma é útil, e podemos procurar nesses campos exemplos de tais idiomas.

Em primeiro lugar alusão de Cort Amom, a genética está no local: a transformação do programa em questão (substituindo )a 5) pode ser visto como uma mutação . Esse tipo de manipulação é comum no campo da computação evolutiva ; em particular, algoritmos genéticos realizam essas transformações em strings , enquanto a programação genética transforma programas . Em ambos os casos, geralmente queremos atribuir significado a todas as possibilidades, pois isso produzirá o espaço de pesquisa mais compacto.

Algoritmos genéticos dependem de algum tipo de função de avaliação para strings; se usarmos um intérprete de linguagem de programação como nossa função de avaliação, teremos um cenário em que uma linguagem de programação que atribui significado a todas as seqüências possíveis é útil. Na programação genética, supõe-se que nossa função de avaliação seja um intérprete de linguagem de programação, mas podemos escolher várias representações para nossos programas; por exemplo, muitos sistemas operam em árvores de sintaxe abstrata. Se escolhermos cadeias de caracteres como nossa representação, recuperaremos o mesmo cenário dos algoritmos genéticos.

Outra situação em que podemos querer que cada string seja um programa válido é quando enumerar programas. Isso está relacionado à bijeção mencionada por CodesInChaos, mas podemos preferir operar em strings em vez de números naturais por vários motivos:

• Se houver alguma estrutura no idioma, por exemplo. podemos atribuir significado a sub-strings; isso pode ser perdido ao traduzir para números naturais. Nesse caso, podemos preferir usar strings, para raciocinar e transformar sub-strings localmente, em vez de representar o programa inteiro como um número. Isso é análogo ao modo como podemos preferir usar operações bit a bit em expressões int em vez de aritméticas, quando cada bit tem um significado individual. Isso é basicamente uma generalização do cenário evolutivo.
• Podemos querer gerar os programas sob demanda; por exemplo, podemos começar a executar um programa que é completamente indeterminado e gerar apenas (por exemplo, aleatoriamente) as instruções individuais (por exemplo, caracteres) quando / se o ponteiro da instrução os alcançar. Isso é comum na teoria algorítmica da informação, onde o programa é uma fita da máquina de Turing e o objetivo é caracterizar o comportamento de programas gerados aleatoriamente. Por exemplo, podemos formular Solomonoff antes de cadeias arbitrárias como a probabilidade de uma máquina universal de Turing com uma fita aleatória produzir essa cadeia.

Em termos de exemplos de linguagens, muitos sistemas de computação evolutiva são baseados em linguagens de pilha como a família Push . Eles tendem a permitir fluxos arbitrários de tokens (que poderíamos representar como caracteres individuais). Às vezes (como no exemplo Brainfuck de BrainSlugs83), existem restrições ao equilibrar parênteses; no entanto, podemos relacionar isso a programas auto-delimitantes , pois uma string como [pode não ser um programa válido , mas é um prefixo de programa válido . Se imaginarmos um compilador / intérprete lendo o código-fonte do stdin, ele não rejeitará uma string como [, simplesmente esperará por mais informações antes de continuar.

Idiomas como Lógica Combinatória Binária e Cálculo Lambda Binário surgiram diretamente do trabalho sobre a teoria da informação algorítmica, por exemplo. de http://tromp.github.io/cl/cl.html

Esse projeto de um computador universal minimalista foi motivado pelo meu desejo de apresentar uma definição concreta da Complexidade de Kolmogorov, que estuda a aleatoriedade de objetos individuais.

Linguagens de programação reais devem transmitir significado às pessoas , não aos computadores. Como muitos textos divertidos, com letras aleatoriamente embaralhadas flutuando ao redor do programa, as pessoas podem ler palavras sem sentido e fazer sentido com isso, mesmo sem perceber abertamente a confusão. Basta pensar em como é difícil encontrar erros de digitação e outros erros nos textos.

Uma linguagem de programação como a que você solicita faria as pessoas entenderem o que elas querem ler, não o que está escrito. A depuração em idiomas onde há um conjunto limitado de declarações legais, onde não há muita ambiguidade possível, já é bastante difícil. Boas línguas reduzem possíveis interpretações devido, por exemplo, a símbolos ou erros de transposição. As línguas naturais também são notórias por sua redundância, pelo mesmo tipo de razão.

Na linguagem de programação Brainfuck , quase todas as expressões binárias possíveis podem ser interpretadas como um programa. - Ou seja, você pode pegar um programa completamente bom, digitar um monte de lixo e ainda assim pode ser compilável / interpretável sem problemas.

( Edit: Acontece que você precisa coincidir com a abertura e o fechamento de colchetes, mas, caso contrário, o exposto acima é verdadeiro.)

Isso é alcançado por meio desses dois métodos simples:

1. Todos os comandos que ele entende são de um único byte (no BF, todos são caracteres ASCII únicos, por exemplo *).

2. Todos os personagens que não entende, descartam como comentários.

A linguagem de programação é Turing completa (ou seja, pode fazer qualquer coisa que qualquer outra linguagem).

*: Acontece que nem todos os comandos BF são um único byte ASCII - ou seja, os colchetes DEVEM corresponder - assim como o idioma não atende aos primeiros critérios. - Mas qualquer linguagem que atenda a ambos os critérios atenderia ao que o OP está pedindo.