Syng

Syng is concurrent separation logic with propositional ghost state, fully mechanized in Agda.

Syng supports propositional ghost state, which brings powerful expressivity, just like an existing separation logic Iris (Jung et al., 2015).
Notably, Syng supports propositional invariants (a.k.a. impredicative invariants).

But in contrast to Iris's fully semantic approach, Syng models the propositional ghost state simply using the logic's syntax (for propositions and judgments).

As a result, while Iris suffers from step indexing everywhere, Syng is not step-indexed at all.
Thanks to that, Syng has intuitive, easy-to-extend semantics and can flexibly support termination-sensitive program reasoning.

Syng is mechanized in Agda, a modern, dependently typed programming language.
Agda is chosen here rather than Coq, Lean, etc., because Agda has excellent support of coinduction enabled by sized types, and Syng's approach takes great advantage of that.

Getting Started

Just install Agda. Syng is known to work with Agda 2.6.2.2.
Syng has no dependencies on external libraries.

Agda Mode

For viewing and editing Agda code, you can use Agda mode for Emacs or VS Code.

When you open an Agda file, you should first load the file (Ctrl-c Ctrl-l in Emacs and VS Code), which loads and type-checks the contents of the file and its dependencies.

Also, you can quickly jump to the definition (Meta-. in Emacs and F12 in VS Code) of any identifiers, including those that use symbols.

Fonts

Syng's source code uses a lot of Unicode characters.
To render them beautifully, we recommend you use monospace Unicode fonts that support these characters, such as the following:

• JuliaMono ― Has a huge Unicode cover, including all the characters used in Syng's source code.
• Menlo ― Is preinstalled on Mac and pretty beautiful. Doesn't support some characters (e.g., ⊢).

For example, in VS Code, you can use the following setting (in settings.json) to use Menlo as the primary font and fill in some gaps with JuliaMono.

"editor.fontFamily": "Menlo, JuliaMono"

Learning Agda

You can learn Agda's language features from the official document.

Here are notable features used in Syng.

• Sized types ― Enable flexible coinduction and induction, especially in combination with thunks and shrunks.
• With-abstractions ― Allow case analysis on calculated values.
• Copatterns ― Get access to a component of records like a pattern.
• Record modules ― Extend record types with derived notions, effectively used by the type ERA.

Source Code

In the folder src is the Agda source code for Syng.

Base/

In Base/ is a general-purpose library (though newly developed for Syng). Some of them re-export Agda's built-in libraries, possibly with renaming. The library consists of the following parts.

• Basics ― Level for universe levels; Func for functions; Few for two-, one- and zero-element sets; Eq for equality; Dec for decidability; Acc for accessibility; Size for sizes (modeling ordinals), thunks and shrunks.
• Data types ― Bool for Booleans; Zoi for zoi (zero, one, or infinity) numbers; Option for option types; Prod for sigma and product types; Sum for sum types; Nat for natural numbers; Natp for positive natural numbers; List for singly linked lists; Seq for infinite sequences; Str for characters and strings; Ratp for positive rational numbers.
• Misc ― Sety for syntactic sets.

Syng/

In Syng/ is the heart of Syng, which consists of the following parts.

• Lang/ ― The target language of Syng.
  • Expr for addresses, types and expressions; Ktxred for evaluation contexts and redexes; Reduce for reduction of expressions.
  • Example for examples.
• Logic/ ― The syntax of the separation logic Syng.
  • Prop for propositions; Judg for judgments.
  • Core for core proof rules; Names for the name set token; Fupd for the fancy update; Hor for the Hoare triple; Heap for the heap; Ind for the indirection modality and the precursors; Inv for the propositional invariant; Lft for the lifetime; Bor for the borrow; Ub for the upper bound.
  • Paradox for paradoxes on plausible proof rules.
  • Example for examples.
• Model/ ― The semantic model and soundness proof of Syng.
  • ERA/ ― Environmental resource algebras (ERAs), for modeling the ghost state of Syng.
    • Base for the basics of the ERA; All for the dependent-map ERA; Bnd for the bounded-map ERA; Fin for the finite-map ERA.
    • Basic ERAs ― Zoi for the zoi ERA; Exc for the exclusive ERA; Ag for the agreement ERA; FracAg for the fractional agreement ERA.
    • Tailored ERAs ― Heap for the heap ERA; Names for the name set ERA; Ind for the indirection ERAs; Inv for the invariant ERA; Lft for the lifetime ERA; Bor for the borrow ERA; Ub for the upper bound ERA.
    • Global ERA ― Glob for the global ERA.
  • Prop/ ― The semantic model of the propositions and the semantic soundness of the pure sequent.
    • Base for the core semantic logic connectives; Smry for the map summary; Names for the name set token; Heap for the heap-related tokens; Lft for the lifetime-related tokens; Ub for the upper bound-related tokens.
    • Basic for basic propositions; Ind for the indirection modality and precursors; Inv for the invariant-related tokens; Bor for the borrow-related tokens.
    • Interp for the semantics of all the propositions; Sound for the semantic soundness and adequacy of the logic's pure sequent.
  • Fupd/ ― The semantic model and soundness proof of the fancy update.
    • Base for the general fancy update; Ind for the fancy update on the indirection modality and precursors; Inv for the fancy update on the propositional invariant; Bor for the fancy update on the borrow.
    • Interp for interpreting the fancy update; Sound for the semantic soundness and adequacy of the logic's fancy update sequent.
  • Hor/ ― The semantic model and soundness proof of the Hoare triples.
    • Wp for the semantic weakest preconditions; Lang for language-specific lemmas on the weakest preconditions; Heap for semantic fancy update and weakest precondition lemmas for the heap.
    • Adeq for the adequacy of the semantic weakest preconditions.
    • Sound for the semantic soundness and adequacy of the logic's Hoare triple.

We also have All for just importing all the relevant parts of Syng.

Meta-logic

As the meta-logic of Syng, we use Agda, under the option --without-K --sized-types, without any extra axioms.

Our meta-logic has the following properties.

• We use only predicative universes and don't use any impredicative universes like Coq's Prop.
• We don't use any classical or choice axioms.
• We don't use the axiom K, an axiom incompatible with the univalence axiom.
• We don't use any proof-irrelevant types like types in Coq's Prop.
• We use sized types for flexible coinduction and induction.
  • Although some concerns about Agda's soundness around sized types exist, the semantics of sized types are pretty clear in theory. In Syng's mechanization, we use sized types carefully, avoiding unsoundness.

Termination verification by induction

Syng has two types of Hoare triples, partial and total.
The partial Hoare triple allows coinductive reasoning but does not ensure termination.
The total Hoare triple allows only inductive reasoning and thus ensures termination.

Why termination verification is tough in step-indexed logics

In step-indexed logics like Iris, roughly speaking, a Hoare triple can only be partial.
They strip one later modality ▷ off per program step, which destines their reasoning to be coinductive, due to Löb induction.
This makes termination verification in such logics fundamentally challenging.

Let's see this more in detail.
Suppose the target language has an expression constructor ▶, such that ▶ e reduces to e in one program step.
We have the following Hoare triple rule for ▶ in step-indexed logics like Iris, because one later modality is stripped off per program step.

▷ { P } e { Q }  ⊢  { P } ▶ e { Q }

Intuitively, ▷ P, P under the later modality ▷, means that P holds after one logical step.

Also, suppose we can make a vacuous loop ▶ ▶ ▶ … of ▶s.
By the rule for ▶, we get the following lemma on ▶ ▶ ▶ ….

▷ { P } ▶ ▶ ▶ … { Q }  ⊢  { P } ▶ ▶ ▶ … { Q }

On the other hand, a step-indexed logic has the following rule called Löb induction.

▷ P ⊢ P
-------
  ⊢ P

If we can get P assuming ▷ P (or intuitively, P after one logical step), then we can get just P.

Combining Löb induction with the previous lemma, we can have a Hoare triple for ▶ ▶ ▶ … without any premise.

⊢  { P } ▶ ▶ ▶ … { Q }

This means that the Hoare triple is partial, not total, as executing the loop ▶ ▶ ▶ … does not terminate.
Essentially, this is due to coinduction introduced by the later modality.

For this reason, Iris does not generally support termination verification.

Transfinite Iris (Spies et al., 2021), a variant of Iris with step-indexing over ordinal numbers, supports time credits with ordinals for termination verification.
However, to use this, one should do careful math of ordinals, which is a demanding task and formally requires classical and choice axioms.

On the other hand, our logic, Syng, simply provides the total Hoare triple with inductive deduction, thanks to being non-step-indexed.
Remarkably, termination verification in Syng can take advantage of Agda's termination checker, which is handy, flexible and expressive.

Verifying richer liveness properties

Because Syng is not step-indexed, it has the potential to verify liveness properties of programs in general, not just termination.

To demonstrate this, the current version of Syng has the infinite Hoare triple.
It ensures that an observable event occurs an infinite number of times in any execution of the program.
This property, apparently simple, is actually characterized as the mixed fixed point, or more specifically, the greatest fixed point over the least fixed point.
For the infinite Hoare triple, usually the hypothesis can be used only inductively, but when the event is triggered, the hypothesis can be used coinductively.
In this way, this judgment is defined coinductively-inductively, which naturally ensures an infinite number of occurrences of the event.

As a future extension, Syng can be combined with the approach of Simuliris (Gäher et al., 2022).
Syng is a logic for verifying fair termination preservation (i.e., preservation of termination under any fair thread scheduling) of various optimizations of concurrent programs.
Fair termination preservation is an applicable but tricky property, modeled coinductively-inductively. For this reason, Simuliris is built on a non-step-indexed variant of Iris, which has given up any kind of propositional ghost state, including propositional invariants.
We can build a logic for fair termination preservation with propositional ghost state, simply by fusing Simuliris with our logic Syng.