efferifick

> Among other things, this means you can "plug your own language" into the syntax library to get a "free" autodiff algorithm.

Hello, as a compiler engineer I am interested in this area. Can you expand a little bit more? How would I be able to plug in my own language for example?

> So for example, you could write a program, then write an x86-specific optimization for one function which you can then prove correct with respect to the more abstract program specification.

So, what you are saying is that catgrad alllows me to write a program and then also plug in a compiler pass? I.e., the application author can also be the compiler developer?

Thank you for sharing!

Damn, I am being nerd-sniped here :)

One thing is that you can think of static analysis as building facts about the program. You can for example start by assuming nothing and then adding facts about the program. And you need to iteratively propagate these facts from one line of code to the next. But you can also start by assuming the universe and removing facts from this universe.

Some classes of program analysis are safe to stop early. For example, if I have a static analysis that tries to find the target of virtual calls (also known as a devirtualization), you can stop early after a time out. Not finding the target just implies a missed optimization.

There are some other classes of program analysis that are not safe until the algorithm finishes. For example, if you have to prove that two variables do not alias each other, you cannot stop until you have all possible points-to sets and verify that for each of those two variables, their points-to sets do not overlap.

So, given the above restriction, the first class (early termination) is perhaps more desirable and throwing more compute time would yield a better approximation. For the second one, it wouldn't.

Another thing to keep in mind is that most of these data flow frameworks are not easily parallelized. The only paper I've read (but I haven't kept up with these avenue of research) that implemented a control flow analysis in the GPU is the following:

* Prabhu, Tarun, et al. "EigenCFA: Accelerating flow analysis with GPUs." ACM SIGPLAN Notices 46.1 (2011): 511-522.

I'm sure people are working on it. (I should mention that there are some program analyses written in Datalog and Datalog can be parallelized, but I think this is a processor based parallelization and not a GPU one).

The third thing is that when you say whether we are limited by algorithms or compute, I think it is important to note that it is impossible to find all possible facts *precisely* about a program without running it. There is some relation between static program analysis and the halting problem. We want to be able to guarantee termination of our static program analysis and some facts are just unobtainable without running. However, there is not just static program analyses, but also dynamic program analyses which can analyze a program as it is running. An example of a dynamic program analysis can be value profiling. Imagine that you have a conditional and for 99% of the time, the conditional is false. With a virtual machine, you can add some instrumentation to find out the probability distribution of this conditional and then generate code without this condition, optimize the code, and only if the condition is false then run a less optimized version of the code with an additional penalty. Some virtual machines already do this for types and values. Type profiling and value profiling.

One last thing, when you say a meaningful performance boost, it depends on your code. If your code can be folded away completely at compile time, then yes, we could just generate the solution at compile time and that's it. But if it doesn't or parts of it cannot be folded away / the facts cannot be used to optimize the code, then no matter how much you search, you cannot optimize it statically.

Compilers are awesome :)

As an addendum, it might be desirable in the future to have a repository of analyzed code. Compilers right now are re-analyzing code on every single compile and not sharing their results across the web. It is a fantasy of mine to have a repository that maps some code with equivalent representations and every time one does a local compile it explores a new area and adds it to the repository. Essentially, each time you compile the code, it explores new potential optimizations and all of them get stored online.

I am not sure why you mention LLM, the post mentions LLVM. Second, you can have different optimization options with different tradeoffs in compile-time and run-time. Third, even if the default and only options distributed with clang are too compile-time intensive, the good news is that this is open source and you could argue against it, or fork and maintain your own compile-time run-time tradeoff compiler along with other people who also want that behaviour. I don't see any benefit of arguing against research. Having new techniques to improve compilers is not a zero sum game.

This post and the Hydra paper reminds me a lot of Ruler and Enumo.

  * Nandi, Chandrakana, et al. "Rewrite rule inference using equality saturation." Proceedings of the ACM on Programming Languages 5.OOPSLA (2021): 1-28.
  * Pal, Anjali, et al. "Equality Saturation Theory Exploration à la Carte." Proceedings of the ACM on Programming Languages 7.OOPSLA2 (2023): 1034-1062.

I will need to read more about both of these techniques along with Synthesizing Abstract Transformers.

Thanks for sharing! Really exciting stuff!

The order goes from simpler to more complex data flow analysis frameworks. These frameworks allow you to encode dataflow problems and solve them.

  * Kam, John B., and Jeffrey D. Ullman. "Monotone data flow analysis frameworks." Acta informatica 7.3 (1977): 305-317.
  * Reps, Thomas, Susan Horwitz, and Mooly Sagiv. "Precise interprocedural dataflow analysis via graph reachability." Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 1995.
  * Sagiv, Mooly, Thomas Reps, and Susan Horwitz. "Precise interprocedural dataflow analysis with applications to constant propagation." TAPSOFT'95: Theory and Practice of Software Development: 6th International Joint Conference CAAP/FASE Aarhus, Denmark, May 22–26, 1995 Proceedings 20. Springer Berlin Heidelberg, 1995.
  * Reps, Thomas, et al. "Weighted pushdown systems and their application to interprocedural dataflow analysis." Science of Computer Programming 58.1-2 (2005): 206-263.
  * Späth, Johannes, Karim Ali, and Eric Bodden. "Context-, flow-, and field-sensitive data-flow analysis using synchronized pushdown systems." Proceedings of the ACM on Programming Languages 3.POPL (2019): 1-29.

Other areas that may be interesting to look at:

  * Points-to Analysis
  * Abstract Interpretation
  * On demand dataflow analyses

I've been a big fan of Emery's research. Coz is one tool that I am always wanting to use, but I haven't had the chance to do so.

Check his other research. Some of it is highly accessible via youtube videos. I recommend watching / reading:

  * Stabilizer
  * Mesh
  * Scalene

I recommend `egglog` which is Datalog + Equality Saturation. It has python bindings and has allowed me to optimize programs in a custom programming language.

https://egg-smol-python.readthedocs.io/en/latest/

I will be in the minority here, but:

Native integration with Datalog.

Many times, I find myself working on a program and I realize that what I need is a database. But having a database, even sqlite3 or Berkely DB, would be an overkill. If I could just express my data and the relationships between them, then I would be able to query what I need in an efficient way.

I think a lot of people in the comments are hung up on defining compiler as "taking a source language and producing a binary". I personally know Eddie and I agree with his points. (Even though his title is a bit provocative and contradicts one of the points in the article "A language is not inherently compiled or interpreted; whether a language is compiled or interpreted (or both!) is an implementation detail.")

I perhaps have not had a long professional life working with compilers (5+ years), but to me the definition of "compiles to binary" is too restrictive. The main things I care for in my work are:

1. To be able to perform some sort of static analysis on the program 2. To be able to transform the program representation

To other commenters: in Python, we have two program representations. The human readable string representation and the bytecode representation. The syntactical errors are a kind of static analysis. To me, the maps between the Python string representation and the bytecode representation and the classes of errors we can catch without running the program is far more interesting than pigeon-holing Python in the "compiled" or "interpreted" hole.

> Spanish Catalan architect Antoni Gaudí disliked drawings and prefered to explore some of his designs — such as the unfinished Church of Colònia Güell and the Sagrada Família — using scale models made of chains or weighted strings. It was long known that an optimal arch follows an inverted catenary curve, i.e., an upside-down hanging chain. Gaudí's upside-down physical models took him years to build but gave him more flexibility to explore organic designs, since every adjustment would immediately trigger the "physical recomputation" of optimal arches. He would turn the model upright by the way of a mirror placed underneath or by taking photographs.

http://dataphys.org/list/gaudis-hanging-chain-models/

I was suggesting a simpler solution: just merge the two civs into one. This would be equivalent to having only one general.

Shouldn't there be the possibility for civilizations to join forces?

Mmm... maybe I'm mistaken. Thanks for the opportunity to reflect a bit more about this. I was remembering this video [0] which talks about Graph Embeddings. In the video, the speaker talks specifically about node classification. Assuming the classes are target functions, this could potentially be used for speculative devirtualization.

Definitely not an expert, just excited to have more tools on which to work with graph data!

[0] Graph Embeddings - Neo4J. Talk by Alicia Frame. https://www.youtube.com/watch?v=oQPCxwmBiWo

I am really interested in GNN in the context of compilers.

* Predicting the color of a node in a graph, could be used for example speculative devirtualization.

* Predicting edges weight could give us a better estimate of hot basic blocks statically.

* Running performance experiments is as easy as running the benchmark and introducing some metric of performance which you can give back to the GNN to learn from.

Imagine also for debugging and IDEs. I haven't played with copilot, but I imagine that something like guessing the graph based on node labels and on some edges is feasible using GNN? This means that the IDE could try to match the name of your variables, the control flow, and the name of the function to other known functions and could potentially point out differences. Potentially giving us a way to fix logic errors, or better algos. E.g., "Mmm... it looks like you are implementing your own bubble sort from scratch. Would you like to click here and use <insert better sort>."

I am not an expert on GNN, but if anyone has resources for someone to learn more about the state of the art of GNNs (a link to a literature review or something similar) do let me know.

This is awesome! Thanks for sharing!

Yes, but the problem is learning through the graph data. I.e., it is not a well-structured problem like an image which will always have a certain size in pixels. Coming from a compiler background I am genuinely excited about the research on learning how to label nodes and edges in graphs, but I know little about the challenges in the ML side to bring this kind of technology into reality.

Something very similar: a "decompiler" that decompiles minified javascript and guesses variables and functions: http://www.jsnice.org/

This reminds me a little of the Voight-Kampff test.

Relevant comic: https://believermag.com/technofeelia-vol4/

Take a look at coz the causal profiler: https://github.com/plasma-umass/coz

From what I know this is the closest project that fits your description.

I wonder how well one can modify the framework laptop to use the 13 inch e-ink monitor. Even if a small hdmi cable needs to run outside the case, as long as the lid can close (no need auto sleep) I'd be happy. I don't know anything about 3D printing, but it will likely be necessary (perhaps not sufficient though).

Do you know if there's any disadvantage on using the Futamura projections to generate a compiler? Harder to maintain? Some optimizations are harder to express this way?

I have some experience writing compiler optimization passes and working on JITs, but I have not worked on an interpreter that uses Futamura's projections to generate a compiler.

The abstract looks very interesting. I will certainly take a look and read during the weekend. Thanks for sharing.

My quick interpretation is that staged abstract interpreters are an optimization for faster analysis similar (or equivalent?) to abstract compilation, however with the added benefit of not having to program the abstract compiler thanks to the Futamura projections, right?

Thanks!

Not sure how much this fits:

* fraidycat: RSS reader where the user can choose refresh rate for different type of feeds. Also different categories (i.e., friends vs brands).

* futureland.tv: a social media website focused on journals to document progress on users' projects. (no-ads)

Came here to point videogrep out. It is a great tool!

I don't remember if this is out of the box for videogrep, but it is possible to generate "fine-grained" subtitle information using speech to text and some massaging. In other words, subtitles that match a specific word.

I worked on something similar to this using videogrep and "fine-grained" subtitle information using Seinfeld clips. My short experiment took as input a string and looked for the longest matching subtitle and created a clip out of longest matching subtitles of characters saying the contents of the input string. I couldn't figure out how to get diarization to work reliably back then, if anyone knows, please let me know!

Here's another model to generate nonsensical words.: https://www.soybomb.com/tricks/words/

Checkout differential datalog. Looks super interesting: https://github.com/vmware/differential-datalog

But I've only played with souffle, which I am not sure where it lands in this taxonomy. I think it lands on the high temporal locality but compared to differential datalog, the biggest difference in my opinion is the souffle solves problems as a batch (i.e., all the inputs are known at command issue time) while differential datalog may receive inputs at runtime.

There's also incA: which I think competes with differential datalog. https://github.com/szabta89/IncA

So, how I see Datalog (which is a subset of prolog) falling into this taxonomy:

Datalog (batch-processing) would fall under structured/high-temporal locality/internally consistent.

Datalog (incremental) would fall on structured/low-temporal locality/internally consistent.

Looking a little closer on what is defined as "consistent" here, incremental Datalog might not be "consistent" because it might return an "incorrect" or "unavailable" computation for a past input if you "update" or modify the input. But if one restricts the subset of Differential Datalog to follow functional semantics, then that would be consistent. Not really super knowledgable about this projects beyond playing with them and reading some papers on Datalog/Souffle.

I wonder how likely are code invariants found in the training set preserved in GPT-2/3. In other words, if I train GPT-2 with C source produce by Csmith (a program generator which I believe produces C programs without undefined behaviour) would programs produced by GPT-2/3 also do not exhibit undefined behaviour?

I understand that GPT-2/3 is just a very smart parrot that has no semantic knowledge of what it is outputting. Like I guess let's take a very dumb markov chain that was "trained" on the following input:

a.c ``` int array[6]; array[5] = 1; ```

b.c

``` int array[4]; array[3] = 2; ```

I guess a markov chain could theoretically produce the following code:

out.c

``` int array[4]; array[5] = 1; ```

which is undefined behaviour. But it is produced from two programs where no undefined behaviour is present. A better question would be, how can we guarantee that certain program invariants (like lack of undefined behaviour) can be preserved in the produced code? Or if there are no guarantees, can we calculate a probability? (Sorry, not an expert on machine learning, just excited about a potentially new way to fuzz programs. Technically, one could just instrument C programs with sanitizers and produce backwards static slices from the C sanitizer instrumentation to the beginning of the program and you get a sample of a program without undefined behaviour... so there is already the potential for some training set to be expanded beyond what Csmith can provide.)

EDIT: I don't know how to format here...

Well... this is how I just found out about them. I find coil very interesting! Strongly thinking about becoming a member, but I would like to find out if the websites I follow use the web monetization tag first.