Наконец-то появился увлекательный и практичный способ изучать теорию вычислений и проектирование языков программирования!
В этой книге теоретическая информатика излагается в хорошо знакомом вам контексте, что поможет оценить, почему ее идеи важны и как они
отражаются на том, чем программист изо дня в день занимается на работе.
Вместо математической нотации или незнакомого академичного языка
программирования типа Haskell или Lisp в этой книге для объяснения
формальной семантики, теории автоматов и функционального программирования вкупе с лямбда-исчислением применяется язык Ruby, сведенный
к минимуму.
Издание предназначено для программистов любой квалификации, знакомых хотя бы с одним из современных языков, но не имеющих формальной подготовки в информатике.
-
Для кого предназначена эта книга
Это книга для программистов, интересующихся языками программирования и теорией вычислений, в особенности для тех, у кого нет формальной подготовки в области математики или информатики.
Если вам интересно расширить кругозор, познакомившись с разделами информатики, в которых изучаются программы, языки и машины, но пугает математический формализм, часто сопутствующий изложению этих тем, то эта книга для вас.
Вместо сложной нотации мы будем использовать код для объяснения теоретических идей, превратив их тем самым в интерактивные инструменты, с которыми вы можете экспериментировать в удобном для себя темпе.
Предполагается, что вы знаете хотя бы один современный язык программирования, например: Ruby, Python, JavaScript, Java или C#.
Все примеры написаны на Ruby, но если вы знакомы с любым другим языком, то все равно сможете понять код.
Однако эта книга не является руководством ни по правильному написанию программ на Ruby, ни по объектно-ориентированному проектированию.
Я стремился, чтобы код был кратким и ясным, но необязательно удобным для сопровождения; задача состояла в том, чтобы с помощью Ruby объяснить информатику, а не наоборот.
Это также не учебник и не энциклопедия, поэтому вместо формальных рассуждений и строгих доказательств я попытаюсь раскрыть некоторые интересные идеи и побудить вас к более углубленному изучению.
Author(s): Стюарт Том
Publisher: ДМК Пресс
Year: 2014
Language: Russian
Pages: 385
City: Москва
Tags: Программирование
Предисловие....................................................................... 10
Для кого предназначена эта книга ........................................... 10
Графические выделения .......................................................... 10
О примерах кода ..................................................................... 11
Как с нами связаться ............................................................... 11
Благодарности ........................................................................ 12
Глава 1. Все, что нужно знать о Ruby............................. 14
Интерактивная оболочка Ruby ................................................. 14
Значения ................................................................................. 15
Простые данные ................................................................. 15
Структуры данных ................................................................... 16
Процедуры .............................................................................. 17
Поток управления .................................................................... 18
Объекты и методы ................................................................... 18
Классы и модули ..................................................................... 20
Прочее .................................................................................... 21
Локальные переменные и присваивание............................. 22
Строковая интерполяция .................................................... 22
Инспектирование объектов................................................. 22
Печать строк ....................................................................... 23
Методы с переменным числом аргументов ......................... 23
Блоки .................................................................................. 24
Модуль Enumerable ............................................................. 25
Класс Struct ........................................................................ 26
Партизанское латание ........................................................ 27
Определение констант........................................................ 28
Удаление констант .............................................................. 28
Часть I. ПРОГРАММЫ И МАШИНЫ ................................. 30
Глава 2. Семантика программ......................................... 32
В чем смысл слова «смысл»? ................................................... 33
Синтаксис ............................................................................... 35
Операционная семантика ........................................................ 36
Семантика мелких шагов ......................................................... 37
Выражения ......................................................................... 39
Предложения ...................................................................... 50
Корректность ...................................................................... 60
Приложения ........................................................................ 61
Семантика крупных шагов ....................................................... 62
Выражения ......................................................................... 63
Предложения ...................................................................... 65
Приложения ........................................................................ 68
Денотационная семантика ...................................................... 70
Выражения ......................................................................... 71
Предложения ...................................................................... 75
Сравнение способов определения семантики .................... 76
Приложения ........................................................................ 77
Формальная семантика на практике ........................................ 79
Формализм ........................................................................ 79
Поиск смысла .......................................................................... 80
Альтернативы ..................................................................... 81
Реализация синтаксических анализаторов .............................. 82
Глава 3. Простейшие компьютеры ................................ 88
Детерминированные конечные автоматы ................................ 88
Состояния, правила и входной поток .................................. 89
Вывод ................................................................................. 90
Детерминированность ........................................................ 91
Моделирование .................................................................. 92
Недетерминированные конечные автоматы ............................ 96
Недетерминированность .................................................... 96
Свободные переходы........................................................ 104
Регулярные выражения ......................................................... 108
Синтаксис ......................................................................... 109
Семантика ........................................................................ 112
Синтаксический анализ .................................................... 122
Эквивалентность ................................................................... 124
Минимизация ДКА ............................................................ 134
Глава 4. Кое-что помощнее ........................................... 136
Детерминированные автоматы с магазинной памятью .......... 140
Память .............................................................................. 140
Правила ............................................................................ 142
Детерминированность ...................................................... 144
Моделирование ................................................................ 145
Недетерминированные автоматы с магазинной памятью ...... 152
Моделирование ................................................................ 156
Неэквивалентность ........................................................... 159
Разбор с помощью автоматов с магазинной памятью ............ 160
Лексический анализ ......................................................... 161
Синтаксический анализ .................................................... 163
Применение на практике .................................................. 168
Насколько мощнее? .............................................................. 169
Глава 5. Окончательная машина .................................. 172
Детерминированные машины Тьюринга ................................ 172
Память .............................................................................. 173
Правила ............................................................................ 176
Детерминированность ...................................................... 180
Моделирование ................................................................ 180
Недетерминированные машины Тьюринга ............................ 187
Максимальная мощность ...................................................... 188
Внутренняя память ........................................................... 189
Подпрограммы ................................................................. 192
Несколько лент ................................................................. 194
Многомерная лента .......................................................... 195
Машины общего назначения ................................................. 196
Кодирование .................................................................... 198
Моделирование ................................................................ 200
Часть II. ВЫЧИСЛЕНИЯ И ВЫЧИСЛИМОСТЬ .............. 201
Глава 6. Программирование на пустом месте .......... 203
Имитация лямбда-исчисления .............................................. 204
Работа с процедурами ...................................................... 205
Задача .............................................................................. 207
Числа ................................................................................ 209
Булевы значения ............................................................... 213
Предикаты ........................................................................ 217
Пары ................................................................................. 218
Операции над числами ..................................................... 219
Списки .............................................................................. 228
Строки .............................................................................. 231
Решение ........................................................................... 234
Более сложные приемы программирования ..................... 238
Реализация лямбда-исчисления ........................................... 245
Синтаксис ......................................................................... 245
Семантика ........................................................................ 247
Синтаксический разбор .................................................... 253
Глава 7. Универсальность повсюду ............................. 256
Лямбда-исчисление .............................................................. 257
Частично рекурсивные функции ............................................ 260
SKI-исчисление ..................................................................... 266
Iota ........................................................................................ 276
Таг-системы .......................................................................... 280
Циклические таг-системы ..................................................... 289
Игра «Жизнь» Конвея ............................................................. 300
Правило 110 .......................................................................... 303
Вольфрамова 2,3 машина Тьюринга ...................................... 307
Глава 8. Невозможные программы.............................. 308
Факты как они есть ................................................................ 309
Универсальные системы могут выполнять алгоритмы ....... 309
Программы могут замещать машины Тьюринга ................ 313
Код – это данные .............................................................. 314
Универсальные системы могут зацикливаться .................. 316
Программы могут ссылаться сами на себя ........................ 323
Разрешимость ....................................................................... 329
Проблема остановки ............................................................. 331
Построение анализатора остановки ................................. 331
Это никогда работать не будет .......................................... 334
Другие неразрешимые проблемы ......................................... 339
Печальные следствия ............................................................ 342
Почему так происходит? ........................................................ 345
Жизнь в условиях невычислимости ....................................... 346
Глава 9. Программирование в игрушечной
стране................................................................................. 349
Абстрактная интерпретация .................................................. 350
Планирование маршрута .................................................. 351
Абстракция: умножение знаков ......................................... 352
Аппроксимация и безопасность: сложение знаков ............ 356
Статическая семантика ......................................................... 361
Реализация ....................................................................... 363
Достоинства и ограничения .............................................. 371
Приложения .......................................................................... 374
Послесловие ..................................................................... 376
Предметный указатель................................................... 378
