News for hackers. Stuff that matters.
Re:Curry-Howard, the Ontological Ultimate by eli_gottlieb on Wednesday October 15, 2014 @02:44PM (#8460785)
>You might argue that we should use a richer type system to express the specification. Sure! We just need to express the idea of "primes below one million" in the type system. But that's at least as difficult and bug-prone as writing the program in the first place, so I have a hard time seeing the benefit.

   Theorem primes_below_million_spec: forall l m,
      (forall p, In p l -> p < 1000000 /\ ~exists n, n <> p /\ n <> 1 /\ Divisible p n) ->
      length l = m ->
      primes_below_million = m.
Done.
Re:Curry-Howard, the Ontological Ultimate by cousin_it on Wednesday October 15, 2014 @03:42PM (#8461194)
I think that's missing an implementation of the function that matches the type. Is that also easy?
Re:Curry-Howard, the Ontological Ultimate by vilhelm_s on Wednesday October 15, 2014 @09:25PM (#8462802)
That's not so easy. That's the point, right? It's easier to write a specification than an implementation, so it's valuable to check that the implementation satisfies the spec.
Re:Curry-Howard, the Ontological Ultimate by eli_gottlieb on Thursday October 16, 2014 @03:22AM (#8463779)
Well if I wasn't so lazy, it would be easy to implement a Sieve of Eratosthenes algorithm yielding a list of primes up to some number, and then another function feeding 1000000 to that function and returning the length of the resulting list. The hard part would be actually proving the theorem I stated in terms of those two functions.