四类程序

redraiment, 2009-07-25

　　前几天读了沈公的《也谈写写编译器》，很认同其观点。我也赞同“编译原理”就像数据结构一样是很基础、很实用的课程：“unix/linux 下随便哪个项目为了方便都可能随手做一个, 这是 unix 程序员的基本功”。但很可惜我们学校软件工程专业不开设编译原理，理由是学了没用。

　　我们都知道“程序=数据结构+算法”，我们姑且通俗地说是程序由“数据”和处理数据的“行为”组成。根据程序对数据和行为的控制，可以将其归类为“硬编码”、“可配置”、“可控制”以及“可编程”四类。下面以简易计算器为例依次讨论。

硬编码

　　此级别的程序，数据和行为都是硬编码到代码中，执行时用户不能改变。比如在C程序中直接printf ( "%d\n", 1+2 );。这时候程序的数据“1”、“2”和行为“+”都是固定不必的。

　　硬编码的程序在实际应用中不常见。

可配置

　　到了可配置级别，程序的行为依然固定，但数据由用户来决定。比如ACM的经典入门题“a+b”：scanf ( "%d%d", &a, &b ); printf ( "%d\n", a + b );。此时程序行为依然是求和，但数据是运行时才确定，程序变得比较灵活。

　　为可配置的程序提供的数据文本，可以看作是一种数据格式（Data formats）。比如 /etc/passwd。

可控制

　　可控制的程序比可配置更灵活，运行时用户不仅可以指定数据，还能指定处理该数据的行为。即运算符“＋、－、×、÷”也由用户指定。例如scanf ( "%d%c%d", &a, &c, &b );，接下来用switch (c) 分别处理四则运算。可控制就是指程序的行为可控制，但行为的范围依然是固定的。也就是说用户指定的行为必须是程序本身提供的，程序只能进行四则运算，求根、阶乘等运算行为程序没提供，因此就无法使用。

　　此时，程序的数据文本具有隐式操作，可以理解成一种暗含控制流的声明性语言。例如 fetchmail(1) 的运行控制语法可视为一种很弱的命令性语言。

可编程

　　可编程的程序，已经同时具备“输入输出、算数运算、内存管理、按条件跳转”四种性质（请参考前文《用DOS批处理来做数字图像处理》）。此时程序的行为是可扩展的，例如能通过迭代来运算阶乘。

　　此时的程序已经发展到命令性（具有显示操作）的微型语言范畴，几乎快成为通用解释器。bc(1) 和 dc(1) 都是完备图灵机语言的好例子，它们都是命令性微型语言。