26,098 papers · page 162 of 1,305
We present Aesop, a proof search tactic for the Lean 4 interactive theorem prover. Aesop performs a tree-based search over a user-specified set of proof rules. It supports safe and unsafe rules and uses a best-first search strategy with customisable prioritisation. Aesop also all…
Sharkovsky's theorem is a celebrated result by Ukrainian mathematician Oleksandr Sharkovsky in the theory of discrete dynamical systems, including the fact that if a continuous function of reals has a point of period 3, it must have points of any period. We formalise the proof in…
Abstract Syntax Notation One (ASN.1) is a language for structured data exchange between computers, standardized by both ITU-T and ISO/IEC since 1984. The Distinguished Encoding Rules (DER) specify its non-malleable binary format: for a given ASN.1 data type, every value has a dis…
The number of attacks and accidents leading to significant losses of crypto-assets is growing. According to Chainalysis, in 2021, approx. $14 billion has been lost due to various incidents, and this number is dominated by Decentralized Finance (DeFi) applications. To address thes…
P4Cub is a new intermediate representation (IR) for the P4 programming language. It has been designed with the goal of facilitating development of certified tools. To achieve this, P4Cub is organized around a small set of core constructs and avoids side effects in expressions, wh…
Our objective is to formally verify the correctness of the hundreds of expression optimization rules used within the GraalVM compiler. When defining the semantics of a programming language, expressions naturally form abstract syntax trees, or, terms. However, in order to facilita…
We present the formalization of Doob’s martingale convergence theorems in the mathlib library for the Lean theorem prover. These theorems give conditions under which (sub)martingales converge, almost everywhere or in L1. In order to formalize those results, we build a definition …
Virtual Machines, Dynamic Compllers, and Implementation Frameworks make dynamic langauges easier and more efficient to optimize. Meanwhile, IDEs, provers, dependent types, type inferencers, and (so-called) “generative AI” mean programmers can express - statically - more informati…
Programming languages offer a number of abstractions such as dynamic typing, sandboxing, and automatic garbage collection which, however, come at a performance cost. Looking back, the most influential programming languages were proposed at a time when Moore’s Law was still in pla…
Polyglot programming is the practice of writing an application with multiple languages to capture additional functionality and efficiency not available to a single language. This happens more often than people think. Some reasons are: to support different platforms (e.g., Android…
Though the 2010s saw many research publications about languages such as JavaScript and Python, there currently appears to be a general loss of interest in dynamic languages, with popular new languages such as Rust and Zig being statically typed, and AOT compilation often being vi…
Over the past decade software development has shifted from a process centered around writing code to a process that increasingly involves composition of external packages and managing the integration of code from other team members. The next decade-plus will be defined by the shi…
Dynamic languages have evolved quite a bit over the past few decades. While there’s always room for improvement, the current generation of languages have rich semantics and expressive syntax, making for a pleasant developer experience. Developers can clearly represent ideas, decr…
WebAssembly (Wasm) is a virtual machine whose defining characteristic is that it is low-level: Wasm is designed to abstract the hardware below, not language concepts above. This is a prerequisite for providing predictable performance and for avoiding language bias without feature…
Since the first bug was discovered in the Mark Harvard II electromechanical computer it was clear that finding bugs and debugging of computer systems would be an extremely challenging task. Today, various reports indicated that programmers spend approximately 50% of their time on…
Issues related to the dereferencing of null pointers are a pervasive and widely studied problem, and numerous static analyses have been proposed for this purpose. These are typically based on dataflow analysis, and take advantage of annotations indicating whether a type is nullab…
Session types provide a typing discipline for message-passing systems. However, most session type approaches assume an ideal world: one in which everything is reliable and without failures. Yet this is in stark contrast with distributed systems in the real world. To address this …
Modern distributed applications increasingly replicate data to guarantee high availability and optimal user experience. Conflict-free Replicated Data Types (CRDTs) are a family of data types specially designed for highly available systems that guarantee some form of eventual cons…
Domain-specific languages (DSLs) are prevalent across many application domains. Such languages let developers easily express computations using high-level abstractions that result in performant implementations. To leverage DSLs, however, application developers need to master the …
Resource-aware type systems statically approximate not only the expected result type of a program, but also the way external resources are used, e.g., how many times the value of a variable is needed. We extend the type system of Featherweight Java to be resource-aware, parametri…