Определение на языке 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. В этих языках аргумент оценивается только тогда, когда требуется узнать его значение. Это позволяет создавать программы, которые выполнялись бы бесконечное время, если бы в них использовались «жадные» вычисления.
Например, можно определить бесконечный список чисел, которые никогда не будут вычислены все, а будут вычисляться только элементы, значения которых необходимы в конкретный момент.
Главная страница сайта, посвященного языку Miranda, который был создан Дэвидом Тёрнером.
После создания императивных и функциональных языков возникла еще одна альтернативная парадигма. Эта третья парадигма получила название логического программирования. Логическое программирование отличается тем, что при создании таких языков программирования используется формальная логика, которая изучает принципы доказательств и формирования корректных умозаключений. Ее не следует путать с математической логикой, которая используется в информатике.
В императивном и функциональном программировании программа понимается как функция, которая выдает результат на основе заданных входных значений. В императивных языках программа — это последовательность команд, определяющих порядок чтения карточек с входными данными и записывающих выходные данные на других карточках после выполнения необходимых вычислений. В логических языках программы реализуют отношения. С помощью множества правил, называемых дизъюнктами Хорна, программист указывает, какие факты являются истинными, а пользователь может сформировать запрос к программе для оценки истинности некоторого отношения. Вычисления основаны на принципе резолюции Робинсона и заключаются в оценке того, истинно или ложно заданное пользователем отношение, либо в указании случаев, когда это отношение является истинным.