[swift-evolution] [Pitch] Contextual variables
rintaro ishizaki
fs.output at gmail.com
Sun Jul 2 21:22:44 CDT 2017
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, [:]) {
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
>
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170703/75254a55/attachment.html>
More information about the swift-evolution
mailing list