去年听王猫猫讲过之后就一直心安理得再也没看过Monad，以至于到昨天还不知State Monad为何物…囧
关于State Monad，似乎见过的教材都是拿随机数作例子，拿Monad跟一堆let对比，满眼的二元组绕啊绕啊，我给你个Monad让它不那么绕（存疑）～其实什么东西理解不了，往往就是因为不知道它怎么用（比如复变函数 =”=）
换个例子，像那个筛掉一个List中重复元素的nub函数多好….在命令式语言下边大约是这样：
def nub(xs)
result=[]
for x in xs
if not result.include? x
result << x
return result若在函数式语言下边，用迭代大约是这样：
inub :: (Eq a) => [a] -> [a]
inub = inub' []
inub' rs [] = rs
inub' rs (x:xs)
| x `elem` rs = inub' rs xs
| otherwise = inub' (rs++[x]) xsinub’这个函数中有个rs参数，就相当于前面那个result变量。它的值会随着迭代发生改变，不同之处就是ts是引用透明的没有副作用。每次函数调用就是一个状态，状态就是一个值。
不喜欢给函数多加个参数怎么办？State Monad可以做到。在State Monad里面有两个函数可以使用：put，设置当前状态的值；get，获得当前状态的值。就相当于给函数加了一个（只有一个）可变的全局变量，在调用别的函数或者递归时这个值可以保留。
State Monad版本（我没觉得好看 =”=）：
mnub :: (Eq a) => [a] -> [a]
mnub xs = evalState (mnub' xs) []
mnub' [] = get
mnub' (x:xs) = do {
rs <- get;
if x `elem` rs then (do {
mnub' xs;
})
else (do {
put $ (rs++[x]);
mnub' xs;
});
}原理大约就是do-notation中的每个语句都是用一个wrapper的类型包起来再不断往下传递么，而State的wrapper就是个类型为(a,s)的二元组（外加一层lambda？），每个语句的返回值放到s里，那个全局的值则放在a里…具体还有点迷糊，哪天推导下再说好了 >_<
Published on
2010年01月19日 in
笔记.
Tags: C, ruby, VM.
因为swdpress.cn的死掉严重打击积极性，好久没更新了。此文纯凑数。
ruby中除了Fixnum，其余所有类型的值都是引用传递。读《ruby hacking guide》时看到如下的定义：
typedef unsigned long VALUE;
同lua那union+tag不一样，ruby中所有类型的值都存放在一个VALUE中，而没有tag指明其类型。如果是Fixnum，就把数值直接放在VALUE里；如果是其它类型，则存放其地址（unsigned long和C中指针类型的长度一致）。不过万一作为Fixnum的VALUE指向的地址与其他对象有重叠怎么办？它又怎么区别数值和地址呢？
这用到了一点tricks，C的struct在内存中都是以4字节对齐，因此ruby中所有对象的地址都偶数。在表示Fixnum时，ruby就将C的int值左移一位再加一，使其看起来总是个奇数，这样就不会与ruby的其它对象有重叠。
123 #define INT2FIX(i) ((VALUE)(((long)(i))<<1 | FIXNUM_FLAG))
122 #define FIXNUM_FLAG 0x01
(ruby.h)
判断一个VALUE是Fixnum还是地址，只需判断VALUE是奇数还是偶数就行了。
表示true,false和nil是这样：
164 #define Qfalse 0 /* Ruby's false */
165 #define Qtrue 2 /* Ruby's true */
166 #define Qnil 4 /* Ruby's nil */
(ruby.h)
都是偶数。像刚才说的，它们不会被当作是地址了么？这就用到了另一个trick：进程虚拟地址空间的前一部分都是不可访问的。因而0,2,4的地址上不会存在ruby对象。
PS: 感谢FX大大提醒，这套方法有个标准的名字叫做“tagged pointer” :)
前些天写html生成器的时候用到了erb，在生成html的时候是这么一句：
binding这个变量（Kernel的一个方法 T_T）有点古怪，就搜了下。它表示了ruby的当前作用域，没有任何对外可见的成员函数，唯一的用途就是传递给eval作第二个参数。因而可以这样：
def test_binding
magic='brother Chun is PURE MAN'
return binding
end
eval "puts magic", test_binding这样就穿越了一个作用域。
有时可以见到这样的构造函数：
a=Baby.new {
name "Makr"
father "Mike"
age 0.2
}
a.cry好处就是好看。实现起来其实也很容易，用instance_eval：
class Baby
def initialize(&blc)
instance_eval(&blc) #here
end
def name(str=nil)
@name=str if str
@name
end
def age(num=nil)
@age=num if num
@age
end
def father(str=nil)
@father=str if str
@father
end
def cry
puts "#{name} is only #{age.to_s} year old, he wanna milk! Brother Chun is PURE MAN!"
end
end有重复代码？用class_eval缩短之，有点像宏了：
class Baby
def initialize(&blc)
instance_eval(&blc)
end
def Baby.my_attr(*names)
names.each{|n|
class_eval %{
def #{n}(x=nil)
@#{n}=x if x
@#{n}
end
}
}
end
my_attr :name, :father, :age
def cry
puts "#{name} is only #{age.to_s} year old, he wanna milk! Brother Chun is PURE MAN!"
end
end
a=Baby.new {
name "Makr"
father "Mike"
age 0.2
}
a.cry这里class_eval穿越到了类的作用域，实现了动态添加函数。instance_eval也是，穿越到了实例的作用域，实现修改其内部数据。明白了它们的穿越关系，我们可以实现自己的class_eval和instance_eval——从合适的地方搞到binding就行了。
class Baby
def my_instance_eval(code)
eval code, binding
end
def Baby.my_class_eval(code='')
eval code, binding
end
end就这么简单。调用的时候就像这样：
class Baby
def initialize(code)
my_instance_eval(code)
end
my_attr :name, :father, :age
end
a=Baby.new %{
name "Test"
father "Orz"
age 0.2
}刚才省略了一点，那就是class_eval和instance_eval可以接受block代替字符串。搜了下，貌似没找到eval接受block的方法，所以这顶多算是只能eval字符串的山寨class_eval。
update: 想起来ruby中lambda和proc在作用域上的小区别，也就是binding的不同了。proc直接使用原先的binding，lambda继承原先作用域创建一个新的binding。
据说若要深入学习MIPS开发的话，《MIPS处理器设计透视》这书是必不可少的。不过若只是学习MIPS汇编，这书可能就不大合适了。汇编语言还是隐藏了CPU的很多细节，而这本书里讲的貌似就是这部分，在对汇编有所了解之后再来阅读可能要更好。
学习函数式语言的时候总是满足于看书，理解下语法语义即可，真正写的代码则少的可怜，不过确实“改变了编程的看法”，目的也算达到了。汇编就不行了，看书不够，一定得动手。所以学MIPS需要一个模拟器。pcspim应该是比较标准的了，不过感觉Mars可能要更好用（准确地说，Mars非常非常好用）。
MIPS是以优雅著称，据说即使是其竞争对手也如此认为。RISC么，32个寄存器，指令长度都一样。其中的指令大约这么三种形式：
j 1000
li $1, 10
add $1, $2,$3
差异就是各个参数的长度不同。如add指令的三个参数都只有两个位宽（0~255），每个参数表示一个寄存器。如果把指令看作函数，那参数就可以看作是有类型的。而MIPS的汇编器是很强大的（听说可以进行窥孔优化），像add $t0, $0, 10这样的指令会被汇编器翻译成addi $t0,$0,10。汇编器处理前后指令的对比可以在Mars中显示出来。
记几个helloworld吧，
求3的阶乘：
li $t0, 0
li $t1, 1
if_1:
add $t0, $t0, 1
mul $t1, $t1, $t0
bne $t0, 3, if_1
在Mars下可以看到寄存器的变化，最后$t1寄存器的值是6。
mips汇编的分支（branch）指令分b系（bne，beq，bgt等等）和j系（j, jr等），差别就是b系指令的跳转都是有条件的，而且地址在参数中指明，而j系的跳转都是无条件的。j系指令的地址长度更长，寻址范围要更大，所以远程跳转都是j。
输出Helloworld：
.text
.globl main
main:
li $v0, 4 # just the print syscall in SPIM
la $a0, str
syscall
.data
str:
.asciiz "hello world"
这应该算个比较完整的汇编程序了。程序的可执行代码都是在.text段，数据在.data段。.globl指明程序的入口地址，那个:str指代的就是这段字符串的地址。字符串么，就是数组。数组不就是指针么。
其中这个syscall会与操作系统的不同而有差异。系统调用的号码由$v0指明，参数在$a系的寄存器中传递，返回值放回到$v0。这里调用的是spim实现的4号系统调用，即print string。
定义一个函数f_add，它可以将两个数相加：
.text
.globl main
f_add:
add $v0, $a0, $a1
jr $ra
main:
li $a0, 1
li $a1, 2
jal f_add
add $t0, $v0, $0
li $v0, 1
add $a0, $0, $t0
syscall
在使用jal指令的时候，它会把发生跳转的地址记录在$ra寄存器中。这样函数在结尾的时候就可以用jr返回原先的位置了。
使用寄存器传递参数的好处貌似就是约定了函数的调用规范，兼容性要更好。例如x86下的BASIC和C在参数传递时压栈的顺序貌似就是相反的。
众所周知，lambda演算通过递归就可以图灵完备。好，用纯lambda演算写个递归吧。
等等，要递归必须得有名字，而lambda演算里赋予名字的唯一方式就是传递参数。像lisp那样define可不行啊。只能这样绕个圈子：
(\f.\x.
(if (= x 1)
1
(* x (f f (- x 1)))))这里把函数本身作为第一个参数传递给自己，从而实现的递归。要调用这个递归函数，还得套一个let（当然，换成lambda形式）:
((\fac. (fac fac 5))
(\f.\x.
(if (= x 1)
1
(* x (f f (- x 1))))))真难看！每次递归都得把自己当作参数传递一遍，很机械！机械的活不应由人类做！想下，如果将递归函数里的(f f (- x 1))换成(f (- x 1))，或许还可以接受…好，Y组合子应运而生，现在你可以这样自然地递归了：
Y (\f.\x
(if (= x 1)
1
(* x (f (- x 1))))) 5数学家在追求美感上可是不遗余力啊。不过Y是如何做到的？
想想，Y组合子又叫不动点函数。什么是不动点？x=f(x)=f(f(x))…，这个x就是不动点：不管套多少层函数调用，在不动点上的值总是相等。Y f = f (Y f)=f (f (Y f))，这个Y f就是个不动点，高阶函数的不动点。什么是组合子？很简单，可以柯里化、没有自由变量的函数就是组合子 :)
便于理解，我们给(\f.\x (if (= x 1) 1 (* x (f (- x 1)))))这个lambda一个名字fac，看看一步步的递归是怎么来的：
Y fac 3
> fac (Y fac) 3 //transform, Y!
> 3 * ((Y fac) 2) //3 !=1 so recurse
> 3 * (fac (Y fac) 2) //Y transform again
> 3 * (2 * ((Y fac) 1)) //2 !=1 so recurse
> 3 * (2 * (fac (Y fac) 1)) //Y transform again
> 3 * (2 * 1) //1=1, so recursion ends.
> 6
就是这样了。里面有柯里化，也有惰性求值（缺一不可！）。一环套一环，然后就递归了。
Y组合子的定义：Y = \y. (\x.y (x x)) (\x.y (x x))，天知道大神（大神的名字叫做Haskell Curry! -v-）是怎么想出来的 =v=
不妨自己在纸上推倒一下(也只能在纸上推倒，这东西在实际的编程中貌似是没有应用的 :D)
FeedBurner
Comment