由一段聊天记录引出的

文号t34429

5977

由一段聊天记录引出的

epi.clyce2011/06/22软件综合 IP:上海

这几天和一个同学聊了点东西，关于一些function在BF语言下的实现

/*教学部分，熟悉BF语言的可以掠过

    BF语言我个人感觉真的是世界上最好学的语言之一，因为你只要三分钟就能学会这个语言的全部，至于如何用BF语言编程，那就看你的脑袋了。

    BF语言的全称叫BrainF**k，是一种极小化的计算机语言，它是由Urban Müller在1993年创建的。Müller的目标是建立一种简单的、可以用最小的编译器来实现的、符合图灵完全思想的编程语言。这种语言由八种状态构成，为Amiga机器编写的编译器（第二版）只有240个字节大小。
    就象它的名字所暗示的，BF程序很难读懂。尽管如此，BF图灵机一样可以完成任何计算任务。虽然BF的计算方式如此与众不同，但它确实能够正确运行。
    这种语言基于一个简单的机器模型，除了指令，这个机器还包括：一个以字节为单位、被初始化为零的数组、一个指向该数组的指针（初始时指向数组的第一个字节）、以及用于输入输出的两个字节流。*

        *来自WikiPedia中文版

    好了，介绍完毕，下面是基本语法：
        '>' 符号表示指针自增一，'<' 符号反之
        '+' 符号表示指针所指内容自增一，'-' 符号反之
        '.'  表示输出当前指针所指内容，',' 表示输入内容到指针所指处
        '[' 表示如果当前指针所指内容为零，跳转至下一个']'后面
        ']' 表示如果当前指针所指内容非零，跳转至下一个'['后面

如果你看到了这里，那么恭喜你，BF语言你已经学会了*/

好了，下面是聊天内容（经过优化，略去不必要的部分），">>"  表示我说的话， "<<" 表示同学说的话

XXXXXXXXXXXXXXXart:
    >> 我觉得比汇编容易

    << 没什么要记的..

    << 但这种代码..

    << 没办法做开发啊

    >> 无法维护

XXXXXXXXXXXXXXXuse:
    - 这里我要说一下，其实维护问题并不难，BF语言中虽然没有注释，但是事实上多数编译器都直接无视非关键字，也就是说你可以到处写注释，甚至把注释当成代码来写。

XXXXXXXXXXXXXXXntinue:
    >> 我发现用这个写程序有个很蛋疼的问题

    >> 你必须记得当前在那个地址，以及每个地址当前的值
          里面所有的指针都是用相对地址

    << 那指针内容什么的怎么搞

    << 比如你要输出ASCII字符
          你怎么去找到这个字符？

    >> 用>和<

    << 比如，输出字符“A”的程序是什么

    >> 输出字符A，如下
       code:
            +++ +++ +++ +
            [
                >+++ +++ +
                <-
            ]
            >-----.

        end of code

    >> 第一行，[0]自增10，作为计数器,然后开始循环,循环中*[1]每次自增7,然后*[0]-1
          当*[0] == 0时跳出循环，这个时候*[1] == 70,然后*[1] - 5,输出
          所以说，你必须记住当前指针指向哪里，以及所有内存区域中的值

    << code:
              +++ +++ +++ + [ > +++ +++ < - ] >+++++ .
          end of code

       这两种写法一样吗？

    >> 一样，非关键字全部忽略

XXXXXXXXXXXXXXXuse:
    - 看，学习BF语言就是这么容易~！

XXXXXXXXXXXXXXXntinue:
    << 没办法直接提取指针，只能依次访问是吧..

    >> BrainFk只有一个指针，你必须随时知道他在哪
          所以养成每句话后面做清理是个好习惯

    << 这样没办法递归吧..

    << 你一次只能指向一个地址

XXXXXXXXXXXXXXXuse:
    - 问题就是从这里开始的。

XXXXXXXXXXXXXXXntinue:
    >> 用循环代替递归

    >> 一切递归都能用循环代替

    << 谁说的

    >> 递归事实上就是给循环体起了个名字 - -

XXXXXXXXXXXXXXXuse:
    - 关于是否所有的递归都可以通过循环来完成，还有待商讨
    - 就我个人而言，我认为一切循环都能够打包成递归，一切递归也都能展开成循环
    - 或者说，我认为递归和循环是相互可逆的，理由如下：
    -     假设说存在一个递归函数
    -         function(var1，var2，static var3，&var4) {...}    // 使用C/C++表示
    -     我们可以按照下述规则将其展开成循环
    -         我们写一个过程体proc
    -         var1，var2在proc中使用赋值语句同步变量，在proc结束时清零
    -         var3在proc中使用赋值语句同步变量，在过程体结束时保留
    -         var4直接使用或者引用所需变量
    -         为proc写循环语句，递归时函数用于判定的参数写入循环语句的判定部分
    -    这样我们就将递归展开成了循环，而同样，将上述方法倒序，我们将从循环得到递归

XXXXXXXXXXXXXXXntinue:
    << 我觉得brainfk不可能在一个程序中用循环代替所有递归

    << 我组织一下思路

    >> 事实上递归就是在函数执行完毕之后将指针指向函数的入口啊

    << 是啊

    >> 所以说说到底还是循环~

    << 你怎么在递归中找到当前指针的位置

    >> 使用一个容器

    << 你只有一个指针
          和递归开始的位置
          你的容器也要用这个指针去找

    >> 比如说，我现在在[7]
          要在[9]开始循环
          我先把[7]归零，[8]增9
          然后每一次循环之后[7]增一
          通过[8]访问函数
          [7]找起来很容易，因为可以先找[0]

    << 找0？

    << 好吧

XXXXXXXXXXXXXXXuse:
    - 事后证明，这个方法是错的
    - 聊天至此，遇到了两个问题：一个是循环和递归是否互相可逆，另一个问题是只有一个指针的情况下究竟能不能对指针进行定位。如果这两个问题的答案都是肯定的，那么BF语言就可以实现递归。
    - 这两个问题中的后一个争论许久，具体的冗长的聊天记录我先不贴出来了，觉得意义不大，争论出结果之前，我遇到点急事下了线，办完事吃了个饭回来，之后有了下面的记录

XXXXXXXXXXXXXXXntinue:
    >> 我现在遇到一个问题，似乎没办法定位指针

    >> 所以有可能你是对的

    >> 不过毕竟有人BrainFk出线GCJ进Final，这个问题应该是有解的

XXXXXXXXXXXXXXXuse:
    - 向天才Luke Pebody致敬，此人3次参加IMO，14岁进入剑桥，16岁毕业，2008年使用BF语言参加GCJ进入Final. *
    -     *参见 XXXXXXXXXXXXXXXXXXXXXXX/wiki/Luke_Pebody

XXXXXXXXXXXXXXXntinue:

    << 我觉得可能是栈模拟

    >> - - 我想想

    << 我想到这个问题完全是因为那时候想用这个写一个快排

    << 但是想着想着就想不通了

XXXXXXXXXXXXXXXuse:
    - 快速排序(QuickSort)是一种基本的排序法，在 XXXXXXXXXXXXXXXXXXXXXX/view/XXXXXXXXm 中有介绍，更详细的算法介绍及实现可以参见任意数据结构教程（不推荐严蔚敏写的数据结构C语言版）。

XXXXXXXXXXXXXXXntinue:
    >> 我现在定位指针绝对位置的唯一办法就是直接循环递减到零指针，然后向后遍历

    << 对的..

    << 或者用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语言实现留给读者们玩吧~~~~

来自：计算机科学 / 软件综合

引用第10楼ltl于2011-07-26 16:29发表的 :

谁告诉你代码是给人看的……你见过那个程序员过几天还看得懂自己的代码的……

多少年来人们一直在强调代码的可读性..
Steve McConnell哭了
Stanford 公开课程编程方法第二课

The important thing to realize in programming is programming is not just about writing a program that the computer understands. Programming is about writing programs that prople understand. I can't stress that enough. That's huge. That's what programming style is all about. It's what good software engineering is all about. Writing a program that just works, that someone else can't read and understand, is actually really terrible sofrware engineering. And I've seen software companies do this where some hotshot programmer comes along and they're like, "Oh, I'm a great programmer." And they go and write some program to do something, and it works the first time and then it breaks. And then they come along and they say, "Hey, we need to actually get that program to do somthing slightly different, or we need to upgrade it." And it's written in terms of the code so badly that they can't do anyting with it, and they throw it out completely, fire the programmer, and get a team of good software engineers to actually do it. I've actually seen that happed multiple times. Okay, so write programs for people to read, not just for computers to read. Both of them need to be able to read it, but it's far more important that a person reads it and understands it. That's the first software engineering principle to think about.

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

当前账号的附件下载数量限制如下：

请选择违规类型：

空空如也