在这篇简短的笔记中,我们将研究如何在Lisp中实现诸如部分应用程序和功能泛滥之类的现在非常流行的软件机制。为此,我将使用Homelisp实现(这是具有某些附加功能的纯Lisp解释器)。
在Common Lisp中使用部分应用程序可能会有些棘手(因为必须使用funcall / apply来调用计算函数对象);在Scheme中应该更容易。我计划很快发布一个新版本的HomeLisp,它不需要funcall / apply来调用计算函数对象。如果代码的行为不同,我将强调这一点。
部分应用和计算是严格的数学运算。但是我们将认为它们“在手指上”,而无需借助lambda微积分和组合逻辑。
函数f的部分应用是从函数f中获得一个已经接受了给定参数并准备接受其余参数的新函数f'。部分申请有什么用?例如,以便可以从函数返回函数值。
让我们考虑一个简单的示例的部分应用程序。假设函数f由以下公式给出:
f(x,y,z)= x + y ** 2 + z ** 3,
则将此函数以参数x = 1和y = 2的部分应用应生成函数:
f'(z)= 1 + 4 + z ** 3 = 5 + z ** 3
在Haskell中,部分应用程序不会使程序员付出任何代价:
Prelude> f x y z = x+y**2+z**3 --
f :: Floating a => a -> a -> a -> a
Prelude> f 1 2 3 -- ...
32.0 -- !
it :: Floating a => a
Prelude> f' = f 1 2 -- x=1 y=2 f'
f' :: Floating a => a -> a
Prelude> f' 3 -- f'
32.0 --
it :: Floating a => a
但是,在Lisp中,此尝试将失败:
(defun f (x y z) (+ x (* y y) (* z z z))) ;;
==> F
(f 1 2 3) ;;
==> 32 ;;
(f 1 2) ;; ...
PairLis:
: F
: (X Y Z)
: (1 2)
==> ERRSTATE
当然,Lisp具有创建带有任意数量参数的函数的机制(&rest结构);您可以创建一个将使用两个或三个(或十个)参数的函数:
(defun s (&rest x) ;; - x
(apply '+ x)) ;;
==> S
(s 1 2) ;;
==> 3
(s 1 2 3) ;;
==> 6
但重要的是要了解它们之间的区别:此函数处理所有参数并返回计算结果,而部分应用程序会生成一个新函数,“可以继续进行计算”。
让我们看看如何在Lisp中实现部分函数应用程序机制。它将为我们提供帮助...是的,使用匿名函数(lambda)。一些程序员认为匿名功能仅需要保存名称(它们在任何stream-map-filter-reduce中的位置,以便对序列元素执行简短操作)。实际上,匿名函数具有更多功能,我们现在将看到。
让我们先来看一个函数如何才能返回另一个函数。在Lisp中,这非常简单:
(defun func-gen (x)
(lambda (y) (+ x (* y y))))
==> FUNC-GEN
(func-gen 5)
==> (CLOSURE (Y) ((+ X (* Y Y))) ((X 5)))
如您所见,该函数返回一个闭包,其中的自由变量x的值是固定的(等于5)。函数的结果可以称为函数。为此,在Common Lisp和HomeLisp(内核版本<= 13.53)中,您将必须使用funcall:
(funcall (func-gen 5) 7)
==> 54
现在很清楚,如果我们想从n个参数和一个x值中获取一个函数f,然后从(n-1)个参数中获取一个函数,该如何进行。让我们用plist表示函数形式参数的列表。然后,您要做的就是构建一个lambda表达式,如下所示:
(lambda (-plist) (apply f (cons x -plist)))
这个想法非常简单:我们在主体中构建一个lambda表达式,我们只需在参数列表中调用原始函数,即可将头替换为值x。
这意味着对于函数的部分应用,您需要基于此函数构建一个lambda表达式,该函数将少一个参数,并且在lambda表达式主体中我们函数的内部调用中将“考虑”部分应用期间指定的参数。
如何实现呢?容易... HomeLisp具有getd函数,该函数提供对函数的定义表达式或宏的访问:
(defun g (x y z) (+ x (* x y) (* x y z)))
==> G
(getd 'g)
==> (EXPR (X Y Z) (+ X (* X Y) (* X Y Z)))
如您所见,getd返回函数的定义表达式,其中“代替” lambda是一个特殊的EXPR原子。我们可以获取函数的参数列表(结果的第二个元素)并构造一个lambda表达式,其参数将成为原始参数列表的尾部,在lambda表达式的主体中,我们将使用完整的参数列表调用原始函数。
(defun part-apply (f a)
(let* ((plist (cadr (getd f))) ;;
(rlist (cdr plist)) ;;
(clist (cons a rlist))) ;; a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
从上面的代码中,很容易理解plist是我们要部分应用的函数f的原始列表。rlist是不带第一个元素的原始列表,而clist是参数的完整列表,其中第一个元素被x代替。具体而言,对于上述函数g,plist =(xyz),rlist =(yz)和clist =(ayz)。现在让我们检查部分应用程序是如何工作的:
(part-apply 'g 111)
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
您可以确保这完全是计划的:部分应用程序返回了一个新函数,该函数具有更少的参数。如果使用参数y和z调用此新函数,则结果与使用以下三个参数调用原始函数g完全相同:111 y和z:
(g 111 1 2)
==> 444 ;;
(funcall (part-apply 'g 111) 1 2) ;; "--"
==> 444
((part-apply 'g 111) 1 2) ;; "-"
==> 444
为了简洁起见,以下I(为了简洁起见)将不指定funcall。在HomeLisp的下一个核心中,用于函数计算的方案将被更改-“方案”语法将变为可用。
让我们走得更远。现在自然会有重新申请重新申请结果的冲动。事实证明这很简单-毕竟,部分应用程序的结果是一个lambda表达式,并且其结构与getd返回的结果几乎相同。 lambda表达式的参数列表是列表中的第二项。所有这些考虑因素使我们能够为问题建立最终解决方案:
(defun part-apply (f a)
(cond ((and (atom f) (member 'expr (proplist f))) ;; *** ***
(let* ((plist (cadr (getd f))) ;;
(rlist (cdr plist)) ;;
(clist (cons a rlist))) ;; a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
((eq 'lambda (car f)) ;; *** - ***
(let* ((plist (cadr f)) ;;
(rlist (cdr plist)) ;;
(clist (cons x rlist))) ;; x
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
(t (raiseerror "part-apply: "))))
这里添加了对第一个参数的分析:如果它是一个原子,则它必须“表示”一个函数(类型为EXPR);如果第一个参数既不是“有效”原子也不是lambda表达式,则将引发错误条件。当然,可以进一步缩短代码,为清晰起见,保留了两个几乎相同的分支。现在,让我们看看该函数的功能:
(part-apply (part-apply 'g 1) 2) ;;
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
((part-apply (part-apply 'g 1) 2) 3) ;;
==> 9
(part-apply (part-apply (part-apply 'g 111) 1) 2) ;;
==> (LAMBDA NIL (APPLY (QUOTE (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))) (LIST 2)))
((part-apply (part-apply (part-apply 'g 111) 1) 2)) ;; ...
==> 444
(setq u (part-apply 'g 111)) ;;
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
;; U
(part-apply u 1) ;;
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))
((part-apply u 1) 2) ;;
==> 444
现在让我们开始吧。咖喱函数,接受的参数数量不足,返回一个可以处理其余函数的函数。currying的主要目的是提供部分应用程序。我们从另一端出发:现在让我们看一下如果存在部分应用程序,如何实现currying。
给出几个参数的函数g。我们将使用其他名称来构建它的咖喱版本!构造的实质如下:函数!G将接受不确定数量的参数。调用之后,它必须检查传递的参数数量。如果该数目等于原始函数g的参数数目,则from应该传递给输入g。如果参数超过g可以接受的范围,则应提出错误条件。但是,如果参数数量少于函数g的数量,则...是,是-您需要执行顺序部分应用程序。返回此应用程序的结果。
在这种情况下,使用宏非常方便。带有注释的代码如下:
(defmacro curry (f)
(let* ((parmlist (cadr (getd f))) ;; f
(body (cddr (getd f))) ;; f
(lp (length parmlist)) ;; f
(cf (implode (cons '! (explode f))))) ;;
`(defun ,cf (&rest x)
(let ((lx (length x))) ;;
(cond ((= lx ,lp) ;;
(let ((e `(lambda ,parmlist ,@body)))
(apply e x)))
((> lx ,lp) ;;
(raiseerror "curry: "))
(t (let ((tmp nil)) ;;
(iter (for a in x) ;;
(setq tmp (if (null tmp) (part-apply (quote ,f) a) (part-apply tmp a))))
tmp)))))))
值得在这里评论新功能名称的构造。为此,请使用HomeLisp爆炸函数,该函数从一个原子构建其组成符号的列表,然后进行爆破,将列表符号压缩为一个,从而创建一个新的原子。
现在,让我们检查一下运行中的宏:
(curry g) ;; g
==> !G ;;
(!g 1 2 3) ;;
==> 9 ;; g
(!g 1 2) ;; -
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
;; :
((!g 1 2) 3) ;;
==> 9
((!g 1) 2 3) ;;
==> 9
(!g 1 2 3 4) ;;
curry:
==> ERRSTATE
固化过程无需其他控制。而且我们还没有实现可弯曲的lambda表达式。如果您愿意,您可以做所有这一切。
这就是您可以轻松实现Lisp中的部分功能应用程序和curring的方法。Lisp是一种很棒的语言!
感谢您的关注。