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

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

Функциональные языки впервые были описаны Джоном Маккарти из MIT (Массачусетского технологического института), создателем термина «искусственный интеллект», в работе, опубликованной в 1960 году в журнале Communications of the ACM . Этот ежемесячный журнал выпускается американской Ассоциацией вычислительной техники (ACM) — обществом, присуждающим премию Тьюринга.

В 1958 году Маккарти изучал использование операций с упорядоченными списками в программе символьного дифференцирования. Дифференцирование — это рекурсивный процесс, поэтому Маккарти использовал рекурсивные функции. Более того, он передавал функции в качестве аргументов другим функциям. Проект по реализации задуманного им языка начался осенью того же года. Результаты были опубликованы спустя два года под названием «Рекурсивные функции над символьными выражениями и их вычисление с помощью машины. Часть I» (часть II никогда не была опубликована). Так появилась первая версия языка LISP(англ. List Processing — «обработка списков») — первого функционального языка, в котором нашло применение множество передовых идей. В описании разработанного им языка Маккарти использовал лямбда-исчисление Алонзо Чёрча.

Джон Маккарти, создатель термина «искусственный интеллект». Стэндфордский университет, 1980 год.

* * *

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

Эта система была разработана Алонзо Чёрчем и Стивеном Клини в начале 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 ), в котором не использовались переменные. Статья пробудила интерес исследователей к функциональным языкам и привела к появлению новых подобных языков.