标签归档:Scheme

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。

具体的用法就看文档吧。

诡秘深奥的现代魔法 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++!玩笑玩笑。

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

继续阅读

诡秘深奥的现代魔法 1.2 下

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

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

1.2.4  求幂

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

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

练习 1.19

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

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

一个解释器

在军训的闲暇写下这个文章。

几个星期前的时候,我突然想做一个Scheme 解释器,然后就去做了,尽管我《SICP》第二章还没仔细看完。在经过这辈子第一次天昏地暗的专心Coding 了以后,成品出来了。也是我第一次做出能拿得出手的东西。

但其实这东西技术含量不高,关键的代码只占用了编码时间的20% 剩下的时间都用来写配套的代码,重构和修改代码还有收拾自己的愚蠢Bug。

时间不多,简单说一下结构和核心代码。 继续阅读

诡秘深奥的现代魔法 1.2 上

1.2 过程与它们产生的计算

菜鸟的读书笔记,如果有常识性错误和非常识性错误请毫不留情的开口指正!

1.2.1 线性的递归和迭代

能耐心看这个语焉不详的文章的读者都知道递归和迭代是两种循环的方式。但是SICP 中说道,一个递归的过程中也有递归和迭代的区别,这就是文中所说的:递归计算过程,和迭代计算过程,我们通常说的递归和迭代只是从语法上而言的,书里说的是计算过程,一个递归计算过程需要维护一个栈来储存信息,所以所需的空间是线性增长的(空间复杂度O(n)),但是迭代计算过程对空间的要求是常数级的(O(1)),是维护着一系列“状态”,当调用自身的时候,其会释放空间,所以会保持函数的递归深度为1。
所以如果要用递归过程的话,如果可能最好用迭代计算过程,当然,编译器或者解释器要支持尾递归优化(当一个过程是迭代计算过程,那么就可以说是尾递归的),能够在递归中不断释放栈,比如说我喜欢的Python 就不支持,仁慈的终生独裁者先生还讲了一堆说程序员最好不要用递归balabala,不过这种实用主义的哲学正是Python 的魅力所在。

迭代计算过程就是那种其状态可以用固定数目的状态变量描述的计算过程,而与此同时,有存在一套固定的规则,描述了计算过程在一个状态到下一个状态转换时,这些变量的更新方式;还有一个(可能有的)结束检测,它描述了这一计算过程应该终止的条件。

注:书中说常见语言的递归过程,即使是尾递归也往往需要线性储存空间,但是现在C 是支持尾递归优化的。并且即使编译器没有尾递归优化也可以用手动 goto 语句来实现。 继续阅读

诡秘深奥的现代魔法 1.1

改名叫《诡秘深奥的现代魔法》,“诡秘深奥”是书中第一章形容程序设计语言的词语。

注意!翻译过程中有一些错误,可以看之前先根据勘误表改正,注意勘误表中有一条关于微分方程的勘误(dy/dt 被勘误表改成 dy/dy)可能是错的(原文的方程可能是对的),修改的时候注意。(update: 我发邮件过去确认了我的猜测是对的,之后可能会被更正。)

这一小结说的内容比较基本,讲述了程序设计和Lisp 里面的一些基本原理。

正则序和应用序

我是这样理解正则序和应用序的,正则序是先展开后求值,应用序是先求值再展开。正则序更常用的术语是惰性求值,我比较熟悉的Python 中的生成器就是惰性求值的例子,其他语言也有类似的,似乎都是受Lisp 的启发。(参见第一条评论,是我搞错了) 继续阅读

诡秘深奥的现代魔法 – SICP 读书笔记 0

明天高考成绩出来以后,这个读书笔记如果没坑,说明我还好。我现在心情压抑的转移注意力。

《计算机程序的构造和解释》(Structure and Interpretation of Computer Programs ,简称SICP,豆瓣链接维基词条)这种好书,很早我就买了,几年了我常常带在身边想要翻看,结果只看了一点点,但是因为常常带在身边,有的时候用作鼠标垫什么的,前几页就磨损的很厉害,我总是很自豪地说我把SICP 翻烂了。

实际上Scheme (SchemeLisp 的一个方言,也是SICP 的教学语言)也就写了个hello world。这本书曾是麻省理工的编程入门课程的教材,但是难度一点都不符合“入门”,但我也不清楚是否真的能行,如果没学过编程的人对自己有信心的话可以借来看看。

现在,在高考成绩发表前的忐忑中,我打算一边看,一边连载读书笔记和习题解答。当然,也有些有趣的摘抄。 继续阅读