От абака к цифровой революции — страница 22 из 24

* * *

ЛЯМБДА-ИСЧИСЛЕНИЕ

Эта система была разработана Алонзо Чёрчем и Стивеном Клини в начале 1930-х годов. Ее возможности были эквивалентны возможностям машины Тьюринга, но основной принцип лямбда-исчисления был иным. С формальной точки зрения в лямбда-исчислении используются выражения и правила преобразования выражений, которые моделируют использование функций и вычислений. Рассмотрим в качестве примера определение истинности и ложности:

истина: λху. х

ложь: λху. у.

Логическая функция «И» определяется так:

И: λpq.p q р.

Чтобы найти значение выражения «истина ложь», заменим каждый член этого выражения его эквивалентом с точки зрения лямбда-исчисления:

(λpq.p q р) (λху. х) (λху. у).

Применив правила записи, получим выражение (λху. у), что, как мы уже говорили, эквивалентно значению «ложь». Числа и операции с числами определяются аналогично.

* * *

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

* * *

ПРЕФИКСНАЯ (ПОЛЬСКАЯ) НОТАЦИЯ

Математические выражения в этой нотации обозначаются символом, соответствующим операции, который располагается перед операндами. Так, выражение

(а + Ь) — (с·d)

в польской записи будет выглядеть так:

- + ab · cd.

* * *

В середине 1960-х Питер Лэндин создал новый функциональный язык ISWIM (от англ. If You See What I Mean — «если ты видишь, что я имею в виду»), в основе которого находился язык LISP и лямбда-исчисление. На основе языка ISWIM было разработано целое семейство функциональных языков (ML, FP, Miranda и другие).

В то время функциональное программирование было интересно лишь немногим исследователям. Оно начало набирать популярность в 1978 году, когда Джон Бэкус, создатель языка Фортран, опубликовал статью «Можно ли освободить программирование от стиля фон Неймана?» Бэкус критиковал традиционные языки программирования и выступал за развитие новой парадигмы, которую он назвал «функциональное программирование». В ней делался акцент на функционалы (функции, аргументами которых являются другие функции). В своей статье, за которую он был удостоен премии Тьюринга, Бэкус описал язык FP (Functional Programming), в котором не использовались переменные. Статья пробудила интерес исследователей к функциональным языкам и привела к появлению новых подобных языков.

В настоящее время существует два обширных семейства функциональных языков. Первое образовано языками, созданными на основе 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). Это означает, что все аргументы функции вычисляются перед ее использованием.

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

Например, можно определить бесконечный список чисел, которые никогда не будут вычислены все, а будут вычисляться только элементы, значения которых необходимы в конкретный момент.



Главная страница сайта, посвященного языку Miranda, который был создан Дэвидом Тёрнером.


Логическая парадигма

После создания императивных и функциональных языков возникла еще одна альтернативная парадигма. Эта третья парадигма получила название логического программирования. Логическое программирование отличается тем, что при создании таких языков программирования используется формальная логика, которая изучает принципы доказательств и формирования корректных умозаключений. Ее не следует путать с математической логикой, которая используется в информатике.

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

* * *

ДИЗЪЮНКТЫ ХОРНА

Дизъюнкты Хорна — это множество логических правил вида «если антецедент является истинным, то консеквент является истинным». Можно сказать, что дизъюнкты Хорна представляют собой логические операции импликации, содержащие множество предпосылок и единственное следствие.

Предпосылок может быть 0, 1 или более:

а1^а2 ^… ^ aN —> b.

* * *

Самым известным логическим языком является Пролог (PROLOG — от фр. PROgrammation еп LOGique). Он был разработан в 1972 году и является единственным логическим языком, широко используемым на данный момент. Первая версия была разработана под руководством Алана Колмерауэра в университете ЭксМарсель группой, работавшей над созданием искусственного интеллекта, при участии британского логика Роберта Ковальски из Эдинбургского университета. Пролог появился в результате слияния двух направлений исследований. Первое, во главе которого стоял Колмерауэр, не было напрямую связано с информатикой, а было посвящено изучению естественного языка; второе, возглавляемое Ковальски, было сосредоточено на автоматическом доказательстве теорем. На этот язык повлияли В-грамматика (нотация, использованная для описания языка Алгол-68) и язык Planner, разработанный в Стэнфордском университете. Успех Пролога был обусловлен его реализацией усилиями Дэвида Уоррена из группы Ковальски в Эдинбургском университете. Так называемая абстрактная машина Уоррена (VAM) исполняла программы со скоростью, сравнимой со скоростью исполнения программ на языке LISP.