11 заметок с тегом

sicp

Сборник по СИКПу

В прошлой статье мы закончили третью главу СИКПа. Всего их пять, но остальные две объясняют как сделать транслятор, а это не наша область. Этой статьёй собираем статьи по СИКПу в кучку, чтобы было удобно пройти его за вечер.

I — Абстракция функций

Вводная в СИКП

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

Основы СИКПа

Знак действия или операция стоит первым потому что ским выделяет фишки абстракции. Сначала стоит знак, а дальше можно писать что угодно — знак не знает про типы и правила

Чёрные ящики и блочная структура

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

Функции, области видимости и структуры

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

Процессы исполнения

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

Простые процессы в СИКПе

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

Высшие функции в СИКПе

II — Абстракция данных

Библиотека обыкновенных дробей

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

Введение в абстрактные данные

Добавили интервалы

Чтобы закрепить составные данные добавили к библиотеке дробей библиотеку интервалов и протестили её на примере с резисторами.

Абстракция данных с интервалами

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

Сначала мы разобрали простые одноранговые списки. Доставали элемент по индексу и измеряли размер на скиме.

Простые списки в СИКПе

Потом мы сделали список списков и получили иерархическое дерево. Это ещё абстрактней, потому что в список чисел можно вставить список строк, а к нему ещё, и ещё, и ещё. Получается дерево — иерархическая схема данных.

Иерархические структуры данных в СИКПе

III — Объекты и потоки

Посмотрели на принцип написания кода с модульностью по объектам и потокам.

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

Модульность в коде и файлах

В модульности с потоками код делится по принципу вычисления: код для параллельного вычисления в одном месте, код для последовательного вычисления — в другом.

Модульность и потоки в исполнении



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

 12   18 дн   sicp

SICP. Потоки

В прошлой статье мы разобрали модульность по файлам и по коду. Суть такая: делим код на объекты, распихиваем их по файлам и получается двойная модульность.
В этой статье разберёмся с модульностью через потоки.

Поток выполнения

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

Это пример для наглядности, потому что на самом деле это процессы внутри ОСки, но суть та же

Затраты на ветви

Когда появляется ветвь, она забирает под себя память и производительность у основного потока, либо просит ещё ресурсов. С расслоением потоков нужно следить за двумя вещами:
Контроль очерёдности
Код выполняется параллельно и приходится запоминать, какой выполнять первее. Сейчас значение переменной равно 2, через две секунды в переменной уже лежит 5, а ещё через три секунды там уже строка.
Общие переменные
Когда потоки начинают работать с одной и той же переменной или объектом начинаются ошибки. Пока первый поток читает список товаров из базы данных, второй удаляет оттуда купленные товары. Третий поток запрашивает список, а там белиберда из товаров на складе и уже купленных.

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

Реализация в коде

Чтобы решать такие проблемы, можно использовать блокировки или очереди. Например, потоки работают с файлом:

  • Блокировка — это ручное управление. Пока первый поток не снимет блокировку, второй не сможет забрать файл себе.
  • Очередь — автоматическое, как только первый поток закончился, сразу запускается второй.

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

Библиотека

Чтобы создать поток нужно импортировать библиотеку threading и вызвать класс Thread. У Thread пять аргументов, но обязательный только один — имя функции, которая будет выполняться в потоке. Чтобы запустить поток нужно вызвать у него метод start

Чтобы заставить второй поток ждать пока закончит первый, нужно вызвать у первого потока метод join в коде второго потока. Тогда второй поток будет ждать пока первый закончит со своей работой.
Для примера сделаем два потока: первый вычисляет сумму чисел от 1 до 9, второй произведение чисел после первого потока.

Запускаем и видим, что код работает не так. Второй поток начал работать раньше, поэтому на выходе мы получили только сумму чисел от 1 до 9.

$ total после mul_sequence = 0
$ total после add_sequence = 45

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

Запускаем и видим, что всё хорошо:

$ total после add_sequence = 45
$ total после mul_sequence = 16329600

Чтобы потоки не соревновались при работе с общими данными, можно использовать блокировку, в библиотеке threading их четыре: mutex, semaphore, event и condition. Нам нужны мьютексы.

Это объект в состоянии истина или ложь. Поток захватывает мьютекс на какой-то объект и пока он у него, другие потоки не получат доступ к объекту. Чтобы другой поток смог получить объект, предыдущий должен освободить мьютекс. Этим занимается программист. Если он забыл освободить мьютекс в потоке, программа зависнет из-за одного бесконечного потока, это называется deadlock

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

После выполнения в файле будет что-то такое

Потоки соревнуются между собой и перебивают друг друга

Теперь добавим блокировку через мьютекс

Теперь потоки не соревнуются и терпеливо ждут пока другой поток закончит запись
 35   25 дн   sicp

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

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

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

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

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

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

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

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

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

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

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

Получается

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

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

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

Как работает

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

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

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

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

 35   1 мес   sicp
Ранее Ctrl + ↓