Arc Forum | Combining lexical and dynamic scope

Arc Forum

Combining lexical and dynamic scope

2 points by akkartik 5176 days ago | 5 comments

With the new fexpr-based interpreter for wart[1] I've been trying to reduce the set of names in the core language and bootstrap complex features by progressive enhancement. For example, I'd like to build arc's if out of a simple two-branch if as follows:

  let oldif if
    mac if args
      oldif (no (cdr args))
        (car args)
        `(,oldif ,(car args)
           ,(cadr args)
           (if ,@(cddr args)))

But macros must evaluate in the caller's lexical scope.

  mac foo(x)
    `(+ ,x 1)

  let y 3
    (foo y) ; must macex to (+ y 1) in foo's scope, then evaluate to 4 in caller scope

The solution I'm trying out to get both these macro examples to work is a sort of gracefully degrading lexical scope. At every call, instead of swapping in the callee's environment, I push it above the caller's environment. This is like lexical scope in how bindings override each other:

  (let x 3
    def foo()
      (let x 4
        (bar))

    def bar()
      x)

  (foo) ; returns 3 from the outer lexical scope

But it also makes the caller's lexical scope available if necessary:

  def bar()
    x

  let x 3
    (bar) ; returns 3 like a dynamic scope

I haven't seen this idea before, and I'm inclined in this case to think it's probably a bad idea. Can anyone think of use cases where having the extra power bites us? Feel free to play with wart:

  $ git clone 
  $ git checkout 4863b4318f
  $ wart

One drawback I found was that macros must now almost always use implicit gensyms[1] to avoid overriding bindings in their callers. The correct definition for if in this scheme is:

  let $if if
    mac if $args
      $if (no (cdr $args))
        (car $args)
        `(,$if ,(car $args)
           ,(cadr $args)
           (if ,@(cddr $args)))

If this macro's parameter was just args it wouldn't have access to any other bindings at macro call-sites using the variable args. It must be a gensym.

  if args
    prn "hi" ; requires gensyms in 'if' macro

I'm still playing with this to see how onerous it is to have all these $vars in macros. If it's not too onerous, and if we don't discover any other issues, it would mean that I can build macros out of just eval and implicit gensyms and lexical scopes.

[1] http://arclanguage.org/item?id=14881, http://github.com/akkartik/wart/tree/unstable

[2] http://arclanguage.org/item?id=13342

2 points by Pauan 5172 days ago | link

So.. let me see if I understand this correctly. Please correct me if I'm wrong. What you are saying is that wart will have lexical scope, just like Arc. But, when a variable does not exist in the lexical scope (it is a global variable), it will then be treated as a dynamic variable, and thus take it from the caller's scope? What about this?

  (def bar (x) x)

  (def foo (x)
    (bar x))

  (foo 5) -> returns 5, as expected

  (let bar nil
    (foo 5)) -> ???

Would the above return 5, or would it treat "bar" as a dynamic variable?

You could work around that by saying that a global variable is only treated as dynamic if it is undefined. In other words, rather than throwing an "undefined variable" error like Racket does, it would instead just grab the value from the caller's scope. That would help a lot, but I predict it would still be somewhat risky.

However, I think there is an inherent benefit/cost tradeoff in all things, and so I suspect that this could actually work out okay in practice. I myself have desired a Lisp where all global variables are dynamic, but I never thought to make all undefined variables dynamic.

My suggestion would be to try it out and see how it works in practice.

-----

2 points by akkartik 5172 days ago | link

"Would the above return 5, or would it treat "bar" as a dynamic variable?"

It overrides bar and so the call to foo fails. You're right, that does seem like action at a distance.

Hmm, that's because I'm using plain dynamic scopes for assign, and therefore for def.

"rather than throwing an "undefined variable" error like Racket does, it would instead just grab the value from the caller's scope."

Yeah, you're right.

---

4 hours later

Now working: http://github.com/akkartik/wart/commit/8806dd7109

(ignore the reference to broken if; that's fixed later as well)

-----

1 point by Pauan 5172 days ago | link

As far as implicit gensyms go, it is certainly nicer than having to explicitly use w/uniq. I can see how it can get rather tedious though, and starts to make your elegant code look a lot like Perl.

Have you considered moving the emphasis away from macros and toward fexprs instead? I suspect if you primarily used fexprs, then the problem with implicit gensyms would go away. Of course, then you end up with new problems... like this:

  (fexpr foo (x)
    (eval x))

  (let x 5
    (foo x)) -> would this return x or 5?

I attempted to add fexprs to ar, and in doing so had to face this problem. I "solved" it by making eval implicitly evaluate in the outer (caller) environment, ignoring the fexpr's environment. You can, however, explicitly evaluate in the current environment by passing a second argument to eval.

-----

1 point by akkartik 5173 days ago | link

One drawback -- this is a mouthful:

  ,@$body

-----

1 point by Pauan 5172 days ago | link

Hello, Perl!

-----