Symbolic derivative in Swift

Question

I just wrote my first Swift program! It is a little computer algebra test that computes the nth derivative of the symbolic expression \$x^x\$. I chose this example because I'm keen to see how ARC will cope with the density of pointers in the heap.

Seeing as I'm completely new to this language I'd appreciate some feedback, especially along the lines of:

1. Is this idiomatic or are there stylistic changes I should be making?
2. Can I coalesce some of the switch cases that have the same rhs, as you do in other languages using a "or pattern"?
3. Am I doing anything stupid with regards to memory management? Are there any obvious ways to reduce the memory consumption, short of changing the algorithm?
4. Have I done anything obviously inefficient?

enum Expr {
  case Int(n: Int)
  case Var(x: String)
  indirect case Add(f: Expr, g: Expr)
  indirect case Mul(f: Expr, g: Expr)
  indirect case Pow(f: Expr, g: Expr)
  indirect case Ln(f: Expr)
}

func pown(a: Int, b: Int) -> Int {
  switch (b) {
    case 0 : return 1
    case 1 : return a
    case let n :
      let b = pown(a: a, b: n / 2)
      return b * b * (n % 2 == 0 ? 1 : a)
  }
}

func add(f: Expr, g: Expr) -> Expr {
  switch (f, g) {
    case (let .Int(n: m), let .Int(n: n)) : return .Int(n: m + n)
    case (.Int(n: 0), let f) : return f
    case (let f, .Int(n: 0)) : return f
    case (let f, let .Int(n)) : return add(f: .Int(n: n), g: f)
    case (let f, let .Add(.Int(n), g)) : return add(f: .Int(n: n), g: add(f: f, g: g))
    case (let .Add(f, g), let h) : return add(f: f, g: add(f: g, g: h))
    case (let f, let g) : return .Add(f: f, g: g)
  }
}

func mul(f: Expr, g: Expr) -> Expr {
  switch (f, g) {
    case (let .Int(n: m), let .Int(n: n)) : return .Int(n: m * n)
    case (.Int(n: 0), _) : return .Int(n: 0)
    case (_, .Int(n: 0)) : return .Int(n: 0)
    case (.Int(n: 1), let f) : return f
    case (let f, .Int(n: 1)) : return f
    case (let f, let .Int(n: n)) : return mul(f: .Int(n: n), g: f)
    case (let f, let .Mul(.Int(n: n), g)) : return mul(f: .Int(n: n), g: mul(f: f, g: g))
    case (let .Mul(f: f, g: g), let h) : return mul(f: f, g: mul(f: g, g: h))
    case (let f, let g) : return .Mul(f: f, g: g)
  }
}

func pow(f: Expr, g: Expr) -> Expr {
  switch (f, g) {
    case (let .Int(n: m), let .Int(n: n)) : return .Int(n: pown(a: m, b: n))
    case (_, .Int(n: 0)) : return .Int(n: 1)
    case (let f, .Int(n: 1)) : return f
    case (.Int(n: 0), _) : return .Int(n: 0)
    case (let f, let g) : return .Pow(f: f, g: g)
  }
}

func ln(f: Expr) -> Expr {
  switch (f) {
    case .Int(n: 1) : return .Int(n: 0)
    case let f : return .Ln(f: f)
  }
}

func d(x: String, f: Expr) -> Expr {
  switch (f) {
    case .Int(n: _) : return .Int(n: 0)
    case let .Var(x: y) : if x == y { return .Int(n: 1) } else { return .Int(n: 0) }
    case let .Add(f: f, g: g) : return add(f: d(x: x, f: f), g: d(x: x, f: g))
    case let .Mul(f: f, g: g) : return add(f: mul(f: f, g: d(x: x, f: g)), g: mul(f: g, g: d(x: x, f: f)))
    case let .Pow(f: f, g: g) : return mul(f: pow(f: f, g: g), g: add(f: mul(f: mul(f: g, g: d(x: x, f: f)), g: pow(f: f, g: .Int(n: -1))), g: mul(f: ln(f: f), g: d(x: x, f: g))))
    case let .Ln(f: f) : return mul(f: d(x: x, f: f), g: pow(f: f, g: .Int(n: -1)))
  }
}

func count(f: Expr) -> Int {
  switch (f) {
    case .Int(n: _) : return 1
    case .Var(x: _) : return 1
    case let .Add(f: f, g: g) : return count(f: f) + count(f: g)
    case let .Mul(f: f, g: g) : return count(f: f) + count(f: g)
    case let .Pow(f: f, g: g) : return count(f: f) + count(f: g)
    case let .Ln(f: f) : return count(f: f)
  }
}

func stringOfExpr(f: Expr) -> String {
  switch (f) {
    case let .Int(n: n) : return String(n)
    case let .Var(x: x) : return x
    case let .Add(f: f, g: g) : return "(" + stringOfExpr(f: f) + " + " + stringOfExpr(f: g) + ")"
    case let .Mul(f: f, g: g) : return "(" + stringOfExpr(f: f) + " * " + stringOfExpr(f: g) + ")"
    case let .Pow(f: f, g: g) : return "(" + stringOfExpr(f: f) + "^" + stringOfExpr(f: g) + ")"
    case let .Ln(f: f) : return "ln(" + stringOfExpr(f: f) + ")"
  }
}

func stringOf(f: Expr) -> String {
  let n = count(f: f)
  if n > 100 {
    return "<<" + String(n) + ">>"
  } else {
    return stringOfExpr(f: f)
  }
}

let x = Expr.Var(x: "x")

let f = pow(f: x, g: x)

func nest(n: Int, f: ((Expr) -> Expr), x: Expr) -> Expr {
  if n == 0 { return x } else {
    return nest(n: n-1, f: f, x: f(x))
  }
}

var dx = { (f: Expr) -> Expr in
  var df = d(x: "x", f: f)
  print("D(" + stringOf(f: f) + ") = " + stringOf(f: df))
  return df
}

var n = Int(CommandLine.arguments[1])

print(count(f: nest(n: n!, f: dx, x: f)))

Answer 1

Here are some suggestions for stylistic and idiomatic changes and simplifications.

Naming the enumeration cases

The enumeration cases should be lowercase, according to the Swift API Design Guidelines:

Names of types and protocols are UpperCamelCase. Everything else is lowerCamelCase.

var is a keyword, therefore it must be quoted in the enum definition (but only there). Alternatively choose a different name, e.g. variable.

IMO const describes the first case better than int, and sum, prod (or product) is a better than add and mul.

I also would omit the labels ("n:", "x:", "f:", "g:"). They are somewhat arbitrary and the code is better readable without, e.g. in your add() function:

case (let .const(m), let .const(n)) : return .const(m + n)

instead of the original

case (let .Int(n: m), let .Int(n: n)) : return .Int(n: m + n)

The definition would then look like this:

enum Expr {
    case const(Int)
    case `var`(String)
    indirect case sum(Expr, Expr)
    indirect case prod(Expr, Expr)
    indirect case power(Expr, Expr)
    indirect case ln(Expr)
}

---

Use properties (or methods) where appropriate

You have a global function

func count(f: Expr) -> Int { ... }

which returns the number of terms in the given expression. This is a property of that expression, and therefore better modelled as a computed property:

enum Expr {
    // ...

    var count: Int { // ... // }
}

or instance method:

enum Expr {
    // ...

    func count() -> Int { // ... // }
}

There are different opinions when to choose which, see for example

• Swift functions vs computed properties
• Computed read-only property vs function in Swift

I would choose a (read-only) computed property here, similar to the count property of Swift Collections.

---

Coalesce cases in switch statements

Cases which bind the same set of variables (or bind no variables at all) can be coalesced together in a switch statement.

Applied to the count we get

enum Expr {
    // ...

    var count: Int {
        switch self {
        case .const, .var:
            return 1
        case let .sum(f, g), let .prod(f, g), let .power(f, g):
            return f.count + g.count
        case let .ln(f):
            return f.count
        }
    }
}

Note also that no "wildcard binding" is needed in the first two cases.

---

Make use of existing protocols

Your function

func stringOfExpr(f: Expr) -> String { ... }

returns a textual description of an expression.

Swift already defines a CustomStringConvertible protocol with a description property for this purpose, which is also used in print() statements and string interpolation, therefore I would define

extension Expr: CustomStringConvertible {
    var description: String {
        switch self {
        case let .const(n) : return String(n)
        case let .var(x) : return x
        case let .sum(f, g) : return "(\(f) + \(g)"
        case let .prod(f, g) : return "(\(f) * \(g)"
        case let .power(f, g) : return "(\(f)^\(g)"
        case let .ln(f) : return "ln(\(f))"
        }
    }
}

instead. Note how string interpolation makes the expression more concise and readable, compared to your original

case let .Add(f: f, g: g) : return "(" + stringOfExpr(f: f) + " + " + stringOfExpr(f: g) + ")"

Now expressions can be passed directly as argument to the print() function, or used in string interpolation. Example:

let f: Expr = .sum(.var("x"), .const(2))
print(f) // (x + 2)
print("derivative = \(d(f, "x"))") // derivative = 1

---

More suggestions

Omit the argument labels in the functions

func add(_ f: Expr, _ g: Expr) -> Expr
func mul(_ f: Expr, _ g: Expr) -> Expr
func pow(_ f: Expr, _ g: Expr) -> Expr
func ln(_ f: Expr) -> Expr

As with the labels in the enum definition, they have no meaning, and the calling code becomes better readable without them.

Define custom operators

extension Expr {
    static func +(_ f: Expr, _ g: Expr) -> Expr { return add(f, g) }
    static func *(_ f: Expr, _ g: Expr) -> Expr { return mul(f, g) }
    static func ^(_ f: Expr, _ g: Expr) -> Expr { return pow(f, g) }
}

so that you can write f + g, f * g etc instead of add(f, g), mul(f, g).