Arc Forum | lib/graph.arc, table misfeatures

Arc Forum

lib/graph.arc, table misfeatures

1 point by rntz 5901 days ago | 2 comments

I've pushed a tiny graph library to anarki: http://github.com/nex3/arc/tree/master/lib/graph.arc. It uses adjacency-list representation, and vertices can be any datatype that can go into a table, though they shouldn't be mutated while any graphs involving them are in use. The library is currently very small, implementing only transposition, topological sorting, and Tarjan's algorithm for finding SCCs. I encourage anyone to add algorithms to it. It also uses lib/util.arc, a file I added to anarki a while ago, which I also encourage people to use and improve.

In making it, however, I encountered something I formerly found merely annoying, but am now confident enough to label a misfeature: Arc does not distinguish between a key mapping to nil in a table and the same key being absent entirely. pg's justification for this is that "in most cases", it isn't a problem; be that as it may, in this case it is a major pain in the ass, as for a vertex in a graph to have no outgoing edges is emphatically not the same as for the vertex to not exist at all. Instead of using lists, I use tconc-cells, from almkglor's lib/tconc.arc; although their primary purpose is to allow fast appending to and catenation of lists, they serve well here since an empty tconc-cell is non-nil. (The performance boost doesn't hurt either, though it doesn't change the asymptotic complexity.)

As an example of what the library can do, suppose we have the following dependency relations among files, such as one might find in a Makefile:

    bar.h: bar.h.m4
    foo.o: foo.c foo.h bar.h
    bar.o: bar.c bar.h
    foo: foo.o bar.o

To calculate the order in which to check the files for changes and possibly rebuild them, we build a graph representing the dependencies, add any files mentioned on the RHS of a make rule but not on the LHS, then transpose and topologically sort the graph:

    (= deps (mlist-graph '((bar.h bar.h.m4) (foo.o foo.c foo.h bar.h) (bar.o bar.c bar.h) (foo foo.o bar.o))))
    (add-implied-leaves deps)
    (top-sort:transpose deps)
    
    => (foo.c foo.h bar.h.m4 bar.c bar.h foo.o bar.o foo)

1 point by eds 5900 days ago | link

> Arc does not distinguish between a key mapping to nil in a table and the same key being absent entirely.

  (def get (tab key (o default))
    ($ (hash-table-get ',tab ',key ',default)))
  
  (= tab (table))
  (= absent-entirely (uniq))
  (get tab 'key absent-entirely)
  
  (defcall table (tab key (o default))
    (get tab key default))
  
  (tab 'key absent-entirely)

;-)

-----

1 point by rntz 5900 days ago | link

It's true, I can override this. But this would change the language for any consumer of my library, as well; and however bad it may be to have absent keys map to nil, it's even worse to face the possibility of breaking the language for someone else. Sure, it's an optional parameter here... but what happens if someone else has their own idea about adding an extra parameter and what it should do? Your idea is probably the right design (though 'len and 'keys and the setter for tables would have to be changed as well to fit it), but it's not the way arc currently works. Hopefully pg will pick it up and run with it, though.

-----