Recursive type definitions for functions

Evolution Pitches
1

Currently recursive type definitions for functions are not allowed.

If they were allowed, writing type-safe code for state machines would become much easier and simpler. The basic technique is to represent each state with a unique function which returns either itself or other function as the next state. This would eliminate the need to rely on enums or to subclass a root class.

Some examples follow to demonstrate the technique.

State Machines with Free Functions
Implementing a state machine with free functions requires defining a type for a free function returning itself or other free function with the same signature:

typealias Function = (OptionalArgTypeList) -> Function

Example F.1: Ideal but not possible

// Ideal but not possible
//
typealias State = () -> State  // error: Type alias State references itself

func state1 () -> State {
    print ("-->", #function)
    return state1
}

func state2 () -> State {
    print ("-->", #function)
    return state2
}

// Helper function
func run (_ f:State) -> State {
    return f ()
}

// test drive
let s1 = state1 ();
let s2 = run (s1)  // s2 = s1 ()
let s3 = run (s2)  // s3 = s2 ()

Example F.2: Possible but not type safe

// Possible but not type safe
//
typealias State = Any

func state1 () -> State {
    print ("-->", #function)
    return state2
}

func state2 () -> State {
    print ("-->", #function)
    return state1
}

// Helper function
func run (_ f:State) -> State {
    let ff = f as! (() -> Any)
    return ff ()
}

State Machines with Member Functions
Implementing a state machine with member functions requires defining a type for a member function returning itself or other member function with the same signature:

typealias Function = (ClassOrStructType)(OptionalArgTypeList) -> Function

Example M.1: Ideal but not possible

// Ideal but not possible
//
struct SM {
    typealias State = (Self) -> (() -> State) // error: Type alias State references itself
    
    func state1 () -> State {
        print ("--> \(type (of:self)) \(#function)")
        return Self.state2
    }
    
    func state2 () -> State {
        print ("--> \(type (of:self)) \(#function)")
        return Self.state1
    }
    
    // helper function
    func run (_ f:State) -> State {
        return f (self)()
    }
}

// Test drive
let sm = SM ()
let s1 = sm.state1 ()
let s2 = sm.run (s1) // s2 = s1 (sm)()
let s3 = sm.run (s2) // s3 = s2 (sm)()

Example M.2: Possible but not type safe

// Possible but not type safe
//
struct SM {
    typealias State = Any

    func state1 () -> State {
        print ("--> \(type (of:self)) \(#function)")
        return Self.state2
    }
    
    func state2 () -> State {
        print ("--> \(type (of:self)) \(#function)")
        return Self.state1
    }
    
    // helper function
    func run (_ f:State) -> State {
        let ff = f as! ((Self)->()->State)
        return ff (self)()
    }
}

Why can't the compiler accept this recursive type definition?

typealias State = () -> State // error: Type alias State references itself

Are there any technical barriers?

2 Likes
2

Don't know why it is not allowed (and/or if it should) but you can do what you want via enum in a type safe manner:

enum TheState {
    // case halt - if you want to have the "terminal node"
    case function(() -> TheState)
}
3

Would a type which defines a callAsFunction() -> Self member work?

3 Likes
4

What’s wrong with using enums for the purpose? They’re extremely suitable for it, especially in combination with the aforementioned callAsFunction() -> Self.

You could even use associated values to restrict functions to specific states, among other things. And all that while being phenomenally efficient and safe.

5

I think it's an interesting idea. The compiler would have to prevent you from using the recursive syntax in a context where the type isn't indirect, and I'm not sure how it would behave in some cases anyway:

typealias Oops1 = Oops1?  // definitely not legal
typealias Oops2 = (Oops2) // very problematic at least
typealias What = [What] // is this legal?...

but used in function types, AFAICT, it would be safe?

6

Very, very few programming languages support infinite types, which add an extraordinary amount of language and implementation complexity for remarkably little benefit. I'm sorry to be abrupt like this, but you should read the literature on this subject if you're interested in understanding it better.

5 Likes
7

Thank you all for the invaluable feedback provided!

Yes, an enum with associated data and with a callAsFunction () does the job quite nicely, with only a tiny amount of extra effort.

//
//  EnumStateMachine.swift - An example state machine implemented with enum
//
//

import Foundation

//
// -----------------------------------------------
//
struct EnumStateMachine {
    // Driver
    static func main () -> Void {
        let sm = SM ()
        var state = sm.startState ()
        while !state.isTerminal {
            state = state ()
        }
    }
}

// -----------------------------------------------
//
extension EnumStateMachine {
    // State function wrapper
    enum State {
        typealias Proc = SM.MemberFunction
        case terminal
        case function (SM, Proc)

        var isTerminal : Bool {
            switch self {
            case .terminal:
                return true
            case .function:
                return false
            }
        }
        
        func callAsFunction() -> Self {
            switch self {
            case .terminal:
                return self
            case .function (let o, let f):
                return f (o) ()
            }
        }
    }
}

// -----------------------------------------------
//
extension EnumStateMachine {
    // The State Machine
    class SM {
        typealias MemberFunction = (SM) -> (() -> State)
        
        var counter = 0
        
        // Helper functions
        //
        // wrap the instance and a member function in a State
        func state (_ f: @escaping MemberFunction) -> State {
            return .function (self, f)
        }
        
        // return the initial state
        func startState () -> State {
            counter = 0
            return state (SM.A)
        }
        
        // State functions
        //
        func A () -> State {
            counter += 1
            print ("--> \(type (of:self)): \(#function) \(counter)")
            return B ()
        }

        func B () -> State {
            counter += 1
            print ("--> \(type (of:self)): \(#function) \(counter)")
            return state (SM.C)
        }

        func C () -> State {
            counter += 1
            print ("--> \(type (of:self)): \(#function) \(counter)")
            return state (SM.D)
        }

        func D () -> State {
            counter += 1
            print ("--> \(type (of:self)): \(#function) \(counter)")
            if counter > 8 {
               return ZZZ ()
            }
            else {
                return state (SM.B)
            }
        }
        
        func ZZZ () -> State {
            counter += 1
            print ("--> \(type (of:self)): \(#function) \(counter)")
            return .terminal
        }
    }
}
2 Likes