quinta-feira, 16 de setembro de 2010

Dia do Programador 2010: Brainfuck


import datetime
x = datetime.date(2010, 1, 1)
y = datetime.date.today()
if (y - x).days == 256:
    print("Feliz Dia do Programador, via #tocadoelfo!")

u_time hora_postagem = 1284627900;

E mais um Dia do Programador chegou e deixei passar, como sempre e aqui estou para dedicar esse dia aos meus amigos, colegas e a mim mesmo. Então, vamos lá.

Dia 13/09 foi comemorado o dia do Programador. O Dia do Programador é uma data festiva no 256º dia do ano, celebrada por programadores de computador em boa parte do mundo. Este número foi escolhido porque é o maior número que pode ser representado por um byte (oito bits). Além disso, esse número é a maior potência de dois que é menor que o número 365 (o número de dias do ano, duh). Também pode ser representado, em hexadecimal como 0x100 e em octal como 0400.

O Dia do Programador é dia 13 de setembro, exceto em anos bissextos, nos quais ele é comemorado no dia 12 de setembro, pois esse é o 256º dia do ano bissexto.

Meu dia do Programador

Conforme tinha dito ano passado, eu tinha prometido mostrar o código-fonte de minha mais não tão nova linguagem baseada em Brainfuck, chamada T+ (T Plus). Sabe, nunca terminei efetivamente de mexer nela, pq saempre acho que algo deveria ser diferente. O que vocês podem ficar sabendo dela é que ela usa duas pilhas para simular o mecanismo de fita e uma pilha extra, para permitir operações de pilha. Enquanto Brainfuck é equivalente à uma máquina de Turing, T+ é a mesma máquina, só que com uma pilha de memória adicional.

No entanto, não vim aqui para falar da linguagem T+, até porque ainda não decidi uma série de fatores. Eu vim para falar de Brainfuck...




Como diz a Wikipédia:

brainfuck (também conhecido como brainf*ck, ou BF) é uma linguagem de programação esotérica notada pelo seu extremo minimalismo, criada por Urban Müller, em 1993. Ela é uma linguagem Turing completa, desenhada para desafiar e confundir os programadores, e não é útil para uso prático. Pela sua simplicidade, o desenvolvimento de compiladores e interpretadores para essa linguagem é muito mais fácil do que para outras linguagens. O nome da linguagem é geralmente não-capitalizado, apesar de ser um substantivo próprio.


A linguagem em si é simples. Ela implementa uma máquina turing de fita, que constitui de um ponteiro de instrução, um array de pelo menos 30.000 células (de acordo com o criador da linguagem) um ponteiro de dados e dois canais de dados, para receber e enviar dados (em C: stdin e stdout).

Os comandos que a linguagem reconhece são os seguintes:

  1. >: Incrementa o ponteiro de dados (move para a direita);
  2. <: Decrementa o ponteiro de dados (move para a esquerda);
  3. +: Incrementa o byte armazenado na célula apontada pelo ponteiro de dados;
  4. -: Decrementa o byte armazenado na célula apontada pelo ponteiro de dados;
  5. .: Imprime o byte armazenado na célula apontada pelo ponteiro de dados;
  6. ,: Lê um byte da entrada (stdin) e armazena na célula apontada pelo ponteiro de dados;
  7. [: Se o byte armazenado na célula apontada pelo ponteiro de dados for zero, em vez de o ponteiro de instrução se mover para a próxima instrução, ele salta para a instrução após o comando "]" correspondente;
  8. ]: Se o byte armazenado na célula apontada pelo ponteiro de dados for diferente de zero, em vez de o ponteiro de instrução se mover para a próxima instrução, ele salta para trás, para a instrução após o comando "[" correspondente.


Como exemplo de programa escrito em Brainfuck, vamos demonstrar o velho e já clássico Hello World:

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.


Como vc pode ver, não é fácil entender o que o programa faz só olhando assim né? Bom, o Brainfuck têm uma característica interessante: Todos os caracteres que não fazem parte da linguagem são ignorados. Isso nos permite poder escrever código com comentários sem nenhuma necessidade de sintaxe especial e em qualquer parte do programa. Vejamos agora uma versão do mesmo programa, com comentários:

+++++ +++++ inicializa um contador para o laço de repetição (célula #0) com o valor 10
[ usa o loop para definir o valor das próximas quatro células com os valores 70, 100, 30 e 10
> +++++ ++ adiciona 7 à célula #1
> +++++ +++++ adiciona 10 à célula #2
> +++ adiciona 3 à célula #3
> + adiciona 1 à célula #4
<<<< - decrementa contador (célula #0)
]
> ++ . imprime 'H'
> + . imprime 'e'
+++++ ++ . imprime 'l'
. imprime 'l'
+++ . imprime 'o'
> ++ . imprime ' '
<< +++++ +++++ +++++ . imprime 'W'
> . imprime 'o'
+++ . imprime 'r'
----- - . imprime 'l'
----- --- . imprime 'd'
> + . imprime '!'
> .


Bom, eu gosto da linguagem, apesar de não conseguir escrever programas de maneira efetiva nela. Eu gosto dessa área de compiladores, e entender como ela funciona foi meu objetivo primário quando fiquei sabendo dela.

Dentre algumas coisas que aprendi a fazer foi operações básicas. Como o array de dados usa células com valores inteiros, nada mais justo que descobrir como fazer operações aritméticas com brainfuck. Vou citar primeiro as minhas conclusões e descobertas (e suas respectivas representações) e depois alguns recursos úteis que você pode aplicar em seus códigos:

Minhas Descobertas:

Limpando uma célula: {x} -> {0}
[-]

Movendo um valor: {x, 0} -> {0, x}
[->+<]

Copiando um valor: {x, 0, 0} -> {x, x, 0}
[->+>+<<]>>[-<<+>>]<<

Fazendo soma: {x, y} -> {0, x+y}
[->+<]

Fazendo subtração: {x, y} -> {0, x-y}
>[-<->]<

Fazendo multiplicação: {x, y, 0, 0} -> {0, y, x*y, 0}
[->[->+>+<<]>>[-<<+>>]<<<]

Fazendo exponenciação: {x, y, 0, 0, 0} -> {x, 0, x**y, 0, 0}
>>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]<

Fazendo divisão: {x, y, 0, 0, 0, 0} -> {x/y, x%y, 0, 0, 0, 0}
[>[->+>+<<]>[-<<-[>]>>>[<[-<->]<[>]>>[[-]>>+<]>-<]<<]>>>+<<[-<<+>>]<<<]>>>>>[-<<<<<+>>>>>]<<<<<
Obs.: Quando y é igual a zero, o código entra em looping infinito.

Funções úteis:

Limpando a célula atual e todas as anteriores
[[-]<]

Lendo e imprimindo na tela
,[.,] ou ,+[-.,+] ou ainda ,[.[-],]

Fazendo uppercase
,----------[----------------------.,----------]

Fazendo buscas
Para frente: -[+>-]+
Para trás: -[+>-]+
Nesse exemplo, o código procura por uma referência de valor 1. Para procurar por referências a outros números, aumente o número dos + e - na quantidade do número. Ex.:
5: -----[+++++>-----]+++++

Exemplos de compiladores e interpretadores

Como não podia deixar de falar, existem centenas de compiladores e interpretadores de Brainfuck por aí. Uma simples busca pelo Google retornará versões para várias linguagens, inclusive interpretadores de Brainfuck escritos em Brainfuck!

Eu tenho aqui três exemplos que implementei durante meus estudos com a linguagem:
  • bf_gerador_codigo.c: Um gerador de código escrito em C que, na verdade, converte o programa em Brainfuck para uma versão em C
  • bf_interpretador.c: Um interpretador escrito em C;
  • bf_python.py: Um gerador de código escrito em Python, que converte para Python e que também é um interpretador.


Se você quiser testar, pode entrar no Javascript Brainfuck Interpreter / Debugger. Muito bom o site, pois te permite acompanhar passo-a-passo a execução do código.

T Plus - A variação de Brainfuck com suporte a uma pilha extra de dados

Como falei no começo do post, a minha linguagem derivada de Brainfuck ainda não está pronta por pura preguiça dessa pessoa que vos escreve. No entanto, pelo menos a definição da linguagem já está especificada. A linguagem usa os mesmos oito operadores do Brainfuck para fazer as operações na fita, e também têm operadores adicionais para interagir com a pilha. Os comandos são os seguintes:

  1. ): Adiciona o valor da célula corrente no topo da pilha (push);
  2. (: Retira o valor do topo da pilha e coloca na célula corrente (pop). Uma pilha vazia retorna zero;
  3. @: Pega o valor do topo da pilha e coloca na célula corrente (peek);
  4. #: Remove o valor do topo da pilha, sem adicionar na célula corrente (drop);
  5. =: Define o valor da célula como a soma do seu valor anterior com o valor do topo da pilha (peek);
  6. _: Define o valor da célula como a diferença do seu valor anterior com o valor do topo da pilha (peek);
  7. }: Desloca os bits do valor da célula corrente para a direita pelo valor do topo da pilha (peek);
  8. {: Desloca os bits do valor da célula corrente para a esquerda pelo valor do topo da pilha (peek);
  9. |: Define o valor da célula com o resultado da operação lógica OR, do seu valor anterior com o valor do topo da pilha (peek);
  10. &: Define o valor da célula com o resultado da operação lógica AND, do seu valor anterior com o valor do topo da pilha (peek).


Então, essa é a minha linguagem, T+ (T Plus). Há uma série de coisas que ainda preciso decidir sobre a sua gramática, de forma a não acontecer o que aconteceu com o Brainfuck, onde definições como a forma que o array de dados é iniciado fizeram com que a linguagem tivesse algumas variações que dificultam a portabilidade do código ou se permito o uso da pilha para armazenar uma determinada posição do ponteiro de programa (e permitir um funcionamento similar ao goto). Tudo isso ainda está por ser decidido, antes que eu realmente implemente a linguagem.

Conclusão

Uma das coisas legais da linguagem Brainfuck é que ela é uma linguagem Turing Completa, ou seja, implementa uma Máquina de Turing, o que significa que qualquer problema recursivamente enumerável pode ser resolvido usando a linguagem.

Bom, é isso. Apesar do atraso, estou postando meu post para o Dia do Programador! Felicidades para todos, e espero que este post tenha sido legal, intuitivo, didático e que vocês tenham aprendido algo com ele.

Referências:

Wikipédia em Português:
http://pt.wikipedia.org/wiki/Dia_do_Programador
Desciclopédia:
http://desciclo.pedia.ws/wiki/Brainfuck
Brainfuck, na Uncyclopédia:
http://uncyclopedia.wikia.com/wiki/Brainfuck
Exemplos de programas em Brainfuck:
http://esoteric.sange.fi/brainfuck/bf-source/prog/