dram.me

Prolog的回溯(backtracking)

作为Prolog的重要概念,回溯在Prolog中有着至关重要的作用。

回溯的最直接体现是在交互模式中,如果可能存在多个联合结果,Prolog会提示是否需要查看其他符合条件的值,其他可能值就是通过回溯得到的。

在脚本中Prolog默认只尝试获取一个联合的结果。更多的值需要通过fail\+等机制主动触发回溯以获取。另外cut(!)可用于删减结果,可以形象得理解为园丁修剪枝叶,去除不必要的分支。如果分支存在,那么一旦子分支中出现匹配错误,并且父层或更高层级choice point存在的话,回溯将会被出发。

针对fail和cut有一个细节,可以加深对于回溯的理解。在一个Stack Overflow的回答中提到,!, fail的模式可用于强制失败,这是先修剪掉所有分支,再显式出错,这时Prolog没有其他choice point,只能得出匹配出错的结果。

urllib3与requests的API设计比较

Python应用最为广泛的HTTP客户端库为requests,这是广为人知的工具库。而urllib3则是requests实现的基石,这个库知道的人不多。

从对两者的比较中,可以发现在功能定位以及API设计中的考量有比较大的差异。

如果从分层结构上考虑,假设Python标准库作为最底的第一层,urllib3大体落在一层,更严格的界定的话可以作为1.5层。考量的因素主要是urllib3总体没有全面覆盖标准库的功能,上层应用在使用时需要借助jsonencodingurllib2等库结合urllib3使用才能完成任务。

但requests则不同,它基于urllib3以及其他标准库封装。在日常使用中,很多时候不需要关注编码、序列化等问题。

可以拿UNIX的 KISS哲学与systemd的不同作为类比。urllib3只做单一的事,而requests则有一种大一统的想法。

urllib3的模式虽则在使用时会显得比较啰嗦,但可以更加灵活地加以应用。并且将部分合理的复杂性暴露给开发人员,有助于增进对系统的理解。对系统的深入理解的益处在排查问题以及应对特殊需求时最能得以体现。

从这一例子中也可以发现,虽然在软件设计中,分层有其非常重要的价值,但过多的不合理的层次也会增加系统的复杂性。

另外一点需要注意的是,urllib3的模式有更低的学习成本,举例来说:urllib3对响应体不做任何处理,所有处理方式由调用者指定,开放人员可以结合自己已有的对json模块的理解组合使用。而对requests则需要了解如何通过不同的参数控制其对响应体的处理。

Prolog的核心概念

Prolog最核心的概念,我觉得是联合(unification)和回溯(backtracking)。从另一个角度说,是选择以及基于选择的遍历。

例如联合产生选择(choice points),而disjunction()和conjunction()分别可以增加和减少选择,cut(!)可以删减选择。

对于遍历,failtrue\+可用于控制backtracking。

所以说,Prolog最核心的机制就是对选择树的遍历。

Smalltalk的可扩展性

Smalltalk由于没有关键词,所有的语言结构都由统一的消息语法定义,可扩展性极强。

比如在Blue Book p.34提到,Smalltalk有ifTrue:ifFalse:消息,也有单分支的ifTrue:ifFalse:。如果需要去除单分支判断(用函数式编程的思路考虑,ifTrue:ifFalse:并不建议使用),在Smalltalk中,只需要删除Object>>ifTrue:ifFalse:即可(前提是未被使用)。而在有些语言中,复杂度则大大增加。原因有两点:

  1. 这些语言分支判断一般在解析和编译阶段,代码有一定复杂度;

  2. 这些语言的解析器和编译器一般不能方便修改。

从中可以看出Smalltalk语言的极大的灵活性。

另外一点,现在新近的语言大都有迭代器的概念。是为增加循环语句对用户自定义数据类型的支持。而在Smalltalk中,只需要针对那些数据类型定义相应的方法就可以了。详见Blue Book p.36中对do:的说明。

Smalltalk的面向对象与消息语法结合的灵活性还有一点,分支语句必须是Boolean类型,没有了其他语言中真值假值定义模糊的问题。

二元运算符优先级

对于二元运算符的优先级问题,在程序语言处理上,一般有这样几种情况:

  1. C语系,定义有复杂的优先级;

  2. Smalltalk,所有二元运算符有相同的优先级,解析从左到右(详见Blue Book p.28);

  3. Self,所有二元运算符有相同的优先级,解析时如果不同运算符连续使用,必须用括号标定;

  4. Prolog,运算符优先级可完全自定义(Prolog中大量语言结构以运算符模式呈现)。

如果考虑自定义运算符的情况,除去算术运算之外,还需要考虑运算符承载其他功能时的呈现。这种情况下,Smalltalk模式从左到右的阅读比较自然。Prolog模式有最大的灵活性,但不便于记忆。而Self模式在多类运算符混用时则需要大量的括号。

当然,Self模式的优点也非常明显,可以规避优先级理解错误导致的问题,比如1 + 2 * 3这样的表达式在Self中是不合法的。

← older posts