·由一段聊天记录引出的·
这几天和一个同学聊了点东西，关于一些function在BF语言下的实现
/*教学部分，熟悉BF语言的可以掠过
BF语言我个人感觉真的是世界上最好学的语言之一，因为你只要三分钟就能学会这个语言的全部，至于如何用BF语言编程，那就看你的脑袋了。
BF语言的全称叫BrainF**k，是一种极小化的计算机语言，它是由Urban Müller在1993年创建的。Müller的目标是建立一种简单的、可以用最小的编译器来实现的、符合图灵完全思想的编程语言。这种语言由八种状态构成，为Amiga机器编写的编译器（第二版）只有240个字节大小。
就象它的名字所暗示的，BF程序很难读懂。尽管如此，BF图灵机一样可以完成任何计算任务。虽然BF的计算方式如此与众不同，但它确实能够正确运行。
这种语言基于一个简单的机器模型，除了指令，这个机器还包括：一个以字节为单位、被初始化为零的数组、一个指向该数组的指针（初始时指向数组的第一个字节）、以及用于输入输出的两个字节流。*
*来自WikiPedia中文版
好了，介绍完毕，下面是基本语法：
'>' 符号表示指针自增一，'<' 符号反之
'+' 符号表示指针所指内容自增一，'-' 符号反之
'.' 表示输出当前指针所指内容，',' 表示输入内容到指针所指处
'[' 表示如果当前指针所指内容为零，跳转至下一个']'后面
']' 表示如果当前指针所指内容非零，跳转至下一个'['后面
如果你看到了这里，那么恭喜你，BF语言你已经学会了*/
好了，下面是聊天内容（经过优化，略去不必要的部分），">>" 表示我说的话， "<<" 表示同学说的话
Conversation.Start:
>> 我觉得比汇编容易
<< 没什么要记的..
<< 但这种代码..
<< 没办法做开发啊
>> 无法维护
Conversation.Pause:
- 这里我要说一下，其实维护问题并不难，BF语言中虽然没有注释，但是事实上多数编译器都直接无视非关键字，也就是说你可以到处写注释，甚至把注释当成代码来写 。
Conversation.Continue:
>> 我发现用这个写程序有个很蛋疼的问题
>> 你必须记得当前在那个地址，以及每个地址当前的值
里面所有的指针都是用相对地址
<< 那指针内容什么的怎么搞
<< 比如你要输出ASCII字符
你怎么去找到这个字符？
>> 用>和<
<< 比如，输出字符“A”的程序是什么
>> 输出字符A，如下
code:
+++ +++ +++ +
[
>+++ +++ +
<-
]
>-----.
end of code
>> 第一行，[0]自增10，作为计数器,然后开始循环,循环中*[1]每次自增7,然后*[0]-1
当*[0] == 0时跳出循环，这个时候*[1] == 70,然后*[1] - 5,输出
所以说，你必须记住当前指针指向哪里，以及所有内存区域中的值
<< code:
+++ +++ +++ + [ > +++ +++ < - ] >+++++ .
end of code
这两种写法一样吗？
>> 一样，非关键字全部忽略
Conversation.Pause:
- 看，学习BF语言就是这么容易~！
Conversation.Continue:
<< 没办法直接提取指针，只能依次访问是吧..
>> BrainFk只有一个指针，你必须随时知道他在哪
所以养成每句话后面做清理是个好习惯
<< 这样没办法递归吧..
<< 你一次只能指向一个地址
Conversation.Pause:
- 问题就是从这里开始的。
Conversation.Continue:
>> 用循环代替递归
>> 一切递归都能用循环代替
<< 谁说的
>> 递归事实上就是给循环体起了个名字 - -
Conversation.Pause:
- 关于是否所有的递归都可以通过循环来完成，还有待商讨
- 就我个人而言，我认为一切循环都能够打包成递归，一切递归也都能展开成循环
- 或者说，我认为递归和循环是相互可逆的，理由如下：
- 假设说存在一个递归函数
- function(var1，var2，static var3，&var4) {...} // 使用C/C++表示
- 我们可以按照下述规则将其展开成循环
- 我们写一个过程体proc
- var1，var2在proc中使用赋值语句同步变量，在proc结束时清零
- var3在proc中使用赋值语句同步变量，在过程体结束时保留
- var4直接使用或者引用所需变量
- 为proc写循环语句，递归时函数用于判定的参数写入循环语句的判定部分
- 这样我们就将递归展开成了循环，而同样，将上述方法倒序，我们将从循环得到递归
Conversation.Continue:
<< 我觉得brainfk不可能在一个程序中用循环代替所有递归
<< 我组织一下思路
>> 事实上递归就是在函数执行完毕之后将指针指向函数的入口啊
<< 是啊
>> 所以说说到底还是循环~
<< 你怎么在递归中找到当前指针的位置
>> 使用一个容器
<< 你只有一个指针
和递归开始的位置
你的容器也要用这个指针去找
>> 比如说，我现在在[7]
要在[9]开始循环
我先把[7]归零，[8]增9
然后每一次循环之后[7]增一
通过[8]访问函数
[7]找起来很容易，因为可以先找[0]
<< 找0？
<< 好吧
Conversation.Pause:
- 事后证明，这个方法是错的
- 聊天至此，遇到了两个问题：一个是循环和递归是否互相可逆，另一个问题是只有一个指针的情况下究竟能不能对指针进行定位。如果这两个问题的答案都是肯定的，那么BF语言就可以实现递归。
- 这两个问题中的后一个争论许久，具体的冗长的聊天记录我先不贴出来了，觉得意义不大，争论出结果之前，我遇到点急事下了线，办完事吃了个饭回来，之后有了下面的记录
Conversation.Continue:
>> 我现在遇到一个问题，似乎没办法定位指针
>> 所以有可能你是对的
>> 不过毕竟有人BrainFk出线GCJ进Final，这个问题应该是有解的
Conversation.Pause:
- 向天才Luke Pebody致敬，此人3次参加IMO，14岁进入剑桥，16岁毕业，2008年使用BF语言参加GCJ进入Final. *
- *参见 http://en.wikipedia.org/wiki/Luke_Pebody
Conversation.Continue:
<< 我觉得可能是栈模拟
>> - - 我想想
<< 我想到这个问题完全是因为那时候想用这个写一个快排
<< 但是想着想着就想不通了
Conversation.Pause:
- 快速排序(QuickSort)是一种基本的排序法，在 http://baike.baidu.com/view/19016.htm 中有介绍，更详细的算法介绍及实现可以参见任意数据结构教程（不推荐严蔚敏写的数据结构C语言版）。
Conversation.Continue:
>> 我现在定位指针绝对位置的唯一办法就是直接循环递减到零指针，然后向后遍历
<< 对的..
<< 或者用0标志
<< 我觉得能实现的递归只能是自然结束的
<< 就是算到某个值符合条件
而这个值也适合作为判断条件
一般来说肯定是0
比如循环语句的实现使用计数器递减到0
但是如果其中的一个变量影响循环本身呢
问题就变得复杂了
>> 我在食堂门口的时候想了一下，每个变量需要至少五个地址
<< 最自然的想法，首先得依据变量的值来修改循环次数,或者另设一个指针记录剩余的次数
>> 但是后来还是发现，没法把相应地址的内容当做指针计数器，因为指针自增的语句导致指针自身也移动了
<< 对的
<< 简单的说这两种做法都将导致你找不到原来的入口了
>> 除非编写(if (1) > elseif (2) >> elseif (3) >>> .......)这样的SB程序2
<< 应该有什么比较适合brainfuck的方式吧..
>> - -我在想
Conversation.End
经过这样的讨论，之前的“是否可以实现指针的动态定位”问题变成了下面的问题：
是否可以找到一种方法，让指针查找的时候，每一次移动都能够找回原来的位置。
在这里解释一下，比如[4]用来存储另一个地址，或者说[4]中存储着一个自定义的指针，如果*[4] = 8，那么当程序执行到[4]的时候应该将主指针定位到[12] // (12 = 8+4)
我们用BF语言试写一下：
我们先初始化主指针到[4]：
>>>>
接下来我们将指针自增 *[4] = 8 次，问题就来了
如果我们只要自增八次，我们只要写下>>>>>>>>即可
但是我们在编写程序的时候可能并不知道[4]的值，或者说，[4]里面是动态的
最早想到的一个办法是指针每自增一次，*[4] - 1，但是事实上 *[4] - 1 这个语句在BF语言中就是一个 '-' ，但是主指针必须指向[4]。
如果我们写 [><-] 那么到最后指针还是停留在[4]上
如果我们把过程拆开，就是[4]值先自减，指针自增，然后自减，值自减，然后自增两次，再自减两次，值自减，自增三次，自减三次，值自减，以此类推，直到*[4] = 0,然后指针自增8次
如果看到这你还没笑，那你看了下面的代码，一定就笑了：
- [
><-
>><<-
>>><<<-
>>>><<<<-
>>>>><<<<<-
>>>>>><<<<<<-
>>>>>>><<<<<<<-
] >>>>>>>>
真是笑死了，这和>>>>>>>>没有任何区别，[]循环形同虚设，还浪费资源，到头来编写者还是要在写程序时得知*[4]
上面的代码唯一值得赞扬的就是画面美感
当然如果你写成
-[><->><<->>><<<->>>><<<<->>>>><<<<<->>>>>><<<<<<->>>>>>><<<<<<<-] >>>>>>>>
那就连画面美感也没了
那么到底有没有一种办法可以在指针自增的同时，让其还可以每一次自增之后再找回原来的[4]呢。
我脑袋比较笨，在讨论的当天并没有想出一个可行的算法来。
想了很多很多办法，包括用五个连续的地址存储一个变量，[n]存储值，[n+1],[n-1],[n+2][n-2]分别存储变量的左右信息等等，但最后都被证明不可行。
然而当天清晨，我鬼使神差地梦到了自己用冒泡排序算法解题。
醒来一拍大腿，哎呀我C，成了。
我所想到的算法类似冒泡排序中冒泡的过程，如下：
指针每自增一次，[n]与[n-1]的值便交换，然后*[n]自减，重复这一过程直到 *[n] = 0
[n]与[n-1]的值交换，可以有两种方法实现，一种是对*[n] 和 *[n-1] 进行异或，还有一种就是利用第三方[m]
鄙人不才，尚未找到在BF中实现抑或的办法，所以决定使用后者。
那么初步的算法如下：
规定当*[n]表示一个地址时，*[n-1]必须为零，作为临时区域，比如上面的例子，就必须*[4] = 8, *[3] = 0，该指针变量由[3]和[4]构成，长度为2，头地址为[3]。
1 指针指向[n+2],将当前指针位记为[n]
2 [n-2] = [n]; [n] = [n-1]; [n-1] = [0]
3 [n]--
4 如果[n+1] 非零，跳转到1
5 指针自减2
这个算法用BF语言书写如下：
[
>>
[<<+>>-]
<[>+<-]
>-<
]<<
当然，如果你嫌行数太多看着难受，也可以写成这样
[>>[<<+>>-]<[>+<-]>-<]<<
接下来把后面的所有内容向前移动两格，填充那个多出来的部分就行了
不过依旧有问题，这样子虽然定位成功，但是把指针定位用的变量给破坏了。
不过这个容易解决，办法是在定位指针前拷贝一份定位用的变量，算法如下：
1 将指针指向程序最后一个地址段[max]，将所有内容后移两个单位（[n+2] = [n]）。
2 将指针指向[0]，将所有内容前移两位，直到移动后指针指向原定位变量所在地址
3 假设此时指向[n]，则[n] = [n+2]，[n+1] = [n+1+2]
那么问题就在于，如何让循环开始或终止于[0]和[max]
我想出的办法是医牺牲一半多的内存，规定除[0]和[max]之外，所有[n]的最高位必须为零，且[n]最大01110，而非01111。
同时将*[0] 和 *[max] 置为 -1
然后所有*[n]自增1
那么遍历判断时，就只有*[0]和*[max]为零了。
鉴于时间关系（困死了我去睡觉了），该算法的BF语言实现留给读者们玩吧~~~~
[解决办法]
额。。。辛苦了
[解决办法]
学习一下，不是很了解！
[解决办法]
一个喜欢捉弄人的人发明了BF语言，或者说是一个喜欢炫耀的人发明了让喜欢炫耀的人炫耀的语言！
[解决办法]
