May 20, 2007

Mazy 编程语言介绍

  • 豆瓣网上的讨论,还真“激烈”,废话请读者自行略过。


2007-05-16 22:11:52   来自: 冰の銳 (南京)

  因为我在网上首次提到我设计的Mazy语言是在这个小组 & 这个小组人还比较多,所以在这儿“大肆”宣传我的东东。
  
  以下摘自我给其初期实现 WebMazy 所写的文档:
  "WebMazy 是一个开放源代码的 Mazy 语言环境,提供用纯JavaScript实现的网页式界面。它还提供了使用JavaScript来扩展Mazy库的方法。
  
  Mazy 语言是作者独立设计的、面向基础数学问题的函数式编程语言(functional programming language),具有极其简洁的语法和一定的直接通过数学表示解决数学问题的能力。"
  
  有需要源程序者发我豆邮付上您的邮件地址。

> 修改 


2007-05-16 22:19:42 冰の銳 (南京)

  以下摘自文档的入门部分,"Hi, I'm Mazy!" :
  
  
  $一个计算器
  
  Mazy 最基本的用途是作计算器——表达方式和你平常在纸上写的那种基本没什么区别。例如(直接的一行指的是在interpretation中的输入,以 > 开头的一行指的是trace中的返回情况):
  
  2+2
  > 4
  (50-5*6)/4 ;这是一个补充型注释
  > 5
  7/3 ;不能整除,返回小数
  > 2.3333333333333335
  pow(2,1000) ;内置函数,这里取2的1000次方
  > 1.0715086071862673e+301
  18%4 ; '%'是取模运算符,简单地说就是返回余数
  > 2
  
  平心而论,Mazy 在简单运算方面并没有太多亮点,和 Haskell 之内的支持无限长整数和复数运算的东西全然不能相比;不过人家毕竟是“世界上最先进的语言”,要知足,要知足~~
  
  
  $带变量支持的计算器
  
  变量是什么?一个静态的定义而已,给一个值一个名字而已:
  
  x = 34 ;现在x这个名字就代表34
  > 34
  x*x
  > 1156
  
  数学上好像只有“代数”这个概念而没有“变量”这个概念,况且 Mazy 是函数式编程语言,变量一经申明就不可在同一环境下改变其值,应该叫“不变量”还差不多;
  
  x = 34 ;重复申明试试,
  > RuntimeError: The name x already has a definition in this level.
  
  这句话是我写的,我很自豪啊^_^
  
  完了,变量值不可改变,难道说每次求一个数的平方都要输一下xx*xx吗?!
  
  $可以定义函数的计算器
  
  函数是什么?在Mazy中,我可以负责地完全使用数学上的定义来回答这个问题:函数是一个确定的、多对一映射。完全不同与C等命令式语言的函数——他们不但状态可变而且行为恶劣。好了,多说无益,看看怎么解决上面的问题:
  这是一个标签型注释,下面我们定义这个返回参数值平方的函数: sqr (x)=x*x
  > function()
  sqr(23) ;23的平方
  > 529
  sqr'2(x)= 2*sqr(x) ;再试一个(注意''和"等效,都可用作命名;Mazy中没有字符串。)
  > function()
  sqr'2(5) > 50
  
  $能作判断的计算器?!
  
  憋死我啦!终于到了展现Mazy力量的时候啦!来看看这个求阶乘的 C 语言程序:
  int fact (int n) {
   int result = 0;
  for (int i = 1; i <= n; i++) {   result *= i;   }    return result;   }      这个是Mazy版的(在inter中深入多行程序时可以用Shift+Enter来输入换行;或者在definition中定义(自己写一遍,不要CC+CV),然后在inter中使用。(*...*)之间是一个文档型注释):   (* 把阶乘的数学定义照抄一遍, 最后加个英文句点就行了 *) fact (n) =   1, n=0 n * fact(n-1).      接着在inter中计算:   fact(10) > 3628800
  
  如果你现在有一种身陷迷宫的感觉,那我的目的就达到了——Mazy意为迷宫般的。
  
  还是说一下这是怎么回事吧!Mazy中,一个函数必须有且只在最后有一个返回表达式(正则尾递归,有了它,程序就不需要循环结构了);在多行申明下的单行中出现了用,分割的两个表达式时,就认为这种情况分析表达式开始,每行的第二个子式分析条件,一旦满足就返回该行的子表达式,直到函数体以. 结束(思想来源于ML)。很明显,这里申明语句是无效的,所以所有的=号执行比较运算,返回布尔值true或 false(Note:布尔值运算符:与& 或| 非! )。
  
  所以,求一个数绝对值的函数就可以写成这样(这只是个说明用法的例子而已):
  abs' (n) =
;加'是因为内置库中已有定义,最好不要覆盖
;顺便提一句:函数的这个位置可以填入属于它的内部申明
;这就是所谓的“块结构”,其本质见于《计算机程序的构造与解释》
普通变量也可以用条件分析句申明,但没有“块结构”
  n, n>0
  0, n=0
  -n, n<0.> 5050
  
  我再来带你们走过迷宫吧!函数参数域中全是常数或者'*'符号的本质上不是函数,他们不允许有“块结构”,他们是函数的“常量”版本,学名叫做 “槽”(chunk)(来自于Haskell, ErLang等FPL),他们常常可以起到支持能通过数学归纳法证明的函数停止的作用。比如这个求n阶等差数列第m项的公式:
  ff(1,*) = 1
  ff(*,1) = 1
  ff(n,m) = ff(n-1,m) + ff(n,m-1)
  
  很多后现代的语言都配备这这个东西,但对于 Mazy,它是有重大意义的。
  
  
  $形式与内容高度同一的自动计算机
  
  C语言吃了大亏了,它总是成为我的反面教材。来看看这个“臭名昭著”的、在无数算法书中被指责为“极其低效”的求菲波那契数列第n项的函数:
  int fib (int n) {

   if (n <= 2) {    return 1;   }   return fib(n-1) + fib(n-2);   }      就一个字:慢,奇慢无比,算法复杂度O(2^n)级,算到40多就彻底崩溃了;但它是到公式的直接翻译,使用了十分清晰递归。我写了一个O(n)级的递归版本:      int i = 3;   unsigned long fib_iter (int x, int y, int n) {   if (i <= n) {   i++;   return fib_iter(y, x + y, n);   } else {   return y;   }   }   //这是被调用的函数   unsigned long fib (int n) {   return fib_iter(1,1,n);   }      然而老师们更希望我们使用更丑、更恶劣的纯循环来完成这个程序;不如干脆我们学习汇编语言吧!那个更快。(我以为,我们现有的计算机教育真的正在歧途中越走越深)      还是让我们回头看看我们美丽的迷宫吧!在Mazy中,使用完整的数学定义直译或者给出某些递归下降点的办法直接写出程序就能获得O(n)级的线性算法复杂度:   fib(1) = 1   fib(2) = 1   fib(n) = fib(n-1) + fib(n-2)      算着玩儿吧,算到100都只是弹指间的事;   fib(100) > 354224848179262000000
  
  如果你是个对于算法有所了解的,此时一定已经从电脑椅上翻下去了;不过,如果你确实对于算法很了解,此刻一定已经想到了一个词——动态规划。
  
  对,动态规划!fib的数学定义为什么慢?充分的计算占到了总计算量的绝大部分;采用一个动态记录计算中已得到的值的标格问题就解决了;再细想下去,基本的、仅针对函数参数进行判断的动态规划是非常机械的,为什么不能成为语言的一种函数调用机制呢?
  
  这种机制叫做“带有自动记忆的按需调用槽”,Mazy 实现了它。
  
  于是,Mazy 带着0个关键字,一系列优雅的、数学语言直译化的语法,破除了使用这些东西可能带来的性能的降低,上路了——一种非常罕见的形式与内容高度同一的自动计算机就此诞生了。
  
  还有什么?
  
  还有什么?Mazy 还有几个成体现的重要特性,但这儿是“初学者课堂”,语法到目前为止基本讲完了,那些“重要特性”的真正有效的使用可不是这样短的一篇文章就能覆盖的。就好比下棋,规则就那么几句,但不是谁都能领略其中的端倪。Mazy 就是这样的一种语言。
  
  最后列出一点东西,作为文章的结束。
  
   * 一元前置运算符:- + !
   * 一元后置运算符:
   o ++(增量位置,相当于Lisp中的car,取出一个列表(list)的首项)
   o --(减量位置,相当于Lisp中的cdr,取出一个list除去第一项后余下的项)
   * 二元运算符:+ - * \ % ,= != > |
   * 行末语法:
   o 一行中存在‘:’的,该行是一个标签型注释;
   o 以‘?’结束的行,该行除去?的表达式是一个前置require断言;
   o 以‘!’结束的行,该行除去!的表达式是一个前置ensure断言。
   * 表申明:作为值出现 [项0, 项1, 项2...]
   * 常量:none(未定义值) nil(空表) NaN(非数字) Infinity(无穷大,除0的返回值)
  
  
  习题
  
  关于列表(list)操作我只提到一个++--;但其实只有这些就够了;Mazy 是面向数学的,不赞成你常常手动构筑表(虽然语言library本身提供了此类支持)。来挑战一下自己的智商吧,下面这个函数可以求出一个list的长度,想想它是怎么工作的:
  len' (ls) =
   0, nil len(ls--) + 1.

> 删除


2007-05-17 01:05:15 AlbertLee (北京)

  和
  len' [] = 0
  len' (_:xs) = 1 + len'(xs)
  
  一样了。
  
  不过 fib 那个例子确实是个亮点。

> 删除


2007-05-17 12:09:23 冰の銳 (南京)

  不好意思,最后一个例子少个换行:
  len' (ls) =
   0, nil
   len(ls--) + 1.
  
  可惜现在的实现还不能得像Haskell一样。

> 删除


2007-05-17 16:40:47 AlbertLee (北京)

  fib 的那个“动态规划” 是什么原理?

> 删除


2007-05-17 16:50:21 codeplayer (武汉)

  动态规划是一种算法了,不过语言自动完成倒是第一次见过。
  没玩过 FP,不过貌似很是有点意思哈。

> 删除


2007-05-17 17:34:57 冰の銳 (南京)

  "fib 的那个“动态规划” 是什么原理?"
  把已计算过的参数、值对应保存在哈希表中;因为函数式语言变量的绑定不变,所以对于一个函数,参数到值是数学上的映射关系,可以直接调出结果。

> 删除


2007-05-17 19:56:59 HYRY

  那么获得O(n)级的算法复杂度的同时,是否增加了空间复杂度了呢?既然用哈希表保存中间值,那么这个哈希表是否有一定的大小限制,总不能无穷大吧。如何知道表中的某个内容不会再被用到,而把它释放掉?
  如果不释放的话,fib(1000000)会不会很占空间?
  

> 删除


2007-05-17 20:48:17 AlbertLee (北京)

  被“动态规划”这个词误导了。
  用哈希表保存中间结果,确实是用空间换时间的一种办法。
  如果能通过程序自动把 fib (n-1) + fib(n-2) 这中类型的递归优化到O(n)的复杂度,那确实是太牛了(近似于妖了),不过我显然低估了这个的困难程度了。
  

> 删除


2007-05-17 21:27:46 冰の銳 (南京)

  这种纯优化的想法是可以实现的,但在解释器环境下就不划算了。
  "如果不释放的话,fib(1000000)会不会很占空间?"
  
  对于目前的实现来说是的。但最终实现大概还要再等两三年吧,我打算优化内存分配来消解哈希表空间消耗。

> 删除


2007-05-17 21:39:27 AlbertLee (北京)

  我直觉上感觉无法根本解决这个问题,只能是通过一些优化手段对特定的问题进行近似的优化。无法获得一个算法能通用的优化这个问题。

> 删除


2007-05-17 21:44:44 AlbertLee (北京)

  感觉真是一句废话!。。。

> 删除


2007-05-17 21:57:54 小豆包-习惯了ubuntu…… (广州)

  想要达到线性复杂度,只要保留前两个元素就好了

> 删除


2007-05-17 22:08:23 HYRY

  用哈希表保存函数的运算结果,使得下次运算时可以直接使用,这个想法和CPU硬件的cache差不多.不过因为没有限制内存使用量,这样就相当于 cache无穷大,实际运用上是不现实的. 如果限制了cache的大小,就会出现很多算法上的细节问题. 软件来实现那种set associative cache算法的话,本身就好耗费很多时间.

> 删除


2007-05-18 12:10:31 冰の銳 (南京)

  "想要达到线性复杂度,只要保留前两个元素就好了"
  这只能解决特定问题啊...
  
  我有个想法,向虚拟机学习,设定heap大小,把所有产生的结果放在共有堆中,用户给定的函数特定值保存在私有堆,这样共有堆的删除就可以随意进行了!
  
  其实我还想听听大家对语法设计方面的看法。

> 删除


2007-05-18 13:34:56 codeplayer (武汉)

  其实要是能够智能判断保存中间结果的数量就更好了,
  比如 f(n) = f(n-1) + f(n-2) 只需要保存两个中间结果就够了。
  f(n) = f(n-1) + f(n-3) 就需要三个了。
  f(n, m) = f(n-1, m) + f(n, m-1) ,这个想了一下,貌似有效中间结果最多差不多也就是是 m+n 左右,而不需要保存所有 m*n 个中间结果。

> 删除


2007-05-18 16:38:41 小豆包-习惯了ubuntu…… (广州)

  我的意思是,可以通过代码分析,有限度缓冲数据。保存所有中间结果没有太大意义。比如f(n) = f(n-1)+f(n+1),完全可以从代码中分析中需要缓冲的回溯级数。

> 删除


2007-05-18 17:42:33 冰の銳 (南京)

  "其实要是能够智能判断保存中间结果的数量就更好了"
  这种技术只能用在编译器上,对于解释器来说绝对浪费...
  
  "从代码中分析中需要缓冲的回溯级数"
  只可惜真正的递归复杂程度远不止于此,有很多论文但都不可行。目前解释器技术能分析正则尾递归我觉得已经很高级了。

> 删除


2007-05-19 10:59:14 仨儿 (北京)

  咔咔咔!国人作品,应该关注!

> 删除


2007-05-19 11:08:10 ookami (Tōkyō)

  任何语言都能写出O(n)的fib算法出来
  这是算法层的问题,而不是语言层的问题。
  时间换空间和空间换时间,都是算法的需要,或者说是业务的需要,在语言上不应该武断地替用户做这种选择。

> 删除


2007-05-19 11:58:14 冰の銳 (南京)

  
  首先请楼上看清楚,Mazy是为了能让数学形式直译的函数都能完美执行而设计的,不像某些语言是为了让用户在想用它们了解计算机科学和数学式成天面对指针和内存而设计的!
  
  "任何语言都能写出O(n)的fib算法出来
   这是算法层的问题,而不是语言层的问题。"
  
  这话说的真的太残忍了...看看我们的小学、中学那些学编程的孩子们,有几个不是为了竞赛,不是为了升学?学的那些Pascal、C,不能说语言本身不好,TMD叫这些孩子在把已有知识转化为能力多么困难啊!而国外呢?小学有用Smalltalk的,中学学习Scheme,10岁小儿就能用 Scheme编写出Adventure游戏,这TMD叫差距啊!为什么啊?我们的教育者成天关注的都是些什么啊?!且不说函数式编程的重要性,就算是 Pascal、C,写那种代码也配叫编程啊?
  计算机教育必须以提升被教育者的思维能力为目的而不是其它!

> 删除


2007-05-19 14:47:11 ookami (Tōkyō)

    不想扯太远,就事论事。
  
    听说lz的lua已经出神入化了,比精通还要精通,就帖一段lua源代码test里面的那个fib吧,我认为你应该看过的
  
  -- very inefficient fibonacci function
  function fib(n)
    if n<2 c="{}" y="c[x]" y="f(x)" fib="cache(fib)"> 删除


2007-05-19 15:21:05 冰の銳 (南京)

  “你的O(n)级的递归版本里面的那个全局变量i用的可真是,,,,,,”
  所以说嘛!
  
  你那个是
  SICP里的原版代码,但不是仍然要求用户思考吗?
  再者,对于既没有赋值又没有宏的函数式语言来说就更不行啦。
  把这个机制做到语言里就是Mazy的当前实现手段。

> 删除


2007-05-19 17:43:09 ookami (Tōkyō)

  --但不是仍然要求用户思考吗?
  难道你觉得用户不应该思考吗?
  
  打住吧,等你的Mazy稍微成熟一些的时候再讨论这个问题,说不定到那个时候你的想法也发生变化了。

> 删除


2007-05-19 18:17:18 冰の銳 (南京)

  --"难道你觉得用户不应该思考吗?"
  啊对对对...我现在就在上高二,你可能不知道我们中国的计算机教育现状。XXXX。不知者无过。
  等着吧,等我一切安定下来了把Mazy i的C语言实现给写了,"你的想法也发生变化了"。
  
  PS: 你的所在地上显示个Tōkyō我不知道是什么意思。

> 删除


2007-05-20 00:35:20 ookami (Tōkyō)

  我不知道中学的计算机教育情况,事实上在我上中学的时候还没有接触过计算机。不过这不重要。
  等着吧,看谁的想法先变。
  PS:你应该是个聪明的人,所以应该有办法知道Tōkyō是什么意思。

> 删除

No comments: