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

23

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?

user1561358
fonte
48
Dado um compilador , crie um novo compilador , que funciona da seguinte forma: dada fonte , passá-lo para . Se está satisfeito com ele e produz um executável, é isso, mas se reclama, emite um executável que imprime O compilador aceita todas as strings como um programa válido. C ' s CCCsCC C 'CCYou are a bimbo.C
Andrej Bauer
1
O BF precisa de [ ]comandos correspondentes (de acordo com a página da Wiki). Meu pensamento era olhar para os opcodes da CPU. Mas, mesmo assim, alguns padrões podem gerar um problema (por exemplo, se um código de operação é de 3 bits, mas seu programa é de apenas 2 bits.) Exceto por esse problema de possível preenchimento com 0 bits extras, pode-se pensar em qualquer CPU com um conjunto completo de opcode que satisfará a reivindicação "toda string é um programa válido". Talvez sem sentido, mas ainda válido.
Ran G.
1
Deixe seu hardware ser uma CPU Z-80 com 64k de RAM. Escreva um compilador que simplesmente copie o código-fonte codificado em ASCII na memória de 64k (truncamento ou preenchimento zero, se necessário). Este compilador nunca fornece um erro de sintaxe.
Ben Crowell
1
@Tocou. Um 'compilador' que processa qualquer fluxo de bits e o corrige como um código de objeto válido para o processador fornecido, acho, atenderia aos requisitos dos OPs. Provavelmente não seria terrivelmente difícil, mesmo para sistemas com conjuntos de instruções complexos como o x86. Li um artigo anos atrás sobre a validade de bytes aleatórios como programas x86 e ele descobriu que o x86 era realmente muito mais robusto do que os autores originalmente esperavam.
Otakucode
2
Sem outras condições, essa pergunta é chata: o comentário de Andrej e a resposta de David dão respostas "triviais". Você precisa definir com mais precisão o que deseja.
Raphael

Respostas:

31

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.

Cort Ammon - Restabelecer Monica
fonte
1
A genética não parece ser um bom exemplo. Em termos de válido ou inválido, você está apenas falando sobre replicação? Porque é claro que toda string será um programa válido para um idioma em que a única instrução possível é replicate this string. Porém, não é realmente uma linguagem de programação significativa, pois não está nem perto do Turing Complete.
tel
2
@tel: Cort provavelmente está falando sobre síntese de proteínas via mRNA, ao invés de replicação. Praticamente qualquer sequência genética pode ser transcrita e, em seguida, colocada no mecanismo de síntese protéica: se a proteína que sai é suficientemente estável e que ainda não se degradou no momento em que foi construída e, em caso afirmativo, se faz algo útil para o organismo, é outro assunto ...
Steve Jessop
3
O código genético não é um código para se reproduzir. É (geralmente) um código para uma proteína. Se a proteína é útil é frequentemente uma questão diferente. Claro que fica mais interessante. Alguns bits de "código" em uma sequência genética acabam sendo mais como uma instrução ao longo das linhas de "esse código algumas linhas abaixo - você às vezes deve ignorá-lo". Há todo tipo de "programas" legais que células e vírus têm escrito lutando entre si.
Joel
O TECO é outro exemplo do mundo real.
Cjm 23/10/2015
1
@cjm wow. "Uma API é finalizada não quando você termina de adicionar tudo, mas quando termina de remover tudo." A menos que você seja TECO, então você termina quando fica sem caracteres para atribuir significado.
Cort Ammon - Restabelece Monica
16

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 onnn é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.

David Richerby
fonte
13

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.

Gilles 'SO- parar de ser mau'
fonte
12

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.

Petr Pudlák
fonte
2
Esta não é uma resposta da ciência da computação .
Raphael
2
@Abdulrhman É simples definir uma bijeção entre cadeias binárias e números naturais. Assim, você pode codificar qualquer programa como um número natural, se desejar.
CodesInChaos
7
@Raphael Por favor, elabore, ou sugira uma melhoria da resposta, teremos prazer em melhorá-la se você fornecer motivos para sua crítica.
Petr Pudlák 23/10/2015
+1, eu estava prestes a dar uma resposta semelhante para uma linguagem de programação fictícia baseada em números naturais, mas isso é semelhante. AFAIK não existe programação (em uso prático) que possua esse recurso, mas é possível construir uma usando apenas números, digamos, onde toda combinação tem um significado (atue como operadores e também como operandos) Essa é a chave
Nikos M.
8

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).

slebetman
fonte
Eu estava pensando sobre isso depois de postar minha resposta cerebral (a sua é melhor, pois está correta), mas estou me perguntando - um programa vazio ainda é um programa? (ou seja, se esses três caracteres estiverem ausentes em todo o fluxo de arquivos). - Tipo, se meu carro estivesse faltando todas as coisas que o transformavam, ainda seria um carro?
BrainSlugs83
Esta não é uma resposta da ciência da computação . (Além disso, "toda cadeia de espaços em branco"! = "Toda cadeia de caracteres".)
Raphael
2
@Raphael: Mas cada corda possível (incluindo aqueles que contêm nenhum espaço em branco) são programas de espaço em branco válidos - note que qualquer personagem que não é um espaço em branco são simplesmente comentários na linguagem de programação whitespace
slebetman
2
@slebetman Você estava interpretando meus comentários entre colchetes muito literalmente. Eu estava falando sobre tokens de loop não pareados. Alguns problemas semelhantes no espaço em branco podem ser: retornar sem uma chamada anterior funciona? (codificado como [LF][Tab][LF]) O que acontece se você exibir uma pilha vazia? O que acontece se você pular para um rótulo indefinido? O que acontece se você definir rótulos duplicados?
CodesInChaos
7

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.

Warbo
fonte
2

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.

vonbrand
fonte
0

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.

BrainSlugs83
fonte
2
Isso não apenas não responde à pergunta, mas também não é uma resposta da ciência da computação .
Raphael
1
Você pode redefinir o idioma para lidar com eles de alguma maneira sensata. por exemplo, inserindo suportes de abertura suficientes no início do programa e fechando-os no final do programa para torná-lo equilibrado. É fácil escrever um intérprete que lide com programas como se esses colchetes existissem sem realmente reescrevê-lo. É claro que iniciar um programa de foda cerebral com um colchete de abertura é bastante inútil, pois ele ignora tudo, até o colchete de fechamento correspondente.
CodesInChaos
1
A pergunta do @Raphael the OP foi "Existe uma linguagem de programação em que toda combinação possível de símbolos - ou seja, toda expressão - faz sentido?" - minha resposta é "sim, aqui está um exemplo de um que se aproxima e aqui está a teoria por trás disso". - além de estabelecer regras exatas para uma classe de idiomas que atendam aos requisitos do OP, não tenho certeza de quanto mais espaço para a ciência existe aqui. Você pode dar um exemplo ou link para um recurso do que exatamente você espera ver aqui? -- Obrigado.
BrainSlugs83
2
David e Gilles dão respostas sobre ciência da computação. Eles exploram princípios e não dizem apenas "a linguagem X faz isso (quase)". Se você ler as respostas deles, aprenderá que as respostas da última forma também são bastante entediantes. A culpa não é sua, mas os OP - a questão (como uma questão de ciência da computação) é chata; há um falso senso de complexidade.
Rafael
Pode-se facilmente "consertar" o BF para que qualquer string seja aceita: você apenas finge que há ]caracteres suficientes no final da fonte para corresponder a todos os [s sem correspondência e suficiente [no início para corresponder a todos os sem correspondência ]. A semântica de [e ]pode ser facilmente alterada para torná-los equivalentes a isso. (por exemplo, se não houver correspondência ], [apenas interrompa a execução se o byte no ponteiro de dados for zero. ]apenas pula para o início do programa em uma situação semelhante.) O idioma resultante seria Turing completo e aceitaria qualquer string.
Nathaniel