Arc Forumnew | comments | leaders | submitlogin
Clojure's syntax-quote in arc
4 points by malisper 3740 days ago | 16 comments
I was thinking it would be nice to have something similar to clojure's syntax-quote which makes writing macros easier through autogensym.

http://blog.8thlight.com/colin-jones/2012/05/22/quoting-without-confusion.html

I managed to get a basic implementation that replaces symbols that end in "@" with a uniq version of it and replaces all of the symbols that are the same with the same uniq.

  (mac syntax-quote (exp)
    (let uniqs (table)
      (list 'quasiquote ((afn (exp)
			   (if (auto exp) (or= uniqs!exp (uniq exp))
			       (atom exp) exp
			       t          (map self exp)))  
		         exp))))

  (def auto (exp)
    (and (atom exp) (endmatch "@" (string exp))))
It has several problems including relying on quasiquote and it autogensyms every symbol that ends with "@" within exp, even if it was unquoted first (the second one may or may not be a problem). I was hoping that by fixing these problems we could easily replace quasiquote with syntax-quote (make ` be syntax-quote instead of quasiquote) because it should make writing macros easier.


3 points by fallintothis 3740 days ago | link

Hey, this is promising work so far. Couple of observations:

1. FYI, uniq doesn't take any arguments in vanilla Arc:

  arc> (syntax-quote (a@ b c))
  Error: "procedure ar-gensym: expects no arguments, given 1: a@"
I'm apparently the sole weirdo who doesn't use Anarki at all, so I had to change this. It's not really necessary for the functioning of this macro, so no biggie.

2. In Arc, the t would be implied by if having an odd number of clauses:

  (if test1 then1
      test2 then2
      ...
            else)
In fact, the recent discussion at http://arclanguage.org/item?id=18215 is related.

3. The uniqs!exp ssyntax stands for (uniqs 'exp) (quoted argument), when you want (uniqs exp) (unquoted argument). You could either write (uniqs exp) by hand, or else use uniqs.exp. As it stands now, this is a bug because you're always looking up the same hash table key, namely 'exp:

  arc> (syntax-quote (a@ b c))
  (gs1745 b c)
  arc> (syntax-quote (a@ b@ c))
  (gs1746 gs1746 c)
  arc> (ssexpand 'uniqs!exp)
  (uniqs (quote exp))
  arc> (ssexpand 'uniqs.exp)
  (uniqs exp)
4. It has several problems including relying on quasiquote

If it helps, here's a pure-Arc implementation of quasiquote: https://bitbucket.org/fallintothis/qq/src

5. it autogensyms every symbol that ends with "@" within exp, even if it was unquoted first

Simple to fix, if it is an issue:

  (mac syntax-quote (exp)
    (let uniqs (table)
      (list 'quasiquote
            ((afn (exp)
               (if (auto exp)     (or= uniqs.exp (uniq))
                   (atom exp)     exp
                   (unquoted exp) exp
                                  (map self exp)))
             exp))))

  (def auto (exp)
    (and (atom exp) (endmatch "@" (string exp))))

  (def unquoted (exp)
    (or (caris exp 'unquote)
        (caris exp 'unquote-splicing)))

  arc> (let a@ 'd (syntax-quote (a@ b c)))
  (gs1758 b c)
  arc> (let a@ 'd (syntax-quote (,a@ b c)))
  (d b c)
6. I was hoping that by fixing these problems we could easily replace quasiquote with syntax-quote (make ` be syntax-quote instead of quasiquote) because it should make writing macros easier.

Could also just hook into mac instead of quasiquote, as in http://www.letoverlambda.com/index.cl/guest/chap3.html#sec_5 This would be an easier way to extend vanilla Arc: just redefine the mac macro, or else define a variant of it if you need to preserve the old "raw" behavior.

-----

2 points by malisper 3739 days ago | link

I managed to implement a version that redefines mac. If people want mac to stay the same we could just switch them so defmacro becomes the new version and mac remains the same. I realized that I actually liked the fact that it autogensyms the symbols that are within an unquote because otherwise you would still need to use uniq in cases where you quote inside of an unquote and you need the symbols to be the same.

  (= defmacro mac)

  (defmacro mac (name args . body)
    (let uniqs (table)
      `(defmacro ,name ,args ,@((afn (exp)
				  (if (auto exp) (or= uniqs.exp (uniq exp))
				      (atom exp) exp
				      t          (map self exp)))  
			        body))))

  (def auto (exp)
    (and (atom exp) (endmatch "@" (string exp))))

-----

2 points by malisper 3740 days ago | link

First of all thanks for finding 3, I only tested the code very in very simple cases.

In response to 2, when I am reading lisp code in the format you suggested, I cannot tell whether the else case is actually part of the clause above it or is actually an else case. I just use t to make it explicit that this is the else case.

And I agree with you for 6. We should just extend mac so that it autogensyms the code it is given. There is no harm in doing this since all of the code previously written should still work.

-----

1 point by akkartik 3739 days ago | link

Yeah, I too like not relying on an implicit 'else'. In fact, I use :else instead of t to be even more clear.

This is all most excellent. Don't be afraid to commit and push! Feel free to override the default mac if there aren't any obvious problems. There aren't very many people using anarki, and we can always roll it back later if necessary.

-----

2 points by malisper 3739 days ago | link

I'm having issues figuring out where to put it in anarki since it has to be defined after "endmatch". I'm going to have to commit it later.

-----

2 points by malisper 3739 days ago | link

I am having some issues with map. Since map only works on proper lists it doesn't work on all of the code. I am trying to change the code so that it recurs on tree instead but I'm having some trouble doing that.

-----

2 points by malisper 3739 days ago | link

I managed to get a version to work using treewise.

  (= defmacro mac)
  
  (defmacro mac (name args . body)
    (let uniqs (table)
      `(defmacro ,name ,args ,@(treewise cons
				         [if (auto _)
					     (or= uniqs._ (uniq _))
					     _]
				         body))))

  (def auto (exp)
    "Tests whether an expression should be autogensymed"
    (and exp (atom exp) (endmatch "%" (string exp)))) 
I'm wondering if we should allow tree-subst (or at least a new function like tree-subst) to use functions in which case the code using treewise above could be written as:

  (tree-subst auto [or= uniqs._ (uniq _)] body)

-----

1 point by akkartik 3739 days ago | link

I'm taking a look now.

Edit 40 minutes later: Everything looks great![1] The unit tests in arc.arc.t all pass, and the HN server comes up fine. I tried submitting, editing, commenting, everything works.

Edit 75 minutes later: I've added your tree-subst suggestion[2]. Good idea, thanks!

[1] https://github.com/arclanguage/anarki/commit/8c6c94c6c7

[2] https://github.com/arclanguage/anarki/commit/e0a2b1e4c4

-----

2 points by malisper 3739 days ago | link

I realized the tree-subst is going to have to be a little more complicated. If the function isn't expecting a list it's going to throw an error.

  (tree-subst even [+ _ 1] '((1 . 2) . (3 . 4)))
This code throws an error even though it is very clear what the result should be. I'm not sure what the best way to fix it is. I managed to write a version that does work but it looks pretty ugly.

  (def tree-subst (old new tree)
    (with (test (testify old)
	   f (if (isa new 'fn) new (const new)))
      (if (no tree)        '()
          (atom&test tree) (f tree)
	  (atom tree)      tree
	  t                (cons (tree-subst test f (car tree))
			         (tree-subst test f (cdr tree))))))
I just realized there probably is a better way to write it using treewise. Something like:

  (def tree-subst (old new tree)
    (with (test (testify old)
	   f (if (isa new 'fn) new (const new)))
      (treewise cons [if (test _) (f _) _] tree)))
20 minutes later: added to anarki

-----

1 point by akkartik 3739 days ago | link

Hmm, that significantly weakens tree-subst since you can no longer search-and-replace over subtrees.

  arc> (tree-subst '(1 2) '(3 4) '((1 2) (5 6)))
  ((3 4) (5 6))
But on the other hand tree-subst compared subtrees using is until my change today, and there are no calls to tree-subst in the repo. So I suppose there's no way to see what the original authors had in mind. Anybody else have use cases to share?

On the third hand, it's easy to use tree-subst the way you want with a slight change to the call, like I showed in my tests:

  (tree-subst atom&even [+ _ 1] '((1 . 2) . (3 . 4)))
That doesn't seem too onerous. What do you think?

-----

2 points by fallintothis 3739 days ago | link

If you want to do substitution using a function, it seems to me like the operation is more of a roundabout map. Particularly if it's just over the atoms of a tree, it's easy to think of the higher-order functions from a different angle, instead of trying to make tree-subst do everything:

  (def leafmap (f tree)
    ; really, just (treewise cons f tree)
    (if (atom tree)
        (f tree)
        (cons (leafmap f (car tree))
              (leafmap f (cdr tree)))))

  (def whenf (test f)
    [if (test _) (f _) _])

  arc> (leafmap (whenf even [+ _ 1]) '((1 . 2) . (3 . 4)))
  ((1 . 3) 3 . 5)
Other name ideas: treemap, maptree, hyphenated versions of any of those, map-leaves.

Digression: the issue I've been more annoyed by in Arc's suite of "tree" utilities is sloppiness with direct cdr recursion. Functions have no way of discerning whether some list (a b c) they're looking at is a "top-level" form or if it's just from recursing on cdrs of (x y z a b c). E.g., using ontree in http://arclanguage.org/item?id=18217:

  arc> (let if 2 (+ if (do 2)))
  4
  arc> (count-ifs-with-do (list '(let if 2 (+ if (do 2)))))
  1
  arc> (ifs-with-do (list '(let if 2 (+ if (do 2)))))
  ((if (do 2)))
  arc> (ifs (list '(let if 2 (+ if (do 2)))))
  ((if 2 (+ if (do 2))) (if (do 2)))
I usually want the recursion to instead occur more like

  (def ontree (f tree)
    (f tree)
    (unless (atom tree)
      (each subexpr tree
        (ontree f subexpr))))
Or even just have the above as a separate function, like on-exprs or something.

Maybe a similar maptree would be helpful:

  (def maptree (f tree)
    (let newtree (f tree)
      (if (atom newtree)
          newtree
          (map [maptree f _] newtree))))

  arc> (let uniqs (table)
         (maptree [if (caris _ 'gensym) (or= uniqs._ (uniq)) _]
                  '(let (gensym a) 5 gensym <--on-its-own (+ (gensym a) 10))))
  (let gs1736 5 gensym <--on-its-own (+ gs1736 10))
Although the above formulation has the potential for infinite looping; e.g., (maptree [cons 'a _] '(a))...maybe better to do something like

  (def maptree (f tree)
    (if (atom tree)
        (f tree)
        (let newtree (f tree)
          (check newtree atom (map [maptree f _] newtree)))))

  arc> (maptree [cons 'a _] '(a))
  ((a . a) (a . a))

-----

2 points by malisper 3739 days ago | link

I'm pretty sure we have to do the car/cdr recursion because functions like map and each don't work on pairs, they only work on proper lists and most trees are not proper lists. Code such as the following wouldn't work mainly because of the use of map/each.

  (treemap [cons 'a _] '(a . a))
I'm pretty sure we would also only want treemap to work only on atoms (your first example), it doesn't make much sense to apply the function then recur on the new tree (I find it very hard to figure out what is going happen). The problem with this is we can no longer call functions on subtrees. I do like the idea of treemap which could be written more cleanly as:

  (def treemap (f tree)
     (treewise cons f tree))
I'm pretty sure we should stick to akkartik's implementation of tree-subst (we can actually remove the first clause because it is covered in the second clause) because it works just like all of the other higher order functions where they testify their input and it works on entire subtrees.

Note: you can use iff instead of writing a new function whenf

-----

2 points by fallintothis 3738 days ago | link

I'm pretty sure we have to do the car/cdr recursion because functions like map and each don't work on pairs, they only work on proper lists and most trees are not proper lists.

I think the obvious problem with that reasoning is it reinforces the notion that map, each, etc. "should" break on dotted lists. Even if that's the case, it's not like ontree & pals couldn't open-code a recursive function that worked on dotted tails; I merely used each/map in my example definitions as a convenience. If you prefer:

  ; Again, not that this has to replace the standard 'ontree...just can't think
  ; of a better name.

  (def ontree (f expr)
    (f expr)
    (unless (atom expr)
      ((afn (subexpr)
         (if (atom subexpr)
             (and subexpr (ontree f subexpr))
             (do (ontree f (car subexpr))
                 (self (cdr subexpr)))))
       expr)))

  arc> (ontree prn '(def f (x . xs) (cons nil xs)))
  (def f (x . xs) (cons nil xs))
  def
  f
  (x . xs)
  x
  xs
  (cons nil xs)
  cons
  nil
  xs
This versus the standard ontree:

  arc> (ontree prn '(def f (x . xs) (cons nil xs)))
  (def f (x . xs) (cons nil xs))
  def
  (f (x . xs) (cons nil xs)) ; <-- this potentially looks like a call to f!
  f
  ((x . xs) (cons nil xs))
  (x . xs)
  x
  xs
  ((cons nil xs))
  (cons nil xs)
  cons
  (nil xs)
  nil
  (xs)
  xs
  nil
  nil
On that note, I certainly find myself working around Arc's rampant disregard for dotted lists in my projects:

https://bitbucket.org/fallintothis/contract/src/d1b4ff38afaf...

https://bitbucket.org/fallintothis/macdebug/src/0be201a14295...

https://bitbucket.org/fallintothis/qq/src/04a5dfbc592e5bed58...

Then some trouble spots I found with avoiding sloppy cdr-recursion:

https://bitbucket.org/fallintothis/contract/src/d1b4ff38afaf...

https://bitbucket.org/fallintothis/contract/src/d1b4ff38afaf...

Note: you can use iff instead of writing a new function whenf

Not in vanilla Arc, I'm afraid. :) And I've always thought Anarki's iff is poorly named, due to the English collision with the "if and only if" abbreviation.

-----

3 points by malisper 3738 days ago | link

It does seem like a good idea, abstracting as a list of lists instead of a binary tree. The best name I can think of is onlol. I really don't think that we should extend map and each to work on dotted lists, instead we should create other functions treemap and treeach since dotted lists are actually trees and no longer lists.

-----

1 point by akkartik 3738 days ago | link

Hmm, it sounds like we need three sets of primitives: for operating on lists, trees and code (like trees, but aware of call vs arg positions). Perhaps we could use the same names like map and count but first tag the arg as tree or code..?

-----

2 points by malisper 3739 days ago | link

I didn't notice that your version could check against subtrees. Another possibility would be to use errsafe along with the function (but I'm worried that might be too dangerous). Other than that I would have to agree with your design. I played around with the common lisp design of subst-if and found it does the exact same thing as yours but it also does not test nil. This can easily be done in arc in a similar way to atom&... with idfn&... I would have to go with your design for now but we might want to think about other designs such as whether or not to test nil.

-----