4 ms·
>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 t
by eli_gottlieb 12y ago
>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.
- cousin_it 12y agoI think that's missing an implementation of the function that matches the type. Is that also easy?
- vilhelm_s 12y agoThat'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.
- eli_gottlieb 12y agoWell 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.