Predicate transformers/symbolic execution about bosquelanguage HOT 5 CLOSED

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.

from bosquelanguage.

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.

from bosquelanguage.

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

from bosquelanguage.

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} {...}

from bosquelanguage.

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

from bosquelanguage.