Бизенц Торра - Том 15. От абака к цифровой революции. Алгоритмы и вычисления

В настоящее время существует два обширных семейства функциональных языков. Первое образовано языками, созданными на основе LISP, второе — языками, созданными на основе ISWIM. К первому семейству принадлежат разновидности языка LISP, например Common LISP, и самостоятельные языки, например Scheme.

Ко второму семейству принадлежит язык Standard ML— результат стандартизации языков MLи Норе, созданных в Эдинбургском университете. ML в отличие от LISP является строго типизированным функциональным языком ( strongly-typed language ). Это означает, что все выражения в этом языке имеют тип, который определяется системой во время компиляции (статический тип). Кроме этого, программист может вводить новые типы, определяя абстрактные типы данных. Язык ML допускает определение модулей и общих модулей, которые называются функторами. В языке Норе, в отличие от ML, типы требуется определять явно.

* * *

ФУНКЦИОНАЛЬНЫЕ ЯЗЫКИ: ПРИМЕРЫ РЕАЛИЗАЦИИ

Ниже приведены примеры определения функции факториала на разных языках программирования. Обратите внимание на схожесть синтаксиса языков, принадлежащих к двум основным семействам функциональных языков. В языках, подобных USP( Scheme, Норе и ML ), используются переменные, определение факториала является рекурсивным и напоминает его определение на языке Java, которое приводилось несколькими страницами ранее. В языке FP, напротив, переменные не используются. В определении на языке FP используется функция iota. Эта функция возвращает список всех натуральных чисел, меньших заданного числа. К этому списку применяется конструкция / *, осуществляющая умножение его элементов. Конструкция /opрасширяет бинарную операцию, применяя ее ко всем элементам списка.

Определение на языке LISP :

(defun factorial (n) (if (= n 0) 1 (* n (factorial (- n 1)))))

Определение на языке Scheme :

(define factorial

(lambda (n)

(if (= n0) 1 (*n (factorial (-n 1))))))

Определение на языке Hope :

dec fact: num — > num;

- - - fact 0 < = 1;

- - - fact n < = n*fact(n — 1);

Определение на языке ML

fun f (0: int): int = 1

|f (n: int): int = n * f(n — 1)

Определение на языке FP :

fact =/* op iota

* * *

БЕСКОНЕЧНЫЕ СПИСКИ ЯЗЫКА HASKELL

Следующие определения двух бесконечных списков на языке Haskellпомогут вам понять разницу между «жадными» и «ленивыми» вычислениями. Эти определения являются рекурсивными, то есть используют сами себя.

Первое определение соответствует списку натуральных чисел. По индукции предполагается, что список уже определен корректно. Все элементы списка увеличиваются на единицу, таким образом, получается список 2, 3, 4…., к которому добавляется единица. В определении все элементы списка натуральных чисел увеличиваются на единицу с помощью конструкции « mар (+1) naturales ».

Второе определение соответствует списку чисел Фибоначчи. Предположим, что этот список уже определен. В определении списка чисел Фибоначчи каждому числу ставится в соответствие следующее число, затем вычисляется сумма в каждой такой паре чисел. В определении « listafibs » ставится в соответствие «хвосту» listafibs , который получается с помощью конструкции « tail listafibs ». Далее соответствующие элементы двух списков складываются с помощью конструкции « zipWith (+) ».

naturales= 1: map (+1) naturales

listafibs= 0:1: zipWith (+) listafibs (tail listafibs)

Эти определения являются корректными, так как в них используются «ленивые» вычисления. Если бы в них, как в большинстве других языков, использовались «жадные» вычисления, то компьютер обрабатывал бы эти определения бесконечно долго. Обратите внимание, что для определения натуральных чисел сначала требуется выявить бесконечный список, после чего прибавить единицу ко всем его элементам.

* * *

В языках LISP и ML используются «жадные» вычисления ( greedy evaluation ). Это означает, что все аргументы функции вычисляются перед ее использованием.

Также существуют языки, где применяются «ленивые» вычисления, в частности Haskell, Lazy ML, некоторые версии языка Норе и в особенности язык Miranda, созданный Дэвидом Тернером на основе языков KRC и SASL. В этих языках аргумент оценивается только тогда, когда требуется узнать его значение. Это позволяет создавать программы, которые выполнялись бы бесконечное время, если бы в них использовались «жадные» вычисления.