Arc Forumnew | comments | leaders | submitlogin
An ssyntax bug that seems to need fexprs
2 points by akkartik 5066 days ago | 15 comments
All the arc releases going back to arc0 suffer from the following bug:

  arc> (let f prn:= (f x 3))
  Error: "reference to undefined identifier: _x"
What's going on here? Since prn:assign is a function it evaluates all its args.

But if that's true, how does this work?

  arc> (prn:= x 3)
  3
  3
The arc compiler has three clauses to make ssyntax work for macros in functional position.

  http://github.com/nex3/arc/blob/f01d3f9c66/ac.scm#L29
  http://github.com/nex3/arc/blob/f01d3f9c66/ac.scm#L550
(It's taken me forever to understand those comments.)

With its fexprs, wart can correctly implement compose by creating a first-class anonymous macro:

  mac compose($f $g)
    `(lambda '$args
       eval `(,,$f (,,$g ,@$args)))
(http://github.com/akkartik/wart/commit/73d9b58ad8)


1 point by rocketnia 5066 days ago | link

"the following bug"

Hey, that's not a bug, that's just metafns. :-p One of my mini-goals writing Penknife was to make metafns more consistent and user-definable, more like macros than special forms. Every syntax would return a "parse fork", which could expand in a few different ways based on being in functional position (metafns and macros), being in assignment position (setforms), etc. The infrastructure was there, and I used it to define ":", but I don't think I ever got around to making an in-language syntax for conveniently defining metafns.

Even if there were a convenient way to define metafns in Penknife, 'compose would still be a complex case: Given ((compose a b) c), we have to decide what data structure 'a receives as input. For maximum flexibility in Penknife, my choice was to define an all new data structure just for this purpose and extend the compiler to deal with it properly. On the downside, that's not a very brief way to go about it. XD

Anyway, with fexprs instead of a compilation phasse, metafns are streamlined already, since--as you've demonstrated--things can return fexprs.

I don't really know the Wart semantics, but here's my Kernel-like-pseudocode take on 'compose (if I choose not to make a separate expression type for the occasion):

  ; Given ((compose a b c) d e f), we evaluate
  ; ('<value of a> ('<value of b> ('<value of c> d e f))), using the
  ; binding of 'quote captured at compose's definition site (i.e., right
  ; here).
  (def compose ops
    (unless ops (err "Not enough operators to 'compose."))
    (let (last-op . ops) rev.ops
      (zap [map [list quote _] rev._] ops)
      (zap [list quote _] last-op)
      (vau args env
        (eval (foldr list ops (cons last-op args)) env))))
Here's a non-varargs version of the same thing:

  (def compose (a b)
    (zap [list quote _] a)
    (zap [list quote _] b)
    (vau args env
      (eval (list a (cons b args)) env)))
With your version, I'm a bit concerned about hygiene: What if the $f and $g expressions contain '$args? I think it could at least help to make 'compose a function rather than a macro, so that any preexisting instance of '$args is resolved outside your own '$args scope.

-----

1 point by akkartik 5066 days ago | link

$args is an implicit gensym :)

"I think it could at least help to make 'compose a function rather than a macro, so that any preexisting instance of '$args is resolved outside your own '$args scope."

There's no difference between functions and macros in wart.

-----

2 points by rocketnia 5066 days ago | link

"$args is an implicit gensym :)"

I wasn't asking a question like that. :-p What I was asking was more along the lines of whether some expression like (compose foo $args) could end up with variable capture issues.

For all I know, maybe it wouldn't. Kernel's approach to evaluating an arg in the caller's scope is to pass scopes around as first-class values. Your approach is to change the scoping rules around in ways I don't really grok yet. Also, the way you're expanding $foo might be a kind of code-walking that essentially takes the form of its own kind of scoping rule.

-

"There's no difference between functions and macros in wart."

I think I already understand what you're trying to clarify here, too. What I'm saying is to use something other than "mac" to define 'compose.

If we forget about "functions" for a moment, what I mean is that instead of doing this...

  mac compose($f $g)
    `(lambda '$args
       eval `(,,$f (,,$g ,@$args)))
...it might be more hygienic to do something like this:

  mac compose($f $g)
    with (f eval.$f g eval.$g)  ; outside the scope of $args
      `(lambda '$args
         eval `(,,f (,,g ,@$args)))
I expect it's easier to make this change by replacing "mac" with "def":

  def compose(f g)
    lambda '$args
      eval `(,f (,g ,@$args))
(Keep in mind that this version still doesn't quote 'f and 'g, which I recommend doing in case they're lists or something.)

-----

2 points by akkartik 5066 days ago | link

Wow, you're right, compose doesn't need to be a macro!

Why was I thinking of it as a macro? Ah, I was blindly copying the arc version. And it looks like that doesn't need to be a macro either:

  (def compose fs
    (if (no cdr.fs)
      car.fs
      (fn args
        (car.fs (apply (apply compose cdr.fs) args)))))
Does that seem right? It seems to be working fine..

---

I still don't follow your arguments about hygiene. I suppose it's conceivable that code could use args2179 directly without going through gensym. Or that compose could call itself recursively and override $args in the caller's scope, and that it would be for some reason undesirable. Is either scenario what you were thinking of?

Thanks a lot for the comments. I think you understand the implications of my design decisions where I've been flailing around writing unit tests as I think up special-cases.

-----

1 point by rocketnia 5064 days ago | link

"Does that seem right?"

Yeah, I don't know why Arc's 'compose is a macro. I think I've tried to (apply compose ...) at least once and gotten bitten by that. ^^

---

"I still don't follow your arguments about hygiene. I suppose it's conceivable that code could use args2179 directly without going through gensym. Or that compose could call itself recursively and override $args in the caller's scope, and that it would be for some reason undesirable. Is either scenario what you were thinking of?"

I don't think so.... What I mean is, is it possible for the value inserted with ",$f" or ",$g" to contain the symbol '$args (assuming $ isn't a reader macro) in a way that causes it to be confused with the lambda's meaning of '$args?

  mac compose($f $g)
    `(lambda '$args
       eval `(,,$f (,,$g ,@$args)))

-----

1 point by akkartik 5064 days ago | link

Ah, I see. The answer is no, there can be no $vars after evaluation. $ is indeed expanded at read time.

-----

1 point by akkartik 5066 days ago | link

"(Keep in mind that this version still doesn't quote 'f and 'g, which I recommend doing in case they're lists or something.)"

You mean for something like:

  (compose '(1 2 3) *)

?

-----

1 point by rocketnia 5064 days ago | link

Yep. Here's a slightly-less-toy toy example:

  (let (foo nil bar nil)
    ; ...build foo and bar up as lists...
    ; ...
    (foo:- len.bar 1)
    ; ...
    )
If 'compose creates (<value of foo> (<value of -> len.bar 1)), then <value of foo>, being a list, might evaluate as an fexpr call.

-----

1 point by akkartik 5064 days ago | link

In wart fexprs either evaluate to a compiled op or to a list with the atom evald-lambda in the car.

You do raise the question of dealing with lists and hashes in function position. Wart doesn't do that yet, and it wasn't even on my todo list so far.

-----

1 point by rocketnia 5064 days ago | link

"You do raise the question of dealing with lists and hashes in function position. Wart doesn't do that yet, and it wasn't even on my todo list so far."

Oh, if you choose not to add that, I don't mind. ^_^

Still, as long as there's no quoting, I'm betting people can inject code in there, like (compose '$args '(while t)). Not that it's wrong to design 'compose with that code-injection feature in mind, but it would surprise me.

-----

1 point by akkartik 5057 days ago | link

I'm not out of the woods yet. If I define rem as follows:

  def rem(f seq)
    if seq
      if (f car.seq)
        (rem f cdr.seq)
        (cons car.seq (rem f cdr.seq))
The simplest definition for keep is now:

  def keep(f seq)
    (rem ~f seq)
Unfortunately this doesn't work. I've narrowed it down to one passing implementation:

  def keep(f seq)
    (rem (fn (_) ~f._) seq) ; unquoted params

  arc> (keep nil? '(1 2 nil 4 nil))
  (nil nil)
and one failing one:

  def keep(f seq)
    (rem (fn'(_) ~f._) seq) ; quoted params

  arc> (keep nil? '(1 2 nil 4 nil))
  nil ; wrong!
Does anybody (rocketnia?) see why this may be? I think it's because f always sees its arg to be car.seq unevaluated. Is there a better implementation for compose? Or is my eval broken?

http://github.com/akkartik/wart/blob/501ac55f30/020.wart

-----

1 point by rocketnia 5056 days ago | link

I expect that to get 'car.seq unevaluated, as you say. Those two simplified examples are both expected behavior, IMO, and so your problem is that ~f isn't acting like (fn (_) ~f._).

-

I don't know if this is on-topic, but here's your definition of 'complement:

  def complement($f)
    fn '$args
      eval `(no:,$f ,@$args)
Wouldn't it be easier (and possibly more hygienic) to do it this way?

  def complement(f)
    compose no f
-

"Is there a better implementation for compose ? Or is my eval broken?"

I don't know your scoping rules well enough to say. ^^; Here's your 'compose:

  def compose($f $g)
    fn '$args
      eval `(,$f (,$g ,@$args))
What environment does 'eval evaluate things in? What expression does it evaluate, exactly (including anything to do with implicit gensyms)?

-----

1 point by akkartik 5054 days ago | link

Ah, thanks for the simplified complement :/ Yeah my tests made no sense.

"I don't know your scoping rules well enough to say. ^^"

:) I just meant that if compose seems right then eval must be broken.

"What environment does 'eval evaluate things in? What expression does it evaluate, exactly?"

I'm not sure how to answer what expression it evaluates, but you're right, the problem's the non-standard scopes. The anonymous macro created by compose and bound to f inside rem gets as its arg just car.seq, so it seems to be having seq bound to the same variable on every recursive call. That's the bug; now to go track down why it is happening.

-----

2 points by akkartik 5051 days ago | link

I figured it out. I was being very lax in ordering my scopes.

The data structure of traditional lexical environments consists of a table of bindings, and a pointer to the next outer binding:

  A -> B -> C -> D
Here A is the innermost scope that gets checked first. The sequence of scopes checked is ABCD.

Wart's new scoping rules are for macros: we provide access to the caller's scope.

  A -> B -> C -> D
   \
    E -> F -> G -> H
Each 'level' of scopes is a traditional lexical environment. Since we want to only use caller scopes for bindings we can't find in the lexical environment, we traverse the lexical environment before 'dropping down a level to the caller's environment. Thus the order of lookups is ABCDEFGH.

This was where things stood until I ran into keep. The problem with keep was that the tree structure was more complex. Consider this slightly more complex scope tree:

  A -> B -> C -> D
   \         \
    E -> F    G -> H
It's clear that ABCD comes before EFGH. But what order should the caller scopes be traversed in? It turns out you want to unwind the stack first close to the callee: ABCDEFGH, which corresponds to a breadth-first traversal. However, I had lazily done the simplest possible thing, a depth-first search. ABCDGHEF. Wrong.

---

This took forever to debug because I struggled to find a nice way to visualize scopes. One drawback of everything being an f-expr is that I quickly run into complex trees that are impossible to visualize (http://github.com/akkartik/wart/commit/3932165bbf until http://github.com/akkartik/wart/commit/9ffcdec864). Eventually I came up with the idea of visualizing paths instead (http://github.com/akkartik/wart/commit/b234594cfa). I came up with a helper that takes a sym and enumerates in order all the paths that find bindings to it in the current environment. Once I did that it became easy to see that 10 should come before 0010 (0 is a horizontal edge, 1 is a diagonal edge)

-----

1 point by akkartik 5048 days ago | link

This seems relevant: "With macros, you have hygiene issues because you work with quoted identifiers, that somehow have to refer back to their original bindings. With fexprs, you have the luxury of using live values instead of identifiers referring to values, thereby achieving hygiene simply through good old lexical scope, already built-in to the language anyway." http://lambda-the-ultimate.org/node/4345#comment-66868

-----