读书记录之《计算的本质》

之前读龙书,读到自动机的时候就完全渐渐就不知所云了。后来试着看看其他类似的书,比如虎书、鲸书,最后统统都放弃了。

最近看了《计算的本质》,感觉看着还不错,简单的解释了龙书里的部分概念,还有一部分SICP的内容。

这本书主体分两部分,第一部分主要是基础的语法语义分析和自动机、下推自动机和图灵机;第二部分是一些图灵等价的机器,比如labmda、SKI、IOTA之类演算,同时还有些机器极限和抽象的讨论。

从小步语义、大步语义开始,一直到语法分析,计算的本质到底是什么?

继续阅读

探索Ruby正则表达式算法(译)

来源:Exploring Ruby’s Regular Expression Algorithm(2012)

ps. 业余翻译的,求轻拍。有什么问题可以直接指出。

大家都熟悉正则表达式,它是开发者的“瑞士军刀”。不管你想查找哪种信息,解析哪些字符串,总有一种正则表达式适合你。事实上,你可能用过很久的ruby所使用的正则表达式了——正则表达式已经被集成到几乎所有主要的语言中好多年了:Perl、javascript、PHP、Java等等。ruby支持是在90年代中期,而正则表达式是在60年代中期发明的,早了30年。

但是正则表达式是怎样工作的呢?如果你对正则表达式引擎后面的计算机原理感兴趣的话,可以读一下这三篇Russ Cox写的极棒的文章:

在这里我不打算重复Russ的内容。但是我准备在第二篇文章中快速的解释一下ruby所使用的“无递归的回溯实现”, 这意味着它可能也会像perl正则表达式一下慢吞吞。就是说,这意味着Ruby并没有使用目前最主流的正则表达式实现方法——Thompson NFA,也就是Russ第一篇文章中所描述的。

今天我们细看一下Oniguruma,也就是Ruby所使用的正则表达式引擎。我们使用一些插图来表现一些简单的正则示例,以此来弄清楚在使用正则的时候是Ruby内部是如何工作的——它比你想象的要复杂多了。

继续阅读

又一次更换域名

这次,我又换了域名,目前lunae.cc会跳转到新域名。

blog.of.vin

由此带来的不便,十分抱歉。

前几天主机忘记续费,导致关机两天左右,我也是醉了。。

———— 分割 ————

2016年,博客更新次数算是屈指可数了。或许是因为内心不够平静,也或是真的到了瓶颈。

这些时光走来,常去的博客渐渐都关门大吉,变成孩子狂欢后丢弃的玩具。我这无人问津确常折腾换名的博客居然还幸存下来,变成一个仅供自己娱乐的微小记号。

Hello,2017。

osx下vagrant box add因curl失败的问题

前几天vagrant做box add的时候发现加不进去,报以下信息:

给vagrant加上debug看看调试信息,这样就知道是什么原因导致的了:

下面是一部分调试信息:

里面说

问题应该就在这里了,curl用不了。这个curl用的是vagrant自带的,需要比较高的lib版本(9。0.0),但是osx里的lib老了点(7.0.0)。

解决方法很简单:只需要把vagrant自带的curl删掉或者移走就可以了。

然后再执行一下box add就解决了。

参考:mac OSX Sierra, can't add vagrant box laravel/homestead, due to needing cURL v 9.0.0 or later, and libcurl.4.dylib providing v7.0.0

好吧,又瞎折腾

昨天把dns服务器从dnspod迁走,结果在新dns服务商那里填错了配置……

现在我还绑着hosts写的这篇博客……

现在配置已经正确修改了,我想很快就会生效了。

这一天多访问带来的不便十分抱歉。

后记:奇怪,nginx偶尔会返回400,粗略看了一下,后台没日志,回头细看。

半年

很久没有更新博客了。

随着工作的深入,可以追寻的技术也越来越模糊,技术类的文章越写越来越少,也越怕误导人。

干脆出了一趟远门,看看外面的路,也看看前面的路。

离职时朋友说:“相信我,你想也想不出什么结果。”

时光慢慢流淌,从嫩绿深绿变枯黄,秋天也快过完了。

路依旧,人也依旧这样。

还好,生活也是这样。

IMG_1066IMG_6530IMG_7408IMG_0006IMG_0500IMG_9484

mail core2编译脚本执行失败的问题

今天编译mail core2的时候发现curl一直下不回文件,导致编译失败,错误如下:

应该是curl下载失败了。

自己手动执行了一下curl命令,或许是我的curl版本有问题,下回来的文件大小为0。

用curl -I 拿回来的头Content-Length并没有什么问题,状态码也是200。

或许是网络问题,或许是curl的bug,curl版本 7.43.0。

既然没查出原因,就先绕条路,把curl下载改为wget(mac需要额外安装,使用brew就可以),把mailcore2项目scripts/include.sh目录下的build-dep.sh(约325行):

替换为

再编译,就通过了。

至于curl无法通过的原因,待查。

两个PHP代码片段

最近有同事碰到两个问题:

这段代码输出什么?

这段呢?

第一个代码输出true,原因在于in_array使用了==的逻辑(如果第三个参数为true则为===的逻辑),不知道这样是否合理。源码中php将字符串转成了数字,转不了则返回0。(以上测试版本为5.5.30和7.0.0)

第二个代码输出:

因为第一次使用了引用,引用计数不释放,引用的地址是数组中c的地址。第二次循环对$m赋值的时候,不停的修改了$m指向的地址,数组中的地址也就发生了变化。赋值的源码位在于zend_execute.c/zend_assign_to_variable方法中。

红黑树

红黑树是一种很常用的自平衡二叉树。之前写过二叉搜索树,我们知道二叉搜索树查找速度是由树的高度决定的,但是因为二叉搜索树对树的平衡没什么限制,如果所有节点都在一个叉上,就变成了链表了。红黑树作为二叉搜索树的同时,用以下五个性质保证了树的平衡:

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

因为这些性质,一棵红黑树尽量保持每个路径上节点数差距不大,从来保证了树的查找速度。

红黑树

红黑树是一颗二叉搜索树,其查找方法自然也就是二叉搜索树的查找方法。因为给二叉搜索树节点涂了颜色,树上面的修改操作(如插入、删除)会影响红黑树的某些性质,恢复其性质需要需要O(log n) 次操作。

继续阅读