Структура и интерпретация компьютерных программ книга обзор
СИКП — не книга про языки программирования или разработку программного обеспечения, не книга по ООП, функциональному программированию или паттернам проектирования.
СИКП — книга об информатике (computer science). Восприятии компьютеров как абстрактных машин, используемых для манипулирования данными. Несмотря на то, что книга впервые опубликована в 1979, она до сих пор не потеряла свою актуальность и не потеряет в будущем. СИКП неизменно находится в топе лучших книг по обучению программированию на протяжении десятков лет.
This is one of the great classics of computer science. I bought my first copy 15 years ago, and I still don’t feel I have learned everything the book has to teach. — Paul Graham.
Стоит ли её читать? Однозначно стоит всем разработчикам на любых языках программирования с любым опытом. СИКП — достаточно сложная книга, поэтому появилось руководство, которое вы прямо сейчас читаете.
Очень краткое содержание
Абстракция с помощью функций
- Элементы программ
- Выражения
- Вычислительные стратегии
- Подстановочная модель вычислений
- Функции и процессы порождаемые ими
- Линейная рекурсия и итерация
- Древовидная рекурсия
- Функции высшего порядка
- Функции как аргументы
- Функции как обобщения
- Функции как возвращаемые значения
Абстракция с помощью данных
- Введение в абстракцию данных
- Барьеры абстракции
- Что такое данные?
- Иерархические данные и свойство замыкания
- Представление последовательностей
- Иерархические структуры
- Последовательности как стандартные интерфейсы
- Символьные данные
- Цитирование
- Множественные представления абстрактных данных
- Тегирование данных
- Программирование управляемое данными. Аддитивность.
Модульность, Объекты и Состояние
- Присваивание и локальное состояние
- Преимущества присваивания
- Недостатки присваивания
- Модель с окружениями
- Правила вычисления
- Применение
- Фреймы как репозитории локального состояния
- Моделирование с изменяемыми данными
- Изменяемый список
- Представление очереди
- Представление таблиц
- Многозадачность
- Потоки
Метаязыковые абстракции
Вычисление с помощью регистровых машин
Рекомендации
Первое, что нужно понимать: СИКП — не просто книга. Это университетский курс, записанный в виде книги. Он сложный и объёмный, его бесполезно проходить без практики. Практику придумывать не придётся. После каждой главы есть блок задач, которые авторы просят выполнить. Некоторые из них сугубо математические (просят что-то доказать), либо подразумевают хорошую математическую базу. Их можно и даже нужно пропускать, иначе вы можете очень быстро потерять мотивацию.
Сколько читать
СИКП условно можно разделить на две части. В первую часть входят главы 1, 2 и 3. Во вторую — 4 и 5. Разница в том, что во вторую часть входят главы, копающие очень глубоко, и пройти сквозь них может только по-настоящему увлеченный человек. По этой причине Хекслет рекомендует поставить себе планкой прохождение первых трех глав. Остальное можно с легкостью отложить на потом.
Для примеров и практики в книге используется язык Scheme (Ским), созданный авторами курса. Это один из диалектов семейства Lisp. Как и полагается любому Lisp-языку, Scheme имеет примитивный синтаксис, который можно изучить буквально за несколько часов. Он очень необычен для тех, кто имел дело только с широко распространенными языками, но обладает рядом серьезных достоинств, о которых говорится в книге.
Его выбор, в качестве основного языка для курса обоснован тем, что Scheme позволяет сосредоточиться на сути вещей вместо синтаксиса, увидеть чистые концепции в первозданном виде. Scheme как и любой Лисп, обладает невероятно высокой выразительностью благодаря тому, что в языке всё есть выражение, а инструкции отсутствуют вообще.
Вторая причина — гомоиконность. Свойство языков, в которых данные и код — одно и тоже. Этот тезис сложно понять на словах, его нужно прочувствовать на практике. Есть еще и третья причина — макросы, но они в книге не используются.
Сам язык Scheme, это в первую очередь стандарт языка плюс разные реализации этого стандарта. На данный момент один из самых развитых – и продолжающих развиваться – потомков Scheme, это язык Racket. Хекслет рекомендует проходить СИКП именно на Racket. Специально для этого гайда мы подготовили репозиторий, который можно использовать как основу для кода. В репозиторий стоит заглянуть хотя бы для того, чтобы узнать, как настроить Racket на совместимость именно с тем стандартом Scheme, который используется для примеров кода в книге: немногие существующие реализации Scheme позволяют воссоздать “то самое” окружение, к счастью, Racket может! Не забудьте правильно настроить редактор: Lisp языки относятся к тем языкам, для которых нужна поддержка со стороны редактора для комфортной работы.
Оформление
На Гитхабе можно найти множество репозиториев, в которых лежат решения задач из СИКП на всех возможных языках программирования. Мы настоятельно рекомендуем поступать также: создать репозиторий в своем аккаунте и выкладывать в него все свои решения. Идеально, если каждое решение будет сопровождаться тестами. Такой подход хорош не только тем, что вы дополнительно прокачиваетесь в git и получаете дополнительную мотивацию, но и тем, что у вас появляется код, который можно показать при поиске работы. Более того, велика вероятность, что собеседовать вас будет человек, знающий про СИКП. Это добавит очков в карму и даст возможность продуктивно пообщаться.
Я считаю, что разработка ПО в значительной степени заключается в программировании на псевдокоде. Если ты представил псевдокод, то перевести его на Python, C, что угодно — не проблема. Основная сложность заключается вот в этой концептуальной деятельности, а не в кодировании. Нужно знать, как подходить к тем или иным вопросам. Модульность, абстракция. Гибкость, надёжность, простота. Шаблоны проектирования. Юнит-тестирование. Ю ноу.
Есть на свете курс «Структура и Интерпретация Компьютерных Программ» (далее СИКП), который позиционируется как введение в Computer Science и ранее использовался в MIT для обучения первокурсников. Два года назад я с удовольствием одолел курс лекций по нему и взялся за книгу.
Сначала расскажу о хорошем. Текст повествует о штуках весьма далёких от моей ежедневной работы и позволил мне по-новому взглянуть на программирование. Функциональщина — это целый мир, живущий по своим законам. Язык Лисп очень отличается от привычного мне языка Си бешеной гибкостью за счёт динамической типизации, автоматического управления памятью, возможности переопределения чего угодно во время выполнения. У меня сформировалась более разностороннее представление о том, как в принципе можно решать разные задачи. Говоря шахматным языком, я сильно пополнил свой репертуар домашних заготовок, которые пригождаются в работе (пусть и не каждый день). Упражнения заставляли мой мозг работать (временами очень интенсивно), переосмысливать и систематизировать ранее полученные знания. В общем и целом изучение СИКП сделало меня более хорошим разработчиком, расширило мой кругозор. Уверен, я стал смотреть на разные вещи более системным и зрелым взглядом.
Книга постоянно толкала на размышления, за это ей низкий поклон. Я глубоко осознал вещи, которые вроде бы всем известны, но которые поэтому все ленятся упоминать. Например, что всё ПО сначала делается простым, а потом неизбежно усложняется ради повышения производительности. Пользователю-то плевать, сколько строк исходного кода внутри, а вот скорость имеет значение.
А что там насчёт конкретных эффектов для работы? Я стал лучше видеть недочёты во время code review (в первую очередь, своего же кода). Полюбил маленькие функции, желательно как можно более общего вида. Стал практиковать аккуратное и уместное использование макросов — иногда на Си можно осторожно сделать что-то не по правилам, и от этого все только победят. Опыт, полученный при решении упражнений из книги, помог мне в некоторых задачах по работе.
Но это одна сторона медали. Другая заключается в том, что подход этого курса к обучению можно выразить английским фразеологизмом «sink or swim». Перед тобой стоит перекладина, рядом с ней задание: подтянуться 10 раз. В принципе, этого достаточно для выполнения задачи, но нельзя сказать, что такой подход приятен. Я бы сказал, он весьма выматывает! Тебя бросают в бой полуподготовленного, и часть материала ты познаёшь не на объяснениях, а на своих ошибках. Наверное, это допустимый способ обучения высокомотивированных людей, но меня-лентяя он порядком выжал. Я с трудом терпел его на протяжении 3 глав из 5 (порой я делал паузы на несколько месяцев!), сделал упражнения в них от начала и до конца, но кажется, моё терпение исчерпано.
Например, в книге нет ни слова о том, как организовать свой рабочий процесс. Нет даже приблизительного рассмотрения таких понятий, как «отладка» (она здесь специфическая), «IDE» (они здесь специфические), «юнит-тесты», «разбиение на файлы для повторного использования». Имеются фрагменты, где разрабатывается некая сложная система, которая будет целиком готова лишь к концу главы, а задания появляются после каждого пункта текста. Т.е. строго говоря, прочитав до страницы N, ты в ряде случаев не можешь решить задачу с этой страницы, не утащив код с последующих страниц. Код нужно тащить аккуратно, ибо в примечаниях могут обсуждаться неочевидные тонкости, а порой какой-то код приводится в качестве примера неработающей идеи. Это раздражает! Да, это прям как в реальной жизни — надо самому доопределять задачу, искать что-то в интернетах, но блин… Этожучебник! Я наедаюсь непростыми задачами на работе, и может, авторам стоило более педантично подойти к тексту? Ладно я, профессиональный погромист с быстрым доступом в интернеты, а как было первокурснику MIT в восьмидесятых? Уверен, несладко…
Подчеркну главные плюсы книги: она позволяет получить личный опыт, набить свои шишки, подумать над сложными проблемами в общем виде. С ними непосредственно связаны минусы: она сложная и зачастую даёт тебе мало подсказок для понимания чего-то. Например, если ты имеешь какой-то боевой опыт, то знаешь, что код без юнит-тестов нельзя назвать решением, но книга тебе об этом не скажет. Надо самому до этого дойти! А как ты думал? Ну или вру, книга об этом скажет, но максимально садистским способом. У тебя будет следующее задание, опирающееся на предыдущее (такое там сплошь и рядом). Если у тебя раньше заработал один тестовый кейс и ты решил «Отлично, едем дальше!», то за поворотом тебя ждёт счастливая отладка решений сразу двух заданий. Наверное, когда это произойдёт несколько раз, ты поймёшь, что делаешь что-то не так. Главное, чтобы в такие моменты ты не бросал курс, а разбирался, тогда всё будет хорошо!
Ещё одна раздражающая черта текста: задания (опять же, как и в реальной жизни) порой недостаточно хорошо определены. Я на днях делал упражнение, за полчаса набросал решение, стал перечитывать формулировку задачи. Оказалось, что если рассуждать педантично, то я выполнил его на 95%, затратив примерно 40% усилий. Большинство чуваков, с которыми я сверялся, сделали так же. Один сделал полноценно, но использовал хак из другого интерпретатора Лиспа. Я огорчился и плюнул, потеряв мотивацию продолжать в ближайшее время. Ещё раз проговорю суть проблемы: есть задания, в которых всё решается просто и логично, но только если не быть к себе строгим. Так и в реальной жизни, я понимаю, но у меня были другие ожидания от учебника. Когда делаешь упражнение в свободное время и сам себя проверяешь, то хочется решить проблему на 100%, а не «достаточно хорошо для текущей итерации».
Проблема с юнит-тестами вообще-то того же рода. Иногда нужно неслабо запотеть и подумать, чтобы просто внедрить их в систему. Я-то знаю, что без них никуда, но более простые ребята просто набрасывают решения без проверки и идут дальше! Чем ты строже, внимательнее, опытнее, тем сложнее для тебя становятся задания. Иногда просто в разы! Это демотивирует, потому что тут, в отличие от работы, за это не хвалят и не платят, а итеративный подход плохо применим. Знания и умения, полезные в реальной жизни, больно бьют по рукам при решении студенческих задачек!
Стоит сказать, что в книге много математики. Решая упражнения, я понял красоту и силу этой науки, но порой мне было тяжело именно из-за этих специфических вопросов, лишь косвенно касающихся решаемых задач. Просто авторы решили что-то показать на примере скажем интегрирования, вот ты и вспоминай да ботай!
В общем и целом, я не жалею, что вписался в эту авантюру, она была для меня полезной. Тем не менее, другим людям я рекомендую поискать что-то получше. Например, на основе СИКП с учётом его ошибок (так говорят, я не проверял) недавно был сделан курс «How to Design Programs». Полагаю, стоило и мне на него позариться, но время уже не отмотаешь.
Недавно успешно завалил собеседование на вакансию фронтэнд разработчик. Меня программист сначала загрузил реализацией map и reduce, а потом вообще вопросы по функциональщине стал задавать и я поплыл. Тем не менее кодер который проводил собеседование дал "хороший" совет "Прочти структуру и интерпретацию компьютерных программ" если поймёшь хотя бы 50 страниц - поговорим снова". Скачал, бегло просмотрел и сейчас в недоумении - каким боком нужна вся эта математика и алгоритмы во фронтенде? Зачем это это надо при разработке сайтов? В чём польза?
ps: может программист решил постебаться таким образом?
Простой 2 комментария
Вообще нужно-то это везде, другое дело что может быть они искали целеустремлённого перспективного специалиста, которому в итоге можно предложить обучение в какой-то важной для них сфере с последующим переходом в другую должность или совмещением.
А может просто отделяли зёрна от плевел, то есть действительно passionate разработчиков от "войти-в-айти"-шников.
Если собеседуешься на джуна и зп не сильно выше рынка - то собеседующий тешит свое ЧСВ
Если мидл+, то стоит прочитать
SICP учит думать по-программерски. Учит находить решения в программерском мире. Есть огромная разница между программистом знающим как использовать фреймворк1, фреймворк2, . фреймворкN и другим программистом, который может даже и не знать как использовать эти фреймворки, но сможет отличить что вон тот код очень похож на работу за O(n) , а вон тот вроде как за O(1) и сможет сделать более правильный выбор. Грубо говоря есть некий базис, который одному позволяет создавать решения более стабильные, более эффективные, а другому из-за не хватки приходится городить костыли.
К примеру общеизвестная задачка на программирование "банерокрутилка". Когда имеется банер1, банер2, . банерN и нужно вывести "псевдослучайно" каждый банер по одному разу. Один программер может применить массив и указвать в нем какие номера он уже выводил, а другой применит математику и при этом решение будет одно проходным и не потребует выделения массива. И таких задачек в программировании хватает!
Даниил Демидко, Кратко не получится ответить. Дам лишь "пинок" куда смотреть ;) Регистр сдвига с линейной обратной связью. Модификация LFSR как раз и есть то, что нужно сделать
Дмитрий, Вы сами не можете кратко объяснить реализацию, а ведь код потом нужно будет сопровождать и не всегда тому кто его написал.
Iruber, Гуглится подобное на Ура! ;) А умение использовать гугл весьма важный навык современного программера, а иначе GSDD: Google-StackOverflow-Driven development не освоить!
Эта же "банерокрутилка" используется и в вирусах. Чтобы скрыть цикл расшифровки. Ведь с точки зрения вируса ему наплевать в какой последовательности участок кода рас-xor-ивается лишь бы расксорился. Вот к примеру по ключевой фразе в гугл "pseudo random index decryption" быстро находит pdf : Advanced Polymorphic Techniques и в нем п с помощью Ctrl+F ищем слово "lfsr".
Туже банерокрутилку много где можно использовать к примеру в парсере сайтов, чтобы не циклом двигаться по сайту запрашивая очередную ссылку, а как бы случайно и это + несколько техник повышает живучесть парсера
от меня +
c SICP по сути как с Кнутом - все советуют, но никто не читает) в 99.9% случаев для промышленной, коммерческой разработки это не нужно
Если что, в той же статье указывается и причина: "бизнес хочет по бырику, но для этого нужно не думать, а методом тыка говном и соплями, посрав на качество и эффективность, связать десяток библиотек. Наш курс для таких задач непригоден."
batyrmastyr, разве библиотеки это плохо ? И решение бизнес задач вы тоже считаете чем то плохим ?
Если курс не пригоден для решения бизнес задач, то значит он не стоит денег. А образование в MIT стоит дорого и от него ожидают практической пользы, а не обучение функциональному программированию на scheme или lisp.
asd111, плохо когда бизнес получает ответ «это невозможно» потому, что самая подходящая библиотека на нужном языке не умеет делать точно так, только с перламутровыми пуговицами, а недопрограммист даже не думает, что можно залезть в её исходники и немного подкрутить. Ну или написать самому, если на это нужны не миллионы строк кода.
batyrmastyr, Бизнес редко получает ответ "невозможно". Обычно ответ "Это будет стоить столько то" и цена либо устраивает либо нет. Поэтому больше всего собственного софта разрабатывают богатые компании, а мелкие довольствуются типовыми решениями.
Многие инженерные специальности опираются на математику, как на фундамент. Одним из базовых навыков для программиста (который инженер, а не специально обученная обезьяна) является умение оценить вычислительную сложность программы и написать эффективный алгоритм. Из-за медлительности яваскрипта и операций с DOM, а также разбухания объёма клиентского кода вопрос эффективности стоит очень остро.
Вместо sicp можно взять любую другую книгу развивающую мышление + дающую понимание «сколько эта операция будет стоит» - хоть «Искусство программирования» Кнута, хоть «Алгоритмы и структуры данных» Вирта, хоть «Структуры данных и алгоритмы» Ахо, Ульмана и Хопкрофта, хоть кого другого.
Вот несколько примеров, что случается если не оценивать сложность, а то и вовсе «сперва кодить, потом думать»:
24-ядерный CPU, а я не могу сдвинуть курсор,
Один разработчик чуть не «сломал» пакетный менеджер NPM,
Facebook и Google выпустили Yarn, новый менеджер п. (npm писали клинические дебилы - грузить десятки раз один и тот же пакет!),
Ещё на новый год многие любят повесить на сайт падающий снег и почти у всех он отжирает целое ядро процессора, в каждой открытой вкладке, Карл! 8 вкладок и у тебя висит даже Core i7. Но если настольные компы просто подвисают, то ноутбуки и телефоны ещё и аккумы разряжают со страшной скоростью.
Слипшиеся слова. Английское слово bugs переведено как "блохи" и т.д. Попытки издательства испортить содержание книги не удачны и бестолковы. Эту книгу должен прочитать и "проработать" каждый уважающий себя программист несмотря на корявый перевод.
Книга подлетела для начала обучения программированию. Эта книга не учит вас синтаксису какого-либо конкретного языка, она учит программированию как таковому. Здесь используется язык Scheme (диалект Lisp), он не сложный, простой и понятный. Советую использовать интерпретатор Racket. Читать полностью
Очень качественный материал и достаточно редкий подход к изучению программирования. Перевод не без ляпов, но на очень достойном уровне (хотя как мне известно это не заслуга издательства. Обложка, листа - зачет.
Единственный заметный и обидный недостаток - это верстка, съеденные пробелы. Причем в электронном оригинале этого нет. Косяк издательства
Отличная книга, то, что нужно для понимания программирования. Во время изучения совсем по другому начинаешь смотреть на программирование в целом.
Книга фундаментальна Написана понятным языком Описывает великолепие языка Lisp (диалект Scheme) Всячески полезна и для начинающих, и для профессионалов
Цена разве что. Книга есть в свободном доступе в сети, тк она в целом бесплатна. Но иметь такую книгу лучше в печатке.
Если честно, не смог осилить - пытался по-началу выполнять задания, но потом, в процессе углубления, начал забивать. Как легкое чтиво и ознакомление с темой не рекомендую. Только для тех кто хочет разобраться и не жалеет на это времени. По каечству книги - твердый переплет, белые плотные листы, шрифт мелковат.
я хотела эту книгу на английском, в оригинале, приходится заказывать с амазона с их драконовскими ценами на доставку
Книга обязательно к прочтению. Не знаю ест ли сейчас в MIT курс по этой книги или нет. Но именно такие курсы читают во всех топовых институтах мира, где готовят специалистов IT. Перевод опечатки… ну да не очень. Но книга топовая! Очень рекомендую к изучению в самом начале своего пути в мир программирования.
Проблема со слитными словами, описанная в предыдущих отзывах, не исчезла, но не выражена в той крайней степени, в какой её выставляют. При осознанном чтении книга не должна оставить никаких впечатлений, кроме положительных - способствуют этому крайне доступный для восприятия перевод и приятная разметка текста. Не буду говорить за сторону квалифицированных. Читать полностью
Слипшиеся слова. Английское слово bugs переведено как "блохи" и т.д. Попытки издательства испортить содержание книги не удачны и бестолковы. Эту книгу должен прочитать и "проработать" каждый уважающий себя программист несмотря на корявый перевод.
Книга подлетела для начала обучения программированию. Эта книга не учит вас синтаксису какого-либо конкретного языка, она учит программированию как таковому. Здесь используется язык Scheme (диалект Lisp), он не сложный, простой и понятный. Советую использовать интерпретатор Racket. Читать полностью
Очень качественный материал и достаточно редкий подход к изучению программирования. Перевод не без ляпов, но на очень достойном уровне (хотя как мне известно это не заслуга издательства. Обложка, листа - зачет.
Единственный заметный и обидный недостаток - это верстка, съеденные пробелы. Причем в электронном оригинале этого нет. Косяк издательства
Отличная книга, то, что нужно для понимания программирования. Во время изучения совсем по другому начинаешь смотреть на программирование в целом.
Книга фундаментальна Написана понятным языком Описывает великолепие языка Lisp (диалект Scheme) Всячески полезна и для начинающих, и для профессионалов
Цена разве что. Книга есть в свободном доступе в сети, тк она в целом бесплатна. Но иметь такую книгу лучше в печатке.
Если честно, не смог осилить - пытался по-началу выполнять задания, но потом, в процессе углубления, начал забивать. Как легкое чтиво и ознакомление с темой не рекомендую. Только для тех кто хочет разобраться и не жалеет на это времени. По каечству книги - твердый переплет, белые плотные листы, шрифт мелковат.
я хотела эту книгу на английском, в оригинале, приходится заказывать с амазона с их драконовскими ценами на доставку
Книга обязательно к прочтению. Не знаю ест ли сейчас в MIT курс по этой книги или нет. Но именно такие курсы читают во всех топовых институтах мира, где готовят специалистов IT. Перевод опечатки… ну да не очень. Но книга топовая! Очень рекомендую к изучению в самом начале своего пути в мир программирования.
Проблема со слитными словами, описанная в предыдущих отзывах, не исчезла, но не выражена в той крайней степени, в какой её выставляют. При осознанном чтении книга не должна оставить никаких впечатлений, кроме положительных - способствуют этому крайне доступный для восприятия перевод и приятная разметка текста. Не буду говорить за сторону квалифицированных. Читать полностью
Читайте также: