跳至內容

隱式編程

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

隱式(tacit)編程[1],或稱為函數級編程,是一種編程范型,也叫做無點(point-free)樣式。其中函數定義不標示所要操作的參數(或稱「」),轉而函數定義只是其他函數的複合,比如那些操縱參數的組合子。隱式編程有着理論價值,因為嚴格的使用複合導致程序非常適配於方程式推理英語Equational logic[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

這裡採用直接函數英語Direct function定義了j函數,其中在{}之間由分隔的是守衛的表達式序列(這裡只有表達式),指示左參數而指示右參數,⍺←指示一元定義需要的缺省左參數。

Unix管道

[編輯]

在Unix腳本中,函數相當於從標準輸入接收數據並發送結果至標準輸出的計算機程序。例如:

sort | uniq -c | sort -rn

是一個隱式或無點複合,它返回它的每個參數的計數和這些參數,並按照這個計數的遞減次序來排序。sortuniq是函數,而-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

函數式編程

[編輯]

一個簡單例子(用Haskell語言)是在一個列表上作合計的函數。編程者可以使用有點方法(相較於值級編程)而遞歸的定義這個合計為:

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

但是,注意到作為一種摺疊(fold),編程者可以將它改寫為:

sum xs = foldr (+) 0 xs

因而參數是不需要的,進而將它改寫成如下無點樣式:

sum = foldr (+) 0

另一個例子使用函數複合英語Function composition (computer science)

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 ;

參見

[編輯]

注釋和引用

[編輯]
  1. ^ 1.0 1.1 Tacit programming. [2022-06-11]. (原始內容存檔於2022-07-20). 
  2. ^ 2.0 2.1 Manuel Alcino Pereira da Cunha (2005) Point-free Program Calculation
  3. ^ W. Neville Holmes, ed. (2006) Computers and People
  4. ^ Dyalog APL. [2022-06-14]. (原始內容存檔於2022-06-28). 
  5. ^ Name code not values. Concatenative.org. [2020-10-16]. (原始內容存檔於2013-09-29). 
  6. ^ pipermail. [2020-04-18]. (原始內容存檔於2012-02-18). 
  7. ^ Pointfree - HaskellWiki. wiki.haskell.org. [2016-06-05]. (原始內容存檔於2021-04-28). 

外部連結

[編輯]