[swift-evolution] [Pitch] Contextual variables
rintaro ishizaki
fs.output at gmail.com
Sun Jul 2 21:47:49 CDT 2017
2017-07-03 11:23 GMT+09:00 rintaro ishizaki via swift-evolution <
swift-evolution at swift.org>:
>
>
> 2017-06-28 21:33 GMT+09:00 Dimitri Racordon via swift-evolution <
> swift-evolution at 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 at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>>
>>
>>
>>
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170703/eb57143f/attachment.html>
More information about the swift-evolution
mailing list