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

• Название: Том 15. От абака к цифровой революции. Алгоритмы и вычисления
• Автор: Бизенц Торра
• Издательство: «Де Агостини»
• Жанр: Математика
• Год: 2014
• ISBN: 978-5-9774-0710-6

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

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

---

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

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

Первым языком, в котором данные и операции группировались в рамках единой сущности, был Simula I, предназначенный для решения задач симуляции. Он был разработан в Норвежском вычислительном центре под руководством математика и политика Кристена Нюгорда. Работы над первой версией языка были завершены в январе 1965 года. Следующая версия получила название Simula 67. Это был язык общего назначения, в котором были формализованы понятия объекта и класса и вводилось понятие наследования. Позднее в языке Smalltalk 80, который был создан на основе языка Simula и двух предыдущих версий (Smalltalk 72 и Smalltalk 76), понятие объекта было обобщено и объекты стали единственными сущностями, используемыми в языке. В начале 1970-х в научно-исследовательском центре Xerox Palo Alto Research Center, известном как Xerox PARC, была создана система Dynabook — персональное средство обработки информации с оконным интерфейсом, текстовыми меню, значками, то есть с полноценным графическим интерфейсом (англ. GUI — Graphical User Interface), очень похожим на современные. Dynabook был разработан американцем Аланом Кеем для обучения детей работе с компьютером. Работы были завершены в 1972 году. Программы в этой системе были написаны на языке BASIC, в них использовался механизм передачи сообщений, а также понятия класса и объекта, введенные в языке Simula.

Алан Кей получает степень почетного доктора испанского Университета Мурсии за вклад в развитие информатики. Торжественная церемония состоялась 28 января 2010 года.

Сейчас существует множество объектно-ориентированных языков программирования (Eiffel, C++ и другие), некоторые из которых являются расширенными и дополненными вариантами других языков. Так, C++ является расширенным вариантом языка С. Он был создан датским программистом Бьёрном Страуструпом и содержит классы, подобно языку Simula. Система CLOS была разработана с целью стандартизировать объектную систему языка Common LISP. Понятия объекта и наследования использовались в работах по созданию искусственного интеллекта при разработке языков для представления знаний, например KRL и KL-ONE, и языков с акторами, в частности Actl, Act2, Act3, ABCL/1 и других.

Абстракция и объекты применяются во всех языках программирования, появившихся в последние годы, как в объектно-ориентированных языках, например Java или Python, так и в процедурных, где используются объектно-ориентированные конструкции, например в языке РНР. Также появились языки, ориентированные на быструю разработку приложений, и сценарные языки. К ним относятся РНР и JavaScript, разработанные в последнее десятилетие XX века. Целью авторов этих языков было упростить и ускорить разработку программ. Разумеется, для небольших программ этого действительно удалось достичь, однако по сравнению с языками прошлого проектирование крупномасштабных программ усложнилось. Как бы то ни было, влияние объектно-ориентированных языков на разработку программ привело к появлению новых вспомогательных средств, например языков моделирования, подобных UML.

Функциональная парадигма

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

Функциональные языки впервые были описаны Джоном Маккарти из 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), в котором не использовались переменные. Статья пробудила интерес исследователей к функциональным языкам и привела к появлению новых подобных языков.

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

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