[科普中国]-面向表达式语言

概述

面向表达式语言也称为应用式语言(App!icative Language)或函数式语言(Functional Language)，是一种全新的程序设计语言。函数式程序没有诸如指令计数器、数据存储器和程序当前状态之类的概念。这种语言的程序是纯数学意义上的函数，它作用于程序的输入，得到的结果值就是程序的输出。因此它不具有副作用，保证了程序各部分的并发执行，不会影响正确结果的获得，对高度并行的系统结构，更适宜于采用函数式语言来设计并发程序。

在函数式程序设计系统中，程序是一个表达式，计算过程仅由函数来描述。对运算的顺序并无显式的描写，运算顺序只蕴涵于各函数调用之间的依赖关系中，且与运行程序的实际运算结构无关。

构成函数程序的主要成分是原函数(Primitive Functions)、复合函数和定义。原函数的主要功能是实现由对象到对象的映射，或是把一个对象变换成另一个对象。常用的原函数有选择函数，算术函数，交叉置换函数，比较、测试函数，加1、减1函数，附加序列函数，分配函数，取序列尾函数等。复合函数的主要功能是利用函数构成算符，将已有的函数构成新的复杂函数，常用的程序构成算符有：组合算符“O”，构造算符“[]”，条件算符“→”，插入算符“/”，作用于全体(Apply to A11)算符“α”等。复合函数只有经定义“f”并输入到机器后方能应用。用户定义的函数由形式参数表和函数体两部分组成。函数定义的过程也就是建立形式参数表中形式参数与函数体中的变量之间约束关系的过程。

归约机是一种面向函数式程序设计语言的计算机，属于需求驱动的系统结构。指令的执行顺序取决于对这些指令产生结果数据的需求，而这种需求又源于函数式程序设计语言对表达式的归约。归约操作主要是函数作用和子表达式变换。归约过程就是将每个最内层可归约表达式用其值来替换，这样又形成了新的最内层可归约表达式，然后再对其进行归约，最后，整个程序全部被归约，仅留下最终结果。1

特点函数式语言的主要特点是：

1)直接由原函数构成，层次分明。所编程序为静态的、非重复的，便于错误检测。

2)程序与数据分开，数据结构不是程序的组成部分，同一个函数程序可处理不同的对象，程序具有通用性。

3)程序中包括了固有并行性，便于检测和并行。

4)程序无状态并采用数据存储单元。

5)无赋值语句，不使用GOTO类控制语句，所使用的程序构成算符，遵从许多基本代数定理，因而由函数式语言所编写的程序的正确性，易于得到证明。1

函数式语言的归约机结构归约机按其归约模型可分为串归约机和图归约机两类，两者的区别主要是对函数表达式所使用的存储方式不同，串归约机以字符串形式存储，图归约机以图的形式存储。

串归约机串归约机的例子是Mago提出的细胞树形结构多处理机FFP。FFP规约机的结构如图所示。

图中线性L单元阵列是一个带有逻辑功能的存储系统，L单元不仅存放FFP表达式(程序和数据)，还执行机器中大部分的工作，因而它又是一个PE(处理单元)。相邻的L单元互联成一个线性阵列，这一线性连接仅为了进行存储管理。前端机控制整个系统，包括对FFP机使用的基本操作进行定义，控制辅助存储器与管理I/O。辅助存储器同L阵列的两端相连，随后机器从辅助存储器取出信息到阵列，使其开始工作。若L阵列中的信息超出其存储容量，把溢出部分移入辅助存储器，L单元间经由互联网进行通信，并具有某些处理功能。

FFP机的实现方案有多种，下图所示的二叉树互联网结构是最简单的方案，二叉树网络的内部节点称T单元，叶节点称L单元，树根连到前端机。这种结构具有易于构造和易于扩展的优点。

FFP机的工作过程可分为多个操作周期，每个周期又可分为三个阶段：分解阶段、执行阶段和存储管理阶段。FFP机能较好地完成程序自动分解，机器运行时按程序的实际需要可不断重构系统。机器以函数式语言FFP编程，无需程序员干预而自动地开发并行性。

下图表示向量(3，2，5，1)各元素平方和与各元素相除的计算过程。

图归约机图归约机将函数定义、表达式和目标以图的形式存储于机器中，因此进行归约的对象是图，最常用的是二叉树和N叉树。英国帝国理工学院的ALICE多处理器系统，其目标语言HOPE是纯函数式语言，程序由函数定义集组成。函数通过重写来加以归约，由存放在函数定义数据库中的代码替换函数加以实现。ALICE图归约机样机的结构如图1所示，它是一个由16个处理器和24个存储模块构成的多处理器系统，由全互连的Delta交叉开关网实现处理器和存储模块之间的互连。图2中示出了处理器及存储模块的内部结构。每个处理器含有五个Transputer，其中两个从事重写操作，每个带有64KB Cache；第三个用作Cache的管理；另外两个分别作接受和发送信息包用。存储模块的内部较简单，只有一个Transputer进行信息包的发送和接收操作，存储容量为2MB。1