News for hackers. Stuff that matters.
Re:Bottom Type in F# by asib on Wednesday September 23, 2020 @04:45AM (#24564590)
Interestingly, if you read the article [0] linked in the reddit post referred to in this blog post, the author points out that the Haskell version of the bottom type has a problem - you can construct an inhabitant. Pulling out the relevant section of code:

  fix :: (a -> a) -> a      -- defined in Data.Function
  fix f = let x = f x in x  -- least fixed point of f

  false :: Void
  false = fix (id :: Void -> Void)
Since you can find an inhabitant of Void, you can therefore create an inhabitant of any type, so you can prove any proposition:

  inhabitant :: a
  inhabitant = fix id
I don't know if this is only really a problem if you were trying to use Haskell as a theorem prover. It might be the case that in practice, you're unlikely to run into this inconsistency. I think [1] provides a bit more discussion regarding this.

[0]: https://gciruelos.com/propositions-as-types.html [1]: https://frenchy64.github.io/2018/04/07/unsoundness-in-untype...

EDIT: Just found this [2] which describes the above problem in type theory language.

[2]: https://en.wikipedia.org/wiki/System_U#Girard's_paradox

Re:Bottom Type in F# by tome on Wednesday September 23, 2020 @05:20AM (#24564820)
> I don't know if this is only really a problem if you were trying to use Haskell as a theorem prover.

Yes, it makes it impossible to use Haskell as anything more than a toy as far as theorem provers go. But that's OK because Haskell is not a theorem prover, it is a programming language!

Re:Bottom Type in F# by dan-robertson on Wednesday September 23, 2020 @05:07AM (#24564736)
You also have

  error "foo" :: Void
Ultimately the issue is that Haskell programs are not guaranteed to terminate. You could write a similar function in F# too. Most (all?) theorem provers require that all functions probably terminate.
Re:Bottom Type in F# by kqr on Wednesday September 23, 2020 @04:57AM (#24564671)
Isn't this the premise of the Fast And Loose Reasoning Is Morally Correct paper, which argues that it's fine to ignore bottom when discussing program semantics? Or did I misunderstand that paper dramatically?
Re:Bottom Type in F# by thedufer on Wednesday September 23, 2020 @10:34AM (#24567567)
This may come across as pedantic, but your example only defines a variable with the bottom type. You never actually "construct an inhabitant" because the construction itself is nonterminating. This is actually, in my experience, one of the more common uses for the bottom type - it can mark functions that never return (the "exit" function, for example, or something that loops infinitely, or something that raises an exception).