Лаборатория Математики и Программирования Сергея Бобровского – Telegram
Лаборатория Математики и Программирования Сергея Бобровского
1.29K subscribers
1.19K photos
24 videos
930 links
ЛаМПовое с Бобровским
Download Telegram
В отношении этого поста, мне тут справедливо заметили, что много анти-унификации тоже плохо :)

Безусловно, потому что если ей следовать механически, то получится так, что куча мест с синтаксически схожим кодом превратится в одну большую функцию с множеством условий и чрезмерным количеством параметров в нарушение всех SOLID-подобных принципов, а цикломатическая сложность взлетит в космос.

Как быть? Ну прежде всего понимать, что код и его спецификация -- принципиально разные логические уровни. Хорошее упражнение -- привести несколько примеров программной логики, которые имеют одинаковую реализацию, но разную спецификацию (и поэтому должны в последующем сопровождаться и развиваться принципиально по-разному).
Наличие фактически идентичного кода никак не может выступать надёжным критерием того, что эти два блока делают одно и то же. Поэтому важно поддерживать (хотя бы в своём уме) соответствующую терминологию при объединении похожих вещей, которые в контексте всей системы могут сочетаться, а могут и не сочетаться.
Кот Шредингера заходит в бар... и не заходит.

Тахион заказывает пиво. Тахион заходит в бар.

Гейзенберг едет в машине с Шредингером, когда полицейский останавливает их за превышение скорости.
- Вы знаете, с какой скоростью ехали? - спрашивает полицейский.
- Нет, - отвечает Гейзенберг, - но я могу точно сказать, где я нахожусь!
- Ладно, умник, открывай багажник!
Гейзенберг подчиняется.
- Вы знаете, что у вас в багажнике дохлая кошка? - спрашивает полицейский. Шредингер отвечает:
- Теперь знаю!
Кстати, специфика собеседований по System Design такая, что в отличие например от АСД, где оцениваются достаточно формальные моменты (алгоритмический и практический проблем солвинг, ясность кода...), в SD интервьюер старается не оценить то, в чём вы норм разбираетесь, а выявить ваши слабые места, где вы плаваете, где у вас мало опыта, и начать давить на них посильнее (сам так очень люблю делать).

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

Не ведите себя на собеседованиях как дитя.

Хороший учебник "System Design. Общие принципы прохождения интервью по проектированию ИТ-систем", рекомендую (конкретно по теме его названия).
Классная задачка, встречается нередко при проектировании нагрузки в распределённых системах.

У вас в саду есть N бамбуковых деревьев с разными темпами роста. В конце дня вы можете спилить один бамбук до размера 0.

Надо подготовить график спиливания деревьев, чтобы минимизировать высоту самого высокого бамбукового дерева.

Частный случай -- когда темпы роста это N значений последовательности Фибоначчи, например для N=8 деревьев: [1, 1, 2, 3, 5, 8, 13, 21].
В первый день самое высокое выросло до 21, спилили; на второй день получилось 26=13+13, спилили ... Получится ли например далее удержать минимальную высоту 26 ?

Эта задача была формализована как Bamboo Garden Trimming (BGT).
Стратегий две: руби самое высокое, и руби самое быстрорастущее среди тех, кто выше x; главное, правильно их скомбинировать.
Сегодня День науки (был в СССР) кстати.

Мощная работа про полный обход конём шахматных досок самых разных форм, даже многомерных.

А "Magic: The Gathering", оказывается, Тьюринг-полная. Ух, сколько я в MtG играл...
Многократно подтверждено практикой в данном случае, это не просто теория Парето, что 80% багов в проекте генерируют 20% программистов в проекте.

Поэтому, таких кококодеров :) надо принудительно посылать на курсы переподготовки, и если они после этого не демонстрируют улучшение своего error rate, не проявляют явное желание расти над собой, выгонять самым безжалостным образом.
"Единственное, что растет быстрее, чем производительность компьютеров -- это человеческая глупость"
приписывается Бьярну Страуструпу (автор С++)
Есть такой малоизвестный класс алгоритмов задержки (backoff algorithms), которые используются во многих распределённых системах, когда несколько сущностей/устройств конкурируют за общий ресурс. Часто задачки по этой теме формулируются как "шары в корзины" (и оказывается, что важным критерием становится количество синглтонов - корзин с одним шаром); однако существующие схемы анализа алгоритмов применяют сложные вероятностные инструменты.
Вот например полезная вводная заметка "Exponential Backoff или как "не завалить сервер", рекомендую всем, кто изучает фундамент highload:
"Совет: используйте экспоненциальное откладывание при любом повторе запроса — в клиенте при обращении к серверу или в сервере при обращении к базе данных или другому сервису."

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

Мартовский свежачок, где пацаны из университета Миссисипи показали, что можно эти задачи решать гораздо проще и точнее с помощью так называемых стандартных границ Чернова (простое оценивание вероятностного распределения); в тему неплохая лекция "Границы Чернова, маршрутизация пакетов по коммуникационной сети".

Сам Герман Чернов кстати, профессор MIT, родился в семье эмигрантов из России в 1923-м и прекрасно себя чувствует :)
"Совет по цифровой экономике при Совете Федерации предложил профильным ведомствам и госкомпаниям восстановить систему распределения для IT-специалистов. После вуза их могут привлечь на работу в оборонно-промышленном комплексе на пять лет".

С одной стороны, пять лет программистом в оборонном ящике после института, конечно многовато (даже в СССР было три года отработки :).

С другой стороны, закончил универ в 22, просидел спокойно пять лет в конторе на броне до дембеля, и дальше свободен. Работа обычно в таких местах "не бей лежачего" -- всё очень спокойно и неспешно, выполнил дневную норму за 1-2 часа, и дальше можешь играть, а лучше заниматься самообразованием на перспективу.

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

Платить, думаю, будут достаточно нормально и стабильно; конечно не как в крипто-стартапах :) но если явно мало, так и кодить люди будут совсем еле-еле. Тут как раз выгоднее не экономить, потому что платя в 2 раза меньше, продукт получишь в 22 раза позже; лучше платить хорошо, близко к "среднерыночной", чтобы был нормальный результат в разумные строки.
Есть такая card-based cryptography, придуманная в 1989-м, когда для качественного шифрования сообщений используется обычная колода игральных карт. Заметочка с хабра "Крипто-шифр "пасьянс".

Так как эта форма криптографии "аналоговая", она и компрометируется в принципе достаточно легко (кто-то колоду перетасовал).

card-based cryptography однако была проработана достаточно глубоко некоторое время назад, и под неё подведено серьёзное научное обоснование: "Foundations for Actively Secure Card-based Cryptography".

В тему полезно также почитать про "ментальный покер".
В мае Пентагон начинает полевые испытания гарнитуры виртуальной реальности Integrated Visual Augmentation System (в частности, как системы кругового обзора для бронетехники), которая на самом деле -- коммерческие VR-очки HoloLens с доработкой под сложные условия эксплуатации, и которые закупаются у Microsoft на 22 миллиарда долларов (столько Газпромнефть стоит например).

А я говорил ещё три года назад (словами профессора Карла Хьюитта :), что

"Масштабируемые интеллектуальные системы SIS -- это самый эпичный программный проект, равных которому по сложности в истории человечества пока не было. В 2018 г за эту тему взялись США, Евросоюз, Китай, Канада, Англия, Тайвань и Япония. России в этом списке увы нету. Предполагается, что SIS вызовут громаднейшие изменения в мире, причём уже к 2025-му году."

Принципиально важно, что клиентские устройства SIS -- это прежде всего VR-очки.
Создавать хорошо масштабируемые серьёзные архитектурные решения очень, очень сложно (особенно если за это берутся госконторы). Смешная история, как Пентагон пытается десятки лет разработать "военный интернет вещей", и получается пока сильно хуже, нежели у частных корпораций -- приходится идти на поклон к Илону Маску например.

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

Напомнило сериал "Космические войска" :)
Тот уровень проектирования, которому я стремлюсь вас научить, включает в себя, в частности, концепцию typestate , когда множество потенциальных логических ошибок вылавливается на фазе компиляции.

Понятно, что в любом типизированном языке присвоить строку целочисленной переменной невозможно; имею в виду более продвинутые вещи, например когда целочисленной переменной разрешается присваивать только положительные значения (а ведь Паскаль/Delphi это умел...).

Так вот, typestate позволяет добавлять в систему типов протоколы. Примерно 10-20% объектов в типовом проекте протоколы "поддерживают" (были научные исследования по их выявлению), только некорректно, а то и потенциально ошибочно. Речь о том, что методы класса в рамках протокола должны вызываться в определённом порядке. Скажем, вы должны сперва открыть файл до того, как будете его читать. Обычный компилятор корректность протокола open => read конечно не проверяет, вы просто получите ошибку рантайма при попытке считать из закрытого файла.

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

['1', '7', '11'].map(parseInt) == [1, NaN, 3]
...Однако, четыре фундаментальных языка (в разных парадигмах), на которых всё ИТ стоит и стоять будет, и которые полезно изучать максимально глубоко (включая понимание, как для них пишутся компиляторы и интерпретаторы) -- это Си, Лисп, SQL и JavaScript.
"Пофиксить баг", который был выявлен, например, в ходе code review, и который в работающей системе пока не проявлялся, на практике часто означает перевести систему из состояния "без наблюдаемых ошибок" в состояние "большое количество наблюдаемых ошибок".
Иногда спрашивают, а что сегодня самый топчик в computer science, но при этом имеет прямое прикладное значение? Ну например DSL для реализации тайп-чекера. Единственной программой на таком языке будет декларативное описание конкретной системы типов в некотором прикладном языке программирования, исполняемая формальная спецификация (вычисляемая математика по Алану Кэю), если хотите. Это уровень ведущих разработчиков MMANGA, и имея подобный проект на гитхабе, вполне можно претендовать на отличный оффер в обход бесконечных типовых собеседований по решению литкодовских задачек. Напишите тайп-чекер для конкретного языка, для Apple Swift например, ну и просто это будет большой пожизненный +1 в вашей карьере.
Метапрограммирование, аланкэевщина -- это в значительной степени про DSL (domain specific language) -- прикладные языки предметных областей. Отличие метапрограммирования от lowcode в том, что мы не берём одно готовое "универсальное", а сами делаем подходящие DSL чётко под нашу проектную семантику. Про DSL относительно мало материалов (это очень продуктивный подход, но и весьма сложный), хотя некоторые относительно популярные языки (например Ruby) парадигму DSL поддерживают.

Но есть в этом контексте другой топчик, ещё более аутентичный -- TSL (type specific language). Идея, что в коде есть функция, которая принимает например регулярное выражение, и когда компилятор это видит, он автоматически переключается на парсер регэкспов, и таким образом можно смешивать много разных языков, много разных синтаксисов в одном файле -- гораздо более концептуальным и элегантным способом, чем другие решения. В некотором смысле например C# можно считать TSL, когда мы нативно используем в коде LINQ.
Полноценный пример TSL -- это язык Wyvern разработка которого была профинансирована Агентством национальной безопасности США, потому что подходы DSL/TSL позволяют существенно повысить надёжность и выразительность кода.
Определений абстракции в программировании существует множество, и возможно вы встречались с одним из них, если изучали учебник "Структура и интерпретация компьютерных программ" (SICP), который считается одной из двух самых великих классик в информатике -- наряду с "Concepts, Techniques, and Models of Computer Programming" (CTM), которая на русский не переводилась (кроме моих курсов :). Так вот, уже первая глава SICP называется "Построение абстракций с помощью процедур", но насколько она адекватно отражает концепцию абстракции?

Gerry Sussman (один из авторов SICP) продолжает успешно профессорствовать в MIT, и наши с вами PhD-друзья из Массачусетса этой весной 2022-го года специально обратились к мэтру, чтобы он окончательно пояснил за его версии абстракций :) По мнению Sussman, абстракция -- это "чемоданный термин", который означает слишком много разных вещей, хотя он видит ровно два её подходящих определения, прямо относящихся к разработке программного обеспечения.

Первое определение: давать имена сущностям, созданным в соответствии со вторым определением. :)

А вот второе определение естественно вытекает из первой теоремы о гомоморфизмах и её обобщений в универсальной алгебре (и тут, говорят, гуру постучал по пухлому учебнику по алгебре на его столе).

В СильныхИдеях в мае разберу эту тему более подробно, на пальцах, доступно любому программисту-нематематику :) Ну и, надеюсь, разберём со временем, как доказать первую теорему о гомоморфизме в HoTT на питончике, в каком-нибудь теорем-прувере.

Стратегически всем без исключения порекомендую по этой теме хороший и понятный учебник
"Элементы универсальной алгебры и ее приложений в информатике" (Бениаминов, Ефимова) (алгебраическое моделирование абстрактных типов данных)
как важный шаг в правильном направлении.
Думаю, это явился в мир киллер JavaScript )))
pynoscript.net

Поддержка добавляется просто двумя строчками в html-страничке.