rage and love, story of my life.
好像刚弄明白动态作用域是怎么回事，拿个例子：
var a=0; //global def f1(): a=1 def f2(): var a; //local f1() f2() puts a
若是静态作用域，f2调用f1，f1修改全局变量a的值为1，输出1。这个多自然…
可是动态作用域就…输出0，全局变量a的值没有变化。
f2不是调用了f1么，f1不是改变a的值么…是啊，f2调用的那个f1改变的是f2那个局部变量a的值。也就是说，同一个函数在不同的环境下调用会有不同的行为。
好吧我正在纳闷为什么会有这种东西存在过…囧
作者：Mark Chu-Carroll (aka MarkCC)
翻译：ssword
原文：http://scienceblogs.com/goodmath/2006/11/the_c_is_efficient_language_fa.php
昨天偶然看到一篇关于程序设计语言的文章，直击我G点，忍不住前来吐槽。这篇文章来自greythumb.org，叫做《程序员的呼喊：C\C++该有什么》。
无非也就是“C\C++是追求高效的首选”之类的老生常谈。他们错了。它们不是。C\C++接近硬件是为了直接控制堆栈、修改寄存器等等，而非为了高效。在科研编程或者数值计算的应用上，它们差劲得很。
贴一段让我崩溃的文字：
首先，那些担忧纯属多余。C\C++永远不会消失。为什么？因为有无数的程序现在是、永远都是吃CPU的。对这些领域的编程而言，根本没有快过C\C++的语言。将来会不会出现这种语言？我非常怀疑。
我说的这些领域就是：科学计算、游戏/物理特效、光线跟踪、实时3D图像、音频处理、编译器、高速路由、进化计算(我的最爱:)，还有高级语言运行时—毫无疑问。再就是像操作系统、硬件驱动之类“接近底层”，需要很多交互、甚至内嵌汇编的程序。C就是简单版的汇编，这就是为何C总是作为此类程序的首选。
对这些领域而言，在语言及架构层面的过早优化是可以接受、有时甚至是必须的。我敢打赌，在五十年后，这些领域的一部分依然会是C\C++或者相似语言的天下。对于同样一个基于进化计算指令集的实现，C要整整快过java两倍。由此你可以看出C是多么的快。
问题在这里：C\C++在数值计算上的性能相当扯淡。它们不是最快的，而且绝非偶然。实际上，受底层实现的一些限制，使得C\C++根本不可能表现得很高效。这便是为什么到今天依然有Fortan应用于在高精度科研项目，而这些应用往往需要榨干机器的每一滴性能——如流体动力学模拟。[1]
程序要高效离不开编译器优化，现代架构的编译器可以达到人类优化汇编代码的极限。有时交换两条无关指令的顺序就可以得到一个出人意料的性能提升，而机器所做的优化，很多都是人类难以企及的。[2]
因此对于现代的开发而言，程序的高效绝非只凭程序员一人之力。程序员需要做的，是仔细选择合适的算法—–这活机器做不了；机器需要做的，是仔细地调整指令、约束流水线、内存延时等等。二者合作才会有高效的程序。二者的工作又是相互影响的：程序员应该用机器能够理解的代码来描述算法，以方便机器进行优化。
这就是C\C++失败的地方。C\C++在语义上过度依赖指针，导致不受约束的指针几乎无处不在。在C\C++中，并没有真正意义上的数组——它们只是指针，下标只是指针运算的简写形式（C\C++里的x[n]与*(x+n)是完全一样的）。
过度依赖指针就意味着，C\C++的编译器会很难辨认两个东西是否独立。由此产生的问题被称作“重名探测”（alias detection），也就是找出可能指向同一个位置的两个变量。若存在不受约束的指针，别名探测几乎就无法实现。举个例子：
for (int i=0; i < 20000) { for (int j=0; j < 20000) { x[i][j] = y[i-2][j+1] * y[i+1][j-2]; } }
看下这个循环。它可以并行化或向量化[3]，但前提必须是x与y没有重合、完全无关，这在C\C++中这根没办法得到保证。Fortran-77就没问题，你可以轻而易举地检查它俩是否不同。若是Fortran-98，你还可以检查出它们是否为指针，若有需要，程序就可以弄清楚它们之间是否有重复。在C\C++下，这就做不到（Fortran也不是最好的——一门来自Lawrence Livermore labs 的实验语言Sisal，在特定代码上要强过Fortran 20%）。
这个例子是拿并行说事，但“重名”带来的问题可不只并行这么简单，说并行只是因为比较好解释。“重名”带来的问题直接影响了C\C++代码的编写。
再举个具体的例子吧，我就不吐槽了。六年前，我在一个项目里需要实现一个相当复杂的算法来计算两个数组的“最长公共串”（longest comon sequence， LCS）。计算LCS的标准算法被称作“动态规划”，是O*(n^3) 的时间，O(n^2) 的空间。搞计算生物学的人们也有个相似的算法，时间与它相同，不过空间平均起来只有O(n)。
我不知道该用哪门语言，就做了个实验。我用C，C++，ocaml，java和python分别实现了一遍LCS算法，来比对代码的复杂度
以及运行效率。2000个元素的数组来做实验数据，所得的测试结果如下：
一年以后，我用新版本的JIT再次测试，java的时间减少到了0.7秒，外加1秒的JVM初始化。（C\C++以及ocaml的初始化时间几乎可以忽略不计）
Objective-Caml字节码解释器的执行效率比经过仔细优化的C程序还要高！为什么？因为Ocaml编译器可以辨别出两个数组的无关性——这一来就不必担心循环中的一个迭代会影响到另一个迭代中的值。C编译器可做的优化就要少得多了，因为它无法辨认这些优化是否会影响到程序的正常运行。
不只没有赋值的函数式语言，不那么高效的高级语言在一些方面的性能也要比C\C++出色。CMU Common Lisp在数值计算上就比C\C++强。几年前有个论文写了这个：在一台Sun Sparc工作站上，如果你带上类型声明，用vector（Lisp的数组）和赋值来实现的科学计算/数值计算Lisp代码，要比经过Solaris C或gcc最大优化的C算法实现更加高效。
译者注：
[1] 从一开始Fortran就被设计成可以进行高度优化的语言…Fortran的设计者关注的是科学计算中代码的运行时性能…在这样想法的指导下，只有当Fortran编译器生成的代码性能是有经验的程序员手写的并经过性能调整的汇编代码性能的两倍时，Fortran语言才会被用户接受。 ——J.Backus《the history of Fortran I , II, III》
C最初被设计成有类型的汇编语言，重点针对可用性，而非优化。 ——《现代体系结构的优化编译器》 p147
[2] 为此就需要对指令重新排列，或成为调度，以使相互冲突或依赖的指令在时间上分离，这种需要也就是为现代处理器做编译器特别困难的主要原因之一。 ——-《程序设计语言：实践之路》 p207
[3] 向量化就是将一个循环中的迭代并行执行。
例如：
For I in 1 to 100
A[i]=i*2
End
其中的a[1]和a[2]可以同时执行，前提就是循环中的每个迭代不会相互影响。古代有种机器貌似叫做向量计算机，里面的循环都是并行执行的，就是比较早的并行计算的大型机了。
ps:
作者原文上的评论是相当的长，应了那句“凡语言贴，必火”。 毕竟没有银弹，要了解一个东西也应该了解它的弱点，不然就容易为你爱的东西所束缚。
不过作者貌似回避了一点，那就是所谓“科学计算、游戏/物理特效、光线跟踪、实时3D图像、音频处理、编译器、高速路由、进化计算，还有高级语言运行时”等等，在实际中还是C用的多。“C是接近硬件，而不是为了高效”，不过游戏、音频等方面还有个东西叫做硬件加速哇。对于C在优化上的限制，可以参考《现代体系结构的优化编译器》 418页，上面举的例子可能要更好，说明也更详细，也有一整章C编译器在优化上的解决方法。
pps: 很明显，第一段翻译的很不妥..求正解
学习haskell一段时间了，关于monad等等东西仍停留在理论上的理解而不了解其应用，练下手总是好的。于是参考这个有名的《Write Yourself a Scheme in 48 Hours》和parsec的手册，实现了个简单的语言。只是简单的递归解析语法树，也没有中间编译，也没有垃圾收集，实现起来还是比较简单的。某天天气不错，晴天，就叫它Fineday。
Fineday的语法比较接近javascript（其实一开始是打算搞成basic-style的，可是不会写bnf…囧），有基本的控制流程if，while,for，有匿名函数，有闭包，有数组，有hash—当然，是忽略了许许多多细节的实现，例如没有求数组length的函数，只有puts而没有gets，没有Int类型（开始的时候为了方便一切都是double），没有像样子的错误提示…呵，but it runs.
像下面这段可以算是一个猥琐的oo实现了:
function makeCounter(init){ var this={ 'n':init, 'add':function(n){ this['n']=this['n']+n; return this['n']; } }; return this; } var counter=makeCounter(1); puts((counter['add'])(2)); --3 puts(counter['add'](3)); --6
前几天又翻了下姐姐送的那本《the ruby way》的序，matz谈及ruby语言的设计时提到了“道”，以及编写ruby时的信条：语言应该为人类服务，而不是相反。于是认识到，语言的设计绝非信手拈来的活计，设计中有太多需要斟酌的地方，有太多需要用心思考的地方。我等玩代码的，还是差的太远了。
项目地址：http://code.google.com/p/fineday/
呵，空白的，懒得再写字了。可以用svn获得源代码及编译的exe文件。
作者：Neil
翻译：ssword
原文：http://neilbartlett.name/blog/2007/04/11/haskell-an-imperative-language-with-mutable-state/
Haskell是一门惰性的纯函数式语言，也就意味着其中没有可变的变量。呃，有，没有？看下这个Factorial的haskell实现吧：
fact n = runST (do r < - newSTRef 1 for (1,n) (\x -> do val < - readSTRef r writeSTRef r (val * x)) readSTRef r)
嗯，我可没说这样写好。实际上，这样写很糟糕，一行纯函数式代码就可以漂亮的搞定同样的工作。不过请注意下这代码与命令式语言是如何的相像，如对“可变变量”r的破坏性更新。再贴一下，与同等的C代码做个对比：
fact n = runST (do | int fact(int n) { r < - newSTRef 1 | int r = 1; | int i; for (1,n) (\x -> do | for(i=1;i< =n;i++) { val <- readSTRef r | writeSTRef r (val * x)) | r = r * i; | } readSTRef r) | return r; | }
瞧，你几乎可以把C的代码一对一地翻译成haskell。不过得承认，haskell的语法要猥琐些。
这一切是如何做到的呢？答案就是ST monad，有了它就可以写出有内部状态更新而对外仍保持纯粹的算法。runST函数是亮点，它创建了个初始的空状态，然后执行一系列的状态转换，到最后再销毁它。fact依然是Int->Int的纯函数，依然保留了引用透明。
另一个亮点是那个“for”，看起来跟个关键字一般，不过它本质就是一普通函数，定义如下：
for :: (Int,Int) -> (Int -> ST s ()) -> ST s () for (i,j) k = sequence_ (map k [i..j])
同理，我们也可以定义出foreach，if，while等等。有haskell这般强大的表达力，没必要再将控制流的操作定义为语言的关键字；我们甚至可以根据自己的需求来发明新的控制流程。
不过你看出来了没？没人会正二八经地像上面那样实现factorial。而且，我们真的希望如这般曲解haskell，以取悦从C过来的老程序员么？
是的，问题就在这里。有这项技巧，是为那些已知难以使用函数式风格或递归搞定的算法提供的折衷。同样，很多算法需要用到数组—–有限的内存和固定的访问时间—–使其更易于处理。在ST monad中实现数组很容易，但在传统的纯函数式代码中就要困难多了。（UPDATE：Cale说，纯代码中实现不可变的数组还是很容易的，只有可变的数组实现其来才困难）。
恩，ST monad和STRef表示了外部不可见的局部状态，那么全局的可变状态呢？我们可以用IO monad和IORef做到。当然，在用IO的时候就没有像runST那样回到纯代码的函数了[1]。
对我，这引发的思考就是：haskell是真正的纯函数式语言吗？我觉得不是—–它超越了纯函数式。它是既允许命令式编程，又使用强大类型系统来把有副作用的代码与纯代码分离。这一点，令它强大无比。
[1] 这不是绝对…其实有个方法：unsafePerformIO。不过我觉得应该辩证地讨论它。
To live and not to breathe, Is to die In tragedy.
To run, to run away. To find what you believe.
-Green Day
FeedBurner
Comment