标签 Blogger 下的文章

Common Lisp初学点滴

Common Lisp是一门Interactive语言,比较容易上手。无论你是用CLISPSBCL还是Clozure CL,你都可以很快地写出一个"Hello, World"程序出来。不过千万不要因此低估了Common Lisp,前人的经验表明:Common Lisp是门庞大且复杂的语言,其学习曲线可并不低。要想真正掌握它,需要你有持续的热情、足够的耐心和不断的练习。我接触Common Lisp时间也不长,是个地地道道的初级选手。这段时间看了些书,做了一些练习,这里把我初学Common Lisp过程中的点点滴滴记录下来,以备忘。

俗话说:工欲善其事,必先利其器。Common Lisp开发者们也有着自己一套高效的开发工具。目前无论是在Windows还是在Linux或是其他平台上,最受Lisper们推崇的工具组合是Emacs+ Slime(The Superior Lisp Interaction Mode for Emacs)。鼎鼎大名的Emacs这里就不说了,Slime对于很多非Lisp开发者来说是一个陌生的名字,我们可以把它看成是一种专门为Lisper们提供的一个嵌入到Emacs中的IDE,通过它我们可以在Emacs编辑器中直接进行Lisp代码的求值,编译,宏扩展,符号定义的查找,名字的自动补全以及在线文档查询等操作。我平时开发更多使用的是另外一种编辑神器-VIM,幸运的是已经有人将Slime移植到了Vim下,Slime摇身一变,变成了Slimv(The Superior Lisp Interaction Mode for Vim)。由于接触时间较短,我目前尚不确定在功能上Slimv是否完全等同于Slime。不过就目前来看,Slimv的确让Vim下Common Lisp代码的编写变的高效了许多。

Slimv的安装极其简单:将Slimv包下载到你的$HOME/.vim下(这里以Linux下的安装为例),直接解压即可。Slimv首先为Vim提供了一种名为Paredit Mode(.vim/doc/paredit.txt )的编辑模式,这种模式专门针对Lisp代码源文件,诸如以.lisp为后缀名的文件。该编辑模式保证内容中所有括号、方括号以及双引号均平衡出现,即成对匹配。当你敲入"(",该模式会自动补充对应的")";删除半个括号时,另半个括号也被自动删除。初次使用Paredit mode很不习惯,特别是不知如何在括号的外层再包裹一层括号,也就是将(list 1 2)变为((list 1 2))。每次在(list 1 2)开始处输入"(",都会得到"()(list 1 2)"。后来才在Stackoverflow上觅到答案:原来先输入"\"再输入"("时,Slimv不会自动补充")",通过这种方式可以在括号的外围再加上一层括号了,在Lisp实际编程过程当中,嵌套括号的情况还是很多的。

打开一个名为xx.lisp的源文件,Slimv就会自动发挥作用。在Vim的命令模式下,敲入",c",Slimv会自动启动Swank Server,这个Server运行着一个Common Lisp的REPL,接收并处理嵌入在Vim中的Slimv client端发出的求值、编译、调试等请求,保存你在Vim中与REPL的session内容。Slimv同时会在Vim里创建一个REPL窗口,不过这仅是用来等待你的输入,真正的求值等操作是在Swank Server完成的。

Slimv会自动Detect你已安装的Common Lisp实现,在我的已经安装过Clisp和SBCL的系统中,Slimv优先选择了SBCL。 关于Slimv,这里不再多说什么了,因为其作者已经编写了一份很详尽的Tutorial在这里,有兴趣的朋友可以参考之。

我在读的Common Lisp书籍主要有两本:一本是"黑客与画家"的作者Paul Graham编写的"ANSI Common Lisp",另外一本则是Peter Seibel的"Practical Common Lisp"(据说该书的中文译本已由binghe完成)。这一周多来,我快速地浏览了Peter Seibel的"Practical Common Lisp",除了惊奇于一些之前未曾接触过的特殊语法结构(如Closure)之外,也感叹于Common Lisp的复杂,数不尽的function, macro和special operator让我有些迷失和混淆。另外Peter Seibel自称书中有关macro的例子都很初级,但就是这样初级的macro也是甚难以理解的。关于macro的深入领会,我看只能指望Paul Graham的大作:"ANSI Common Lisp"和"on lisp"了。

另外一本名为"Common Lisp Quick Reference"的小书也值得一看,不过更适合Common Lisp老手查阅手册时使用。

浏览完"Practical Common Lisp“后,继续精读"ANSI Common Lisp",并且对其中的习题也不放过。这些练习估计很初级,不过对于我这个初级选手来说正合适。刚刚看完第二章(Welcome to Lisp),这里将我的习题答案放到这里,供大家批评指正:

练习1.
(a) 14
(b) (1 5)
(c) 7
(d) (NIL 3)

练习2.
[1]> (cons 'a '(b c))
(A B C)
[2]> (cons 'a (cons 'b (cons 'c nil)))
(A B C)
[3]> (cons 'a (list 'b 'c))
(A B C)

练习3.
[1]> (defun my-fourth (x)
          (car (cdr (cdr (cdr x)))))
MY-FOURTH
[2]> (my-fourth '(1 2 3 4 5))
4

练习4.   
[1]> (defun my-max (x y)
         (if (> x y) x y))
MY-MAX
[2]> (my-max 5 6)
6
[3]> (my-max 7 6)
7

以上方案只适用于整数等适用>进行比较的类型,下面是一个更加通用的版本:

[1]> (defun my-max1 (x y comp_func)
         (if (funcall comp_func x y) x y))
MY-MAX1
[2]> (defparameter *cf* (lambda (x y) (if (> x y) t nil)))
*CF*
[3]> (my-max1 5 6 *cf*)
6
[4]> (my-max1 7 6 *cf*)
7
[5]> (defparameter *ccf* (lambda (x y) (if (char> x y) t nil)))
*CCF*
[6]>  (my-max1 #\c #\b *ccf*)
#\c
[7]> (my-max1 #\c #\d *ccf*)
#\d

练习5.
(a) enigma函数的功能是找出list中是否有值为nil的元素,如果有,返回T;否则返回nil
(b) mystery函数的功能是返回x在y列表中的位置(下标)

练习6.
(a) x = car
(car (car (cdr '( a (b c) d ) ) ) )

(b) x = or
(or 13 (/ 1 0))
注:短路求值,后一项在13为t的情况下不被求值,避免了divide by 0错误

(c) x = apply

注意funcall与apply的区别
(funcall function arg1 arg2 …)
==  (apply function arg1 arg2 … nil)
==  (apply function (list arg1 arg2 …))

练习7.
(defun have-list-param-p (x)
  (let ((result nil))
    (dolist (obj x)
      (if (listp obj)
        (setf result t)))
    result))

[1]> (load "list_param.lisp")
;; Loading file list_param.lisp …
;; Loaded file list_param.lisp
T
[38]> (have-list-param-p '(1 2 3))
NIL
[39]> (have-list-param-p '(1 (2 3) 4))
T

练习8.
(a)
iterative solution:
(defun print_dots (number-of-dots)
  (do ((i 1 (+ i 1)))
    ((> i number-of-dots))
    (format t ".")))

recursive solution:
(defun print_dots (number-of-dots)
  (let  ((i number-of-dots))
     (if (> i 1)
        (print_dots (- number-of-dots 1)))
     (format t ".")))

练习9.
(a) 问题所在:remove返回一个新的lst,原来的lst如果包含nil,则+会提示nil is not a number
修改后:
(defun summit (lst)
  (setf lst (remove nil lst)) 
  (apply #'+ lst))

(b) 问题所在:导致无穷递归,提示Program stack overflow. RESET
修改后:
(defun summit (lst)
  (if lst (+ (or (car lst) 0) (summit (cdr lst))) 0))
     
Common Lisp与Haskell不同,Common Lisp并非纯函数式编程语言,其中包含了诸多命令式(imperative)的元素,这样对于习惯了命令式编程的初学者来说,在学习过程中就不会感觉到过于剧烈的思维跳跃了。

偿还N年前的一笔技术债

记得刚来公司时曾参与过一个项目,项目中用到了部门基础库中的一个B+树接口。不过在程序调试过程中我们发现可执行程序总是dump core(在sparc solaris上),经初步分析,断定问题就出在B+树接口处,但一时又找不到问题原因。还好这个B+树的实现者就坐在我的旁边。他分析后告诉我:这个B+树接口要求用户自定义的索引结构体的size应该为4的整数倍。按照他的说法,我为结构体打了padding,以满足结构体size为4的整数倍的要求。修改后果然不再dump core了。当时项目进度紧,我也没有求甚解,这件事也就过去了。

一晃N年过去了。今天在做程序的64位移植过程中我再次遇到了这个问题。问题的表象就是程序运行时dump core,通过gdb或pstack查看core的内容,发现程序是在B+ Tree初始化时出的core。显然这又是一个内存违规访问的问题,且在Sparc上出现(x86 Linux上运行正常)十有八九与内存对齐有关。

B+ Tree出问题首先让我想到了N年前的那个解决方法。我先查看了自定义的索引结构体(usr_idx):

struct usr_idx {
    unsigned int usr;
};

不过sizeof(usr_idx)无论是32bit编译还是64bit编译,其值都是4。那按照B+树原作者的说法,这显然不足以让B+树出现问题。事实也的确如此,32bit编译的程序在Sparc Solaris下运行良好,只是目前改为了64bit编译,才dump core,那问题到底出现在哪呢?

到这里,我也只能从代码着手了,把N年前没弄清楚的原因找出来,顺便也把这个存在了N年的Bug彻底解决掉,把这笔技术债还了。pstack的输出告诉我问题出在一个名为bptree_create_node的函数中,嫌疑最大的一处代码大致是这样的:

for (i = 0; i rank; i++) {
    (elem_base(tree, tmp_bn, i))->key = key_base(tree, tmp_bn, i);
    (elem_base(tree, tmp_bn, i))->pointer = NULL;
}

直觉告诉我问题出在elem_base这个宏里,elem_base的定义如下:

#define elem_base(tree, eb, index) ((xx_bptree_elem*)((char *)&(eb)->e_base.mw_cp + ((SIZEOF_bptree_elem + (tree)->keysize))*(index)))

很显然这个定义最终是想得到一个xx_bptree_elem*类型的指针。从内存地址角度来说,我们会得到了一个内存地址,且这个地址被认为是一个xx_bptree_element元素的起始地址。那么是否所有地址作为xx_bptree_element元素的起始地址都合法呢?答案是不一定,至少在Sparc平台上不是所有地址都可以作为xx_bptree_elem的起始地址的。

那么什么样地址可以作为xx_bptree_element的起始地址呢?在Sparc上这取决于结构体的对齐系数。xx_bptree_elem结构的定义如下:

union mem_word {
    void  *mw_vp;
    void (*mw_fp)(void);
    char  *mw_cp;
    long   mw_l;
    double mw_d;
};
typedef union mem_word mem_word;
#define SIZEOF_mem_word (sizeof(mem_word))

struct xx_bptree_elem {
    void       *key;
    void       *pointer;
    mem_word   base;
};
typedef struct xx_bptree_item xx_bptree_item;
#define SIZEOF_bptree_elem        (sizeof(xx_bptree_elem)-sizeof(mem_word))

在32bit编译的情况下,系统默认对齐系数为4(参见/usr/include/sys/isa_defs.h中的宏_MAX_ALIGNMENT),则该结构体的对齐系数 = min(max(sizeof(key), sizeof(pointer), sizeof(base)), 4) = 4。这样xx_bptree_elem在32bit下的有效起始地址为可被4整除的内存地址。

而在用64bit编译时,系统默认的对齐系数为16(同参见isa_defs.h),但由于xx_bptree_elem中size最大的字段(base)的size为8,则结构体的对齐系数就等于8。即xx_bptree_elem元素的有效起始地址为可被8整除的地址。

好了,我们再回过头来看看elem_base宏在不同编译情况下能否总是返回合法的地址。

#define elem_base(tree, eb, index) ((xx_bptree_elem*)((char *)&(eb)->e_base.mw_cp + ((SIZEOF_bptree_elem + (tree)->keysize))*(index)))

这个宏中有三个元素决定返回地址,分别是"基址":&(eb)->e_base.mw_cp、偏移量SIZEOF_bptree_elem和(tree)->keysize。其中基址是另外一个结构体xx_bptree_node中一个mem_word类型字段的地址,你知道的,mem_word这种手法可以保证其起始地址严格按照其内部最大字段的对齐系数对齐的,也就是说mem_word的对齐系数与double的对齐系数一致,即无论是32bit编译还是64bit编译,其对齐系数都是8,也就是说我们可以确保这个”基址“是可以被8整除的;至于偏移量SIZEOF_bptree_elem,我们可以直接可以得出其大小:

32bit下,SIZEOF_bptree_elem = 8
64bit下,SIZEOF_bptree_elem = 16

可以看出无论是32bit还是64bit编译,SIZEOF_bptree_elem的值都是8的倍数;显然这两个值都不会影响elem_base最终返回地址的合法性。

现在剩下的就是(tree)->keysize了。keysize是由xx_bptree_init接口传进来的,它在上层实际上就是用户自定义的索引结构体的大小,显然这个大小不一定就是8的倍数。在我们的系统中,keysize = sizeof(usr_idx) =
4。这个keysize在32bit编译下是没有问题的,因为32bit编译只需要elem_base返回的地址可以被4整除即可,这也是为什么我们的程序在32bit编译下运行正常的原因。回想一下N年前的那个问题,其真正原因也就在这里:当时我定义的索引结构体的大小无法被4整除。在64bit编译下,keysize显然不能满足被8整除的要求,导致elem_base返回的地址只能被4整除。而xx_bptree_elem这个结构体的地址是严格要求必须可被8整除的。将一个只能被4整除而不能被8整除的地址强制转换为xx_bptree_elem元素地址并通过该强制类型转换后的地址访问xx_bptree_elem内部的元素显然就会导致core的出现了。

现在看来当初我的同事并未真正理解该B+ tree为何要求用户自定义结构体的大小必须为4的整数倍了,他只是通过现象得到了那条经验罢了,这笔技术债务也就从那时留了下来。

解决该问题并不难,作为基础库,我们无论如何都不应该依赖用户的自觉,我们在接口实现中增加一个转换就可以解决这一隐藏了若干年的Bug,将外面传入的keysize经align_word转换后再赋给tree->keysize,这样就可以保证elem_base始终返回合法的地址了。

突然想起了那句话:”出来混,总是要还的“,我们欠的技术债务也不例外。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats