😒🤚 "Я простудился и у меня жар"
😏👉 "Я горяч"

#prog #rust #rustreleasenotes

Вышла версия Rust 1.78.0! Как всегда, тут только то, что показалось мне интересным, а всё остальное в детальных заметках о релизе.

▪️Появилось новое пространство имён для атрибутов: diagnostic. В настоящий момент там только один атрибут: on_unimplemented (о котором я рассказывал). Он позволяет кастомизировать сообщение, выдаваемое компилятором для случаев, когда обобщённому коду, который требует этот трейт на обобщённом параметре, предоставляется тип, не реализующий этот трейт. Это уже используется в axum.

▪️В std при debug_assertions теперь проверяются некоторые из предусловий на unsafe функциях. Раньше это было невозможно из-за того, что std всегда поставлялась в релизной сборке.

▪️Некоторые из функций на указателях стали более полезными, поскольку теперь обещают более строгие результаты.
🔸pointer::align_offset возвращает смещение, необходимое для того, чтобы выровнять указатель до указанного выравнивания, или usize::MAX, если это невозможно. Раньше ей разрешалось всегда возвращать usize::MAX.
🔸slice::align_to и slice::align_to_mut переводят &{mut} [T] в (&{mut} [T], &{mut} [U], &{mut} [T]), где слайс в середине теперь максимально возможного размера с учётом ограничений на выравнивание и размер. Раньше функциям разрешалось возвращать, скажем, исходный слайс целиком как первый элемент тройки.

Обе оговорки были связаны с применением этих функций в const-контексте. Сейчас их убрали, поскольку они и сейчас нестабильны в const-контекстах.

▪️async-методы теперь могут возвращать в реализациях конкретные типы, реализующие Future (а не только impl Future).

▪️Реализация RwLock теперь полностью кастомная и не зависит от pthread. Это позволяет оградиться от багов на старых системах, а также избежать аллокаций (т. к. примитивы синхронизации pthread неперемещаемы) и повысить производительность.

▪️В метод char::is_grapheme_extended добавлена проверка на ASCII, чтобы избежать лукапа по юникодным таблицам (последовавший за ним PR переместил эту проверку в код, генерируемый по таблицам Unicode). Звучит, как что-то узкоспециализированное, но этот метод в конечном счёте вызывается в реализации Debug для str. Как следствие, это изменение более чем вдвое ускорило дерайв Debug!

▪️В паттернах теперь нельзя использовать константы типов, не реализующих PartialEq и NaN.

▪️Компилятор теперь по умолчанию не компилирует код с неверными #[doc]-атрибутами.

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

▪️Компилятор теперь предлагает переместить macro_rules! выше по тексту, если декларативный макрос вызывается раньше, чем определяется в этом файле.

▪️Компилятор теперь диагностирует каст ссылки из одного типа в другой с бо́льшим размером.

раньше я программировал без костылей
теперь вот, обзавелся

можно смело учить раст

Сижу, наполняю себя пищей. А хочется... Кое-чем другим.

Знаниями, разумеется. А вы о чём подумали?

bash — это как асбест: вреден для здоровья и присутствует во многих старых конструкциях

Тогда неинтересно

#prog #article

Zed Decoded: Rope & SumTree

Об основной структуре данных в основе текстового редактора Zed и о том, какие преимущества она предоставляет (спойлер: rope — производная от этой структуры).

Note: D&D is cool

#music

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

youtube.com/watch?v=j8dG8adbOXQ

Науки бывают естественные, неестественные и противоестественные

Как же порой хочется, чтобы папищеки мне дали денег

#prog про YAML опять

- А давайте настраивать log::LevelFilter через YAML
- А давайте!
- info
- passed
- warn
- passed
- error
- passed
- off
- SchemaValidationError: false is not one of ["trace","debug","info","warn","error","off"]

#prog #article

How the GNU C Library handles backward compatibility

#prog #article

From Batch to Stream: Automatic Generation of Online Algorithms (pdf)

Среди алгоритмов, которые считают какое-то скалярное значение на потоке данных, можно выделить две категории: offline алгоритмы и online алгоритмы. Offline алгоритмы работают, исходя из предположения, что весь набор данных есть наперёд и его отдельные элементы можно получать сколько угодно раз. Online алгоритмы же работают, получая по одному элементу за раз и имея доступ к результату работы на всех предыдущих элементах — либо как изменяемое состояние, либо как явный аргумент.

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

def variance(xs):
    s = 0
    for x in xs:
        s += x
    avg = s / len(xs)

    sq = 0
    for x in xs:
        sq += (x - avg) ** 2
    return sq / len(xs)

, а вот аналогичный online алгоритм — именно, алгоритм Велфорда (Welfords's algorithm) — значительно менее очевидный:

def welford(v, s, sq, n, x):
    new_s = s + x
    new_n = n + 1
    avg = new_s / new_n
    tmp = s / n
    new_sq = sq + (x - tmp) * (x - avg)
    new_v = new_sq / new_n
    return new_v, new_s, new_sq, new_n

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

Авторы этой статьи предлагают общий метод, который позволяет взять описание offline алгоритма, который принимает на вход список значений, и преобразовать его в online алгоритм (включая вывод сигнатуры с прокидываемыми промежуточными значениями). Работает он при этом не напрямую с императивным представлением, а промежуточным функциональным ML-подобным языком, в котором нет изменяемых значений, а операции над списком выражаются только в терминах левой свёртки (foldl), отображения (map) и фильтрации (filter).

Этот метод существенным образом опирается на RFS, relational functional signature. Это набор формул, каждая из которых выражает дополнительный аргумент online алгоритма в терминах входного списка данных. Предлагаемый метод при этом синтезирует не просто online алгоритм, а алгоритм, индуктивный относительно данной RFS. Это означает, что если RFS выполняется на произвольном списке xs и наборе дополнительных аргументов y, то после вычисления алгоритма P на новом элементе списка x RFS также справедливо на списке xs' = xs ++ [x] и наборе дополнительных аргументов y' = P(y, x). Иными словами, RFS остаётся справедливым после каждого нового элемента.

Общий вид этого метода такой: взять offline алгоритм в функциональном представлении, вывести RFS из всех термов, зависящих от терма, обозначающего исходный список, затем переписать программу так, чтобы заменить дырками термы, непосредственно зависящие от списков (такие по определение в online алгоритме отсутствуют), и синтезировать выражения для дырок, опираясь на ограничения, задаваемые RFS.

Мы можем при должном везении синтезировать выражения для дырок, эксплуатировав индуктивность итоговой программы, а именно, заменив в offline алгоритме терм xs (обозначающий входной список) на xs ++ [x] и упростить выражения, задействовав аксиомы для списковых функций:

foldl(𝑔, 𝑐, 𝑥𝑠++[𝑥]) = 𝑔(foldl(𝑔, 𝑐, 𝑥𝑠), 𝑥)
map(𝑔, 𝑥𝑠++[𝑥]) = map(𝑔, 𝑥𝑠)++[𝑔(𝑥)]
filter(𝑔, 𝑥𝑠++[𝑥]) = 𝑔(𝑥) ? filter(𝑔, 𝑥𝑠)++[𝑥] : filter(𝑔, 𝑥𝑠)

, после чего выражения, зависящие от xs, можно попытаться выразить в терминах дополнительных аргументов для online программы, то есть выражений из RFS.

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

Почему это работает? Потому что, хоть задача и сводится к синтезу выражений, вместо синтеза online алгоритма целиком метод пытается синтезировать отдельные независимые кусочки итоговой программы и при этом эксплуатирует индуктивность итоговой программы. Авторы провели сравнение своей реализации с синтезаторами программ общего назначения и обнаружили, что их метод значительно эффективнее. Из 51 задачи генерации online алгоритма их метод справился со всеми, кроме одной: вычисление kurtosis, четвёртого центрального предела. Соответствующая online программа в одном месте имела терм, слишком большой для поиска перебором.

Разумеется, у этого метода есть и ограничения.

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

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

Ещё одно ограничение, которое авторы почему-то не упоминают в разделе "Limitations" и упоминают лишь мельком:

Ideally Opera [так авторы назвали реализацию] would check equivalence between the online and offline expressions over all possible input streams. However, since automatically checking equivalence is out of scope for existing techniques, Opera resorts to unsound equivalence checking methods based on testing and bounded verification. However, in practice, we have not come across any cases where the equivalence checker yielded an incorrect result.

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

А вот напоследок хочется попенять сам папир. Исходники Opera авторы не выложили. Также в некоторых местах для теорем отсутствуют доказательства, за которыми авторы отсылают к "extended version of paper", но таковой в открытом доступе, судя по всему, пока не существует и не будет раньше июня. 😒

Профунктор стырил. Клоуны.