只有咸鱼看不懂的解释器科普 第一步:解析

嗯,这篇文章是我用来介绍自己的解释器 ika 的,不是宜家是乌贼娘!

ika

ika 其实没有什么独创的设计思想都是抄袭来的,所以我觉得要介绍还不如写一篇科普文。

当然这篇科普文会比较简略,毕竟我也扯不出那么多嘛,不过看完了,虽然不能让你闭着眼睛写一门语言,不过该给你的都会给你……吧。

继续阅读

pyPEG 一个很不错的 PEG 文法 Parser 生成器

所谓 Parser(维基百科称作语法分析器,但是我还没见什么人这样说。) ,就是把字符串转化成程序内部的数据结构,所有编程语言,或者 JSON,XML 这种都需要 Parser。一开始人们人肉写 Parser,然后人们崩溃了,尝试提取 Parser 的模式出来,创造了 Parser 生成器,Parser 生成器通过某些规则来生成 Parser,这种规则就是描述语言文法规则的形式文法,常用的是 BNF 以及其扩展。

因为第四次(还是第五次?)重写自己的 Scheme 解析器,看了自己人肉手写的 Parser,虽然经过多次重构,逻辑更清晰一致,但是还是十分冗杂,本来一直在犹豫要不要用 Parser 生成器,最后 Belleve 大神的文章让我下定决心(已成为脑残粉!本来对 Node.js 不屑一顾,现在打算试试了),用,找不到合适的就写。

我之所以那么纠结用不用 Parser 生成器的原因,一是我想让自己这个东西变得纯净,不是依赖别人的轮子,而是从头发明轮子。二,也是最重要的是 Python 最知名的 Parser 生成器 PLY,并不符合我的口味,先不提很久没更新了,更重要的是,PLY 大量使用了反射,破坏了 Python 原本的模式,以前缀为约定,并不美。

中间还在 GitHub 上找到一个同样是 PEG 文法的 Parser 生成器 但是很遗憾,Python 2 Only。最终还是选择了 pyPEG,虽然感觉知名度不太高,但是文档完备,支持 Python 3 ,而且用法也很清新。

因为这个是我用的第一个 Parser 生成器,所以我不能给你讲 PEG 文法好在哪里,不过和 (E)BNF 最大的差别就是,表达式的析取 (expr | expr) 是有顺序的,如果匹配了一个,就会终止匹配,所以 | 在 PEG 文法里面会写作 /。

虽然说是 PEG 文法,其实并不是像别的工具一样,程序员通过 PEG 文法来写,而是用 Python Class,根据规则来进行,这样虽然有一点麻烦和不直观(嗯,主要是写递归规则的时候有点麻烦。),但是因为不像别的库,没有形式化语言和程序语言的连接问题(比如说 Yacc,里面既有 BNF 也有 ),感觉有点清爽。

于是我用了五行就写了一个 S 表达式解释器,但是现在不这样了,因为 Python 有递归深度限制,还有一些特殊情况比如说 Quote。

具体的用法就看文档吧。

函数式编程简介

这是我为了学校的一个活动准备的讲稿,这几天会不断编辑。

伪代码

为了便于理解,这里用类似 JavaScript 的代码,在文中可能不会给出函数的具体实现,但都是容易实现的。

在这里,我尽量使用比较通用的名词,但是因为语言不同也会有差异。

另外,JavaScript 也算是函数式编程语言,所以文中的伪代码在简单的修改以后应该可以运行。

什么是函数式编程?

广义上很多编程语言都是函数式编程语言,比如说 Python、Ruby,而在最近 Java 8 和 C++ 11 都引入了很多函数式特性。

概括说,函数式编程往往有这些特点,而且这些特点是有关联的:

  • “第一级”(first class)的函数,常常使用高阶函数来抽象。
  • 利用递归进行循环。
  • 将程序看作表达式的组合,尽量避免“副作用”——很少使用变量!
  • 惰性求值。

下面就稍微说一说。 继续阅读

我的三观 基础

现在又是例行的神棍时间,这篇文章我一直想写啦,各位大大就看看笑笑吧,我幼稚的三观如果今后有小变化就在这篇文章里面改,大变化估计要重写了~

以下是中二病患者浅薄的污物,如果不想被精神污染的话请不要阅读!

我是中二星球的一个和平主义者,我首先收到HTTP请求是你们的幸运,警告你们:不要阅读!不要阅读!不要阅读!!!

好,不说废话,直接进入正题,三观我暂且定义成“理念”这类东西,就不纠结哪些是人生观价值观世界观了。 继续阅读

什么是独立思考?

很多人说要独立思考,但是当这句话被广泛认同以后我觉得自己有点想法。

独立思考本身没错,但是如何独立思考呢?我举个例子,就拿手下的键盘来说。

我们的键盘大多是 QWERT 键盘,但是一开始很少有人想过到底为什么,有些人想了,并且在网上查了,发现是因为打字机时代,其实键位是 ABCDE 这样的,但是打字员用得太熟练,速度太快了,故障率也随之上升,于是打乱按键人为添加困难,随后电脑的键盘也继承了布局。

这个解释合情合理,让人恍然大悟。但是有一天我在网上逛,发现这个解释其实是捏造出来的实际上是为了分开常用的一些字母,降低错误,提升效率,设计师花了五年时间来完善这个布局继续阅读

作为初学者给编程初学者的建议

同为编程初学者,特别建议初学者把自己的代码发到 GitHub。

首先不管是不是有人看,代码总是在大庭广众之下的,你也有动力去反复改反复注意如何编码更好,总之就是代码写得丑了不好出门见人的感觉。

其次是版本控制的天然优势,你可以翻自己以前的代码,看到自己是怎么进步的,代码是如何从少变多从简单变复杂的。Commits tioover/cbase GitHub (别学我,我原地踏步)

再次是如果有问题,你可以直接贴地址给别人,有代码高亮也有评论功能,实在不行还能把代码下载下来自己调试。这个就是昨天我遇到了问题,@csslayer 和 雷喵 两位好人大大帮助了我解决这个弱智低级错误:

同时 GitHub 上也有很多项目,不乏同是新手的联系项目和帮助新手的手册等等,你看我随便一搜“中文”二字就出来一堆很赞的教程: Unknwon/the-way-to-go_ZH_CN · GitHub youyudehexie/node123 · GitHub justjavac/free-programming-books-zh_CN · GitHub

然后然后你可以参与开源项目,就算只是提交几个 Issue。

最后,你还可以看个人页面的格子图,一年里哪天荒废了,哪天代码写得很多一目了然,既激励又敦促。

GitHub_grid
荒废了那么多时光……

你们看,那么好的方法,对初学者来说简直就是量身打造啊。

诡秘深奥的现代魔法 1.3 下

虽然是下,但是因为只剩一个小节了所以没什么好说

1.3.4 过程作为返回值

过程作为返回值,意思是在函数里面用 lambda 动态的生成一个函数作为返回值,作为一种抽象工具来说是十分强大的,在后面的例子里也能看到。

这一小节的实例是牛顿法,可以逼近方程的解,我猜计算器解方程就用得是这种方法。

在这个例子里面,“高阶函数做抽象”这一节里面学到的方法基本上都被用到。

后面的习题看着虽然吓人,之前还吓退了我,不过硬着头皮去做会发现不难。

练习 1.45

这一题要写代码不断试做实验,但是因为用了前面的习题的代码所以要保证前面的习题的正确。

实验以后可以看到:(平均阻尼次数 -> 开次方数)

  • 2 -> 4
  • 3 -> 8
  • 4 -> 16
  • 5 -> 32
  • ……

显然是对数的规律,k次开方最少需要 \lfloor lg(k) \rfloor 次平均阻尼,lg 代码懒得写,是从这里复制的。

诡秘深奥的现代魔法 1.3 上

用高阶函数做抽象

终于来到这里了,前面的大都是开胃菜,我们常说的函数式编程最大的特点就是,函数也像一个数据一样可以被放进数据结构里面,也可以作为参数传入,作为返回值,在程序中动态生成,一个常用的行话叫做:把函数作为一等公民。

这个特性能让程序的表现力大大提高,以至于很多新旧语言都吸纳了这个特性。我们从现在开始真正学习抽象这个极其有力的魔法,到了这本书后面你就会觉得,自己动手让没有 OO (面向对象)特性的 Scheme 语言支持 OO 实在是一件简单的事情。有人想对 C 这样做,最后出来的是 C++!玩笑玩笑。

言归正传,书中也讲了,高阶过程就是将过程作为参数或者返回值的过程,在数学里面很高端地叫做“泛函”,还有一个高大上的数学分支叫做“泛函分析”,我是完全搞不懂啦。

继续阅读

微世纪

我觉得可以有一个信仰微生物的宗教啊。

  • 起初没有世界也没有神,神在混沌中被孕育。祂无比的微小,但是又无比浩瀚,因为祂可以复制自身,神复制了以后依旧是神,依旧只有一个神,所有微小的亿万分之一的整体才是祂。
  • 经历了漫长的岁月以后,神想要创造世界。神必须审判自己,让自己的一部分褪去神性。
  • 神化作蓝藻,从混沌中采集负熵,降下了审判。神的审判遮蔽了这个世界,现在的凡人唤作氧气。
  • 失去神性的神难以对抗外界,他们聚在一起成为了多细胞生物。
  • 神是遍在的,神调和着自然的规律。神将死去的生物分解,轮回于自然。神将创生无穷力量的权柄化作叶绿体分享给了一脉生物,将使用这些力量的权柄化作线粒体分享给了所有生物,权柄都含有神性。
  • 多细胞生物不断繁衍壮大,存在于海中和陆地。神帮助它们,也用死亡选择他们。神是仁慈的,也是残酷的。
  • 最后,灵长类的裸猿诞生了,与此同时世界也诞生了。
  • 神安息了。
  • 神被惊醒了,因为裸猿窃取了专属于祂的权柄——青霉素——对抗祂自身。神愤怒的降下审判,专属于裸猿的审判,裸猿唤作 HIV。

诡秘深奥的现代魔法 1.2 下

这个系列好久没写了,刚刚依靠光速浏览看到了第三章的结尾,于是回顾以前的章节开始认认真真读第二遍了。看以前的写的内容感觉就像习题解答一样无趣,于是多一点理解少一点习题,有趣的习题当然还是要写的,没写出来的习题也应该在这个仓库里面,如果没有的话大概是我不会做。

1.2 过程与它们所产生的计算

1.2.4  求幂

这里介绍了求幂的一种\Theta(\log(n))时间界。特别舒爽。下面的习题里面的迭代计算过程的求幂比较简单,后面的练习 1.17 也没什么难点。

对数步骤的求幂已经很让人奇异了,下面还有对数步骤的斐波那契数。

练习 1.19

这一题别看说什么变换族,什么让你证明,实际上挺容易的。

a\leftarrow bq+aq+ap
b\leftarrow bp+aq
.
继续阅读

生命,宇宙,以及一切的元

这篇文章想写很久了,这两年稍微了解了一点公理系统,哥德尔不完备定理以及其它的一些杂七杂八的东西总结的一些粗浅的玩意儿。如果看到上面一些名词就猜到我大概想要说些什么的人,基本上也不用看这一篇文章了。

从小时候开始,我注意到一个很有趣的现象,对生活中的任意问题“钻牛角尖”“打破沙锅问到底”,最后总会得到一个无法解决的问题。

“妈妈你为什么一定要我吃蔬菜?” “因为吃蔬菜会让你身体健康。”

“妈妈我为什么要身体健康?” “因为身体健康了以后才能活得长久。”

“妈妈我为什么要活?” “……没有为什么,因为你就要活下去。”

往往会收敛到一个哲学上的“终极问题”上。 继续阅读

近况

1

家里的情况越来越糟了,我不敢想像未来会是什么样的发展,自己又什么都做不了只能添乱。

2

在学校的OJ 上做题,快有一百道了,做的大多是C 基础题,虽然很多不难但是感觉自己对C 的熟练度提升了不少。

感觉做这种题注重解决问题不注重抽象,不过自己好好命名函数,grep 找找也是很棒的,很多题大同小异甚至复制就能AC。

3

心情很糟。

18 岁到了什么事情都来了。

好想和以前一样无忧无虑。

关于辩证法的一点疑惑

连写了3 篇哲♂学日志,你们一定以为我中二病犯了吧。其实这几天一直在做SICP,这些文章主要是把我一直以来的发病产物总结了而已。

我不了解这东西,只被科普过,所以下面的内容看看笑笑就好。

刚听到辩证法的时候感觉确实很有道理,枪能杀人也能保家卫国,塞翁失马……反正没什么东西只有好处没有害处,也没有什么东西只有害处没有好处的。

在我的理解中,辩证法是这个样子的,通过两个对立的概念分析一样事物,将事物属于这两方面的特性给“解”开来。

很明显,事物都有两面性,这是不容置疑的。但同样明显的是,辩证法并非真理。那么是什么地方出了问题了呢?

我们假设地球其实处在外星人的实验室里面,一个外星人正在记录,对这个外星人来说人类只是这个实验的一个现象而已,从微观上来看还有更多细小的现象,这一切和他没关系,要做的仅仅是记录而已。 继续阅读

黑白玛丽不存在

黑白玛丽也是一个著名的思想实验,指出了“知道”与“体验到”存在决定性的差异。[1]

哲学家提出这个概念是为了反驳物理主义中,认为一切都是物理过程的机械演变,和拉普拉斯妖的假设有点像,不过这个物理过程不局限于经典力学,也就是说不管是波函数还是别的,或者是未被发现的理论……也就是说,物理过程就是一切可以用理性加以实证的东西。用物理主义的观点来解释人类,就是复杂的结构,身体中的神经元细胞中的电流产生了名为“意识”的,实际上不存在的现象。

// 题外话,或许可以将其称之为“机械唯物主义”。XD

黑白玛丽的说法,其实就是“不可与夏虫语冰”,看上去确实无懈可击。但我认为是诡辩,因为混淆了“身体不能做到的”和“实际不能做到的”。(这里的说法我感觉不确切,但是想不到更合适的了。)

为了说明这一点,只要稍微修改这个实验就好了,很简单,一句话:

玛丽自己发明制造了一个仪器,能对自己大脑关于视觉的神经元进行精确的刺激,从而让大脑体会到色彩。

[1] 哲學哲學雞蛋糕 黑白瑪莉

拉普拉斯妖不存在

以前提出了这样的思想实验,如果有一个妖怪或者机器能获取全宇宙所有粒子的位置,然后根据经典力学推演就能预知未来。对小时候的我来说,很长一段时间因为这种宿命论和自由意志的虚无而感到无可适从。

不过因为量子力学引入的不确定性就宣告了拉普拉斯妖的死亡,但是即使是经典力学下拉普拉斯妖也是不能预知未来的。

拉普拉斯妖等同于一个计算机,那么就可以用计算机的理论去讨论了,如果它要预知未来,必须计算全宇宙所有的粒子,但是问题是,拉普拉斯妖也是宇宙中由粒子组成的物质,它计算了未来以后大脑里面的状态也是不一样的,“计算”这个行为本身也是要纳入计算的,也就是说对未来的计算会陷入无穷递归之中。[1]

也就是说,我要计算我之后要想什么,我之后必然是在计算我之后之后在想什么,我之后之后必然是在计算我之后之后在想什么……

当然有一个方法能规避这一困境,就是拉普拉斯妖位于宇宙之外,不参与宇宙,所以不需要计算自己的大脑,但是这样的话,拉普拉斯妖就可以用奥卡姆剃刀杀死。

更新:

CS Slayer 大大指出,关于自指地计算大脑形成无限递归从而无法计算的论述不成立,因为 继续阅读

由Cookie Clicker 想到的

Cookie Clicker 真是一个神奇的游戏。

刚开始玩的时候, 一下一下点,觉得自己有成百上千个饼干顶天了,然后慢慢的,有了鼠标和老奶奶了以后觉得可以尝试一下几千个饼干了,一万个饼干觉得遥不可及……

慢慢地,现在每秒钟都有十亿个饼干了,但是发现自己从来没满足,以前感觉能让自己满足的数字,真到了那个时候也就轻轻跨越,将目光放在更庞大的数字。

cookie

或许,“满足”是和“明天”一样的概念。不过感慨这些是毫无意义的陈词滥调,人类如果懂得满足的话现在不就只能住在洞穴里面了吗?

我只想说一句,好想好想让每秒饼干产量突破百亿啊!好想刷成就啊!好想把能升级的全升级了啊!

UPDATE 不知因为BUG 还是什么,我的饼干全没了,还我,还我!!!