再谈js闭包

网上关于 js 闭包的文章多如牛毛,这里之所以再写一篇,主要是因为网上的那些文章要么对初学者不够友好,要么根本就没有谈到重点。在读过那些文章后的很长一段时间里,我对闭包都是似懂非懂。直到在学 react 的过程中逐渐接触函数式编程,才开始真正理解闭包。

Trick

请先思考一下下面两段代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function createFunction() {
let arr = [];
for (var i = 0; i < 5; i++) {
arr[i] = function () {
return i;
};
}
return arr;
}
const result = createFunction().map(e => e());
console.log(result); // [5, 5, 5, 5, 5]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function counter() {
let n = 0;
return {
increase() { ++n; },
get() { return n; },
};
}
const cnt1 = counter();
const cnt2 = counter();
cnt1.increase();
console.log(cnt1.get()); // 1
console.log(cnt2.get()); // 0

在往下阅读之前,请再次确保你有花时间理解上面两段代码。虽然它们跟下文内容并没有一毛钱关系,不过反正没事烧烧脑也没什么坏处。。。
这里我想表达的只是,网上大量关于闭包的文章大抵都遵循这个模式,先制造一堆跟上面例子类似的函数,之后让读者尝试给出运行结果,最后在配合上自己的一顿讲解,仿佛能理解这些代码就是懂了闭包。而事实却是,能看懂这些代码并不代表你就理解了闭包,理解闭包之后再看这些代码也不一定就都能立刻指出运行结果。

阅读全文

B-tree数据结构

几乎所有文件系统索引,数据库索引,都需要用到B-tree或其变种。因此对于码农而言,理解它如何工作还是相当有必要的。然而我最近阅读了很多相关的文章,它们往往一上来就试图跟读者解释branchingFactor/degree, B-1<=keys<2B-1,B<=children<2B blablabla...,在读者还不懂原理时就开始描述实现细节。导致像我一样没学过正统cs课程的野生码农严重怀疑自己的智商。这篇文章试图向跟我一样的小白来描述B-tree(前提是你能理解二分查找)。

一.B tree,B-tree,B+tree

如果你在google搜索B-tree数据结构,你可能会找到以上三个关键字相关的文章,这一度让我觉得它们是三种不同的数据结构(既然有BPlusTree,很容易让人想到还有BMinusTree,再加上一些不负责任的翻译版算法书竟然丧心病狂的使用 B- tree (注意空格)来标识B-tree)。事实上这里的 - 只是连字符,B-tree与B tree是同一回事。而B+tree则是它们的一个演化版。当然你也许还会发现一些文章中的B-tree和另一些文章中的B tree有着不同的实现。请依然不要被误导,我读了大概20来篇B-tree相关的文章,至今没有发现两个完全相同的实现。。。

阅读全文

lambda calculus:Y-combinator

上篇文章的末尾提到了一个问题,如何使用λ演算实现递归函数?其中最出名的解决方案是由数学家Haskell B. Curry发现的一个被称为Y-combinator的函数。

一.推导过程

Y-combinator简单来说就是一个输入函数,返回该函数递归版本的函数。关于它的推导我读了很多文章,以下是我总结的一个个人认为比较好理解的版本。(本文代码,可以在y-combinator-js仓库中下载)

Step1

首先回到大家学习递归函数的起点,阶乘函数,以下是js版本:

1
2
3
4
5
const FACT10 = 3628800;
function factorial(n) {
return n === 0 ? 1 : n * factorial(n - 1);
}
factorial(10).should.equal(FACT10);

现在我们的问题是如何将其转换为合法的λ表达式,换句话说如何将其转换为匿名函数?唯一的可能就是把factorial作为参数传入,下面是修改后的版本:

1
2
3
4
5
6
7
8
9
10
11
//注意下面的anonymous函数名是不必要的,可以直接写成立即执行函数(IIFE),之所以我没那样写是为了读起来更清晰
//es5
function anonymous1(factorial) {
return function (n) {
return n === 0 ? 1 : n * factorial(n - 1);
};
}
//es6
const anonymous2 = f => (n => n == 0 ? 1 : n * f(n - 1));
anonymous1(factorial)(10).should.equal(FACT10);
anonymous2(factorial)(10).should.equal(FACT10);

现在已经可以使用λ表达式来描述上面的递归函数了,λ演算版本大概长这样(看不懂不要紧,描述的意思跟上面的anonymous函数是一样的)

1
λf.λn.ISZERO n 1 (MULT n (f (PRED n)))

不过事情并没有这么简单,仔细想想我们刚才干了啥?我们定义了一个阶乘函数,但是这个阶乘函数却需要一个已经存在的阶乘函数作为参数才可以正常工作,它就像这个手电筒。


electric torch

换句话说,如果给上面的anonymous函数传入一个阶乘函数,它就能返回一个阶乘函数,如果传入的不是阶乘函数,返回的也肯定不是阶乘函数(请叫我达文西...)。

阅读全文

lambda calculus:Introduction

λ演算是函数式编程范式的理论基础,然而我读了两本关于fp的书(《java8函数式编程》,《javascript函数式编程》)都没有提到它,因此自己在网上看了一些资料,并写了这篇作为学习心得。

一.λ演算(lambda calculus简称LC)与图灵机

首先,λ演算的提出者丘奇(Alonzo Church)是普林斯顿大学的教授。1935年,丘奇发表论文使用λ演算证明基本数论中存在不可解决的问题。1936年4月,丘奇指出自己的那篇论文可以推论出著名的判定性问题(Hilbert Decision-problem)是不可解决的。1936年5月,图灵发表论文使用他自己假想的计算机器(后被称为图灵机)证明了同一个问题。当时丘奇几乎是世界上唯一能够验证这篇论文正确性的人。因此丘奇将图灵收入门下读博士。之后他们共同提出了邱奇-图灵论题(Church–Turing thesis),该论题的核心思想是

如果某个算法是可计算的(Computability),那这个算法同样可以被图灵机,以及λ演算所实现,图灵机与λ演算是等价的。

阅读全文

加密算法简介

最近听到一个来公司面试的码农说他使用Base64加密数据(Base64是一种编码格式,在编码解码计算过程中不会丢失信息量。通俗点说就相当于把“你好”加密成了“hello”),这跟明文没什么区别,如果一个hacker有本事截获你的数据,你不可能指望他不会解码Base64。这篇文章希望能分享一些关于加密的常识。

一.散列函数(Hash function)

1.常见误区

关于加密算法,最常见的一个误区在于认为MD5,SHA1,SHA256就是加密算法,其实它们只是用来实现加密算法的一部分,更准确的说,它们只是散列函数,就像java中随处可见的hashCode方法一样,它们的共同点在于都要尽可能避免冲突(两个不同的输入却有相同的输出),而区别在于java中的hashCode方法用于提高散列表的性能,因此主要关注于计算速度而不是安全。
第二个常见误区在于,大家都觉得MD5,SHA1之所以安全,是因为它们计算过程不可逆,举个例子:

1
MD5("hello") = 5D41402ABC4B2A76B9719D911017C592

对MD5散列函数输入字符串"hello",总是可以得到5D41402ABC4B2A76B9719D911017C592,但现在没有以后也不可能有任何方法将5D41402ABC4B2A76B9719D911017C592解密为"hello"(目前所有所谓的解密都是基于猜测)。乍一看这很神奇,在解释它之前,先来看下维基百科上对散列函数的定义:

散列函数是一种输入任意大小的数据,返回固定大小的值的函数

继续以MD5为例,对它输入任意大小的数据,它的返回值都是128位(16字节)。假如这个过程可逆,那么无损压缩就不再有极限,也就意味着给你一张软盘,你就能存储全世界!换句话说,按照上面的定义,根本不存在可逆的散列函数。看到这里你可能依然很困惑,对于任意大小的数据散列不可逆也许比较好理解,但是"hello"明明只有5个字符,为什么也不可逆呢?专业一点解释就是,在计算过程中丢掉一部分信息量即可(对于信息的量化,可以参考我这篇文章香农信息论与回答老鼠喝药问题的正确姿势),草根一点的解释是,你只要让你的函数对于不同的输入,可以得到相同的输出即可。比如f(x)=x^2就是一个不可逆的函数,因为已知f(x)=1,没办法知道x到底是正1还是负1。

2.散列冲突(Hash collision)

对于任意输入数据,经过散列函数计算后得到的散列值,又称为数据指纹(fingerprint)或摘要(digest),它就像人类的指纹一样,你不可能通过一个人的指纹而了解这个人的全部信息,但是你总是可以快速的取到一个人的指纹。并且很难重复,如果两个不同的输入数据有着同样的散列值,则称为散列冲突。正常情况下假设一个结果分布完全均匀的散列函数输出128位的散列值,那么发生冲突的概率大概在$1/2^{128}$这个数量级,这几乎等同于不可能。但人们可以根据散列函数的实现过程,设计算法来查找冲突值,也就是常说的碰撞攻击(collision attack)。加密用散列函数最大的设计难点,就在于要让别人即使知道了该函数的所有实现细节,也无法找到高效的碰撞攻击算法。

3.过时的散列函数(Deprecated hash function)

2004年山东大学的王小云教授宣布攻破MD4,MD5(Collisions for Hash Functions),2017年(也就是最近)荷兰密码学研究小组与Google宣布攻破SHA-1(Announcing the first SHA1 collisionshattered),下图解释了对这些函数查找散列冲突所需的计算量:
hash-collision-computation
可以看到使用google最近研究的算法破解SHA-1需要110块GPU一年的计算量,虽然这个数字看起来非常大,不过依然比暴力算法快了十万倍,因此Google已将SHA-1算法标记为过时(deprecated)的(顺便提一句,linus(linux,git的开发者)最近也受到这条新闻的压力,发文宣布更新git中用到的SHA-1算法)。当然上图还有一点值得注意,前文提到的MD5算法,对它进行碰撞攻击只需要消耗一台智能手机30秒的计算量。

阅读全文