免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12
最近访问板块 发新帖
楼主: walleeee

每一个喜欢计算机的人都该理解lisp这个语言 [复制链接]

论坛徽章:
0
发表于 2012-05-11 22:30 |显示全部楼层
回复 10# walleeee


    以前学数据结构的时候,一个递归算法总是存在非递归版本,其实就是将递归变成循环。

如果把循环全部写为递归,就是函数式编程。

变化的只是表象和形式,不变的是算法复杂度和操作语义。

所以不管表述如何变化,都改变不了一个理论本质,那就是计算机只是一个自动机,如果把所有的操作都看作是字母的话,程序就是运行在这个自动机上的语言接受器,当接受某段语言(操作)的时候就有正确的输入输出,当拒绝某段语言的时候,就有错误的输入输出,甚至蓝屏死机。就蓝屏这段操作来讲,它对于驱动来说是不可接受的,但对于操作系统来说是可接受的。

所以不同的语言其实就跟二进制、八进制、十进制、十六进制数一样。只不过普通人习惯十进制,程序员习惯十六进制,硬件习惯二进制,如果要处理不习惯的进制数,那就翻译一下变成习惯的进制数,就跟在计算机上跑脚本一样,虽然慢一点,但至少方便沟通。

论坛徽章:
0
发表于 2012-05-11 22:41 |显示全部楼层
本帖最后由 sonicling 于 2012-05-11 23:42 编辑

举个例子吧,我是研究编译和文法的。假设有这么一段文法要用递归下降分析来实现:

文法1:
expr -> expr '+' term | expr '-' term | term

他是左递归的,会导致递归下降程序进入死递归过程导致爆栈,所以要写成递归下降,就变换一下,变成右递归:

文法2:
expr -> term expr-right
expr-right -> ε | '+' term expr-right | '-' term expr-right

好了,可以照葫芦画瓢了:
  1. function read_expr(lexer)
  2. {
  3.     read_term(lexer);
  4.     while (lexer.peek() == '+' || lexer.peek() == '-')
  5.     {
  6.         lexer.read_token(); // + / -
  7.         read_term(lexer)
  8.     }
  9. }
复制代码
好了,文法1、2和后面的递归下降分析其实表达的是同一个意思。只不过文法表述更像是函数式的,而递归下降的程序是过程式的。

论坛徽章:
0
发表于 2012-05-11 23:57 |显示全部楼层
回复 11# sonicling


操作语义显然变了。不变的仅仅是限定输入和输出的公理语义。

论坛徽章:
0
发表于 2012-05-12 00:48 |显示全部楼层
回复 13# 幻の上帝


    好吧,如果真要深究的话,操作语义和公理语义都要变。因为两种不同的语言,语法不一样,程序的组成也不一样。对于操作语义来讲,语法范畴变了;对于公理语义来讲,语句集合变了。

但要说公理语义没变我也能理解,因为只要语言宣称是图灵完备的,那就可以和图灵机程序互模拟,两种图灵完备的语言都能和图灵机程序互模拟,那么这两种语言必定也能互模拟,通过互模拟状态就可以找到互模拟的语句,那么就把其中一种语言的公理语义中语句Q替换为另外一种语言对应的语句Q’。就能得到另外一种语言的公理语义了。

而这一变换过程其实对操作语义也可以用。操作语义中有变换语义。两种语义的语法不同不是?如果其中一种语言的任何语法结构能够用另外一种语言模拟出来(语句级可以互模拟,语法结构一定也可以,因为语法可以通过枚举所有语句得到),把对应的语法范畴变换一下就能由一种语言的操作语义得到另外一种语言的操作语义。

这两种变换的本质都是相同的。

论坛徽章:
0
发表于 2012-05-12 01:03 |显示全部楼层
要声明一点:

从实践来说,对于操作语义的变换,很少有人真的通过枚举语句来获得语法,一般都是直接拿定义好的语法来比较,找语法级别的互模拟关系比较困难。对于公理语义的变换,找语句的互模拟关系明显简单一些。

但是谈理论就别谈实践,理论多半都是不切实际的。要较真的话,在实践中公理语义难以形式化描述,能形式化构造的那部分公理语义都是很简单的东西。

论坛徽章:
0
发表于 2012-05-12 11:19 |显示全部楼层
有道理有道理
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP