? ? ? ? 在前言中我們提到了一種語言，brainfuck。接下來的幾篇里，我們將詳細介紹這種語言，并使用其進行結(jié)構(gòu)化編程。

背景

????????1993年，一個叫做FALSE的Esolang出現(xiàn)了，它是圖靈完備的，而且最初的編譯器只有1024個字節(jié)。這種語言影響了后來的許多Esolang，比如Befunge和我們今天要談到的brainfuck。

????????同樣是在1993年，Urban Müller發(fā)現(xiàn)了這個編譯器極小的語言后，想要更上一層樓，發(fā)明一個使用更小體積編譯器的語言。于是一個只需要240字節(jié)的編譯器橫空出世。后來Brain Raiter更是寫出了一個只需要171字節(jié)的編譯器。[3]

????????這種語言是圖靈完備的。事實上，現(xiàn)在證明圖靈完備的方法之一就是寫出一個brainfuck解釋器(就是不知道這種方法學(xué)不學(xué)術(shù)……)。

????????Müller將其命名為brainfuck。然而，由于眾所周知的原因，該語言的名稱常被隱去，取而代之的是brainf*ck、bf、brainoof等等。如果要中文翻譯的話，腦操真的挺適合的，不管是直譯還是意譯。

????????Brainfuck，官方建議是除了句子開頭以外全部用小寫，不過大寫問題也不大。

語言概述

? ? ? ? Brainfuck基于這樣一臺機器。它具有一列初始化為0的數(shù)組（數(shù)組長度最初要求是30,000，但這個標準不是必要的）和一個初始指向第一個元素的指針。

? ? ? ? 該語言總共只有8個命令><+-.,[]

????????以下是每一個命令的含義以及對應(yīng)的C語句（p是一個char*）：

解釋器

? ? ? ? fatiherikli寫了一個解釋器，擁有27個上限為255的存儲單元，運行代碼時可以看到當前運行命令和各個單元的數(shù)值。

? ? ? ? 網(wǎng)址：http://fatiherikli.github.io/brainfuck-visualizer

????????這里還有一個解釋器，支持負的數(shù)組下標，數(shù)組長度也不只局限于27，但是沒有過程顯示。

????????網(wǎng)址：https://tio.run/#brainfuck#

? ? ? ? 還能搜到其他一些解釋器。而且由于brainfuck本身不難，寫一個解釋器也不是什么難事。在學(xué)Brainfuck的時候，開個解釋器很有必要。與之同樣必要的還有ASCII碼表，除非你已經(jīng)背下來了。

輸出Hello， World！

????????當拿到一種新的語言時，作為慣例，第一個程序永遠是打印一個Helloworld。不過在那之前，我們先了解一些知識。

????????首先，如何用BF換行？

????????需要注意的是，BF標準規(guī)定換行符使用'\n'(10)而非'\r'(13)，所以現(xiàn)在我們需要輸出一個10。我們使用+和.兩個命令

++++++++++.

????????這樣我們就成功換行。

????????但接著問題就來了，如果我要打印一個'A'(65)怎么辦？寫65個+？估計這樣的話鍵盤磨損很快吧（當然如果你用程序輸出程序當我沒說）

????????這種時候，我們就需要使用乘法了。65=8*8+1，而乘法可以使用循環(huán)寫，我們再引入其他幾個命令。

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

????????看這個程序，其先將當前位置加8，然后循環(huán)運行右移加8左移減1直到左側(cè)單元為0，然后右移加1，就獲得了65。這實際上就是將8加8次然后加1。用類似的方法可以大大壓縮程序大小。

????????有了這些知識儲備，我們就可以寫一個輸出"Hello, World!"的程序了

++++++++[>+++++++++<-]>.>>++++++++++[<++++++++++>-]<+.+++++++..+++.>>++++[<+++++++++++>-]<.------------.<<<+++[>+++++<-]>.>.+++.------.--------.>+.(147)

????????括號里就是整個程序的長度，如你所見，這是很簡單的。

????????但是，brainfuck之所以被稱為腦操，不僅是因為它的直譯，還因為這玩意兒就像智力游戲一樣，極度耗腦子。用BF的人們以壓縮程序長度為樂，而有時候極度困難的。比如說，下面就是一個更短的輸出"Hello, World"的bf程序。

++++++++[>++++[>++>+++>+++>+>+<<<<<-]>+>+>->+[<]<-]>>.>---.+++++++..+++.>>++++.>.<<-.<.+++.------.--------.>>>+.(112)

????????這程序比起上面我寫的看起來就有點復(fù)雜了。沒事，咱們一點一點分析

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

   這一段話結(jié)束后從第二個元素開始會是0 8 12 12 4 4，指針在第二個元素上

2. >+>+>->+

   這段話結(jié)束后是0 9 13 11 5 4

3. [<]

   向左移到第一個為0的元素，即第二個元素

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

   將8乘上上述數(shù)列，結(jié)果從第一個元素開始為0 0 72 104 88 40 32

5. >>.>---.+++++++..+++.>>++++.>.<<-.<.+++.------.--------.>>>+.

   然后分別加上或減去偏移量輸出。

? ??????實際上，如果我們放寬限制，或者考慮上BF的其他特性，我們還能得到更短的程序。

????? ? 比如，如果元素的值沒有范圍限制且允許負數(shù)，那么我們可以寫出如下程序[4]

(>>>>>>>>>>>>>>>>)+[+[<<<+>>>>]+<-<-<<<+<++]<<.<++.<++..+++.<<++.<---.>>.>.+++.------.>-.>>--.(76(92))

--->->->>+>+>>+[++++[>+++[>++++>-->+++<<<-]<-]<+++]>>>.>-->-.>..+>++++>+++.+>-->[>-.<<](87)

????????第一個程序使用了負的數(shù)組下標，長度旁邊括號里的數(shù)字是加上最開始移位后程序的長度。

????????再比如，如果我們規(guī)定超出0~255范圍的數(shù)字需要取模255（這實際上是大部分解釋器規(guī)定的），我們還有如下三個程序。[4][5]

(>>>>)--<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.+.>>.>>.<<<.+++.>>.>>-.<<<+.(78(82))

(>)-[++[<++>->+++>++<<]---->+]<<<<.<<<<-.<..<<+.<<<<.>>.>>>-.<.+++.>>.>-.<<<<<+.(78(79))

(>>>>>)+[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++[.>]<<<<.+++.------.<<-.>>>>+.(72(77))

????????不過上面兩個程序?qū)嵲谑沁\行時間太久了，所需的數(shù)組長度也非常長。與上面兩個相比，最底下那個簡直可以稱之為優(yōu)美。它是由KSab用C++程序暴力破解出來的。這個可以在上面提到的fatiherikli的解釋器中運行，強烈建議輸進去欣賞一下。

? ? ? ? 所以BF真的挺廢腦子的，你永遠也不知道一個更簡單的程序可能會長啥樣。這可能就是BF的魅力之一吧。

參考：

[1]brainfuck - Esolang?https://esolangs.org/wiki/Brainfuck

[2]The Brainfuck Programming Language?http://www.muppetlabs.com/~breadbox/bf/

[3]Basics of Brainfuck?https://gist.github.com/roachhd/dce54bec8ba55fb17d3a#file-readme-md

[4]code golf - "Hello, World!" - Code Golf Stack Exchange?https://codegolf.stackexchange.com/questions/55422/hello-world/163590#163590

[5]code golf - "Hello, World!" - Code Golf Stack Exchange?https://codegolf.stackexchange.com/questions/55422/hello-world/68494#68494

[6]Github:ksabry/bfbrute?https://github.com/ksabry/bfbrute