隱式編程
隱式(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)