Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

• Название: ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда
• Автор: Даглас Хофштадтер
• Издательство: Издательский Дом «Бахрах-М», 2001.
• Жанр: Математика
• Год: 2001
• ISBN: ISBN 5-94648-001-4

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

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

Автор размышляет над одной из величайших тайн современной науки: каким образом человеческое мышление пытается постичь самое себя. Хофштадтер приглашает в мир человеческого духа и «думающих» машин. Это путешествие тесно связано с классическими парадоксами, с революционными открытиями математика Курта Геделя, а также с возможностями языка, математических систем, компьютерных программ и предметного мира говорить о самих себе с помощью бесконечных отражений.

Начав читать эту книгу,вы попадете в волшебные миры, отправитесь в путешествие, изобилующее увлекательными приключениями, путешествие, после которого вы по-иному взглянете на мир и на самого себя.

Переведенная на 17 языков, книга потрясла мировое интеллектуальное сообщество и сразу стала бестселлером. Теперь и русский читатель получил доступ к одной из культовых книг XX века.

---

Были изобретены также интерпретаторы. Подобно компиляторам, интерпретаторы переводят с языков высших уровней на машинный язык, но вместо того, чтобы сначала переводить все высказывания и затем выполнять машинный код, они считывают одну строчку и тут же ее выполняют. Преимущество здесь в том, что для использования интерпретатора не обязательно иметь полную программу. Программист может придумывать свою программу строчка за строчкой и проверять ее в процессе создания. Интерпретатор по сравнению с компилятором — то же, что устный переводчик по сравнению с переводчиком письменных текстов. Один из самых интересных и важных языков программирования — это ЛИСП (от английского List Processing — обработка списка), изобретенный Джоном Маккарти примерно тогда же когда был изобретен АЛГОЛ. Впоследствии ЛИСП приобрел большую популярность среди специалистов по искусственному интеллекту.

Между принципом работы интерпретаторов и компиляторов есть одно интересное различие. Компилятор берет входные данные (к примеру, законченную программу на Алголе) и производит некий результат (длинную последовательность команд на машинном языке). На этом его работа закончена и результат вводится в компьютер для обработки. Интерпретатор, напротив работает непрерывно, пока программист вводит одно за другим высказывания ЛИСПа, каждое из них немедленно выполняется. Однако это не означает что каждое высказывание сначала переводится и затем выполняется — тогда интерпретатор был бы всего лишь построчным компилятором. Вместо этого в интерпретаторе операции считки новой строчки, ее «понимания» и выполнения переплетены — они происходят одновременно.

Поясню эту идею немного подробнее. Как только новая строчка ЛИСПа вводится в интерпретатор, он пытается ее обработать. Это означает, что интерпретатор начинает действовать, и в нем выполняются некие машинные команды. Какие именно — это зависит, разумеется, от данного высказывания ЛИСПа. Внутри интерпретатора много команд типа ПЕРЕХОД, так что новая строчка ЛИСПа может заставить контроль двигаться довольно сложным путем вперед, назад, затем опять вперед и т. д. Таким образом, каждое высказывание ЛИСПа превращается в некий «маршрут» внутри интерпретатора, и следование по этому маршруту приносит нужный эффект.

Иногда бывает полезно интерпретировать высказывания ЛИСПа как некие блоки данных, которые постепенно вводятся в непрерывно действующую программу машинного языка (интерпретатор ЛИСПа). Думая об этом таким образом, вы по-иному видите отношения между программой, написанной на языке высшего уровня, и исполняющей эту программу машиной.

Самонастройка

Разумеется, компилятор, будучи программой, должен быть сам написан на каком-либо языке. Первые компиляторы были созданы на языке ассемблера вместо машинного языка; таким образом полностью использовались преимущества подъема на одну ступеньку над машинным языком. Краткое описание этих довольно сложных понятий представлено на рис. 58.

РИС. 58. Как ассемблеры, так и компиляторы — это переводчики на машинный язык. Это указано прямыми линиями. Более того, поскольку они сами являются программами, они первоначально также создаются на каком-либо языке программирования. Волнистые линии указы указывают на то, что компилятор может быть написан на языке ассемблера, а ассемблер — на машинном языке.

По мере того, как программирование становилось более изощренным, было замечено, что частично законченный компилятор может быть использован для того, чтобы компилировать собственные продолжения. Иными словами, когда создано определенное минимальное ядро компилятора, это минимальное ядро может переводить большие компиляторы на машинный язык, пока таким образом не создастся окончательный, полный компилятор. Этот процесс известен под именем «самонастройки»; он несколько напоминает достижение ребенком критического уровня владения своим родным языком, после чего его словарь и грамматическое мастерство растут как снежный ком, так как для изучения языка он может использовать сам язык.

Уровни описания работающих программ

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

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

Уровень машинного языка:

«Выполнение программы прекратилось по адресу 1110010101110111»

Уровень языка ассемблера:

«Выполнение программы прекратилось, когда она дошла до команды РАЗДЕЛИТЬ».

Уровень языка компилятора:

«Выполнение программы прекратилось в момент оценки алгебраического выражения „(А + B)/Z“».

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

Микропрограммирование и операционные системы

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

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

Рассмотрим первую телефонную систему. Александр Грэхем Белл мог позвонить своему ассистенту в соседнюю комнату: электронная передача голоса! Это сравнимо с простым компьютером без операционной системы: электронные вычисления!

Рассмотрим теперь современную телефонную систему. У вас есть выбор, с каким телефоном соединиться; к тому же, можно отвечать на многие звонки одновременно. Вы можете добавить код и соединиться с другими районами. Вы можете позвонить прямо или через оператора; так, что звонок будет оплачен вашим собеседником или по вашей кредитной карточке. Можно говорить с одним человеком или сразу с несколькими; можно «перенаправить» или проследить звонок. Существует сигнал «занято», сигнал, говорящий вам, что набранный номер не является «хорошо сформированным» и сигнал, говорящий вам, что вы набирали номер слишком долго. Вы можете установить местный коммутатор, соединяющий несколько телефонов, — и так далее, и тому подобное. Это удивительный список, если подумать, сколько возможностей он представляет, в особенности, по сравнению с былым чудом «голого» телефона. Вернемся теперь к компьютерам: сложные операционные системы выполняют примерно те же операции направления трафика и переключения уровней по отношению к пользователям и их программам. Мы можем быть практически уверены в том, что у нас в мозгу происходят некие параллельные процессы, одновременная обработка многих стимулов; решения о том, что должно выйти на первый план и на какое время; мгновенные «перерывы» из-за неожиданных событий и критических положений и так далее.