September 16, 2007

Mazy i 编程语言定义 (1,2)


 ;; 纯属写着玩儿,尚未最终决定的版本已经与此差别很大,比方说 第二章
 ;; 因为修改麻烦,本博客有关 Mazy(i) 设计方面的文章从此只发表第一稿。

1. 前言
Mazy i 编程语言,是一种用一阶λ演算的观点解决普通数学问题的纯函数式编程语言,具有极其简洁的语法和一定的通过数学表示推导解决数学问题的能力。它被设计为一种附合熟悉普通数学记法的用户在思考函数式编程时使用的简记记法的语言。它在语法、语义、实现方面的设计必须附合这一要求。第2章对此给出了概述性的解释。
第3章具体描述 Mazy i 的所有语法,每个语法后有用 Mazy i 扩展记法给出的语义描述,某些语法可能附上实现指导。
第4章描述了 Mazy i 程序文件中位于代码之前的文件说明区块,以及程序文件的加载、执行方式。
第5章描述了 Mazy i 内置库中的所有函数和宏,重点概念会给出 Mazy i 扩展记法的描述。
附录A总结第3章给出的用简化的 BNF 表示的 Mazy i 形式语法。
附录B列出了部分参考文献。
Mazy i 指的是 Mazy 语言第三版。Mazy 代表数学和懒惰,不是混乱和忙碌。字母 i 源自 Mazy 语言的版本命名传统,从第一到第七版分别为 s-t-i-n-g-e-r,排版字体为斜体,下标。Stinger 这个单词是作者姓氏,此外没有其它含义。
以下用 Mazy 代指 Mazy i。

2. 概述
编程语言必须对其设计意图有强大的表现力。强大基于完备,完备基于简单。
Mazy 的设计意图是作为一种可执行的简记记法帮助熟悉简单数学表示法的用户思考、编程或教学。也就是说,Mazy 试图用程序的观点去解释范围不超过基本函数、数列的数学记法。当然,作为基于λ演算的编程语言,Mazy 还有足够的表现力去解决更复杂的问题。
例如,Mazy 中的列表可以作数列解释。对于给定的列表 l,其第 n 项在 Mazy 中可直接表示为 l n。同时,使用递推的观点可以写出求列表长度的函数。下面的函数就是一个合法的 Mazy 程序:
 len ls =
   0, ls = ()
   len(tail ls) + 1.
Mazy 可以把列表看作是第一项 x 与剩余项 xs 的组合 x:xs,所谓 tail 函数不过是:
 tail (x:xs) = xs
那么 len 函数就可以直接写成:
 len () = 0
 len (x:xs) = len xs + 1
以上是 Mazy 在语法方面试图实现其设计意图的一个例子,用到了单一控制结构和函数单参数的语法特性。其它语法,包括块结构、列表领悟、λ形式等,以及为保证这些语法的等效性而设计的 Mazy 编程语言语义,例如完全无副作用,单一数据类型,单一数据结构,完全基于模式匹配等,都会在本文档中给出详细描述;附加的实现指导,例如尾递归优化,列表、元组共存模型,缓存机制等,则用于指导 Mazy 的实现人员更好地保证基于这些语义的程序高效地执行,以防止用户被迫转用其它语义思考和编程。

No comments: