2017-07-03 11:23 GMT+09:00 rintaro ishizaki via swift-evolution < swift-evolution@swift.org>:
> > > 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, [:]) { > > Ah, this must be `saveAndRestore(&symbols, [:]) {` of course. > 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 > >
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution