brzozowski

What I would like is a CPU with a highly parallel array of "worker cores" all addressing the same memory...

I too am very interested in this model. The Linux kernel supports up to 4,096 cores [1] on a single machine. In practice, you can rent a c7a.metal-48xl [2] instance on AWS EC2 with 192 vCPU cores. As for programming models, I personally find the Java Streams API [3] extremely versatile for many programming workloads. It effectively gives a linear speedup on serial streams for free (with some caveats). If you need something more sophisticated, you can look into OpenMP [4], an API for shared-memory parallelization.

I agree it is time for some new ideas in this space.

[1] https://www.phoronix.com/news/Perf-Support-2048-To-4096-Core...

[2] https://aws.amazon.com/ec2/instance-types/c7a/

[3] https://docs.oracle.com/en/java/javase/24/docs/api/java.base...

[4] https://docs.alliancecan.ca/wiki/OpenMP

Wouldn't every Turing complete cellular automaton have this property? What would be an example of a nontrivial (i.e., sufficiently expressive) CA that is "predictable"?

I also experienced an irregular heartbeat for several months after receiving the Moderna vaccine (June, 2021) up to this month (December, 2021). It seems to be getting better, but is accompanied by a mild pain, tightness in the chest and shallow breath. This is despite regular diet, exercise and otherwise normal health. I am 31 years old.

There are many bizarre visualizations that are solely cosmetic and serve no purpose other than to attract the eyes. I've noticed the same pattern with many other videos churned out by popular science channels. The visual editing is delirious and the narration is devoid of much intellectual substance. Hard to pinpoint exactly what's wrong with it, it's just extremely bland and borderline uncanny valley.

The author frames this as a contest between two architectures: either spend a lot of effort building custom developer tools, or repurpose the compiler as a server for multiple clients. Both approaches have their tradeoffs: the first, as the author mentions, violates DRY [1]. The second violates the Unix philosophy [2].

However, there is a third way. Both developer tools and compilers can be seen as special cases of a much simpler and more general pattern known as a graph database [3, 4, 5].

[1] https://en.wikipedia.org/wiki/Don%27t_repeat_yourself

[2] https://en.wikipedia.org/wiki/Unix_philosophy

[3] https://www.youtube.com/watch?v=WxyyJyB_Ssc

[4] https://petevilter.me/post/datalog-typechecking/

[5] https://arxiv.org/pdf/2004.03082.pdf

And when your surpassing creations find the answers you asked for, you can’t understand their analysis and you can’t verify their answers. You have to take their word on faith—Or you use information theory to flatten it for you, to squash the tesseract into two dimensions and the Klein bottle into three, to simplify reality and pray to whatever Gods survived the millennium that your honorable twisting of the truth hasn’t ruptured any of its load-bearing pylons. You hire people like me; the crossbred progeny of profilers and proof assistants and information theorists…

In formal settings you’d call me Synthesist.

—Peter Watts, Blindsight (2006)

[1] https://www.rifters.com/real/Blindsight.htm

Space filling curves have some super important applications for indexing and information retrieval. I recently stumbled on an fascinating library called Uzaygezen for multidimensional Hilbert space filling curves. Extremely high quality code and documentation:

https://github.com/aioaneid/uzaygezen

https://opensource.googleblog.com/2008/08/uzaygezen-multi-di...

Anyone with a software engineering background interested probabilistic model checking and learning automata should check out the work from ICSAS led by Prof. Lijun Zhang, Yong Li and Andrea Turrini. In particular their work on ePMC and ROLL are really excellent:

https://github.com/ISCAS-PMC/ePMC

https://github.com/ISCAS-PMC/roll-library

Storm is another probabilistic model checker from RWTH Aachen, developed Christian Hensel, Sebastian Junges, Tim Quatmann, Matthias Volk et al. at , which has a nice Python API:

https://www.stormchecker.org

The fact that there is no actual methodology published for how this index of popularity is actually generated makes me highly sceptical of the whole idea.

As soon as a metric becomes a target...

I recently learned there are a few groups at ETZH working on traffic simulation and fleet planning in transportation networks. Are you affiliated with the Autonomous Mobility on Demand / IDSC folks?

https://www.amodeus.science/

https://idsc.ethz.ch/education/lectures/duckietown.html

The paper has some nice illustrations in case anyone is interested in reading about it in more detail: https://sci-hub.tw/https://doi.org/10.1093/zoolinnean/zlaa06...

Computers will never fully automate mathematical reasoning, because mathematical reasoning cannot be fully automated.

One possible reason why mathematics cannot be automated is because some important piece of contemporary mathematics is fundamentally unsound, e.g. ∞, LEM, AOC. Mathematicians are very clever at building and manipulating formal systems, but are prone to mistakes and must accept on faith some foundations to make any progress. If you spent your entire career building a castle and someone like Gödel or Brouwer came along and claimed the whole thing is built on sand, naturally you (and all your venerable castle-building colleagues) would be unwilling to simply accept this development and move on.

I suspect what many people call mathematics today lost its course somewhere after Cantor, who was a supremely clever human being, but either mentally unstable or driven to madness trying to operationalize infinite sets. If our universe were infinite, maybe his ideas would be valid, but even then we could never build machines to verify those claims. While it has produced an abundance of useful ideas, it also generates a number of paradoxes (e.g. Zeno, Banach-Tarski), which are simply incompatible with the universe in which we live.

As a grad student who has been using Kotlin in research for the last few years, it can also be a great language for data science. Kotlin is one of the few statically typed languages with scripting and Jupyter notebook support, and offers some great features for parallel and asynchronous data processing. Once you set up a project and import the right dependencies, the workflow really clicks. It works smoothly with the JVM and JS ecosystems, which have a bunch of fantastic libraries for data processing and visualization. Happy to answer any questions about using Kotlin for DS/ML if anyone’s curious.

Reminds me of the watching-eye effect:

https://en.wikipedia.org/wiki/Watching-eye_effect

Interesting, thanks for the pointer Adam!

I have updated the WL(1) implementation to iterate until fixpoint termination, and mentioned the failure case. Thank you for reading carefully!

Have you thought of applying this to web-stacks?

Yes, it seems like a good place to start. I was thinking of writing a PoC interpreter for a subset of the JS syntax. Thanks for the suggestion!

Definitely the product of an over-excited grad student who’s fallen in love with these ideas for the first time. Thanks for reading, I hope you were able to get something from it (if not what to avoid)!

Yes, I was originally inspired by GraalVM’s work! They were one of the first to realize a practical implementation of Futamura’s ideas. I briefly discuss it towards the end:

http://breandan.net/2020/06/30/graph-computation/#programs-a...

Sure, I made plenty of bad predictions too! I have written about some of the harmful effects of trust and bias in automation, feel free to check it out:

https://breandan.net/2017/02/02/trust-in-automation/

Very cool, thank you! Link was broken, here is the full reference: https://www.cs.utexas.edu/~pingali/CS395T/2009fa/papers/ferr...

It has been rebranded a number of times, from automatic differentiation to algorithmic differentiation to differentiable programming. Takeo Imai wrote a blog post about the origins and history of the term and its modern usage:

https://bonotake.github.io/deep%20learning%20and%20cs/2019/0...

It seems like the overall goal is to provide some intuition for how automatic differentiation & program synthesis might be implemented efficiently using matrices.

Right! I wish I had emphasized that theme a little more. This is basically a long digression on how to think about automatic differentiation in the context of program synthesis, two topics which I enjoy thinking about.

However, I'm a little confused on how the section on Weifeiler-Lehman & checking for isomorphic graphs ties in to the rest of the article?

Great question! I introduce isomorphism testing for two reasons:

1. It is an example of a general purpose algorithm which, although we do not show it, can be implemented completely using matrix multiplication.

2. It is an example of how message passing on graphs works. This helps us build an intuition for how to implement more complex graph algorithms.

Hamilton (2020), does a much better job at introducing the WL algorithm and why it matters in the context of graph representation learning:

https://cs.mcgill.ca/~wlh/comp766/notes.html

Feel free to drop me an email if I can help clear anything up. Thanks for reading carefully and leaving a comment!

I hope you mean by parallel processing, on a single machine.

Not necessarily! Parallelism in the more general sense. We can parallelize matrix multiplication and there is good research on distributing graph algorithms across multiple machines. Spielman discusses this in his recent talk on Algebraic Graph Theory:

https://youtu.be/CDMQR422LGM?t=1755

I guess by alphabets you mean dictionaries.

Just unordered collections of symbols. Depending on the dictionary or alphabet implementation, it might have an ordering.

I don't agree that the web is a directed graph.

This was intentionally vague, but depending on which types of links you consider it may or may not have directionality. Hyperlinks, for example, are directional.

I wouldn't include formula or code parsing because in such cases they are just a means to an end.

Part of my goal is to show how simple implementing these algorithms can be. Agree it doesn't flow very well, maybe it should be in the appendix.

You might want to talk here to someone at Oracle.

Agreed, I think the work they're doing in probabilistic programming languages is super interesting. I recently gave a short presentation about loopy belief propagation (another interesting graph algorithm for PGMs).

https://github.com/breandan/kaliningraph/blob/master/latex/c...

That all being said, I'd like to reiterate on talking to the semantic web community...Cambridge Semantics are quite good

Will definitely look into them, thank you! I am fascinated by the whole topic of knowledge bases and semantic parsing, and appreciate the suggestions you provided.

Thanks for your comments! I enjoyed reading about STKs, which I had not heard about before. I know lots of people are interested in applying kernel methods to graphs, and it seems like a important area of research. As your post discusses, one of the problems with defining an algebraically valid graph kernel arises with Mercer's symmetric condition. As far as I know, defining a valid convolutional kernel on graphs is still an active area of research. Hamilton (2020) discusses this problem in the notes from his recent GRL seminar here:

https://cs.mcgill.ca/~wlh/comp766/files/chapter6_draft_mar29...

I am convinced that using graphs to link semantics with structure is under-explored.

I hope you continue to explore this direction! Designing better semantic parsing algorithms seems really important for knowledge retrieval. I would love to learn more about natural language parsing in general (e.g. grounding, PCFGs, HMMs), this is one area I feel we could learn a lot from in programming languages research.

Perhaps the IPU units from Graphcore are a move towards this? I could use clarification on your points regarding next steps in low-level languages and hardware.

Not very familiar with the Graphcore architecture, although their engineers have tried to explain it to me several times. I think this is going to be a co-design problem, but we can start to realize some progress by compiling to pure BLAS primitives. GPGPU-based approaches seem like a good start.

Hi Dan, thanks for taking the time to read this and leave your feedback. I'll try to address your remarks one-by-one.

I found the frequent self-quotes odd and the self-congratulatory introduction more odd.

Thank you for the candid feedback! I have reflected a bit about this and where it comes from. It detracts from the main theme, which I regret, but also gives the reader context. Like many, I have flaws and ego is one of them. I try to be upfront about this, so the reader can bail early.

It starts with a paragraph which seems to be for someone who has never heard of graphs.

This is a good point. I did not think very carefully about the audience. It is mostly, as you mention, a brain dump. At the same time, I am trying to explain some ideas which may be familiar to you, but others are encountering for the first time. I agree, this could be clearer what parts are for what audience.

this function must be linear and the numbers in a matrix are in some sense unimportant because they are relative to some basis

Not attempting to be mathematically rigorous, but I think you raise an important point here, and I will try to clarify this point more carefully. Linearity can be a constraint in real vector spaces, but is less of a problem in Boolean algebra. The goal here is just to show how matrices can represent a function between vector spaces.

Then there’s a section about raising matrices to a power except when you look at it you realise it’s actually a product of different matrices.

Not sure I follow, can you be more specific? I will try to clear this up.

The “matrix multiplications” in the section on data flow graphs don’t make sense to me, even with the random extra rules given above.

Completely agree, this algorithm needs to be made more explicit, because it is a poorly written example. The full example can be found in Miller (1987).

https://www.cs.cmu.edu/~glmiller/Publications/MRK86b.pdf

I don’t want to be overly negative.

Not at all! Again, thanks so much your comments. I would be happy to discuss them further here or by email.

Thanks, this is helpful feedback. I was thinking about this, and where it comes from in my writing. I’m not going to erase these details, because it documents who I am, and my frame of mind. If you leave with a poor opinion of the writer because of it, that’s something we share in common. I think people should keep their egos in check, and I try my best to do so. But you cannot erase ego entirely, and to hide it would be disingenuous. Ego is part of who we are as human beings, and part of what gives us motivation. This blog is partly a research journal, and partly because I seek validation from Hacker News. I am no genius, I just listen to the right people and write about ideas that interest me. If it makes the reader uncomfortable, I can completely understand that. I’m not trying to hide anything, ego included.

Anyhow, I just wanted to say I appreciate your taking the time to write this comment!

Thanks for your feedback! I like the WL algorithm for its simplicity, but agree there are specific cases it does not handle well. It is meant to illustrate a simple message passing algorithm, and is not a particularly efficient implementation. Will clarify this point, thanks!

I would say that’s becoming increasingly plausible, but it’s not exactly what the authors show in this paper. In order to translate from Datalog queries, you would need to show how to encode arbitrary propositional formulae as a graph reachability problem. This appears to be possible following Reps et al. [1], but is still far away from becoming a push-button solution. Here, they are proposing a new architecture which is capable of inferring abstract relations between program states (e.g. variables), trained on a synthetic dataset of pairwise relations, and empirically showing its generalization performance on those specific tasks.

This is a promising early result, but does not show how to encode arbitrary static analyses at runtime. The authors have related work (Shrivastava et al. [2]) applying few-shot learning to source code, which (just speculating) might be amenable to a graph representation, by accepting as input (1) a graph program and (2) static analysis / reachability query, and returning the answer (a la NLP question-answering, but for code). It might also be possible to synthesize new static analyses from a dataset of labeled examples. Maybe you can reach out to the authors to discuss their broader goals for this work?

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61....

[2] https://arxiv.org/pdf/2003.11768v1.pdf

Yes, “program synthesis” or “program induction” are the broader topics, which span automata theory, type theory and (more recently) representation learning. Prior work has relied on classical algorithms like proof search, SMT solvers and learning automata. Recently there has been a lot of progress in applying statistical learning algorithms to program synthesis, as researchers began to realize it shares a lot in common with linear algebra and graph representation learning. I wrote a blog post about some of those connections in case you’re interested in learning more:

http://breandan.net/2020/06/30/graph-computation/