Bow {🏹️} Swift

2023, Apr 01    

🌈 Briefing of my tour in Bow: a functional programming library for swift. The project provides comprehensive implementation of functional programming concepts like kind, monad, applicative as well as common function programming techniques such as partial application, curry, memoizations.

📖 For people who want to learn systematic knowledge on functional programming, I do feel this project can be used as a swift version language guide book.

❓ To study the framework: Firstly the bow’s core compnent are throughly analysed, where common syntaxes, typical higher-kinded-types and patterns for functional programming are implemented using Swift. Then an example in nef is explored to see how the above framework is applied in real project. 👼

1. The Project 

The project contains mainly two layers:

  • Bow module act as the first layer, which provides all the core operators, protocols, common higher-kinded-types as well as techniques abstracted into forms of swift protocols.
  • The rest of modules act as the second layer, which further provides support of the Bow module to make the whole framework easier to use for different scenarios. Some typical candidates in these layers include:
    • BowEffect: provides a foundation to work with the side effects in a functional manner.
    • BowOptics: provides several utilities to work with immutable data structures, which enables easy access to getting, setting and modifying deeply nested data structure.

1.1 Bow

As I mentioned, most part of bow’s code falls in this part, hence to learn the framework we have to lean this module first.

$ tree -L 1 Bow
Bow
├── Arrow
├── Data
├── Instances
├── Syntax
├── Transformers
└── Typeclasses

Syntax: provides implementations on common functional programming techniques such as currying, partial application, reverse, memoization. But most importantly, introduced the concept of Kind. So you may ask, what is Kind? in regular programming paradigms, Types are used to create instances, here Kind is used to create Types(sounds like a meta class). 🦄️

/// Simulates a Higher-Kinded Type in Swift with 1 type argument.
///
/// This class simulates Higher-Kinded Type support in Swift. `Kind<F, A>` is an alias for `F<A>`, which is not syntactically valid in Swift.
/// Classes that want to have HKT support must extend this class. Type parameter `F` is reserved for a witness to prevent circular references in the inheritance relationship. By convention, witnesses are named like the class they represent, with the prefix `For`. As an example:
///
///     class ForOption {}
///     class Option<A>: Kind<ForOption, A> {}
open class Kind<F, A> {
    /// Default initializer
    public init() {}
}

/// Simulates a Higher-Kinded Type in Swift with 2 type arguments.
///
/// This class simulates Higher-Kinded Type support in Swift. `Kind2<F, A, B>` is an alias for `F<A, B>`, which is not syntactically valid in Swift.
/// Classes that want to have HKT support must extend this class. Type parameter `F` is reserved for a witness to prevent circular references in the inheritance relationship. By convention, witnesses are named like the class they represent, with the prefix `For`.
public typealias Kind2<F, A, B> = Kind<Kind<F, A>, B>

/// Yes, now you can guess how Kind3 is like: wrapping another layer of Kind with the new type C and Kind2
public typealias Kind3<F, A, B, C> = Kind<Kind2<F, A, B>, C>

Arrow: which contains all the scala typed functional programming arrow concepts, such as Kleisli, Cokleisli, Function, LazyFunction. The concept Function here refers to both ordinary functions processing on types as well as functions processing on higher-kinded-types(aka Kind).

So what is a Kleisli? it is a specific type of wrapper of functions that return a monadic value (if you dont know what is a monadic value🃏, please checkout my previous article). Then why Kleisli? because you can not directly compose two functions that return monadic values directly, but you can compose two Kleisli. The Swift version of Kleisli is implemented below:

/// Witness for the `Kleisli<F, D, A>` data type. To be used in simulated Higher Kinded Types.
public final class ForKleisli {}

/// Partial application of the Kleisli type constructor, omitting the last parameter.
public final class KleisliPartial<F, D>: Kind2<ForKleisli, F, D> {}

/// Higher Kinded Type alias to improve readability over `Kind<KleisliPartial<F, D>, A>`.
public typealias KleisliOf<F, D, A> = Kind<KleisliPartial<F, D>, A>

/// Kleisli represents a function with the signature `(D) -> Kind<F, A>`.
public final class Kleisli<F, D, A>: KleisliOf<F, D, A> {
    internal let f: (D) -> Kind<F, A>

    /// Initializes a Kleisli value.
    ///
    /// - Parameter run: Closure to be wrapped in this Kleisli.
    public init(_ f: @escaping (D) -> Kind<F, A>) {
        self.f = f
    }

    /// Inkoves this Kleisli function with an input value.
    ///
    /// - Parameter value: Input to the function.
    /// - Returns: Output of the Kleisli.
    public func run(_ value: D) -> Kind<F, A> {
        f(value)
    }

    /// Transforms the result of this Kleisli function.
    ///
    /// - Parameter f: Transforming function.
    /// - Returns: A Kleisli function that behaves as the original one, with its result transformed.
    public func transformT<G, B>(_ f: @escaping (Kind<F, A>) -> Kind<G, B>) -> Kleisli<G, D, B> {
        Kleisli<G, D, B>(self.f >>> f)
    }

    /// Where the >>> is the compose function:
    /// Composes a 1-ary function with a 1-ary function.
    ///
    /// Returns a function that is the result of applying `g` to the output of `f`.
    ///
    /// - Parameters:
    ///   - g: Left-hand side of the function composition.
    ///   - f: Right-hand side of the function composition.
    /// - Returns: A function that applies `g` to the output of `f`.
    public func >>><A, B, C>(_ f: @escaping (A) throws -> B, _ g: @escaping (B) -> C) -> (A) throws -> C {
        { x in g(f(x)) }
    }
}

Typeclasses: Well actually not as what the name indicates, it is purely the protocol definitions and their extensions for functional programming concepts such as functor, applicative, monad. Protocols are further implemented in Data Types. (Will talk later right after this.)

/// A Functor provides a type with the ability to transform its value type into another type, while preserving its structure.
///
/// Using the encoding for HKTs in Bow, in the type `Kind<F, A>`, `A` is the value type and `F` represents the structure of the type. An instance of `Functor` for `F` allows to transform `A` into another type, while maintaining `F` unchanged.
public protocol Functor: Invariant {
    /// Creates a new value transforming the type using the provided function, preserving the structure of the original type.
    ///
    /// The implementation of this function must obey two laws:
    ///
    /// 1. Preserve identity:
    ///
    ///         map(fa, id) == fa
    ///
    /// 2. Preserve composition:
    ///
    ///         map(map(fa, f), g) == map(fa, compose(g, f))
    ///
    /// - Parameters:
    ///   - fa: A value in the context of the type implementing this instance of `Functor`.
    ///   - f: A transforming function.
    /// - Returns: The result of transforming the value type using the provided function, maintaining the structure of the original value.
    static func map<A, B>(
        _ fa: Kind<Self, A>,
        _ f: @escaping (A) -> B) -> Kind<Self, B>
}

The above functor protocol is further implemented in various data types provided in bow. For example, in Either

/// Witness for the `Either<A, B>` data type. To be used in simulated Higher Kinded Types.
public final class ForEither {}

/// Partial application of the Either type constructor, omitting the last parameter.
public final class EitherPartial<L>: Kind<ForEither, L> {}

/// Partial application, function application
extension EitherPartial: Functor {
    public static func map<A, B>(
        _ fa: EitherOf<L, A>,
        _ f: @escaping (A) -> B) -> EitherOf<L, B> {
        fa^.fold(Either.left, Either.right <<< f)
    }
}

// where <<<
/// Composes a 0-ary function with a 1-ary function.
///
/// Returns a function that is the result of applying `g` to the output of `f`.
///
/// - Parameters:
///   - g: Left-hand side of the function composition.
///   - f: Right-hand side of the function composition.
/// - Returns: A function that applies `g` to the output of `f`.
public func <<<<A, B>(_ g: @escaping (A) -> B, _ f: @escaping () -> A) -> () -> B {
    f >>> g
}

Data Types: regular data types which follows the functional programming protocols defined in Typeclass.There are two categories of data types, the first such as Either, Day, Option. The second which provides wrapper for the Kind style HKT use cases, such as: EitherK. By comparing their declaration, you will see the differences:


// MARK: - EitherK

/// Witness for the `EitherK<F, G, A>` data type. To be used in simulated Higher Kinded Types.
public final class ForEitherK {}

/// Partial application of the EitherK type constructor, omitting the last parameter.
public final class EitherKPartial<F, G>: Kind2<ForEitherK, F, G> {}

/// Higher Kinded Type alias to improve readability over `Kind<EitherKPartial<F, G>, A>`.
public typealias EitherKOf<F, G, A> = Kind<EitherKPartial<F, G>, A>

/// EitherK is a sum type for kinds. Represents a type where you can hold either a `Kind<F, A>` or a `Kind<G, A>`.
public final class EitherK<F, G, A>: EitherKOf<F, G, A> {
    fileprivate let run: Either<Kind<F, A>, Kind<G, A>>
}

// MARK: - Either

/// Witness for the `Either<A, B>` data type. To be used in simulated Higher Kinded Types.
public final class ForEither {}

/// Partial application of the Either type constructor, omitting the last parameter.
public final class EitherPartial<L>: Kind<ForEither, L> {}

/// Higher Kinded Type alias to improve readability over `Kind2<ForEither, A, B>`
public typealias EitherOf<A, B> = Kind<EitherPartial<A>, B>

/// Sum type of types `A` and `B`. Represents a value of either one of those types, but not both at the same time. Values of type `A` are called `left`; values of type `B` are called right.
public final class Either<A, B>: EitherOf<A, B> {
    fileprivate let value: _Either<A, B>
}

1.2 BowEffect

Now since we already go through the core module structure, now let’s take a look at the effect handling layer of bow. Imagine there is a network call function and a print function, you want to invoke the print function inside of the network function, usually it is hard to compose the two function directly:

func greet(name: String) {
    print("Hello \(name)!")
}

func homePage(callback: @escaping (Either<Error, Data>) -> ()) {
    if let url = URL(string: "https://bow-swift.io") {
        URLSession.shared.dataTask(with: url) { data, _, error in
            if let data = data {
                callback(.right(data))
            } else if let error = error {
                callback(.left(error))
            }
        }.resume()
    }
}

To resolve the problem, the two function can be warpped as:

func greetIO(name: String) -> IO<Never, Void> {
    return IO.invoke { greet(name: name) }
}

func homePageIO() -> IO<Error, Data> {
    return IO.async { callback in
        if let url = URL(string: "https://bow-swift.io") {
            URLSession.shared.dataTask(with: url) { data, _, error in
                if let data = data {
                    callback(.right(data))
                } else if let error = error {
                    callback(.left(error))
                }
            }.resume()
        }
    }^
}

Now the two function can be composed via:

let result: IO<Never, Void> = homePageIO().flatMap { data in greetIO("done") }

The flowMap is provided in IO, where the IO is actually a data class of:

public typealias IOOf<E: Error, A> = Kind<IOPartial<E>, A>

And for IOPartial<E> acting as the F, we have the IOPartial version of Monad implementation:

// MARK: Instance of Monad for IO
extension IOPartial: Monad {
    public static func flatMap<A, B>(
        _ fa: IOOf<E, A>,
        _ f: @escaping (A) -> IOOf<E, B>) -> IOOf<E, B> {
        Join(fa^.map { x in f(x)^ }^)
    }

    public static func tailRecM<A, B>(
        _ a: A,
        _ f: @escaping (A) -> IOOf<E, Either<A, B>>) -> IOOf<E, B> {
        f(a)^.flatMap { either in
            either.fold({ a in tailRecM(a, f) },
                        { b in IO.pure(b) })
        }
    }
}

2. The Demo

Now let’s come to the real world example, the nef-plugin. The plugin calls up a Mac client App named nef, for each url scheme action, a corresponding controller is initialized. And all the controller conforms to the runAsync protocol. Internally it uses IO kind to handle asynchronous function calls.

struct NotificationConfig {
    let openPanel: OpenPanel
}

class ImageNotificationController: NefController {
    let image: Data
    let code: String
    let action: String
    let config: NotificationConfig

    init?(userInfo: [String: Any], action: String, openPanel: OpenPanel) {
        guard let image = userInfo[NefNotification.UserInfoKey.imageData] as? Data,
              let code = userInfo[NefNotification.UserInfoKey.description] as? String else { return nil }
        self.image = image
        self.code = code
        self.action = action
        self.config = .init(openPanel: openPanel)
    }

    func runAsync(completion: @escaping (Result<Void, Swift.Error>) -> Void) {
        runIO(image: image, code: code, action: action).provide(config)
            .map(Browser.showFile)^
            .unsafeRunAsyncResult(completion: completion)
    }

    func runIO(image: Data, code: String, action: String) -> EnvIO<NotificationConfig, NefNotification.Error, URL> {
        processNotification(image: image, code: code, action: action)
            .flatMap(clipboardFile)^
    }

    private func processNotification(image: Data, code: String, action: String) -> EnvIO<NotificationConfig, NefNotification.Error, NefNotification.Response> {
        switch action {
        case NefNotification.Action.saveImage.identifier:
            return persistImageClipboard(image: image, code: code)
        case NefNotification.Action.cancel.identifier:
            return EnvIO.pure(.dismiss)^
        default:
            return EnvIO.raiseError(.unsupportedAction)^
        }
    }

    private func persistImageClipboard(image: Data, code: String) -> EnvIO<NotificationConfig, NefNotification.Error, NefNotification.Response> {
        image.persist(command: .exportSnippetToClipboard(selection: code))
             .contramap(\.openPanel)
             .mapError { _ in .persistImage }.map { .saveImage($0) }^
    }

    private func clipboardFile(response: NefNotification.Response) -> EnvIO<NotificationConfig, NefNotification.Error, URL> {
        EnvIO.invoke { config in
            guard case let .saveImage(url) = response else {
                throw NefNotification.Error.noImageData
            }
            return url
        }^
    }
}

Here, we will pick up several things for highlights, actually both of the following highlights are from the code block:


func runAsync(completion: @escaping (Result<Void, Swift.Error>) -> Void) {
    runIO(image: image, code: code, action: action).provide(config)
        .map(Browser.showFile)^
        .unsafeRunAsyncResult(completion: completion)
}

2.1 Conversion between EnvIO types

now, lets look at the .map function first, the function is provided by IOPartial: Functor, the f here refers to Browser.showFile, which is a normal function irrelevant to bow: public static func showFile(_ file: URL).

// MARK: Instance of Functor for IO
extension IOPartial: Functor {
    public static func map<A, B>(
        _ fa: IOOf<E, A>,
        _ f: @escaping (A) -> B) -> IOOf<E, B> {
        FMap(f, fa^)
    }
}

The return class here FMap(f, fa^) is just a wrapper on the current execution and the f. So the FMAP’s _unsafeRunSyncEither is triggering the action’s _unsafeRunSyncEither method. If map /flatMap is called multiple times, the function is nested, and eventually map with action value with the function f.

internal class FMap<E: Error, A, B>: IO<E, B> {
    let f: (A) -> B
    let action: IO<E, A>

    init(_ f: @escaping (A) -> B, _ action: IO<E, A>) {
        self.f = f
        self.action = action
    }

    override internal func _unsafeRunSyncEither(on queue: Queue = .queue()) -> Trampoline<(Either<E, B>, Queue)> {
        .defer {
            self.action._unsafeRunSyncEither(on: queue).map { result in
                (self.on(queue: result.1) { result.0.map(self.f)^ }, result.1)
            }^
        }
    }
}

So where the _unsafeRunSyncEither get triggered? Yes, from unsafeRunAsyncResult(), in nef, there is a extension for IO:

extension IO {
    func unsafeRunAsyncResult(
      on queue: DispatchQueue = .main,
      completion: @escaping (Result<A, Swift.Error>) -> Void
      ) {
        unsafeRunAsync(on: queue) { either in
            completion(either.toResult().eraseError())
        }
    }
}

2.2 Async execution of EnvIO

Finally, let’s take a look at some other details in the unsafeRunAsync call. From Section 2.1, we see that actually for IO type, all the executions are defered, until the async/unsafeRunAsync call. In the method signature _unsafeRunSyncEither(on queue: Queue = .queue()) -> Trampoline<(Either<E, B>, Queue)>, we can see the function returns the Type Trampoline. The class caches the function execution in it’s value, and when the external unsafeRunAsync get called, the most outside layer of Trampoline instance is called for run. So the layers of trampoline instances are called run recursively. (please refer to the while clause in the run function).


/// The Trampoline type helps us overcome stack safety issues of recursive calls by transforming them into loops.
public final class Trampoline<A>: TrampolineOf<A> {
    fileprivate init(_ value: _Trampoline<A>) {
        self.value = value
    }

    fileprivate let value: _Trampoline<A>
    /// Creates a Trampoline that does not need to recurse and provides the final result.
    ///
    /// - Parameter value: Result of the computation.
    /// - Returns: A Trampoline that provides a value and stops recursing.
    public static func done(_ value: A) -> Trampoline<A> {
        Trampoline(.done(value))
    }

    /// Creates a Trampoline that performs a computation and needs to recurse.
    ///
    /// - Parameter f: Function describing the recursive step.
    /// - Returns: A Trampoline that describes a recursive step.
    public static func `defer`(_ f: @escaping () -> Trampoline<A>) -> Trampoline<A> {
        Trampoline(.defer(f))
    }

    /// Creates a Trampoline that performs a computation in a moment in the future.
    ///
    /// - Parameter f: Function to compute the value wrapped in this Trampoline.
    /// - Returns: A Trampoline that delays the obtention of a value and stops recursing.
    public static func later(_ f: @escaping () -> A) -> Trampoline<A> {
        .defer { .done(f()) }
    }

    /// Executes the computations described by this Trampoline by converting it into a loop.
    ///
    /// - Returns: Value resulting from the execution of the Trampoline.
    public final func run() -> A {
        var trampoline = self
        while true {
            let step = trampoline.step()
            if step.isLeft {
                trampoline = step.leftValue()
            } else {
                return step.rightValue
            }
        }
    }

    internal func step() -> Either<() -> Trampoline<A>, A> {
        value.step()
    }
}

3. Thoughts After Reading

Overall, this framework is quite eye openning and provides me some new ideas in future coding. But there are several things which makes me feel worth to rethink about:

3.1 Nature of Async

How does the above IO module support suspended asynchronous programming?

In programming paradigms, this is like a recursive builder, and when the asyncRun called, the previously recusive structure is executed layer by layer.

3.2 Fundamental Characters of Bow

What are the core idea behind all these implementations in the bow framework?

As what mentioned in the old day school books: composition and cascading call support.

Seems to be a nice framework but why only 600 stars in github?

There is definitely a learning curve for this framework and yet there is no sufficient tutorials for it. Taking myself as an example for users who occasionally wants to explore the framework. I have to learn quite a lot of parts of it from reading the source code and an external opensource project which applies it.

In the meanwhile, there are some other alternatives framework which provides similar functionality but easier readability, such as RXSwift. And since iOS 13.0, the system already officially supports the usage of Combine which provides strong traits in functional programming as well. The competition between multiple candidate exists and this framework simply lacks enough of support to win it.

4. References

Twitter
# ios # design
TOC