The Deep Link Equating Math Proofs and Computer Programs

• cakeml

  14 912 9.8 Standard ML

  CakeML: A Verified Implementation of ML

  

If I understand what you are asking about correctly, then I do think you are mistaken.

As a sibling comment observed, you would be proving something about a program, but proving things about programs is both possible and done.

This ranges from things like CakeML (https://cakeml.org/) and CompCert (compilers with verified correctness proofs of their optimizations) to something simple like absence of runtime type errors in statically strongly soundly-typed languages.

Of note is that you are proving properties of your program, not proving them perfect in every way. The properties of your program that you prove can vary wildly in both difficulty and usefulness. A sufficiently advanced formally verified compiler like CakeML can transfer a high-level proof about your source code to a corresponding proof about the behavior of the generated machine-executable code.

• FStar

  42 2,567 9.9 F*

  A Proof-oriented Programming Language

  

I don't think something that specific exists. There are a very large number of formal methods tools, each with different specialties / domains.

For verification with proof assistants, [Software Foundations](https://softwarefoundations.cis.upenn.edu/) and [Concrete Semantics](http://concrete-semantics.org/) are both solid.

For verification via model checking, you can check out [Learn TLA+](https://learntla.com/), and the more theoretical [Specifying Systems](https://lamport.azurewebsites.net/tla/book-02-08-08.pdf).

For more theory, check out [Formal Reasoning About Programs](http://adam.chlipala.net/frap/).

And for general projects look at [F*](https://www.fstar-lang.org/) and [Dafny](https://dafny.org/).

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• dafny

  31 2,665 9.7 C#

  Dafny is a verification-aware programming language

  

I don't think something that specific exists. There are a very large number of formal methods tools, each with different specialties / domains.

For verification with proof assistants, [Software Foundations](https://softwarefoundations.cis.upenn.edu/) and [Concrete Semantics](http://concrete-semantics.org/) are both solid.

For verification via model checking, you can check out [Learn TLA+](https://learntla.com/), and the more theoretical [Specifying Systems](https://lamport.azurewebsites.net/tla/book-02-08-08.pdf).

For more theory, check out [Formal Reasoning About Programs](http://adam.chlipala.net/frap/).

And for general projects look at [F*](https://www.fstar-lang.org/) and [Dafny](https://dafny.org/).

• aGdaREP

  1 31 10.0 Agda

  Implementing grep in Agda

I've been dabbling with Idris and agda and coq. I think I'm pretty much settling on agda, because I can appeal to Haskell for help. It's tough finding things that aren't just proofs, actually running a program isn't hard, there just doesn't seem to be many people who do it. I've got some toy projects in mind, and I'm going to lean hard on https://github.com/gallais/aGdaREP (grep in agda). I can't tell you if it's ten times harder - that seems high. It's different, sure. I'm having a tougher time than with, say, prolog. But most of the bumps and bruises are from lack of guidance around, uh, stuff.

So given that context, it doesn't sound to tough to add a cost to the type for each operation, function call, whatever, and have the type checker count up the cost of each call. So you'd have real proof that you're under some threshold. I wouldn't put the agda runtime on a flight control computer. But I think I could write a compiler, now, For like a microcontroller that would count up (or spend time budget, doesn't matter).

A more sophisticated computer would be way way harder, and be resource efficient. But if you modeled it as "everything's a cache miss" and don't mind a bunch of no-ops all the time, that would be a pretty straightforward adaptation of the microcontroller approach.

• free-arrow

  2 17 2.9 Scala

  Implementation of the Free Arrow in Scala and other helpful tools for working with Arrows

my first thought was something something dependent types (Idris, Agda), but it also sounds like TS-like structural typing with a Rust-like Result type. proving that every incoming message is either parsed correctly or we return an error seems to be the basic building block. and then every transformation should be other pure functions.

thought I guess you mean something more top-downish? for that there's "program interpretation" ( https://github.com/AdrielC/free-arrow )

plus something very heavy-handed https://deepai.org/publication/a-coq-based-synthesis-of-scal...

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

Suggest a related project