More Like this

1. Soundly Handling Linearity

   https://doi.org/10.1145/3632896  

   Tang, Wenhao; Hillerström, Daniel; Lindley, Sam; Morris, J. Garrett (January 2024, Proceedings of the ACM on Programming Languages)

   Hicks, Michael (Ed.)

   We propose a novel approach to soundly combining linear types with multi-shot effect handlers. Linear type systems statically ensure that resources such as file handles and communication channels are used exactly once. Effect handlers provide a rich modular programming abstraction for implementing features ranging from exceptions to concurrency to backtracking. Whereas conventional linear type systems bake in the assumption that continuations are invoked exactly once, effect handlers allow continuations to be discarded (e.g. for exceptions) or invoked more than once (e.g. for backtracking). This mismatch leads to soundness bugs in existing systems such as the programming language Links, which combines linearity (for session types) with effect handlers. We introduce control-flow linearity as a means to ensure that continuations are used in accordance with the linearity of any resources they capture, ruling out such soundness bugs. We formalise the notion of control-flow linearity in a System F-style core calculus Feff∘, equipped with linear types, an effect type system, and effect handlers. We define a linearity-aware semantics in order to formally prove that Feff∘ preserves the integrity of linear values in the sense that no linear value is discarded or duplicated. In order to show that control-flow linearity can be made practical, we adapt Links based on the design of Feff∘, in doing so fixing a long-standing soundness bug. Finally, to better expose the potential of control-flow linearity, we define an ML-style core calculus Qeff∘, based on qualified types, which requires no programmer provided annotations, and instead relies entirely on type inference to infer control-flow linearity. Both linearity and effects are captured by qualified types. Qeff∘ overcomes a number of practical limitations of Feff∘, supporting abstraction over linearity, linearity dependencies between type variables, and a much more fine-grained notion of control-flow linearity. 

   more » « less
2. Higher-Kinded Data Types: Syntax and Semantics

   https://doi.org/10.1109/LICS.2019.8785657  

   Johann, Patricia; Polonsky, Andrew (January 2019, Logic in Computer Science)

   We present a grammar for a robust class of data types that includes algebraic data types (ADTs), (truly) nested types, generalized algebraic data types (GADTs), and their higher-kinded analogues. All of the data types our grammar defines, as well as their associated type constructors, are shown to have fully functorial initial algebra semantics in locally presentable categories. Since local presentability is a modest hypothesis, needed for such semantics for even the simplest ADTs, our semantic framework is actually quite conservative. Our results thus provide evidence that if a category supports fully functorial initial algebra semantics for standard ADTs, then it does so for advanced higher-kinded data types as well. To give our semantics we introduce a new type former called Lan that captures on the syntactic level the categorical notion of a left Kan extension. We show how left Kan extensions capture propagation of a data type’s syntactic generators across the entire universe of types, via a certain completion procedure, so that the type constructor associated with a data type becomes a bona fide functor with a canonical action on morphisms. A by-product of our semantics is a precise measure of the semantic complexity of data types, given by the least cardinal λ for which the functor underlying a data type is λ-accessible. The proof of our main result allows this cardinal to be read off from a data type definition without much effort. It also gives a sufficient condition for a data type to have semantic complexity ω, thus characterizing those data types whose data elements are effectively enumerable. 

   more » « less
3. Type-I permanence

   https://doi.org/10.1090/ert/648  

   Chirvasitu, Alexandru (July 2023, Representation Theory of the American Mathematical Society)

   We prove a number of results on the survival of the type-I property under extensions of locally compact groups: (a) that given a closed normal embedding $\mathbb{N}⊴<\#comment/>\mathbb{E}$of locally compact groups and a twisted action $(\mathrm{\alpha <\#comment/>},\mathrm{\tau <\#comment/>})$thereof on a (post)liminal $C^{\ast <\#comment/>}$-algebra $A$the twisted crossed product $A{⋊<\#comment/>}_{\mathrm{\alpha <\#comment/>},\mathrm{\tau <\#comment/>}}\mathbb{E}$is again (post)liminal and (b) a number of converses to the effect that under various conditions a normal, closed, cocompact subgroup $\mathbb{N}⊴<\#comment/>\mathbb{E}$is type-I as soon as $\mathbb{E}$is. This happens for instance if $\mathbb{N}$is discrete and $\mathbb{E}$is Lie, or if $\mathbb{N}$is finitely-generated discrete (with no further restrictions except cocompactness). Examples show that there is not much scope for dropping these conditions. In the same spirit, call a locally compact group $\mathbb{G}$type-I-preserving if all semidirect products $\mathbb{N}⋊<\#comment/>\mathbb{G}$are type-I as soon as $\mathbb{N}$is, andlinearlytype-I-preserving if the same conclusion holds for semidirect products $V⋊<\#comment/>\mathbb{G}$arising from finite-dimensional $\mathbb{G}$-representations. We characterize the (linearly) type-I-preserving groups that are (1) discrete-by-compact-Lie, (2) nilpotent, or (3) solvable Lie. 

   more » « less
4. Online Structure Learning for Feed-Forward and Recurrent Sum-Product Networks

   Kalra, Agastya; Rashwan, Abdullah; Hsu, Wei-Shou; Poupart, Pascal; Doshi, Prashant; Trimponias, Georgios (December 2018, Advances in Neural Information Processing Systems (NeurIPS))

   Sum-product networks have recently emerged as an attractive representation due to their dual view as a special type of deep neural network with clear semantics and a special type of probabilistic graphical model for which inference is always tractable. Those properties follow from some conditions (i.e., completeness and decomposability) that must be respected by the structure of the network. As a result, it is not easy to specify a valid sum-product network by hand and therefore structure learning techniques are typically used in practice. This paper describes a new online structure learning technique for feed-forward and recurrent SPNs. The algorithm is demonstrated on real-world datasets with continuous features for which it is not clear what network architecture might be best, including sequence datasets of varying length. 

   more » « less
5. Nonconvex ancient solutions to curve shortening flow

   https://doi.org/10.1090/tran/8943  

   Zhang, Yongzhe; Olson, Connor; Khan, Ilyas; Angenent, Sigurd (July 2023, Transactions of the American Mathematical Society)

   We construct an ancient solution to planar curve shortening. The solution is at all times compact and embedded. For $t\ll <\#comment/>0$it is approximated by the rotating Yin-Yang soliton, truncated at a finite angle $\mathrm{\alpha <\#comment/>}\left(t\right)=-<\#comment/>t$, and closed off by a small copy of the Grim Reaper translating soliton. 

   more » « less