#article
Lightweight linear types in System F°
We present System F°, an extension of System F that uses kinds to distinguish between linear and unrestricted types, simplifying the use of linearity for general-purpose programming. We demonstrate through examples how System F° can elegantly express many useful protocols, and we prove that any protocol representable as a DFA can be encoded as an F° type. We supply mechanized proofs of System F°’s soundness and parametricity properties, along with a nonstandard operational semantics that formalizes common intuitions about linearity and aids in reasoning about protocols.
We compare System F° to other linear systems, noting that the simplicity of our kind-based approach leads to a more explicit account of what linearity is meant to capture, allowing otherwise-conflicting interpretations of linearity (in particular, restrictions on aliasing versus restrictions on resource usage) to coexist peacefully. We also discuss extensions to System F° aimed at making the core language more practical, including the additive fragment of linear logic, algebraic datatypes, and recursion.
---
Об одном важном моменте в абстракте, впрочем, не упомянуто: они вводят не просто kinds, но и отношение subkinding, конкретно ★ ≤ ◦, где ★ — kind обычных типов, чьи значения могут быть дублированы и отброшены без ограничений, и ◦ — kind линейных типов, чьи значения не могут быть дублированы и должны быть использованы ровно один раз. У этого подхода оказалось несколько приятных следствий, но одно из них — это то, что, стерев информацию о сортах, можно получить широко изученную System F, про которую уже известны многие приятные свойства, в частности, корректность, гарантия прогресса и сильная нормализация.
Lightweight linear types in System F°
We present System F°, an extension of System F that uses kinds to distinguish between linear and unrestricted types, simplifying the use of linearity for general-purpose programming. We demonstrate through examples how System F° can elegantly express many useful protocols, and we prove that any protocol representable as a DFA can be encoded as an F° type. We supply mechanized proofs of System F°’s soundness and parametricity properties, along with a nonstandard operational semantics that formalizes common intuitions about linearity and aids in reasoning about protocols.
We compare System F° to other linear systems, noting that the simplicity of our kind-based approach leads to a more explicit account of what linearity is meant to capture, allowing otherwise-conflicting interpretations of linearity (in particular, restrictions on aliasing versus restrictions on resource usage) to coexist peacefully. We also discuss extensions to System F° aimed at making the core language more practical, including the additive fragment of linear logic, algebraic datatypes, and recursion.
---
Об одном важном моменте в абстракте, впрочем, не упомянуто: они вводят не просто kinds, но и отношение subkinding, конкретно ★ ≤ ◦, где ★ — kind обычных типов, чьи значения могут быть дублированы и отброшены без ограничений, и ◦ — kind линейных типов, чьи значения не могут быть дублированы и должны быть использованы ровно один раз. У этого подхода оказалось несколько приятных следствий, но одно из них — это то, что, стерев информацию о сортах, можно получить широко изученную System F, про которую уже известны многие приятные свойства, в частности, корректность, гарантия прогресса и сильная нормализация.
👍4🤯1
#prog #rust
Хозяйке на заметку
Положили значение в умный указатель со счётчиком ссылок, а теперь хотите достать обратно? Не беда: в std есть API специально для такого случая! Функция Arc::try_unwrap возвращает значение, если сильная ссылка уникальна, и сам Arc в неизменном виде в противном случае. Разумеется, Rc::try_unwrap тоже есть.
Хозяйке на заметку
Положили значение в умный указатель со счётчиком ссылок, а теперь хотите достать обратно? Не беда: в std есть API специально для такого случая! Функция Arc::try_unwrap возвращает значение, если сильная ссылка уникальна, и сам Arc в неизменном виде в противном случае. Разумеется, Rc::try_unwrap тоже есть.
doc.rust-lang.org
Arc in std::sync - Rust
A thread-safe reference-counting pointer. ‘Arc’ stands for ‘Atomically Reference Counted’.
👍6
Forwarded from Backtracking (Дима Веснин)
This media is not supported in your browser
VIEW IN TELEGRAM
для тех, кто часто копирует большие файлы, держите приложение, которое определяет диалог копирования в windows 10/11 и рисует поверх него игру lunar lander (в которую можно поиграть)
https://github.com/Sanakan8472/copy-dialog-lunar-lander
https://github.com/Sanakan8472/copy-dialog-lunar-lander
👏15👍4👎2🤔2❤1
Forwarded from я что-то �� и всё ����
Завтра английский в аудитории 404
Интересно, можно ли на него не прийти, сославшись на не найденную аудиторию :ageblobcat:
Интересно, можно ли на него не прийти, сославшись на не найденную аудиторию :ageblobcat:
💩15🔥2❤1