Chinaunix首页 | 论坛 | 博客
  • 博客访问: 626737
  • 博文数量: 37
  • 博客积分: 106
  • 博客等级: 民兵
  • 技术积分: 993
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-30 18:26
个人简介

来自汉江北邻的IT男一枚,专注于PHP和C#开发... 最常更新的技术Blog → https://enjoy233.cnblogs.com/

文章分类

全部博文(37)

文章存档

2013年(36)

2012年(1)

我的朋友

分类: 高性能计算

2013-04-15 18:28:58


                                                                    Lisp匿名递归函数

主流的 Lisp 实现(CLISPGuileEmacs Lisp 等)中默认都没提供定义匿名的递归函数的方法。上 Google 搜索了一下,看到不少人也都在抱怨不过 Lisp 一个特色就是你可以自己动手添加需要的语言特性!于是我就尝试着自己写一个宏来实现这个功能

用 Lisp recursive lambda 做关键词搜索,找到老外一篇 08 年的文章 ,里面提到一种用两个 Lambda 实现的递归方法我将格式整理了一下:

(funcall
 (lambda (fn n)
   (funcall fn n fn))
 (lambda (n this)
   (cond ((> n 0)
          (* n (funcall this (- n 1) this)))
         (t 1)))
 10)

方法就是额外添加一个参数,用于传递函数本身个人觉得这个方法不够优雅,如果需要定义多个匿名的递归函数,冗余的代码也会相当多。不过它已经反映出实现匿名递归函数的本质方法:将匿名函数赋给一个临时变量。

我的想法是在定义 lambda 函数时使用 this 来代表自身例如编写一个用递归实现的匿名阶乘函数:

((lambda (n)
   (if (> n 1)
       (* n (this (1- n)))
     1))
 10)

根据上述期望的代码,目标是:

  1. 定义一个能创建并返回匿名函数的宏;
  2. 这个匿名函数要绑定到 this 符号(Symbol)上

我一开始先尝试用 Emcas Lisp 来实现实现第一个目标很简单,只要将宏的参数和 lambda 这个符号链接起来即可:

(defmacro re-lambda (&;rest cdr)
   (cons 'lambda cdr))

第二个目标可以使用 defalias它能将符号绑定到函数空间里(setq 只能绑定到变量空间,因此通过 setq 绑定的函数只能用 funcall 来调用):

(defmacro re-lambda (&;rest cdr)
  `(defalias 'this
     ,(cons 'lambda cdr)))

这样就拥有了符合上述要求,可以定义匿名递归函数的方法了用这个宏来编写阶乘函数并执行:

(funcall
 (re-lambda (n)
   (if (> n 1)
       (* n (this (1- n)))
     1))
 10)
; 执行结果:3628800

执行结果正确,实现的代码也很简短,看起来很不错的样子可惜它有个不足之处:Emacs Lisp 中有 let 等函数来定义局部变量,却没用类似的方法来定义局部函数,而且也不支持闭包,所以 this 这个符号是所有匿名函数共用的如果同时用 re-lambda 定义了两个匿名函数,前一个函数就会被覆盖:

(setq factorial
 (re-lambda (n)
   (if (> n 1)
       (* n (this (1- n)))
     1)))

(funcall factorial 10) ; 执行结果:3628800

(setq sum
 (re-lambda (n)
   (if (> n 1)
       (+ n (this (1- n)))
     1)))

(funcall sum 10)       ; 执行结果:55
(funcall factorial 10) ; 执行结果:55

好在 Common Lisp 中提供的 labels 可以定义局部函数,有了它就不用担心命名空间被污染了:

(defmacro re-lambda (&;rest body)
  `(lambda (&;rest args)
     (labels (,(cons 'this body))
        (apply #'this args))))

上面代码中,因为 this 是作为返回的匿名函数中的一个局部函数,因此不必担心命名冲突问题你可能会想,为什么不用 re-lambda 代替 this?这样也能避免 this 和其他全局变量或函数冲突即:

((lambda (n)
   (if (> n 1)
       (* n (lambda (1- n)))
     1))
 10)

这看起来很不错:lambda 在不同的上下文里表现出不同的角色而且实现的方法也很简单,只要将上述代码中的 this 替换成 re-lambda 即可但这会引起另一个问题:不能定义嵌套匿名递归函数。例如,求 1 到 n 所有阶乘的和:

(format t "~A~%"
  (funcall
    (re-lambda (n)
      (if (> n 1)
          (+ (this (1- n))
	     (funcall (re-lambda (n)
	                 (if (> n 1)
	                     (* (this (1- n)) n)
			   1))
		      n))
	1))
    10))

如果没用 this 的话,就很难分辨哪些 re-lambda 是定义函数,哪些是计算结果

最后,还有一个遗憾:你可能也发现了,我给的期望结果里调用 lambda 都不需要 funcall因为它是按 Scheme 的语法写的,而实现的代码是按 Common Lisp 的语法写的。就这方面来说,我觉得 Scheme 的语法更优雅些。

在Common Lisp中实现Clojure的fn 


上文提到 Emacs LispScheme 和 Common Lisp 中默认都没提供定义可递归的 lambda 函数的方法。并在文章里提供了我自己实现的 Emacs Lisp 版本和 Common Lisp 版本在那之后,我学习了 Clojure,发现 Clojure 中的 fn 在定义 lambda 函数的同时还允许给它取一个临时的名字,这样就能在函数体中递归地调用自己了,比如下面用来临时求第12个斐波那契数的匿名函数:

((fn fibonacci [n]
   (if (<= 2 n)
     (+ (fibonacci (- n 1))
        (fibonacci (- n 2)))
     1))
 12)

这个方法比我之前实现的要高明的多!我的方法会额外“霸占”一个名字“this”来代表自己,这样很容易有命名冲突的问题但像 fn 这样,名字由开发者自己提供,就能避免这样的问题。因此,我开始琢磨怎么把 fn 迁移到 Common Lisp 中。

有了之前开发的经验,这一次实现起来顺手多了观察 fn 的语法,与 lambda 相比它多了一个可选的名字。所以,当函数名未提供时和 lambda 无区别:

(defmacro fn (&;rest body)
  (if (listp (car body))
    `(lambda ,@body)
    ))

然后是 else 块,这部分和之前文章里介绍的一样,都是需要让返回的匿名函数能识别一个额外的函数名,并且那个函数名指向函数本身区别仅是之前 hard code 成 this,而这回名字由开发者指定。所以,也是用“局部函数”来实现,即 Common Lisp 中的 labels,或 Emacs Lisp 中的 flet:

(defmacro fn (&;rest body)
  (if (listp (car body))
    `(lambda ,@body)
    `(lambda (&;rest args)
       (labels (,body)
         (apply (function ,(car body)) args)))))

来写个函数测试一下比如输出一棵树的所有子节点:

(funcall
  (fn dump-list (o)
    (if (consp o)
      (dolist (item o)
        (dump-list item))
      (format t "~A~%" o)))
  '(1 (2 (3 (4) 5) 6) 7 (8 9)))

在 clisp 中执行结果如下:

λ clisp -q
[1]> (defmacro fn (&rest body)
  (if (listp (car body))
    `(lambda ,@body)
    `(lambda (&;rest args)
       (labels (,body)
         (apply (function ,(car body)) args)))))
FN
[2]> (funcall
  (fn dump-list (o)
    (if (consp o)
      (dolist (item o)
        (dump-list item))
      (format t "~A~%" o)))
  '(1 (2 (3 (4) 5) 6) 7 (8 9)))
1
2
3
4
5
6
7
8
9
NIL
[3]> 
 
阅读(2840) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~