文档章节

在NewLisp中实现匿名函数的递归

句龙胤
 句龙胤
发布于 2015/06/20 20:35
字数 1374
阅读 911
收藏 17

匿名函数在很多语言中的表现形式大概如下:

(lambda (n)
  (* (+ n 1) (- n 1)))

只有参数列表和函数体,而没有名字。在大部分情况下没问题,但是一旦需要用到递归的话,就有点麻烦了,因为不知道如何去递归的调用一个匿名函数。


在学术界中有一些解决这个问题的办法,其中一个就是Y组合子,但是那个太繁琐,而且难以通过宏自动将一个lambda变成可递归形式,没什么好处。

根据历史经验,目前比较好的办法,就是实现一个操作符,匿名函数通过这个操作符来调用自身:

(lambda (n) ... (this (- n 1))) 或者是 (lambda (n) ... (lambda (- n 1)))

第一种是用this或其他东西来表示当前匿名函数本身,直接调用就可以递归。第二种是和有名函数一样,用和定义匿名函数一样的操作符来调用自身。

然而第二种不实际,因为这样会造成混乱,比如需要嵌套lambda时,而且其语义也不对。

所以此文主要围绕第一种方式:实现让this指向当前匿名函数,从而可以递归调用自身。


NewLisp是一个Lisp语言的实现,也可以说是一个方言,其与Common Lisp相比,少了很多东西,但远比Common Lisp容易使用。Lisp系列的语言有一个特点:没有语法。或者说极小语法,用Lisp编写程序,直接没有了语法阶段,从语义开始起步,所以非常接近编译器。Lisp是一个多范式编程语言,支持命令式、函数式、面向对象等等,当然Lisp其实应该被称为:列表处理语言。或者说是:抽象语法树处理语言。源程序就是AST,通过设计AST来构建软件。

首先我们找个最简单的办法,然后逐步改善。

在匿名函数内部定义一个局部函数,通过调用这个函数,就可以实现递归自身了。比如在要定义的递归匿名函数中再定义一个函数作为主体函数,通过调用这个函数来实现递归的效果。

大概的形式如下:

(lambda (n)
  (define this (n) (if (< n 2) 1 (* n (this (- n 1)))))
  (this n))

现在可以设计一个定义可递归匿名函数的宏了:

(define-macro
  (lambda* _args)
  (letex ((fargs _args) 
          (fbody (cons 'begin $args))
          (fcall (cons 'this (flat _args))))
    (lambda
      fargs
      (define (this fargs) fbody)
      fcall)))

这样,只需要用lambda*,就可以定义一个可递归的匿名函数:

; 通过this来调用自身
(lambda* (n) (if (< n 2) 1 (* n (this (- n 1)))))

但是这样有一个很大的问题,这个定义的函数会污染名称空间,而且不同的lambda*会覆盖掉this,因为define是在全局中定义的。在Common Lisp中,可以通过定义仅在函数内部可见的嵌套函数来解决:

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

但是在NewLisp中,我没有找到如何定义仅在函数内部可见的嵌套函数,所以还需要通过其他的办法才能解决。


于是我想到了自动生成函数名的方式,NewLisp有一个函数(time-of-day),返回一个以较为精确的时间戳:

> (time-of-day)
66359119.140
> (time-of-day)
66359415.039

这样我们可以在扩展宏时自动生成一个函数名,以避免冲突:

 (define-macro
  (lambda* _args)
  (let ((f (string "$."(time-of-day)))) ;生成一个随时间变化的函数名
    (eval
      (list
        'define
        (cons (sym f) (flat _args))
        (list
          'let
          (list (list 'this (sym f))) ; this指向这个函数
          (cons 'begin $args))))))

于是当用lambda*定义时,会自动生成一个每个时刻都不同的名称,比如$.66789291.992、$.66922513.671,几乎不会有重复。


但是这样依然不行,因为只是避免的名称冲突,但还是会污染名称空间,而且在某些情况下依然会造成难以预料的问题。所以在最后,设计了一个终极版本的lambda*,没有任何负面作用。


终极版本

(define-macro
  (lambda* _args)
  (letex ((fargs _args) 
          (fbody (cons 'begin $args))
          (fcall (cons 'this (flat _args))))
    (lambda
      fargs
      (let ((this (lambda fargs fbody)))
        fcall))))

通过在扩展宏时,在lambda内部在定义一个lambda作为主体函数,使用let将局部变量this指向这个主体函数,于是就可以通过this来模拟调用自身了,函数不需要有名字,而只有一个指向函数的局部变量this,效果非常好:

; 阶乘函数
(lambda* (n)
  (if (< n 2)
    1
    (* n (this (- n 1)))))

; 宏展开后如下=>
(lambda (n)
  (let ((this
        (lambda (n)
          (begin
            (if (< n 2)
              1
              (* n (this (- n 1))))))))
    (this n)))

一段测试结果:
> ((lambda* (n) (if (< n 2) 1 (* n (this (- n 1))))) 1)
1
> ((lambda* (n) (if (< n 2) 1 (* n (this (- n 1))))) 2)
2
> ((lambda* (n) (if (< n 2) 1 (* n (this (- n 1))))) 3)
6
> ((lambda* (n) (if (< n 2) 1 (* n (this (- n 1))))) 4)
24
> ((lambda* (n) (if (< n 2) 1 (* n (this (- n 1))))) 5)
120
> ((lambda* (n) (if (< n 2) 1 (* n (this (- n 1))))) 20)
2432902008176640000
> this
nil
> (setf this 100)
100
> ((lambda* (n) (if (< n 2) 1 (* n (this (- n 1))))) 10)
3628800
> this
100


* 勿轻易尝试Lisp的宏,更不要轻易尝试NewLisp的宏,前者你会受伤,后者你能体会到和查C++模板错误一样的过程,甚至更加爆炸。

用农业界的一个术语来说:就像一颗原子弹。

© 著作权归作者所有

句龙胤
粉丝 10
博文 6
码字总数 13207
作品 0
广州
架构师
私信 提问
加载中

评论(1)

句龙胤
句龙胤 博主
发现了一个问题,原来当时多个一个函数调用(第5行)

修正:

(define-macro
(lambda* _args)
(letex ((fargs _args)
(fbody (cons 'begin $args))
(fcall (cons 'this _args))) ;不需要flat
(lambda
fargs
(let ((this (lambda fargs fbody)))
fcall))))
newLISP你也行 --- newLISP简介

############################################################################# # Name:newLISP你也行 --- newLISP简介 # Author:黄登(winger) # Gtalk:free.winger@gmail.com # Gtalk-Gr......

天国之翼
2012/05/31
1K
0
newLISP 是如何令我惊愕忘形的

译者:skydark 偶然看到这篇文章, 感到非常有意思,忍不住想翻译一下。 原文标题是“How newLISP Took My Breath (And Syntax) Away”,非常漂亮的一个标题,但是不知道怎么翻译好,就随便编...

天国之翼
2012/07/25
7.6K
7
newLISP你也行 --- 基础知识

############################################################################# # Name:newLISP你也行 --- 基础知识 # Author:黄登(winger) # Project:http://code.google.com/p/newlisp......

天国之翼
2012/05/31
710
0
使用NewLisp设计Key-Value数据库系统

Lisp是一个很好的语言,最强大的就是其S-表达式,可以说是Lisp能活到今天的唯一一个原因。其次就是函数为基本类型和后来的闭包。当然Lisp也有很大的缺点,即:一般的设计师难以避免Lisp的缺点...

句龙胤
2015/06/23
554
2
newLISP 10.5.8 发布,类似 Lisp 的脚本语言

newLISP 10.5.8 发布,此版本是个开发版,添加了一个原生宏函数,一些领域的功能改进。 newLISP是一个类似Lisp语言的、用于一般用途的脚本语言。它具有 LISP 语言所有的魔力,但更容易学习和...

oschina
2014/03/12
382
0

没有更多内容

加载失败,请刷新页面

加载更多

sync 包讲解

sync.Once Once 的作用是多次调用但只执行一次,Once 只有一个方法,Once.Do(),向 Do 传入一个函数,这个函数在第一次执行 Once.Do() 的时候会被调用,以后再执行 Once.Do() 将没有任何动作...

李琼涛
刚刚
0
0
java中的byte占一字节或4字节

https://www.jianshu.com/p/2f663dc820d0

南桥北木
14分钟前
1
0
Cassandra 常用命令

Linux控制台命令 #进入Cassandra的安装目录 cd /home/db/cassandra/cassandra #进入Cassandra 无密码 ./bin/cqlsh localhost(IP)有密码 ./bin/cqlsh localhost(IP)-u 用户名 #显示所...

最菜最菜之小菜鸟
19分钟前
1
0
自建redis笔记

自建redis笔记 最近在linux安装了一下redis,特做一些笔记! 本文先单节点启动redis,然后再进行持久化配置,在次基础上,再分享搭建主从模式的配置以及Sentinel 哨兵模式及集群的搭建 单节点...

北极之北
27分钟前
1
0
扛住阿里双十一高并发流量,Sentinel是怎么做到的?

Sentinel 承接了阿里巴巴近 10 年的双十一大促流量的核心场景 本文介绍阿里开源限流熔断方案Sentinel功能、原理、架构、快速入门以及相关框架比较 基本介绍 1 名词解释 服务限流 :当系统资源...

分布式系统架构
35分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部