tgoop.com/plcomp/102
Last Update:
Implementation Strategies for Mutable Value Semantics
Dimitri Racordon, Denys Shabalin, Daniel Zheng, Dave Abrahams, Brennan Saeta
https://kyouko-taiga.github.io/assets/papers/jot2022-mvs.pdf
Одно из неоспоримых достоинств языка Rust — он наглядно показал, что безопасная работа с указателями и ссылками сложна, и требует следовать довольно замысловатым правилам, уберегающим от неочевидных потенциальных проблем. Даже опыт более простых языков, повсеместно использующих ссылки и GC — например, Java — показывает, что непреднамеренный алиасинг (aliasing) может создавать дыры в системе безопасности, помимо других проблем.
Эти два фактора — сложность системы типов и владения в Rust, и сложность безопасного использования ссылок без контроля алиасинга — привели к появлению ряда языков, например, https://www.hylo-lang.org/ или https://vale.dev/, отказавшихся от первоклассных ссылок вообще. Отказ от первоклассных ссылок означает, что в языке просто нет механизмов, позволяющих явным образом взять ссылку на объект в памяти, передать её в функцию или того хуже — записать в поле другого объекта.
Отказавшись от ссылок и ссылочной семантики, мы приходим к семантике значений. Концептуально, каждое присваивание копирует значение целиком из одного места в другое, а каждый объект владеет своими частями (whole-part relation). Благодаря этому все данные в программе образуют лес, корни деревьев которого располагаются в переменных. И поскольку в такой структуре не может быть алиасинга, можно безбоязненно сделать значения изменяемыми, откуда и возникает Mutable Value Semantics — семантика изменяемых значений. Возможность изменения "по месту" (in-place) частей объектов и отличает MVS от семантики неизменных (immutable) значений в функциональном программировании, которая тривиально реализуется поверх ссылок на общие части в персистентных структурах данных.
Естественно, что наивная реализация такой семантики крайне неэффективна из-за постоянного копирования развесистых структур данных. Самое очевидное узкое место — работа с массивами: при передаче массивов в функции их пришлось бы копировать, а единственный способ вернуть массив из функции — снова создать копию. Для обхода этой проблемы и реализации работы с массивами и другими структурами "по месту" (in-place) предлагается использовать ключевое слово inout для параметров функций, передаваемых "по ссылке". Это и есть "ссылки второго класса", которые возникают и используются неявно, без возможности сохранения в переменных или полях объектов.
Тем не менее, поскольку по ссылке могут передаваться только аргументы функций, а всё остальное должно копироваться — это всё ещё непозволительно много копирований. Особенно "лишних" копирований значений, которые никогда и не меняются, что значит для них алиасинг не наблюдаем и не создаёт проблем (аналогично ФП, упоминавшемуся выше). Чтобы избавиться от этих копий предлагается использовать механизмы Copy-on-Write и подсчёт ссылок при реализации языка. Для уменьшения инкрементов и декрементов счётчика предлагается обратиться к таким работам как Perceus для Koka и Lean 4.
Однако возникает вопрос: коль скоро мы вводим неявные ссылки в наш язык и его реализацию, не сломают ли они семантику изменяемых значений? Чтобы на него ответить, авторы формализуют core language, его систему типов и операционную семантику, после чего доказывают корректность оптимизаций и сохранение семантики изменяемых значений теми правилами, которым подчиняется работа inout аргументов.
Но авторы не ограничились теоретическим рассмотрением вопроса, а пошли дальше, и реализовали прототип предлагаемой семантики с оптимизациями в виде упрощённого языка программирования на основе Swift, используя LLVM в качестве бэкенда. Это позволило оценить производительность прототипа в сравнении с другими языками, использующими LLVM (C++, Swift, Scala Native) на ряде синтетических бенчмарков и общеизвестных примеров (Mandelbrot, NBody, NQueens, etc.).
BY PLComp
Share with your friend now:
tgoop.com/plcomp/102