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
.
应该算是最符合直觉的一种。
1 2 3 4 5 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里面的函数是一级公民,可以作为参数进行传递,也知道怎么去写高阶函数。
但是之前总觉得只有到被完全调用之后,得到具体数值之后,才是有具体意义的。
而这里是第一次让我真的感觉到函数和数据之间的隔阂被打破了。
它不需要被调用来证明自己,就能表示一个直观的东西。
1 2 3 4 const CONS = (x, y ) => (select ) => select ? x : y const CAR = (cons ) => cons(true )const CDR = (cons ) => cons(false )
实现3
这是来自sicp的另一种,可以看到这里所有功能的具体实现都是在 CONS
中定义的。
整个过程有点绕,需要一段时间思考里面的调用关系。
1 2 3 4 5 6 7 8 9 10 11 12 13 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 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() inputs = wires break } case inputCount: { output = new 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 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
来实现所有逻辑门。
根据逻辑代数的 幂等律
和 对偶律
等公式,就可以很容易地证明这一点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 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) }
简单逻辑门测试
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 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' ))]) } 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触发器,并进行测试
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 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) console .log(S.signal) console .log(Q.signal) console .log(Q_.signal) S.upDown() console .log(R.signal) console .log(S.signal) console .log(Q.signal) console .log(Q_.signal)
Stream
Stream(流)
这个概率其实在 Java8
里面就已经出现了,可以使用Stream
来进行一些链式编程,也涉及到函数式编程。
在 JS
里面其实也有对于数组或者可迭代对象的一些可以进行链式编程的方法,比如我前面可能也有用到的一些 map
,forEach
,reduce
,filter
等函数。
所以我以前对于Stream
的理解,仅仅只是可以进行链式编程的这么一个东西。但是SICP里面的 Stream
让我对于无穷和递归这些概率有了更深的认识。
摘一段我当时写的想法:
怎么构建一个无限的事物?
并不需要真的构建出所有的细节,只需要在我们观察的时候,该对象能构建出我们所观察的部分,就可以被当作是无限的。
一般来说这种事物,包括对于已经被观察的部分的缓存 和未被观察的部分的生成器
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 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)) } 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 { 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 f:X→X f : X → X ,如果有x = f ( x ) x=f(x) x = f ( x ) ,那么x x x 就是f f f 的一个不动点。
其中,有些不动点是 吸引
的。也就是说,当从一个比较合理的值出发,不断迭代地调用函数,函数的值会在理论上无限接近不动点。
高阶函数的Fixed Point
SICP在这里拿指数函数做例子,但是其实并不局限于指数函数。
如果说写一个递归的指数函数,其实很简单。(当然这里只考虑的是非负整数的指数)
1 const exp = (x, n ) => n ? x * exp(x, n - 1 ) : 1
但是假设我们并【没有】这样的一个指数函数。
但我们只有一个能计算有限次方(比如0)的指数函数,还有一个【以指数函数作为不动点,并且是吸引】的高阶函数,也就是说 f ( e x p ) = e x p f(exp) = exp f ( e x p ) = e x p .
那要怎么得到一个任意次方的指数函数呢?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 const brokenExp0 = (x, n ) => 1 const metaExp = (g ) => (x, n ) => x * g(x, n-1 )const brokenExp1 = metaExp(brokenExp0)const brokenExp2 = metaExp(brokenExp1)const brokenExp3 = metaExp(brokenExp2)const brokenExpN = metaExp(brokenExpN_1)
然后可以看到一个结果就是: 定义 f ≜ m e t a E x p g ≜ b r o k e n E x p 0
f \triangleq metaExp\\
g \triangleq brokenExp0
f ≜ m e t a E x p g ≜ b r o k e n E x p 0
则有 lim n → + ∞ f n ( g ) = e x p
\lim_{n \to +\infty} f^n(g) = exp
n → + ∞ lim f n ( g ) = e x p
然后就可以看出此时 f ( e x p ) = e x p
f(exp)=exp
f ( e x p ) = e x p
Y算子
Y算子,是一种不动点算子 ,是一个满足 Y ( F ) = F ( Y ( F ) ) Y(F)=F(Y(F)) Y ( F ) = F ( Y ( F ) ) 的东西。
以 lambda抽象
表示就是Y = λ f . ( λ x . f ( x x ) ) ( λ x . f ( x x ) ) {\textsf {Y}}=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)) Y = λ f . ( λ x . f ( x x ) ) ( λ x . f ( x x ) )
写成代码的形式就是
1 2 3 4 5 6 7 const 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
来判断一个程序对应一个输入是否会停机。
1 2 3 4 5 6 7 8 9 10 11 12 13 let isSafeconst inf = () => (x => x(x))(x => x(x))const diag1 = (f ) => isSafe(f, f) ? inf() : 42 diag1(diag1) const diag2 = (f ) => isSafe(f, f) ? !f(f) : 42 diag2(diag2)
就和罗素悖论以及哥德尔数一样,其实都是通过 自指
和 否定
来形成一种不完备的状态。