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.
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.
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:
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
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.
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.
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.
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.
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.
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:
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!
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)))
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:
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:
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.
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
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:
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.
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.
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..?
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.
