Predicate transformers/symbolic execution

[mrkmarron]

This is a priority for this project. In theory, and our hand worked examples, the Bosque language allows the effective manipulation of symbolic state for the code. This is foundational to many of the other things we want to do for tooling and would be an exciting step in PL research.

We will be working on parts of this but are happy to collaborate with others who may be interested in the topic.

[lochbrunner]

Could you explain your thoughts related to this topic in more detail?

[mrkmarron]

I’ll refer to the Wikipedia page on predicate transformers (symbolic execution). The ability to compute these formulas would enable us to reason about the meaning of a program in a very deep manner. For straight line and conditional statements the computation is very simple. However, as you see in the page, when you get to iteration you suddenly need a generalized invariant. Computing this invariant is undecidable in general and, even for practical cases, is still a very open problem (even 40 years later).

Bosque does not have loops. Instead it has higher-order functors (filter/map/find/etc.). Our goal would be to build this library of functors carefully and, for each of them, write precise transformers that can be instantiated like the other primitive commands in the transformer calculus. There is a hand worked example in section 5 of the technical report.

[lochbrunner]

Very interesting topic!
Would it make sense to combine predicate and type information for one symbol?
Similar to mathematical syntax? x ∈ {y % 2 == 0: y ∈ Int}

It would be more visible for the reader that this gets evaluated by the compiler and not during runtime in the body of the function.

function(a: I)
  where I: {i:Int && i%2 == 0} {...}

[mrkmarron]

That is an interesting idea. I believe this type of combined predicate/type system is usually called dependent or refinement typing (wikipedia).

I have some MSR colleagues who work on a lanugage called F* that is based on these and supports building fully verified software (they are focused on crypto and the TLS stack) but requires users to write and manage some parts of the proof process.

[mrkmarron]

Landing in master ... will open smaller issues as needed.