Fleurer.Lee

作者：Mark C. Chu-Carroll
翻译：Fleurer
原文：http://scienceblogs.com/goodmath/2008/02/abstract_algebra_and_computati.php

在前两篇post，我们以范畴的角度观察了群论。范畴论给了我们一个全新的视角来理解对偶。与传统代数不同，范畴论的对偶是从groupoid中出现的，而群则被视为是带对偶的更简单的结构。

看其它的代数结构也是同样。比如环（rings），换个视角，也可以见到一个大不相同的环。

在看范畴论下的环之前，我们不妨先看个简单点的结构。在范畴中，环是通过monoid表示的。不过Monoid绝不仅仅只是环前面的开胃菜，它本身就是好东西。

它们的魅力在什么地方？首先，它们是范畴和代数之间的一座桥梁。我们知道，范畴中的groupoid（广群）使得群论无缝地归入了范畴论。Monoid也可以同样：它们也有范畴中的等价物。而且，Monoid还有地地道道的实际应用——你可以用Monoid表示计算。而且也许不广为人知，计算机科学中很多得力的基础工具其实都是Monoid。

我们先用代数的视角看下，呆会再换到范畴视角。在抽象代数中，Monoid正好跟复合函数的思想一致。开窍了吧，范畴论的基本思路就是复合函数的抽象化！

Monoid跟群类似，是一组支持二元运算的值的集合。Monoid更简单——它只要组合，不要逆元。我们令Monoid里面值的集合为M，二元运算为º，就有三条性质：

1. 封闭性（Closure）: ∀a,m∈M: aºb ∈ M
2. 单位元（Identity）: ∃ i∈M : ∀f∈M : iºf = fºi = f.
3. 结合律（Associativity）: ∀ a,b,c∈M: (aºb)ºc = aº(bºc).

这就是了。有这几条性质，想想函数和复合函数，套进去就满靠谱了。这对大多数函数都适用，于是所有的函数都成了对象，比如定义域和值域都是自然数的函数。封闭性要求两个简单完全函数复合的结果依然是简单完全函数；单位元可以是一个函数f(x)=x；交换律是交换表达式中元素的顺序，不影响最终结果。这都是复合函数天生的性质。

如果拿monoid像群一样，给它加一个操作又会怎样？答案对我们学计科的同学再熟悉不过了：有限自动机！

取一个monoid，(M,º)。我们可以在集合S上定义这monoid的一个操作，也就是：*:M×S→S，取M的一个值和S的一个值，得S的一个值。这个monoid操作显示了两条性质——都是来自monoid。

1. Identity: ∀s∈S, i*s=s.
2. Associativity: ∀a,b∈M, ∀s∈S: a*(b*s) = (aºb)*s.

这意味着什么？意味着我们给这个monoid加上了函数应用。这个monoid操作就是M中函数的应用。

这样，有了一个组可组合的函数，一个可以应用到函数的特定集合。可以得到什么？

一台自动机——也就是一种数学上的计算模型。

这个自动机是怎么出来的？

在这个monoid操作里，monoid的每个成员都是函数，也就是值到值的映射；组合符将这些函数链到一起。对自动机来说，monoid中的每个成员都是计算中的一个步骤，组合符将这些步骤连续起来。这还不是完整的计算——但已经靠一个简单的形式，前进了一大步。

多想想。还记得lambda演算？它就是一个表示计算的逻辑工具，里面除了函数什么都没有。想到了吧，我们刚刚只是重新发明了lambda演算的一部分，以抽象代数的思路。

在以后的post里面我会多讲些——不过我得先给你过上一遍，在范畴论里面这些东西都是什么样子——下一步往哪走，在范畴的大陆上清晰无比。

随便写了下，没仔细调试。

大约这么定义
double parse_expr(char *input, char **output);

input就是表达式的字符串，output是解析剩下的部分。如果output==input，就是解析失败。如果正确，返回运算结果。

用起来大约这样

    char *out, *exp="2+(1+3)*4";
    double r = parse_expr(exp, &out);
    if (out==exp){
        printf("parse fail\n");
        return 0;
    }
    printf("%s => %f \n", exp, r);

回头想下，思路跟以前写的parser几乎是葫芦画瓢，也该算是递归下降吧。

代码如下

exp.h

double parse_expr(char *input, char **output);
double parse_term(char *input, char **output);
double parse_fact(char *input, char **output);
double parse_numb(char *input, char **output);

exp.c

#include "exp.h"
 
// expr ::= term {[+-] term}
double parse_expr(char *input, char **output){
    double r=0;
    char *tmp, op;
    tmp = input;
    // factor
    r = parse_term(tmp, output);
    if (output==tmp){
        return 0;
    }
    // {[+-] term}
    tmp = *output;
    while ((op=*tmp)=='+' || op=='-'){
        double r2 = parse_term(++tmp, output);
        if (tmp==*output){
            *output = input;
            return 0;
        }
        r = (op=='+')? r+r2: r-r2;
        tmp = *output;
    }
    return r;
}
 
// term ::= factor {[*/] factor}
double parse_term(char *input, char **output){
    double r=0;
    char *tmp, op;
    tmp = input;
    // factor
    r = parse_fact(tmp, output);
    if (output==tmp){
        return 0;
    }
    // {[*/] factor}
    tmp = *output;
    while ((op=*tmp)=='*' || op=='/'){
        double r2 = parse_fact(++tmp, output);
        if (tmp==*output){
            *output = input;
            return 0;
        }
        r = (op=='*')? r*r2: r/r2;
        tmp = *output;
    }
    return r;
}
 
// fact ::= (expr) | numb
double parse_fact(char *input, char **output){
    double r=0;
    char *tmp;
    // (expr)
    if (*input=='(') {
        tmp = input+1;
        r = parse_expr(tmp, output);
        if(**output==')'){
            (*output)++;
            return r;
        }
        // if fail, output == input
        else {
            *output = input;
            return 0;
        }
    }
    // numb
    r = parse_numb(input, output);
    return r;
}
 
double parse_numb(char *input, char **output){
    double  r = 0;
    char ch, *tmp=input;
    while((ch = *tmp++)>='0' && ch<='9'){
        r = r*10+ch-'0';
    }
    *output = tmp-1;
    return r;
}

main.c

int main(){
    double r;
 
    char *out, exp[1024];
    scanf("%256s", exp);
    r = parse_expr(exp, &out);
    if (out==exp){
        printf("parse fail\n");
        return 0;
    }
    printf("%s => %f \n", exp, r);
 
    return 0;
}

经常踩大街。一人出去走到哪儿是哪儿，半阴不晴的鬼天气，没有店牌的店面们没精打采的耸拉着横幅，各种喇叭不甚自信地喊着各种优惠，摆摊的人们逛街的人们钻下水道的人们上学放学的人们熙熙攘攘的人们。地方就这么大，变的都是人。

学校里各种活动…社团每年的份额。辩论赛，书画比赛，考研，考试，奖学金等等，人们总有的忙。推特上的民主人士无限精力地bs着这个当权派，新华网上依旧按部就班的各种无耻新闻。豆瓣的人们为中医是不是科学争个面红耳赤。0bug老师升级为0(7)老师然后关博。脑残不休圣战不止的圣战悄无声息地不见了声势。人们总有的忙。我呢。

目的这东西，在我意识到它不见的时候，却发现已如背叛你的一切，早已无处可寻。若是空虚得紧，就是什么函数式什么内核也无济于事。“不过走下去自然有路。”我这么安慰自己，甚至不知道自己信还是不信。“走下去自然有路。”如此，走遍了这座小城。走过了曾经不减肥的五月和这个徒伤悲的六月。

—-

昨晚在大路兄宿舍阳台上，看楼下的辅导员和警车。第二天封楼。

“咱们学校倒也还不错的。”
“建设的很好，不过上面是一群官僚。”

对付学生，上面经验的很。扣下学生一张证件，若哪个宿舍有酒瓶暖瓶之类的杂物掉下，楼下的辅导员定位出来就扣下整个宿舍的证件。也得警车来来回回威慑，要诀就是防患于未然，要是学生都闹起来扣毕业证就不好使了。

保卫科的小面包上面放一个小灯，跟警车一起来来回回的转。辅导员不停地拍着蚊子。身在这个官僚体系最底层的人们如此兢兢业业…真是个神奇的世界。

过两个月，迎接新生又会是什么图景！

我就想，我们认认真真生活的这个世界，又有多少是别人认认真真装出来的？

这可是四年的地方，谁舍得。

—-

没找着某佳的宿舍，给某鹏和飞哥打电话也没通。突然就难过的很，这些人说不见就不见了不成！

过会儿飞哥打电话回来，刚才在收拾东西。还好还好，还能打个电话。

有段时间飞哥忙着写书，经常能见面，见面就去北门吃饭。“在餐厅吃也方便，不过得多走走。”飞哥，zneil等等几人一伙，必点西红柿炒鸡蛋。

有次回来飞哥问喜不喜欢看水浒。“我最佩服林冲，太能忍了。当年统领八十万禁军啊…光忍不行，也得能怒，你看风雪山神庙…这就是大侠！”

这人混过学生会，干过程序，写过书，考过研，搞过机器人。说不累是假的。

去年一个莫名其妙的饭局上，发现飞哥不见了。出来找，见他一人在外面。“我爸刚才给我电话，没敢接怕他听出来喝酒。。。走，出去透口气。”

问我“你有什么打算？”

不知道…不考研反正…不敢想以后…

然后坐在马路牙子上，吐酸水。“你知道我为什么理平头？掉头发。前几天去拿药，医生说我胃分泌的有点乱。。”

“千千万万在大四前解决感情问题。。做这机器人耽误了暑假的两个月，考研的黄金时期。。”

一会儿回去，仍是同样的谈笑风生，跟社会上的那帮人闹的不亦乐乎，整个桌子依然围着他转。你保准看不出一丝破绽。

。。。

如今能说的只剩下保重，后会有期。

—–

把zneil叫出来吃饭，这人神奇的课表剩下整整一年完全没课，再没考研的打算，整个人都宅了。

这帮混蛋整的都是什么事情！不甘心…可我们有什么办法？No body cares，所以认真你就输了。

无能为力，这就叫一败涂地。

还是老老实实的，搞好自己吧。

—–

《了不起的盖茨比》里面印象最深的是这么一段：

“他们都是一帮混蛋，”我隔着草坪喊道：“把他们加在一起都比不上你！”

我后来一直很高兴我说了那句话。那是我对他说过的唯一一句恭维话。因为我自始至终都不认同他。

—–

“干死英格兰！”

对面楼上喊，不过灯已经黑了一半。辅导员应该结束了几天的辛苦，可以睡个安稳觉了。

他们会在什么地方看球！

起比VC风格的内联汇编，GCC的确实要别扭些，一开始要不看手册肯定一头雾水。

int foo = 10, bar = 15;
asm volatile("addl  %%ebx,%%eax"
            :"=a"(foo)                //output constraint
            :"a"(foo), "b"(bar)      //input constraint
            :                            //clobbered registers(ignored)
);

指令大家都明白，不过:”=a”(foo)这样的语法就古怪了。:后面的东西好像叫做约束，指明了输出和输入中用到的变量和寄存器。第一个的”=a”(foo)是输出的约束，就表示汇编执行完毕后foo=a。后面的”a”(foo)是输入的约束，表示汇编执行前的a=foo。这一来C和汇编就可以在约束下边交换数据了。

刚才这个a就是表示分配eax寄存器。

各种约束还挺多的…

为什么要这么难看的语法呢…我猜这东西最早应该是给编译器而不是给人类设计的吧，比起VC风格的内联汇编，它可以得到更多关于变量和寄存器的信息，编译器分配起寄存器来可以心里有数，不用怕自作聪明的人类把事情都搞乱掉。

看的这个教程 http://share.solrex.org/WriteOS/

仿照《自己动手写操作系统》的格式，除却gas确实很囧的因素，大体上还是不错的。万事开头难，在开头的bootloader这里卡了好久的说…不过动手写一下也不过半小时的功夫 TvT

机器在启动的时候可能是遍历每个磁盘分区，若有发现第512字节位置是个0xAA55的魔数，就认为这是个引导的分区了。然后就把它的前512字节装入内存，从0×7c00位置开始执行。这就是最简单的引导方式了好像。

我们把汇编代码编译成一个512bytes的二进制文件，再把它放到一个软盘的映像里就好。

boot.S

[bits 16]                       ;real mode
[org 0x7c00]                  ;put code start at 0x7c00
[section .text]
 
_start:
    mov     ax, cs            ; init seg registers
    mov     ds, ax
    mov     es, ax
    call    _print_str      
 
_print_str:
    mov     ax, str            
    mov     cx, len    
    mov     bp, ax
    mov     bx, 0x000c
    mov     dl, 0
    mov     ax, 0x1301
    int     0x10                              ;int 0x10, just as manual says
 
_loop: 
    jmp     _loop                             ; forever loop
 
str: db      "screw you guys all fucked up~",10,13
len: equ     $-str
 
times 510-($-$$) db 0                   ; fill the rest with 0
dw 0xAA55                                  ; magic number

编译之

nasm -f bin boot.S

生成一个boot.bin，下一步搞个软盘镜像

dd if=boot.bin of=boot.img bs=512 count=1
dd if=/dev/zero of=boot.img skip=1 seek=1 bs=512 count=2879

ls -l 下，大约会是这样

-rwxr-xr-x 1 ssword ssword     512 2010-05-26 21:28 boot.bin
-rw-r--r-- 1 ssword ssword 1474560 2010-05-26 21:28 boot.img
-rw-r--r-- 1 ssword ssword     399 2010-05-26 21:28 boot.S

然后打开virtualbox，设置软驱映像为boot.img。启动虚拟机就可以看到一个可爱的”screw you all”什么的了 >v<