Lean Programming Language - with formally verified code
(lean-lang.org)
from Kissaki@programming.dev to programming_languages@programming.dev on 31 Jul 06:52
https://programming.dev/post/34840099
from Kissaki@programming.dev to programming_languages@programming.dev on 31 Jul 06:52
https://programming.dev/post/34840099
Lean is a theorem prover and programming language that enables correct, maintainable, and formally verified code
/-- A prime is a number larger than 1 with no trivial divisors -/ def IsPrime (n : Nat) := 1 < n ∧ ∀ k, 1 < k → k < n → ¬ k ∣ n
-- 'Grind' efficiently manages complex pattern matching and -- case analysis beyond standard tactics. example (x : Nat) : 0 < match x with | 0 => 1 | n+1 => x + n := by grind
-- Automatically solves systems of linear inequalities. example (x y : Int) : 27 ≤ 11*x + 13*y → 11*x + 13*y ≤ 45 → -10 ≤ 7*x - 9*y → 7*x - 9*y > 4 := by grind
Does anyone have experience with Lean? Can it be useful for implementing algorithms or logic beyond mathematical proofs, for software libs?
threaded - newest
I haven’t tried Lean, but one of my university courses had us use Dafny, which essentially states the pre- and postcondition of a function. If it can’t prove the conditions are fulfilled, you get an error. This essentially turns all of your bugs (that is, unexpected behaviour) into specification problems. It can also prove that loops eventually end, and the data in a structure follows a specific pattern.
Yeah you can use it for normal software. It is very complex though, and the documentation assumes you already have a PhD in formal verification.
I wouldn’t go that far. I don’t have a PhD in anything, and I find it pretty comprehensible for the most part. I did focus on formal logic for my undergrad computer science degree, but that’s my only formal training, and I’m not some genius or anything approaching that.
The comment in the first example is wrong, it should be no nontrivial divisors.
Quite ironic, that they can prove theorems about their code, but the comments can’t be checkt by the compiler, resulting in their first math example being wrongly described.
I’ve used Lean 4 a decent amount. It’s quite usable for writing normal software in the way you would write Haskell. I find it nicer than Haskell, frankly; more predictable. It’s even pretty easy to model ocaml/sml modules, roughly. There’s an ever-present temptation to lean into using advanced type theory in ways you couldn’t in those simpler languages, and which will complicate your design and make the programming quite a bit more challenging as it goes on, but you don’t have to give in to temptation.