Computer Science

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

SICP. Модульность

В прошлых статьях мы разобрали основные темы из первой и второй главы сикпа.
В первой главе было про функции и ранги абстракции:

Во второй главе про типы данных:

С этой статьи начинаем главу про модульность кода: как правильно разбивать задачу на части и изолировать их друг от друга.

Разбить по кусочкам

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

Модульность бывает по коду и по файлам. Опять пример с пиццой: аккуратно разложенные ингредиенты — это кодовая модульность, а отдельные кусочки — это файловая модульность. Вместе получается целая и красивая пицца.

Пишем код, разносим его по файлам и собираем всё в одну программу

Состояние данных

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

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

Получается

=> Свет включен
=> Свет выключен
=> Свет включен
=> Свет выключен

Замыкаем состояние состояние переключателя. Код работает так же, но теперь состояние объекта защищено и никому не мешает

Такой подход напоминает ООП — объектно ориентированное программирование. Программа будет почти целиком состоять из независимых объектов на одном уровне модульности. В ООП это называется наследованием. Когда будем проходить C++ объясним.

Как работает

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

Технически, окружение — последовательность кадров, в каждом кадре лежит таблица связываний. В таблице хранится ссылка на окружение выше и пары: (имя переменной, её значение).
В таком коде будет два кадра

При вычислении суммы a и b, интерпретатор возьмёт значение a из оранжевой области, а b из синей

В нашем примере с переключателем тоже два кадра, но во втором будет две ссылки

 1   3 дн   sicp

SICP. Иерархические данные

В прошлой статье мы разобрались как создавать списки в скиме и написали три пользовательские абстрактные функции. В этой статье тоже списки, но вложенные и по-абстрактней.

Списки в списках

Иерархические данные могут состоять сами из себя, то есть мы можем сделать список списков, а там ещё список, и ещё, и ещё. Хранить данные в таких структурах просто так нет смысла, но иногда это полезно: кучу чисел можно запихнуть в двоичное дерево чтобы быстрее их искать, связанные друг с другом данные — в граф. Вот такой список со списком, он состоит из 4 элементов: «1 2 3» — просто числа, а («4 5 6») — ещё один список, внутри него лежат обычные числа «4 5 6».

(list 1 2 3 (list 4 5 6))

В статье про Фибоначчи мы говорили, что древовидная рекурсия плохо справляется с вычислениями, но отлично подходит для иерархических объектов. Тут всё сходится, сделаем подсчёт элементов дерева:

  1. Если получаем пустой список, то возвращаем 0
  2. Если получаем число, то возвращаем 1
  3. Если ничего из этого, то возвращаем сумму двух вызовов функции с car и cdr списка

Все чётные числа

В программировании есть такое понятие как последовательная обработка. Это когда несколько функций по очереди делают свои дела. Чтобы показать её на примере, в СИКПе писали функцию для вычисления суммы квадратов чётных чисел дерева. Для наглядности сделали иерархическое дерево, искали, возводили в квадрат все чётные числа, а потом складывали. Алгоритм такой:

  1. Если функция получила пустой список, то возвращает 0
  2. Если функция получила чётное число, то возводит его в квадрат и возвращает
    Если число нечётное, то возвращает 0
  3. Иначе складывает результат вызова функции с car и cdr списка. В цепочке отложенных сложений будут стоять чётные числа и нули, так получается из-за условия во втором шаге.

Пишем код и получается что-то такое

Улучшаем

Пример выше без последовательной обработки, надо исправить.
Из кода понятна схема проверки:

  1. Выбирается элемент дерева
  2. Проверяется на чётность
  3. Если он чётный, то возводится в квадрат
  4. Возведённые числа откладываются в отдельный список

Превращаем эти пункты в отдельные функции:

  1. Перечислитель перебирает и отдаёт элементы дерева
  2. Фильтр собирает новый список из элементов старого по условию
  3. Мап проходится по каждому элементу списка и применяет к нему функцию из аргумента. На выходе получается новый список
  4. Накопитель собирает в себе чётные элементы списка

Пишем эти функции, переписываем код основной функции и проверяем

Функция так же выводит 56, значит мы ничего не сломали. Через последовательную обработку мы сделали код функции sum-even-squares меньше и понятнее, потому что добавили четыре функции accumulate, map, filter, и enumerate-tree.
Их называют стандартными интерфейсами, потому что они не привязаны к конкретным объектам и их можно использовать для других функций и данных, будто они встроены в сам язык программирования.

 7   11 дн   sicp

SICP. Списки

В прошлых статьях мы работали с парами: создавали пары, писали через них библиотеку обыкновенных дробей и библиотеку интервалов. Теперь усложняемся: будем строить иерархические типы данных на основе пар.

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

Математическое замыкание, это когда множество замкнуто относительно операции и при использовании элементов множества операцией, получается новый элемент множества. Объясняем на томатах: есть 5 грядок разных видов томатов на одном участке. Участок — это множество, грядки — подмножество, а кусты томатов — элементы. Делаем операцию по пересадке: берём по одному кусту и высаживаем шестую грядку. Множества разрослись за счёт элементов этого же множества.

Списки

Мы пропустим момент с созданием библиотеки для списков и возьмём уже готовые скимовские библиотеки, весь код можно проверять на реплите, в этой статье весь код на скиме.

Чтобы создать список нужно написать ключевое слово list и последовательность элементов, которая будет в нём храниться

(list 2 3 4 5 6 7) ; => (2 3 4 5 6 7)

Для списков тоже работает car и cdr, только немного по-другому:

  • car — возвращает первый элемент списка, обычно его называют хэд или же голова
  • cdr — возвращает все кроме первого, их называют тэил или же хвост

Есть ещё несколько базовых операций, но мы их напишем сами чтобы лучше понять устройство списков, сделаем три: получение элемента по индексу, вычисление длины и склеивание двух списков.

Получаем элемент по индексу

Чтобы достать что-то из списка нужен сам список и номер этого чего-то. Это аргументы, теперь продумываем алгоритм:

  1. Если индекс = 0, то возвращаем первое значение в списке
  2. Если нет, то вызываем функцию снова с хвостом списка и индексом − 1
В других языках можно выбрать только последний элемент, но не в скиме

Вычисляем длину

Здесь нужна встроенная функция null?, она определяет пустой список или нет.

Будем проверять по одному элементу и прибавлять к счётчику 1 за каждый новый шаг. За самым последним элементом остаётся пустое пространство, на нём null? и сработает:

  1. Если список пустой, то возвращаем 0
  2. Если не пустой, то прибавляем 1 и вызываем функцию снова с хвостом списка
Сначала функция создаст цепочку отложенных операций, потом вычислит её и получит значение 3

Склеиваем два списка

Разделяем первый список на элементы и приклеиваем по одному элементу ко второму списку. Вытаскивать из первого списка будем командой car. Получится список наоборот, но из-за свёртки рекурсивных вызовов на выходе получится красиво.

Если бы рекурсивные вызовы сворачивались в прямом порядке, всё было бы плохо: (2 4 8) + (16 32 64) = (8 4 2 16 32 64)
Но рекурсия сворачивается в обратном порядке и всё встаёт нормально: (2 4 8) + (16 32 64) = (2 4 8 16 32 64)

Получается такой алгоритм:

  1. Если первый список пустой, то возвращаем второй список
  2. Если второй список не пустой, то собираем пару
Функция создаёт цепочку отложенных операций, потом ко второму списку по одному начинают приклеиваться элементы первого

Тестим

Соберём и проверим наши функции в одном файлике. К слову, тут у нас абстракция чёрным ящиком, потому что мы не знаем как работают функции list, car и cdr внутри.

 15   18 дн   sicp
Ранее Ctrl + ↓