Cтраница 1
Удалив б-правила, мы получим чистое Я-исчисление. В нем можно выразить любые функции, несмотря на отсутствие б-правил. [1]
Правила преобразования графа, соответствующего применению примитивной функции, задаются б-правилами для этой функции. [2]
Термин б-редекс поэтому соответствует выражению, которое может быть упрощено с помощью б-правила, а р-редексом называется выражение, которое можно упростить с помощью р-редукции. Так же как в случае б-редукции, мы не будем помечать стрелку ( - -), обозначающую редукцию, символсУм Р в тех случаях, когда ясно, что упрощаемое ( под) выражение явлйется р-редексом. [3]
Мы будем опускать символ б везде, где ясно, что используемое правило редукции является б-правилом. [4]
Применения примитивных функций включают ( рекурсивную) редукцию строгих аргументов примитива и проведение затем примитивной операции в соответствии с б-правилами. [5]
Применение константной функции, однако, может быть преобразовано при наличии достаточного количества аргументов с использованием встроенных правил, которые часто называют б-правилами. Применение любой функции записывается в виде выражения для этой функции, за которым следуют выражения для ее аргументов. [6]
Определив, как находить вершину очередного редекса на каждом этапе вычислений, мы должны теперь определить преобразования графа, соответствующие редукциям подвыражений. Мы уже видели, что все редексы являются - вершинами и что каждое преобразование должно представлять либо р-ре-дукцию, либо применение б-правила. [7]
Заметим, что указатель AFT не изменяется, указывая на - вершину, к которой нужно вернуться после вычисления аргумента. Подобным образом левый указатель этой вершины по-прежнему направлен вверх по гребню в сторону вершины редекса применения примитивной функции. Однако правый указатель теперь направлен вниз по гребню. Аргумент, который необходимо вычислить следующим ( если он есть), будет определен б-правилами применяемой примитивной функции и текущим состоянием при выполнении этих правил. [8]
Заметим, что ПГ являются ациклическими, и поэтому инструкция, соответствующая вершине в ПГ, после выполнения удаляется, поскольку данные на ее входящих дугах появиться не могут. Заметим также, что набор все необходимые аргументы соответствует входам вершины ПГ, на которых наличие данных обязательно, чтобы операция этой вершины могла быть выполнена. Эти входы задаются правилами, специфическими для каждого типа инструкций. В случае инструкции типа слияние необходим первый ( управляющий) вход, а также второй ( Т) или третий ( F) в зависимости от того, имеется ли на первом входе значение true или false соответственно. В случае примитивной функции входы, на которых требуется наличие данных, соответствуют определяемым б-правилами строгим аргументам этой функции. Таким образом, в каждом случае все из необходимых элементов входного списка известны. [9]