Arc Forumnew | comments | leaders | submitlogin
Apply for macros: a follow-up
1 point by akkartik 1560 days ago | 51 comments
http://arclanguage.org/item?id=15659

I've been chatting with Pauan offline (thanks Pauan!) and wanted to highlight something that may not have been obvious in the original thread (Especially http://arclanguage.org/item?id=15771). At least it wasn't obvious to me ^_^. Even implementing apply as:

  (eval (cons (unwrap combiner) args))
doesn't always work with macros like it does for functions. For example, consider this function:

  (def foo(a b) (cons a b))
You might use it like this:

  (foo 1 '(2 3)) ; => (1 2 3)
The equivalent call using apply is:

  (apply foo '(1 (2 3))) ; => (1 2 3)
If you turn foo into a macro, this equivalence won't work.

  (mac foo(a b) `(cons ,a ,b))
  (foo 1 '(2 3)) ; => (1 2 3)
  (apply foo '(1 (2 3))) ; => runs afoul of the implicit eval in foo
This apply works for some macros (like Pauan's def example), just not all of them. I think apply would have to be really sophisticated to work all the time. For now I've setup wart to just throw a warning in such situations.

---

In other news, eval in wart now takes an environment in the usual manner. I've also setup a read-only variable called caller-scope. Here's how I define anonymous macros now:

  = m (fn '(a b) (eval `(cons ,a ,b) caller-scope))

  (m 1 '(2 3))
The combination of quoted parameters and caller-scope seems to do everything vau does, as far as I can see. I'd love comments on this way of decomposing things. It seems all its drawbacks wrt vau involve hygiene, which I want to explore ignoring.

---

Phew, that was a two-week-long tangent that involved me ripping wart down to its foundations before building it up again, and revisiting all my assumptions about how things work.

http://github.com/akkartik/wart/compare/5d227d659c...2ce78d2074

Now I'm going to work on my inliner again, to regain some of wart's squandered performance.



1 point by Pauan 1560 days ago | link

"This apply works for some macros (like Pauan's def example), just not all of them."

I think the fundamental reason for this is that macros don't evaluate their arguments, but functions do. Your example macro is written like as if it were a function, but it's not a function. If you instead wrote it as a macro, like so:

  (mac foo (a b) `(cons ',a ',b))
Then it should work just fine. As I said in my e-mail, I think this demonstrates a mistake in the foo macro, not a mistake in apply. Do you have a better example of a macro that breaks with apply, a macro that's actually written as a macro, rather than as an almost-function?

---

"This apply works for some macros (like Pauan's def example), just not all of them."

It still works if you call it like this: (apply foo '(1 '(2 3)))

As I mentioned in my e-mail, I agree that is an inconsistency when trying to make apply work with fexprs, which is part of why I prefer Kernel's approach of requiring you to wrap the fexpr before calling apply on it... but that doesn't mean that a version of apply that works on fexprs is necessarily broken, just a bit hacky and inconsistent.

I wouldn't call apply broken for the reason you demonstrate above (with the foo macro), because foo really should be written as a function, or its definition should be changed to make use of the non-evaluating nature of its operands.

---

It seems to me that when you talk about apply "working correctly" you're expecting it to somehow guess that the foo macro is behaving like a function, so applying it should treat it like a function, even though it's a macro. But precisely because macros/fexprs might or might not evaluate their arguments, apply cannot guess that.

apply can know whether its argument is a function or fexpr, but not whether the fexpr will actually evaluate its operands or not... so it seems your concept of apply "working correctly" would require apply to essentially read your mind, or do some sort of crazy static analysis and make guesses.

Let me put it like this. When calling apply on something, let's pretend that apply maps quote over the argument list, so that these two are equivalent:

  (foo 1 '(2 3))
  (apply foo '(1 (2 3)))
Okay, but that doesn't work for things like def, which expect unquoted unevaluated operands. So in the case of def, the following must be equivalent:

  (foo 1 (2 3))
  (apply foo '(1 (2 3)))
This is easy enough to do: just change apply so it does one thing for functions and something different for fexprs. Using unwrap is a clean and easy way to do that. But your foo macro is a fexpr, so how is apply supposed to know that it's supposed to treat it like a function, even though it's a fexpr? How is it supposed to know that it's supposed to treat the foo macro different from the def macro?

Really, if you want to solve this, I would suggest having two operators, one for the function-like behavior, and one for the fexpr-like behavior. I'll call these two "apply" and "operate", respectively. So, assuming foo is a function, then the following are equivalent:

  (foo 1 '(2 3))
  (apply foo '(1 (2 3)))
  (operate foo '(1 '(2 3)))
And then you'd use operate for fexprs, and apply for functions. But as already noted in the Kernel Report... operate is always exactly equivalent to calling wrap:

  (apply (wrap foo) '(1 '(2 3)))
So it's rather pointless to provide an "operate" operator since apply + wrap does the same exact thing. And if you want even more fine-grained control, you can use eval directly:

  (eval `(,foo 1 '(2 3)))
Which, incidentally, is sometimes shorter than calling apply, assuming your language has support for quasiquote sugar.

---

"I'd love comments on this way of decomposing things."

Naturally I prefer Kernel's approach of having $vau and then having functions just be a thin wrapper around it. In that case you can create wart's version of fn (quoted args and all) as a fexpr, without needing fn to be built-in.

-----

1 point by akkartik 1560 days ago | link

To me the whole point of macros is that you don't have to worry about whether something is a function or a macro when you call it.

"Do you have a better example of a macro that breaks with apply, a macro that's actually written as a macro, rather than as an almost-function?"

How about and in the previous thread? I tried to use it like this:

  (def all-trues(xs)
    (apply and xs))
This suddenly doesn't work if one of the elements of xs is a list:

  (all-true (list '(1 2))) ; => error
It's pretty clear that 'apply for macros' is an ill-posed, arguably meaningless problem, and I thank you for helping me understand that.

-----

1 point by Pauan 1560 days ago | link

"To me the whole point of macros is that you don't have to worry about whether something is a function or a macro when you call it."

But that's completely incorrect because you always always have to know whether it's a function or a macro, even in a language like Arc or Scheme, because they are fundamentally different things.

Even fexprs aren't the same as functions because they don't evaluate their arguments, and argument evaluation is important, so it's very important that you understand whether something is a function or fexpr, and if it's a fexpr, which arguments are evaluated, and how.

That's a large part of the reason Kernel prefixes fexprs with $ by convention: it really helps you to notice right away the difference between the two, and it's an important difference.

---

"How about and in the previous thread?"

Yeah, I think that qualifies as a good example. It breaks for the exact same reason that your foo macro breaks: it evaluates its arguments, so you have to double-quote them:

  (all-true '('(1 2)))
---

"It's pretty clear that 'apply for macros' is an ill-posed, arguably meaningless problem, and I thank you for helping me understand that."

Sure, I see now that trying to make apply work on macros is quite tricky indeed, especially if you want to "not have to worry about the difference between macros and functions". So providing it a la carte with wrap and unwrap (like Kernel) seems far superior to me.

-----

1 point by akkartik 1560 days ago | link

"it evaluates its arguments, so you have to double-quote them"

But the whole point is that the list is just a list of elements! Imagine it's coming from a whole complex sequence of functions. Don't think of it like this:

  (all-true '((1 2))
Think of it like this:

  (all-true l) ; with l bound to ((1 2))
You want callers of all-true to take the trouble to quote elements of l, to be aware that it's going to go through all-true. Isn't that simply hideous? What if they then have to go through a different path that doesn't eventually pass through a macro? Do they have to recompute l without quotes?

"that's completely incorrect because you always always have to know whether it's a function or a macro, even in a language like Arc or Scheme"

What I called the 'point of lisp' was my sense of the ideal. The promise of a high-level language is that you can create new names and use them like primitives that the language came with.

  (let x 3
    bar.x) ; Does the language come with let? Who cares?
All languages break this abstraction, yes. But lisp is lisp because it takes this abstraction farther than anything else.

You've explained the technical reasons why 'apply for macros' is hard, and that makes sense. But the solution is to not use apply with macros, not tie ourselves up in knots with quote.

-----

1 point by Pauan 1560 days ago | link

"Think of it like this: (all-true l)"

Sure, I already considered that. That is, after all, the most common use for apply. And I agree that's ugly. You'd have to say something like (all-true (wrap-quote l)) or somesuch. Ugly.

---

"Isn't that simply hideous?"

Sure is!

---

"The promise of a high-level language is that you can create new names and use them like primitives that the language came with."

And fexprs/macros let you do that. That wasn't my point. What you said is that the point of macros is being able to call things without caring whether the thing is a macro/function/whatever. That view is incorrect because the meaning of the expression differs depending on whether it's a function or macro.

For instance, in the "let" expression you just gave, it doesn't evaluate the variable "x", but you only know that because "let" is a macro. If it were a function it would throw a "x is undefined" error. So you have to know whether something is a function or macro in order to use it correctly.

The same is true of apply: it has two different (and inconsistent) behaviors depending on whether its argument is a fexpr or a function. And that's a problem because it's confusing and makes it really easy to get it wrong. Hence why Kernel makes you explicitly use wrap to specify your intent.

---

"You've explained the technical reasons why 'apply for macros' is hard, and that makes sense. But the solution is to not use apply with macros, not tie ourselves up in knots with quote."

Sure, and even with that approach, if your language has wrap/unwrap, then you can still use apply on macros, you just need to wrap them first:

  (apply (wrap foo) ...)
And if that breaks, then you bring out eval:

  (eval `(,foo ...))

-----

1 point by akkartik 1560 days ago | link

"For instance, in the "let" expression you just gave, it doesn't evaluate the variable "x", but you only know that because "let" is a macro. If it were a function it would throw a "x is undefined" error."

No, I thought about that when I built let. And then I forgot about it. Now when I see that expression I think, "oh, I'm creating a binding." The point of having power is to not have to derive things from first principles every time we see them.

"And fexprs/macros let you do that. That wasn't my point. What you said is that you want to be able to call things without caring whether the thing is a macro/function/whatever."

Yeah, I'm still struggling to express what I mean by 'use them like language primitives'. I think I'm trying to invoke a sense of fundamental knowledge. When I was taught lisp I didn't think, "wait how does (setq a 3) work if a is not bound". I thought, "Ok, setq is assignment." Functions, macros, fexprs, these are all tools to setup such axiomatic intuitions. That's the whole point.

-----

1 point by Pauan 1560 days ago | link

"No, I thought about that when I built let. And then I forgot about it."

Yes, but you still need to carry around that knowledge in your subconscious, and retrieve that knowledge every time you use "let". That was my point: that the distinction between them is important.

---

"The point of having power is to not have to derive things from first principles every time we see them."

Yes... and I'm agreeing with you.

You said that the point of macros is not having to care whether something is a function/macro or not. But on a very fundamental level you do have to care, just like how you have to care about whether a variable is a string or a number.

I was only disagreeing with that statement, that you don't need to care about the differences between fexprs/functions. All the problems with apply come about because of misunderstandings of the differences between the two:

  ;; functions
  (foo '1 '(2 3))
  (apply foo '(1 (2 3)))

  ;; fexprs
  (foo 1 (2 3))
  (apply foo '(1 (2 3)))
This difference is what causes the confusion and makes it very easy to make mistakes when using apply on fexprs. So it's not so much that apply doesn't work on fexprs, as it is that the behavior of apply for fexprs is different than the behavior of apply for functions... which is awfully confusing and inconsistent.

So choosing to make apply work only on functions is a perfectly reasonable position that discourages mistakes.

-----

1 point by akkartik 1560 days ago | link

"And if that breaks, then you bring out eval"

  wart> = l '((1 2))
  wart> (and @l) ; error
  wart> (wrap.and @l) ; error
  wart> (eval `(,wrap.and ,@l)) ; error
  wart> (eval `(,wrap.and ,@(map (fn(_) (cons quote _)) l))) ; error
I think our aesthetics are in disagreement :) When the second one (or maybe the third one, in extreme extremis) fails, I would simply go back and rewrite all-true to not use apply/splice, like I did all: http://github.com/akkartik/wart/commit/d25410707d

-----

1 point by Pauan 1560 days ago | link

Er, shouldn't it be (list quote _) ...? In any case, you can wrap up the last one into a function:

  (def operate (f args)
    (eval `(,f ,@(map (fn (_) (list quote _)) args))))
Then it would just be (operate and l)

I'm not saying that's necessarily a good idea, but if it comes up often enough, might as well write a helper function for it.

---

And when I said "bring out eval" I meant like this:

  (eval `(,and ,@l))
In other words, not wrapping it.

-----

2 points by akkartik 1560 days ago | link

"In other words, not wrapping it."

Ah, this works :)

  (eval `(,and ,@(map (fn(_) (cons quote _)) l)))
In wart, 'a is just (' . a). That eliminates questions like, "what happens if quote gets multiple args?" :)

-----

1 point by akkartik 1560 days ago | link

Pauan, I'm starting to think it's a win to define mapquote like you suggested:

  def all-true(xs)
    (and @mapquote.xs)
But using quoting to suppress future eval like this makes me nervous. Do you think it's a correct transformation?

-----

1 point by Pauan 1560 days ago | link

My position is quite simple: if you want clean elegance, just use Kernel. Seriously.

If that definition of all-true works and doesn't have any noticeable bugs... then go ahead and use it. It'll be hacky and won't be clean and elegant, but it'll be short and simple and work. And it seems to me that wart is trying to get the power of fexprs in a more hacky Arc-ish way, so that's perfectly fine.

-----

1 point by Pauan 1560 days ago | link

Ah, like PicoLisp. Neat, I like that.

-----

1 point by akkartik 1560 days ago | link

  > > Isn't that simply hideous?
  >
  > Sure is!
I think we're in complete agreement that apply for macros is not well-behaved. The rest is just splitting hairs :)

-----

2 points by Pauan 1560 days ago | link

"I think we're in complete agreement that apply for macros is not well-behaved."

Yes, and as I already said a while ago, I think Kernel's approach is ideal. Except now I actually have some solid reasons to back up that statement, thanks to you.

-----

2 points by rocketnia 1560 days ago | link

"The combination of quoted parameters and caller-scope seems to do everything vau does, as far as I can see. I'd love comments on this way of decomposing things."

Can you implement vau like this?

  ; (vau (a b c) env ...body...)
  ; ==>
  ; (fn '(a b c) (let env caller-scope ...body...))
  ;
  (def vau '(parms env body)
    (eval (list fn (list quote parms)
            (list* let env 'caller-scope
              body))
          caller-scope))
If so, I think you're pretty well off the way you are. ^_^

What is 'caller-scope bound to at the top level?

---

"It seems all its drawbacks wrt vau involve hygiene, which I want to explore ignoring."

What drawbacks are those?

---

"Phew, that was a two-week-long tangent that involved me ripping wart down to its foundations before building it up again, and revisiting all my assumptions about how things work."

I hope it's worth it for you. XD

-----

1 point by akkartik 1560 days ago | link

"What drawbacks are those?"

I get the sense that vau/wrap/unwrap are the 'structured' equivalents of caller-scope. They're more well-behaved, and they make it harder to do super ugly things like functions reaching in to modify their caller's scopes ^_^. This well-behavedness also makes it tractable to specify their semantics, prove theorems about the calculus, regularity, smoothness, being hygienic, and whatnot.

-----

1 point by Pauan 1560 days ago | link

Actually, I see them as just being stylistic differences... Kernel already lets you mutate the caller's scope via $set! so I assume you're talking about the parent of the caller's scope... Yeah you can't do that, but you could make a language very similar to Kernel, with that one thing changed if you wanted to.

Or perhaps you're talking specifically about functions mutating their environment... well you can do that in Kernel too:

  (wrap ($vau ... env ...))
The above creates a function that has access to its dynamic scope. This isn't used most of the time in Kernel, but it is used in a couple places, like the "get-current-environment" function. Most of the time you would use $lambda.

I think the benefit of vau/wrap/unwrap is that it makes it super easy to coerce between functions/fexprs. It's also very clean and easy to reason about. But I don't see them as being necessarily more "well behaved" than wart's approach.

-----

1 point by akkartik 1560 days ago | link

"I think the benefit of vau/wrap/unwrap is that it makes it super easy to coerce between functions/fexprs."

Ah, this was what I was missing. This makes your position crystal clear, thanks.

-----

2 points by Pauan 1560 days ago | link

One other benefit: the environment argument is local, rather than a global hard-coded "caller-scope". This not only lets you write it shorter (such as "env") but also avoids collisions in the case of nested $vau's:

  ($vau ... env1
    ($vau ... env2
      ...))
I suppose in that one case, $vau is more well-behaved. You can emulate that behavior with let, though:

  (fn '...
    (let env1 caller-scope
      (fn '...
        (let env2 caller-scope
          ...)))
Which is admittedly verbose.

-----

1 point by akkartik 1560 days ago | link

Yeah, those are great examples.

For all my rhetoric about "give the programmer absolute powa!!1!" I'm uncomfortable making caller-scope too easy to use ^_^. It'll just be the next case of, "when I understand why I need this power, I'll mix it in."

-----

1 point by akkartik 1560 days ago | link

"I hope it's worth it for you. XD"

I think so, yes!

I got to properly understand vau, to realize that its environment arg is never explicitly passed in.

And I got to replace the magical mfn primitive for macros with the far simpler caller-scope. I think that's a good trade.

-----

1 point by akkartik 1560 days ago | link

"What is 'caller-scope bound to at the top level?"

  wart> caller-scope
  007scope.cc:122 No binding for caller-scope
:)

-----

2 points by Pauan 1560 days ago | link

I'd rather it be bound to the global environment, but that's just me nitpicking.

-----

2 points by rocketnia 1560 days ago | link

That's already the current scope, though.

If I just saw 'caller-scope in pseudocode somewhere, I'd implement it as an anaphoric variable of 'fn (and I'd implement a non-anaphoric variant of 'fn to base it on, so we'd basically be at vau again :-p ). So at the global scope, my implementation would just treat 'current-scope as a global variable.

For a third option, maybe 'caller-scope at the top level should be the scope of eval's caller. I'm not sure the point of that, and it might make the language even harder to optimize, but I'm just throwing it out there.

-----

1 point by Pauan 1560 days ago | link

Yeah, but then you can say (eval ... caller-scope) at the top-level, and if your language has a facility for setting variables in a particular scope, you can say this:

  (env= caller-scope foo 5)
And you can say this:

  (let global caller-scope
    ...
    (env= global foo 5)
    ...
    (eval ... global))
Kernel already does this via the "get-current-environment" function:

  ($let ((global (get-current-environment)))
    ...
    ($set! global foo 5)
    ...
    (eval ... global))
Just to be clear: Kernel's "get-current-environment" is not the same as the environment argument passed to fexprs. But since wart is implementing the environment argument as a global hard-coded "caller-scope" variable, I think it makes sense to merge the two in wart, even though I think it's cleaner to have them be two separate things, as in Kernel.

-----

2 points by Pauan 1560 days ago | link

Which reminds me... rocketnia, you mentioned being able to define vau in terms of wart's magical fn. You're mostly right, except... there will be two ways to grab the environment: the env parameter and the implicit global caller-scope. So that's a bit of a leaky abstraction.

On the other hand, it's quite easy to define wart's magical fn in terms of vau... with no leaky abstractions! The only catch is that caller-scope will always refer to the global scope inside vau forms... that could be changed too, by extending/overwriting vau, but I didn't do that:

  (= get-current-environment (wrap (vau () e e)))

  ;; don't define this if you don't want caller-scope at the global level
  (= caller-scope (get-current-environment))
  
  ;; simple fn, without magical quoted args or caller-scope
  (= fn (vau (parms . body) env
          (wrap (eval `(,vau ,parms nil ,@body)))))

  ;; omitting other stuff like afn, no, caris, list, etc.
  ;; but they can all be defined in terms of simple fn
  ... 
          
  ;; makes these variables hygienic
  (with (with  with
         eval  eval
         let   let)
         
    ;; this recreates the part of wart that is currently handled in C++
    (= parse-fn (fn (parms env)
                  (if (caris x 'quote)
                      (list (cdr parms) nil)
                      ((afn (x vars parms)
                         (if (no x)
                               (list (rev parms)
                                     (rev vars))
                             (caris (car x) 'quote)
                               (self (cdr x)
                                     vars
                                     (cons (cdar x) parms))
                             (let c (car x)
                               (self (cdr x)
                                     `((,eval ,c ,env) ,c ,@vars)
                                     (cons c parms)))))
                       parms nil nil))))
    
    ;; overwrite with the complex fn which has quoted args and caller-scope
    (= fn (vau (parms . body) env
            (w/uniq new-env
              (let (parms vars) (parse-fn parms new-env)
                (eval `(,vau ,parms ,new-env
                         (,with ,vars
                           (,let caller-scope ,new-env
                             ,@body)))
                      env))))))
I have not run the above code, but it should give the general idea... Basically, what it does is it takes this...

  (fn (a 'b . c)
    ...)
...and converts it into this (where "g1" is a gensym and "with", "eval", and "let" are hygienic):

  (vau (a b . c) g1
    (with (a (eval a g1)
           c (eval c g1))
      (let caller-scope g1
        ...)))
I know the above code looks verbose, but keep in mind that quoted args and implicit caller-scope is currently handled in C++, whereas I recreated it from scratch using vau + simple functions (defined with wrap).

One more caveat: I'm not sure how you implemented caller-scope. If it's hardcoded into every function such that functions can't have an argument called "caller-scope" then the above will work the same way. But if it's a global implicit parameter like in Nu and ar, then you'll need to search the arg list for an argument called "caller-scope", which is doable but would require some more code, especially for handling argument destructuring.

---

Anyways, I'm not saying you should necessarily do it this way in wart, but... I think it's cleaner, conceptually, for functions to be defined in terms of vau, rather than vau being defined in terms of functions.

Of course, as I already said, if you care about cleanliness, I'd suggest just using Kernel, which doesn't support the magical fn like wart, which I consider to be a good thing.

-----

3 points by rocketnia 1559 days ago | link

"Which reminds me... rocketnia, you mentioned being able to define vau in terms of wart's magical fn. You're mostly right, except... there will be two ways to grab the environment: the env parameter and the implicit global caller-scope. So that's a bit of a leaky abstraction."

Hmm... yeah, it's a pretty leaky abstraction. It's one of these features with ambient authority:

  (if designed like a global variable assigned at the beginning of each
  call)
  
  Right now, get the most recently started call's caller's environment.
  
  
  (if designed like a continuation mark)
  
  Right now, get the deepest-on-the-stack call's caller's environment.
  
  
  (if designed like a local variable bound by each (fn ...))
  
  Given a non-global lexical environment, its local variables must have
  been initially bound by some call, so get the lexical environment
  that was used to evaluate that call.
---change of topic--

...Actually, the first two of these designs are broken! Say I define a simple fexpr like this one:

  (def idfn '(result)
    (eval result caller-scope))
Now if I run the code ((fn () (idfn caller-scope))), the call stack at the evaluation of 'caller-scope looks something like this:

  ((fn (a) ((fn () (idfn caller-scope)))) 1)  ; eval'd in global scope
  ((fn () (idfn caller-scope)))  ; eval'd in local scope of (fn (a) ...)
  (idfn caller-scope)            ; eval'd in local scope of (fn () ...)
  (eval result caller-scope)     ; eval'd in local scope of idfn
  caller-scope                   ; eval'd in local scope of (fn () ...)
IMO, the value we get should be the local scope of (fn (a) ...), so that it doesn't matter if we replace ((fn () (idfn caller-scope))) with ((fn () caller-scope)). However, the calls to 'idfn and 'eval are deeper on the stack and their start times are more recent, so we get one of those caller scopes instead.

Does Wart have this awkward behavior, akkartik?

---/change of topic---

To get back to the point, the local-variable-style version of the feature (the only version that works?) doesn't strike me as completely undesirable. It lets the programmer evaluate expressions in arbitrary ancestor stack frames, and that isn't a shocking feature to put in a debugger.

Sure, it makes it almost impossible to hide implementation details and keep privilege from leaking to all areas of the program, but it could be useful in a language where all code that runs in a single instance of the language runtime has been personally scrutinized (or even written) by a single programmer. That's the primary use case akkartik has in mind anyway.

-----

1 point by akkartik 1559 days ago | link

the value we get should be the local scope of (fn (a) ...)

Wart returns the scope with a set to 1. Is that the one you mean? It's different from the value of:

  ((fn (a) caller-scope) 1)

-----

1 point by rocketnia 1559 days ago | link

That's all what I was hoping for. ^_^

I'm impressed you're managing to keep track of that with mutation. Are you setting 'caller-scope on every entry and exit of a function and on every entry and exit of an expression passed to 'eval?

-----

1 point by akkartik 1559 days ago | link

caller-scope acts like an implicit param of all functions:

http://github.com/akkartik/wart/blob/98685057cd/008eval.cc#L...

Perhaps you're concerned about something I haven't even thought of :)

-----

1 point by rocketnia 1558 days ago | link

Oh, Pauan had mentioned 'caller-scope being a "global hard-coded" variable, and I didn't see you disagreeing, so I assumed you were just assigning to it a lot behind the scenes. :-p

-----

2 points by akkartik 1559 days ago | link

It's likely that as I reflect on vau, wart will start to look more like Kernel.

But I don't think it will become Kernel. Kernel seems really elegant as long as you give up quote and quasiquote. I suspect if you bolt them onto Kernel it'll have slid from its sweet-spot peak of elegance. A language that encourages quoting and macros will diverge significantly from Kernel.

One simplistic way to put it: Kernel is scheme with fexprs done right, while wart tries to be lisp with fexprs done right. It's far from that local extremum, though. It's even possible the wisdom of caring about hygiene in a lisp-1 is deeper than I realize. Perhaps quasiquote needs to go the way of dynamic scope.

-----

1 point by akkartik 1559 days ago | link

"I'm not sure how you implemented caller-scope. If it's hardcoded into every function such that functions can't have an argument called "caller-scope" then the above will work the same way."

http://github.com/akkartik/wart/blob/98685057cd/008eval.cc#L...

It tries to bind caller-scope after the params, so this fails:

  wart> def foo(caller-scope) 34
  wart> foo 3
  007scope.cc:77 Can't rebind within a lexical scope
  dying
Anyways, I haven't thought about these corner cases at the moment.

-----

2 points by rocketnia 1559 days ago | link

If you want 'caller-scope to be built into the language and you want to skirt the issue of name collisions, you could devote a separate reader syntax like "#caller-scope" to it and make it a type of its own.

-----

1 point by akkartik 1559 days ago | link

"..if your language has a facility for setting variables in a particular scope.."

In wart scopes are just tables. It's not a good idea to modify them, but nobody will stop ya :)

"Kernel's "get-current-environment" is not the same as the environment argument passed to fexprs."

Can you elaborate? In

  ($vau foo env
    ..)
(get-current-environment) would return the callee scope, and env contains the caller scope, right?

Wart doesn't currently have an easy way to get at the callee scope (you could peek inside (globals)), but it's on my radar to change that if necessary.

-----

1 point by Pauan 1559 days ago | link

  ($let ((env1 (get-current-environment)))
    ...
    ($vau foo env2
      ...
      ($let ((env3 (get-current-environment)))
        ...))
In the above, env1 is the lexical scope where the $vau is defined. It does not include bindings for foo, env1, env2, or env3, but contains all the bindings on the outside of the $let, where the $vau is defined.

env2 is the dynamic scope where the $vau is called, it does not include bindings for foo, env1, env2, or env3.

env3 is the environment of the $vau itself. This environment inherits from env1, and thus is lexical just as env1 is. And so, it contains all the bindings of env1, in addition to bindings for foo, env1, and env2, but not env3.

So, by using this combination of lexical and dynamic scope, you can express a huge variety of different things in Kernel.

---

Let me explain via a more elaborate example:

  ($let ((global (get-current-environment)))
    (display (eval 'x global))
    
    ($set! global $foo
      ($vau (x) env
        (display (eval 'x env))
        (display (eval 'env env))
        
        ($let ((inner (get-current-environment)))
          (display (eval 'x inner))
          (display (eval 'env inner))
          (display (eval 'global inner))))))
          
  ($let ((x 10))
    ($foo 20))
First, we use $let to bind the variable 'global to the global environment using get-current-environment. Then we try to evaluate the symbol 'x in that environment. The variable 'x of course does not exist in the global environment, so it throws an error.

Then, we create a $vau form and assign it to the variable $foo in the global environment. This is the same as saying ($define! foo ...) at the top level, but is necessary when inside a $let.

Now, at the bottom, we use $let to bind the variable 'x to 10 and then call $foo with the single argument 20. First, $foo tries to evaluate the variable 'x in the dynamic environment "env". This should display 10, because it's using the binding in the $let where $foo is called.

We then evaluate the variable 'env in the $vau's dynamic environment. But the variable 'env does not exist in the dynamic environment, so it throws an error.

Then, we use a $let inside the $vau to grab a hold of the $vau's inner environment and bind it to the variable 'inner. We then evaluate the variable 'x in the $vau's inner environment. This should display 20, because it's using the binding inside the $vau, which is bound to the $vau's argument 'x which was 20 when calling the $vau.

We then evaluate the variable 'env in the $vau's inner environment, which evaluates to the dynamic environment, because inside the $vau, the variable 'env is bound to the dynamic environment.

Lastly, we evaluate the variable 'global in the $vau's inner environment. This evaluates to the global environment because the $vau's inner environment inherits from the top-level $let where the variable 'global is bound.

--

Here is a picture showing the environments in the above code:

http://img42.imageshack.us/img42/1870/vauenvironments.png

The global environment is pink, the first blue environment is the $let's environment that inherits from the global environment, plus a binding for the variable 'global. The green is the $vau's environment which inherits from the $let's environment, plus a binding for the variables 'x and 'env. And the yellow is the $let's environment that inherits from the $vau's environment.

Lastly, the second blue environment is the dynamic environment that is bound to the 'env variable inside the $vau when it is called.

-----

1 point by akkartik 1559 days ago | link

Thanks. So what Kernel calls the dynamic environment is identical to caller-scope, right?

I think I find this confusing because when I hear 'dynamic environment' I keep thinking of dynamic scope (special variables in common lisp). If we only create bindings using let and combiner parameters, the dynamic environment is just the caller's static environment, is that right?

-----

1 point by Pauan 1559 days ago | link

Yes, it is identical to caller-scope.

In Kernel, the dynamic environment is exactly analogous to dynamic scope. The difference is that lexical scope is the default, and you have to explicitly ask to evaluate things with dynamic scope, rather than earlier Lisps which used dynamic scope by default and didn't even have lexical scope.

Special variables in Common Lisp are similar to dynamic scope, except you're flagging only certain variables to be dynamic, whereas the dynamic environment in Kernel lets you evaluate any variable with dynamic scope.

---

"If we only create bindings using let and combiner parameters, the dynamic environment is just the caller's static environment, is that right?"

Yes. In fact, in Kernel, $let is defined just like it is in Arc, using $lambda. And $lambda uses $vau, and $vau is the only way to create new environments in Kernel, as far as I know. So, environments are all about $vau.

---

By the way, I just edited the post you're replying to, and added a picture.

-----

2 points by Pauan 1559 days ago | link

In fact, I like to think of environments in a similar way as continuations. Consider this, for instance:

  ($define! $foo
    ($vau (x) env
      (list x env)))
      
  ($define! $bar
    ($vau (x) env
      ($foo x)))
      
  ($bar 10)
The above should return a list containing two elements: the number 10 and $bar's environment. The way I think of it is like this:

  ($define! $bar
    ($vau (x) env
      ($foo x env)))
That is, the $bar fexpr implicitly passes its own internal environment to the $foo fexpr. And $let's work this way as well, so that this:

  ($let ((x 10))
    ($bar x))
Would be equivalent to this:

  ((wrap ($vau (x) env
           ($bar x env)))
   10)
So it's really all about $vau's passing their own internal environment whenever they call something else, similar to the idea of all functions implicitly passing their own continuation when calling something else.

-----

1 point by akkartik 1559 days ago | link

Very cool. While struggling with the $vau concept I thought about whether I could build lazy eval directly using $vau, without first building force and delay (SICP 4.2). But it's not quite that powerful, because lazy eval also needs the ability to stop computing the cdr of a value. Your intuition tying $vau to continuations is a similar you-see-it-if-you-squint-a-little correspondence.

-----

1 point by Pauan 1559 days ago | link

I somewhat remember either the Kernel Report or John's dissertation mentioning the similarities between continuations and environments, but I might be mistaken on that...

---

"I thought about whether I could build lazy eval directly using $vau"

Directly? Not sure, but ยง9.1.3 of the Kernel Report does show how to build promise?, memoize, $lazy, and force as a library using existing Kernel features.

-----

1 point by akkartik 1559 days ago | link

"Special variables in Common Lisp are similar to dynamic scope, except you're flagging only certain variables to be dynamic, whereas the dynamic environment in Kernel lets you evaluate any variable with dynamic scope."

Ah! I considered this approach when I was building dynamic variables in wart, but it seemed less confusing to attach the scope to the binding. Wart is unlike common lisp in this respect. SBCL:

  * (defvar foo 34)
  * (defun bar() (foo))
  * (bar)
  34
  * (let ((foo 33)) (bar))
  33 ; foo is still dynamic. WEIRD.
But:

  wart> = foo 34
  wart> def bar() foo.
  wart> bar.
  34
  wart> let foo 33 bar.
  34 
  wart> making foo 33 bar.
  33 ; dynamic scope
I'm starting to appreciate that $vau and first-class environments give the programmer a lot more power (aka rope to hang himself with :) than caller-scope.

-----

1 point by Pauan 1559 days ago | link

"foo is still dynamic. WEIRD."

The reason for this is that Common Lisp explicitly states that if you use "let" on a dynamic variable, it dynamically changes that variable for the scope of the "let". So Common Lisp combines both "let" and Racket's "parameterize" into a single form, rather than keeping them separate.

-----

2 points by akkartik 1559 days ago | link

Yes, of course. I prefer racket's approach in this case.

-----

1 point by akkartik 1559 days ago | link

I'm struggling to wrap my head around the idea that you can define variables to have dynamic scope using just $vau or caller-scope..

-----

1 point by Pauan 1559 days ago | link

You don't define variables to have dynamic scope. They automatically have dynamic scope when you evaluate them in the dynamic environment:

  ($vau () env
    (eval 'x env))
The above, when called, will evaluate the variable 'x in whatever scope it was called in. Thus, the above $vau has just "made" the variable 'x dynamic. But of course this ability to evaluate things in the dynamic scope is only available to fexprs.

---

If you're talking about something similar to Racket's parameterize, you should be able to build that using dynamic-wind. Then something like this...

  ($parameterize ((foo 10))
    ...)
...would be equivalent to this:

  ($let ((env   (get-current-environment))
         (orig  foo))
    (dynamic-wind ($lambda ()
                    ($set! env foo 10))
                  ($lambda ()
                    ...)
                  ($lambda ()
                    ($set! env foo orig))))
---

In fact, I'm gonna write a $parameterize form right now:

  ($define! $parameterize-redirect
    ($vau (target tree . body) env
      ($let ((inner (get-current-environment))
             (env   (eval target env)))
        (dynamic-wind
          ($lambda ()
            ($set! inner orig
              (map ($lambda ((var expr))
                     (list var (eval var env)))
                   tree))
            (for-each ($lambda ((var expr))
                        (eval (list $define! var expr) env))
                      tree))
          ($lambda ()
            (eval (cons $sequence body) env))
          ($lambda ()
            (for-each ($lambda ((var expr))
                        (eval (list $define! var expr) env))
                      orig))))))
                      
  ($define! $parameterize
    ($vau (tree . body) env
      (eval (list* $parameterize-redirect env tree body) env)))
Warning: untested and may not work. However, if it does work then it will work for all variables, global or local, without declaring them as dynamic before-hand. So this will work:

  ($let ((x 5))
    ... x is 5 ...

    ($parameterize ((x 10))
      ... x is 10 in here ...
      )

    ... x is 5 again ...
    )
The catch is that in order to parameterize global variables, the $parameterize form itself needs to be at the top level, because it's mutating the immediate ancestor environment.

If you want to parameterize something other than the immediate environment, use $parameterize-redirect which accepts an environment as the first argument, and then evaluates in that environment instead.

-----

2 points by rocketnia 1559 days ago | link

"Wart doesn't currently have an easy way to get at the callee scope"

What about this?

  (def get-current-environment ()
    caller-scope)

-----

1 point by akkartik 1559 days ago | link

Lol! Yes, that works :)

-----

3 points by rocketnia 1558 days ago | link

If you define (thunk ...) ==> (fn () ...), then using 'get-current-environment is actually more verbose than writing the implementation directly:

  get-current-environment.
  thunk.caller-scope.
Actually, 'thunk and infix syntax isn't necessary, and Kernel has the same quirk:

  (get-current-environment)
  ((fn () caller-scope))     ; Wart
  (($vau () e e))            ; Kernel

-----

1 point by akkartik 1560 days ago | link

Good point!

-----