• Bayesian Neural Networks:贝叶斯神经网络

    贝叶斯神经网络,简单来说可以理解为通过为神经网络的权重引入不确定性进行正则化(regularization),也相当于集成(ensemble)某权重分布上的无穷多组神经网络进行预测。

    本文主要基于 Charles et al. 2015[1]

    另发表于知乎

    神经网络的概率模型

    众所周知,一个神经网络模型可以视为一个条件分布模型 P(yx,w)P(\mathbf{y}|\mathbf{x},\mathbf{w}) :输入 x\mathbf{x} ,输出预测值 y\mathbf{y} 的分布, w\mathbf{w}为神经网络中的权重。在分类问题中这个分布对应各类的概率,在回归问题中一般认为是(标准差固定的)高斯(Gaussian)分布并取均值作为预测结果。相应地,神经网络的学习可以视作是一个最大似然估计(Maximum Likelihood Estimation, MLE):

    wMLE=argmaxwlogP(Dw)=argmaxwilogP(yixi,w)\begin{aligned} \mathbf{w}^\mathrm{MLE}&=\arg\max_\mathbf{w}\log P(\mathcal{D}|\mathbf{w})\\ &=\arg\max_\mathbf{w}\sum_i\log P(\mathbf{y}_i|\mathbf{x}_i,\mathbf{w}) \end{aligned}

    其中 D\mathcal{D} 对应我们用来训练的数据集(dataset)。回归问题中我们代入高斯分布就可以得到平均平方误差(Mean Squared Error, MSE),分类问题则代入逻辑函数(logistic)可以推出交叉熵(cross-entropy)。求神经网络的极小值点一般使用梯度下降,基于反向传播(back-propagation, BP)实现。
    MLE 中不对 w\mathbf{w} 的先验概率作假设,也就是认为 w\mathbf{w} 取什么值的机会都均等。如果为 w\mathbf{w} 引入先验,那就变成了最大后验估计(Maximum Posteriori, MAP):

    wMAP=argmaxwlogP(wD)=argmaxwlogP(Dw)+logP(w)\begin{aligned} \mathbf{w}^\mathrm{MAP}&=\arg\max_\mathbf{w}\log P(\mathbf{w}|\mathcal{D})\\ &=\arg\max_\mathbf{w}\log P(\mathcal{D}|\mathbf{w}) + \log P(\mathbf{w}) \end{aligned}

    代入高斯分布可以推出 L2 正则化(倾向于取小值),代入拉普拉斯分布(Laplace)可以推出 L1 正则化(倾向于取 0 使权重稀疏)。

    贝叶斯起来了!

    贝叶斯估计(bayesian estimation)同样引入先验假设,与 MAP 的区别是贝叶斯估计求出 w\mathbf{w} 的后验分布 P(wD)P(\mathbf{w}|\mathcal{D}) ,而不限于 argmax\arg\max 值,这样我们就可以为神经网络的预测引入不确定性。由于我们求得的是分布,基于 w\mathbf{w} 由输入 x^\hat{\mathbf{x}} 预测 y^\hat{\mathbf{y}} 的概率模型就变成了:

    P(y^x^)=EP(wD)[P(y^x^,w)]\begin{aligned} P(\hat{\mathbf{y}}|\hat{\mathbf{x}})=\mathbb{E}_{P(\mathbf{w}|\mathcal{D})}[P(\hat{\mathbf{y}}|\hat{\mathbf{x}},\mathbf{w})] \end{aligned}

    这样我们每次预测 y^\hat{\mathbf{y}} 都得求个期望,问题是这个期望我们并不可能真的算出来,因为这就相当于要计算在 P(wD)P(\mathbf{w}|\mathcal{D}) 上的所有可能的神经网络的预测值。
    另一方面,求后验分布 P(wD)P(\mathbf{w}|\mathcal{D}) 也是件麻烦的事情。众所周知,根据贝叶斯理论,求 P(wD)P(\mathbf{w}|\mathcal{D}) 需要通过:

    P(wD)=P(w,D)P(D)=P(Dw)P(w)P(D)\begin{aligned} P(\mathbf{w}|\mathcal{D})= \frac{P(\mathbf{w},\mathcal{D})}{P(\mathcal{D})} =\frac{P(\mathcal{D}|\mathbf{w})P(\mathbf{w})}{P(\mathcal{D})} \end{aligned}

    这东西也是难解(intractable)的。

    所以,为了在神经网络中引入贝叶斯估计,需要找到方法近似这些东西,并且最好能转化成为求解优化(optimization)问题的形式,这样比较符合我们炼丹师的追求。

    变分估计

    利用变分(variational)的方法,我们可以使用一个由一组参数 θ\theta 控制的分布 q(wθ)q(\mathbf{w}|\theta) 去逼近真正的后验 P(wD)P(\mathbf{w}|\mathcal{D}) ,比如用高斯来近似的话 θ\theta 就是 (μ,σ)(\mu,\sigma),这样就把求后验分布的问题转化成了求最好的 θ\theta 这样的优化问题。这个过程可以通过最小化两个分布的 KL 散度(Kullback-Leibler divergence)实现:

    θ=argminθDKL[q(wθ)P(wD)]=argminθq(wθ)logq(wθ)P(w)P(Dw)dw=argminθDKL[q(wθ)P(w)]Eq(wθ)[logP(Dw)]\begin{aligned} \theta^*&=\arg\min_\theta D_\mathrm{KL}[q(\mathbf{w}|\theta)||P(\mathbf{w}|\mathcal{D})]\\ &=\arg\min_\theta \int q(\mathbf{w}|\theta)\log \frac{q(\mathbf{w}|\theta)}{P(\mathbf{w})P(\mathcal{D}|\mathbf{w})} d\mathbf{w}\\ &=\arg\min_\theta D_\mathrm{KL}[q(\mathbf{w}|\theta)||P(\mathbf{w})] - \mathbb{E}_{q(\mathbf{w}|\theta)}[\log P(\mathcal{D}|\mathbf{w})] \end{aligned}

    这样看起来比前式好多了。写成目标函数(objective function)的形式就是:

    F(D,θ)=DKL[q(wθ)P(w)]Eq(wθ)[logP(Dw)]     (1)\begin{aligned} \mathcal{F}(\mathcal{D},\theta)=D_\mathrm{KL}[q(\mathbf{w}|\theta)||P(\mathbf{w})]-\mathbb{E}_{q(\mathbf{w}|\theta)}[\log P(\mathcal{D}|\mathbf{w})] \end{aligned}\ \ \ \ \ (1)

    这个其实仍然没法算出来,但是至少长得更像能算出来的东西。第一项就是我们的变分后验与先验的 KL 散度;第二项的取值依赖了训练数据。 把第一项叫作复杂性代价(complexity cost),描述的是权重和先验的契合程度;把第二项叫作似然代价(likelihood cost),描述对样本的拟合程度。优化这个目标函数可以看作是炼丹师们最熟悉的正则化,在两种代价中取平衡。

    对于 P(w)P(\mathbf{w}) 的形式, 给出了一个混合尺度高斯先验(scale mixture gaussian prior):

    P(w)=jπN(wj0,σ12)+(1π)N(wj0,σ22)\begin{aligned} P(\mathbf{w})=\prod_{j} \pi \mathcal{N}\left(\mathbf{w}_{j} | 0, \sigma_{1}^{2}\right)+(1-\pi) \mathcal{N}\left(\mathbf{w}_{j} | 0, \sigma_{2}^{2}\right) \end{aligned}

    即每个权重其分布的先验都是两种相同均值、不同标准差的高斯分布的叠加。

    下一步要做的就是继续对目标函数取近似,直到能求出来为止。

    遇事不决,蒙特卡罗

    蒙特卡罗方法(Monte Carlo method)是刻在炼丹师 DNA 里的方法。(1) 中有一个期望不好求,可以使用这种喜闻乐见的办法弄出来。

    众所周知,同样利用贝叶斯估计推导出来的变分自编码器(Variational Auto-Encoder, VAE)[2] 引入了一个妙不可言的重参数化(reparameterize)操作:对于 zN(μ,σ2)z\sim \mathcal{N}(\mu,\sigma^2) ,直接从 N(μ,σ2)\mathcal{N}(\mu,\sigma^2) 采样(sample)会使得 μ\muσ\sigma 变得不可微;为了得到它们的梯度,将 zz 重写为 z=σϵ+μz=\sigma \epsilon+\mu ,其中 ϵN(0,1)\epsilon\sim \mathcal{N}(0,1) ,这样便可以先从标准高斯分布采样出随机量,然后可导地引入 μ\muσ\sigma

    对此进行了推广,证明了对一个随机变量 ϵ\epsilon 和概率密度 q(ϵ)q(\epsilon) ,只要能满足 q(ϵ)dϵ=q(wθ)dwq(\epsilon)d\epsilon=q(\mathbf{w}|\theta)d\mathbf{w},则对于期望也可以使用类似操作得到可导的对期望偏导的无偏估计:

    θEq(wθ)[f(w,θ)]=Eq(ϵ)[f(w,θ)wwθ+f(w,θ)θ]\begin{aligned} \frac{\partial}{\partial \theta} \mathbb{E}_{q(\mathbf{w} | \theta)}[f(\mathbf{w}, \theta)]=\mathbb{E}_{q(\epsilon)}\left[\frac{\partial f(\mathbf{w}, \theta)}{\partial \mathbf{w}} \frac{\partial \mathbf{w}}{\partial \theta}+\frac{\partial f(\mathbf{w}, \theta)}{\partial \theta}\right] \end{aligned}

    利用这一点可以得到 (1) 的蒙特卡罗近似:

    F(D,θ)i=1nlogq(w(i)θ)logP(w(i))logP(Dw(i))     (2)\begin{aligned} \mathcal{F}(\mathcal{D}, \theta) \approx \sum_{i=1}^{n} \log q\left(\mathbf{w}^{(i)} | \theta\right)-\log P\left(\mathbf{w}^{(i)}\right) -\log P\left(\mathcal{D} | \mathbf{w}^{(i)}\right) \end{aligned}\ \ \ \ \ (2)

    其中 w(i)\mathbf{w}^{(i)} 是处理第 i 个数据点时的权重采样。

    [1] 中提出的这个近似把 F(Dθ)\mathcal{F}(\mathcal{D}|\theta) 的 KL 项也给蒙特卡罗了,而其实对于很多先验形式这个 KL 项是可以有解析解的。[1] 这么做的理由是为了配适更复杂的先验/后验形式。另一篇文章 只考虑高斯先验,于是在同样的证据下界中取了 KL 项的解析解。实践中可以根据使用的先验不同来取不同的近似。

    贝叶斯小批梯度下降

    (1) 中的目标函数及 (2) 中的近似都是模型在整个数据集上的下界。实践中的现代炼丹都是采用的小批梯度下降(mini-batch gradient descent),所以需要相应地缩放复杂性代价。假设整个数据集被分为 M 批,最简单的形式就是对每个小批作平均:

    FiEQ(Di,θ)=1MKL[q(wθ)P(w)]Eq(wθ)[logP(Diw)]\begin{aligned} \mathcal{F}_{i}^{\mathrm{EQ}}\left(\mathcal{D}_{i}, \theta\right)=\frac{1}{M} \mathrm{KL}[q(\mathbf{w} | \theta) \| P(\mathbf{w})] -\mathbb{E}_{q(\mathbf{w} | \theta)}\left[\log P\left(\mathcal{D}_{i} | \mathbf{w}\right)\right] \end{aligned}

    这样可以使得 iFiEQ(Di,θ)=F(D,θ)\sum_{i} \mathcal{F}_{i}^{\mathrm{EQ}}\left(\mathcal{D}_{i}, \theta\right)=\mathcal{F}(\mathcal{D}, \theta) 成立。在此基础上 还提出了另一种缩放:

    Fiπ(Di,θ)=πiKL[q(wθ)P(w)]Eq(wθ)[logP(Diw)]\begin{aligned} \mathcal{F}_{i}^{\pi}\left(\mathcal{D}_{i}, \theta\right)=\pi_{i} \mathrm{KL}[q(\mathbf{w} | \theta)\| P(\mathbf{w})] -\mathbb{E}_{q(\mathbf{w} | \theta)} &\left[\log P\left(\mathcal{D}_{i} | \mathbf{w}\right)\right] \end{aligned}

    只要取 π[0,1]M\pi \in[0,1]^{M} 并保证 i=1Mπi=1\sum_{i=1}^{M} \pi_{i}=1 ,那么 i=1MFiπ(Di,θ)\sum_{i=1}^{M} \mathcal{F}_{i}^{\pi}\left(\mathcal{D}_{i}, \theta\right) 就是 F(D,θ)\mathcal{F}(\mathcal{D}, \theta) 的无偏估计。特别地,取 πi=2Mi2M1\pi_{i}=\frac{2^{M-i}}{2^{M}-1} ,可以使在一轮(epoch)训练的初期着重于契合先验、后期着重于拟合数据,带来(玄学的)性能提升。

    局部重参数化

    至此为止的在神经网络权重中引入的不确定性可以看作是全局的(global)不确定性。在神经网络中引入全局不确定性意味着在推理计算(inference)过程中要对全局所有参数进行采样操作,这个代价其实要比想象中高昂——比如一个 1000×10001000\times1000 的全连接层(fully connected layer),对于 M×1000M\times1000 的输入需要 M×1000×1000M\times1000\times1000 个不同的采样,并且更致命的是,一般的神经网络中这样的全连接层,由于参数是同一个矩阵,可以转换为一个 (M,1000) 矩阵和 (1000,1000) 矩阵之间的乘法;而引入了不确定性后,需要采样 M 组不同的 (1000,1000) 参数,进行 M 次 (1,1000) 与 (1000,1000) 的矩阵乘法,对于一般的矩阵并行库而言这是两件完全不同的事情。

    针对这个问题,[3] 观察到,如果所有参数都是独立高斯分布,那么进行矩阵乘法后的结果也都会是独立高斯分布。也就是说,对于 Y=XW\mathbf{Y}=\mathbf{X}\mathbf{W} ,若有

    q(wi,j)=N(μi,j,σi,j2)wi,jW\begin{aligned} q\left(w_{i, j}\right)=N\left(\mu_{i, j}, \sigma_{i, j}^{2}\right) \forall w_{i, j} \in \mathbf{W} \end{aligned}

    那么对于 Y\mathbf{Y} 就会有

    q(ym,jX)=N(γm,j,δm,j)\begin{aligned} q\left(y_{m, j} | \mathbf{X}\right)=N\left(\gamma_{m, j}, \delta_{m, j}\right) \end{aligned}

    其中 γm,j=ixm,iμi,j\gamma_{m, j}=\sum_{i} x_{m, i} \mu_{i, j}δm,j=ixm,i2σi,j2\delta_{m, j}=\sum_{i} x_{m, i}^{2} \sigma_{i, j}^{2}

    有了这个结论,我们就没有必要每次都采样参数 W\mathbf{W} 了,可以直接计算出结果 Y\mathbf{Y} 的均值和方差进行采样,然后反向传播到 W\mathbf{W} 上。这样每次计算进行的采样都是相应数据点的局部(local)采样, 将这个技巧称为局部重参数化(local reparameterization)。

  • 〔吐槽向〕Windows 输入法的 metro 应用兼容性改造

    |

    TL;DR

    微软真是坑爹不允许在 UWP 里用共享内存结果小狼毫就挂了,改成用 Windows 的 named pipe 来做跨进程交互后就可以用了。

    缘由

    重新捡起五笔后,一直苦恼没有一个合用的五笔输入法。身为半个初学者,很看中的一个功能就是五笔反查——总不能每个不会的字都专门打开一个反查工具;而 Windows 自带的五笔只有一个并不好用的五笔拼音混输功能。各种老牌的五笔输入法要么面界太丑要么久不更新,更有甚者会摆出一幅流氓作派。

    几年之前试水过 RIME 输入法,知道它是一个很强大的输入法,可以满足各种定制需求。但是当初的我并没有开发能力,RIME 的定制又稍显复杂,于是并没有继续下去。现在有了需求后回头看,发现 RIME 无疑是最适合现在的我的。

    但是现在要在 Windows 下使用 RIME 却有了个当初没有的新问题——兼容性。作为第一批 Windows 10 用户,无疑需要一个能够在 UWP 应用下正常使用的输入法。但是 RIME 最初的 Windows 前端「小狼毫」却对从 Windows 8 开始的 Metro 应用——包括 Windows 10 的 UWP 都不兼容。原作者也因为无暇分身而放弃了「小狼毫」的维护;其它开发者实现的其它前端又存在各种不稳定的问题——比如 RIME 吧的用户将 RIME 移植到了一个叫作 PIME 的输入法框架下,这个框架的界面实现非常的搓,除此之外它的输入服务实现也很蛋疼,经常崩溃,也没有可靠的异常处理,很多时候需要手动重启输入服务。

    开源界的一大准则就是「你行你上」和「show me the code」。当年使用小狼毫的时候没有经历过什么异常崩溃,说明它在这方面的设计是十分优秀的;现在的主要问题也就是不兼容 Metro 应用而已。既然现在自己有了开发能力,不如自已维护一下,方便自己,也方便他人。

  • Miko: Geisha 的半残编译器

    |

    人的命运就是这么不可预料,最后 Geisha 的编译器实现居然是作为学校的课程设计在考研期间抽空肝出来的。

    因为各种因素,最后交上去的结果和预想的其实差了挺远——比如没来得及实现 GC 所以闭包是残缺的;比如自定义类型根本就没有。不过总归最后做成了一个有结果的东西(虽然是半残的)。

    这篇是暑假期间作为课程报告交上去的文档。至于后续的工作,虽然现在已经考完研了但是突然又多出了一堆事情,只能看看什么时候有空能继续完善了……

    代码当然也在 GitHub 上,只不过 star 都点在了之前那个 Haskell 写的前端 demo 上,这个就无人问津 emmmm

    整体设计

    利用了 rust-peg 生成语法分析程序,以 LLVM 为代码生成后端。

  • 如何编译函数闭包

    |

    // 知乎不仅不给我开专栏还说我这篇文章zz敏感,破网站吃枣药丸

    闭包(英语:Closure),又称词法闭包(Lexical Closure)或函数闭包(function closures),是引用了自由变量的函数。这个被引用的自由变量将和这个函数一同存在,即使已经离开了创造它的环境也不例外。所以,有另一种说法认为闭包是由函数和与其相关的引用环境组合而成的实体。闭包在运行时可以有多个实例,不同的引用环境和相同的函数组合可以产生不同的实例。

    想要实现一个同时支持词法作用域与 first-class function 的编程语言,一个重要的转换就是所谓的 lambda-lifting:把嵌套函数定义(包括匿名函数)转换为独立的全局函数定义;把自由变量的引用转换为参数传递。

  • 基于 Hash 与 Winnowing 方法的文档查重

    这只是一篇实验报告

    设计思路

    基于现实计算能力考虑,许多大段文档之间的相似性比较不可能使用传统的文本 diff 算法等耗时长的方法。Hash 值可以在一定程度上反应数据的特征;但是一般的 Hash 方法强调避免碰撞,源数据的少许改变就可以引起 Hash 值的较大变化。对于查重来说,需要提取出文档的特征,这个特征在源数据相似时也应具有相似性。

    Winnowing 方法是 Saul Schleimer 等提出的提取文档特征(文档指纹)的方法。通过对文档的 K-gram 序列进行 hash ,提取出能够反应文档相似性的特征值序列,再对这个特征值序列进行比较[1],得到的相同特征值的比例即可反映出文档之间的相似性。

  • Windows LLVM 环境的二三事

    |

    讲道理,考研党被这种配环境的事情打扰了咸鱼的生活是很不开心的。

    起因是 Haskell 的 LLVM binding —— llvm-general 在 Hackage 上只支持到 3.5 版本。当然 repo 里是有后续版本的,但是作者在 issues 里说后续的版本并没有弄好。

    既然如此那就装 3.5 吧。然而下载了 LLVM 3.5.2 的源码后,Cmake 很顺利,用 VS 2017 打开也很顺利,然而编译的时候报错

    这里假装有编译 log (好吧忘记存了)

    总之就是某个类的方法后有 const 限定符,然后调用的上下文却又不是返回 const 于是不给过。

    奇怪的是报错的位置是 VS 提供的标准库文件。这就很尴尬了。我要么改 VS 的标准库要么研究一波 LLVM 源码。

    在 WSL 里试了一下,无痛编译。看来是 VS 有什么蛋疼的限制。网上稍微搜了一圈也没发现有类似情况(毕竟 3.5 的年代他们还没官方支持 VS 编译吧)。于是决定上 MinGW 来构建。

    使用 CMake 生成 MinGW 的 makefile 并没有问题,然而在 make 的时候提示命令语法错误

    命令语法不正确。
    mingw32-make.exe[2]: *** [tools\lto\CMakeFiles\LTO_exports.dir\build.make:61: tools/lto/LTO.def] Error 1
    mingw32-make.exe[2]: *** Deleting file 'tools/lto/LTO.def'
    mingw32-make.exe[1]: *** [CMakeFiles\Makefile2:9977: tools/lto/CMakeFiles/LTO_exports.dir/all] Error 2
    mingw32-make.exe: *** [Makefile:151: all] Error 2

    找到了这个 build.make 发现这一行的命令很奇怪

    cd /d C:\Users\hcyue\code\llvm-3.5.2.build\tools\lto && "C:\Program Files\CMake\bin\cmake.exe" -E echo EXPORTS > LTO.def
    cd /d C:\Users\hcyue\code\llvm-3.5.2.build\tools\lto && type C:/Users/hcyue/code/llvm-3.5.2.src/tools/lto/lto.exports >> LTO.def

    纵横 Windows 这么多年没见过 cd 还可以带个 /d 参数的 似乎 powershell 的 cd 并不支持 /d 参数。那把它删了吧。

    之后继续报错,link 的时候找不到 symbol。发现是刚刚改的那两行生成的目标文件 LTO.def 有问题,不知道为什么没有写入成正常的文本文件,而是二进制文件(VS code 打开提示文件过大或为二进制文件)。直接 type 出来是一个奇怪的、字距拉得很开的、看起来像是文本文件的格式。很气。

    然而既然 .def 反正是文本文件,我大不了手动构建一下 def 。于是手动运行命令把 lto.exports 里的东西 type 出来

    type C:/Users/hcyue/code/llvm-3.5.2.src/tools/lto/lto.exports

    得到一大堆符号名

    lto_get_error_message
    lto_get_version
    lto_initialize_disassembler
    lto_module_create
    lto_module_create_from_fd
    lto_module_create_from_fd_at_offset
    lto_module_create_from_memory
    (……一大堆 lto 符号名)
    LLVMCreateDisasm
    LLVMCreateDisasmCPU
    LLVMDisasmDispose
    LLVMDisasmInstruction
    LLVMSetDisasmOptions

    新建个 LTO.def 把原来的覆盖掉,贴进去。

    重新运行 cmake --build . ,终于过了。

  • 使用 Parsec 处理左递归

    |

    在给之前写的 Lisp 解释器之前套上表达式语法时,遇到这样几条文法

    ExprFactor...ExprsExpr,ExprsFactorIntegerApplyIdentify...(Expr)Integer......ApplyFactor(Exprs)\begin{aligned} Expr & \rightarrow Factor ... \\\\ Exprs & \rightarrow Expr , Exprs\\\\ Factor & \rightarrow Integer|Apply|Identify|...|{(} {Expr} {)} \\\\ Integer & \rightarrow... \\\\ ...\\\\ Apply & \rightarrow Factor ( Exprs ) \end{aligned}

    显然,non-terminal ApplyApply 的派生最左端会进入 FactorFactor ,之后又会回到 ApplyApply 。教科书式的左递归。

  • Call With Current Continuation: Coroutine

    通过嵌套 call/cc 可以方便的实现协程

    (define (coroutine routine)
    (let ((current routine)
    (status 'suspended))
    (lambda args
    (cond ((null? args)
    (if (eq? status 'dead)
    (error 'dead-coroutine)
    (let ((continuation-and-value
    (call/cc (lambda (return)
    (let ((returner
    (lambda (value)
    (call/cc (lambda (next)
    (return (cons next value)))))))
    (current returner)
    (set! status 'dead))))))
    (if (pair? continuation-and-value)
    (begin (set! current (car continuation-and-value))
    (cdr continuation-and-value))
    continuation-and-value))))
    ((eq? (car args) 'status?) status)
    ((eq? (car args) 'dead?) (eq? status 'dead))
    ((eq? (car args) 'alive?) (not (eq? status 'dead)))
    ((eq? (car args) 'kill!) (set! status 'dead))
    (true nil)))))
  • Write You a Scheme

    |

    撸了个 Scheme 解释器,也算是拿 Haskell 做过东西了(虽然只是个玩具

    最大的体会就是,既熟悉了 Haskell,也巩固了 Scheme (虽然看过 SICP 但是并不是很明白它的 quosiquote 和 call/cc 之类的鬼东西

    本来是打算自己定义一门语言(像这个),但是发现挺麻烦的(大雾),而且我比较关心的也是解释执行的过程,于是还是决定把 Scheme 实现一下。大体上是跟着 Write Yourself a Scheme in 48 Hours 来的,在它的基础上增加了 Continuation 之类的玩意儿

  • 什么是函数式编程思维?

    |

    我为什么要把我的知乎回答搬到这里呢……大概是太久没发东西了来凑数吧。

    作者:nameoverflow

    链接:https://www.zhihu.com/question/28292740/answer/100284611

    来源:知乎

    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    函数式编程与命令式编程最大的不同其实在于:

    函数式编程关心数据的映射,命令式编程关心解决问题的步骤

    这里的映射就是数学上“函数”的概念——一种东西和另一种东西之间的对应关系。

    这也是为什么“函数式编程”叫做“函数式编程”。

    这是什么意思呢?

    假如,现在你来到 google 面试,面试官让你把二叉树镜像反转一下(大雾

    几乎不假思索的,就可以写出这样的 Python 代码:

    def invertTree(root):
    if root is None:
    return None
    if root.left:
    invertTree(root.left)
    if root.right:
    invertTree(root.right)
    root.left, root.right = root.right, root.left
    return root

    好了,现在停下来看看这段代码究竟代表着什么——

    它的含义是:首先判断节点是否为空;然后翻转左树;然后翻转右树;最后左右互换。

    这就是命令式编程——你要做什么事情,你得把达到目的的步骤详细的描述出来,然后交给机器去运行。

    这也正是命令式编程的理论模型——图灵机的特点。一条写满数据的纸带,一条根据纸带内容运动的机器,机器每动一步都需要纸带上写着如何达到。

    那么,不用这种方式,如何翻转二叉树呢?

    函数式思维提供了另一种思维的途径——

    所谓“翻转二叉树”,可以看做是要得到一颗和原来二叉树对称的新二叉树。

    这颗新二叉树的特点是每一个节点都递归地和原树相反。

    用 haskell 代码表达出来就是:

    data Tree a = Nil | Node a (Tree a) (Tree a)
    deriving (Show, Eq)
    invert :: Tree a -> Tree a
    invert Nil = Nil
    invert (Node v l r) = Node v (invert r) (invert l)

    (防止看不懂,翻译成等价的 python )

    def invert(node):
    if node is None:
    return None
    else
    return Tree(node.value, invert(node.right), invert(node.left))

    这段代码体现的思维,就是旧树到新树的映射——对一颗二叉树而言,它的镜像树就是左右节点递归镜像的树。

    这段代码最终达到的目的同样是翻转二叉树,但是它得到结果的方式和 python 代码有着本质的差别:通过描述一个 旧树->新树 的映射,而不是描述“从旧树得到新树应该怎样做”来达到目的。

    那么这样思考有什么好处呢?

    首先,最直观的角度来说,函数式风格的代码可以写得很精简,大大减少了键盘的损耗(

    更重要的是,函数式的代码是“对映射的描述”,它不仅可以描述二叉树这样的数据结构之间的对应关系,任何能在计算机中体现的东西之间的对应关系都可以描述——比如函数和函数之间的映射(比如 functor);比如外部操作到 GUI 之间的映射(就是现在前端热炒的所谓 FRP)。它的抽象程度可以很高,这就意味着函数式的代码可以更方便的复用。

    同时,将代码写成这种样子可以方便用数学的方法进行研究(这就是为什么可以扯上“___范畴上的___”这种数学上的高深概念)

    至于什么科里化、什么数据不可变,都只是外延体现而已。