第四章 模式与规则

    函数语言中引入模式匹配，使得程序形式简洁、可读性好而且有利于程序的正确性证明，所以许多函数型语言，如ML，HOPE，Miranda等都引入了这一机制。Fuxi作为一种逻辑函数型语言，模式的匹配与合一是Fuxi的基本驱动方式。

    模式是由函词、参量表构成的，它是一种表达式的框架。规则是由模式和规则体(Contractum)构成的。

§4.1 模式(Pattern)

    Fuxi中模式(Pattern)定义的文法形式如下：

<模式>定义为：

<标识符>()
<标识符>(<参量表>)

<参量表>定义为：

<参量>{,<参量>}

    其中<模式>定义中的<标识符>称为函词(Functor)。而<参数表>是由0个或多个参数构成的表，如果参数个数大于1，则参数之间采用逗号(，)分隔。参数的个数称为该模式的元。

§4.1.1 模式参量(Pattern Argument)

    模式参量是构成模式的元素。模式参量可以是常量，变量，也可以是由参量组成的表或元组(Tuple)。模式参量定义的文法形式如下：

<参量>定义为：

[<类型>]<常量>                 (1)
[<类型>]_                      (2)
[<类型>]<变量名>               (3)
[[<类型>]]                     (4)
[<参量>{,<参量>}]              (5)
[<参量>{,<参量>}:_]            (6)
[<参量>{,<参量>}:<变量名>]     (7)
<标识符>(<参量>{,<参量>})      (8)

<变量名>定义为：

<标识符>

    模式的参量可以是常量，例如f(10)。(1)中的<类型>是可选项，当常量的数值类型和参量类型不一致，可能导致歧义的情况下，可以在常量前面使用<类型>来声明常量的类型，以便系统进行类型转换，例如f(byte 10)。
符号'_'表示计算过程不关心的计算成份。在可能会出现歧义的情况下，可以采用在前面加上<类型>来声明其类型。

    (4)表示一个空表，在可能会出现歧义的情况下，使用<类型>来声明空表中元素的类型。例如[int]表示一个元素类型为int的空表，或者说类型为int[]的空表。而[int[]]表示一个元素类型为int[]的空表。

    (5)表示一个定长表；(6)表示表头由几个特定元素构成的任意长度的表；(7)可以将表尾约束到某个变量上，该变量的类型就是该表的类型(因此(7)中<变量名>无须任何类型说明)。表中的<参量>必须具有相同的或相兼容的数据类型，该类型的表就表的类型。

    (8)表示元组，它是对象的模式，在无法进行类型确认的情况下，需要在其前面使用<类型>来声明元组的类类型。

    每个参量都是自由变量的模式称为通用模式(Generic Pattern)，带有常量或约束变量的模式称为特定模式(Specific Pattern)。

§4.1.2 模式签名

    模式的函词、各参数的类型共同构成这个模式的签名(Signature)。以下是一个模式的例子：

Fun( 0, int x, double y, false )

这是一个4元模式，其签名为Fun(int, int, double, bool)。

§4.1.3 模式变量

    参量表中的<变量名>，在首次出现时，必须在其前面使用<类型>来规定其类型，表示在模式中声明一个类型为<类型>的模式变量。模式中每个变量只能声明一次，但可以在变量声明后多次使用这个变量，表示处在相同变量出现位置的参量值相同的模式，例如：

f(int x, x)

模式中，不可以声明同名的变量，也就是说，模式中每个变量只能声明一次。例如，

f(int x, double x)

就是一个非法的模式。

§4.2 规则(Rule)

    Fuxi中规则的定义文法为：

<规则>定义为：

<模式> <定义符> <表达式>

<模式>我们已在前面讨论过了。

<定义符>可以是下面符号之一：

=   <-   ->

    <定义符>为等号(=)的规则称为方程式(Equation)；<定义符>为‘<-’称为子句(Clause)；而<定义符>为'->'称为产生式(Production)。规则中<定义符>右边的<表达式>称为规则的右值。方程式的右值可以是任何类型的表达式，而子句或产生式的右值只能为bool型。

    规则中的模式签名、定义符和及规则的右值的类型共同构成该规则的类型。

    我们来看几条规则的例子：

f(0, int x, double y, false) = 0
g(int x, int y) <- k(0, x) && y == 10
t(10) -> g(10,10)

    例子中的第一条规则为方程式，其类型为f(int, int, double, bool) = int；第二条规则为子句，其类型为g(int, int) <- bool；而第三条规则为产生式，其类型为t(int) -> bool。

    具有相同类型的方程式构成一个函数，该类型即为此函数的类型。我们先看一个例子。

// Fibonacci Numbers - Fib.fux
class FibApp : Application
{
    Fib( 0 ) = 1
    Fib( 1 ) = 1
    Fib( int n ) = Fib( n - 1 ) + Fib( n - 2 )

    public Activate( ) =
    {
        Console.Println( "Input a number: " )
        Console.Println( "Fib=" +
        Fib( Console.Readln().ToInteger() ) )
    }
}

    在这个例子里，Fib函数由三个方程式构成，Fib的类型为Fib(int)=int。

    采用规则的方式来定义函数，其结果与参数的关系十分清晰，将大大地提高了程序的可读性、可靠性。

    Fuxi中，规则总是被封装在某个类中，类中所有规则构成了该类的规则库。因此，类也可以被看作是状态和规则库的联合体，这种联合体也称为智能体(Agent)。

§4.3 模式的匹配与合一

    模式实际上是一种表达式框架。函数定义中，等号左边的模式代表了函数作用的计算结果与参数形式的一种关系。模式匹配即为对这种关系的检测及根据检测的结果进行相应的操作。

    模式匹配(Pattern Matching)是将一个方法调用表达式(可能已进行了部分计算)与一个模式进行比较，判断它们的结构是否一致，并把模式中的变量约束到表达式相应部分的过程。

定义4.1 当且仅当下面三条之一成立，表达式A和模式B是匹配的：

1) A = B；
2) B是变量或'_'；
3) 设A = C_a(A₁, A₂, .., A_k)，B = C_b(B₁, B₂, .., B_k)，则C_a = C_b，同时A_i和B_i(i=1,2,...,k)。

如果A，B是匹配的，则称A是B的一个实例(Instance)。

    在前面计算Fibonacci数的程序，Fib函数就使用了模式匹配。例如计算Fib(2)，Fib(2)和Fib函数的第三个模式Fib(int n)匹配，把变量n约束为2。计算等号右边的表达式时，须分别计算Fib(1)和Fib(0)，这两个表达式分别与函数的第二和第一模式匹配。

    在模式匹配的过程中，总是把模式中的变量约束成表达式的对应部分。从另一个角度，我们也可以把模式匹配的过程，看成是方法调用表达式把其参数的值单向地传输给模式。事实上，函数的调用表达式中，每个参数都是约束表达式或值表达式，在模式匹配的过程中参数变量是不允许改变的。

    在模式的合一中，变量的约束是双向的，模式中变量可以被约束为调用表达式的对应参数，同时调用表达式中的自由变量将被约束为模式中对应的内容。

    Fuxi语言的合一算法：

1. 自由变量可以同任何项合一。合一后该自由变量被约束为与之合一的项。

2. 常量可与自身或自由变量合一。

3. 若两个复合项的函词相同，且参数个数相同，则这两个复合项可以合一的条件是：所有参数能够对应合一，自由变量要用合一后的约束值来替换。
   在模式的合一过程中，系统完成以下操作：
   a) 对变量赋值（传递参数）。
   b) 借助模式匹配机制，存取数据结构。
   c) 对等式进行验证。

// Query of Distance
import fuxi.*
public active class QueryApplication: Applet
{
    road( "Tampa", "Houston", 200 )#
    road( "Gordon", "Tampa", 300 )#
    road( "Houston", "Gordon", 100 )#
    road( "Houston", "Kansas City", 120 )#
    road( "Gordon", "Kansas City", 130 )#

    route( String city1, String city2, int distance ) <-  road( city1, city2, distance )
    route( String city1, String city2, int distance ) <-  road( city2, city1, distance )
    route( String city1, String city2, int distance ) <- 
        let
        {
             String city3
             int X, Y
        } 
        in 
        {
             route( city1, city3, X )
             route( city3, city2, Y )
             distance := X + Y
        } 
    public Activate( ) =
        let
        {
             String city1
             String city2
             int distance
        }
        in
        {
             Console.Print( "City 1:" )
             city1 := Console.Read( 16 )
             Console.Println( "" )
             Console.Print( "City 2:" )
             city2 := Console.Read( 16 )
             Console.Println( "" )

             if( route( city1, city2, distance ) )
                  Console.Println( "The distance between " + city1 + " and " + city2 + " is: "  +  distance )
             else
                  Console.Println( "I do not know the distance." )