Arc Forum | Traversal

Arc Forum

Traversal

15 points by pg 6117 days ago | 11 comments

One thing I've been meaning to do for a while is to try and figure out what the ideal general structure-traversing operator should look like. The bst-trav function in bst.arc set off my missing abstraction detector. I had that "I've written this code about 30 times before" feeling.

So here is a shot at a general-purpose traverser:

  (mac trav (x . fs)
    (w/uniq g
      `((afn (,g)
          (when ,g
            ,@(map [list _ g] fs)))
        ,x)))

You can get a lot of different behaviors out of it. E.g. printing the elements of a list is:

  arc> (trav '(1 2 3) [pr (car _)] [self (cdr _)])
  123nil

This is only to illustrate its behavior, of course. You'd only use it to traverse more complicated structures. E.g. bst-elts becomes

  (def bst-elts (b)
    (accum a (trav b [self _!l] [a _!d] [self _!r])))

Does this seem the Right Thing?

(It's not limited to traversal of structures, incidentally.)

5 points by vincenz 6117 days ago | link

What you basically want, since you do not want pattern matching, is eliminators/folds/church-encoding (pick your favourite terminology).

-----

2 points by vrk 6117 days ago | link

  (= src car)
  (= trg cadr)
  (= w car:cddr)

  (def make-edges l
    (let edges (join l (map [list trg._ src._ w._] l))
      (let from [keep (fn (e) (is src.e _)) edges]
          (rfn fetch (a)
              (if (no a) nil
                  (atom a) (from a)
                  (join (from car.a) (fetch cdr.a)))))))

  ; Dijkstra's algorithm.
  (def shortest-paths (edges s) 
    (with (T (table)
           S (table)
           num [case _ nil +inf.0 _])
      (= T.s 0)
      (= S.s t)
      (trav edges.s
         [map [= (T:trg _) (min (num:T:trg _) (+ (num:T:src _) w._))] _]
         [map [= (S:trg _) t] _]
         [let next (keep no:S:trg (edges (map trg _)))
                 (let m (apply min (map num:T:trg next))
                   (self (keep [<= (num:T:trg _) m] next)))])
      T))

  (= edges (make-edges 
                '(a b 2) '(a c 3)
                '(b c 2) '(b d 1) '(b e 3) '(b f 2)
                '(c e 1)
                '(d e 2) '(d f 1)
                '(e f 2)))

  (prn (shortest-paths edges 'a))

It looks a bit unwieldy, and one could argue this is perverse use of the trav macro, but there you have it.

-----

3 points by mattjones 6117 days ago | link

I think this is a good abstraction. Brevity is important since the amount of logic being abstracted away isn't very much, and I think this achieves it.

You could do the same thing using just one lambda:

    (def bst-elts (b)
      (accum a (trav b (fn (x)
                           (self x!l)
                           (a x!d)
                           (self x!r)))))

That works fine and in some situations (with more complicated logic) it might be better. But the shorter version is compelling to me because brevity is so important in this case.

-----

2 points by byronsalty 6117 days ago | link

Wow. This is why I'm playing with arc. This hurt my brain for about 10 minutes but now that I understand it - it seems like the most natural way to do this.

I also got an OnLisp dejavu. Another good thing.

-----

1 point by almkglor 6117 days ago | link

How about this one instead:

  (mac trav (x . fs)
    (w/uniq g
      `((rfn go (,g)
          (when ,g
            ,@(map [list _ g] fs)))
        ,x)))

   (def bst-elts (b)
    (accum a (trav b [go _!l] [a _!d] [go _!r])))

"self" doesn't strike me as being properly descriptive of how trav uses it - so I suggest using "go" instead of "self". It would be nice to re-use "trav" instead too - although you'd have to dive in the user's code and replace 'trav with a (uniq)'ed symbol.

   (def bst-elts (b)
    (accum a (trav b [trav _!l] [a _!d] [trav _!r])))

-----

7 points by pg 6117 days ago | link

Since captured symbols are kind of freaky I want to be conservative with names: it for objs in general, and self for fns. I wouldn't want to use trav in case someone actually wants to call trav in one of the arguments.

-----

4 points by almkglor 6117 days ago | link

Well, "self" has attached itself (in my mind, anyway) to afn. Seeing "trav" use "self" is disturbing - its like "self" is an unfaithful wife or something.

"self" for "afn" is OK, because "afn" is defined as "a function which calls itself". It's not so OK for "trav", because "trav" doesn't call "itself" (yes, internally it does, but for the user of the macro, it isn't - it's traversing a structure). That's why I'd rather suggest using go. Or alternatively have an optional "go" argument:

  (mac trav (struct . body)
    (with
         (
           gofn (if (isa (car body) 'sym) (car body) 'self)
           fns (if (isa (car body) 'sym) (cdr body) body))
    (w/uniq g
      `((rfn ,gofn (,g)
          (when ,g
            ,@(map [list _ g] fs)))
        ,x))))

So:

  (trav b go [go _!l] [a _!d] [go _!r])

or:

  (trav b [self _!l] [a _!d] [go _!r])

Of course this has the problem where the user might have an existing named function that he or she just wants to call to handle some part of the structure:

   (trav b existing-fun [self _!next])

A possible alternative would be to force the user to add a ' to the gofn symbol. Since symbols cannot be applied (yet), it would unambiguously specify a special symbol to replace the default 'self:

  (mac trav (struct . body)
    (withs
         (
           is-quote-form [caris _ (car ''x)]
           quote-form-var cadr
           gofn
           (if (is-quote-form (car body))
              (quote-form-var (car body))
              'self)
           fns
           (if (is-quote-form (car body))
              (cdr body)
              body))
    (w/uniq g
      `((rfn ,gofn (,g)
          (when ,g
            ,@(map [list _ g] fs)))
        ,x))))

Then I could either use:

  (trav b [self _!l] [a _!d] [self _!r])

or:

  (trav b 'go [go _!l] [a _!d] [go _!r])

A final alternative is to imitate 'rfn and 'afn: define 'rtrav which requires a symbol for the "go" action, and 'atrav which specifically uses 'self.

-----

4 points by almkglor 6116 days ago | link

Yet another alternative:

   (mac trav ((go v) s . body)
      `((rfn ,go (,v)
            ,@body)
        ,s))

   (trav (go node) b
      (go node!l)
      (a node!d)
      (go node!r))

The above is arguably lispier, and removes the need for [] everywhere.

-----

1 point by almkglor 6116 days ago | link

Bugged, of course ^^ Forgot the (when ...) test.

   (mac trav ((go v) s . body)
      `((rfn ,go (,v)
            (when ,v
              ,@body))
        ,s))

-----

2 points by mattjones 6117 days ago | link

What about calling the macro w/trav and the rfn trav:

   (def bst-elts (b)
    (accum a (w/trav b [trav _!l] [a _!d] [trav _!r])))

or some other such convention where the macro name predicts the name of the recursive function?

-----

3 points by almkglor 6117 days ago | link

Doesn't feel like the Right Thing; I keep getting lost in it.

-----