Языки программирования

Кризис оснований математики

В основу современного программирования легли несколько математических работ, написанных в 20–30-х годах XX века. Наша профессия возникла как побочный эффект битвы математиков за математику.

Битва эта началась в конце XIX века, когда разные части математики удалось свести в единую систему. С помощью теории множеств учёные обосновали и алгебру, и геометрию, и исчисление предикатов.

Недолгую идилию разрушил Бертран Рассел. Он сформулировал парадокс, доказавший противоречивость теории множеств. И, поскольку из неё следует даже элементарная арифметика, перед математиками встал вопрос, не противоречива ли и вся математика?

Парадокс Рассела

Предположим, у нас есть множество всех множеств, которые не являются собственными элементами. Является ли это множество собственным элементом?

Если да, то оно не может входить в множество всех множеств, которые не являются собственными элементами, и, таким образом, не является собственным элементом.

Если нет, то оно входит в множество всех множеств, которые не являются собственными элементами, и, таким образом, является собственным элементом.

Формулировка выглядит шутливой, однако именно парадокс Рассела привёл к кризису оснований математики.

Причина парадокса в том, что классическая (наивная) теория множеств не слишком формально определяет множества всех множеств и множества, которые являются собственными элементами. Математики, в том числе и Рассел, предложили несколько способов решения проблемы, и, в конце концов, теория устояла.

Однако новый неожиданный вопрос так и остался без ответа: как доказать непротиворечивость математики?

Непротиворечивость

Стоит ли вообще городить огород? Так ли плоха противоречивость? И, кстати, что это такое?

Противоречивость это свойство теории. Теорию называют противоречивой, если в ней истинны и утверждение, и его отрицание. Математически это можно записать как (p & ¬p) ⇒ q. Из утверждения p и его отрицания ¬p следует утверждение q. По закону исключения третьего (p & ¬p) всегда false, так что мы можем записать false ⇒ q.

По правилам импликации из ложной посылки могут следовать как истинные, так и ложные следствия. Если q оказалось неправдой, мы ничего не можем сказать о посылке. С другой стороны, в непротиворечивой теории, если предсказание q — ложно, значит, ложью является и посылка.

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

За доказательство непротиворечивости взялся предводитель математиков Давид Гильберт. Он формализовал понятия теории и доказательства, и предложил исследовать их математическими средствами.

Учёным удалось формально описать элементарную логику, логику предикатов, арифметику и теорию множеств. Каждую из этих них можно представить, как расширение предыдущей.

Какие вопросы стоят перед авторами теории?

Достаточно ли у нас аксиом для того чтобы вывести все важные теоремы? Полон ли набор аксиом?
Нет ли среди аксиом таких, которые дублируют друг друга? Независимы ли аксиомы?
Не противоречат ли правила вывода друг другу? Непротиворечива ли теория?
Какова сложность теории? Можно ли предложить способ поиска доказательств? Если нет, можно ли разрешить вопрос, является теорема доказумой, или нет?

Для самой простой из теорий — исчисления высказываний — можно доказать и полноту, и непротиворечивость. Алгоритм разрешения в элементарной логике также существует. Например, если мы хотим доказать закон контрапозиции (x ⇒ y) ⇒ (¬y ⇒ ¬x), нам достаточно построить таблицу истинности:

x	y	u = x ⇒ y	v = ¬y ⇒ ¬x	u ⇒ v
0	0	1	1	1
0	1	1	1	1
1	0	0	0	1
1	1	1	1	1

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

Следующая по сложности теория — исчисление предикатов — также полна и непротиворечива, как и арифметика с операцией сложения.

А вот арифметика со сложением и умножением уже принципиально неполна, независимо от количества аксиом. Неполны и все теории, которые включают арифметику, например, теория множеств.

Это положение доказал Курт Гёдель. Его первая теорема о неполноте гласит, что любая формальная теория, не менее сложная, чем арифметика, либо полна, либо непротиворечива. Вторая теорема утверждает, что средствами арифметики нельзя доказать её собственную непротиворечивость.

Следует ли из этого, что мы доказали противоречивость арифметики? Нет. Ученик Гильберта немецкий математик Генцен, доказал непротиворечивость арифметики, применив более мощную теорию. Но её непротиворечивость также требовала обоснования. В полном соответствии с теоремами Гёделя, надеждам на обоснование математики не суждено было сбыться.

Но, если математики проиграли сражение за полноту и непротиворечивость, может быть они могли выиграть на поле разрешения?

Проблема разрешения

Как мы помним, в исчеслении высказываний существует разрешаюшая процедура для определения истинности теорем. Чтобы узнать, верна ли теорема, мы строим таблицу истинности и изучаем столбец результата. Жизнь математиков сильно упростилась бы, умей они определять истинность теорем во всех системах.

Уже известный нам Давид Гильберт сформулировал проблему разрешения — найти разрешающую процедуру для систем сложнее логики.

Проблема разрешения (нем. Entscheidungsproblem, произносится ɛntˈʃʌɪdʊŋsˌpɹɒbləm) важна тем, что вводит понятие процедуры или алгоритма. Чтобы разобраться с ней, американский математик Алонзо Чёрч применил разработанное им лябда-исчисление.

Лямбда-исчисление

Чёрч исследовал природу функций, и формализовал такие понятия, как функция, параметр, применение функции и связывание переменной.

Что можно сделать с помощью таких несложных конструкций? Чёрчу удалось представить в виде λ-функций логику и арифметику натуральных чисел. Поищите в сети булеаны Чёрча и нумералы Чёрча, это очень интересно, но выходит за рамки нашей статьи.

Вычислимыми считаются функции, которые можно представить в виде λ-выражения, например, сложение.

Вычислима ли разрешающая процедура для логики предикатов? В своей работе Чёрч доказал, что нет. Следовательно, проблема разрешения не может быть решена ни для неё, ни для более сложных систем.

С другой стороны, некоторые функции вполне себе λ-определимы, и, следовательно, у нас есть способ их вычисления.

Через несколько месяцев после Чёрча неразрешимость Entscheidungsproblem доказал английский математик Алан Тьюринг, использовав умозрительную конструкцию, которая сейчас называется машиной Тьюринга.

Машина Тьюринга

Машина похожа на обычную печатную машинку. Вместо листа бумаги у неё бесконечные бумажные ленты с печатающими устройствами — каретками.

Машина умеет выполнять команды: напечать символ, стереть символ, сдвинуть каретку вправо или влево. В «программе» Тьюринга все команды пронумерованы, и каждая инструкция завершается указанием, какую команду выполнять следующей. Есть в машине и условные команды, которые выполняеются, только если напротив каретки находится нужный символ.

Что такое вычислимость по Тьюрингу? Возьмём машину из трёх лент и на первых двух лентах запишем два числа в унарной системе счисления. Единицу обозначим символом X, двойку — символами XX в двух соседних клетках, тройку — XXX, и так далее. Последнюю ленту оставим пустой.

Сможем ли мы составить программу, которая напечатает на третьей ленте сумму чисел с первых двух лент? Если нам это удастся, то сложение вычислимо по Тьюрингу.

Тьюринг доказал, что нельзя составить разрешающую процедуру для арифметики, как программу для его машины. Так как его работа появилась позже работы Чёрча, он сравнил два доказательства. Оказалось, что с помощью λ-исчисления и машины Тьюринга можно вычислять одни и те же функции. Как сказал бы математик, классы вычислимых функций совпадают. Для программиста это означает, что любую функциональную программу, можно написать на императивном языке, а любую императивную — на функциональном.

Тьюринг-полные языки программирования

Если λ-исчисление и машина Тьюринга эквиваленты, означает ли это, что экивалентны все известные модели вычисления? Нет.

Языки, не менее мощные, чем машина Тьюрига, называются полными по Тьюрингу. Существуют и неполные языки, например, регулярные выражения. Предположим, мы хотим написать программу, которая проверяет правильность арифметической формулы. Одним из правил для проверки будет парность скобок. В регулярных выражениях не существует способа проверить, что количество левых скобок равно количеству правых, кроме как явно перечислить все случаи:

ε | (ε) | ((ε)) | (((ε))) | …

Для бесконечной формулы нам потребуется написать бесконечное регулярное выражение, в то время как контекство-свободная грамматика позволяет обойтись короткой программой:

ε ::= (ε)

Если говорить об эквивалентности, то регулярные выражения совпадают с конечными автоматами, а контекстно-свободные грамматики — со стековой машиной (конечный автомат с одним стеком).

Но и стековая машина не является Тьюринг-полной. Предположим, мы считаем правильными такие строки:

αβγ
ααββγγ
αααβββγγγ
α…αβ…βγ…γ
 ᵐ  ᵐ  ᵐ

Количество символов α, β и γ должно совпадать. Стековая машина, в отличие от привычных языков программирования, не позволяет распознавать такое множество строк. Но стоит добавить к ней второй стек, как она становится эквивалентна машине Тьюринга.

На практике, от языков программирования не требуется быть Тьюринг-полными. Например, один из самых популярных — C — не является полным из-за адресной арифметики. Указатель в C может быть преобразован к машинному целому числу, а это означает, что память C-машины потенциально ограничена. В то же самое время, в Java и C# указатель это просто указатель, стандарты языков не накладывают ограничений на его размер. Используя потенциально бесконечную структуру данных однонаправленный список, мы можем описать объект любого размера. А вот массивы в Java и C# имеют целочисленный размер, поэтому не могут являться основой для Тьюринг-полной программы.

Мы можем делать выводы об языке программирования, зная, является ли он Тьюринг-полным. Скажем, классический SQL не поддерживает рекурсию, поэтому не позволяет извлекать иерархические данные произвольной вложенности. С другой стороны, SQL с поддержкой обобщённых табличных выражений (common table expressions) — позволяет.

Препроцессор C не реализует циклы, поэтому с его помощью нельзя вычислять числа Фибоначчи на этапе компиляции. А с помьщью Тьюринг-полных шаблонов C++ — можно.

Модели вычисления играют важную роль, если в расчёт принимаются временная сложность алгоритма и простота его реализации. Примитивные вычислители проще в разработке и быстрее. Именно поэтому для создания компиляторов в UNIX используют две программы: Lex и Yacc. Первая умеет расознавать лексемы, и по сложности соответствует конечному автомату. Вторая разбирает бесконечно вложенные выражения и соответствует стековой машине. Мы могли бы ограничиться одной программой Yacc, поскольку она умеет то же, что и Lex. Но раз стековая машина работает медленнее, компилятор, сделанный только на Yacc, тоже окажется медленнее.

Программисты знают, как иногда мучительны медленные компиляторы.

От теории к практике

«Всё это конечно интересно» — скажут ползучие прагматики, — «но как это можно применить практически»? Действительно, Чёрч и Тьюринг доказали, что разрешающая процедура не может быть придумана даже для арифметики. Как с этим фактом связаны компьютеры и программирование?

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

Если подходить строго, мы должны доказывать корректность каждого придуманного алгоритма также, как это делал Алонзо Чёрч. На практике такие доказательства можно встретить в научных статьях, а популярные издания их опускают.

Первые языки программирования

Историю языков программирования можно разложить в простую схему, которая, как и все простые схемы, будет неверной. Например, можно сказать, что первая веха в становлении программирования — период с 45-го по 55-й год. Удобно, что числа круглые.

На самом деле, писать первые программы начали чуть раньше 45-го года, в 43-м. Средством общения с компьютером были машинные коды. Язык ассемблера появился в 49-м году. Веха закончилась созданием первого высокоуровневого языка программирования Fortran в 54-м году.

«Веха 43–54» выглядит совершенно некругло. И год окончания не совсем корректен — на языке ассемблера массово писали даже в 80-х, так что появление Fortran, если и изменило ситуацию, то не сразу, и не быстро. Поэтому говорить мы будем не о вехах, а о тенденциях.

Архитектура первых компьютеров была основана на модели Тьюринга. Собрать машину из электронных компонентов того времени оказалось проще, чем λ-вычислитель. Аналогом ленты в компьютере служит оперативная память. Она состоит из ячеек, куда можно записать число из небольшого диапазона, или, как сказали бы математики, символ из ограниченного алфавита.

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

Архитектура фон Неймана

В одной и той же памяти хранится как данные, так и команды.

Память компьютера пронумерована, номер или адрес ячейки позволяет процессору прочитать или изменить содержимое ячейки.

Процессор интерпретирует программу, как набор команд в оперативной памяти. Он выполняет их последовательно, пока не встретит команду перехода.

Вся информация кодируется в двоичной системе.

Машинный код — это программа в том виде, как её видит процессор, то есть набор двоичных слов, каждое из которых либо код команды, либо её параметры. Такая программа императивна, поскольку содержит набор инструкций (указаний, императивов), которые машине следует выполнить. Разработка программ в чистом машинном коде требует внимания и скурпулёзности, и считается делом крайне трудоёмким. Существует легенда, что один из основателей компании Microsoft — Пол Аллен — вносил изменения в машинный код по дороге на важную встречу. Ошибись он в одной цифре, и компании Microsoft могло бы не быть.

Очевидно, программистам требовались средства для упрощения работы, и первым шагом на этом пути стал язык Ассемблера. Важная терминологияеская тонкость заключается в том, что Ассемблер — это программа, переводящая мнемоники в машинный код. Будучи настоящим программистом, нельзя говорить «написал программу на Ассемблере» — только «на языке Ассемблера».

В языке Ассемблера все машинные команды кодируются простыми словами, зачастую даже сокращениями: MOV (move), DIV (divide), XCHG (exchange) и даже JNE (jump if not equal). Кроме того, Ассемблер во время трансляции самостоятельно вычисляет относительные адреса меток и процедур и избавляет от этой работы программиста. В результате, мы можем осуществлять переход на именованную метку или вызывать именованную процедуру.

Чтобы вы почувствовали вкус языка Ассемблера, приведу код программы для виртуальной машины LLVM, которая печатает первые двадцать чисел Фибоначчи.

@format = private constant [3 x i8] c"%d\0A"

define i32 @main() {
entry:
  %a = alloca i32, align 4
  store i32 0, i32* %a
  %b = alloca i32, align 4
  store i32 1, i32* %b

  %i = alloca i32, align 4
  store i32 0, i32* %i

  br label %l1

l1:
  %0 = load i32* %a, align 4

  %1 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([3 x i8]* @format, i32 0, i32 0), i32 %0)

  %2 = load i32* %b, align 4
  %3 = add i32 %0, %2
  store i32 %3, i32* %a
  store i32 %0, i32* %b

  %4 = load i32* %i, align 4
  %5 = add i32 %4, 1
  store i32 %5, i32* %i

  %6 = icmp eq i32 %5, 20
  br i1 %6, label %l2, label %l1
  
l2:
  ret i32 0
}

declare i32 @printf(i8*, ...)

Не вдаваясь в детали, можно заметить, что программист делает много работы низкого уровня: самостоятельно распределяет локальную память процедуры, кодирует вычисления, организует цикл с помощью инструкций IF и GO TO. Для печати чисел программа вызывает функцию printf системной библиотеки. На самом деле это старая добрая функция printf из C:

printf("%d\n", a);

Функция возвращает целое число — количество напечатанных символов. Результат работы printf обычно игнорируется в C, но в языке Ассемблера мы не можем просто так его отбросить: мы явно сохраняем результат в регистре, а потом его не используем.

На языке Ассемблера сложно записывать математические выражения, такие как SQRT(X + Y * 38.7). Проблему перевода выражений в машинный код решил Fortran, само название которого означает Formula Translator. Также там появился оператор цикла DO, который не имеет аналога в машинном коде. Он собирается из примитивов IF и GO TO, и является, по сути, синтаксическим сахаром. Через 15 лет (почти через 15) он позволил сформулировать принципы структурного программирования.

Наконец, Fortran стандартизировал вызов процедур. Программируя на машинном языке, мы можем вызывать подпрограммы, самостоятельно организуя передачу параметров и возврат значений через регистры, стек, кучу и глобальную память. Даже в пределах одной программы допустимо произвольным образом смешивать разные способы вызова. Однако появление компилятора привело к необходимости формализовать соглашение о вызовах. И если разные компиляторы следуют одному соглашению, можно стыковать подпрограммы, написанные на разных языках. Благодаря этому, код на Fortran до сих пор легко подключить к проектам, написанным на C, C++ и даже Java.

Не смотря на то, что Fortran является императивным языком, запись математических выражений на нём функциональна. Увидев формулу A * B + A * C, мы не можем предсказать, в каком порядке будут вычисляться слагаемые: сначала A * B или сначала A * C. Истинно императивной записью выражений является постфиксная форма, которая обязывает программиста думать о порядке выполнения операций: A B * A C * +. При такой записи, как видим, разночтений нет.

Напечатаем первые двадцать чисел Фибоначчи на Fortran.

program fibonacci
  integer a, b, t
  a = 0
  b = 1
   
  do n = 1,20
    print *, a
    t = b
    b = a + b
    a = t
  end do
end program fibonacci

Как и в программе на языке Ассемблера, мы используем аккумуляторы a и b, которые содержат два последних вычисленных значения. Временная переменная t позволят обменивать значения a и b перед тем, как вычислить следующее число. Благордаря этому обмену мы сохраняем семантику «a — предпоследнее вычисленное число, а b — последнее».

Некоторые программисты любят «оптимизировать» код, чтобы отказаться от переменной t,

    print *, a
    b = a + b
    a = b - a

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

Результат работы:

Функциональное программирование

LISP, дедушка современных функциональных языков, был разработан в 1958-м году, всего через четыре года после Fortran. Его название расшифровывается как list processor, то есть обработчик списков.

Очевидно, список — одно из фундаментальных понятий в языке. Речь идёт о связном однонаправленном списке, где вставка в начало выполняется за время O(1), то есть очень быстро. Эта структура данных настолько удобна, что перекочевала во все современные функциональные языки.

Данные и программы записываются одинаково, в виде S-выражений, знаменитой скобочной записи:

(cons 1 '(2 3 4))

Здесь мы вызываем функцию cons с параметрами 1 и (2 3 4), то есть одиночным числом и списком чисел. Функция возвращает список, где первый параметр вставлен в начало второго, то есть (1 2 3 4).

Такая запись подчёркивает факт, что процедуры ничем не отличаются от данных: функция может принимать функцию в качестве параметра и возвращать её как результат. Единственное отличие заключается в том, что функцию можно вызвать или, как говорят математики, применить.

Напечатаем первые двадцать чисел Фибоначчи на Scheme, современном наследнике языка LISP:

(define (fibonacci-series n)
 (define (build-fibonacci m a b l)
  (cond
   ( (= m 0) l)
   (else (build-fibonacci (- m 1) (+ a b) a (cons a l)))))
  (build-fibonacci n 0 1 '()))

(print (fibonacci-series 20))

Результат:

(4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0)

Здесь мы написали функцию fibonacci-series, которая принимает в качестве параметра размер последовательности. В результате её вызова мы получаем список чисел Фибоначчи указанной длины.

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

Структурное программирование

Конец эпохи Fortran принято связывать со знаменитой статьёй Дейкстры «О вреде оператора GOTO», которая вышла в 1968г. В данном случае слова «конец эпохи» следует воспринимать условно, поскольку в математических программах Fortran активно используется до сих пор.

В действительности основы структурного подхода были заложены за десять лет до статьи, при разработке языка программирования Algol-58. Если Fortran следовал той же парадигме программирования, что и машинный код — программа это просто набор команд, то в Algol ввели понятие структуры. Программа разбивалась на блоки, которые могли быть вложенными. Плюс такого разбиения заключается в снижении количества ошибок. При программировании на Fortran бичом программистов был так называемый спагетти-код, в котором сложно отследить порядок выполнения, поскольку управление постоянно скачет то вверх, то вниз.

Дейкстра предложил несколько принципов, которые позволили читать программу сверху вниз. Он доказал, что любой спагетти-код можно преобразовать в последовательность одиночных операторов, циклов и ветвлений. В современных языках оператор GO TO практически не встречается, вместо него используют более предсказуемые операторы break, continue и return.

Структура программ позволила разрабатывать средства для работы с потоком управления. Компилятор может предупредить программиста о недостежимом коде, потому что знает, что в определённые места программы управление никогда не попадёт.

Посмотрим, как задача с числами Фибоначчи решается в языке структурного программирования Pascal:

program FibonacciSeries;

var
  A, B, T: integer;
  I: integer;

begin
  A := 0;
  B := 1;
  
  for I := 1 to 20 do
  begin
    WriteLn(A);
    T := A;
    A := A + B;
    B := T;
  end;
end.

Здесь мы видим блоки, ограниченные ключевыми словами begin и end, а также отступы, которые подчёркивают структуру. В Pascal количество пробелов в начале строки незначимо, но хорошей практикой считается «сдвигать» вложенные блоки вправо. В языке Python отказались от ключевых слов и фигурных скобок, сделав пробелы значимыми:

import itertools
    
def fib():
  a, b = 0, 1
  while True:
    yield a
    a, b = b, a + b

for f in itertools.islice(fib(), 20):
  print(f)

Типы данных

Fortran умел работать с переменными двух типов: целые числа и действительные числа. Переменные можно было не описывать, поскольку в языке применялись правила автоматического объявления типа. Переменные, чьё имя начиналось на I, J, K, L, M и N считались целыми, все прочие — действительными.

При разработке Algol объявление переменных вместе с указанием их типа сделали явным. В программе необходимо указать название каждой используемой переменной и её тип. Такое дублирование позволяет исключить большой класс ошибок-опечаток уже на стадии компиляции. Объявления переменных обычно связывают со статической типизацией, но это не идентичные концепции. Например в языке Perl есть режим strict vars, при котором каждая переменная должна быть объявлена, а вот значение и тип ей можно назначить значительно позже.

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

type
  IntegerBinaryNode = record
    Value: Integer;
    Left: ^IntegerBinaryNode;
    Right: ^IntegerBinaryNode;
  end;

  StringBinaryNode = record
    Value: String;
    Left: ^StringBinaryNode;
    Right: ^StringBinaryNode;
  end;

В 1963 году Джон Алан Робинсон придумал принцип резолюции, позволявший эффективно доказывать формализованные теоремы. Этот принцип нашёл своё применение при реализации языков Prolog и ML. Создавая ML, его авторы, Хиндли и Милнер, опирались на типизированное λ-исчисление. Они разработали алгоритм автоматического выведения типов, который сейчас называется их именами. Алгоритм, используя данные об операциях, где участвуют переменные, накладывает ограничения на множество типов, до тех пор, пока не унифицирует их. Унификация в данном контексте означает приведение к одному, то есть в результате работы алгоритма каждая переменная получает свой тип. Важной особенностью алгоритма является умение работать с параметризованными типами, то есть в отличии от Pascal, в ML можно описать бинарное дерево чего-нибудь, а не конкретно строк или чисел.

Вот пример такого дерева на языке OCaml:

type 'a binary_tree = Leaf
                    | Node of 'a * 'a binary_tree * 'a binary_tree

Элементами бинарного дерева являются либо концевые участки (Leaf), либо узлы, содержащие элемент любого типа (обозначен 'a) и два поддерева.

Знатоки C++, Java и C# немедленно опознают в этом коде обобщённое программирование (generic programming), и не зря. В функциональной парадигме такой подход называется параметрическим полиморфизмом. Полиморфная функция, которая определяет, содержит ли дерево элемент, выглядит так:

let rec contains x t = match t with
                     | Leaf -> false
                     | Node (y, left, right) -> x = y || contains x left || contains x right

Благодаря выведению типов мы можем не указывать тип параметров x и t, а также тип возвращаемого значения. Сейчас алгоритмы выведения типов активно используются даже в императивных языках, например, в C++, Java и C#.

Логическое программирование

Логическое программирование ассоциируется с языком программирования Prolog, который разработали в начале 1970-х годов во Франции. Программа на нём состоит из фактов, правил вывода и запросов. Описав факты и правила вывода, программист строит запросы, на которые среда автоматически отвечает.

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

Часть функций Prolog сумели взять на себя реляционные базы, где факты могут быть представлены данными в связанных таблицах, а правила вывода присутствуют в запросах в виде условий. В качестве примера рассмотрим, как в SQL могут быть решены задачи поиска в генеалогическом дереве, в которых традиционно хорош Prolog.

CREATE TABLE People
(
  Id INT NOT NULL,
  Name VARCHAR(100) NOT NULL,
  Gender VARCHAR(7) NOT NULL
)

INSERT INTO People (Id, Name, Gender)
VALUES (1, 'Вася', 'мальчик'),
       (2, 'Даша', 'девочка'),
       (3, 'Петя', 'мальчик'),
       (4, 'Мила', 'девочка'),
       (5, 'Коля', 'мальчик'),
       (6, 'Вера', 'девочка'),
       (7, 'Жора', 'мальчик'),
       (8, 'Зина', 'девочка')

CREATE TABLE Parents
(
  ParentId INT NOT NULL,
  ChildId INT NOT NULL
)

INSERT INTO Parents (ParentId, ChildId)
VALUES (1, 3),
       (1, 4),
       (1, 5),
       (2, 3),
       (2, 4),
       (2, 5),
       (3, 6),
       (3, 7),
       (4, 8)

На основании изложеных фактов давайте узнаем, кто мама Зины?

SELECT People.*
  FROM People
  JOIN Parents ON Parents.ParentId = People.Id
 WHERE Parents.ChildId = 8 AND People.Gender = 'девочка'

А вот дедушка Зины:

SELECT People.*
  FROM People
  JOIN Parents AS Parents1 ON Parents1.ParentId = People.Id
  JOIN Parents AS Parents2 ON Parents2.ParentId = Parent1.ChildId
 WHERE Parents2.ChildId = 8 AND People.Gender = 'мальчик'

В нашей базе только один дедушка, но если мы добавим ещё одного, запрос покажет обоих.

В современном SQL присутствуют средства для построения рекурсивных запросов, а именно обобщённые табличные выражения, с помощью которых мы можем вычислить и двадцать первых чисел Фибоначчи:

WITH FibonacciSeries AS
(
  SELECT 1 AS Number, 0 AS A, 1 AS B
   UNION ALL
  SELECT Number + 1 AS Number, (A + B) AS A, A AS B
    FROM FibonacciSeries
   WHERE Number < 20
)
SELECT Number, A FROM FibonacciSeries

Результат:

Объектно-ориентированное програмирование

Simula 67 считается первым объекто-ориентированным языком программирования. Как видно из названия, она появилась 1967-м году. Через несколько лет, в 1972-м Алан Кей разработал первую версию SmallTalk.

Не смотря на общие идеи, Simula и SmallTalk не сильно похожи друг на друга. Их различие до сих пор служит поводом для религиозных интернет-споров о чистоте объектно-ориентированного подхода.

В SmallTalk всё является объектом, включая числа и логические значения. Объекты пересылают друг другу сообщения, а не вызывают методы. Оператор IF в SmallTalk отсутсвует. Логические операторы, такие как a < 3 возвращают экземляр типа False либо типа True, каждый из которых является наследником Boolean. Они умеют обрабатывать сообщения ifTrue и ifFalse, которые принимают код для исполнения в параметре. ifTrue из True исполняет свой код, а ifFalse — нет. У объекта False сообщения работают наоборот.

Вместо оператора IF в SmallTalk пишут:

a < 3
  ifTrue: ['less than 3' displayNl].

Обратите внимание, что displayNl — это соообщение, которое посылается объекту-строке 'less than 3' чтобы строка сама себя напечатала.

Первые двадцать чисел Фибоначчи на SmallTalk вычисляются так:

a := 0.
b := 1.
20 timesRepeat: [
   a displayNl.
   t := a.
   a := b + a.
   b := t.
].

Программы на Simula 67 гораздо больше похожи на то, что мы видим в C++ и Java. Язык является надмножеством Algol 60 и даже назывался «Algol с классами».

Одним из основных отличий SmallTalk и Simula является способ реализации полиморфизма. Так как в Simula типизация статическая, полиморфизм классов реализуется с помощью наследования, а конкретно — с помощью переопределяемых методов, которые могут отличаться у класса-предка и класса-наследника. В Simula эти методы назвали виртуальными.

Полиморфизм

В 1967-м году Кристофер Стрэчи вводит понятие полиморфизма. Он рассматривает его сначала на примере арифметических оператов, таких как «+» и «×», а затем — на примере произвольных функций.

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

Но Стрэчи полиморфными называет именно функции.

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

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

В Simula для того, чтобы реализовать новую версию полиморфного метода, мы должны создать класс-наследник и переопределить метод. В SmallTalk достаточно добавить обработку сообщения с нужным именем и набором параметров. Это всё равно ad hoc полиморфизм, поскольку мы пишем ещё одну реализацию функции, но он не требует наследования.

Такой подход называется утиной типизацией и встречается во всех динамических объектно-ориентированных языках.

Из мира SmallTalk в современные объектно-ориентированные языки пришли модульные тесты и шаблоны проектирования. Не смотря на свои сильные стороны, SmallTalk не стал массовым языком разработки из-за проблем с производительностью. Помимо динамической типизации здесь сыграли роль сборка мусора и байткод.

В 1983г. молодой программист Бьярн Страустрап, размышляя об эффективной реализации полиморфизма, придумал элегантный способ переопределения методов через таблицу виртуальных функций. Сейчас он применяется в большинстве объектно-ориентированных языков. C++ оказался очень производительным, а благодаря совместимости с C он позволял использовать тысячи готовых библиотек. Именно он проложил дорогу объектно-ориентированному программированию в массы на рубеже 80-90-х годов.

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

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

А наследование позволяет повторно использовать код.

В 96-м году Джеймс Гослинг выпустил первую версию языка Java. К тому времени C++ накопил немало проблем. Язык был, с одной стороны, низкоуровневым, совместимым с C, а с другой — объектно-ориентированным. Он поддерживал и адресную арифметику, и множественное наследование, и побитовые операции, и обобщённое программирование, и, кажется, всё, что могло оказаться актуальным. 3-е издание книги Страустрапа по C++, вышедшей в 1997-м году содержало 1040 страниц. Учить и применять язык стало сложно.

В то же время программы на C++ росли в размерах, как и количество объектов, и связей между ними. Программисты всё чаще допускали ошибки при работе с памятью: они могли освободить объект, который был кому-то нужен; или не освобождать объект, не нужный никому.

C++, как и C, имел проблемы с переносимостью. С одной стороны, исходный код программ действительно можно было собирать на множестве платформ, с другой — из-за того, что языки были низкоуровневыми — это достигалось с помощью сложной условной компиляции. Загляните в код открытых библиотек общего назначения и оцените количество директив #ifdef _WIN32 или #elif defined(__GNUC__) && __GNUC >= 4.

Java решила эти проблемы. Гослинг почистил C++ и язык стал проще. Для переносимого выполнения программ была разработана виртуальная машина, а для управления памятью — сборщик мусора. В 80-м байткод и сборкщик помешали популярности SmallTalk, но в 96-м оказалось, что программы на Java работают с приемлимой скоростью и содержат меньше ошибок. Пользователь не замечает разницы между откликом 0,1с и 0,2с.

Через несколько лет стал очевиден ещё один плюс языка. В Java отказались от препроцессора, из-за которого программы на C/C++ с трудом поддаются анализу. В Java код анализировать проще, поэтому в IDE стали встраивать подсказки ввода и средства рефакторинга. Сейчас программисты на Java активно используют IDE, что сильно повышает производительность труда.

Java-вариант вычисления чисел Фибоначчи:

public class FibonacciSeries {
  public static void main(String []args) {
    int[] fibonacciSeries = new int[20];
    fibonacciSeries[0] = 0;
    fibonacciSeries[1] = 1;
    
    for (int i = 2; i < fibonacciSeries.length; i++)
      fibonacciSeries[i] = fibonacciSeries[i - 1] + fibonacciSeries[i - 2];
        
    System.out.println(java.util.Arrays.toString(fibonacciSeries));
  }
}

Результат:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Параллельное программирование

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

Основы параллельного программирования были заложены ещё в начале 60-х — синхронизирующую конструкцию семафор Эдгар Дейкстра описал в 1962-м году. Практики монтировали несколько процессоров в одну схему, предоставляли им доступ к одним и тем же периферийным устройствам и заставляли работать. Именно в то время появились понятия блокировка ресурса, взаимная блокировка, состояние гонки.

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

В середине 70-х годов к решению задачи распараллеливания подтянулись теоретики. Хоар, Милнер, и другие исследователи предложили несколько моделей описания распределённых вычислений. Одной из самых известных является модель акторов.

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

Самым известным языком, реализующим модель акторов, стал Erlang. Он активно используется при разработке высоконагруженных систем. Ниже приведена параллельная программа печати первых двадцать чисел Фибоначчи. Каждое число вычисляет и печатает отдельный процесс.

-module(fibonacci).
-export([fibonacci_series/3]).

fibonacci_series(1, A, _) ->
  io:format("~B~n", [A]),
  self();

fibonacci_series(N, A, B) ->
  Pid = spawn(fibonacci, fibonacci_series, [N - 1, A + B, A]),
  io:format("~B~n", [A]),
  Pid.

Что дальше?

Рубеж 70-80-х оказался роковым для индустрии. Средние и малые ЭВМ были достаточно мощными, располагали оперативной памятью в один-два мегабайта, и выполняли до ста тысяч операций в секунду. На таких компьютерах можно было выполнять байткод, собирать мусор, даже динамически определять тип переменных.

К сожалению, стоили они немало, поэтому массовый рынок с распростёртыми объятиями принял дешёвые персональные компьютеры. Которые вернули индустрию на годы назад — в ситуацию, когда битва шла за каждый такт и за каждый байт.

Smalltalk для первых Atari, Apple и IBM PC оказался слишком требовательным, как и функциональные языки программирования. Одним из важных ограничений функциональной экосистемы является практическая обязательность сборщика мусора. Другим — неизменяемость данных и необходимость их копирования. Всё это было неподъёмно для маломощных персональных компьютеров начала 80-х.

И, не смотря на последующий рост мощности, низкие накладные расходы языков, играли важнейшую роль на протяжении практически двух десятилетий.

Но Java всё изменила.

В ней был байткод, и программы на существующем железе работали с достаточной скоростью. Программисты Sun внедрили в виртуальную машину JIT-компилятор, что также ускорило выполнение. Сборка мусора не играет существенного значения в большинстве настольных приложений, да и для многих серверных тоже. Веб-сервер, отвечающий на запрос с другого конца света за две секунды, может потратить на сборку мусора полсекунды. Да и размер оперативной памяти вырос настолько, что сама необходимость в сборке возникает гораздо реже.

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

В C++ с 1997-го года есть средства обобщённого программирования. Это тот самый параметрический полиморфизм типов, разработанный авторами ML. Чуть позже эти средства пришли в Java и C# с похожим синтаксисом. C#, начиная с 2008-го года, поддерживает полноценные лямбда-функции, деревья выражений, язык запросов LINQ и вывод типов.

Сейчас уже никого не удивить разработкой на Scala и Clojure в экосистеме Java, на F# и Nemerle — в мире .NET. Для виртуальной машины LLVM разработано несколько комплияторов, в частности, для языка Scheme.

Для того, чтобы предположить, куда будут развиваться языки программирования дальше, посмотрим на тенденции в области развития аппаратного обеспечения:

Объём оперативной памяти всё ещё растёт в соотвествии с законом Мура. По прогнозам, к 2021-му году плашка 64Гб будет стоить меньше ста долларов. Никого не удивишь оперативной памятью объёмом 100–200Гб, в том числе на мобильных устройствах.
Производительность процессоров складывается из тактовой частоты и количества ядер. Если тактовая частота расти практически перестала, то на настольных системах обычным делом стали процессоры с восьмью ядрами. Cкоро речь пойдёт на десятки.
Средства ввода: мы активно используем голосовой ввод и жесты.
Средства вывода: мониторы становятся больше и тоньше. В скором времени стоит ожидать качественного перехода, когда монитор будет, как лист ватмана. Его можно будет скрутить и носить с собой.

Для устройств с десятками гигабайт ОЗУ и десятками ядер хорошо подойдут языки с поддержкой многозадачности и сборкой мусора. Камнем преткновения становится клавиатура, как средство ввода, которая не вписывается в концепцию компьютер как лист формата А3, управляемый голосом и жестами. Казалось бы, язык программирования тоже должен стать визуальным, но мы знаем, что такие языки до сих пор не смогли занять серьёзной ниши.

Одну из причин я вижу в том, что императивный язык с трудом поддаётся визауализации. Глядя на блок-схему и на соответствующий ей код, трудно убедить себя, что блок-схема понятней.

Другое дело декларативные языки, которые хорошо представляются в графическом виде. В книге Красного Дракона (Ахо, Сети, Ульман: Компиляторы) для описания лексем используются не регулярные выражения, а диаграммы переходов. Для представления реляционных таблиц и связей схема базы данных гораздо удобнее кода на SQL. Поэтому программисты баз данных активно используются схемы сущностей-отношений в повседневной работе.

Здесь речь идёт о специализированных языках. Функциональные языки по сути своей декларативны, но остаётся вопрос: возможно ли создать визуальный функциональный язык общего назначения? Думаю, уже в ближайшие пять лет мы увидим первые языки программирования такого рода.