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.
$这是什么？函数？
这一节只是讲一个简单的语法形式而已；不过，它的意义远比其形式重大的多。
有些时候，我们在数学上定义一个函数并非是像上面那样给出一个完整的分段函数，而是先给出函数的一般性结喉，再取函数的某几个点上的值来完成申明。例如求1, 2, 3 ...等差数列的递推公式：
S(1)=1
S(n)=S(n-1)+1
现在告诉大家一个令人震惊的消息：把上面两句话抄到definition就能运行了。
S(100) > 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-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-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
不想扯太远，就事论事。
听说lz的lua已经出神入化了，比精通还要精通，就帖一段lua源代码test里面的那个fib吧，我认为你应该看过的
-- very inefficient fibonacci function
function fib(n)
if n<2 then
return n
else
return fib(n-1)+fib(n-2)
end
end
-- a general-purpose value cache
function cache(f)
local c={}
return function (x)
local y=c[x]
if not y then
y=f(x)
c[x]=y
end
return y
end
end
fib=cache(fib)
另，你的O(n)级的递归版本里面的那个全局变量i用的可真是，，，，，，> 删除 -
-
-
-
-
-
-
-
2007-07-09 22:05:19 zlk
刚刚被带来的，看了一下，不好意思打断一下，我们回到斐氏数列问题。这是我一个朋友的成果，我转来大家看看
1.Problem Description
二阶Fibonacci数列的定义如下：F0=1,F1=1,F2=2,F3=3,F4=5,…, Fi=Fi-1+ Fi-2, i≥1。试用递归和非递归两种方法写出计算Fn的函数。
函数声明为：unsigned long Fib_rec(unsigned long N);
unsigned long Fib_ite(unsigned long N);
2.Algorithm Specification
略。
3.Program
#include "stdio.h"
#include "time.h"
unsigned long Fib_rec(unsigned long N);
unsigned long Fib_ite(unsigned long N);
unsigned long Fib_rec(unsigned long N){
if (N<=1) return 1;
else return Fib_rec(N-1)+Fib_rec(N-2);
}
unsigned long Fib_ite(unsigned long N){
long int f1,f2;
int i,temp = 0;
f1 = 1;
f2 = 1;
for (i = 3;i <= N +1 ; i++)
{
temp = f1 + f2;
f1 = f2;
f2 = temp;
}
return f2;
}
4.Test Records
测试结果如下表如示：
N
函数 10 15 20 25 30 35 40 45
89 987 10946 121393 1346269 14930352 165580141 1836311903
Fib_rec(T1) 1.218 15.546 0.1703ms 1.906ms 20.93ms 0.2343s 2.578s 28.703s
Fib_ite(T2) 0.014 0.0187 0.0312 0.0437 0.050 0.0546 0.0593 0.064
虽然Fib_rec程序非常清晰，但当N大约为20时，Fib_rec比Fib_ite慢很多。
5.Analysis and Comments
(1) Fib_ite的复杂度分析
在非递归算法Fib_ite中，其基本运算为temp = f1 + f2，其运算次数为N-2次，所以其时间复杂度为O(N)。
(2) Fib_rec的复杂度分析
初步分析：
在算法中存在着大量多余的工作，违反了递归的第四条主要法则（合成效益法则）。如：在计算Fib_rec (N)时，需计算Fib_rec (N-1)和Fib_rec (N-2)，而在计算Fib_rec (N-1)时又计算了Fib_rec (N-2)，如此导致了巨大的运算时间。
时间复杂度分析：
令T(N)为函数Fib_rec(N)的运行时。（把Fib_rec简写成F）。
（1）则当N=0或N=1时，运行时间是某个常数值，即T(0)=T(1)=1。
（2）当N>2时，则执行时间是第一行上的常数工作加上第二行上的工作。第二行由一次加法和两次函数调用组成。第一次函数调用是F (N-1)，从而按照上面的定义，它需要T(N-1)个时间单元。类似第二次调用需要T(N-2)个时间单元。因此，总的时间为：T(n-1)+T(n-2)+2，其中“2”指的是第一行上的工作加上第二行上的加法。于是可得：
T(N)=T(n-1)+T(N-2)+2
但F (N)=F (N-1)+F (N-2)，因此由归纳法容易证明T(N) F(N)。
（3）根据Fibonacci的定义，有Fi=Fi-1+ Fi-2 。则对于i 1，满足 ，可由归纳法证明之。
（4）由上（1）（2）（3）可得该递归算法的时间复杂度为O( )，或 （ ）。
～～～～～～～～～～～～～～～～～～～～
也就是说，斐氏数列的难度是确定的。楼主提到的另一个问题，什么国外１０岁孩子怎么怎么样，我希望楼主明确一点，国外１０岁孩子能做的，我们的１０岁孩子没理由做不了，只要他们有这样的机会。但是我们国内那些参加各种信息竞赛的孩子，他们做的这些，国外同年龄小孩做不到。而且，楼主是否想过，既然１０岁孩子都可以很快做到的，那么让我们国内年纪大点的学生来做，是不是也会很快学会呢？你在另一帖里和０３１８争论的一个问题很有意思，他／她有个说法，很快能学会的东西都很浅薄，具体他说的是多快我不记得，但是这个说法，抛弃极端的部分，这个说法不能算错。外国有神童，但多数孩子的智力和中国孩子比，并不特别突出，他们１０岁学会的东西不会很深奥，我猜想大概就是用一些别人的类库等等拼凑一下。当然，如果你所谓的外国１０岁小孩，是某一两个天才，那当另算，天才和你我这样的凡人没有可比性。但就一般来说，外国小孩并不更聪明。中国小孩做那些信息学竞赛里的题目有什么意思，我看没有，那些都是到大学要重讲的东西，而他们只不过先学了几年而已。同样，我们的中学生国际学科比赛总是领先，但成年人世界竞争却没有太大优势，为什么？也是因为我们参加比赛的中学生已经预先学了大学的知识，外国人比我们只是晚学了几年而已，他们做的是一些兴趣的发展，而这些知识到了大学他们也学了，和我们之间的差距就没有了。如果这个说法你没意见，那么我们就推到外国孩子身上，其实他们也只是先学了几年而已。我们的学生更多的则是在做基本功，基础的训练。这个到底是好是坏，我看还是个可以讨论的话题
另外，美国很多很好的大学，本科学生整天学习不刻苦，比国内好多大学玩的还疯，这是我亲眼看到的。> 删除 -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
> 我来回应
登录 · · · · · ·
这个小组的成员也喜欢去 · · · · · ·
- Django (1337)
- Vim (3252)
- Google App Engine (1416)
- Linux (4189)
- ubuntu (4504)
- Ruby (1146)
最新话题:
请问python有没有简便的字符串解析方法 (NULL)
blast....biopython (Lydia)
关于 Douban 一个URL的问题 (X先生)
请大家谈谈对各种python web框架的感受和优缺点！ (米奇·猴)
http://www.python.org/又打不开了？？ (小艾)
一个wxPython问题 (BeefLiu)
大家是为啥选择python？ (Lydia)
仿google wave写了个网站 (戴铭)