A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Cancel Create
SICP / README.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Cannot retrieve contributors at this time
717 lines (494 sloc) 22.1 KB
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents Copy raw contents
Copy raw contents
Харольд Абельсон, Джеральд Джей Сассман. «Структура и интерпретация компьютерных программ».
Harold Abelson, Gerald Jay Sussman. «Structure and Interpretation of Computer Programs»
Чтобы не забыть:
- Eli Bendersky’s website : http://eli.thegreenplace.net/tag/sicp
- SICP по-русски : http://sicp.sergeykhenkin.com/sicp-exercise-solutions/
1. Построение абстракций с помощью процедур
Слушать книгу Структура и интерпретация компьютерных программ 2.11
1.1. Элементы программирования
1.1.2. Имена и окружение
1.1.3. Вычисление комбинаций
1.1.4. Составные процедуры
1.1.5. Подстановочная модель применения процедуры
1.1.6. Условные выражения и предикаты
- Упражнение 1.1.
- Упражнение 1.2.
- Упражнение 1.3.
- Упражнение 1.4.
- Упражнение 1.5.
######* 1.1.7. Пример: вычисление квадратного корня методом Ньютона*
- Упражнение 1.6.
- Упражнение 1.7.
- Упражнение 1.8.
* 1.1.8. Процедуры как абстракции типа *
1.2. Процедуры и порождаемые ими процессы
######* 1.2.1. Линейные рекурсия и итерация*
- Упражнение 1.9.
- Упражнение 1.10.
1.2.2. Древовидная рекурсия
- Упражнение 1.11.
- Упражнение 1.12.
- Упражнение 1.13.
- Упражнение 1.14.
- Упражнение 1.15.
1.2.4. Возведение в степень
- Упражнение 1.16.
- Упражнение 1.17.
- Упражнение 1.18.
- Упражнение 1.19.
1.2.5. Нахождение наибольшего общего делителя
- Упражнение 1.20.
1.2.6. Пример: проверка на простоту
- Упражнение 1.21.
- Упражнение 1.22.
- Упражнение 1.23.
- Упражнение 1.24.
- Упражнение 1.25.
- Упражнение 1.26.
- Упражнение 1.27.
- Упражнение 1.28.
1.3. Формулирование абстракций с помощью процедур
1.3.1. Процедуры в качестве аргументов
- Упражнение 1.29.
- Упражнение 1.30.
- Упражнение 1.31.
- Упражнение 1.32.
- Упражнение 1.33.
1.3.2. Построение процедур с помощью lambda
1.3.3. Процедуры как обобщенные методы
- Упражнение 1.35.
- Упражнение 1.36.
- Упражнение 1.37.
- Упражнение 1.38.
- Упражнение 1.39.
1.3.4. Процедуры как возвращаемые значения
Слушать книгу Структура и интерпретация компьютерных программ 1
- Упражнение 1.40.
- Упражнение 1.41.
- Упражнение 1.42.
- Упражнение 1.43.
- Упражнение 1.44.
- Упражнение 1.45.
- Упражнение 1.46.
2. Построение абстракций с помощью данных
2.1. Введение в абстракцию данных
2.1.1. Пример: арифметические операции над рациональными чис-
2.1.2. Барьеры абстракции
- Упражнение 2.2.
- Упражнение 2.3.
- Упражнение 2.4.
- Упражнение 2.5.
- Упражнение 2.6.
2.1.4. Расширенный пример: интервальная арифметика
- Упражнение 2.7.
- Упражнение 2.8.
- Упражнение 2.9.
- Упражнение 2.10.
- Упражнение 2.11.
- Упражнение 2.12.
- Упражнение 2.13.
- Упражнение 2.14.
- Упражнение 2.15.
- Упражнение 2.16.
2.2. Иерархические данные и свойство замыкания
2.2.1. Представление последовательностей
- Упражнение 2.17.
- Упражнение 2.18.
- Упражнение 2.19.
- Упражнение 2.20.
- Упражнение 2.21.
- Упражнение 2.22.
- Упражнение 2.23.
2.2.2. Иерархические структуры
- Упражнение 2.24.
- Упражнение 2.25.
- Упражнение 2.26.
- Упражнение 2.27.
- Упражнение 2.28.
- Упражнение 2.29.
- Упражнение 2.30.
- Упражнение 2.31.
- Упражнение 2.32.
2.2.3. Последовательности как стандартные интерфейсы
- Упражнение 2.33.
- Упражнение 2.34.
- Упражнение 2.35.
- Упражнение 2.36.
- Упражнение 2.37.
- Упражнение 2.38.
- Упражнение 2.39.
- Упражнение 2.40.
- Упражнение 2.41.
- Упражнение 2.42.
- Упражнение 2.43.
2.2.4. Пример: язык описания изображений
- Упражнение 2.44.
- Упражнение 2.45.
- Упражнение 2.46.
- Упражнение 2.47.
- Упражнение 2.48.
- Упражнение 2.49.
- Упражнение 2.50.
- Упражнение 2.51.
- Упражнение 2.52.
2.3. Символьные данные
- Упражнение 2.53.
- Упражнение 2.54.
- Упражнение 2.55.
2.3.2. Пример: символьное дифференцирование
- Упражнение 2.56.
- Упражнение 2.57.
- Упражнение 2.58.
2.3.3. Пример: представление множеств
- Упражнение 2.59.
- Упражнение 2.60.
- Упражнение 2.61.
- Упражнение 2.62.
- Упражнение 2.63.
- Упражнение 2.64.
- Упражнение 2.65.
- Упражнение 2.66.
2.3.4. Пример: деревья кодирования по Хаффману
- Упражнение 2.67.
- Упражнение 2.68.
- Упражнение 2.69.
- Упражнение 2.70.
- Упражнение 2.71.
- Упражнение 2.72.
2.4. Множественные представления для абстрактных данных
2.4.1. Представления комплексных чисел
2.4.3. Программирование, управляемое данными, и аддитивность
- Упражнение 2.73.
- Упражнение 2.74.
- Упражнение 2.75.
- Упражнение 2.76.
2.5. Системы с обобщенными операциями
2.5.1. Обобщенные арифметические операции
- Упражнение 2.77.
- Упражнение 2.78.
- Упражнение 2.79.
- Упражнение 2.80.
2.5.2. Сочетание данных различных типов
- Упражнение 2.81.
- Упражнение 2.82.
- Упражнение 2.83.
- Упражнение 2.84.
- Упражнение 2.85.
- Упражнение 2.86.
2.5.3. Пример: символьная алгебра
- Упражнение 2.87.
- Упражнение 2.88.
- Упражнение 2.89.
- Упражнение 2.90.
- Упражнение 2.91.
- Упражнение 2.92.
- Упражнение 2.93.
- Упражнение 2.94.
- Упражнение 2.95.
- Упражнение 2.96.
- Упражнение 2.97.
3. Модульность, объекты и состояние
3.1. Присваивание и внутреннее состояние объектов
3.1.1. Внутренние переменные состояния
- Упражнение 3.1.
- Упражнение 3.2.
- Упражнение 3.3.
- Упражнение 3.4.
3.1.2. Преимущества присваивания
- Упражнение 3.5.
- Упражнение 3.6.
3.1.3. Издержки, связанные с введением присваивания
- Упражнение 3.7.
- Упражнение 3.8.
3.2. Модель вычислений с окружениями
3.2.1. Правила вычисления
3.2.2. Применение простых процедур
- Упражнение 3.9.
3.2.3. Кадры как хранилище внутреннего состояния
- Упражнение 3.10.
3.2.4. Внутренние определения
- Упражнение 3.11.
3.3. Моделирование при помощи изменяемых данных
3.3.1. Изменяемая списковая структура
- Упражнение 3.12.
- Упражнение 3.13.
- Упражнение 3.14.
- Упражнение 3.15.
- Упражнение 3.16.
- Упражнение 3.17.
- Упражнение 3.18.
- Упражнение 3.19.
- Упражнение 3.20.
3.3.2. Представление очередей
- Упражнение 3.21.
- Упражнение 3.22.
- Упражнение 3.23.
3.3.3. Представление таблиц
- Упражнение 3.24.
- Упражнение 3.25.
- Упражнение 3.26.
- Упражнение 3.27.
3.3.4. Имитация цифровых схем
- Упражнение 3.28.
- Упражнение 3.29.
- Упражнение 3.30.
- Упражнение 3.31.
- Упражнение 3.32.
3.3.5. Распространение ограничений
- Упражнение 3.33.
- Упражнение 3.34.
- Упражнение 3.35.
- Упражнение 3.36.
- Упражнение 3.37.
3.4. Параллелизм: время имеет значение
3.4.1. Природа времени в параллельных системах
- Упражнение 3.38.
3.4.2. Механизмы управления параллелизмом
- Упражнение 3.39.
- Упражнение 3.40.
- Упражнение 3.41.
- Упражнение 3.42.
- Упражнение 3.43.
- Упражнение 3.44.
- Упражнение 3.45.
- Упражнение 3.46.
- Упражнение 3.47.
- Упражнение 3.48.
- Упражнение 3.49.
3.5.1. Потоки как задержанные списки
- Упражнение 3.50.
- Упражнение 3.51.
- Упражнение 3.52.
3.5.2. Бесконечные потоки
- Упражнение 3.53.
- Упражнение 3.54.
- Упражнение 3.55.
- Упражнение 3.56.
- Упражнение 3.57.
- Упражнение 3.58.
- Упражнение 3.59.
- Упражнение 3.60.
- Упражнение 3.61.
- Упражнение 3.62.
3.5.3. Использование парадигмы потоков
- Упражнение 3.63.
- Упражнение 3.64.
- Упражнение 3.65.
- Упражнение 3.66.
- Упражнение 3.67.
- Упражнение 3.68.
- Упражнение 3.69.
- Упражнение 3.70.
- Упражнение 3.71.
- Упражнение 3.72.
- Упражнение 3.73.
- Упражнение 3.74.
- Упражнение 3.75.
- Упражнение 3.76.
3.5.4. Потоки и задержанное вычисление
- Упражнение 3.77.
- Упражнение 3.78.
- Упражнение 3.79.
- Упражнение 3.80.
3.5.5. Модульность функциональных программ
- Упражнение 3.81.
- Упражнение 3.82.
4. Метаязыковая абстракция
4.1. Метациклический интерпретатор
4.1.1. Ядро интерпретатора
- Упражнение 4.1.
4.1.2. Представление выражений
- Упражнение 4.2.
- Упражнение 4.3.
- Упражнение 4.4.
- Упражнение 4.5.
- Упражнение 4.6.
- Упражнение 4.7.
- Упражнение 4.8.
- Упражнение 4.9.
- Упражнение 4.10.
4.1.3. Структуры данных интерпретатора
- Упражнение 4.11.
- Упражнение 4.12.
- Упражнение 4.13.
4.1.4. Выполнение интерпретатора как программы
- Упражнение 4.14.
4.1.5. Данные как программы
- Упражнение 4.15.
4.1.6. Внутренние определения
- Упражнение 4.16.
- Упражнение 4.17.
- Упражнение 4.18.
- Упражнение 4.19.
- Упражнение 4.20.
- Упражнение 4.21.
4.1.7. Отделение синтаксического анализа от выполнения
- Упражнение 4.22.
- Упражнение 4.23.
- Упражнение 4.24.
4.2. Scheme с вариациями: ленивый интерпретатор
4.2.1. Нормальный порядок вычислений и аппликативный порядок
- Упражнение 4.25.
- Упражнение 4.26.
4.2.2. Интерпретатор с ленивым вычислением
- Упражнение 4.27.
- Упражнение 4.28.
- Упражнение 4.29.
- Упражнение 4.30.
- Упражнение 4.31.
4.2.3. Потоки как ленивые списки
- Упражнение 4.32.
- Упражнение 4.33.
- Упражнение 4.34.
4.3. Scheme с вариациями — недетерминистское вычисление
- Упражнение 4.35.
- Упражнение 4.36.
- Упражнение 4.37.
4.3.2. Примеры недетерминистских программ
- Упражнение 4.38.
- Упражнение 4.39.
- Упражнение 4.40.
- Упражнение 4.41.
- Упражнение 4.42.
- Упражнение 4.43.
- Упражнение 4.44.
- Упражнение 4.45.
- Упражнение 4.46.
- Упражнение 4.47.
- Упражнение 4.48.
- Упражнение 4.49.
4.3.3. Реализация amb-интерпретатора
- Упражнение 4.50.
- Упражнение 4.51.
- Упражнение 4.52.
- Упражнение 4.53.
- Упражнение 4.54.
4.4. Логическое программирование
4.4.1. Дедуктивный поиск информации
- Упражнение 4.55.
- Упражнение 4.56.
- Упражнение 4.57.
- Упражнение 4.58.
- Упражнение 4.59.
- Упражнение 4.60.
- Упражнение 4.61.
- Упражнение 4.62.
- Упражнение 4.63.
4.4.2. Как действует система обработки запросов
4.4.3. Является ли логическое программирование математической
- Упражнение 4.64.
- Упражнение 4.65.
- Упражнение 4.66.
- Упражнение 4.67.
- Упражнение 4.68.
- Упражнение 4.69.
4.4.4. Реализация запросной системы
4.4.4.1. Управляющий цикл и конкретизация
4.4.4.3. Поиск утверждений с помощью сопоставления с образцом
4.4.4.4. Правила и унификация
4.4.4.5. Ведение базы данных
- Упражнение 4.70.
4.4.4.6. Операции над потоками
4.4.4.7. Процедуры, определяющие синтаксис запросов
4.4.4.8. Кадры и связывания
- Упражнение 4.71.
- Упражнение 4.72.
- Упражнение 4.73.
- Упражнение 4.74.
- Упражнение 4.75.
- Упражнение 4.76.
- Упражнение 4.77.
- Упражнение 4.78.
- Упражнение 4.79.
5. Вычисления на регистровых машинах
5.1. Проектирование регистровых машин
- Упражнение 5.1.
5.1.1. Язык для описания регистровых машин
- Упражнение 5.2.
5.1.2. Абстракция в проектировании машин
- Упражнение 5.3.
5.1.4. Реализация рекурсии с помощью стека
- Упражнение 5.4.
- Упражнение 5.5.
- Упражнение 5.6.
5.1.5. Обзор системы команд
5.2. Программа моделирования регистровых машин
- Упражнение 5.7.
5.2.3. Порождение исполнительных процедур для команд
- Упражнение 5.9.
- Упражнение 5.10.
- Упражнение 5.11.
- Упражнение 5.12.
- Упражнение 5.13.
5.2.4. Отслеживание производительности машины
- Упражнение 5.14.
- Упражнение 5.15.
- Упражнение 5.16.
- Упражнение 5.17.
- Упражнение 5.18.
- Упражнение 5.19.
5.3. Выделение памяти и сборка мусора
5.3.1. Память как векторы
- Упражнение 5.20.
- Упражнение 5.21.
- Упражнение 5.22.
######5.3.2. Иллюзия бесконечной памяти
5.4. Вычислитель с явным управлением
5.4.1. Ядро вычислителя с явным управлением
5.4.2. Вычисление последовательностей и хвостовая рекурсия
5.4.3. Условные выражения, присваивания и определения
- Упражнение 5.23.
- Упражнение 5.24.
- Упражнение 5.25.
5.4.4. Запуск вычислителя
- Упражнение 5.26.
- Упражнение 5.27.
- Упражнение 5.28.
- Упражнение 5.29.
- Упражнение 5.30.
5.5.1. Структура компилятора
- Упражнение 5.31.
- Упражнение 5.32.
5.5.2. Компиляция выражений
5.5.3. Компиляция комбинаций
5.5.4. Сочетание последовательностей команд
5.5.5. Пример скомпилированного кода
- Упражнение 5.33.
- Упражнение 5.34.
- Упражнение 5.35.
- Упражнение 5.36.
- Упражнение 5.37.
- Упражнение 5.38.
5.5.6. Лексическая адресация
- Упражнение 5.39.
- Упражнение 5.40.
- Упражнение 5.41.
- Упражнение 5.42.
- Упражнение 5.43.
- Упражнение 5.44.
5.5.7. Связь скомпилированного кода с вычислителем
- Упражнение 5.45.
- Упражнение 5.46.
- Упражнение 5.47.
- Упражнение 5.48.
- Упражнение 5.49.
- Упражнение 5.50.
- Упражнение 5.51.
- Упражнение 5.52.
Источник: github.com
Структура и интерпретация компьютерных программ (2 изд) Абельсон
Цена на сайте может отличаться от цены в магазинах сети. Внешний вид книги может отличаться от изображения на сайте.
Цена на сайте может отличаться от цены в магазинах сети. Внешний вид книги может отличаться от изображения на сайте.
Поделиться с друзьями
Ссылка скопирована
Книга посвящена описанию различных систем программного синтаксиса, анализу перехода от набора алгоритмов к программному коду. Значительное место уделяется обсуждению набора «элементарных программ», использующихся в качестве элементов конструкции программ более высоких уровней сложности, оптимизации соотношения их «веса» и эффективности. Особое внимание авторы уделяют анализу проблемы взаимодействия компьютера как физического объекта и программного кода, обеспечивающего информационную составляющую вычисления. Книга будет полезна всем, кому приходится иметь дело с программированием, в том числе и в гуманитарных областях знания.
Характеристики
Книга посвящена описанию различных систем программного синтаксиса, анализу перехода от набора алгоритмов к программному коду. Значительное место уделяется обсуждению набора «элементарных программ», использующихся в качестве элементов конструкции программ более высоких уровней сложности, оптимизации соотношения их «веса» и эффективности. Особое внимание авторы уделяют анализу проблемы взаимодействия компьютера как физического объекта и программного кода, обеспечивающего информационную составляющую вычисления. Книга будет полезна всем, кому приходится иметь дело с программированием, в том числе и в гуманитарных областях знания.
Источник: www.chitai-gorod.ru
Есть ли практическая польза от книги sicp?
Недавно успешно завалил собеседование на вакансию фронтэнд разработчик. Меня программист сначала загрузил реализацией map и reduce, а потом вообще вопросы по функциональщине стал задавать и я поплыл. Тем не менее кодер который проводил собеседование дал «хороший» совет «Прочти структуру и интерпретацию компьютерных программ» если поймёшь хотя бы 50 страниц — поговорим снова».
Скачал, бегло просмотрел и сейчас в недоумении — каким боком нужна вся эта математика и алгоритмы во фронтенде? Зачем это это надо при разработке сайтов? В чём польза?
ps: может программист решил постебаться таким образом?
- Вопрос задан более трёх лет назад
- 3965 просмотров
2 комментария
Простой 2 комментария
Вообще нужно-то это везде, другое дело что может быть они искали целеустремлённого перспективного специалиста, которому в итоге можно предложить обучение в какой-то важной для них сфере с последующим переходом в другую должность или совмещением.
А может просто отделяли зёрна от плевел, то есть действительно passionate разработчиков от «войти-в-айти»-шников.
Если собеседуешься на джуна и зп не сильно выше рынка — то собеседующий тешит свое ЧСВ
Если мидл+, то стоит прочитать
Решения вопроса 0
Ответы на вопрос 5
System programming, Reversing Engineering, C++
SICP учит думать по-программерски. Учит находить решения в программерском мире. Есть огромная разница между программистом знающим как использовать фреймворк1, фреймворк2, . фреймворкN и другим программистом, который может даже и не знать как использовать эти фреймворки, но сможет отличить что вон тот код очень похож на работу за O(n) , а вон тот вроде как за O(1) и сможет сделать более правильный выбор. Грубо говоря есть некий базис, который одному позволяет создавать решения более стабильные, более эффективные, а другому из-за не хватки приходится городить костыли.
К примеру общеизвестная задачка на программирование «банерокрутилка». Когда имеется банер1, банер2, . банерN и нужно вывести «псевдослучайно» каждый банер по одному разу. Один программер может применить массив и указвать в нем какие номера он уже выводил, а другой применит математику и при этом решение будет одно проходным и не потребует выделения массива. И таких задачек в программировании хватает!
Ответ написан более трёх лет назад
Нравится 4 4 комментария
Плиз, расскажите как это сделать без массива. Разве что по циклу пл номерам?
Даниил Демидко, Кратко не получится ответить. Дам лишь «пинок» куда смотреть 😉 Регистр сдвига с линейной обратной связью. Модификация LFSR как раз и есть то, что нужно сделать
Дмитрий, Вы сами не можете кратко объяснить реализацию, а ведь код потом нужно будет сопровождать и не всегда тому кто его написал.
Iruber, Гуглится подобное на Ура! 😉 А умение использовать гугл весьма важный навык современного программера, а иначе GSDD: Google-StackOverflow-Driven development не освоить!
Эта же «банерокрутилка» используется и в вирусах. Чтобы скрыть цикл расшифровки. Ведь с точки зрения вируса ему наплевать в какой последовательности участок кода рас-xor-ивается лишь бы расксорился. Вот к примеру по ключевой фразе в гугл «pseudo random index decryption» быстро находит pdf : Advanced Polymorphic Techniques и в нем п с помощью Ctrl+F ищем слово «lfsr».
Туже банерокрутилку много где можно использовать к примеру в парсере сайтов, чтобы не циклом двигаться по сайту запрашивая очередную ссылку, а как бы случайно и это + несколько техник повышает живучесть парсера
Такие вопросы задают неадекваты. sicp довольно общая книга, можно не читать. Даже в MIT эту книгу больше не читают. https://habrahabr.ru/post/282986/
Не обращай внимания на такие собеседования, неадекваты на собеседованиях большая редкость.
В целом вопросы на собеседовании соответсвуют тому что указано в вакансии.
Если спрашивают дичь, которая не имеет отношения к твоим обязанностям, значит коллектив так себе и заставят писать фронтенд на лиспе или что то в таком духе.
Ответ написан более трёх лет назад
Нравится 4 5 комментариев
от меня +
c SICP по сути как с Кнутом — все советуют, но никто не читает) в 99.9% случаев для промышленной, коммерческой разработки это не нужно
Если что, в той же статье указывается и причина: «бизнес хочет по бырику, но для этого нужно не думать, а методом тыка говном и соплями, посрав на качество и эффективность, связать десяток библиотек. Наш курс для таких задач непригоден.»
batyrmastyr, разве библиотеки это плохо ? И решение бизнес задач вы тоже считаете чем то плохим ?
Если курс не пригоден для решения бизнес задач, то значит он не стоит денег. А образование в MIT стоит дорого и от него ожидают практической пользы, а не обучение функциональному программированию на scheme или lisp.
asd111, плохо когда бизнес получает ответ «это невозможно» потому, что самая подходящая библиотека на нужном языке не умеет делать точно так, только с перламутровыми пуговицами, а недопрограммист даже не думает, что можно залезть в её исходники и немного подкрутить. Ну или написать самому, если на это нужны не миллионы строк кода.
batyrmastyr, Бизнес редко получает ответ «невозможно». Обычно ответ «Это будет стоить столько то» и цена либо устраивает либо нет. Поэтому больше всего собственного софта разрабатывают богатые компании, а мелкие довольствуются типовыми решениями.
каким боком нужна вся эта математика и алгоритмы во фронтенде?
Многие инженерные специальности опираются на математику, как на фундамент. Одним из базовых навыков для программиста (который инженер, а не специально обученная обезьяна) является умение оценить вычислительную сложность программы и написать эффективный алгоритм. Из-за медлительности яваскрипта и операций с DOM, а также разбухания объёма клиентского кода вопрос эффективности стоит очень остро.
Вместо sicp можно взять любую другую книгу развивающую мышление + дающую понимание «сколько эта операция будет стоит» — хоть «Искусство программирования» Кнута, хоть «Алгоритмы и структуры данных» Вирта, хоть «Структуры данных и алгоритмы» Ахо, Ульмана и Хопкрофта, хоть кого другого.
Вот несколько примеров, что случается если не оценивать сложность, а то и вовсе «сперва кодить, потом думать»:
24-ядерный CPU, а я не могу сдвинуть курсор,
Один разработчик чуть не «сломал» пакетный менеджер NPM,
Facebook и Google выпустили Yarn, новый менеджер п. (npm писали клинические дебилы — грузить десятки раз один и тот же пакет!),
Ещё на новый год многие любят повесить на сайт падающий снег и почти у всех он отжирает целое ядро процессора, в каждой открытой вкладке, Карл! 8 вкладок и у тебя висит даже Core i7. Но если настольные компы просто подвисают, то ноутбуки и телефоны ещё и аккумы разряжают со страшной скоростью.
Источник: qna.habr.com