2017-06-28 21:33 GMT+09:00 Dimitri Racordon via swift-evolution < swift-evolution@swift.org>:
> Hello community! > > I’d like to pitch an idea for a user-friendly way for functions to pull > values from an arbitrary environment. Let me introduce the concept with a > motivational example before I dig into dirty syntax and semantics. Note > that I intentionally removed many pieces of code from my examples, but I > guess everybody will be able to understand the context. > > Say you are writing a visitor (with the pattern of the same name) for an > AST to implement an interpreter: > > class Interpreter: Visitor { > func visit(_ node: BinExpr) { /* ... */ } > func visit(_ node: Literal) { /* ... */ } > func visit(_ node: Scope) { /* ... */ } > func visit(_ node: Identifier) { /* ... */ } > } > > Although this design pattern is often recommended for AST processing, > managing data as we go down the tree can be cumbersome. The problem is that > we need to store all intermediate results as we climb up the tree in some > instance member, because we can’t use the return type of the visit(_:) method, > as we would do with a recursive function: > Why you can't use the return type? associatedtype doesn't solve the problem? protocol Visitor { associatedtype VisitResult func visit(_ node: BinExpr) throws -> VisitResult func visit(_ node: Literal) throws -> VisitResult func visit(_ node: Scope) throws -> VisitResult func visit(_ node: Identifier) throws -> VisitResult } extension BinExpr { func accept<V : Visitor>(_ visitor: V) throws -> V.VisitResult { return visitor.visit(self) } }extension Literal { func accept<V : Visitor>(_ visitor: V) throws -> V.VisitResult { return visitor.visit(self) } }extension Scope { func accept<V : Visitor>(_ visitor: V) throws -> V.VisitResult { return visitor.visit(self) } }extension Identifier { func accept<V : Visitor>(_ visitor: V) throws -> V.VisitResult { return visitor.visit(self) } } class Interpreter : Visitor { func visit(_ node: BinExpr) -> Int { let lhsResult = node.lhs.accept(self) let rhsResult = node.rhs.accept(self) /* ... */ return result } /* ... */ } > class Interpreter: Visitor { > func visit(_ node: BinExpr) { > node.lhs.accept(self) > let lhs = accumulator! > node.rhs.accept(self) > let rhs = accumulator! > /* ... */ > } > > func visit(_ node: Literal) { /* ... */ } > func visit(_ node: Scope) { /* ... */ } > func visit(_ node: Identifier) { /* ... */ } > > var accumulator: Int? = nil > > /* ... */ > } > > As our interpreter will grow and need more visitors to “return” a value, > we’ll be forced to add more and more stored properties to its definition. > Besides, the state of those properties is difficult to debug, as it can > quickly become unclear what depth of the tree they should be associated to. > In fact, it is as if all these properties acted as global variables. > > The problem gets even bigger when we need to *pass* variables to a > particular execution of a visit(_:). Not only do we need to add a stored > property to represent each “argument”, but we also have to store them in > stacks so that a nested calls to a particular visit can get their own > “evaluation context”. Consider for instance the implementation of the > visit(_ node: Identifier), assuming that the language our AST represents > would support lexical scoping. > How about returning curried function from visitor? class Interpreter : Visitor { typealias VisitResult = ([String:Int]) throws -> Int func visit(_ node: Identifier) throws -> VisitResult { return { symbols in guard let result = symbols[node.name] { throws UndefinedIdentifierError(node.name) } return result } } /* ... */ } > class Interpreter: Visitor { > /* ... */ > > func visit(_ node: Scope) { > symbols.append([:]) > for child in node.children { > child.accept(self) > } > symbols.removeLast() > } > > func visit(_ node: Identifier) { > accumulator = symbols.last![node.name]! > } > > var symbols = [[String: Int]]() > } > > We could instead create another instance of our visitor to set manage > those evaluation contexts. But that would require us to explicitly copy all > the variables associated to those contexts, which could potentially be > inefficient and error prone. > > In fact, this last point is also true when dealing with recursive > functions. For instance, our visit(_ node: Identifier) method could be > rewritten as: > > func interpret(_ identifier: Identifier, symbols: [String: Value]) -> Int > { /* ... */ } > > so that its evaluation context is passed as a parameter. But this also > requires all other functions to also pass this argument, even if their > execution does not require the parameter. > > func interpret(_ binExpr: BinExpr, symbols: [String: Value]) -> Int { > let lhs = interpret(node.lhs.accept, symbols: symbols) > /* ... */ > } > > This technique consisting of passing parameters through a function just so > that another function called deeper in the stack can get its variable is > actually quite common. Sadly, it clouds all signatures with many > parameters, which make it more difficult to reason about what a particular > function actually needs from its caller. Note also that this overuses the > running stack, putting many unnecessary values in all execution frames. > > The idea I’d like to pitch is to offer a mechanism to address this issue. > Namely, I’d like a way to provide a function with an environment when using > its parameter and/or return type is not an option, or when doing so would > add unnecessary complexity to its signature (like illustrated above). While > this mechanism would share similarities with how functions (and closures) > are able to capture variables when they are declared, it would differ in > the fact that these environment would depend on the execution frame prior > to that of a particular function call rather than the function > declaration/definition. > > First, one would declare a *contextual variable:* > > context var symbols: [String: Int]? > > Such contextual variables could be seen as stacks, whose values are typed > with that of the variable. In that particular example, the type of the > context symbols would be [String: Int]. The optional is needed to > explicitly represent the fact that a context may not always be set, but > this could be inferred as well. One would be able to set the value a > contextual variable, effectively pushing a value on the stack it represent, > before entering a new execution frame: > > set symbols = [:] in { > for child in node.children { > child.accept(self) > } > } > > In the above example, the contextual variable symbols would represent an > empty dictionary for all execution frames above that of the context scope > (delimited by braces). Extracting a value from a context would boils down > to reading an optional value: > > guard let val = symbols?[node.name] else { > fatalError("undefined symbol: \(node.name)") > } > accumulator = val > > You can do something like this: func saveAndRestore<T, R>(_ variable: inout T, _ tmpVal: T, body: () -> R) -> R { let savedVal = variable variable = tmpVal defer { variable = savedVal } return body() } class Interpreter : Visitor { var symbols: [String: Int] = [:] func visit(_ node: Scope) throws -> Int { return saveAndRestore(symbols, [:]) { for child in node.children { child.accept(this) } return 0 } } func visit(_ node: Identifier) throws -> Int { guard let result = symbols[node.name] { throws UndefinedIdentifierError(node.name) } return result } /* ... */ } And as contextual variables would actually be stacks, one could push > another value on the top of them to setup for another evaluation context. > Hence, would we call set symbols = [:] in { /* ... */ } again, the > contextual variable symbols would represent another empty dictionary as > long as our new context would be alive: > > set symbols = ["foo": 1] in { > set symbols = ["foo": 2] in { > print(symbols!["foo”]!) > // Prints 2 > } > print(symbols!["foo”]!) > // Prints 1 > } > > The advantage of that approach is threefold. > > 1. It lets us provide an environment to functions that can’t receive > more parameters or return custom values. This is particularly useful when > dealing with libraries that provide an entry to define custom behaviour, > but fix the API of the functions they expect (e.g. a visitor protocol). In > those instances, capture by closure is not always possible/desirable. > 2. In large function hierarchy, it lets us provide deep functions with > variables, without the need to pass them in every single function call just > in the off chance one function may need it deeper in the call graph. > 3. It better defines the notion of stacked environment, so that one > can “override” an execution context, which is often desirable when > processing recursive structures such as trees or graphs. In particular, it > is very useful when not all functions require all data that are passed down > the tree. > > > Using our contextual variables, one could rewrite our motivational example > as follows: > > class Interpreter: Visitor { > func visit(_ node: BinExpr) { > let lhs, rhs : Int > set accumulator = nil in { > node.lhs.accept(self) > lhs = accumulator! > } > set accumulator = nil in { > node.lhs.accept(self) > rhs = accumulator! > } > > switch node.op { > case "+": > accumulator = lhs + rhs > case "-": > accumulator = lhs - rhs > default: > fatalError("unexpected operator \(node.op)") > } > } > > func visit(_ node: Literal) { > accumulator = node.val > } > > func visit(_ node: Scope) { > set symbols = [:] in { > for child in node.children { > child.accept(self) > } > } > } > > func visit(_ node: Identifier) { > guard let val = symbols?[node.name] else { > fatalError("undefined symbol: \(node.name)") > } > accumulator = val > } > > context var accumulator: Int? > context var symbols: [String: Int]? > } > > It is no longer unclear what depth of the tree the accumulator variable > should be associated with. The mechanism is handled automatically, > preventing the programmer from incorrectly reading a value that was > previously set for another descent. It is no longer needed to manually > handle the stack management of the symbols variable, which was error > prone in our previous implementation. > > The scope of contextual variables should not be limited to type > declarations. One may want to declare them in the global scope of a module, > so that they would be part of the API of a library. Imagine for instance a > web framework library, using contextual variables to provide the context of > a request handler: > > // In the framework ... > public context var authInfo: AuthInfo > > // In the user code ... > framework.addHandler(for: URL("/index")) { > guard let user = authInfo?.user else { > return Redirect(to: URL("/login")) > } > > return Response("Welcome back \(user.name)!") > } > > In that example, one could imagine that the framework would set the > contextual authInfo variable with the authentication information it would > parse from the request before calling the registered handlers. > > This idea is not exactly new. In fact, people familiar with Python may > recognise some similarities with how "with statements" work. Hence, it is > not surprising that things one is able to do with Python’s contexts would > be possible to do with contextual variables as presented above. Consider > for instance the following class: > > class Connexion { > init(to: URL) { /* ... */ } > > deinit { > self.disconnect() > } > > func disconnect() { /* ... */ } > } > > Thanks to Swift’s memory lifecycle, instantiating an instance of Connexion as > a contextual variable would automatically call its destructor when the > context would get popped out. > > context var conn: Connexion > set conn = Connexion(to: URL("http://some.url.com")) in { > /* ... */ > } // the first connection is disconnected here > > I see many other applications for such contextual variables, but I think > this email is long enough. > I’m looking forward to your thought and feedbacks. > > Best regards, > > > Dimitri Racordon > CUI, Université de Genève > 7, route de Drize, CH-1227 Carouge - Switzerland > Phone: +41 22 379 01 24 <+41%2022%20379%2001%2024> > > > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution > > > > > >
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution