Tutorial de Brainfuck

Este artigo foi arquivado. Isto significa que o artigo não será mais atualizado e pode conter erros ou omissões.

O Brainfuck (também conhecido por Brainf*ck ou por BF, devido ao seu nome polémico) é uma linguagem esotérica, cujo objetivo é “torrar cérebros” a ler o código. Mas, vão ver que depois de aprenderem toda a lógica de Brainfuck, ainda vão conseguir criar umas coisas engraçadas de forma fácil!

Um primeiro olhar

Antes de continuar a avançar “em seco”, aqui fica o típico “Hello World”:

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

No final do tutorial, vamos ver em detalhe como funciona este código. Para avançar com as explicações, é preciso que estejam familiarizados com códigos da tabela ASCII e noções básicas de apontadores (ou vetores, também serve para o efeito). Recomendo a manter estes sites abertos enquanto seguem o tutorial:

Referência para tabela ASCII: https://asciitable.com/ (ou outro site similar da vossa preferência)
Para correr os exemplos que forem colocados e testarem código vosso podem usar o Brainfuck Interpreter do Project Nayuki.

Comecem por testar o código anterior e vão obter o famoso Hello World:

Hello World!

Como funciona o Brainfuck?

No Brainfuck, como noutras linguagens, temos variáveis. As variáveis são, na verdade, uma única memória composta por células ou posições. Não há, por isso, nomes ou etiquetas que correspondam a uma variável, mas sim uma posição. Cada posiçõa irá guardar um valor numérico inteiro, que faz correspondência com um caractere da tabela ASCII (daí a necessidade de ter uma tabela com os códigos correspondentes ou então conhecê-la muito bem :-) ).

Memória: [ 65 0 89 72 ] 
Posição:   ^

Neste exemplo é possível ver que temos uma memória com 4 posições conhecidas: a primeira com o valor 65, a segunda com o valor 0, etc. Apenas é possível ler um valor de cada vez, de acordo com a posição atual. Por omissão, o programa começa na primeira posição, onde temos o valor 65. Se for mais fácil de perceber, podemos fazer uma analogia com uma lista duplamente ligada, na qual é possível aceder a uma posição à esquerda ou à direita da posição atual.

Nas próximas secções vamos ver como ler e definir valores nesta memória e como alternar entre posições.

Operadores em Brainfuck

Em Brainfuck, temos apenas 8 operadores. Tipicamente, os interpretadores de Brainfuck ignoram tudo o que não sejam estes 8 operadores, por isso o resto pode ser considerado como comentários.

Operador	Equivalente em C	Explicação
>	++p (incr. endereço)	Muda para a posição seguinte da memória
<	−−p (decr. endereço)	Muda para a posição anterior da memória
+	++(*p)	Incrementa o valor da memória na posição atual
-	−−(*p)	Decrementa o valor da memória na posição atual
.	putchar(p)	Imprime no ecrã o caractere ASCII correspondente ao valor da memória na posição atual
,	*p = getchar(p)	Lê um caractere de teclado (ou de outra fonte de input) para a posição atual
[	while(*p) {	Inicio de um ciclo while, com o valor da posição atual como guarda/condição (!= 0)
]	}	Fim de ciclo

(Tabela adaptada de http://www.muppetlabs.com/~breadbox/bf/)

Manipulação básica

Em Brainfuck, a memória tem estado, ou seja, um valor alterado ou uma posição trocada irá manter-se na próxima iteração. A ideia base de um programa em Brainfuck é guardar valores correspondentes a carateres ASCII, de forma a poder usá-los mais tarde. Vamos ver um exemplo prático:

++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
+++++
.

Usem o Brainfuck Interpreter para testar: copiem o código do exemplo para a caixa “Code”, carreguem no botão “Load” para iniciar a máquina de estados de depois no botão “Run”. Devem obter o seguinte output:

Incialmente a memória interna do programa tem este estado:

Memória: [ 0 ] 
Posição:   ^

Se consultarem a tabela ASCII, vão reparar que o caractere A maiúsculo corresponde ao inteiro 65. Segundo a tabela de operadores que já foi apresentada, o operador + (mais) serve para incrementar numa unidade (+1) o valor da posição atual da memória (inicializado internamente a zero). As 6 primeiras linhas têm 10 operadores + e a penúltima tem mais 5 operações: 65 operadores de incremento. Isto vai permitir colocar o valor 65 na primeira posição de memória, precisamente o que queremos para que apareça a letra A. No final da execução, a memória tem este estado:

Memória: [ 65 ] 
Posição:   ^

Mas é necessário mais um passo. A última linha contém o operador . (ponto), que nada mais faz que ir buscar o valor atual e imprimir o caractere correspondente. O resultado é o caractere pretendido impresso no ecrã.

Usar várias posições

Até aqui ainda só usámos a primeira posição da memória, na qual guardámos o valor. Mas como é natural, pode interessar-nos manter mais que um valor em memória. Vamos ver como usar várias posições e como alternar entre elas.

++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++.
>
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
+++++++++.
<.

Corram agora este exemplo no Brainfuck Interpreter. O output deve ser a típica expressão LOL:

LOL

É semelhante ao exemplo anterior, com a diferença que desta vez introduzimos mais dois operadores: o operador > (maior) muda para a posição à direita/seguinte; de forma inversa, o operador < (menor) muda para a posição à esquerda/anterior. Neste exemplo, são usadas 2 posições de memória. Na primeira posição é colocado o valor 76, que corresponde ao L maiúsculo em ASCII.

Memória: [ 76 ] 
Posição:   ^

De seguida imprimimos para o ecrã, com o operador . (ponto). Na 9ª linha, encontramos o operador >, que vai trocar a posição atual. Então significa que temos agora duas posições conhecidas na memória: a primeira, com o valor 76, e agora esta 2ª posição para a qual acabamos de mudar, inicializada a 0.

Memória: [ 76 0 ] 
Posição:   ^

Vamos então criar a letra O, cujo código ASCII é 79. Tal como para o L, vamos colocar nesta nova posição o valor 79 correspondente ao caractere O e imprimimos. Tal como anteriormente, chamamos tantos operadores + quanto necessários para obter o valor. Até agora temos o output:

LO

A memória está assim:

Memória: [ 76 79 ] 
Posição:      ^

Resta-nos a última letra L. Podíamos colocar novamente 76 operadores de incremento e imprimir, mas na nossa primeira posição já temos o valor que corresponde ao L maiúsculo: tudo o que temos de fazer é ir lá buscá-lo; voltamos à posição anterior do vetor com o operador <, e imprimimos o L. É tudo o que faz a última linha de código. Em termos de memória, apenas se trocou a posição atual:

Memória: [ 76 79 ] 
Posição:   ^

Tirar partido dos ciclos

O Brainfuck também tem ciclos, semelhantes ao while: vamos tirar partido deles para escrever (um pouco) menos linhas de código. Como sabemos, no ciclo while, temos uma condição que enquanto foi verdadeira, o ciclo continua. No Brainfuck, é similar: como apenas dispomos de valores inteiros, a condição de paragem de um ciclo nesta linguagem é quando a posição atual, na altura da comparação, tem o valor 0.

Para ser mais específico, vamos ter de inicializar uma posição de memória, que irá servir de guarda do ciclo, com o número de iterações que queremos que o nosso ciclo faça, e ir decrementando. A nossa condição de paragem é quando este valor da guarda chegar a zero: aí, o ciclo deixa de executar, logo interessa-nos colocar exatamente o número de vezes que queremos que o ciclo repita, e ir subtraindo até chegar a 0. Vamos voltar ao exemplo da letra A, agora com ciclos:

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

Output:

Comparando ao exemplo anterior, conseguimos poupar alguns caracteres ao usar ciclos. O objetivo é o mesmo: obter o valor 65 na primeira posição de memória.

Analisando: a primeira linha inicializa a primeira posição com o valor 6. Hã, mas não era 65 que queríamos? Sim. Mas não vai ser esta posição que vamos usar para mostrar o A. Na verdade, esta posição vai ser a condição de paragem (guarda) do nosso ciclo. Vamos então analisar o corpo do ciclo que fica entre os parênteses retos [ e ] (ou seja, o código que vai ser repetido à semelhança do ciclo while). No caso do Brainfuck, um ciclo continua até que a posição atual tenha o valor 0.

No interior do ciclo, tudo o que fazemos é trocar para a segunda posição, incrementar 11 unidades, voltar a trocar para a primeira posição e decrementar uma unidade com o operador - (menos). Esta última linha do ciclo é particularmente importante, porque é ela responsável por atualizar a condição de paragem. Na primeira iteração do ciclo, o valor da primeira posição vai passar de 6 para 5, e como 5 é diferente de 0, o código do ciclo vai ser novamente executado. E assim sucessivamente, até que o valor seja 0, e aí o ciclo termina.

Resumindo, a utilização do ciclo vai nos permitir colocar o valor 66 na segunda posição: o código do ciclo foi executado 6 vezes, e por cada vez, foram incrementadas 11 unidades na segunda posição, totalizando as 66 unidades (6 * 11 = 66). O nosso objetivo é imprimir o caractere correspondente ao valor 65, por isso, tendo o 66 na segunda posição, resta-nos trocar para a segunda posição novamente, decrementar uma unidade, e imprimir.

Um quadro resumo das iterações:

Nº Iterações ciclo	1ª posição	2ª posição
Antes do ciclo	6	0
Após 1ª	5	11
Após 2ª	4	22
Após 3ª	3	33
Após 4ª	2	44
Após 5ª	1	55
Após 6ª	0	66

Há aqui um pormenor importante: com os ciclos obtemos sempre aproximações dos números ASCII que pretendemos, com vista a diminuir o código produzido. Neste caso, usamos a aproximação de 66, para escrevermos o 65 mas, por outro lado, podíamos incrementar 13 unidades 5 vezes e ter o valor 65, e tornava-se desnecessário fazer mais uma operação de decremento. No entanto, a técnica é pegar no ciclo e obter uma aproximação ou valor exato, se possível, numa posição de memória, trocar para essa posição, incrementar/decrementar para obter o valor pretendido (se for necessário) e imprimir.

Esta é uma das estratégias para otimizar programas em Brainfuck, guardando alguns caracteres em diversas posições de memória, para depois “jogar” com operações de incremento e decremento (aproximação a vários caracteres).

Análise ao Hello World!

Conhecer ciclos, operadores de incremento e decremento, e ainda os operadores de troca de posições, é o suficiente para compreender o programa Hello World! Vejamos novamente o programa:

++++++++++
[
  >+++++++
  >++++++++++
  >+++
  <<<-
]
>++.                    # Escrever H
>+.                     # Escrever e
+++++++..               # Escrever l (2 vezes)
+++.                    # Escrever o
>++.                    # Escrever um espaço
<<+++++++++++++++.      # Escrever W
>.                      # Escrever novamente o
+++.                    # Escrever um r
------.                 # Escrever um l
--------.               # Escrever um d
>+.                     # Escrever um !

Alternando as posições de memória, e aproveitando de forma inteligente os valores que já dispomos, conseguimos minimizar os programa em Brainfuck de modo a parecerem mais simples.

Receber dados de input

Já vimos até agora 7 dos 8 operadores de Brainfuck. Falta-nos apenas falar do operador responsável pela leitura de dados, o operador , (vírgula). Este operador lê um único caractere, obtém o seu valor inteiro equivalente, segundo a tabela ASCII, e armazena-o na posição atual. O seu funcionamento depende da implementação de cada compilador/interpretador: os caracteres podem ser lidos de ficheiros, teclado, por passagem de argumentos ao programa, etc. Não vou avançar muito mais que isto, pelo que me fico por um exemplo muito simples:

,-.+.+.

Na sua essência, este programa recebe um caractere como argumento, e mostra o caractere anterior, o próprio, e o caractere seguinte, segundo a tabela ASCII. Por exemplo, se introduzirem na caixa Input do JavaScript Interpreter (antes de correr o programa) a letra D, o programa irá produzir o seguinte output:

CDE

Desafios/Exercícios de revisão

Para tornar este tutorial mais rico, resolvi adicionar dois simples exercícios para tentarem resolver e aplicarem conhecimentos adquiridos aqui e nos links de secção de referências.

Fazer um programa que imprima o alfabeto de letras minúsculas de A até Z, faça uma quebra de linha, e imprima os números de 9 até 0 (ou seja, ordem inversa de 0-9)
Dados dois caracteres como argumento, o programa deve dizer quantos caracteres de distância faz de um a outro. Por exemplo, se tivermos as letras A e C, o resultado deve ser 2; se tivermos os caracteres D e M o resultado deve ser 9. (Não esquecer que o Brainfuck apenas imprime caracteres da tabela ASCII e não valores, dica útil para apresentar o resultado). Ajuda: a distância não deve ser maior que 9 caracteres; o primeiro caratere deve ser inferior (isto é, ter uma posição menor) que o segundo.

A ideia é que tentem resolver os exercícios através deste tutorial e de alguma pesquisa. No entanto, deixo aqui propostas de resolução dos exercícios se estiverem perdidos ou para comparar com as vossas soluções.

Extensões à implementação do Brainfuck

O modelo original do Brainfuck apenas podia expandir células para a direita e tinha um limite de 30 000 bytes (30 KBytes). Porém, existem propostas de interpretadores que libertam estas restrições.

Células virtualmente infinitas sem limite de expansão

Na implementação original do Brainfuck, é usado um vetor com limite para simular a memória de células. Isto traz os limites já referidos.

No entanto podemos suprimir estes limites, gastando mais alguma memória. Se forem usadas listas duplamente ligadas, ganhamos de imediato duas vantagens:

A memória de células é expansível para a esquerda e para a direita em todas as situações
Não existe um limite de células que podemos usar (virtualmente)

O inconveniente desta solução é o aumento de memória por célula. Se, por exemplo, usarmos a linguagem C e uma máquina de 32 bits, para criar um vetor necessitamos de alocar esta quantidade de memória:

1 byte por célula (usa tipo de dados byte)
Vetor de 30000 bytes
=> 30000 células, 30 KBytes

Na solução com listas ligadas, assumindo que apenas criamos nós e estes são geridos pelo interpretador (isto é, não existe nada a indicar inicio e fim de lista; temos sempre um apontador para a célula atual), e assumindo ainda que usamos uma estrutura para o efeito, teríamos algo como:

1 estrutura nó
-> Valor (byte) = 1 byte
-> Apontador para célula anterior = 4 bytes
-> Apontador para célula seguinte = 4 bytes
Total = 9 bytes por célula
=> 30000 células, 30000 * 9 = 270 KBytes

Ou seja, para replicar a implementação original, gastaríamos 9 vezes mais memória.

Eu fiz um pequeno interpretador que implementa esta ideia, podem experimentar e consultar o código no Github (está em linguagem C e funciona em ambientes GNU/Linux): https://github.com/leplastic/brainfuck-interpreter

Notas e referências

Para finalizar este tutorial de Brainfuck, sugiro-vos alguns endereços web onde podem explorar mais sobre a linguagem, das quais recolhi muita informação para criar o artigo: