Seemingly Impossible Swift Programs

Re:Seemingly Impossible Swift Programs by mrmr1993 on Monday December 10, 2018 @06:40AM (#18647129)

> It’s going to seem incredible, almost magical, but be assured you there are no tricks involved.

The trick involved is: BitSequence.find is a naïve brute-force search, but the predicates only check n bits (for some n), and laziness ensures that at most n bits are generated.

We run into the expected problems if n is large, or there is no such n. For example,

    func evenNumberOfOnesAtStart(_ s : BitSequence) {
      return (s.atIndex(0) == .zero ||
        (s.atIndex(1) == .one &&
        evenNumberOfOnes(BitSequence { s.atIndex($0 + 2) })))
    }
    
    evenNumberOfOnesAtStart == evenNumberOfOnesAtStart

will never terminate. (Disclaimer: I don't write Swift.)

While it's nice to try smuggling in some mathematics at the end, I think a better conclusion for the article to draw is: if you ask a computer to do a brute-force search on some fixed number of bits, it will do it, even where has to compute this number of bits itself along the way.

[ Parent | on HN ]

Re:Seemingly Impossible Swift Programs by Spivak on Monday December 10, 2018 @04:01PM (#18651136)

I think there might be a clearer explanation.

If a predicate only looks a finite number, n, of bits of a bitsequence then you can brute-force search the space containing the (2^n) sequences shorter than n. And a predicate can't possibly look at infinitely many bits of a bitsequence as the function which resolves that predicate would never terminate.

[ Parent | on HN ]

Re:Seemingly Impossible Swift Programs by mrmr1993 on Monday December 10, 2018 @04:32PM (#18651332)

Agreed.

(Although it's (2^m) sequences, where m is the largest index of the n.)

[ Parent | on HN ]