Элементы чисто аппликативных языков программирования

Особый класс языков программирования (ЯП) образуют так называемые аппликативные,

или функциональные, ЯП. Они называются так потому, что для них центральным элементом языка является применение функций.

Так как представление алгоритма с помощью редукционной системы (системы подстановки термов) для многих постановок задач было бы весьма ненаглядным, охотнее применяют формальную нотацию (язык программирования), для которой можно дать общую редукционную систему, которая реализуется в ЭВМ и тем самым позволяет выполнять программу. В этом случае пишут термы ("программы") над сигнатурой (элементами ЯП), для которой имеется в распоряжении общий алгоритм вычислений ("интерпретатор"). Тем самым каждая программа (каждый терм ЯП) представляет определенным образом снова алгоритм. Таким образом, над заданной вычислительной структурой можно определять дальнейшие функции через алгоритмы.

Существует два дополняющих семантических взгляда на ЯП. По первому из них ЯП можно понимать, как возможность формулировать над заданной вычислительной структурой алгоритмического базиса новые выражения и функции. Это дает возможность программисту работать чисто функционально. Впрочем, элементы ЯП выбирают так, что имеются в распоряжении алгоритмы (например, путем замены термов), которые предпринимают вычисление значений выражений, формулируемых в языке. На ЭВМ выполнение аппликативной программы осуществляется, как правило, не с помощью СПТ, а путем выполнения на ЭВМ специальной программы, называемой интерпретатором.

Функциональная программа состоит, как правило, из объявлений некоторого количества функций и задания выражения, которое образуется с помощью этих функций. Выполнение программы состоит в развертывании (вычислении) заданного выражения.

Пример (функция факториала). Математически факториал может быть специфицирован следующим образом: факториал есть отображение !: N>N в постфиксной записи (точка показывает позицию аргумента.). Имеют место равенства:

О! = 1,

(n+1)! = (n+1) * (n!).

Существует единственная фикция (факториал), которая удовлетворяет этим равенствам, т.е. эти равенства однозначно определяют функцию. Таким образом, факториал однозначно описывается с помощью равенств. К аналогичному определению факториала приводит сведение обоих равенств в одно прямое различение случаев:

           1,                  если n=0,

n! =

           n*((n-1)!),    если n>0.

В языке программирования (ЯП) Паскаль это записывается аналогичным образом (с fac(n)=n!):

function fac (n: integer): integer;

begin if n = 0   then fac := 1



else fac := n * fac(n - 1)

еnd;

В ЯП Модула-2 это соглашение о функции читается следующим образом:

PROCEDURE fac (n: CARDINAL): CARDINAL;

BEGIN IF n=0 THEN RETURN 1

ELSE RETURN n * fac(n - 1)

END

END fac

Из этого примера видно, как может быть введена функция, связанная с символом функции fac. При этом предполагается ряд заданных "примитивных" символов функции и операций. В примере факториала таковыми являются сравнение = (точнее, сравнение на нуль = 0), умножение * и вычитание -. Особое место занимает разветвление (различие случаев) if-then-else-fi. Оно рассматривается не как (нестрогая) функция, а как элемент аппликативного языка.

В аппликативных, или функциональных, языках центральным элементом языка является применение функции и соответственно понятие функции. Программа в значительной мере состоит из определений ряда функций и их использования в термах. Термы, которые содержат только символы операций из заданной вычислительной структуры (из алгоритмического базиса), называются примитивными термами. Термы, которые содержат также языковые элементы аппликативного ЯП, называются выражениями.

Так, в вышеприведенном примере терм вида

mult (1, ... , mult (n – 1, n) ...)

представляет примитивный терм, а терм вида

fac (n)

представляет (непримитивное) выражение.


Содержание раздела

---

---