学习SICP中用JS写的一些Demo

Cons

理解

Cons 就是 Constitute，用来将两个东西组合成一个对象(Pair).

同时定义了 CAR 和 CDR 来获取这个Pair的左边和右边。

用 Jest 写就是

1 2	expect( CAR(CONS(X,Y)) ).toBe( X ) expect( CDR(CONS(X,Y)) ).toBe( Y )

另外还有 SET_CAR 和 SET_CDR 可以修改这个 Pair对应的值。

实现1

这里的思路就是用一个数组去表示一个 Pair.

应该算是最符合直觉的一种。

const CONS = (x, y) => [x, y]
const CAR = (cons) => cons[0]
const CDR = (cons) => cons[1]
const SET_CAR = (cons, value) => CONS(value, CDR(cons))
const SET_CDR = (cons, value) => CONS(CAR(cons), value)

实现2

这是来自sicp的第一种，也就是用一个if else去实现一个 Pair.

但是从本质上来说，其实这里是用一个函数去表示一个对象。

之前我也知道，JS里面的函数是一级公民，可以作为参数进行传递，也知道怎么去写高阶函数。

但是之前总觉得只有到被完全调用之后，得到具体数值之后，才是有具体意义的。

而这里是第一次让我真的感觉到函数和数据之间的隔阂被打破了。

它不需要被调用来证明自己，就能表示一个直观的东西。

const CONS = (x, y) => (select) => select ? x : y 
const CAR = (cons) => cons(true)
const CDR = (cons) => cons(false)
// `SET_CAR` 和 `SET_CDR` 同上。

实现3

这是来自sicp的另一种，可以看到这里所有功能的具体实现都是在 CONS 中定义的。

整个过程有点绕，需要一段时间思考里面的调用关系。

const CONS =
  (x, y) =>
    (callback) =>
      callback({
        x,
        y,
        setCar: (value) => { x = value },
        setCdr: (value) => { y = value },
      })
const CAR = (cons) => cons(({ x }) => x)
const CDR = (cons) => cons(({ y }) => y)
const SET_CAR = (cons, value) => cons(({ setCar }) => setCar(value))
const SET_CDR = (cons, value) => cons(({ setCdr }) => setCdr(value))

Digital Circuits Simulator

数字电路模拟器，其实是基于观察者模式实现

实现1

Gates

class Gates {
  static buildGate (logicFn) {
    const inputCount = logicFn.length
    return function () {
      let inputs, output
      const wires = [...arguments].filter(s => s)

      switch (wires.length) {
        case inputCount + 1: {
          output = wires.pop()  // pop the last which is output
          inputs = wires        // the rest is inputs
          break
        }
        case inputCount: {
          output = new Wire()   // create output Wire
          inputs = wires
          break
        }
        default: {
          throw new Error(
            `Expect: ${inputCount} input(s) or 1 output.\n` +
            `Actual: ${arguments.length} input(s) or output in total\n`)
        }
      }

      let callback = () => {
        output.signal = logicFn(...inputs.map(input => input.signal))
      }

      inputs.forEach(input => input.addListener(callback))

      return output
    }
  }

  static AND = Gates.buildGate((s1, s2) => s1 && s2)
  static OR = Gates.buildGate((s1, s2) => s1 || s2)
  static NOT = Gates.buildGate((s) => !s)
  static NAND = Gates.buildGate((s1, s2) => !(s1 && s2))
  static NOR = Gates.buildGate((s1, s2) => !(s1 || s2))
  static XOR = Gates.buildGate((s1, s2) => s1 ^ s2)
  static XNOR = Gates.buildGate((s1, s2) => !(s1 ^ s2))
  static BUF = Gates.buildGate((s) => s)
  static IMPLY = Gates.buildGate((s1, s2) => !s1 || s2)
  static NIMPLY = Gates.buildGate((s1, s2) => !(!s1 || s2))
}

Wire

class Wire {
  static wireCount = 0

  // 该线路的标签
  symbol
  // 该线路的信号
  _signal
  // 该线路的影响范围
  listeners = []

  noticeWhenChanging = false

  constructor (
    symbol = 'Wire' + Wire.wireCount++,
    initSignal = 0,
    noticeWhenChanging = false,
  ) {
    this.symbol = symbol
    this.signal = initSignal
    this.noticeWhenChanging = noticeWhenChanging

    this.listeners.push(({ symbol, signal, noticeWhenChanging }) => {
      if (noticeWhenChanging) { console.log(`${symbol} is set to ${signal}`) }
    })
  }

  get signal () { return this._signal }

  set signal (val) {
    val = val ? 1 : 0

    if (this._signal !== val) {
      this._signal = val
      this.listeners.forEach(cb => cb(this))
    }
  }

  // 设置为高电平
  up () { this.signal = 1 }

  // 设置为低电平
  down () { this.signal = 0 }

  // 给一个正脉冲
  upDown () {
    this.up()
    this.down()
  }

  // 给一个负脉冲
  downUp () {
    this.down()
    this.up()
  }

  addListener (cb) {
    this.listeners.push(cb)
    cb(this)
  }
}

实现2

但是理论上，我们可以使用 NOR 或者 NAND 来实现所有逻辑门。

根据逻辑代数的 幂等律 和 对偶律等公式，就可以很容易地证明这一点。

class GeneralGates {
  static NAND = Gates.NAND

  static NOT = (I, O) =>
    GeneralGates.NAND(I, I, O)

  static AND = (I1, I2, O) =>
    GeneralGates.NOT(GeneralGates.NAND(I1, I2), O)

  static OR = (I1, I2, O) =>
    GeneralGates.NAND(GeneralGates.NOT(I1), GeneralGates.NOT(I2), O)

  static NOR = (I1, I2, O) =>
    GeneralGates.NOT(GeneralGates.OR(I1, I2), O)

  static XOR = (I1, I2, O) =>
    GeneralGates.OR(
      GeneralGates.AND(GeneralGates.NOT(I1), I2),
      GeneralGates.AND(GeneralGates.NOT(I2), I1), O)

  static XNOR = (I1, I2, O) =>
    GeneralGates.NOT(GeneralGates.XOR(I1, I2), O)

  static BUF = (I, O) =>
    GeneralGates.NOT(GeneralGates.NOT(I), O)

  static IMPLY = (I1, I2, O) =>
    GeneralGates.OR(GeneralGates.NOT(I1), I2, O)
  
  static NIMPLY = (I1, I2, O) =>
    GeneralGates.NOT(GeneralGates.IMPLY(I1, I2), O)
}

简单逻辑门测试

function autoTestGate (gate, inputCount) {
  let inputs =
    Array(inputCount).fill()
      .map((_, i) => new Wire(String.fromCharCode('A'.charCodeAt() + i)))
  autoTraverseAndObserve(inputs, [gate(...inputs, new Wire('Output'))])
}

// 遍历xs所有可能的信号组合，观察ys的信号
function autoTraverseAndObserve (xs, ys) {
  const table = []
  table.push([
    ...xs.map(x => x.symbol + '\t'), '|',
    ...ys.map(y => y.symbol + '\t')])
  for (let i = 0; i < (1 << xs.length); i++) {
    for (let j = 0; j < xs.length; j++) {
      xs[xs.length - 1 - j].signal = (i >> j) % 2
    }
    table.push([
      ...xs.map(x => x.signal + '\t'), '|',
      ...ys.map(y => y.signal + '\t')])
  }
  table.forEach(line => console.log(...line))
}

  console.log('Test AND')
  autoTestGate(Gates.AND, 2)
  console.log('Test OR')
  autoTestGate(Gates.OR, 2)
  console.log('Test NOT')
  autoTestGate(Gates.NOT, 1)
  console.log('Test NAND')
  autoTestGate(Gates.NAND, 2)
  console.log('Test NOR')
  autoTestGate(Gates.NOR, 2)
  console.log('Test XOR')
  autoTestGate(Gates.XOR, 2)
  console.log('Test XNOR')
  autoTestGate(Gates.XNOR, 2)
  console.log('Test BUF')
  autoTestGate(Gates.BUF, 1)
  console.log('Test IMPLY')
  autoTestGate(Gates.IMPLY, 2)
  console.log('Test NIMPLY')
  autoTestGate(Gates.NIMPLY, 2)

测试结果

展开查看

Test AND
A        B       | Output
0        0       | 0
0        1       | 0
1        0       | 0
1        1       | 1
Test OR
A        B       | Output
0        0       | 0
0        1       | 1
1        0       | 1
1        1       | 1
Test NOT
A        | Output
0        | 1
1        | 0
Test NAND
A        B       | Output
0        0       | 1
0        1       | 1
1        0       | 1
1        1       | 0
Test NOR
A        B       | Output
0        0       | 1
0        1       | 0
1        0       | 0
1        1       | 0
Test XOR
A        B       | Output
0        0       | 0
0        1       | 1
1        0       | 1
1        1       | 0
Test XNOR
A        B       | Output
0        0       | 1
0        1       | 0
1        0       | 0
1        1       | 1
Test BUF
A        | Output
0        | 0
1        | 1
Test IMPLY
A        B       | Output
0        0       | 1
0        1       | 1
1        0       | 0
1        1       | 1
Test NIMPLY
A        B       | Output
0        0       | 0
0        1       | 0
1        0       | 1
1        1       | 0

构建高级组件测试

利用很简单地构建一个SR触发器，并进行测试

class Components {
  static SR_NOR_LATCH (R, S, Q, Q_) {
    Gates.NOR(R, Q_, Q)
    Gates.NOR(S, Q, Q_)
  }
}

const R = new Wire('R')
const S = new Wire('S')
const Q = new Wire('Q')
const Q_ = new Wire('Q_')

Components.SR_NOR_LATCH(R, S, Q, Q_)

R.upDown()
console.log(R.signal)     // 0
console.log(S.signal)     // 0
console.log(Q.signal)     // 0
console.log(Q_.signal)    // 1

S.upDown()
console.log(R.signal)     // 0
console.log(S.signal)     // 0
console.log(Q.signal)     // 1
console.log(Q_.signal)    // 0

Stream

Stream(流) 这个概率其实在 Java8 里面就已经出现了，可以使用Stream来进行一些链式编程，也涉及到函数式编程。

在 JS 里面其实也有对于数组或者可迭代对象的一些可以进行链式编程的方法，比如我前面可能也有用到的一些 map,forEach,reduce,filter等函数。

所以我以前对于Stream的理解，仅仅只是可以进行链式编程的这么一个东西。但是SICP里面的 Stream 让我对于无穷和递归这些概率有了更深的认识。

摘一段我当时写的想法：

怎么构建一个无限的事物？

并不需要真的构建出所有的细节，只需要在我们观察的时候，该对象能构建出我们所观察的部分，就可以被当作是无限的。

一般来说这种事物，包括对于已经被观察的部分的缓存和未被观察的部分的生成器

实现

class Stream {
  _head
  _tailBuilder
  _tailBuffer

  constructor (head, tailBuilder) {
    this._head = head
    this._tailBuilder = tailBuilder
  }

  get head () { return this._head }

  get tail () {
    if (!this._tailBuffer) { this._tailBuffer = this._tailBuilder() }
    return this._tailBuffer
  }

  nth (n) {
    return n ? this.tail.nth(n - 1) : this.head
  }

  log (cb = () => {}) {
    console.log(this.head)
    cb(this, this.head)
    this.tail.log(cb)
  }

  filter (predicate) {
    return predicate(this.head)
      ? new Stream(this.head,
        () => this.tail.filter(predicate))
      : this.tail.filter(predicate)
  }

  map (mapFn) {
    return new Stream(mapFn(this.head), () => this.tail.map(mapFn))
  }

  add (stream) {
    return new Stream(this.head + stream.head, () => this.tail.add(stream.tail))
  }

  // allow stream to use stream[n] to get nth element of stream
  asArray () {
    return new Proxy(this, {
      get (target, property, receiver) {
        const isNumber = (str) => /\d+/.test(str)
        return isNumber(property)
          ? target.nth(parseInt(property))
          : Reflect.get(...arguments)
      },
    })
  }
}

class Sequences {
  // 无穷的1
  static ones =
    new Stream(1,
      () => Sequences.ones)
      .asArray()

  // 全体正整数
  static integers =
    new Stream(1,
      () => Sequences.integers.add(Sequences.ones))
      .asArray()

  // 无穷的斐波那契数列
  static fibs =
    new Stream(0,
      () => new Stream(1, () => Sequences.fibs.add(Sequences.fibs.tail)))
      .asArray()

  // 全体质数
  static primes = (() => {
    // 添加筛法
    Stream.prototype.sieve = function () {
      return new Stream(this.head,
        () => this.tail.filter((n) => n % this.head !== 0).sieve())
    }

    function integerFrom (n) {
      return new Stream(n, () => integerFrom(n + 1))
    }

    return integerFrom(2).sieve()
      .asArray()
  })()
}

Tips:

在Sequences中，我写了四个有趣的无穷数列。

你可以使用类似 Sequences.primes.log() 来查看数列全体

或者使用 Sequences.primes[10]来查看数列的某一项。

Fixed Point 和 Y算子

上面说，“第一次让我真的感觉到函数和数据之间的隔阂被打破了”。

而这里是真的又一次让我对于函数和数据的区别的认识（或者说成见）被打碎。

Fixed Point (不动点) 其实就是对于一个函数，输入等于输出的点。也就是对于 $f:X→X$ ，如果有 $x=f(x)$ ，那么 $x$ 就是 $f$ 的一个不动点。

其中，有些不动点是 吸引的。也就是说，当从一个比较合理的值出发，不断迭代地调用函数，函数的值会在理论上无限接近不动点。

高阶函数的Fixed Point

SICP在这里拿指数函数做例子，但是其实并不局限于指数函数。

如果说写一个递归的指数函数，其实很简单。(当然这里只考虑的是非负整数的指数)

1	const exp = (x, n) => n ? x * exp(x, n - 1) : 1

但是假设我们并【没有】这样的一个指数函数。

但我们只有一个能计算有限次方（比如0）的指数函数，还有一个【以指数函数作为不动点，并且是吸引】的高阶函数，也就是说 $f(exp) = exp$ .

那要怎么得到一个任意次方的指数函数呢？

// 只能计算0次方的指数函数
const brokenExp0 = (x, n) => 1

// 可以看到这个函数，将一个求解x的n次方的问题分解为两个子问题，
// 在这里，它相信g可以完成求解x的n-1次方的问题
const metaExp = (g) => (x, n) => x * g(x, n-1)

// 然后我们可以得到一个新的指数函数
// 这个函数可以计算0次方和1次方
const brokenExp1 = metaExp(brokenExp0)
// 然后不断迭代
const brokenExp2 = metaExp(brokenExp1)
const brokenExp3 = metaExp(brokenExp2)
// ...
const brokenExpN = metaExp(brokenExpN_1)

然后可以看到一个结果就是: 定义 $f \triangleq metaExp\\ g \triangleq brokenExp0$

则有 $\lim_{n \to +\infty} f^n(g) = exp$

然后就可以看出此时 $f(exp)=exp$

Y算子

Y算子，是一种不动点算子，是一个满足 $Y(F)=F(Y(F))$ 的东西。

以 lambda抽象 表示就是 ${\textsf {Y}}=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))$

写成代码的形式就是

const Y = (F) => {
  // Y(F) = loop(loop) = F(loop(loop)) = F(Y(F))
  let loop = (loop) => F(loop(loop))
  return loop(loop)
}

const exp = Y(metaExp)

上面可以看到

1	Y(F) = loop(loop) = F(loop(loop)) = F(Y(F))

然后就形成了一个无穷次的F嵌套，相当于上面写的那个极限

但是代码肯定是不能运行的，运行的唯一结果就是内存溢出。

计算极限

这部分讲的其实也就是停机问题。

也就是无法写出一个函数 isSafe 来判断一个程序对应一个输入是否会停机。

// 假设存在isSafe
let isSafe

// 反例1
// 死循环
const inf = () => (x => x(x))(x => x(x))
const diag1 = (f) => isSafe(f, f) ? inf() : 42
diag1(diag1)

// 反例2
const diag2 = (f) => isSafe(f, f) ? !f(f) : 42
diag2(diag2)