martin-liu / martin-liu.github.io Goto Github PK
View Code? Open in Web Editor NEWMartin Liu's Blog
Home Page: https://mliu.me
License: MIT License
Martin Liu's Blog
Home Page: https://mliu.me
License: MIT License
bolg test by messiah thanks for martin-liu
I learned from your code in src/components/Giscus.astro
that you use:
const currentTheme = localStorage.getItem("theme");
to ensure the theme of the comment block matches the blog theme each time a post page is entered. But the localStorage
cannot be accessed from the server. Hence, this design raised an error called "localStorage is not defined" on my computer. Can you please tell me how to solve this issue?
随着ECMAScript 2015(ES6)的正式发布,以及babel这种ES6转ES5的工具的慢慢成熟, 在真实产品里使用ES6已经完全可行了。
写JS的朋友们,是时候点开es6features看一下了。
值得一提的是,ES6特性里竟然包括尾调用优化(tail call),真是要点个赞:thumbsup:。然而,这并没有什么用。
在ES6众多新特性里,Generator无疑是一个很酷的东西。cool在哪里?看code:
// 注: 以下code可以在chrome dev tool的console里直接跑
function* fib() { // 用function*来定义generator
var pre = 0, cur = 1;
for (;;) { // 无限循环
var temp = pre;
pre = cur;
cur += temp;
var reset = yield cur; // yield决定next()的返回值
if (reset){
pre = 0, cur = 1;
}
}
}
var g = fib();
console.log(g.next().value); // 1
console.log(g.next().value); // 2
console.log(g.next().value); // 3
console.log(g.next().value); // 5
console.log(g.next(true).value); // 1
在这里,我们定义了一个fibonacci数列的generator, 每次调用next()
, 会yield下一个数字; 而next
的参数则会是yield表达式的值,比如next(true)
, 则 yield cur
就返回true。
可以看到code里有一个无限循环,但并不会导致CPU hang住, 因为每一次yield
后,程序会暂停,而在next()
之后又继续运行。而这,便是generator最cool的地方:它改变了程序的控制流!
简单来说,yield停止,next继续,于是通过这个规则,我们就可以控制程序的运行顺序。于是我们可以写出这样的code:
co(function* (){
var data1 = yield ajax_call_1(); // 发出一个ajax请求
console.log(data1); // 输出response
var data2 = yield ajax_call_2(data1); // 发出另一个请求
console.log(data2); // 输出response
var data3 = yield ajax_call_3(data2); // 发出另一个请求
console.log(data3); // 输出response
});
//----------------------------------
// 以下为对比的callback写法
(function(){
ajax_call_1(function(data1){
console.log(data1);
ajax_call_2(data1, function(data2){
console.log(data2);
ajax_call_3(data2, function(data3){
console.log(data3);
...
});
...
});
});
})();
这段看似同步的代码实际上是异步执行的,但是直观简单漂亮,写起来可以谈笑风生,比callback不知道高到哪去了(关于这一点,可以看tj写的callbacks vs coroutines)。至于那个co
,就是某个奇怪的函数,在适当的时候(比如callback时)调一下next
让generator继续跑。感兴趣的话,请戳co
现在让我们总结一下: generator是一种特殊的子程序,而yield
是一种流程控制
指令,在generator里使用yield会将程序的控制权
交还给调用者(即返回调用处),而外界调用generator的next
方法会让该generator继续
执行。generator可以用来做iterator,也可以用来玩魔法(同步转异步),因为它提供了一种较为优雅的流程控制方式
不过,说是magic,但其实程序的世界,并没有无根之木、无源之水。接下来,就让我们回溯本源,探一探各种流程控制结构的来龙去脉
所谓控制流,说白了就是程序执行的顺序。
我们知道,程序执行的基本原理是:cpu从program counter(一个寄存器)拿指令的内存地址,然后去内存拿指令来执行,执行过程中会改变program counter的值(比如加1,也就是顺序执行)。如此循环往复直至结束。
程序流程的控制,实际上就是在特定的情况下,更新特定的值到program counter。而上升到编程的层次,则是提供代表特定策略的流程控制语句,用以实现各种丰富的功能。
一般而言,流程控制语句可以分为以下几类:
无条件分支
就是goto了,想去哪去哪(当然还是有限制的,比如c语言里goto就不能跳出当前function)。其缺点在于,程序可读性/可维护性容易变得极差。
条件分支
这个其实就是大家耳熟能详的各种基本流程控制语句了,比如if-else, switch, 以及for, while等loop语句
无条件终止程序
比如exit, return
运行位在不同位置
的一段指令,但完成后会继续
运行原来要运行的指令
包括子程序(subroutine)、协程(coroutine)及延续性(continuation)。(注:generator实际上是一种coroutine)
前三种比较直白简单,也比较常见,我们主要看第四种。
运行另一段指令,然后返回原指令段中继续执行。这种情况最常见的就是subroutine(比如function或者OO语言里的method)了,一般都是通过call stack
来实现,每次function call都产生一个stack frame压入栈顶,该function结束时将其出栈,这样栈顶就变回其caller的stack frame了,于是可以继续执行caller的代码。
我们看一下典型的subroutine调用:
function doOtherthing(){
// block B
{
console.log("executing...doOtherthing");
return;
}
}
function doSomething(){
// block A
{
console.log("executing...doSomething");
}
doOtherthing();
// block C
{
console.log("continue executing...doSomething");
return;
}
}
doSomething();
// executing...doSomething
// executing...doOtherthing
// continue executing...doSomething
这里没什么奇怪的东西,分成几个block只是为了方便引用,相信学过几天编程的都能理解。
现在我们从控制流的角度分析一下这个程序。block B明显与A和C不在一处,但执行顺序却是A=>B=>C。A执行后是subroutine调用,jump到B处执行;而B执行后会返回到C处执行,这也正是return语句的语义。
subroutine调用的执行顺序是固定的,这是因为return是一个关键字,提供隐式的流程控制,我们并不能像操作一个object一样来操作它——等等,如果可以呢?
如果return的语义可以被抽象出来并能在程序中操作,那么我们将可以保存任意的执行点,并且在任意时候返回该处继续执行。这句话的意思是,我们的程序将可以实现任意的控制流,而无需运行环境的支持,比如说我们可以在ES5里实现generator。
你或许已经听过这种抽象的名字:continuation
在计算机科学里,Continuation是指可以被编程语言访问的、对程序控制流程/状态的抽象表示。简单来说,就是程序运行时
的某个执行点,比如上文所说的block B里的return运行后的那个点。而return语句可以理解为隐式的调用了current continuation。
我们说current continuation
, 是指在那个点之后将要执行的代码,比如B return时,current continuation就是整个block C。
说到continuation,就不得不说CPS(continuation passing style),顾名思义,就是显式的将continuation作为参数传递,以此来进行流程控制。而我们平常写的code叫做direct style,比如上文doSomething那段code。
我们现在将之前的code改写成CPS:
function doOtherthing(k){
// block B
{
console.log("executing...doOtherthing");
k();
}
}
function doSomething(k){
// block A
{
console.log("executing...doSomething");
}
doOtherthing(function(ret){
// block C
{
console.log("continue executing...doSomething");
k();
}
});
}
doSomething(function(){});
// executing...doSomething
// executing...doOtherthing
// continue executing...doSomething
改写后执行结果是一样的。可以看到函数调用变成了callback的形式,而return都变成了k()
,这个k就是传入的continuation。
注意,这里的重点并不在于callback形式,而在于CPS变换,之前的code和这段code是等价的。在这里我们是手动做的CPS变换,但实际上,所有direct style的code都可以被自动
变换成CPS的code。(至于怎么变换,可以尝试看How to compile with continuations)
为何要强调自动的CPS变换?因为它可以用来实现一个锋利无匹的强大函数: call/cc
scheme语言里有一个著名的函数,叫做call-with-current-continuation, 一般简称为call/cc。
call/cc接受一个函数作为参数,并捕捉current continuation然后将之传递给这个函数。而continuation一被调用,call/cc立即返回,返回值即为传给continuation的参数。
比如:
(let ((a (call/cc
(lambda (k)
(begin
(display "will execute\n") ; 输出 "will execute\n"
(k 1)
(display "will not execute")))))) ; 不执行
(display a)) ; 输出1
再来段JS的版本,JS里当然是没有call/cc的了,不过这不妨碍我用JS来表达。此处假设js里有一个等价的callcc:
var a = callcc(function(k){
console.log('will execute'); // 输出 "will execute"
k(1);
console.log('will not execute'); // 不会执行
});
console.log(a); // 输出1
这段code等同于:
(function(k){
console.log('will execute'); // 输出 "will execute"
k(1);
})(function(a){
console.log(a);
});
这实质上就是自动做了CPS变换。
有了call/cc,就可以直接在程序里操作continuation了。仅从功能上来说,就可以实现各种高级控制流,而不需要编译器/解释器这个level的支持了。
接下来就让我们看看call/cc的power
Coroutine(协程)是一种类似subroutine但更灵活的控制结构,它允许有多个程序进入点,可以随意暂停
或继续
执行,主要用来做nonpreemptive multitasking(非抢占式多任务处理)。
在coroutine中,可以通过yield
语句来转移控制权,比如两个coroutine,c1和c2,在c1中调用yield to c2
(伪代码), 就会去执行c2,在c2中又调用yield to c1
,就会继续
执行c1(重新进入之前的执行点)。听起来和之前说的generator有些像?其实generator就是一种coroutine,我们之后会讲到。
Donald Knuth说:"subroutine是coroutine的特例",因为subroutine可以看作不使用yield
的coroutine。
我们说coroutine是用来做nonpreemptive multitasking(非抢占式多任务处理)的,要理解这一点,最好先理解preemptive multitasking(抢占式多任务处理)。
我们熟知的基于多线程的多任务/并发处理就是preemptive的, 程序控制权由调度器而非程序自身来决定, 实质上就是在程序外部
强行打断程序的运行,再根据某种策略(优先级,动态时间片)决定由哪个线程继续执行。
而coroutine是自已决定将控制权交给谁(yield),因而不会有race condition, 不需要考虑锁的问题,可以极大的简化并发编程。
这里要提一下为何我们熟知的是抢占式多任务处理,因为人们需要流畅的同时做多件(不相关的)事的能力,比如在上网时下载和听音乐,而抢占式的多任务处理有助于实现这一点(不会因为控制权被占用而导致其它应用hang住)。而编程时关注的是如何更高效的做好事情,并且开发者知晓全部的context,也就容易明白如何去协调控制权,所以从编程的角度,非抢占式多任务处理反而更有优势。
而从具体实现的角度来看,coroutine一般是语言级别的实现,实际上是在用户态进行上下文切换,不会陷入内核态,因而更高效。
coroutine的缺点是无法利用多核,它只能做concurrency,而不能做parallelism,因为一般它是跑在一个线程上,多个coroutine不能同时运行。但是也有改进的方案,比如go语言的goroutine, 就是work在一个线程池之上的,不过这样就需要更复杂的调度了,当然名字也华丽的变了。
以下是用callcc实现简单的协程(不过不能运行):
var queue = [];
function isEmpty(){
return queue.length == 0;
}
function enqueue(x){
queue.push(x);
}
function dequeue(){
return queue.shift();
}
function run(f){
callcc(function(k){
enqueue(k); // 将current continuation enqueue
f();
});
}
function $yield(){
callcc(function(k){
enqueue(k);
dequeue()(); // dequeue某个continuation并执行
});
}
function doSomething(str){
for(;;) {
console.log(str);
$yield(); // 放弃控制权
// point C
}
}
run(function(){
doSomething("A");
});
// point A
run(function(){
doSomething("B");
});
// point B
if(!isEmpty){
dequeue()();
}
// 理论上的输出结果为
// A
// B
// A
// B
// ..., A和B交替输出
简单描述一下程序的执行:
$yield()
$yield()
$yield()
可见通过callcc
和一个queue,我们可以轻易的实现coroutine
Generator又叫Semi-Coroutine(半协程)或Asymmetric Coroutine(不对称协程),它本质上仍是协程,和一般的协程的区别在于,generator只能把控制权交还给它的caller
, 而coroutine是可以决定把控制权交给谁。
先看一个callcc实现的generator:
function fib(){
var controlState = function($yield){
var pree = 0;
var pre = 1;
while (true){
callcc(function(resume){
controlState = resume;
$yield(pree);
});
var tmp = pree;
pree = pre;
pre = tmp + pre;
}
};
return {
next: function(){
return callcc(controlState);
}
};
}
next
调用时,进入controlState函数,$yield一旦调用,马上返回,但是controlState已经被替换成内部循环处的continuation,因而当next
再调用时会回到循环处继续执行。
其实generator可以和coroutine互相转化,因为它们本质上是一样的东西。generator加一个scheduler就可以实现coroutine(yield一个value, 然后根据value决定resume哪个generator)
来一个用ES6 generator模拟couroutine的例子(可以在chrome dev tool里运行):
function * ge1(){
for (var i = 1; ;i++){
console.log('running...generator 1, ' + i + ' times');
yield 'g2';
}
}
function * ge2(){
for (var i = 1; ;i++){
console.log('running...generator 2, ' + i + ' times');
yield 'g1';
}
}
function schedule(){
var map = {
'g1': ge1(),
'g2': ge2()
};
var current = 'g1';
for(var i = 0; i < 100; i++) {
current = map[current].next().value; // current 在'g1'和'g2'间来回变化
}
}
schedule();
关于continuation, 还有一个值得一提的是Delimited Continuation,Scala里就支持这种continuation。它是在一个限定的区域里,捕捉continuation并具体化成一个函数,以供复用。一般是通过reset+shift来表达:
(reset
(display (* 2 (shift k
(k 2)
(k 4)
(k 3)))))
用JS来翻译一下:
reset(function(){
var x = shift(function(k){
k(2);
k(4);
k(3);
});
console.log(2 * x);
});
// 4
// 8
// 6
再翻译成CPS:
(function(k){
k(2);
k(4);
k(3);
})(function(x){
console.log(2 * x);
});
现在应该很好理解了,类似于call/cc的情况,不过用reset限定了一个scope。 将shift之后reset之内的代码捕捉并封装成一个函数,然后传递给shift块里的那个函数。
这里一个要注意的点是,shift里的k
是一个函数,所以它可以多次使用;而call/cc里的k
调用一次就退出了,后边的都会ignore。
从这个角度而言,delimited continuation是纯粹的函数,而undelimited continuation不是,因而delimited continuation更直观更符合直觉,也就更适合我们用来编程
碍于能力以及篇幅,本文仅是对程序控制流的浅尝辄止。
纵观而言,各种高阶的流程控制结构,都与continuation相关,这是因为continuation是对(隐式的)控制流本身的抽象。
不过现代的高级语言里,一般不直接提供first-class的continuation, 而是提供如generator, coroutine甚至delimited continuation等的高阶控制结构,因为它们足够强大而又相对call/cc更可控更易于理解。
而它们的实现也不会是像我这里所写的那样简单,甚至也不一定是基于call/cc去实现,然而其基本原理是一致的。因此理解continuation, 理解CPS,理解call/cc,将有助于更好的玩转各种流程控制。
你好。
我在linux vps上搭建了你这个博客程序:http://mlgi.bright.biz.st/#!/ ,不过如何新建源帖??
谢谢侬。
我还记得,很久很久以前,我信誓旦旦的告诉自己,要每周写多少多少篇文章,多少多少篇技术博客。实际上在更久更久以前,我的理想是做一名文学家,当然,到了很久很久以前,已经变成了文艺型软件架构师。总之,很久很久以前,我抿起嘴,锁起眉,做出坚毅的姿态。就像现在一样。
有人说惰性是人一生最大的敌人,其实我认为时间才是,因为我可以克服一切,却克服不了时间。好吧,我始终认为,我可以克服惰性,虽然它已伴我数十年而仍无倦意。
惰性是可怖的,它抗拒改变,因而也抗拒学习、精益和成长,它会侵蚀智慧,令珠玉斑驳,令理想沉沙。而或许是普遍的不幸,在我们几经流转的人生,惰与勤辗转往复,见证了所有的过往和悲欢。
那么,这惰性从何而来,因何而去,为何而发,缘何而隐?
度娘告诉我,懒惰是一种心理上的厌倦,生气、羞怯、嫉妒、嫌恶等都会引起懒惰,使人无法按照自己的愿望进行活动。当然,惰性不只是懒惰,却是懒惰的本性,在我们的认识中往往正表现出无法如愿的坚持。它或许不可磨灭,却并非无法控制,而我们所要的,仅仅是在某些关键点上的压制,因为成功并不要求完美。
我们曾经决意为之而最终惰于持之的诸事,大抵非是没有相应的驱动,却最终心生厌倦而终告失败,内心深处或潜意识中必有所权衡和取舍。如我之写作者,若随意堆砌,亦非难事,然我本人虽不喜苛求,却总有克己的傲气,凡事惟尽力,不免增加了许多成本,也势必侵害其它习惯性的需求如娱乐,久之,自然会有所反弹。
万物皆趋向平衡,当外力打破一种平衡,最终会仍回归于该平衡,或者形成新的平衡。
克服惰性亦是如此,如果不能形成新的稳固的平衡,以满足生理的需求,满足心理的愉悦或自我实现,则仍会回归原本的非所愿的平衡。这正是种种失败的坚持失败之所在。
在我们的生活中,有无数这样失败的例子,甚至每天都在发生,如各种学习计划,还有某些人的减肥。而与此同时,我们成功的改变也不在少数,可能是戒烟、学英语甚或每天刷牙,其共同的抽象是认识的稳固、身体的习惯、心理的舒适。
然而身心的习惯与满足并非轻易可达,尤其当我们意欲推行的活动需要消耗较多的精力与时间,必将影响到已有的愉悦与满足,并竞争有限的驱动力。这种情况下,我们考虑生理的需求与负荷不会有显著的上升空间,只有着力于提升心理的认知与内在驱动。
规划,系统的规划,明确目标与期望,明确达成目标的预估投入,并基于清晰的理性认知与思辨去调整既定的计划与行为,找到新的平衡点。惟其如此,方不需勉力长久的推动,也不会于力尽时有所往复。
[2018-09-27] 此文已经outdated,我使用angular 6重写了这个blog system. 现在只需fork并简单操作即可使用。see instructions.
不过原理仍是类似的,此文可作为参考.
最近写了一个简单的博客并放在github上,在此详述一下细节,以为分享。
方法并不高端,但是:
不需要数据库,不需要服务器,不需要域名
,因为github都帮我们做了,壮哉我大github!好了,废话稍止,进入正文。
写前端代码
并host在github pages, 利用github issues做为后台, 通过github API完成前后端交互
- Github 提供的托管
静态网页
的服务,基本使用方法是建立一个名为YOUR_USER_NAME.github.io
的repo, 并把代码push到master
branch。- 注意其只支持
静态内容
。- 另外,如果你有自己的域名,也可以将域名指向github pages
每个github repo自带的tracking系统,支持markdown, 代码高亮,图片,表格,emoji表情
Github提供的API, 可以拿到你的issues内容,可以render markdown... 更多请看文档
事实上,直接使用issues作为博客也是可行的,从这个角度,就是把github issues当成博客平台。
这个方案的缺陷是:
而使用github API来构建no backend app, 即可以合理利用github提供的强大功能,又能随心所欲的定义自己的网站,还能集成任意的第三方服务(评论、分享等),十分潇洒
本博客基于m-angular-boilerplate开发,这是我写的一个前端快速开发框架
,主要技术为angularJS + bootstrap + grunt + coffeeScript
,有兴趣的朋友可以看看。 😄
这个框架的scope不同于博客系统,在此先不多说。本文会主讲博客涉及到的内容。
首先要在Github上建立repo,名字为YOUR_USER_NAME.github.io
, 比如我的martin-liu.github.io
。
拉到本地后开始coding。 以下为coffee编译出来的js代码,主要使用angularJS,如用其它框架实现,按同样的原理来就是
注册routing。就是把url和页面逻辑对应,比如http://martin-liu.github.io/#!/
这个url就找partials/home.html
这个html,并执行HomeCtrl
这个function。如果找不到,就去404页面
angular.forEach(Config.routes, function(route) {
if (route.params && !route.params.controller) {
route.params.controller = 'BaseCtrl';
}
$routeProvider.when(route.url, route.params);
});
$routeProvider.otherwise({
templateUrl: 'partials/404.html'
});
Config.routes内容为:
[
{
"url": "/",
"params": {
"name": "home",
"label": "Home",
"templateUrl": "partials/home.html",
"controller": "HomeCtrl"
}
},
{
"url": "/article/:id",
"params": {
"name": "article",
"hide": true,
"templateUrl": "partials/article.html",
"controller": "ArticleCtrl"
}
},
{
"url": "/about",
"params": {
"name": "about",
"label": "About",
"templateUrl": "partials/about.html"
}
}
]
Home页面的实现
code如下,BlogRemoteService.getBlogs()
就是ajax call刚刚那个url,拿issues数据
BlogRemoteService.getBlogs().then((function(_this) {
return function(blogs) {
return _this.data.blogs = _this.processBlogs(blogs);
};
})(this));
processBlogs = function(blogs) {
return _.map(blogs, BlogService.decorateBlog);
};
BlogService.decorateBlog就是下面的取summary
可以看到,文章内容有一段注释,里面是json代码。注释不会显示,但可被获取,做为metadata
<!--
{
"summary":"渺小如我们,是风吹动水面,是蝴蝶一次振翅。在正确的位置,也能掀起远方的风暴;找到那个支点,也能撬动地球。"
}
-->
BlogService.decorateBlog的内容如下,用来解析注释内容,赋值给blog.meta
decorateBlog: function(blog) {
var e, meta, metaStr;
if (!blog.body) {
return blog;
}
metaStr = blog.body.substring(0, blog.body.indexOf('-->'));
metaStr = metaStr.replace(/\n|\r|<!-{2,}/gm, ' ');
try {
meta = JSON.parse(metaStr);
} catch (_error) {
e = _error;
console.log(e);
}
blog.meta = meta;
if (blog.meta.summary) {
BlogRemoteService.renderMarkdown(blog.meta.summary).then(function(data) {
return blog.meta.summary = data;
});
}
return blog;
}
<m-loading ng-if="!vm.data.blogs"></m-loading>
<div ng-if="vm.data.blogs" ng-repeat="blog in vm.data.blogs">
<div style="cursor:pointer"
ng-click="Util.redirect('/article/' + blog.number)">
<h3 ng-bind="blog.title"></h3>
<p class="summary" ng-bind-html="blog.meta.summary"></p>
<span ng-bind="blog.created_at | date:'yyyy-MM-dd'"</span>>
</div>
<hr/>
</div>
文章页面的实现
javascript BlogRemoteService.getBlog(id).then((function(_this) { return function(blog) { if (blog.body) { _this.data.blog = BlogService.decorateBlog(blog); BlogRemoteService.renderMarkdown(blog.body).then(function(ret) { return _this.data.content = ret; }); return $rootScope.blog = _this.data.blog; } }; })(this));
post
blog.content到https://api.github.com/markdown<m-loading ng-if="!vm.data.content"></m-loading>
<div ng-if="vm.data.content">
<h2 class="align-center" ng-bind="vm.data.blog.title"></h2>
<p ng-bind="vm.data.blog.created_at | date:'yyyy-MM-dd hh:mm:ss'" class="created-at"></p>
<br/>
<div ng-bind-html="vm.data.content"></div>
</div>
<br/>
<br/>
<hr/>
<p>欢迎扫码订阅公众号:</p>
<img width="120" src="/image/qrcode_wechat.jpg"/>
<div ng-if="vm.data.blog.number"
duoshuo data-thread-key="{{vm.data.blog.number}}"></div>
关于css
css主要是用的bootstrap, 但是代码高亮是copy from github, 代码在这里
使用多说评论,百度统计,jiathis社会化分享
需要到各自的网站上注册,得到相应代码
以下为异步加载多说和百度统计的代码
function addScript(src){
var el = document.createElement("script");
el.src = src;
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(el, s);
}
// duoshuo
var duoshuoQuery = {
short_name: 'martin-liu'
}
// baidu statistics
var _hmt = _hmt || [];
_hmt.push(['_setAutoPageview', false]);
var scriptSrcs = [
'http://static.duoshuo.com/embed.unstable.js', // duoshuo
'//hm.baidu.com/hm.js?a67e974dea316e70836c07c3e3576a29' // baidu statistics
]
for(var i = 0; i < scriptSrcs.length; i++){
addScript(scriptSrcs[i]);
}
另外,对于多说使用angular-duoshuo来支持angularJS
<div ng-if="vm.data.blog.number"
duoshuo data-thread-key="{{vm.data.blog.number}}"></div>
百度统计, url变化时触发
$rootScope.$on('$routeChangeSuccess', function($event, current) {
if (_hmt) {
return _hmt.push(['_trackPageview', $location.url()]);
}
});
fork me on github
见https://github.com/blog/273-github-ribbons
使用locache做本地cache, 减少request数量,提高用户体验。我设置为5分钟失效
this.getWithCache = function(key, isSession, getFunc, timeout) {
var cache, data, defer, promise;
cache = Cache;
if (isSession) {
cache = Cache.session;
}
defer = $q.defer();
data = cache.get(key);
if (data) {
defer.resolve(data);
return defer.promise;
} else {
promise = getFunc();
promise.then(function(data) {
return cache.set(key, data, timeout);
});
return promise;
}
};
push到github,等几分钟,一个新鲜的热乎乎的博客就出现了!
以下是我的部署script,因为有build过程(concat, uglify之类)
#!/bin/bash
grunt build
( cd dist
git init
git add .
git commit -m "Deployed to Github Pages"
git push --force --quiet "https://github.com/martin-liu/martin-liu.github.io.git" master
)
还有一些问题没有解决,如
可以看到,这是个非常简单的blog,并不完善,但是workable,可以在此基础上迭代开发。这一点相当重要,因为
Done is better than perfect.(完成更胜完美)
-- facebook标语
动笔之前,稍一回顾,发现上一篇文字竟是13年11月所作。
不知觉间,又有一年未曾动笔,不由感叹人生无常,惰性使然
。
之前的文章且不去迁移,唯有两年前的一篇《论惰性》搬迁于此。此文如今看来颇显空泛,却也不失为一份自嘲与警醒。
构建这个博客的目的,主要是打算尝试一些技术类的写作,在一个严肃的地方,写一些严肃的文字。
寻求自我的表达,也做一些小小的分享,或许有朋友能看到,彼此交流,成长路上,我道不孤。
不过以我的德性 😏 ,应该会变成一个大杂烩 😆
本博客基于m-angular-boilerplate开发,host于github pages, 后台直接使用github issues, 十分偷懒耍滑,简单可依赖。。。具体细节我会开一篇文章详述。
那么开始吧,写博客只是小小的一步,但这一次,不能在开始时停下。
生活巨大的惯性,曾让我迷失。活在自己的舒适区,虽自觉努力,却跳不出圈子。悄忽时间消逝,却难以自知,在惯性中随浮随沉。未曾想,只有死鱼才随波逐流。
这个世界如此奇妙,有雄奇险峻的风光,有平淡悠远的画卷,有恣意狂放的少年,有温婉细腻的妹纸,当然也有恣意狂放的妹纸,温婉细腻的少年。
这个世界又是如此残酷,美丽背后,常有忧伤,光明之下,岂无阴影。太多的美好,都对应难解的苦痛;太多的收获,都来自不渝的付出。但苦痛却不一定带来美好,付出也不一定有所收获。
因为在这个宏大的程序中,我们只是一个小小的变量,等待着调用,产生未知的副作用。
但是,这未知也是无限的可能。渺小如我们,是风吹动水面,是蝴蝶一次振翅。在正确的位置,也能掀起远方的风暴;找到那个支点,也能撬动地球。
而如果我们只是一个静止的变量,这一切都不会发生,也许下一轮GC,就不再有一丝痕迹。
所以,开始吧。
让我们从这段话开始:
也许每个人出生的时候都以为这世界是为他一个人而存在的, 当他发现自己错的时候, 他便开始长大.
—— 今何在 《悟空传》
可惜,长大并不能解决根本问题。它破除了一个典型的傲慢的偏见,却无法避免更多的傲慢和偏见。
如果你常与人沟通——在没有学会只讨论天气
之前——你会发现,分歧无处不在。即便在“人以群分”的隐式筛选之后,分歧仍不可避免,更不用说那个与你有半个物种之差的TA了。
我们总是从一个往往是错误的『确定性』开始,停留,或者跳转到另一个往往仍是错误的确定性,循环往复。
在大多数时刻,在被压倒性的证据推翻之前,我们对自已的认知总是坚信不移的,因而在大多数时刻,我们是傲慢的,这是诸多分歧与争端的根源之一。
当然,分歧之外,我们也有很多的『共同点』。比如:
术语 | 解释 | 举例 |
---|---|---|
验证性偏见 | 选择性地回忆、搜集有利细节,忽略不利或矛盾的资讯,来支持自己已有的想法。 | 比如夫妻争吵时 |
从众效应 | 指人们受到多数人一致性**或行动的影响,而跟从大众的**或行为,常被称为“羊群效应”。 | 比如吃饭时,倾向于去人多的饭馆,即便要排队 |
巴纳姆效应 | 人们会对于他们认为是为自己量身定做的一些人格描述给予高度准确的评价,而这些描述往往十分模糊及普遍,以致能够放诸四海皆准 | 比如占卜,人格测试,还有星座 |
... | ... | ... |
这些偏见在日常生活中四处可见,它们并非一定带来苦果,却是智慧
的绊脚石
当我们讨论人性的弱点,傲慢与偏见是不可回避的话题,它们如此平常而神秘,无孔不入而又难以自觉。它们虚耗生命,它们制造争端,它们引领我们在错误的路上愈行愈远。
要是他没有触犯我的骄傲,我也很容易原谅他的骄傲
——《傲慢与偏见》
让我们来剖析傲慢与偏见的根源
首先,关于人类。
人是没有羽毛两脚直立的动物
—— 据说是柏拉图说的
据说是柏拉图说的话朴素而不动人,它简单的揭示了一个典型的“傲慢”:我们总是高估人类和动物的差异。
和动物一样,我们通过感官感受世界,通过大脑处理信息,通过身体做出行为。那么,请先暂停一下无谓的高傲,让我们来看看,人类这种动物,具体是如何工作的。
在这里,我会简单的将人类这个复杂系统的运行模式,分为三个过程,并逐一讨论各过程中可能存在的问题,这些问题导致我们选择并坚持我们的傲慢以及偏见。
感知
的过程简化为**“输入过程”。模式匹配
式的复杂大脑活动,产生或获取各种策略,以驱动行为。这个过程包括但不限于思维过程。需要说明的是,这三个过程形成的循环无时无刻不在发生。很多时候,同时存在多个独立的循环,比如你可以看似互不干扰的在厕所看书和听音乐
输入过程的问题
人和人的感官是有差异的,视力有强弱,听力有强弱,所处的位置、角度也有差异;而知觉又依赖于经验和判断,不同的个体差异巨大。这些差异不可避免的导致输入的差异化和失真化。
事实上,我们看似身体健全,但在认知事物时,仍是盲人摸象。比如那只羊,可能是一条批着羊皮的狼;比如那条咸鱼,可能是一个没有梦想的人(星爷表示躺枪 🔫)
输入过程的问题远不只这些,事实上我们有大量的各类错觉,比如电影其实是每秒24格的幻灯片。关于视觉错觉,可以看一看逃出你的肖申克(二):仁者见仁智者见智?从视觉错觉到偏见
这里的一个关键点在于,我们从感官接收到的信息是片面的、不足够的、不准确的,但是我们的大脑不会怀疑
,并试图迅速给出一个尽量**“合理”**的感知结果。这是因为大脑服务于生存,而不是真理
,它需要快速的响应,哪怕是错误的响应。
处理过程的问题
脑部的构造极其复杂。我们知道,复杂性往往导致可靠性降低
,我们的大脑并不如我们想像的可靠。
简单说一下复杂性。
脑部神经管分化为五部分:端脑、间脑、中脑、后脑、延髓。我们一般讲大脑,说的是端脑。人类端脑属于脑和整个神经系统演化史上
最为晚出现、功能上最为高级
的一部分。
然后
端脑
分为两侧大脑半球、胼胝体与基底核。
两侧大脑半球就是我们常说的左右脑了,而两个半球上那些吓人的皱褶则是大脑皮层。大脑皮层又分为不同的叶
,处理不同的细分功能,其中最“高级”的当属额叶
根据进化史,大脑皮层分为
新皮层
(Neocortex)和古皮层新皮层与一些高等功能如知觉,运动指令(motor commands)的产生,空间推理,
意识
及人类语言有关系额叶,高级认知功能,比如学习、语言、决策、抽象思维、情绪等,自主运动的控制
我们可以看到,大脑极端复杂,而且它不是一个设计良好的一致性系统,它是在老的系统上修修补补,慢慢演化。比如新皮层就是在漫长进化中,在那些老的模块之上构建出来的。从这一点上,再考虑到思维过程的复杂性,就容易理解为什么我们的主意识与潜意识、本能并不能完美的协调了。
比如说左脑处理逻辑,右脑处理情感,这两者就常常合作不愉快。你做了一个梦,却说不出来;同样的还有,你突然有一个想法,当你试图说出来时,你脑子里一片空白。因为语言功能主要在左脑控制,而做梦/异步的想法是在右脑,当左脑占用输出时,并不能很好的从右脑获取信息。
这是由于我们不同脑区可以同时工作,但却不能同时输出,于是不可避免的导致了争用
。《程序员的思维修炼》中将大脑比作双CPU单总线
的设计,不无道理。
另外一个方面,大脑会同时进行多个“输入-处理-输出”过程,不幸的是,它们会相互干扰,你意识不到,只不过是被你的“傲慢”所蒙蔽。比如在口算一道数学题时,手持质量较重的物品,人们更容易给出较高的估算值;比如喝了一杯甜饮的人比喝凉白开的人更愿意原谅别人;而更常见的,你的任何情绪都会影响你的行为。
这就像一个低劣的多线程程序,饱受共享变量之苦。于是,很多时候,我们的认知过程受到其它的认知过程的影响,最终偏离了真实情况,出现可捉摸的规律性的偏误,这将影响到我们的智慧,也给了别人可趁之机。
还有一个要命的地方:我们的大脑是有缓存的。缓存的命中率很高,更新策略却极为拙劣。
很多时候,我们并不会深入的思考,而是在看到事物后,根据以往的经验,瞬间给出答案,大脑并不保证准确度,也不会标注说,这是一个未经充分验证的判断。
我们生活中的各种脸谱化思维,标签化思维都是如此。比如各种肤色、种族、性别歧视,还有各种惯性思维,都是直接从缓存中选取策略,而不考虑现实的情况,不经过主意识的思考。
这同样是因为我们对快速响应
的需求,我们不需要正确
,我们需要生存
、安全
等等基本的保障。
关于大脑的“缓存机制”,感兴趣的同学可以看看杏仁核
杏仁核是边缘系统的皮质下中枢,有调节内脏活动和
产生情绪
的功能。引发应急反应
,让动物能够挺身而战
或是逃离危险
。
输出过程的问题
输出过程的问题在于,我们高估了对身体的控制能力。事实上太多时候我们都是想的太美,身体做不到。这个方面不是本文的重点,在这里就不展开了。
由于在进化史上的漫长时间里,人类基本都处于一个危险的、恶劣的
环境,我们对于生存
的需求远远大于其它。文明的历史如此短暂,几千年的时间在进化史上不过是一瞬间,不足以颠覆以往的架构。于是,我们的身体、大脑构造和工作模式都是服务于生存
,而不是其它
这要求我们快速响应
外界的变化,随时准备战斗或者逃跑
。即便如今我们大多数时候并不需要如此,这些古老的习惯仍在不知不觉中影响着我们,导致各种负面的影响
我们虽然有了更高级的大脑皮层,有清晰的主意识,但它太过年幼,并不能主宰一切,在我们的身体里,时刻有一个更原始也更强大的声音,驱动着我们产生奇怪的想法,做一些莫名奇妙的事情。
而生活中影响深远的傲慢与偏见,都是在这种“不兼容”的状态下产生,且生生不息
我用了很大的篇幅,试图说明在现代文明环境
下,人类是一个多么糟糕的过时的
老系统。在一个崭新的时代,我们仍保留着大量原始时代的架构,新与旧的不兼容状态下,出现傲慢与偏见这类问题不可避免。
当我们使用大脑的高级功能去思考、探索、创造时,那些低级的功能仍在无时无刻给予错误的判断,不断提醒你随时去战斗或逃跑
,并占用我们大量的脑容量。
但是,作为渺小的人类,我们尚不足以触及“神的领域”,并不能随心所欲的调整大脑结构。
基于这样的事实,我们应该明白,在相当长的远远大于我们寿命的时间内,傲慢与偏见,及由此产生的争端,都是无解的。
我们只能尽量清醒的认识到,我们所有的认知,无论你多么确信,都可能是偏误的,都可能是原始大脑的误判。
认识到这一点并不是多么恐怖的事情,我们的高级
的额叶皮层,能够处理好未知和不确定的事务,前提是它能意识到,并接管当前的处理过程。
当你看到一条井绳,你的原始大脑疯狂提醒你,“那是一条蛇,快战斗或者逃跑”,你应该先听从,然后适度的怀疑。
当别人指出你的问题,或者因分歧而争辩,你的原始大脑疯狂提醒你,“受到威胁,快战斗或者逃跑”,你一定要hold住,只要你意识到这可能是错误的讯息,你的额页皮层就能去控制住场面,令你表现出高等动物
的智慧
请问如何修改About页面的内容,以及修改locale(将网站的语言自定义成中文)语言包?是否能直接在master分支中直接修改相关文件以达成目的?谢谢!
this is a test
function(){
alert('a');
}
class Test{
public static void main(String[] args){
System.out.println("test");
}
}
test
测试下
最近在学习Scheme,来自MIT的一个著名的Lisp方言。它诞生于1975年,和c语言(1972)算是同龄,对比现在当道的90后语言(java, javascript, php, python, ruby... ),在这日新月异的程序界,算得上是“老掉牙”了。
那么问题来了,有这工夫,为啥不学学新潮的Go, Rust,偏偏学一个这么古老的语言?
答案很简单: Scheme简洁优雅强大,直指编程本质。学之能去芜存精,助我们提升编程水平。
关于Scheme的书籍最有名的当属MIT的《计算机程序的构造和解释》(SICP,或“魔法书”),到08年为止,曾三十年为作为MIT计算机科学的入门课程。
不过SICP虽“说”是入门
,其实又厚又深,所以我选择了另一本经典书籍作为入门:The Little Schemer。这本书仅仅200页,且通篇都由question&answer
的对话构成,由浅入深,深入浅出,从lambda以及几个built-in函数出发,一路推导出各种运算方法、数据结构,并深入到continuation,停机问题,Y-combinator, 甚至最后直接写了个简单的解释器出来,令人惊叹。
事实上,本文可算是The Little Schemer
的笔记和总结。
我使用的scheme实现是Guile, 然后在emacs中使用了王垠的scheme配置, 配置文件在这里
Scheme的语法就是Lisp语法,括号套括号...很多人不爽lisp满屏的括号,觉得可读性差。不过,可读性应该是用缩进来保证的,任何语言的code,不用换行和缩进,都不能谈可读性。
事实上,由于Lisp的程序和数据是同一种表达方式(列表)——本质上就是AST的前缀表示——这给了lisp无与伦比的表达力和扩展性。
下面简单说一下其语法元素:
表达式只有两种, atom
和list
, atom是number或者symbol(类似于string), list就是那坨括号
3 ; 数字3
1.14 ; 数字1.14
#t ; boolean True
#f ; boolean False
abc ; simbol abc
() ; empty list
(abc xyz) ; list
(+ 1 (- 3 2)) ; nested list
(lambda (x)
(+ x 1))
其实就是匿名函数,等同于javascript里的:
function(x){
return x + 1;
}
注意这里不是在说Lisp的7公理,也不是列出所有scheme的built-in函数,而是在The Little Schemer
中必需的函数
quote
(quote x)
返回x, 等价的写法是'x
, '
是一个语法糖。quote的作用是区分代码和数据
,比如(+ 1 2)
表示代码,执行结果为3;而'(+ 1 2)
表示数据,执行结果为(+ 1 2)
这个list
cons, 用来构造list
(cons 'a 'b)
返回(a . b)
, 这个叫做dotted pair。 dotted pair是list的基本组成元素,(cons 'a '())
返回的是(a . ())
, 我们将这种结构叫做list, 并简写
为(a)
;同理,(cons 'a '(b))
返回(a . (b . ()))
, 我们简写为(a b)
car, 返回list的第一个元素
(car '(a b)
返回a
cdr, 返回除第一个元素的所有元素组成的表
(cdr '(a b c))
返回(b c)
cond, and, or, not, 条件语句
(cond
(condition1 return1)
(condition2 return2)
...
else default)
null?, 判断是否为空list
(null? '())
返回#t
, (null? OTHERS)
返回#f
eq?, 判断是否相等
atom?, 判断是否为atom, 不是list的就是atom
zero?, 判断数字是否为0
add1, 数字加1
sub1, 数字减1
number?, 判断是否为数字
好了,没有了,就这些,让我们开始奇妙的编程之旅吧!
等等 +、-、*、/、>、<
都没有, for loop, while loop也没有,这能编程?:open_mouth:
别急,让我们一点点来,让我们尝试去构造它们,看看那些熟悉的编程元素,是否真的必不可少。在这个过程里,也让我们去思考也去寻找,有关编程的一些更本质的东西。
没有循环,那我们如何去处理重复操作?答案是递归。比如阶乘:
(define fact
(lambda (x)
(cond
((eq? x 1) 1)
(else (* x (fact (- x 1)))))))
递归强大而易读,有简洁的数学美。我们只需要:
终止条件
,以便递归返回,比如(eq? x 1)
则返回1
朝终止条件靠近
(这样才能最终结束),比如(- x 1)
假设
这个函数已经是work的,并以此填充表达式可以看到,递归和数学归纳法十分类似:先考虑x = 1
的情况,再假设x = k - 1
时是work的,然后考虑x = k
时的情况。这个过程充分展现了强大的数学美。
然而,我们常常听到一个说法:避免递归,多用循环(迭代)。这在一般情况下(比如c、java程序里)是正确的,因为递归会不断进行函数调用,系统需要保存调用信息和返回地址到调用栈,这样不仅性能慢,而且容易栈溢出。
但是在函数式编程语言里,一般都支持尾递归优化(javascript的话,ES6将支持尾递归优化, excited!),可以很好的解决这个问题。不过在这里我们主要考虑编程的**,优化之类的问题先不多谈。
另外,如果细心的话,你可能会发现,刚才的阶乘算法里的define
, 并不在之前提到的built-in的list里。实际上,define也可以只是一个语法糖。难道给函数命名也不是必需的?关于这一点,我们会在之后的Y-combinator
一节得到答案。而现在,让我们先认为define存在并且work。
让我们来实现那些基本的运算。注意,我们暂时只考虑自然数
的情况。
我们可以使用add1
, sub1
以及zero?
来实现加法。对于n + m
, 当m
为0
时,返回n
,这是设置一个停止条件;然后让m
往0
逼近,递归调用加法函数即可。代码如下:
(define +
(lambda (n m)
(cond
((zero? m) n)
(else (add1 (+ n (sub1 m)))))))
(define -
(lambda (n m)
(cond
((zero? m) n)
(else (sub1 (- n (sub1 m)))))))
(define *
(lambda (n m)
(cond
((zero? m) 0)
(else (+ n (* n (sub1 m)))))))
, <, 还有数字的
=
, 因为eq?
是一个更大的scope
;; define >
(define >
(lambda (n m)
(cond
((zero? n) #f)
((zero? m) #t)
(else (> (sub1 n) (sub1 m))))))
;; define <
(define <
(lambda (n m)
(cond
((zero? m) #f)
((zero? n) #t)
(else (< (sub1 n) (sub1 m))))))
;; define =
(define =
(lambda (n m)
(cond
((> n m) #f)
((< n m) #f)
(else #t))))
(define /
(lambda (n m)
(cond
((< n m) 0)
(else (add1 (/ (- n m) m))))))
(define %
(lambda (n m)
(cond
((< n m) n)
((= n m) 0)
(else
(% (- n m) m)))))
漂亮!可以看到,通过lambda和递归,我们只使用zero?
, add1
, sub1
,便实现了加减乘除,求余,还有大于、小于、相等的判定功能。:smile:
值得一题的是,The Little Schemer
里还略微探讨了一下类似邱奇数的问题,当然不是真的邱奇数,而是类似邱奇数的简化版,且同样只考虑自然数。
简单的说,就是用()
表示0,(())
表示1,(()())
表示2,循环往复。
;; use '() to represent 0, '(()) represent 1
(define sero?
(lambda (n)
(null? n)))
(define edd1
(lambda (n)
(cons '() n)))
(define zub1
(lambda (n)
(cdr n)))
以上是新版本的zero?
, add1
和sub1
。有了这几个,根据上一节的code,我们就可以抛开数字
,玩转各种运算了! 😏
Scheme里只有链表,不过,其它数据结构都可以由链表来模拟或生成,比如array, set, map(table)
当数组用:
;; (pick n lat), get the element of lat in position n
(define pick
(lambda (n lat)
(cond
((zero? (sub1 n)) (car lat))
(else (pick (sub1 n) (cdr lat))))))
Set:
;; makeset, make a lat to a set
(define makeset
(lambda (lat)
(cond
((null? lat) '())
((member? (car lat) (cdr lat))
(makeset (cdr lat)))
(else (cons (car lat) (makeset (cdr lat)))))))
这里member?
的代码就不贴出了
关于Table(map), 我们一般会构造Entry
这样的结构,在scheme里可以表示为(keys values)
这样的形式,而table(map)
就是entry
的list。
至于一些相应的操作方法,由于本文并非流水帐(:sweat:), 此处就不贴出了
跟着The Little Schemer
的步伐,我们会一路build出越来越复杂的方法,也会开始学会abstract
, 通过复用来简化code。不过,这些其实也并没有太出彩的地方。
但到了第8章,我们将会碰到一个神奇的东西,continuation。
讲continuation之前,我先简单说一下continuation-passing style (CPS)。
在JavaScript程序里, 我们经常会用到回调函数
,比如ajax call:
$.getJSON("ajax/test.json", function(data) {
console.log(data);
});
getJSON
异步拿到数据后,便会执行pass进去的function,而这个funcion就是continuation了。
有朋友可能会觉得,哎哟,不就是回调嘛,这有什么了不起的?
当然不只是回调。所谓continuation,其实是对程序的控制流的抽象表示。上面的例子里,getJSON
执行完后,控制流转到传入的匿名函数,在这里,实际上控制流是由我们所控制。
如果使用这种style,我们甚至不再需要return
。
比如将
function f(a){
return a;
}
改成:
function f(a, continuation) {
continuation(a);
}
事实上很多编译器都会做这种事情。
而更重要的是,使用Continuation我们可以实现更复杂的控制流,比如Exception(try-catch block), coroutine(协程), generator
对于编译器来说,可以容易的把这些复杂的结构脱糖处理,变成简单的CPS,这将极大的简化编译器的实现。
关于continuation的话题可以非常大,这里篇幅有限,暂不深入讨论。我将单独开一篇博文详谈。
回到The Little Schemer
, 我不得不贴一下里面讲解continuation的code, 非常之赞,因为真正的在解决问题,而不是如我这样空泛的举例:
(define multirember&co
;; param: atom, list, collector
(lambda (a l col)
(cond
((null? l)
(col '() '()))
((equal? a (car l))
(multirember&co a (cdr l)
;; 每次(cdr l), 都包一次col, seen经过(cons (car l)),收集了所有等于a的atom
(lambda (newlat seen)
(col newlat
(cons (car l) seen)))))
(else
(multirember&co a (cdr l)
(lambda (newlat seen)
(col (cons (car l) newlat) seen)))))))
这里很重要的一点是,我们现在并没有提供局部变量
的功能,但是通过continuation来巧妙的做collect工作。从这个角度来讲,局部变量也可以是语法糖!
为了便于不熟悉scheme的人理解,我用javascript翻译了一下,可在chrome develop tool或者firebug里have a try。注意,里面的局部变量仅仅是为了写的方便,理解这个意思就行。
var multirember = function(a, arr, collector) {
var tmp;
if (arr.length === 0) {
return collector([], []);
} else {
tmp = arr.shift();
if (a === tmp) {
return multirember(a, arr, function(notseen, seen) {
seen = [a].concat(seen);
return collector(notseen, seen);
});
} else {
return multirember(a, arr, function(notseen, seen) {
notseen = [tmp].concat(notseen);
return collector(notseen, seen);
});
}
}
};
multirember(1, [1, 2, 3, 1, 4, 5, 1, 6], function(notseen, seen) {
console.log("notseen is: " + notseen);
return console.log("seen is: " + seen);
});
// result:
// notseen is: 2,3,4,5,6
// seen is: 1,1,1
经过continuation的一知半解和意犹未尽,让我们缓一缓,来看看停机问题。所谓停机问题,就是判断任意一个程序是否会在有限的时间之内结束运行的问题。
首先,我们写一个无限递归永不停机的函数:
(define eternity
(lambda (x)
(eternity x)))
然后,我们假设存在一个函数will-stop?
能判断一个函数是否会停机。然后我们再构建一个绝妙的矛盾的函数:
(define last-try
(lambda (x)
(and (will-stop? last-try)
(eternity x))))
如果last-try
会停机,即(will-stop? last-try)
返回#t,将执行eternity
,于是无限递归永不停机;如果last-try
不会停机,即(will-stop? last-try)
返回#f,last-try停机并返回#f。
无论哪种情况,都是矛盾的,于是证明will-stop?
不存在,停机问题得解。
这样看起来还是蛮简单的嘛,不过,没看过我肯定想不出来。。。啥也不说了,拜谢图灵!
在The Little Schemer
第九章里,还有一个大名鼎鼎的东西,Y combinator。我也曾看过一些关于它的文章,但大多都深奥晦涩,难以捉摸。而在The Little Schemer
里,完全用code的方式来一步步引导出来,不过,为了接受度,且让我使用js来描述。
还记得我们之前提到define
其实不是必需的么?想一想,如果我们只有lambda,也就是只有匿名函数,可以实现递归么?
让我们试一试。
从一个简单的递归开始:
var f = function(n){
if (n == 1){
return 1;
} else {
return n * f(n-1);
}
}
由于只有匿名函数,所以f(n-1)
是不存在的,那么这个写法就不正确了。
不过,如果我们能给出真正的递归函数
f,那我们就可以写出以下的函数:
var F = function(f){
return function(n){
if (n == 1){
return 1;
} else {
return n * f(n-1);
}
}
}
这个函数是可以给出的,因为f(n-1)
里的f
是外界传进来的,所以它是有意义的。而var F
, 我们可以当做语法糖,因为函数定义里没有引用到它。不过,给出了F
也不能解决问题,因为我们不知道如何给出f
。
但是没关系,让我们一点点尝试,或许能慢慢逼近正确答案。
让我们看看F(f)
的结果是什么?
// F(f)的展开
function(n){
if (n == 1){
return 1;
} else {
return n * f(n-1);
}
}
这个f
是我们传进去的真正的递归函数,而如果f是真正的递归函数,那么很明显,F(f)
就是f
本身。
也就是说,F(f) = f
。很好,虽然我们还不能给出f
,但我们能给出F
,并找到了F
和f
的关系。让我们继续尝试,看能否通过F
来最终找到f
。
我们现在知道,F(f)
就等于我们要找的递归函数。而F和f的定义看起来是很类似的,那我们来试试F(F)
。F(F)
展开的结果是:
// F(F)的展开
function(n){
if (n == 1){
return 1;
} else {
return n * F(n-1);
}
}
你应该能注意到,F(n-1)
不对,因为F
接受一个函数作为参数。而如果从理论上递归函数的定义来看,应该是F(F)(n-1)
才对。可以做到么?可以!我们再写一个函数G:
var G = function(f){
return function(n){
if (n == 1){
return 1;
} else {
return n * f(f)(n-1); // 注意是f(f)
}
}
}
这里G
和F
唯一的区别就是里面递归调用的是f(f)
而不是f
。现在G(G)
的展开里会是这样:
// G(G)的展开
function(n){
if (n == 1){
return 1;
} else {
return n * G(G)(n-1);
}
}
这不就是递归函数的定义么?看起来似乎没什么问题,G
的定义里并没有引用G
,那么理论上说G(G)
就是我们的递归函数了。
让我们来测试一下,G(G)(5); // return 120
,漂亮!我们成功了!原来只需要匿名函数,我们就可以实现递归!:beers:
不过,稍等一下,还差一点点,这还不是Y-combinator,因为还不够美。让我们更进一步,把f(f)
再抽象一下:
var G = function(f){
return (function(f) {
return function(n) {
if (n === 1) {
return 1;
} else {
return n * f(n - 1);
}
};
})(f(f));
}
不难看出,这个定义等价于之前G
的定义。
而根据之前的F
的定义,这实际上就是:
var G = function(f){
return F(f(f));
}
由于G(G)
是我们的递归函数,于是我们可以定义函数Y,使得Y(F) == G(G)
:
var Y = function(F){
var G = function(f){
return F(f(f));
}
return G(G);
}
这个Y
就是我们的Y-combinator了,只要把一个形似F
的函数丢给Y
,就可以获得一个完美的递归函数了!
我们已经测试过了G(G)
, 让我们再试试Y(F)
。咦,不对啊,Uncaught RangeError: Maximum call stack size exceeded
,难道我们推理有误?
好吧,这是最后一个坑了。问题出在F(f(f))
,实际上我们需要在else
分支执行f(f)(n-1)
,而由于JS是没有Lazy Evaluation的,于是F(f(f))
里的f(f)
会直接执行。让我们来fix这个bug:
var Y = function(F){
var G = function(f){
return F(function(x){
return f(f)(x);
});
}
return G(G);
}
最后,让我们把语法糖去掉,看看完全匿名函数写成的递归函数:
(function(F){
return (function(G){
return G(G);
})(function(f){
return F(function(x){
return f(f)(x);
});
});
})(function(f){
return function(n){
if (n == 1){
return 1;
} else {
return n * f(n-1);
}
}
})(5); // output 120
😂 😹 😆
The Little Schemer
的第十章,主要是讲如何用scheme实现一个简单的scheme解释器,虽然只支持built-in的方法和lambda,但已然十分强大,其实现过程真正体现了数据即程序
的特点。不过这个code就真是一大坨了,在此就不张贴了。要看code的戳这里
最后,The Little Schemer
里总结了十条诫律,非常有价值,在此罗列如下
eqlist?'和
equal?'互相依赖所有code放在这里,如果真有人想看的话 😶
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.