Классика Computer Science: Структура и интерпретация компьютерных программ

Structure and Interpretation of Computer Programs (SICP) - Структура и интерпретация компьютерных программ - замечательная книга Харольда Абельсона и Джеральда Сассмана о программировании. Книга действительно является настоящей классикой Computer Science(первое издание датируется 1985 г). Фактически это учебник к вводному курсу по программированию в Массачусетском технологическом институте (MIT).

Мой обзор книги не претендует на полноту описания и, в общем, не является рецензией. Скорее это попытка обратить внимание на такую классику, как SICP, тех, кто ещё не знаком с ней. Тем биоинформатикам, которые начинают вникать в вопросы программирования эта книга задаст правильное направление развития.

 

SICP

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

Отличительной особенностью SICP является также то, что в качестве языка программирования выбран Scheme. Это диалект Lisp, в котором совсем немного базовых конструкций и совсем немного синтаксиса. Это сделано не случайно. Scheme позволяет продемонстрировать различные техники программирования, и при этом синтаксис языка не отвлекает от идеи, которую выражает код. Кроме того, выучить Scheme довольно просто в процессе прочтения книги (на самом деле Scheme, конечно, больше, чем представлено в книге). Упражнения можно выполнять и на любых других языках программирования. С решениями на Scheme и другой полезной информацией на русском языке можно ознакомиться здесь.

Кратко опишу содержание глав SICP, чтобы дать общее представление об объёме информации, который уместился в 576 страниц.

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

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

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

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

Во второй главе рассматривается построение абстракций данных. Сначала вводятся понятия конструктора и селектора для работы с составными типами данных и рассматривается пример их использования для построения процедур, работающих с рациональными числами. Далее рассматривается понятие барьера абстракций: расслоение системы на уровни, которые работают друг с другом через интерфейсы. За которым следует замечательный раздел, в котором показано, как можно данные представить в виде процедур! Ну и, конечно же, обсуждаются такие структуры данных, как пары и списки, которые являются основой для конструирования более сложных типов данных(в Lisp, диалектом которого является Scheme - пары и списки - это вообще основа основ. Не даром Lisp это акроним от List processing)

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

В главе 3 вводится изменяемое состояние и, фактически, строится объектно-ориентированная модель на классическом примере банковского счета. Далее обсуждаются методы моделирования на основе изменяемых данных, проблемы параллелизма с изменяемыми данными.

В заключение главы вводится понятие потока (Stream), который фактически является «ленивым» списком, в котором значения вычисляются не сразу, что представляет возможности для улучшения модульности программы.

Глав 4 и 5 я подробно касаться не буду, хотя там и рассмотрены интересные проблемы, но они более специфичны для Computer Science.

Глава 4 описывает построение метациклического интерпретатора языка Scheme (интерпретатор Scheme, написанный на Scheme), в том числе расширения, необходимые для реализации ленивой модели вычислений, недетерминистской модели вычислений и логического программирования. Глава 5 — вычисления на регистровых машинах и компиляцию.

PS: Второе издание книги распространяется по лицензии Creative Commons, поэтому с текстом книги можно свободно ознакомиться на официальной странице MIT Press. Русский перевод книги можно скачать здесь.

PPS: если вы все-таки решили порешать задачки из книги на Scheme, рекомендую воспользоваться Racket. Это современный диалект Scheme имеющий довольно неплохую базу библиотек, а также IDE DrRacket.

Добавить комментарий


Защитный код
Обновить