隐式编程

隐式（tacit）编程，或称为函数级编程，是一种编程范型，也叫做无点（point-free）样式。其中函数定义不标示所要运算的被称为“点”的参数，转而函数定义只是其他函数的复合，比如那些操纵参数的组合子。隐式编程有着理论价值，因为严格的使用复合导致程序适配于等式逻辑。隐式编程是特定编程语言的天然样式，这包括了APL的一些现代实现和方言，和串接式语言比如Forth。由于缺少参数命名，认为这种风格导致了不必要的晦涩难懂的人，给它起了个绰号叫做“无意义”（pointless）风格。

## 管道主范型语言

以管道作为主范型的脚本语言有：

### Unix shell

在Unix shell脚本中，命令是从标准输入接收数据并发送结果至标准输出的过滤器 (软件)。例如：

```bash
sort | uniq -c | sort -rn
```

可以视为一个隐式或无点复合，它返回它的每个参数的计数和这些参数，并按照这个计数的递减次序来排序。命令`sort`和`uniq`相当于函数，而`-c`和`-rn`是控制这些函数的选项，但是不提及参数。管道`|`相当于函数复合算子。下面是其用例：

```console
$ send () { for i in "$@"; do echo $i; done }
$ send 2 4 3 1 3 12 2 | sort | uniq -c | sort -rn
      2 3
      2 2
      1 4
      1 12
      1 1
```

### jq语言

jq是面向JSON的纯函数式编程语言，它使用`|`符号来连接过滤器形成流水线。例如：

```console
$ echo '[1,2]' | jq 'add/length'
1.5
$ jq -n '[1,2] | add/length'
1.5
```

这里jq内的JSON阵列`[1,2]`是求值为阵列的一个jq过滤器。尽管类似于Unix流水线，jq流水线允许将到来数据，如同并行的发送到在`|`右手端的多于一个接收者。

上述Unix管道中的命令例子，在jq中等价的无点风格定义为：

```python
def uniq_c:
    map(tostring) 
    | reduce .[] as $i ({}; .[$i] += 1)
    | to_entries | map([.value, .key]);
def sort_nr:
    sort | reverse | map([.[0], (.[1]|tonumber)]);
[2, 4, 3, 1, 3, 12, 2] 
| sort | uniq_c | sort_nr
```

将这段代码保存入`pipeline.jq`文件中，下面是其执行结果：

```console
$ jq -nc -f ./pipeline.jq 
[[2,3],[2,2],[1,4],[1,12],[1,1]]
```

## 串接式语言

在串接式编程语言和面向堆栈编程语言中，主要采用的就是无点方法，调用函数所给出的参数压入堆栈之中而不需要给它们显式的命名。例如，计算斐波那契数的过程，在Unix的dc命令中可实现为：

```bash
# F(x):
#   1 < x ? G(x) : x
# G(x):
#   F(x-1) + F(x-2)
# F()
[d1<G]sF [d 1- lFx r 2- lFx +]sG lFx
```

下面是其用例：

```console
$ echo 7 | dc -e '? [d1<G]sF [d 1- lFx r 2- lFx +]sG lFx p'
13
```

在Factor中可与其等价的实现为：

```factor
: fib ( n -- Fn )
    dup 1 > [
        [ 1 - fib ] [ 2 - fib ] bi +
    ] when ;
```

这里的`( n -- Fn )`是叫做“堆栈作用”声明的一种注释。

## APL系语言

在APL的一些当代方言中，允许将函数组合入服从几个规则的“列车”（train）；这允许建立复杂的派生函数，而不需要显式指定任何参数；实现了列车的APL方言包括：J语言、Dyalog APL、dzaima/APL、ngn/apl和NARS2000。

### J语言

在J语言中，下列在一个数值的列表（阵列）上计算平均值的函数采用了一种无参数样式代码：

```j
avg=: +/ % #
```

`+/`通过将求和（`+`）插入（`/`）到一个阵列的所有元素之间来计算它们的合计值。`#`总计一个阵列的元素数目。`%`用`+/`这个阵列的结果值除以`#`这个阵列的结果值。

欧拉公式$e^{ix} = \cos x + i\sin x$可隐式表达为：

```j
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`。

### Dyalog APL

上述相同的隐式计算用APL的现代版本Dyalog APL表达为：

```APL
avg ← +⌿ ÷ ≢

cos ← 2 ○ ⊢
sin ← 1 ○ ⊢
j   ← {⍺←0 ⋄ ⍺+0j1×⍵}  ⍝ j函数的定义不是隐式的
Euler ← *∘j = cos j sin
```

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

## 纯函数式语言

下面是采用纯函数式编程语言Haskell的一个简单例子，它在一个列表上作合计的函数。编程者可以使用“有点”（pointed）也称为值级编程的方法，而递归的定义这个合计为：

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

这是一种折叠（fold）运算，编程者可以将它改写为：

```haskell
sum xs = foldr (+) 0 xs
```

这里的参数是不必须的，进而将它改写成如下“无点”也称为函数级编程的样式：

```haskell
sum = foldr (+) 0
```

Haskell拥有函数复合 (计算机科学)算子：

```haskell
(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)
```

它有如下性质：

```haskell
f . g = f(g) = (.) f g
f . g = (f .) g = ((.) f) g
f . g = (. g) f
```

这里的`((.) f)`和`(. g)`，分别称为`.`的左“分节”（section）和右“分节”，是对这个中缀算子的左侧和右侧部分应用。左分节的`((.) f)`表示形式，在从左至右分析之时比`(f .)`要易于区分于右分节`(. g)`。在“无点”中的点（point）指称参数，而非不使用点号（period）。

下面的例子展示其用法，给出一个函数`p`的定义：

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

在伪代码形式下，对函数$f(x, y)$的右结合性的柯里化形式$\text{curry}(f) = \lambda x.(\lambda y.(f(x,y))) = \lambda x. \lambda y. f(x,y)$，采用括号显式的表示出其函数应用的左结合性，即$\text{curry}(f) \; x \;y = (\text{curry}(f) \; x) \;y$，经过如下推导：

```haskell
p = \x -> \y -> \z -> f (g x y) z
  = \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
  = ((.) f) . g
```

它可以归约成无点的等价定义：

```haskell
p = ((.) f) . g
```

这里最右侧的`g`首先接受从左至右的实际参数，而随后接受余下的从左至右的实际参数的左分节`((.) f)`，由于复合运算的右结合性它必须保留最外层括号。

下面是一个复杂一些的例子，这里的`mf`是一个先做映射（map）再加过滤器（filter）的函数，它接受一个列表`list`，向它应用一个函数`operator`，接着基于一个准则`criteria`来过滤元素：

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

在伪代码形式下，设

```haskell
x = criteria; y = operator; z = list
```

经过如下推导：

```haskell
mf = \x -> \y -> \z -> filter x (map y z)
   = \x -> \y -> \z -> (filter x) ((map y) z)
   = \x -> \y -> \z -> (filter x) . (map y) z
   = \x -> \y -> (filter x) . (map y)
   = \x -> \y -> ((.) (filter x)) (map y)
   = \x -> \y -> ((.) . filter x) . map y
   = \x -> ((.) . filter x) . map
   = \x -> (. map) ((.) . filter x)
   = \x -> (. map) . ((.) . filter) x
   = (. map) . ((.) . filter)
```

它可以归约为无点样式：

```haskell
mf = (. map) . (.) . filter
```

这里最右侧的左分节`(.) . filter`首先接受从左至右的实际参数，由于复合运算的右结合性它可以省略最外层括号；而随后接受余下的从左至右的实际参数的是右分节`(. map)`，由于复合运算的右结合性它必须保留最外层括号。

## Python

如下Python代码中的函数定义和一序列的运算，对应前面示例中Unix管道中的命令：

```python
def sort(argv):
    return sorted(argv, key=str)

def uniq_c(argv):
    counts = {}
    for i in argv:
        counts[i] = counts.get(i, 0) + 1
    return ((v, 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 = [2, 4, 3, 1, 3, 12, 2]
b = sort_rn(uniq_c(sort(a)))   
```

这里的`uniq_c()`所采用的实现方法，不要求其输入数据是有序的。

基于标准库的函数式编程工具`functools`中的部分应用函数`partial()`和归约函数`reduce()`，这个例子可以写为无点样式的没有参数的一序列函数的复合：

```python
from functools import partial, reduce

def compose_left(*func_list):
    return partial(reduce, lambda v, f: f(v), func_list)

c = compose_left(sort, uniq_c, sort_rn)(a)
assert b == c
```

这里用到的标准库函数：

- 从左至右地在可迭代对象`iterable`的项目上，累计应用有两个实际参数的函数`function`，从而将`iterable`归约成一个单一的值。给`function`的左参数是累计值，而右参数是来自`iterable`的更新值。如果可选的初始值`initial`存在，则将它用作最初的累计值。
- 返回一个新的`partial`对象。这个对象在被调用时表现得如同`func(*args, **keywords)`，这里`args`是位置实际参数列表，而`keywords`是关键字实际参数字典。它在被调用之时，如果提供了更多的实际参数，则将它们添加到`args`；如果提供了额外的关键字实际参数，则用它们扩展和覆盖`keywords`。

## 外部链接

- From Function-Level Programming to Pointfree Style
- 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)