Обработка ошибок и проектирование компилятора

Перевод статьи Error Handling in Compiler Design.

Задача по обработке ошибок (Error Handling) включает в себя: обнаружение ошибок, сообщения об ошибках пользователю, создание стратегии восстановления и реализации обработки ошибок. Кроме того система обработки ошибок должна работать быстро.

Типы источников ошибок

Источники ошибок делятся на два типа: ошибки времени выполнения (run-time error) и ошибки времени компиляции (compile-time error).

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

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

Читать далее Обработка ошибок и проектирование компилятора

Статические и динамические области видимости

Перевод статьи Static and Dynamic Scoping.

Область видимости переменной x это область программы в которой использование имени x ссылается на объявление этой переменной. Одна из причин использование областей видимости — сохранить переменные в разных частях программы отличными друг от друга. Количество коротких имён для переменных ограничено и программисты используют общепринятые имена (например i для индекса массива). В любой программе среднего размера одинаковые названия переменных используются в разных частях программы.

Области видимости делятся на два вида: статические и динамические.

Статические области видимости

Статические области видимости (Static scoping) так же называются лексическими областями видимости (Lexical scoping). В этих областях видимости имена переменных всегда ссылаются на окружение более верхнего уровня. Это свойство текста программы и не связано со стеком вызовов во время выполнения. Статические области видимости упрощают написание модульного кода, так как программист вычисляет область видимости просто смотря на код. В отличии от этого, динамические области видимости требуют от разработчика учитывать все возможные варианты динамического контекста.

Читать далее Статические и динамические области видимости

Python. Структуры данных: список, кортеж, множество, словарь

Перевод параграфа 3.6 Data Structures из книги Intermediate Python.

Python содержит встроенные типы данных: списки, кортежи, словари.

Списки

Чтобы создать список используйте квадратные скобки или функцию list():

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

Первый элемент списка находится под индексом 0, последний — на единицу меньше длины списка.

Метод append() добавляет элемент в список.

Читать далее Python. Структуры данных: список, кортеж, множество, словарь

Отзыв про Стратоплан

Я обучался на Стратоплане с сентября 2018 по май 2019, специальность "Руководитель отдела". Далее я опишу организацию процесса обучения.

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

Занятия

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

У нас занятия проходили в 19 мск. Два раза в неделю, по будням. Одно занятие длилось в среднем час. Занятия проходили по Skype, голосом без видео.

Перед занятием обучающиеся смотрят видео (в среднем 40-60 минут). Кроме видео выдавалась ссылка на страницу с заданием в гуглдоке. На этой же странице ученики пишут ответы на вопросы из задания. Ответы от каждого ученика отдельно, но все видят ответы друг друга. Написание ответа рекомендовалось, но не было обязательным.

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

К конце занятие куратор давал ссылку на страницу с решением от преподавателя и предлагал прочитать и сравнить его с решением группы.

Читать далее Отзыв про Стратоплан

Задача Pythagorean Triplet

Условие

Дано число \(N\). Найти все пифагоровы тройки такие что \(a + b + c = N\). Пифагоровы тройки удовлетворяют условиям \(a^2 + b^2 = c^2\) и \(a \lt b \lt c\).

Решение

Простейшее решение перебором даёт сложность \(O(n^2)\):

Оптимизации на сокращение перебора в случае когда он дальше не имеет смысла не влияют на порядок роста.

Эту же задачу можно решить за \(O(n)\). Из условий задачи следуют два уравнения:

  • \(a + b + c = N\)
  • \(a^2 + b^2 = c^2\)

\(N\) является константой. Примем так же за константу \(a\). Остаётся система из двух уравнений с двумя неизвестными. Последовательно решаем её.

  • \(c = N - a - b\) (1)
  • \(c^2 - b^2 = a^2\)
  • \((c - b)(c + b) = a^2\) (2)
  • \((n - a - b - b)(n - a - b + b) = a^2\) (подставляем 1 в 2)
  • \((n - a - 2b)(n - a) = a^2\)
  • \(n^2 - an - 2nb - an + a^2 + 2ab = a^2\)
  • \(n^2 - 2an - 2nb + 2ab = 0\)
  • \((2a - 2n)b = 2an - n^2\)
  • \(b = \frac{2an - n^2}{2a - 2n}\)
  • \(c = N - a - b\)

Используя формулы для вычисления \(b\) и \(c\) в цикле по \(a\) находим все пифагоровы тройки.

Курсы на brilliant.org

Brilliant org logo

На brilliant.org находятся курсы по математике и CS (полный список курсов). Курсы построены в полуигровой форме, сначала даётся попытка решить задание, потом краткое объяснение. Задачи направлены на концептуальное понимание тем, теории мало, периодически бывают ссылки на подробное описание.

Большинство задач очень простые, так как темы делятся на маленькие шаги. Например, в теме про наименьшее общее кратное, перед его объяснением проходит более 10 шагов. Часть задач интерактивная, например, связанные с алгоритмами и программированием.

Кроме курсов на brilliant.org есть ежедневные задачи на темы освещенные в курсах и wiki с подробным разъяснением теории.

Курсы платные, примерно 4500р. при годовой подписке.

Задачи на Brilliant.org только на английском, сайт может быть полезен и просто в качестве практики чтения при изучении языка.

Проверка xml по xsd на Python через lxml

В библиотеке lxml содержаться функции для проверки xml по xsd. Пример кода:

Метод validate возвращает False если xml не проходит проверку по схеме. Свойство error_log содержит список несоответствий xml схеме из xsd.

Notepad++ XML Tools, проверка xml по xsd

Описание работы с плагином для Notepad++ XML Tools:

  • Установка
  • Автоматическая првоерка XML
  • Форматирование XML
  • Проверка XML по XSD

Установка XML Tools

Заходим в Управление плагинами:

Управление плагинами Notepad++

Выбираем XML Tools и нажимаем установить:

Установка XML Tools в Notepad++

Читать далее Notepad++ XML Tools, проверка xml по xsd

Задача Bitwise AND

В задаче Bitwise AND дано множество чисел \(S = \{1, 2, 3, ..., N\}\), нужно найти два числа \(A\) и \(B\) такие что значение \(A \& B\) (побитовый оператор И) наибольшее, но меньше заданного \(K\). Вывести наибольшее возможное \(A \& B\).

Ограничения:

  • \(2 \leq N \leq 10^3\)
  • \(2 \leq K \leq N\)

Решение

Решение с перебором рабочее, но не проходит по скорости: всего пар \(N * (N - 1)\), сложность получается \(O(n^2)\).

У этой задачи есть решение за константное время. Предположим число \(K\) нечётное. Это значит что в побитовой записи справа у него находится единица:

\(11_{10} = 1011_2\)

Рассмотрим \(K-1\), в двоичной записи все его цифры совпадают с \(K\) кроме последней в которой находится 0:

\(10_{10} = 1010_2\)

Читать далее Задача Bitwise AND

Использование Saved messages в Telegram

Saved messages Telegram

Saved messages — особый контакт Telegram. Некоторые варианты его использования:

  • Перенос файлов между устройствами
  • TODO-списки, задачи
  • Хранение ссылок, контактов

Первый пункт неинтересен, а второй и третий разберём в соответствии с Джедайскими техниками (Лабиринт).

Задачи

Полностью вести список задач в Saved messages неудобно, Telegram для этого не предназначен. Следовательно, если задачи скапливаются в Telegram то это уже второй (энный) список.

Главный принцип списка задач — список задач должен быть один. Накапливать задачи в Telegram нельзя. Остаётся рассматривать Saved messages как один из источников входящих, так же как почту.

Когда нет возможности записать задачу в основной список задач, удобно быстро отправить сообщение в Telegram. Чужие сообщения можно даже просто пересылать в Saved messages. Но отношение к ним должно быть как к входящим, а не как к задачам. Сообщения разбираются по обычным принципам и переносятся либо в список задач либо в информацию.

Информация

Ссылки и контакты относятся к кускам информации. Главный принцип её хранения — простой и быстрой поиск информации когда она нужна. Обычно, для этого информация хранится в структурированном виде. По проектам, областям, файлам или любым другим способом.

Как и для задач, Telegram не предоставляет возможностей для эффективного хранения информации. Поэтому работа с такими сообщениями такая же как с задачами: при разборе входящих куски информации из Saved messages сортируются и помещаются в наиболее подходящие места, в идеальном случае, в одну или несколько баз знаний.