Non-escaping error when implementing Church Numerals in Swift 3

Question

I am attempting to implement Church Numerals in Swift 3. Currently, I have:

func numToChurch(n: Int) -> ((Int) -> Int) -> Int {

    return { (f: (Int) -> Int) -> (Int) -> Int in
        return { (x : Int) -> Int in
            return f(numToChurch(n: n - 1)(f)(x))
        }
    }
}

func churchToNum(f: ((Int) -> Int) -> (Int)-> Int) -> Int {
    return f({ (i : Int) -> Int in
        return i + 1
    })(0)
}

At this line in my function numToChurch:

return f(numToChurch(n: n - 1)(f)(x))

I keep getting a compile-time error that "Closure of non-escaping parameter 'f' may allow it to escape". As a quick-fix, I accepted the recommended changes to include @escaping:

func numToChurch(n: Int) -> ((Int) -> Int) -> Int {

    return { (f: @escaping (Int) -> Int) -> (Int) -> Int in
        return { (x : Int) -> Int in
            return f(numToChurch(n: n - 1)(f)(x))
        }
    }
}

But even after making the changes, I keep getting told the same error and it recommends adding another @escaping after "f:". I understand that this has to do with marking function parameters as @escaping to tell the compiler that the parameters can be stored or captured for functional programming. But I don't understand why I keep getting this error.

Original non-escaping question resolved

Help with understanding church encoding in Swift cont:

func zero(_f: Int) -> (Int) -> Int {
    return { (x: Int) -> Int in
        return x
    }
}

func one(f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { (x: Int) in
        return f(x)
    }
}

func two(f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { (x: Int) in
        return f(f(x))
    }
}

func succ(_ f: Int) -> (@escaping (Int) -> Int) -> (Int) -> Int {
    return { (f : @escaping ((Int) -> Int)) -> Int in
        return { (x : Int) -> Int in
            return f(n(f)(x))
        }
    }
}


func sum(m: @escaping ((Int) -> (Int) -> Int)) -> ((Int) -> (Int) -> Int) -> (Int) -> (Int) -> Int {
    return { (n: @escaping ((Int) -> Int)) -> (Int) -> (Int) -> Int in
        return { (f: Int) -> (Int) -> Int in
            return { (x: Int) -> Int in
                return m(f)(n(f)(x))
            }
        }
    }

Answer 1

You're using currying for multi-parameter functions. That isn't a very natural way to express things in Swift and it's making things complicated. (Swift is not a functional programming language.)

As your linked article says, "All Church numerals are functions that take two parameters." So do that. Make it a two parameter function.

typealias Church = (_ f: ((Int) -> Int), _ x: Int) -> Int

This is a function that takes two parameters, a function and its argument.

Now you want to wrap the argument in the function N times:

// You could probably write this iteratively, but it is pretty elegant recursively 
func numToChurch(_ n: Int) -> Church {
    // Church(0) does not apply the function
    guard n > 0 else { return { (_, n) in n } }

    // Otherwise, recursively apply the function
    return { (f, x) in
        numToChurch(n - 1)(f, f(x))
    }
}

And getting back is just applying the function:

func churchToNum(_ church: Church) -> Int {
    return church({$0 + 1}, 0)
}

---

Just building up on this, you can curry it (and I think I'm just saying what @kennytm has also answered). Currying is just slightly more complicated in Swift:

typealias Church = (@escaping (Int) -> Int) -> (Int) -> Int

func numToChurch(_ n: Int) -> Church {
    // Church(0) does not apply the function
    guard n > 0 else { return { _ in { n in n } } }

    return { f in { x in
        numToChurch(n - 1)(f)(f(x))
        }
    }
}

func churchToNum(_ church: Church) -> Int {
    return church({$0 + 1})(0)
}

There's a very reasonable question: "Why do I need @escaping in the second case, but not in the first?" The answer is that when you pass the function in a tuple, you've already escaped it (by storing it in another data structure), so you don't need to mark it @escaping again.

---

To your further questions, using a typealias dramatically simplifies this problem and helps you think through your types much more clearly.

So what are the parameters of zero? Nothing. It's a constant. So what should its signature be?

func zero() -> Church

How do we implement it? We apply f zero times

func zero() -> Church {
    return { f in { x in
        x
        } }
}

One and two are nearly identical:

func one() -> Church {
    return { f in { x in
        f(x)
        } }
}

func two() -> Church {
    return { f in { x in
        f(f(x))
        } }
}

What is the signature of succ? It takes a Church and returns a Church:

func succ(_ n: @escaping Church) -> Church {

Because this is Swift, we need a little nudge by adding @escaping and _ to make things more natural. (Swift is not a functional language; it decomposes problems differently. Composing functions is not its natural state, so the over-abundence of syntax should not shock us.) How to implement? Apply one more f to n:

func succ(_ n: @escaping Church) -> Church {
    return { f in { x in
        let nValue = n(f)(x)
        return f(nValue)
        } }
}

And again, what is the nature of sum? Well, we're in a currying mood, so that means it's a function that takes a Church and returns a function that takes a Church and returns a Church.

func sum(_ n: @escaping Church) -> (@escaping Church) -> Church

Again, a little extra syntax is needed because Swift. (And as above I've added an extra let binding just to make the pieces a little more clear.)

func sum(_ n: @escaping Church) -> (@escaping Church) -> Church {
    return { m in { f in { x in
        let nValue = n(f)(x)
        return m(f)(nValue)
        } } }
}

The deep lesson here is the power of the Church typealias. When you try to think of Church numbers as "functions that blah blah blah" you quickly get lost in the curry and syntax. Instead, abstract them to be "Church numbers" and just think about what every function should take and return. Remember that a Church number is always a function that takes an Int and returns an Int. It never grows or shrinks from that no matter how many times it's been nested.

---

It's worth taking this example in a couple of other directions because we can play out some deeper ideas of FP and also how Swift should really be written (which are not the same....)

First, writing Church numbers in pointed style is...inelegant. It just feels bad. Church numbers are defined in terms of functional composition, not application, so they should be written in a point-free style IMO. Basically, anywhere you see { f in { x in ...} }, that's just ugly and over-syntaxed. So we want functional composition. OK, we can dig into some experimental stdlib features and get that

infix operator ∘ : CompositionPrecedence

precedencegroup CompositionPrecedence {
    associativity: left
    higherThan: TernaryPrecedence
}

public func ∘<T, U, V>(g: @escaping (U) -> V, f: @escaping (T) -> U) -> ((T) -> V) {
    return { g(f($0)) }
}

Now, what does that do for us?

func numToChurch(_ n: Int) -> Church {
    // Church(0) does not apply the function
    guard n > 0 else { return zero() }
    return { f in f ∘ numToChurch(n - 1)(f) }
}

func succ(_ n: @escaping Church) -> Church {
    return { f in f ∘ n(f) }
}

func sum(_ n: @escaping Church) -> (@escaping Church) -> Church {
    return { m in { f in
        n(f) ∘ m(f)
        } }
}

So we don't need to talk about x anymore. And we capture the essence of Church numbers much more powerfully, IMO. Summing them is equivalent to functional composition.

But all that said, IMO this is not great Swift. Swift wants structure and methods, not functions. It definitely doesn't want a top-level function called zero(). That's horrible Swift. So how do we implement Church numbers in Swift? By lifting into a type.

struct Church {
    typealias F = (@escaping (Int) -> Int) -> (Int) -> Int
    let applying: F

    static let zero: Church = Church{ _ in { $0 } }

    func successor() -> Church {
        return Church{ f in f ∘ self.applying(f) }
    }

    static func + (lhs: Church, rhs: Church) -> Church {
        return Church{ f in lhs.applying(f) ∘ rhs.applying(f) }
    }
}

extension Church {
    init(_ n: Int) {
        if n <= 0 { self = .zero }
        else { applying = { f in f ∘ Church(n - 1).applying(f) } }
    }
}

extension Int {
    init(_ church: Church) {
        self = church.applying{ $0 + 1 }(0)
    }
}

Int(Church(3) + Church(7).successor() + Church.zero) // 11

Answer 2

@escaping is part of the argument type, so you need to do it like:

func numToChurch(n: Int) -> (@escaping (Int) -> Int) -> (Int) -> Int {
//                           ^~~~~~~~~

Complete, working code:

func numToChurch(n: Int) -> (@escaping (Int) -> Int) -> (Int) -> Int {
//                           ^~~~~~~~~                        ^~~~~~
    return { (f: @escaping (Int) -> Int) -> (Int) -> Int in
//               ^~~~~~~~~
        if n == 0 {
            return { x in x }
        } else {
            return { (x : Int) -> Int in
                return f(numToChurch(n: n - 1)(f)(x))
            }
        }
    }
}

func churchToNum(f: (@escaping (Int) -> Int) -> (Int) -> Int) -> Int {
//                   ^~~~~~~~~
    return f({ (i : Int) -> Int in
        return i + 1
    })(0)
}

let church = numToChurch(n: 4)
let num = churchToNum(f: church)

Note:

1. Your return type of numToChurch is wrong even without the @escaping part. You are missing a -> Int.

2. I have added the base n == 0 case in numToChurch, otherwise it will be an infinite recursion.

3. Since the result of numToChurch has an escaping closure, the same annotation needs to be added to that of churchToNum as well.