Beyond Booleans - “bool expressions” in Lean, proposition, proof (overreacted.io)

submitted 5 months ago by Kissaki@programming.dev to c/programming_languages@programming.dev

1 comments fedilink hide all child comments

Explores how the Lean programming language handles 2 + 2 = 4, which other programming languages collapse into a bool, but Lean considers a Proposition, and requires Proof.

How does provably correct programming look? This article seems to give a good introduction and example.

you are viewing a single comment's thread
view the rest of the comments

[-] coherent_domain@infosec.pub 4 points 5 months ago* (last edited 5 months ago)

The name "bool expression" is rather unfortunate, since it is usually reserved for "an expression of type Bool". What is discribed here is really propositions, i.e. "Prop".

Prop is fundamentally different from Bool in Lean and all the language I know. For lean in particular, Prop is defined as a complete lattice, yet Bool is only inhabited by True and False (ignoring incomputable etc). More intuitively, Bool require all the true (or false) statements to be collapsed into a single value true (or false); yet for Prop, provable statements are not necessarily equal to each other.

But I really enjoyed the analogy between expressions that returns bool in other languages and leans prop, seem like a great starting point for people.

this post was submitted on 17 Aug 2025

9 points (100.0% liked)

Programming Languages

1453 readers

2 users here now

Hello!

This is the current Lemmy equivalent of https://www.reddit.com/r/ProgrammingLanguages/.

The content and rules are the same here as they are over there. Taken directly from the /r/ProgrammingLanguages overview:

This community is dedicated to the theory, design and implementation of programming languages.

Be nice to each other. Flame wars and rants are not welcomed. Please also put some effort into your post.

This isn't the right place to ask questions such as "What language should I use for X", "what language should I learn", and "what's your favorite language". Such questions should be posted in /c/learn_programming or /c/programming.

This is the right place for posts like the following:

"Check out this new language I've been working on!"
"Here's a blog post on how I implemented static type checking into this compiler"
"I want to write a compiler, where do I start?"
"How does the Java compiler work? How does it handle forward declarations/imports/targeting multiple platforms/?"
"How should I test my compiler? How are other compilers and interpreters like gcc, Java, and python tested?"
"What are the pros/cons of ?"
"Compare and contrast vs. "
"Confused about the semantics of this language"
"Proceedings from PLDI / OOPSLA / ICFP / "

See /r/ProgrammingLanguages for specific examples

Related online communities

founded 2 years ago

MODERATORS

armchair_progamer@programming.dev