Memoization for functions without parameters in enums


(Tierry Hörmann) #1

Hi all

I discovered that memoization is currently a pain to implement when using functional programming.
E.g. when implementing a lazy linked list, one obviously uses an enum to represent the data. But there is also a wrapper struct needed with lazy variables (especially a lazy property tail), as enums can not have stored properties. Here some example code of such a lazy linked list:

public struct LazyList<T> {
    let root: LLE<T>
    
    init(_ root: LLE<T> = LLE<T>.End) {
        self.root = root
    }
    
    public var hd: T? {
        get {return root.val()}
    }
    
    lazy private var tail: LLE<T> = self.root.tail()()
    public var tl: LazyList<T> {
        mutating get {
            return LazyList<T>(tail)
        }
    }
}

enum LLE<T> {
    case End
    indirect case Node(T, () -> LLE<T>, Int)
    
    func val() -> T? {
        switch self {
        case let .Node(v, _, _):
            return v
        default:
            return nil
        }
    }
    
    func tail() -> () -> LLE<T> {
        switch self {
        case let .Node(_, tl, _):
            return tl
        default:
            assert(false, "Can't call tail on empty list")
            return {self}
        }
    }
}

In my opinion this isn’t optimal (and can also create bigger problems, e.g. when implementing count). But enums in swift are purely functional and therefore functions without parameters always return the same value in an enum, so storing the result of a function call with no parameters could in some situations give a great performance boost.
Has this issue already been discussed? If yes, what was the outcome? And if no, I would suggest an additional keyword “memoizing” for functions without parameters in enums. Or maybe someone has a better idea, which would fit better inside the swift universe?

Greetings
Tierry Hoermann


(David Sweeris) #2

Hi all

I discovered that memoization is currently a pain to implement when using functional programming.
E.g. when implementing a lazy linked list, one obviously uses an enum to represent the data. But there is also a wrapper struct needed with lazy variables (especially a lazy property tail), as enums can not have stored properties. Here some example code of such a lazy linked list:

public struct LazyList<T> {
    let root: LLE<T>
    
    init(_ root: LLE<T> = LLE<T>.End) {
        self.root = root
    }
    
    public var hd: T? {
        get {return root.val()}
    }
    
    lazy private var tail: LLE<T> = self.root.tail()()
    public var tl: LazyList<T> {
        mutating get {
            return LazyList<T>(tail)
        }
    }
}

enum LLE<T> {
    case End
    indirect case Node(T, () -> LLE<T>, Int)
    
    func val() -> T? {
        switch self {
        case let .Node(v, _, _):
            return v
        default:
            return nil
        }
    }
    
    func tail() -> () -> LLE<T> {
        switch self {
        case let .Node(_, tl, _):
            return tl
        default:
            assert(false, "Can't call tail on empty list")
            return {self}
        }
    }
}

In my opinion this isn’t optimal (and can also create bigger problems, e.g. when implementing count). But enums in swift are purely functional and therefore functions without parameters always return the same value in an enum, so storing the result of a function call with no parameters could in some situations give a great performance boost.
Has this issue already been discussed? If yes, what was the outcome? And if no, I would suggest an additional keyword “memoizing” for functions without parameters in enums. Or maybe someone has a better idea, which would fit better inside the swift universe?

We've talked about "pure" functions (a prerequisite for memoization) a few times. Usually around the time we start talking about which definition of "pure" we want to use, someone will come by and say it's out of scope. IIRC, the last time it happened was after we started discussing Swift 4, so I'd guess it's still out of scope.

- Dave Sweeris

···

Sent from my iPhone

On Apr 25, 2017, at 06:44, Tierry Hörmann via swift-evolution <swift-evolution@swift.org> wrote:


(Xiaodi Wu) #3

Well, first, let's address some misconceptions in Tierry's email:

"Enums in swift are purely functional and therefore functions without
parameters always return the same value in an enum"...is not true. A
function without parameters can have any amount of side effects and can
return a random value or a copy of a global variable.

There are some nice designs out there for memoization in Swift. I recall
one in the excellent Advanced Swift, but I could be remembering another
source. I'd suggest a discussion on swift-users.

But yes, pure functions are some ways off.

···

On Tue, Apr 25, 2017 at 12:19 David Sweeris via swift-evolution < swift-evolution@swift.org> wrote:

Sent from my iPhone

On Apr 25, 2017, at 06:44, Tierry Hörmann via swift-evolution < > swift-evolution@swift.org> wrote:

Hi all

I discovered that memoization is currently a pain to implement when using
functional programming.
E.g. when implementing a lazy linked list, one obviously uses an enum to
represent the data. But there is also a wrapper struct needed with lazy
variables (especially a lazy property tail), as enums can not have stored
properties. Here some example code of such a lazy linked list:

public struct LazyList<T> {
    let root: LLE<T>

    init(_ root: LLE<T> = LLE<T>.End) {
        self.root = root
    }

    public var hd: T? {
        get {return root.val()}
    }

    lazy private var tail: LLE<T> = self.root.tail()()
    public var tl: LazyList<T> {
        mutating get {
            return LazyList<T>(tail)
        }
    }
}

enum LLE<T> {
    case End
    indirect case Node(T, () -> LLE<T>, Int)

    func val() -> T? {
        switch self {
        case let .Node(v, _, _):
            return v
        default:
            return nil
        }
    }

    func tail() -> () -> LLE<T> {
        switch self {
        case let .Node(_, tl, _):
            return tl
        default:
            assert(false, "Can't call tail on empty list")
            return {self}
        }
    }
}

In my opinion this isn’t optimal (and can also create bigger problems,
e.g. when implementing count). But enums in swift are purely functional and
therefore functions without parameters always return the same value in an
enum, so storing the result of a function call with no parameters could in
some situations give a great performance boost.
Has this issue already been discussed? If yes, what was the outcome? And
if no, I would suggest an additional keyword “memoizing” for functions
without parameters in enums. Or maybe someone has a better idea, which
would fit better inside the swift universe?

We've talked about "pure" functions (a prerequisite for memoization) a few
times. Usually around the time we start talking about which definition of
"pure" we want to use, someone will come by and say it's out of scope.
IIRC, the last time it happened was after we started discussing Swift 4, so
I'd guess it's still out of scope.

- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Tierry Hörmann) #4

That’s true, I also discovered the case, where the enum has a reference type as an associated value, which is then modified by a function. Such a function would clearly not be pure either, so a pure function should not be able to capture from a different scope and should not be able to access reference types. I see the problem there.
But with the workarounds for memoization there is still a problem with enums: As enums cannot have stored properties, it is not possible to create a constant closure in the enum. Isn’t this somehow a inconsistency that I can’t write

enum Test {
    let foo = {0}
}

but I can write

enum Test {
    func foo() -> Int {
        return 0
    }
}

For this I would have two possible solutions: Allow assigning to a function somehow like this:

func foo = {0}

Or allowing constants in enums as a constant would not be anything else than an associated type with a possible default value, which every case of the enum contains.

But I see this is out of scope for this discussion and I will look for other ways for memoization on swift-users.

Thanks
Tierry Hoermann

···

On 25 Apr 2017, at 19:47, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:

Well, first, let's address some misconceptions in Tierry's email:

"Enums in swift are purely functional and therefore functions without parameters always return the same value in an enum"...is not true. A function without parameters can have any amount of side effects and can return a random value or a copy of a global variable.

There are some nice designs out there for memoization in Swift. I recall one in the excellent Advanced Swift, but I could be remembering another source. I'd suggest a discussion on swift-users.

But yes, pure functions are some ways off.

On Tue, Apr 25, 2017 at 12:19 David Sweeris via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Sent from my iPhone

On Apr 25, 2017, at 06:44, Tierry Hörmann via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi all

I discovered that memoization is currently a pain to implement when using functional programming.
E.g. when implementing a lazy linked list, one obviously uses an enum to represent the data. But there is also a wrapper struct needed with lazy variables (especially a lazy property tail), as enums can not have stored properties. Here some example code of such a lazy linked list:

public struct LazyList<T> {
    let root: LLE<T>
    
    init(_ root: LLE<T> = LLE<T>.End) {
        self.root = root
    }
    
    public var hd: T? {
        get {return root.val()}
    }
    
    lazy private var tail: LLE<T> = self.root.tail()()
    public var tl: LazyList<T> {
        mutating get {
            return LazyList<T>(tail)
        }
    }
}

enum LLE<T> {
    case End
    indirect case Node(T, () -> LLE<T>, Int)
    
    func val() -> T? {
        switch self {
        case let .Node(v, _, _):
            return v
        default:
            return nil
        }
    }
    
    func tail() -> () -> LLE<T> {
        switch self {
        case let .Node(_, tl, _):
            return tl
        default:
            assert(false, "Can't call tail on empty list")
            return {self}
        }
    }
}

In my opinion this isn’t optimal (and can also create bigger problems, e.g. when implementing count). But enums in swift are purely functional and therefore functions without parameters always return the same value in an enum, so storing the result of a function call with no parameters could in some situations give a great performance boost.
Has this issue already been discussed? If yes, what was the outcome? And if no, I would suggest an additional keyword “memoizing” for functions without parameters in enums. Or maybe someone has a better idea, which would fit better inside the swift universe?

We've talked about "pure" functions (a prerequisite for memoization) a few times. Usually around the time we start talking about which definition of "pure" we want to use, someone will come by and say it's out of scope. IIRC, the last time it happened was after we started discussing Swift 4, so I'd guess it's still out of scope.

- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution