How to improve compilation time for currying and partial application with an operator

I'm new to Swift, and trying to implement currying and partial application for functional programming in Swift. I encounter compilation problem when calling a function having many parameters with an operator for currying and partial application.

Curry function implementation (you may skip this part)

There is no problem to implement curry functions:

// curry1
@inlinable public func curry<A, Z>(_ fx: @escaping (A) -> Z) -> (A) -> Z {
  fx
}

// curry2
@inlinable public func curry<A, B, Z>(_ fx: @escaping (A, B) -> Z) -> (A) -> (B) -> Z {
  { a in { b in fx(a, b) } }
}

// curry3
@inlinable public func curry<A, B, C, Z>(_ fx: @escaping (A, B, C) -> Z) -> (A) -> (B) -> (C) -> Z {
  { a in { b in { c in fx(a, b, c) } } }
}

// curry4
@inlinable public func curry<A, B, C, D, Z>(_ fx: @escaping (A, B, C, D) -> Z) -> (A) -> (B) -> (C) -> (D) -> Z {
  { a in { b in { c in { d in fx(a, b, c, d) } } } }
}

// curry5
@inlinable public func curry<A, B, C, D, E, Z>(_ fx: @escaping (A, B, C, D, E) -> Z) -> (A) -> (B) -> (C) -> (D) -> (E) -> Z {
  { a in { b in { c in { d in { e in fx(a, b, c, d, e) } } } } }
}

// curry6
@inlinable public func curry<A, B, C, D, E, F, Z>(_ fx: @escaping (A, B, C, D, E, F) -> Z) -> (A) -> (B) -> (C) -> (D) -> (E) -> (F) -> Z {
  { a in { b in { c in { d in { e in { f in fx(a, b, c, d, e, f) } } } } } }
}

// curry7
@inlinable public func curry<A, B, C, D, E, F, G, Z>(_ fx: @escaping (A, B, C, D, E, F, G) -> Z) -> (A) -> (B) -> (C) -> (D) -> (E) -> (F) -> (G) -> Z {
  { a in { b in { c in { d in { e in { f in { g in fx(a, b, c, d, e, f, g) } } } } } } }
}

// curry8
@inlinable public func curry<A, B, C, D, E, F, G, H, Z>(_ fx: @escaping (A, B, C, D, E, F, G, H) -> Z) -> (A) -> (B) -> (C) -> (D) -> (E) -> (F) -> (G) -> (H) -> Z {
  { a in { b in { c in { d in { e in { f in { g in { h in fx(a, b, c, d, e, f, g, h) } } } } } } } }
}

// curry9
@inlinable public func curry<A, B, C, D, E, F, G, H, I, Z>(_ fx: @escaping (A, B, C, D, E, F, G, H, I) -> Z) -> (A) -> (B) -> (C) -> (D) -> (E) -> (F) -> (G) -> (H) -> (I) -> Z {
  { a in { b in { c in { d in { e in { f in { g in { h in { i in fx(a, b, c, d, e, f, g, h, i) } } } } } } } } }
}

and which can pass the test:

func test_currying() {
  // test curry()

  func sumTo(_ x: Int) -> Int {
    return (x + 1) * x / 2
  }

  let add1 = { (a: Int) in a }
  XCTAssertEqual(curry(add1)(1), sumTo(1))

  let add2 = { (a: Int, b: Int) in a + b }
  XCTAssertEqual(curry(add2)(1)(2), sumTo(2))

  let add3 = { (a: Int, b: Int, c: Int) in a + b + c}
  XCTAssertEqual(curry(add3)(1)(2)(3), sumTo(3))

  let add4 = { (a: Int, b: Int, c: Int, d: Int) in a + b + c + d }
  XCTAssertEqual(curry(add4)(1)(2)(3)(4), sumTo(4))

  let add5 = { (a: Int, b: Int, c: Int, d: Int, e: Int) in a + b + c + d + e }
  XCTAssertEqual(curry(add5)(1)(2)(3)(4)(5), sumTo(5))

  let add6 = { (a: Int, b: Int, c: Int, d: Int, e: Int, f: Int) in a + b + c + d + e + f }
  XCTAssertEqual(curry(add6)(1)(2)(3)(4)(5)(6), sumTo(6))

  let add7 = { (a: Int, b: Int, c: Int, d: Int, e: Int, f: Int, g: Int) in a + b + c + d + e + f + g }
  XCTAssertEqual(curry(add7)(1)(2)(3)(4)(5)(6)(7), sumTo(7))

  let add8 = { (a: Int, b: Int, c: Int, d: Int, e: Int, f: Int, g: Int, h: Int) in a + b + c + d + e + f + g + h }
  XCTAssertEqual(curry(add8)(1)(2)(3)(4)(5)(6)(7)(8), sumTo(8))

  let add9 = { (a: Int, b: Int, c: Int, d: Int, e: Int, f: Int, g: Int, h: Int, i: Int) in a + b + c + d + e + f + g + h + i }
  XCTAssertEqual(curry(add9)(1)(2)(3)(4)(5)(6)(7)(8)(9), sumTo(9))
}

Partial application operator (encountering compilation problem)

Now I implement partial application with a symbol (option + J), and it can be used like this:

let add4param = { (a: Int, b: Int, c: Int, d: Int) in a + b + c + d }
add4param(1,2,3,4)           // 10

// currying and applying
curry(add4param)(1)(2)(3)(4) //10

// automatically currying and applying parameters 
//   without parentheses using operator ∆
add4param ∆ 1 ∆ 2 ∆ 3 ∆ 4    // 10

// currying and partial application with ∆
let partialAdd = add4param ∆ 1 ∆ 2 ∆ 3  // (Int) -> Int
partialAdd(4)   // 10

Here is the implementation of operator (option + J):

precedencegroup xl_group_l_10 {
  associativity: left
  higherThan: AssignmentPrecedence  // should be: xl_group_r_9
}

// MARK: currying and partial application operator `∆` (option + J)
infix operator ∆ : xl_group_l_10


// curry1 and apply
@inlinable public func ∆ <A, Z>(_ lhs: @escaping (A) -> Z, _ rhs: A) -> Z {
  lhs(rhs)
}

// curry2 and apply
@inlinable public func ∆ <A, B, Z>(_ lhs: @escaping (A, B) -> Z, _ rhs: A) -> (B) -> Z {
  curry(lhs)(rhs)
}

// curry3 and apply
@inlinable public func ∆ <A, B, C, Z>(_ lhs: @escaping (A, B, C) -> Z, _ rhs: A) -> (B) -> (C) -> Z {
  curry(lhs)(rhs)
}

// curry4 and apply
@inlinable public func ∆ <A, B, C, D, Z>(_ lhs: @escaping (A, B, C, D) -> Z, _ rhs: A) -> (B) -> (C) -> (D) -> Z {
  curry(lhs)(rhs)
}

// curry5 and apply
@inlinable public func ∆ <A, B, C, D, E, Z>(_ lhs: @escaping (A, B, C, D, E) -> Z, _ rhs: A) -> (B) -> (C) -> (D) -> (E) -> Z {
  curry(lhs)(rhs)
}

// curry6 and apply
@inlinable public func ∆ <A, B, C, D, E, F, Z>(_ lhs: @escaping (A, B, C, D, E, F) -> Z, _ rhs: A) -> (B) -> (C) -> (D) -> (E) -> (F) -> Z {
  curry(lhs)(rhs)
}

// curry7 and apply
@inlinable public func ∆ <A, B, C, D, E, F, G, Z>(_ lhs: @escaping (A, B, C, D, E, F, G) -> Z, _ rhs: A) -> (B) -> (C) -> (D) -> (E) -> (F) -> (G) -> Z {
  curry(lhs)(rhs)
}

// curry8 and apply
@inlinable public func ∆ <A, B, C, D, E, F, G, H, Z>(_ lhs: @escaping (A, B, C, D, E, F, G, H) -> Z, _ rhs: A) -> (B) -> (C) -> (D) -> (E) -> (F) -> (G) -> (H) -> Z {
  curry(lhs)(rhs)
}

// curry9 and apply
@inlinable public func ∆ <A, B, C, D, E, F, G, H, I, Z>(_ lhs: @escaping (A, B, C, D, E, F, G, H, I) -> Z, _ rhs: A) -> (B) -> (C) -> (D) -> (E) -> (F) -> (G) -> (H) -> (I) -> Z {
  curry(lhs)(rhs)
}

The problem is that it takes about 1 min to compile the following test function (on my old MacBookPro 2014), although it can pass the test:

func test_partial_application() {
  // test curry()

  func sumTo(_ x: Int) -> Int {
    return (x + 1) * x / 2
  }

  let add1 = { (a: Int) in a }
  XCTAssertEqual(add1 ∆ 1, sumTo(1))

  let add2 = { (a: Int, b: Int) in a + b }
  XCTAssertEqual(add2 ∆ 1 ∆ 2, sumTo(2))

  let add3 = { (a: Int, b: Int, c: Int) in a + b + c}
  XCTAssertEqual(add3 ∆ 1 ∆ 2 ∆ 3, sumTo(3))

  let add4 = { (a: Int, b: Int, c: Int, d: Int) in a + b + c + d }
  XCTAssertEqual(add4 ∆ 1 ∆ 2 ∆ 3 ∆ 4, sumTo(4))

  let add5 = { (a: Int, b: Int, c: Int, d: Int, e: Int) in a + b + c + d + e }
  XCTAssertEqual(add5 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5, sumTo(5))

  let add6 = { (a: Int, b: Int, c: Int, d: Int, e: Int, f: Int) in a + b + c + d + e + f }
  XCTAssertEqual(add6 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6, sumTo(6))

  let add7 = { (a: Int, b: Int, c: Int, d: Int, e: Int, f: Int, g: Int) in a + b + c + d + e + f + g }
  XCTAssertEqual(add7 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6 ∆ 7, sumTo(7))

  let add8 = { (a: Int, b: Int, c: Int, d: Int, e: Int, f: Int, g: Int, h: Int) in a + b + c + d + e + f + g + h }
  XCTAssertEqual(add8 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6 ∆ 7 ∆ 8, sumTo(8))

  let add9 = { (a: Int, b: Int, c: Int, d: Int, e: Int, f: Int, g: Int, h: Int, i: Int) in a + b + c + d + e + f + g + h + i }
  XCTAssertEqual(add9 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6 ∆ 7 ∆ 8 ∆ 9, sumTo(9))
}

I find that it takes much time to compile using operator with many parameters

let add9 = { (a: Int, b: Int, c: Int, d: Int, e: Int, f: Int, g: Int, h: Int, i: Int) in a + b + c + d + e + f + g + h + i }
// Compile quickly
add9(1, 2, 3, 4, 5, 6, 7, 8, 9)
curry(add9)(1)(2)(3)(4)(5)(6)(7)(8)(9)
(add9 ∆ 1)(2)(3)(4)(5)(6)(7)(8)(9)
(add9 ∆ 1 ∆ 2)(3)(4)(5)(6)(7)(8)(9)
// Compile slowly
add9 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6 ∆ 7 ∆ 8 ∆ 9
(add9 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6 ∆ 7 ∆ 8) (9)

Is there any way to improve the compilation time If I want to keep using this syntax for partial application?

The compiler has a lot of work to resolve those function calls.

add9 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6 ∆ 7 ∆ 8 ∆ 9
  • There are 9 function overloads to choose from.
  • There are 9 such calls in the same expression.
  • There are 9 integer literals in the expression.
  • An integer literal could be any ExpressibleByIntegerLiteral type, of which there are at least 14 (Int, Int8, Int16, Int32, Int64, UInt, UInt8, UInt16, UInt32, UInt64, Float16, Float, Double, Float80).

Together, that is at least 9 × 9 × 9 × 14 = 10 206 different permutations for the compiler to sift through. Reducing any of those factors will make it faster.

// Slow (9 × 9 × 9 × 14 = 10 206 permutations)
add9 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6 ∆ 7 ∆ 8 ∆ 9

// Make ∆ a single generic function instead of several overloads:
// (probably impossible for your use case)
// Faster (1 × 9 × 9 × 14 = 1134 permutations)
add9 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6 ∆ 7 ∆ 8 ∆ 9

// Split up the expressions:
// Faster (9 × 1 × 1 × 14) × 9 = 1134 permutations)
let partial1 = add9 ∆ 1
let partial2 = partial1 ∆ 2
let partial3 = partial2 ∆ 3
let partial4 = partial3 ∆ 4
let partial5 = partial4 ∆ 5
let partial6 = partial5 ∆ 6
let partial7 = partial6 ∆ 7
let partial8 = partial7 ∆ 8
let complete = partial8 ∆ 9

// Make sure the literal types are resolved first:
// Faster (9 × 9 × 9 × 1 = 729 permutations)
let _1: Int = 1
let _2: Int = 2
let _3: Int = 3
let _4: Int = 4
let _5: Int = 5
let _6: Int = 6
let _7: Int = 7
let _8: Int = 8
let _9: Int = 9
add9 ∆ _1 ∆ _2 ∆ _3 ∆ _4 ∆ _5 ∆ _6 ∆ _7 ∆ _8 ∆ _9

Note that the more operators you string together, the faster the problem gets worse:

// 9 × 1 × 1 × 14 = 126 permutations
add1 ∆ 1

// 9 × 2 × 2 × 14 = 504 permutations
add2 ∆ 1 ∆ 2

// 9 × 3 × 3 × 14 = 1134 permutations
add3 ∆ 1 ∆ 2 ∆ 3
5 Likes

Proper currying really requires variadic generics. And, hopefully, a way to get unapplied mutating function references that can actually be used. i.e. of the type (inout T, Args...) -> R

1 Like

Moderator note: several posts here were moved from a re-posted thread