😒🤚 Writing compiler from scratch
😏👉 Writing compiler in Scratch

Знаете как назвать гея, который поддерживает спецоперацию?

Виталий Милонов

Ситуация "Умный дом". Привык, что дома включаю и выключаю свет через Алису. Пошёл выключать чайник, подхожу к газовой плите; и железному чайнику со свистком говорю: "Алиса, выключи чайник". Лишь через секунд 5 до меня дошло, что чайник-то обычный и свистит вполне себе паром, а не динамиками.
Похоже пора покупать умный чайник.

#rust

poignardazur.github.io/2022/11/05/political-messages-in-the-rust-blog

(thanks @rustamann)

Алсо ОФИГЕТЬ, НОВЫЙ ПОСТ В RUSTA::MANN

И днём и ночью кот учёный
Всё ходит по цепи кругом

Потому что блоки для блокчейна майнит

Возможности Telegram:

* лагать
* убирать настройки внешнего вида

И, на самом деле, на подтверждение этого тезиса я натыкаюсь постоянно.

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

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

Да бог с ней, с водой — возьмём что ещё проще. Скажем, колеблющуюся струну, и опять в максимально идеализированном виде — когда мы можем притвориться, что сила натяжения, действующая на участок струны, пропорциональна его смещению относительно соседних участков. Это — тоже уравнение в частных производных, причём в отсутствие внешних сил — линейное. Казалось бы, оно легко решается, ведь так? Ну, в принципе, да, вот только решение включает в себя интегралы от начальных условий. И если производная от композиции элементарных функций выражается через композицию элементарных функций, то аналогичное утверждение насчёт интегралов неверно: даже такая простая функция, как sin(x) / x, имеет первообразную, невыразимую в элементарных функциях, и носящую собственное имя.

Ладно, а если мы откажемся от непрерывности и переместимся в область дискретной математики, станут ли дела проще? В конце-концов, есть же такая простая вещь, как лямбда-исчисление, которое не хуже машины Тьюринга годится для формализации алгоритмов. Однако в определении лямбда-исчисления входит понятие переменной — и, как оказывается, для моделирования вычислений достаточно лишь понятия функции и аппликации, что показывает комбинаторная логика. Обычно в качестве базиса в комбинаторной логике выделяют комбинаторы K, S и I:

Ix = x
Kxy = x
Sxyz = xz(yz)

, и если поведение I и K ясно и легко описывается, то коротко охарактеризовать поведение S не выходит. Более того, этот базис, вообще говоря, избыточен, поскольку I описывается в терминах S и K:

((S K K) x)
= (S K K x)
= (K x (K x))
= x

Можно ли уменьшить этот базис? Можно! Для построения всех комбинаторов достаточно одного комбинатора ι (йота), поведение которого можно определить в терминах термов лямбда-исчисления:

ι := λf. ((f λa. λb. λc. ((ac)(bc)))λd. λe. d)

Или, в терминах SK:

ι := λf. ((fS)K)

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

Ладно, упростим ещё больше: перейдём к булевой алгебре. Нет, сама булева алгебра проста, как сапог, но вот наборы аксиом, которые её задают, зачастую избыточны. Насколько сильно можно уменьшить этот набор? Как показал Стивен Вольфрам (основатель Wolfram|Alpha), для булевой алгебры достаточно всего одной аксиомы об операции NAND (здесь обозначаемой стрелкой, так как эта функция также известна, как стрелка Пирса):

((p↑q)↑r)↑(p↑((p↑r)↑p)) = r

Базис аксиоматики? Безусловно. Просто? Я бы сказал, что нет.

Но и в чисто прикладных вещах этот тезис получает своё подтверждение. Лично мне на ум приходит понятие итераторов (на всякий случай: сказанное ниже в основном относится к external iterator). Казалось бы, операции типа map, filter и fold/reduce куда проще определить непосредственно на коллекциях (и, собственно, в Javascript и Kotlin так и делают). Понятие итератора уже является некоторой абстракцией, полезность которой не ясна с первого взгляда, а уж комбинатор итераторов является абстракцией высшего порядка: он принимает итератор на вход и выдаёт итератор на выход. Казалось бы, к чему эти усложнения, почему нельзя обойтись монолитными операциями? В пользу итераторов есть несколько аргументов (впрочем, сильно завязанных друг на друга):

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

Выразительность: с помощью итераторов можно выразить то, что невозможно выразить на ограниченном наборе монолитных операций. Например, имея на руках map, невозможно в его терминах выразить операцию zip, для которой требуется перебирать последовательности синхронно друг с другом. Имея абстракцию итераторов, можно написать zip самостоятельно, в случае же с монолитными операциями мы вынуждены внести в набор примитивных операция zip... Для каждой пары коллекций! Другой пример — раннее прерывание итерации по какому-то условию. Опять-таки, вызывающий код контролирует, когда итератор выдаёт элементы, и потому ничто не мешает ему самостоятельно принимать решение, когда итерацию прерывать (и начинать ли её вовсе). В случае с монолитными операциями нет никакой возможности вклиниться в процесс итерации. Также можно упомянуть операции над данными, которые материализуются на лету, например, вычисляются или считываются по сети. Для таких источников операция map, сохраняющая тип "коллекции", попросту не имеет смысла, итераторы же работают с этим без проблем.

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

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

===

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

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

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

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

Хоспаде, изначально я хотел этот пост написать сразу после публикации того видео от 3b1b. Почему на это ушла целая неделя?

#prog #php #cpp #article

Как мы наш большой проект на KPHP мигрировали

Безумству храбрых поём мы песню

Сделал, performancetrap

#prog #rust #rustlib

smart-default

Custom derive for automatically implementing the Default trait with customized default values:

#[macro_use]
extern crate smart_default;

#[derive(SmartDefault)]
enum Foo {
Bar,
#[default]
Baz {
#[default = 12]
a: i32,
b: i32,
#[default(Some(Default::default()))]
c: Option<i32>,
#[default(_code = "vec![1, 2, 3]")]
d: Vec<u32>,
#[default = "four"]
e: String,
},
Qux(i32),
}

assert_eq!(
Foo::default(),
Foo::Baz {
a: 12,
b: 0,
c: Some(0),
d: vec![1, 2, 3],
e: "four".to_owned(),
},
);

#prog #python #abnormalprogramming #article

Оказывается, механизм разрешения зависимостей из Poetry можно использовать для решения судоку. И судоку, и разрешение зависимостей — это задачи удовлетворения ограничений (constraint satisfaction problem), поэтому достаточно лишь записать правила судоку в виде пакетов с зависимостями и заставить Poetry это установить. А если добавить флажки для подробного вывода, то Poetry еще по пути будет объяснять, почему он решает судоку именно так. Офигенно!

Статья | Тред на реддите

Еп