Paulo Henrique Rodrigues Pinheiro

Um blog sobre programação para programadores!

Suporte a loops aninhados em meu interpretador BrainFuck

Continuando o projeto de fazer um interpretador brainfuck em GO

Gopher

O Problema

É algo simples, "eu já tinha pensado nisso", mas não me animava a implementar. Se temos loops aninhados, precisamos de um tratamento especial. Eis um exemplo:


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

E finalmente tomei coragem para fazer essa implementação. Na tag 0.0.4, eu tentei resolver isso implementado um stack, mas claro que não deu certo. Como eu sei quando um ] é relativo ao [ em que estou? Esse era o problema que eu estava ignorando.

Aqui um diff completo em relação ao último texto.

Nem só isso

Uma importante alteração foi o controle sobre o valor do ponteiro de memória. Eu não tinha feito nada para controlar underflow ou overflow, até que me deparei com códigos que funcionam como se não houvesse amanhã!


if l.pos < 0 {
        l.pos = len(l.memory) - 1
} else if l.pos >= len(l.memory) {
        l.pos = 0
}

Não importa o que se faça, sempre se estará apontando para uma região válida da memória.

Também resolvi imprimir o caractere correspondente ao número armazenado, para pode rodar os programas BF que tem por aí e comparar a saída:


 func main() {
@@ -84,7 +107,7 @@ func main() {
                '<': func(l *Language) { l.pos-- },
                '+': func(l *Language) { l.memory[l.pos]++ },
                '-': func(l *Language) { l.memory[l.pos]-- },
-               '.': func(l *Language) { fmt.Println(l.memory[l.pos]) },
+               '.': func(l *Language) { fmt.Print(string(l.memory[l.pos])) },
                '[': func(l *Language) { open_bracket(l) },
                ']': func(l *Language) { close_bracket(l) },
        }

O interessante aqui é a função string, que eu estava procurando sem saber que existia :).

Finalmente

Foram implementados os cuidados para quando se depara com um [:


func open_bracket(l *Language) {
    if l.memory[l.pos] != 0 {
        return
    }

    for depth := 1; depth > 0; {
        l.instruction++

        instruction := l.source[l.instruction]
        if instruction == '[' {
            depth++
        } else if instruction == ']' {
            depth--
        }
    }
}

Se o valor na posição corrente de memória for zero, nem entramos no loop, procurando seu final.

E quando se depara com um ], eis os cuidados:


func close_bracket(l *Language) {
    for depth := 1; depth > 0; {
        l.instruction--
        instruction := l.source[l.instruction]
        if instruction == '[' {
            depth--
        } else if instruction == ']' {
            depth++
        }
    }
    l.instruction--
}

Simplesmente procuramos o [ correspondente, onde a verificação do loop está.

As ideias para a busca dos limitadores de loop foram copiados dessas implementações:

Torture Tests para seu interpretador BF podem ser encontrados nesse link.

O Futuro

Está quase no ponto em que essa série deixará de ser sobre GO e o mais importante será a linguagem BF. Algumas coisas que pretendo resolver logo: