Arc Forumnew | comments | leaders | submitlogin
Apply for macros: a solution
2 points by akkartik 4347 days ago | 21 comments
(Followup: http://arclanguage.org/item?id=15659, http://arclanguage.org/item?id=15907)

Wart now supports apply on macros -- as long as they are implemented using backquote syntax.

I'm still in dread that some show-stopper bug will refute my solution. But if it holds up, this makes macros 'even more first-class'. And it puts Kernel to the question; without quote, Kernel can't use this solution, so it can't use apply with operatives, and so its fexprs are less powerful.

=== How it works

Here's the problematic test macro and call from the previous thread:

  (mac foo(a b) `(cons ,a ,b))

  (foo @'(11 (12 13)))
@ is wart's version of apply. I'm going to take you inside my interpreter from a few days ago to see what used to happen to this call:

  eval: (foo @'(11 (12 13)))
  after splice: (foo 11 (12 13))
  eval: (eval ((fn nil `(cons ,a ,b))) caller-scope)
  evalArgs: ((fn nil `(cons ,a ,b)))
    eval: `(cons ,a ,b)
    eval: b
    lookup: b => (12 13)
    eval: a
    lookup: a => 11
  eval: (cons 11 (12 13))
  evalArgs: (12 13)
  Error: 12 is not a function
Today we instead see the following sequence of events:

  eval: (foo @'(11 (12 13)))
  after splice: (foo ''11 ''(12 13))                 a)
  eval: (eval ((fn nil `(cons ,a ,b))) caller-scope)
  evalArgs: ((fn nil `(cons ,a ,b)))
    eval: `(cons ,a ,b)
    eval: b
    lookup1: b => ''(12 13)                          c)
    eval: a
    lookup1: a => ''11
  eval: (cons ''11 ''(12 13))
  evalArgs: ''(12 13)
  lookup0: $y => (12 13)                             b)
There are 3 changes:

a) When splicing a list, we tag its elements[1] with ''. That's two single-quotes.

  (... @'(a b)) -> (... ''a ''b)
'' is an internal detail. The reader provides no way to type it in. If you ever see it printed at the REPL, that's a bug. I recommend pronouncing it as 'already evaluated'.

b) When a function evals its args, '' behaves just like ' -- it suppresses evaluation of that arg. The interpreter's evalArgs strips the '' and provides the function body with the quoted value. The final lookup0 lines show this situation in action. This is the default, and it ensures '' is usually quickly consumed. [2]

c) However, within a comma expression evalArgs passes '' without stripping it out. The lookup1 lines above show this situation. As a result, '' in macro arguments ripple through until they exit the macro. This prevents (12 13) above from being evaluated as a function call. [3]

=== Details

More tests: http://github.com/akkartik/wart/blob/d863ad0748/030.test#L8

This change costed[4] me 30 LoC[5]. However that underestimates the complexity costs; eval now has an additional parameter to indicate when it's being called within a comma expression. So far I've been focused on just getting this working; now I'll spend some time reclaiming spaghetti.

[1] http://github.com/akkartik/wart/blob/a345f64d24/008eval.cc#L85. Why not just tag its elements with quote? http://news.ycombinator.com/item?id=4038195.

[2] http://github.com/akkartik/wart/blob/a345f64d24/007scope.cc#L131

[3] http://github.com/akkartik/wart/blob/a345f64d24/008eval.cc#L272. The final 'true' argument suppresses '' stripping.

[4] http://akkartik.name/blog/28672493

[5] git diff --stat c7068c0a85 d863ad0748 *.cc (skipping extra tests)



2 points by rocketnia 4346 days ago | link

"without quote, Kernel can't use this solution,"

Er, I'll assume you're talking about the fact that Kernel omits quote from the core language, and instead leaves it up to programmers to implement their own nonstandard quote if they need it.

  ($define $q
    ($vau (result) env
      result))
Even so, I'm not sure what having quote has to do with anything. Your examples don't use quote except to get first-class access to symbols, which you could already get access to as the unevaluated arguments of an fexpr call.

---

"so it can't use apply with operatives, and so its fexprs are less powerful."

I can understand if you've got the @ syntax on your mind and you'd like to squeeze a lot of value out of it, the way Arc squeezes so much out of putting things in functional position. However, whatever power you get here, I don't think it makes up for the ways you undermine your language, as I describe in my other comment.

As we continue to discuss this, it might help if we look at things in terms of John Shutt's own thorough definitions of expressive and abstractive power (http://lambda-the-ultimate.org/node/4345#comment-66918). A formal theory can't tell us how to formalize the informal things we care about, but if we do manage to use it well, we can skip ahead to more profound conclusions. This theory in particular has gotta be extremely relevant to Kernel, since it's by the same person. :-p

-----

1 point by akkartik 4346 days ago | link

I haven't looked at your link yet, but I want to clarify my comment first so that we can attack it together after I'm updated. ^_^

My solution relies on unquote and therefore on backquote. I don't recall Kernel mentioning them; scheme seems to ignore them in general. But let's assume that they are implementable just like quote. When I say "quote" I mean this holy trinity :)

I know Kernel doesn't prevent quote, but it discourages it. Even if you got apply working with backquoted macros in Kernel, it wouldn't be very helpful if most macros were backquote-less as a matter of course. This seems like a limitation of the philosophy.

More strongly, I want to argue that having syntax for quote/backquote/unquote is valuable. In wart all symbols are overrideable[1]. It uses punctuation for quote/backquote/unquote/splice to highlight that they are different from symbols, more fundamental to the programming model. Supporting apply for macros has made them even more so, even more fundamentally entangled together and baked into the interpreter.

[1] The one exception is fn. Perhaps I should make it λ? Nah, that doesn't solve the problem. Hmm, the only punctuation character wart hasn't already put to use is #.. :D

-----

2 points by rocketnia 4343 days ago | link

"My solution relies on unquote and therefore on backquote."

Oh, right.

---

"More strongly, I want to argue that having syntax for quote/backquote/unquote is valuable."

I don't think that's as expressive as infix syntax. With the right kind of a.b syntax, we could write `(a b ,c) as qq.(a b uq.c), trading in some readability for the flexibility to define our own variants.[1] Would you still want to have dedicated quasiquotation syntax then?

(Even I might answer yes sometimes. The staged fexpr system I describe at http://arclanguage.org/item?id=15868 uses unquote syntax as a way to compute during a previous stage of the command processor.)

[1] Penknife does something like this, but the use of structured string manipulation instead of s-expressions forces it to use a string-like escaping mechanism for unquote: qq.[a b \,c]

-----

1 point by akkartik 4343 days ago | link

Yeah, that's really interesting.

But is it convincing that existing lisp syntax is more valuable than Kernel's approach of no syntax?

-----

1 point by rocketnia 4343 days ago | link

"But is it convincing that existing lisp syntax is more valuable than Kernel's approach of no syntax?"

Well, I'd say so, yeah. I'd say `foo is a less helpful syntax than a.b, but still helpful.

-----

1 point by akkartik 4343 days ago | link

Thanks. I'm going to keep the qq.() idea up my sleeve. It's totally consistent with my idea that symbols should be overrideable and syntax should not.

-----

2 points by rocketnia 4346 days ago | link

Doesn't this feature mean I have to use quasiquotation to build macro results if I want this behavior? I'm guessing if I try to use any function as I'm building macro results, it'll strip '' on the way into the function. This limits me to fexprs that don't use functions this way. And if I use a typical macro, that macro will probably be prepared for splicing itself, which means it too will intentionally strip '' on the way in.

Now that we're disarmed of functions and of splice-friendly macros (which probably encompasses almost the entire standard library!), we have to see if we can make do with whatever we have left. I don't think that's very much in the spirit of "first-class."

-----

1 point by akkartik 4346 days ago | link

Ah, I figured out what you were getting at:

  wart> (def helper(a b) `(cons ,a ,b))
  wart> (mac foo(a b) (helper a b))
  wart> (foo 1 '(2 3))
  (1 2 3)
  wart> (foo @'(1 (2 3)))
  008eval.cc:79 calling macros with splice can have subtle effects (http://arclanguage.org/item?id=15659)
  005types.cc:263 can't coerce number 2 to function
Eep! You're right, this is a fairly common use case.

The good news is that wart's warning system has held up. If it can't handle it it throws that warning.

-----

1 point by akkartik 4335 days ago | link

macros-calling-functions-generating-backquoted-lists now works!

The cost is a special variant of eval to call inside macros: http://github.com/akkartik/wart/commit/e3124e9559#diff-3

I still emit the warning, because examples like this fail:

  wart> (def helper(a b) `(cons ,a ,b))
  wart> (mac foo args (helper @args))
  wart> (foo @'(1 (2 3)))
  008eval.cc:79 calling macros with splice can have subtle effects (http://arclanguage.org/item?id=15659)
  005types.cc:263 can't coerce number 2 to function

-----

1 point by akkartik 4346 days ago | link

I'm not sure I understand you, so let me show a few examples:

  ; function calls inside macros?
  wart> (def f(x) x)
  wart> (mac foo(a b) `(cons ,a ,f.b))
  wart> (foo @'(1 (2 3)))
  (1 2 3)

  ; splice friendly macros?
  wart> (foo @(foo @'(1 ((2 3)))))
  (1 2 3)

  ; splice friendly macros?
  wart> (mac bar(a b) `(cons 3 ,@(foo a b)))
  wart> (bar @'(1 (2 3)))
  (3 . 1)
Do these address any concerns?

-----

1 point by rocketnia 4346 days ago | link

It does tell me I don't understand your system yet, at least. :-p

So if x is a variable containing ''abc, when we say (bar x x) we wind up evaluating (cons 3 ''(cons ''x ''x))?

When we evaluate (cons ''x ''x), it strips off the '' to get (cons foo foo), and then we end up with (''abc . ''abc)?

Then, altogether, we end up with a result of (3 . (''abc . ''abc)), which appears at the REPL complete with ''?

Let me know if I'm getting anything wrong.

-----

1 point by akkartik 4346 days ago | link

Almost:

  wart> (mac foo(a b) `(cons ,a ,b))
  wart> (mac bar(a b) (prn `(cons 3 ,@(foo a b)))) ; prn for debugging
  wart> ((fn(x) (bar x x)) 'abc)
  (cons 3 x . x)
  004cell.cc:158 car of non-cons: x
  004cell.cc:158 car of non-cons: x
  (3 . abc)
My bar example is poorly constructed; besides that I think you're right.

-----

1 point by rocketnia 4343 days ago | link

Oh, I see. Would you mind showing me what happens with (mac bar(a b) `(cons 3 ,(foo a b)))?

-----

1 point by akkartik 4343 days ago | link

  wart> (mac foo(a b) `(cons ,a ,b))
  wart> (mac bar(a b) `(cons 3 ,(foo a b)))
  wart> ((fn(x) (bar x x)) 'abc)
  005types.cc:263 can't coerce symbol abc to function
There was a typo in grandparent, so let me summarize the correct versions:

  wart> (mac foo(a b) `(cons ,a ,b))
  wart> (mac bar(a b) `(cons 3 ,@(foo a b)))
  wart> ((fn(x) (bar x x)) @'(abc))
  (3 . abc)

  wart> (mac foo(a b) `(cons ,a ,b))
  wart> (mac bar(a b) `(cons 3 ,(foo a b)))
  wart> ((fn(x) (bar x x)) @'(abc))
  005types.cc:263 can't coerce symbol abc to function   ; no change
I think you're asking what happens to (''a b c). Hmm, I don't translate that to ''(a b c). It seems to be acting like (a b c). Does that seem right?

---

Another potential concern: I'm using a single boolean to track whether we encounter a '', and I reset it before unquote's eval and check it after. I think it might need to be a stack of booleans to handle nested expressions, but I've not been able to come up with a failing test case.

http://github.com/akkartik/wart/blob/6d5d5a845c/007scope.cc#...

-----

1 point by akkartik 4343 days ago | link

Ah, I answered my own question. It turns out this doesn't work:

  (all present? '((1) (2 4 6)))
if you define all as:

  def all(f seq)
    (and @(map f seq))
For precisely this reason.

(present? is a synonym for idfn.)

-----

1 point by rocketnia 4343 days ago | link

Hmm, what happens when you say `,(write `,'foo)? ^_^

-----

1 point by akkartik 4343 days ago | link

  wart> `,(write `,'foo)
  foo005types.cc:263 can't coerce symbol foo to function
Is that what you expect? I'm not sure what you're trying.

-----

1 point by rocketnia 4342 days ago | link

Something bugs me about this claim:

" '' is an internal detail. The reader provides no way to type it in. If you ever see it printed at the REPL, that's a bug."

If unquote adds a '', then `,'foo should return ''foo, right? Then 'write should write ''foo at the REPL.

In order to weasel out of anything that stripped '' from the arguments to a function, I tried putting `, around the whole command, in the hopes that it would somehow manipulate the state of the don't-strip-'' flag(s) for the duration of the command.

In any case, there's no reason foo should be called, is there? O_o

In other news, this might be an easy test case for the scope of the don't-strip-'' flag. If your implementation sets it to true on the way in and false on the way out, then it'll become false on the way out of the inner `, , rather than recovering its previous value of true.

-----

1 point by akkartik 4333 days ago | link

"If unquote adds a '', then `,'foo should return ''foo, right?"

Unquote doesn't add '', @ does. Perhaps that changes your example?

"In any case, there's no reason foo should be called, is there? O_o"

:) Yeah that's a bug with my paren inference; it was implicitly wrapping the expression in parens. I'd never seen backquote-comma before. Here's a temporary workaround:

  wart> (list `,(write `,'foo))
  foo(foo)  ; ignore the (foo) -- it's the return value
Update: fixed (http://github.com/akkartik/wart/commit/70cfb18504)

  wart> `,(write `,'foo)
  foofoo

-----

1 point by akkartik 4342 days ago | link

Hmm, I haven't fully digested this, but I do have a passing test on nested unquote: http://github.com/akkartik/wart/blob/a5a9f2ffcd/030.test#L35

-----

1 point by akkartik 4343 days ago | link

One thing I should explicitly mention: you could replace '' with an extra bit of metadata in all values (symbols, cons cells). I'm averse to adding a field to my core Cell data type for this because I don't want a reader coming to see it for the first time to be distracted with house-keeping for a special-case. It also seems more space efficient to only pay for '' when you have to, but that's a negligible concern.

-----