隐式编程

隐式(tacit)编程,也叫做无点(point-free)样式,是其中函数定义不标示所要操作的参数(或称“点”)一种编程范型。转而函数定义只是其他函数的复合,比如那些操纵参数的组合子。隐式编程有着理论价值,因为严格的使用复合导致程序非常适配于方程式推理[1]。它也是特定编程语言的自然样式,包括APL及其派生者[2],和串接语言比如Forth。将参数缺席称为“point-free”导致了不必要的晦涩,故而有了别名为“pointless”[1]

概述

J语言中,下列在一个数值的列表(阵列)上计算平均值的函数采用了一种无点样式代码:

avg=: +/ % #

+/通过将求和(+)插入(/)到一个阵列的所有元素之间来计算它们的合计值。#总计一个阵列的元素数目。%+/这个阵列的结果值除以#这个阵列的结果值。相同的隐式计算用APL2表达为:

avg  + ÷ 

再比如,Unix脚本通过管道采用了这种范式。

隐式编程的关键想法是在适当的抽象层级上对运算操作加以辅助。就是说,将通过柯里化给出的自然变换

转换成计算机函数,这里左侧表示函数的未柯里化形式,而右侧是柯里化后的形式。 CA指示从A到C的泛函(参见指数对象),而A×B指示A和B的笛卡尔乘积

例子

APL家族

J语言中,欧拉公式可隐式表达为:

cos =: 2 o. ]
sin =: 1 o. ]
Euler =: ^@j. = cos j. sin

这里用到了一些原语(primitive)函数:=:表示全局定义;o.表示圆函数,由左侧名词参数选择具体的函数;]不变动的返回右侧名词参数;^的一元定义为指数函数;j.的一元定义为虚数单位0j1乘以右侧参数y,而它的二元定义为x + 0j1*y,即组合左侧参数x和右侧参数y成为复数,而二者分别是其实部和虚部;@表示数学函数复合=等于布尔运算,两侧参数相等返回1而不等返回0。相同的隐式计算用Dyalog[3]APL表达为:

cos  2  
sin  1  
j    {0  +0j1×}  ⍝ 这部份不是隐式的
Euler  *j = cos j sin

这里采用直接函数定义了j函数,其中在{}之间由分隔的是守卫的表达式序列(这里只有表达式),指示左参数而指示右参数,⍺←指示一元定义需要的缺省左参数。

Unix管道

在Unix脚本中,函数相当于从标准输入接收数据并发送结果至标准输出的计算机程序。例如:

sort | uniq -c | sort -rn

是一个隐式或无点复合,它返回它的每个参数的计数和这些参数,并按照这个计数的递减次序来排序。sortuniq是函数,而-c-rn控制这些函数,但是不提及参数。|是复合算子。

Python

如下Python代码是对应上节Unix管道命令的函数定义和一序列的运算操作[note 1]

def sort(argv):
    return sorted(argv, key=str)
def uniq_c(argv):
    counts = {}
    for i in argv:
        counts[str(i)] = counts.get(str(i), 0) + 1
    return [(v, int(k)) for k , v in counts.items()]
def sort_rn(argv):
    sort_rk2 = sorted(argv, key=lambda x:str(x[1]), reverse=True)
    return sorted(sort_rk2, key=lambda x:x[0], reverse=True)

a_list = [2, 5, 4, 14, 3, 1, 3, 12, 2]
a = sort(a_list)    
b = uniq_c(a)
c = sort_rn(b)

它可以写为无点样式的没有参数的一序列函数的复合[4]

from functools import partial, reduce

def compose(*func_list):
    return partial(reduce, lambda argv,func:func(argv), func_list)

pipeline = compose(sort, uniq_c, sort_rn)
d = pipeline(a_list)
assert c == d

函数式编程

一个简单例子(用Haskell语言)是在一个列表上作合计的函数。编程者可以使用有点方法(相较于值级编程)而递归的定义这个合计为:

sum (x:xs) = x + sum xs
sum [] = 0

但是,注意到作为一种折叠(fold),编程者可以将它改写为:

sum xs = foldr (+) 0 xs

因而参数是不需要的,进而将它改写成如下无点样式:

sum = foldr (+) 0

另一个例子使用函数复合

p x y z = f (g x y) z

下列类Haskell伪码展示了如何将一个函数定义归约成无点的等价定义:

p = \x -> \y -> \z -> f (g x y) z
  = \x -> \y -> f (g x y)
  = \x -> \y -> (f . (g x)) y
  = \x -> f . (g x)
  = \x -> ((.) f) (g x)
  = \x -> (((.) f) . g) x
  = ((.) f) . g

所以:

p = ((.) f) . g

最后看一个复杂的例子,想象一个映射(map)过滤器(filter)程序,它接受一个列表,向它应用一个函数,接着基于一个准则(criterion)来过滤元素:

mf criteria operator list = filter criteria (map operator list)

它可以表达为无点样式为[5]

mf = (. map) . (.) . filter

注意如前面所说,在“无点”中的点指称参数而非不使用点,这是常见误解[6]

基于堆栈语言

面向堆栈编程语言(和串接编程语言)中,无点方法也很常用。例如,计算斐波那契数列的过程可以用PostScript写为如下:

 /fib
 {
    dup dup 1 eq exch 0 eq or not
    {
       dup 1 sub fib
       exch 2 sub fib
       add
    } if
 } def

参见

注释和引用

  1. 下列例子中的uniq_c()这么写是出于简短和完备,下面的替代写法更加有效率但需要符合unix的uniq应当处理sort之后的数据的原义。
    def uniq_c(argv):
        if argv == None or argv == []:
            return
        uniq = [] 
        p, count = argv[0], 1
        for c in argv[1:]:
            if c == p:
                count = count + 1
            else:
                uniq.append((count, p))
                p, count = c, 1
        uniq.append((count, p))
        return uniq
    
  1. Manuel Alcino Pereira da Cunha (2005) Point-free Program Calculation
  2. W. Neville Holmes, ed. (2006) Computers and People
  3. 页面存档备份,存于
  4. . Concatenative.org. [2020-10-16]. (原始内容存档于2013-09-29).
  5. pipermail
  6. . wiki.haskell.org. [2016-06-05].

外部链接

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.