I might add another class of languages: those intended to express proofs, via the Curry-Howard correspondence. Lean is a primary example here. This could be considered a subclass of functional languages but it might be different enough to warrant a separate class. In particular, the purpose of these programs is to be checked; execution is only secondary.

▲

armchairhacker 4 hours ago | parent | next [-]

Theorem proving and complex types are like extensions on an otherwise ordinary language:

- Agda, Idris, etc. are functional languages extended with complex types

- Isabelle, Lean, etc. are functional languages extended with complex types and unreadable interactive proofs

- Dafny etc. are imperative languages extended with theorems and hints

- ACL2 is a LISP with theorems and hints

Related, typeclasses are effectively logic programming on an otherwise functional/imperative language (like traits in Rust, mentioned in https://rustc-dev-guide.rust-lang.org/traits/chalk.html).

▲

nextaccountic 4 hours ago | parent [-]

> Agda, Idris, etc. are functional languages extended with complex types

I think they are not. No amount of type level extensions can turn a regular functional language like Haskell into something suitable for theorem proving. Adding dependent types to Haskell, for example, doesn't suffice. To build a theorem prover you need to take away some capability (namely, the ability to do general recursion - the base language must be total and can't be Turing complete), not add new capabilities. In Haskell everything can be "undefined" which means that you can prove everything (even things that are supposed to be false).

There's some ways you can recover Turing completeness in theorem provers. You can use effects like in F* (non-termination can be an effect). You can separate terms that can be used in proofs (those must be total) from terms that can only be used in computations (those can be Turing complete), like in Lean. But still, you need the base terms to be total, your logic is done in the fragment that isn't Turing complete, everything else depends on it.

▲

LeCompteSftware 4 hours ago | parent [-]

This is just wrong, you're being too didactic. Idris specifically lets you implement nontotal functions in the same way that Rust lets you write memory-unsafe code. The idea is you isolate it to the part of the program with effects (including the main loop), which the compiler can't verify anyway, and leave the total formally verified stuff to the business logic. Anything that's marked as total is proven safe, so you only need to worry about a few ugly bits; just like unsafe Rust.

Idris absolutely is a general-purpose functional language in the ML family. It is Haskell, but boosted with dependent types.

▲

nextaccountic 3 hours ago | parent | next [-]

I mentioned this later

> You can separate terms that can be used in proofs (those must be total) from terms that can only be used in computations (those can be Turing complete), like in Lean

What I meant is that the part of Idris that lets people prove theorems is the non-total part

But, I think you are right. Haskell could go there by adding a keyword to mark total functions, rather than marking nontotal functions like Idris does. It's otherwise very similar languages

▲

andai 3 hours ago | parent | prev [-]

Random passerby chiming in: so this means you can write "regular" software with this stuff?

While reading TFA I thought the theorem stuff deserved its own category, but I guess it's a specialization within an ur-family (several), rather than its own family?

It definitely sounds like it deserves its own category of programming language, though. The same way Lojban has ancestry in many natural languages but is very much doing its own thing.

	▲	nextaccountic 3 hours ago \| parent [-]
		Yes Idris was meant to write regular code. F* is also meant to write regular code But I think that the theorem prover that excels most at regular code is actually Lean. The reason I think that is because Lean has a growing community, or at least is growing much faster than other similar languages, and for regular code you really need a healthy ecosystem of libraries and stuff. Anyway here an article about Lean as a general purpose language https://kirancodes.me/posts/log-ocaml-to-lean.html

▲

LeCompteSftware 4 hours ago | parent | prev [-]

Lean is definitely a dependently typed ML-family language like Agda and Idris, so "ML" has it covered. And the long-term goal of Lean certainly is not "execution is only secondary"; Microsoft is clearly interested in writing real software with it: https://lean-lang.org/functional_programming_in_lean/Program...

OTOH if you really want to emphasize "intended to express proofs" then surely Prolog has that covered, so Lean can be seen as half ML, half Prolog. From this view, the Curry-Howard correspondence is just an implementation detail about choosing a particular computational approach to logic.