隐式编程
隐式(tacit)编程[1],或称为函数级编程,是一种编程范型,也叫做无点(point-free)样式。其中函数定义不标示所要操作的参数(或称“点”),转而函数定义只是其他函数的复合,比如那些操纵参数的组合子。隐式编程有着理论价值,因为严格的使用复合导致程序非常适配于方程式推理[2]。它也是特定编程语言的自然样式,包括APL的一些现代实现和方言[3],和串接式语言比如Forth。将参数缺席称为“point-free”导致了不必要的晦涩,故而有了别名为“pointless”[2]。
例子
APL家族
在一些APL方言中,允许将函数组合入服从几个规则的“列车”(train);这允许建立复杂的派生函数,而不需要显式指定任何参数;实现了列车的APL方言包括:J语言、Dyalog APL、dzaima/APL、ngn/apl和NARS2000[1]。在J语言中,下列在一个数值的列表(阵列)上计算平均值的函数采用了一种无参数样式代码:
avg=: +/ % #
+/
通过将求和(+
)插入(/
)到一个阵列的所有元素之间来计算它们的合计值。#
总计一个阵列的元素数目。%
用+/
这个阵列的结果值除以#
这个阵列的结果值。
欧拉公式可隐式表达为:
cos =: 2 o. ]
sin =: 1 o. ]
Euler =: ^@j. = cos j. sin
这里定义的函数Euler
在任何输入值上都恒等于1
,即这个等式永远为真。其中用到了一些原语(primitive)函数:=:
表示全局定义;o.
表示圆函数,由左侧名词参数选择具体的函数;]
不变动的返回右侧名词参数;^
的一元定义为指数函数;j.
的一元定义为虚数单位0j1
乘以右侧参数y
,而它的二元定义为x + 0j1*y
,即组合左侧参数x
和右侧参数y
成为复数,而二者分别是其实部和虚部;@
表示数学函数复合;=
是等于布尔运算,两侧参数相等返回1
而不等返回0
。
上述相同的隐式计算用APL的现代版本Dyalog APL[4]表达为::
avg ← +⌿ ÷ ≢
cos ← 2 ○ ⊢
sin ← 1 ○ ⊢
j ← {⍺←0 ⋄ ⍺+0j1×⍵} ⍝ j函数的定义不是隐式的
Euler ← *∘j = cos j sin
这里采用直接函数定义了j
函数,其中在{
与}
之间由⋄
分隔的是守卫的表达式序列(这里只有表达式),⍺
指示左参数而⍵
指示右参数,⍺←
指示一元定义需要的缺省左参数。
Unix管道
在Unix脚本中,函数相当于从标准输入接收数据并发送结果至标准输出的计算机程序。例如:
sort | uniq -c | sort -rn
是一个隐式或无点复合,它返回它的每个参数的计数和这些参数,并按照这个计数的递减次序来排序。sort
和uniq
是函数,而-c
和-rn
控制这些函数,但是不提及参数。|
是复合算子。
Python
如下Python代码是对应上节Unix管道命令的函数定义和一序列的运算操作:
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)
aList = [2, 5, 4, 14, 3, 1, 3, 12, 2]
a = sort_rn(uniq_c(sort(aList)))
它可以写为无点样式的没有参数的一序列函数的复合[5]:
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)
b = pipeline(aList)
assert a == b
jq语言
jq是面向JSON的编程语言,使用|
符号来连接过滤器形成流水线。例如:
$ jq -n '[1,2] | add'
3
这里的JSON阵列[1,2]
是求值为阵列的一个jq过滤器。
上述Python章节中例子,在jq中等价的无点风格定义为:
def pipeline: sort | uniq_c | sort_rn;
函数式编程
一个简单例子(用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)程序,它接受一个列表list
,向它应用一个函数operator
,接着基于一个准则criterion
来过滤元素:
mf criteria operator list = filter criteria (map operator list)
它可以表达为无点样式为[6]:
mf = (. map) . (.) . filter
注意如前面所说,在“无点”中的点指称参数而非不使用点,这是常见误解[7]。
串接式编程
在串接式编程语言(和面向堆栈编程语言)中,无点方法也很常用。例如,计算斐波那契数列的过程可以用Factor写为如下:
: fib ( n -- m )
dup 2 < [
[ 1 - fib ] [ 2 - fib ] bi +
] unless ;
参见
- 组合子逻辑
- 串接式编程语言
- 函数级编程
- Joy (编程语言),现代的高度隐式语言
注释和引用
- ^ 1.0 1.1 Tacit programming. [2022-06-11]. (原始内容存档于2022-07-20).
- ^ 2.0 2.1 Manuel Alcino Pereira da Cunha (2005) Point-free Program Calculation
- ^ W. Neville Holmes, ed. (2006) Computers and People
- ^ Dyalog APL. [2022-06-14]. (原始内容存档于2022-06-28).
- ^ Name code not values. Concatenative.org. [2020-10-16]. (原始内容存档于2013-09-29).
- ^ pipermail. [2020-04-18]. (原始内容存档于2012-02-18).
- ^ Pointfree - HaskellWiki. wiki.haskell.org. [2016-06-05]. (原始内容存档于2021-04-28).
外部链接
- Pure Functions in APL and J How to use tacit programming in any APL-like language
- Closed applicative languages 1971 - 1976 ff (页面存档备份,存于互联网档案馆), in John W. Backus (Publications)