Lisp 匿名递归函数

主流的 Lisp 实现(CLISP、Guile、Emacs 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 的语法更优雅些。



为方便其他朋友提问和指正,转载时请保持文章完整性,并以超链接形式注明原始作者“redraiment”和主站点地址,谢谢。

我的邮箱,欢迎来信(redraiment@gmail.com)
我的CSDN博客(子清行):http://blog.csdn.net/redraiment
我的百度空间(子清行):http://hi.baidu.com/redraiment

时间: 2025-01-21 06:39:41

Lisp 匿名递归函数的相关文章

递归函数(七):不动点算子

递归函数(一):开篇递归函数(二):编写递归函数的思路和技巧递归函数(三):归纳原理递归函数(四):全函数与计算的可终止性递归函数(五):递归集与递归可枚举集递归函数(六):最多有多少个程序递归函数(七):不动点算子递归函数(八):偏序结构递归函数(九):最小不动点定理 - 回顾 以上几篇文章中,我们讨论了可计算性理论相关的一些内容,可计算性与递归函数论存在着千丝万缕的联系,不动点理论也是这样的,我们定义的递归函数一定存在吗?在什么情况下它是存在的? 要回答以上这些问题,还要从方程,不动点,不动

php的闭包(Closure)匿名函数详解

 本文主要给大家介绍的是php5.3引入的PHP匿名函数,也就是闭包(Closure),以及闭包的作用,非常详细,这里推荐给有需要的小伙伴们.     php的闭包(Closure)也就是匿名函数,是PHP5.3引入的. 闭包的语法很简单,需要注意的关键字就只有use,use是连接闭包和外界变量.   代码如下: $a = function() use($b) {}   简单例子如下:   代码如下: function callback($fun) { $fun(); } $msg = "Hel

Clojure快餐教程(1) - 运行在JVM上的Lisp方言

Clojure快餐教程(1) - 运行在JVM上的Lisp方言 Java作为目前为止被使用最广泛的使用虚拟机的编程语言,带动了JVM上语言族的繁荣. 有根红苗正的为JVM设计的动态语言Groovy,目前最主要被用于Gradle编译环境中:也有Jython, JRuby等动态语言在JVM上的实现,也有scala这样强大的混合语言. 在这之中,clojure是比较特殊的一种,它是Lisp语言在JVM上的一种方言. 使用clojure调用java 首先我们先看一下如何用clojure来调用java的方

Javascript的匿名函数小结_javascript技巧

一.什么是匿名函数? 在Javascript定义一个函数一般有如下三种方式: 函数关键字(function)语句: function fnMethodName(x){alert(x);} 函数字面量(Function Literals): var fnMethodName = function(x){alert(x);} Function()构造函数: var fnMethodName = new Function('x','alert(x);') 上面三种方法定义了同一个方法函数fnMetho

递归函数(一):开篇

递归函数(一):开篇递归函数(二):编写递归函数的思路和技巧递归函数(三):归纳原理递归函数(四):全函数与计算的可终止性递归函数(五):递归集与递归可枚举集递归函数(六):最多有多少个程序递归函数(七):不动点算子递归函数(八):偏序结构递归函数(九):最小不动点定理 提到函数式编程,人们最多想到的可能是它的某些性质, 例如,不可变性,无副作用,惰性求值,类型推导,等等. 然而,这些性质可能并不是它能吸引粉丝的根本原因, 而是它从工业界触手可及的直接应用出发,带我们看到了人类能力的边界, 函数

我也说说Emacs吧(7) - lisp基础

Lisp基础 Lisp是仅次于Fortran的第二古老的著名计算机语言. Lisp从一开始就与众不同的一点在于,它是基于S-表达式的语言.也就是说,代码和数据是用同一种方式表达出来的. S-表达式,我们直观上理解,就是用括号括起来的一串列表. 比如: (+ 1 1) Lisp会对这个S-表达式进行求值. S-表达式可以嵌套,比如可以这样写 (+ 1 (* 2 3)) 在lisp中,默认的操作是对S-表达式求值.如果是个数字,就对数字直接求值.如果是字符串也是如此.如果是个表,则将第一个原子当成函

为什么Lisp语言如此先进?(译文)

翻译完这本书,累得像生了一场大病.把书稿交出去的时候,心里空荡荡的,也不知道自己得到了什么,失去了什么. 希望这个中译本和我的努力,能得到读者认同和肯定. 下面是此书中非常棒的一篇文章,原文写于八年前,至今仍然具有启发性,作者眼光之超前令人佩服.由于我不懂Lisp语言,所以田春同学帮忙校读了一遍,纠正了一些翻译不当之处,在此表示衷心感谢. ============================ 为什么Lisp语言如此先进? 作者:Paul Graham 译者:阮一峰 英文原文:Revenge

在 NewLisp 实现匿名函数的递归

匿名函数在很多语言中的表现形式大概如下: (lambda (n) (* (+ n 1) (- n 1))) 只有参数列表和函数体,而没有名字.在大部分情况下没问题,但是一旦需要用到递归的话,就有点麻烦了,因为不知道如何去递归的调用一个匿名函数. 在学术界中有一些解决这个问题的办法,其中一个就是Y组合子,但是那个太繁琐,而且难以通过宏自动将一个lambda变成可递归形式,没什么好处. 根据历史经验,目前比较好的办法,就是实现一个操作符,匿名函数通过这个操作符来调用自身: (lambda (n) .

使用Lambda表达式编写递归函数

前言 著名的牛顿同学曾经说过:如果说我比别人看得更远些,那是因为我站在了巨人的肩上. 原文:If I have been able to see further, it was only because I stood on the shoulders of giants. What's Lambda表达式? 请参考msdn:Lambda 表达式(C# 编程指南) Lambda表达式编写递归函数? How? 建议没有看过老赵的<使用Lambda表达式编写递归函数>这篇文章的朋友,请先前往围观,