函数式编程与电路

最近正在重温计算机组成原理，看到简单的逻辑单元组成了复杂的加法器， 锁存器，乘法器等等。感受到了计算机自底向上抽象的魅力。于是手痒也想写着玩玩。但是我对各类HDL并不很熟悉。并且又想从无到有构建出这些逻辑结构，体验创造的乐趣。所以我就用js写了一个非常简单的HDL(jshdl)。结果发现电路真的很有趣。这也是我第一次把一些函数式编程的理念完美运用到实际中的体验。加深了我对这两者的理解。下面我会介绍jdhdl和一些有趣细节。

首先定义一个基础的对象:Bit。Bit有两个值0和1。Bit的值由他的源决定。比如bitA.connect(bitB)中，bitB的值由bitA决定，因为他们连接在一起了。当bitA改变的时候bitB也会改变。

除了Bit之外，还有三个基础操作，来产生Bit。对应着电路中的三个基础门电路and, or, not。他们的用法也很简单，由已存在的Bit创造一个新的Bit。例如：

bitA = and(bitB)(bitC)

上面的等式代表一个与门输入两个Bit，得到一个新的Bit。bitA就是bitB和bitC的与。你可能会疑惑，为什么不是and(bitB, bitC)在jshdl中，所有的逻辑都是柯里化函数，这可以提高代码的复用。

在我写的第一个版本中and函数可以接收任意多个Bit，返回所有Bit的与。另一个andM函数能够与两个Bit组（实际电路中不会单用一个Bit。往往会用8/16/32个Bit组来进行运算）。这时如果我需要一个andMs函数用来与多个Bit组，我需要再重新写一个。

仔细观察这一系列函数，我发现这里涉及两种不同的操作：lift2和fold一个是把操作单个Bit的函数lift成操作Bit组的函数，另一个是把一个二元操作变成一个多元操作:

add ---fold--> adds
|
|
lift2
|
|
addM --fold--> andMs

通过定义lift2和fold函数，任何一个二元单Bit操作都能免费获得其余的三个函数了。

有了这些工具，我们就可以定义任何一个电路了（由于我只是简单的设计了一个event base的机制，时序不能很好的体现出来。）在基础电路里面最有趣的就是加法器了，我们现在可以定义一个加法器：

1，定义半加器

//输入两个Bit，输出 结果 和 进位标志
//这边没有使用柯里化，是因为不需要对半加器做变换
const half = (a: Bit, b: Bit): [Bit, Bit] => [xor(a)(b), and(a)(b)]

2， 定义全加器

//全加器的返回和半加器一样，多了一个进位输入
const adder = (a: Bit) => (b: Bit) => (carryIn: Bit): [Bit, Bit] => {
  const [sum1, carryOut1] = half(a, b);
  const [sum2, carryOut2] = half(sum1, carryIn);
  return [sum2, or(carryOut1)(carryOut2)];
}

这样一个单Bit的加法器就完成了。但是我们发现，由于加法器之间需要首尾相连。我们无法用简单的lift2把加法器扩展到两个Bit组之间。这时，我们把加法器看成是一个输入carryIn，输出carryOut的函数，然后定义一个carry 的 Monad：AdderMonad来保存sum值,并且处理carryIn，carryOut。以达到链式调用的目的：

AdderMonad定义：

class AdderMonad {
  constructor(public sums: Bit[], public carryOut: Bit, public lastCarryOut?: Bit) {}
  bind(fn: (carryIn: Bit) => AdderMonad): AdderMonad {
    const result = fn(this.carryOut);
    return new AdderMonad(result.sums.concat(this.sums), result.carryOut, this.carryOut)
  }
}

adder也修改为返回monad形式:

export const adder = (a: Bit) => (b: Bit) => (carryIn: Bit): AdderMonad => {
  const [sum1, carryOut1] = half(a, b);
  const [sum2, carryOut2] = half(sum1, carryIn);
  return new AdderMonad([sum2], or(carryOut1)(carryOut2));
}

修改后的adder用法

//geca + hfdb
adder(a)(b).bind(add(c)(d)).bind(add(e)(f)).bind(add(g)(h))

bind函数相当于把处理adder之间的关系的内容隐藏起来了，从而简化了adder向Bit组的扩展。最后，使用lift2可以将adder扩展为输入Bit组，输出一组处理carry的函数的函数。很简单就能定义出liftAdder:

const liftAdderFn = lift2(adder);

//把函数依次使用carryIn调用
export const liftAdder = (xs: Bit[]) => (ys: Bit[]) => (carryIn: Bit): AdderMonad =>
  liftAdderFn(xs)(ys).reverse().reduce((am, fn) => am.bind(fn), new AdderMonad([], carryIn))

这是我第一次在现实当中使用函数时编程的思想，非常有趣。记录一下。还有一个signal的概念没有介绍，大致就是一个Bit组。更多的代码在这里

⌂