C99 implementation of new O(m log^(2/3) n) shortest path algorithm

https://github.com/danalec/DMMSY-SSSP

#HackerNews #C99 #O(m #log #n #shortest #path #algorithm #DMMSY-SSSP

Right, thanks.
Do you know off the top of your head
when Interlisp acquired specifically such markers for shared structure (circularity etc.)?
(Like Common Lisp's #n= and #n#, but I don't know its particular syntax.)

#Lisp

@amoroso @weekend_editor @screwlisp @BobKerns

Reader macros were indeed older. They were in Lisp Machine Lisp, and I think in Maclisp before that.

But CLtL is the first place I remember seeing #n= and #n# to build weird list structures *at read time*.

I dunno if it's *the* first; that's extraordinarily hard to demonstrate. If you were to make that claim, then inevitably somebody would come up with a macro facility in BCPL that did it in 1967, or some such thing of equal improbability.

It's the first time *I* saw it, though. It was also the first time I saw anybody use the #n= construct in the reader.

It would have been around 1985 - 1987, based on what else was happening at the time.

Bob, if you see this, do you remember?

I'm not aware of anything that specifically rules it out of the language, other than the unstated pragmatic advice not to feed circular lists to the compiler.

If you think about it somewhat abstractly, it's *exactly* how they model recursion in denotational semantics, using the Y combinator.

I gave up groping for 40 year old
memories and thought of something like:

#1=(lambda(n)
(if (= n 0)
1
(* n (#1# (1- n)))))

That's probably wrong in detail, but the general idea is there.

@BobKerns once circulated a joke at Symbolics along these lines.

It was factorial, but using ' #n=' to create a circular list instead of recursing.

I recall the comment text was something like "Caution: Do Not Compile".