RSS Feed

Posts Tagged ‘lisp’

  1. Macro

    December 20, 2014 by xudifsd

    A few month ago, I wrote a Clojure macro, looks like this:

    It means if current env is test, then generate normal function, otherwise generate async function and log the error if catched. We need this because when we call some functions, we don’t want to wait them to return, but we still want to catch their exception and log it. But when in test env, we want them to throw exception to make error more obvious. We determine env by environment variable, and default to test env if not provided.

    After I finished this macro, and kicked it online, everything seems fine. But somehow I recall this macro while I was doing something else, and found it has a bug that is difficult to detect. The bug stems from the way I treat it as normal function instead of macro.

    Because macro expansion happens at compile time instead of runtime, this macro needs env variable at compile time, otherwise it will generate normal function. But normally we won’t set env variable at compile time (lein jar), and only set env variable at runtime, because normally env variables only take effect at runtime. So we didn’t get async function online at all, they’re all normal functions. Solution for this is simple, just set env variable before compile.

    This kind of problem is hard to find, because no matter what function we get, the behavior is identical, just a little bit slower.

    It seems mastering macro is not that simple. But macro is less mysterious to me now, when I was reading , macro is something I can’t understand, because the book tells all the goodness about macro without telling any principle about it, this just makes it mysterious, but after you understand all the principle, it’s just a tool to generate code for you, the goodness is you can use normal function in macro just like in other function, but actually macro is not as flexible as function sometimes: they can’t being passed as value.

    Now, I’m quite understand the rule for macro: “don’t write macro if you can”.


  2. 关于Typed Clojure

    August 17, 2014 by xudifsd

    最近一直很忙,都没空写什么东西了。今天终于闲下来了一些,现在正值今年GSOC项目要结束,而且国内关于Typed Clojure的资料少得可怜,所以写点东西介绍一下。

    Typed Clojure

    Typed Clojure的作用就是给Clojure语言提供一个可选的类型系统,以获得与静态类型语言同等的类型检查能力,但是这种能力的获得仍然是需要一定的代价:那就是使用者需要为每一个全局变量以及函数都加上类型注释,现有的类型可以见项目的wiki。不过它确实能完成对Clojure的类型检查,甚至包括对nil或者java null的捕捉,这一点还是很帅的。

    感兴趣的话可以看作者Ambrose在Clojure conj上的介绍视频(需翻墙),这个介绍讲的还是很清楚的。Typed Clojure完全通过Clojure的宏来实现,而不需要特殊的解释器或编译器,这也是Lisp类语言最大的优势,试想如果需要给python加一个类型系统,不自己重写个解释器是不可能。

    Typed Clojure受Typed Racket的影响很大,很多理念都是借鉴自他们,甚至我今年的实现内容也受到他们的影响。就健全性来说Typed Racket要优秀很多,因为Typed Clojure现在就只有Ambrose在维护,贡献者也很少。而Typed Racket就有点像是一个学术项目了,它们的贡献者以及维护者大多是Northeastern University PLT实验室的博士或博导,他们大多会在这上面发论文,比如这篇介绍,就说“Typed Racket is not just a nice language … it’s also informing PL research at every level”。

    我的工作

    我今年GSOC的内容就是给Typed Clojure类型系统添加两个函数类型,让Clojure中一些特别奇葩的函数也能使用first class type做类型标记而不需要在类型系统内部特殊处理。这些奇葩的函数就包括assochash-map。因为这两个函数对参数还有特殊的要求:因为都是操作map的,所以要求接收的参数与返回值map的key和value的类型匹配,而且也要求参数是成对出现的。

    Typed Clojure已经有了和Typed Racket类似的dotted type variables,这种类型已经可以用来表示不限参数个数的、任意类型的函数,并在结果上对参数类型加以限制。但是却无法表示要求参数成对出现,所以之前Ambrose的想法就是提供一个类似...2这样的语法来表示参数成对出现,不过这种做法有点类似将参数写死在类型系统里,如果之后出现了要求参数成三个出现,则又必须提供...3这样的语法。

    在与Typed Racket的人交流后,我们决定使用最lisp的方式解决——使用list。简单来说就是给list类型加上一个:repeat这样的属性,让:repeat的list可以匹配与它长度成倍的list,例如,(HVec [Number String] :repeat true)可以匹配(HVec [Number String])以及(HVec [Number String Number String])之类的,并且给函数类型加上<*以及<...这样的语法,意思是将多出来的参数捕获并与它之前的类型进行匹配,它之前的类型一般是有:repeat属性的list,这样就很好地解决了写死参数的问题——多给list内部加一个类型就能支持参数成三个出现的要求了。

    如果对细节感兴趣的话可以看下我写的关于我的实现细节以及Typed Clojure类型推导的文档

    Typed Clojure现在仍然很不成熟,从版本号(0.2.66)就可以看出来,现阶段已经可以在一些小的项目中使用了,但是我觉得在真正的生产环境还是最好不要使用,首先一个原因就是它的类型检查还是比较慢的,再者就是他的硬伤——学习成本,需要在项目中使用就需要完完全全学会它的类型注释。

    如何向Clojure贡献

    Clojure以及任何Clojure官方库的贡献都要求签CA,以前还必须是纸质信件邮寄到美国,现在终于支持电子版了,内牛满面。不过签完CA后还不能通过github的PR进行贡献,必须通过Clojure的JIRA提交patch。这确实有点麻烦,但是Clojure也是通过这种手段保证不会有有版权代码的进入。

    如果想要给Clojure或它的官方库贡献代码的话可以从它的JIRA中的issues下手,因为那里一般都是一些实现的bug,会有比较清晰的思路着手,并且能在这个过程中熟悉原有代码结构。

    关于开源

    今年参与Typed Clojure觉得最大的收获就是了解了下国外的开源是怎么运作的,我觉得这中间最重要的就是sponsor扮演的角色。很多项目开发者要不就是兼职开发开源项目要不就是全职开发了,比如我的mentor Ambrose就是全职在开发Typed Clojure,但是收入从哪来呢?就是通过sponsor,比如他就通过国外的众筹来筹得一些项目经费。

    甚至在Typed Clojure还没开始时,sponsor就在扮演很重要的角色了,见。Ambrose就是这样参加了那次Clojure conj,并在这个会上介绍逻辑编程,在会下和别人交流时别人提到有类型系统的需求,然后Ambrose才开始着手实现Typed Clojure的。

    国内貌似还是没有这样的捐助气氛的吧。


  3. 两种基本的GC方法和他们的关系

    March 19, 2013 by xudifsd

    垃圾收集是高级编程语言最重要的一部分,不过垃圾收集是否值得也要看具体应用,我就很同意这个观点。最近写了个玩具lisp解释器,由于不想自己去管理所有内存,所以用了libgc库,也顺便了解了下GC的一些技术。

    而对于垃圾收集有两种最基本的方式:reference counttracing。更多的变种见

    Reference Count

    reference count是最简单垃圾收集的方法,内核的代码就是手工模拟该算法的,而一些有虚拟机的语言就直接使用了该算法,例如CPython

    reference counting example

    如果使用引用计数方法,那么所有的在堆上的对象都会多一些空间用于记录对该对象的引用数,见上图。并且该方法需要编译器或者解释器的特殊支持,否则上图中m = l语句和l->next = n语句就无法修改对象的引用计数(所以C中没有使用这种算法的库)。并且RC方法有个最不好的一面就是无法收集环状的垃圾。例如以下语句:

    struct intlist *j, *k;
    j = alloc();
    k = alloc();
    j->next = k;
    k->next = j;
    j = k = NULL;

    在以上语句执行完后在堆上应该没有任何东西,但是之前j和k所指向对象的引用计数却都是1(因为互相指向对方),所以单纯的引用计数的方法无法收集环状垃圾,这是它致命的缺点。它还有个缺点就是效率不高,因为每次对指针进行修改和赋值甚至以指针为函数参数都需要修改引用计数,这样的效率是很低下的。不过它的好处就是一旦有垃圾就马上收集,可以用于内存紧张的地方,不像Google的V8引擎这么耗内存。

    Tracing

    Mark and Sweep算法

    另一种方法是通过探测哪些堆上的对象再也无法被引用来进行垃圾收集,由McCarthy(Lisp创造者)提出。它的基本理念是:从“根”开始遍历所有能被根引用的对象,并进行标记,完成后再遍历所有堆上的对象,那些没有被标记的对象就是无法被程序引用的垃圾,可以将他们回收。这就是Mark and Sweep算法,见上图。

    但是该算法有个麻烦的地方就是需要找出“根”。所谓的“根”就是可以引用堆上对象的指针,所以程序需要扫描整个程序的bss段,data段和stack段,并找出那些看上去像指针的值(所谓看上去像就是值在堆的地址空间内,并且符合一定的对齐标准)。这样需要扫描的实现就叫保守式gc,因为它并不精确定位每个指针,这种实现方法就非常适合做C语言库。最出名的库就是Boehm-Weiser GC,它的实现有两个优化:

    1. 将堆置于内存的高地址,这样很少会有程序的整型值会是合法的堆地址。
    2. 假设所有符合对齐的值就是堆地址

    这种Tracing的方法可以避免reference count算法所无法识别的环状垃圾,所以某些reference count算法会有些优化来识别环状垃圾,而这种优化就是使用和tracing类似的方法。

    两种算法的关系

    这样初看起来两种算法似乎没有什么关系,但是这篇论文(感谢lisp聚会上的liancheng提供)提到了这两种算法共享了一些最基本的结构。而其他所有GC算法只是为了时间或空间上的trade-off而结合两种算法。

    实际上,这两种算法最终都是要求出每个对象的精确引用计数(可以将tracing算法的标记当作退化了的引用计数),只是tracing算法倾向于低估对象的引用计数(在mark阶段初始化为0),而rc算法倾向于高估对象的引用计数(被引用计数为0的对象引用的对象的RC高于真实的RC)。并且tracing算法跟踪“活”对象的引用计数,而reference count算法跟踪“死”对象的引用计数(一旦某对象的引用计数为0就递归减少所有该对象引用了的对象的引用计数)。

    所以所有的GC算法的最终不同就是存储区域的划分和维护真实RC的方式的不同,在做出这些设计决定后就只是一些空间、时间的trade-off了。


  4. 关于lisp解释器

    September 28, 2012 by xudifsd

    在上个月重新看了《SICP》第四章后觉得写个lisp解释器也不是很困难,甚至我发现只要理解了其中的原理整个解释器其实非常简单。我觉得书中理解原理的关键一段就在4.1节

    The metacircular evaluator is essentially a Scheme formulation of the environment model of evaluation described in section 3.2. Recall that the model has two basic parts:

    1. To evaluate a combination (a compound expression other than a special form), evaluate the subexpressions and then apply the value of the operator subexpression to the values of the operand subexpressions.

    2. To apply a compound procedure to a set of arguments, evaluate the body of the procedure in a new environment. To construct this environment, extend the environment part of the procedure object by a frame in which the formal parameters of the procedure are bound to the arguments to which the procedure is applied.

    These two rules describe the essence of the evaluation process, a basic cycle in which expressions to be evaluated in environments are reduced to procedures to be applied to arguments, which in turn are reduced to new expressions to be evaluated in new environments, and so on, until we get down to symbols, whose values are looked up in the environment, and to primitive procedures, which are applied directly.

    也就是说eval和apply是相互递归的,eval会调用apply去产生结果,而apply会调用eval解释整个程序的子句。

    apply的基本作用就是在调用函数之前创造出一个环境帧,这个帧中包含解析函数子句所必需的变量绑定,而被apply调用的eval会在这个新的环境中解析函数子句。

    而eval则是负责在环境中查找符号的绑定,根据表达式中的第一个符号的内容(也就是表达式的operator),来决定下一步行动,如果是普通函数则调用apply,如果是宏则调用macroexpand,宏扩展之后再调用eval去解析扩展后的表达式。这样说可能有些难以理解,具体可以看我以前写的一篇关于lisp环境帧的文章。在理解了这个原理之后再看SICP的就好理解了。

    总的来说,整个解释器也就这些东西了。而且由于lisp基本上都内置了read函数直接返回读到的表达式,而且由于表达式就是列表,所以用lisp来解释lisp简直没什么技术含量,所以我也就花了几天时间就写出了个lisp解释器。我实现的基本上是scheme的函数,并且支持call/cc,不过宏却是CL类的宏,因为scheme的宏虽然干净但是感觉还是太难用了,还是觉得defmacro用起来舒服,所以我也就只实现了defmacro宏。

    关于lisp解释器

    虽然lisp版的解释器已经实现了,但是完成后却发现没什么技术含量,不过由于使用高阶语言完成了一个项目,那么整体的思路也已经掌握,所以我还是想用C实现一个解释器,这样一想其实会多很多工作量:内存管理,垃圾收集,符号查找,链表的读入等这些在lisp实现中完全不需要考虑的细节全部冒出水面了。

    不过即使是使用高阶语言来实现我也发现自己对难度的判断有些错误(看来别人说的“要把程序员估计的困难提高几个数量级才能得出正确值”是对的):本来以为call/cc实现起来非常困难,但是实际上直接使用原生的call/cc就能非常轻松地把这个功能提供给使用者。就算是使用C实现起来也不会困难,只是一个setjmp和一个longjmp而已,但是实现之前想做的的干净宏却异常困难,最后不得以,只能拿CL的defmacro(由于没有支持gensym,所以一些高级宏没办法支持)的语义来充数了。

    如果有人对lisp实现感兴趣以下是一些提示:

    这个解释器所支持的语法虽然混合了CL的和scheme,但是只能由scheme解释器当宿主解释器。推荐使用chicken scheme,因为我用的就是这个,使用时直接用csi main.scm就能进入repl,现在支持的一些函数和基本语法见eval.scm和setup.scm,其中setup.scm中直接导入了宿主解释器的基本函数,还定义了let和cond宏,这样你也可以照着写一个由scheme来解释的CL宏(个人觉得好帅)。

    关于C实现的lisp解释器

    基本功能已经在lisp实现中实现了。但是我仍然想用C来解释lisp,这样更有挑战性也更有意思。准备实现的基本解释器其实应该算是个库,它提供接口让所有链接到该库的软件可以直接解释lisp,这个接口应该包括:

    • 允许让用户自己加入primitive procedure:比如库本身不提供打开文件的接口,但是应该允许用户自己拿C语言实现这个函数,并能将其加入到环境中就好像库本身提供一样,这样用户可以自己扩展该库而不需要改变库。
    • 提供类似eval-string的C语言接口,让用户可以eval外部提供的lisp语言。从这个意义上来说:repl本身就是该库的一个thin wrapper。

    希望最终能完成这个项目,现在还有很多的困难需要克服,最大的困难就是garbage collection,实在不知道应该怎么解决这个问题,还需要调查很久,而且一旦这个地方出现bug将会非常难找到。而性能问题也将是一个头痛的问题,因为从来没写过一个性能需求很高的软件,很多次的优化最终常常被证明还不如不优化。所以,成品估计也只能当作是一个勉强能用的东西吧。


  5. SICP练习题1.45——求n次方根

    December 19, 2011 by xudifsd

    SICP》第一章最后有个练习非常有意思:求n次方根。书的第一章几乎用了所有的篇幅来讲一些算法和抽象,并且在第一章第一节就说到了用牛顿迭代法来求一个数的平方根,在第一章最后一节的练习中要求一个数的n次方根。

    根据书上前面几节的说法,求x的平方根就是求函数y->x/y的不动点,而不动点的求法就相当简单了,随便猜一个数带入函数,如果结果不好再将结果带入函数,最终函数总会得到不动点。但是如果直接这样求平方根会有一个问题:函数并不收敛(假设最开始猜y,那么带入函数会得到x/y,将结果再带入函数又得到y),补救办法就是使用一个叫average damp的方法(实在找不到中文的翻译,直译过来就是平均阻尼),average-damp可以直接用下面函数定义出来:

    (define (average-damp f)
        (lambda (x)
            (average x (f x))))

    这个函数的作用就是取函数返回值和函数参数的平均数,这样先对y->x/y这个函数取average damp,再对结果取不动点就能得到平方根了。我们也能用同样的方法取一个数的三次方根,只要将函数换为y->x/y2即可,但是对于四次方根无法得到结果,原因也是不收敛,而解决办法竟然是对原始函数取两次average damp。题目要求我们做实验得出为了取n次方根而必须取average damp次数的规律,这样我们可以定义下面的函数:

    (define (fixed-point f guess)
     (define (close-enough? a b)
      (< (abs (- a b)) 0.0001))
     (let ((guess-value (f guess)))
      (if (close-enough? guess guess-value)
       guess
       (fixed-point f guess-value))))
    
    (define (repeated f n)
     (define (iter f n result)
      (if (< n 1)
       result
       (iter f (- n 1) (lambda (x) (f (result x))))))
     (iter f n identity))
    
    (define (average-damp f)
     (lambda (x)
      (average x (f x))))
    
    (define (average a b)
     (/ (+ a b) 2))
    
    (define (square x)
     (* x x))
    
    (define (nth-root x n)
     (fixed-point
      ((repeated average-damp 2)
       (lambda (y) (/ x (expt y (- n 1)))))
      1))

    其中fixed-point需要一个函数f,和一个最初的猜测数,返回满足要求的不动点;而repeated将带入的函数f迭代n次。
    实验结果如下:

    #;1> (nth-root 8 3)
    2.00003461276416
    #;2> (nth-root 128 7)
    1.9999526734277

    但是一到8次方根以上程序便会在两个数之间跳转,因此需要再将函数average damp一次,而函数到了16次方后又需要average damp一次。这样看基本上得出了规律:只需要将所求的根数取log2即可,但是scheme只提供了以自然对数为底的log函数,不过只需要定义下面的函数就可以求以2为底的log了:

    (define (log2 x)
     (/ (log x) (log 2)))

    这样我们就能够解决1.45的习题了:

    (define (nth-root x n)
     (fixed-point
      ((repeated average-damp (floor (log2 n)))
       (lambda (y) (/ x (expt y (- n 1)))))
      1))

    由于数学能力有限实在是无法证明为什么结果是这样,而且对于average damp这样一种方法维基百科上竟然没有!以前的数学实在学得不怎么样啊。不过《SICP》的习题做起来确实很有意思,还教你直接求tan、黄金分割数还有e的方法。