(This paper gets rediscovered by HN every so often, there are interesting discussions on past threads) While Appel is definitely a smart guy (he's been working

(This paper gets rediscovered by HN every so often, there are interesting discussions on past threads) While Appel is definitely a smart guy (he's been working in the field for a very long time), this is kind of the limit of taking something that was done to be eminently practical reasons and trying to turn it into a theoretical masterpiece. In the time period in which he did it, he did it because SSA was super-popular and he was trying to repopularize functional programming, AFAICT. Note also: The functional guys never proved anything about any of the time bounds/etc below - because that was never their goal. SSA was created and thought about for a simple reason: To make dataflow problems faster in compilers. So saying they are doing exactly the same thing is also a bit silly in the sense that one of them is trying to make compilers faster, and don't actually care how they do it - if they could wave a wand, they would have. The other group had very very different goals. They wouldn't have particularly cared if you could make the compilers faster, they were trying to make programming better. (This is a rough generalization, of course). Zadeck[1] certainly understood SSA was functional, they just didn't really care, it wasn't particularly relevant to interests :) The analogy also breaks down really heavily once you start to extend SSA. This is why SSA and other things went in the direction they did afterwards - extensions towards faster/better dataflow. It's worth understanding a little history (which i am going to do off the top of my head and probably get a few details wrong - sorry. I'm also going to generalize a little bit, because it's hard to summarize an entire field's development in a few paragraphs) In the 70's, we had a problem. We had discovered and built generalized frameworks for analysis of programs[2]: General bitvector dataflow (which was what was done in the 70's and early eighties) has proven timebounds, and they are not good. It was being worked on by some of the smartest people i've ever had the honor of meeting (Aho, Ullman, Allen, Tarjan, Kennedy, etc). For general dataflow problems, those timebounds are N^3[3]. You can prove that, the way it was done, if you could solve it faster, you get yourself a faster algorithm for transitive closure/boolean matrix multiplication. That's the point at which practical people tend to go "well shit we're screwed" Then some of these folks proved that a class of dataflow problems (which included a lot people wanted to do) known as RAPID problems could be solved in linear number of steps. This brought overall time to N^2 for those problems. These are the analysis/optimization you generally saw in compilers for many years until SSA took over. N^2 was somewhat fine because of the state of the kinds of programs being compiled and the limitations people were willing to accept in things like "number of variables allowed per function" at the time. At this point, the world split, with various people going down the path of trying to find more general frameworks that expand that class of problems, others sticking with rapid problems, and a small number going off and trying ways that looked different from the way current dataflow problems were done. Zadeck (who created that part of SSA) is arguably in the latter category. His thesis was on partitioned variable approaches, which are basically "instead of one large dataflow graph, make one per variable that can be computed faster"[4]. This is the essence of SSA, and interestingly is not constrained by the bitvector time bound i gave you above (he told me he basically had to argue about this to everyone he ever met because they wouldn't believe it). Which brings us back around to why SSA exists: To take classes of problems that were constrained by the proven time bounds of bitvector dataflow, making them N^2 overall (or worse), unconstrain them by enabling sparse formulations that could be done in linear time. That's it. There were other attempts outside of SSA, that did not involve actual renaming forms, SSA just caught on because it was simple and handled the stuff people wanted to do at the time (IMHO). SSA can be generalized in a way that does this for other classes of problems too: https://homepages.dcc.ufmg.br/~fernando/classes/dcc888/readingMat/SparseAbstractInterpretation.pdf https://homepages.dcc.ufmg.br/~fernando/classes/dcc888/readi... (There are also sparse evaluation graphs, but they are slower and don't generalize as well, as the paper goes into). In essence: SSA can be shown to be part of a general class of linear time transforms to program representations that make other dataflow analysis/optimization linear time. In the end, it's relationship to functional programming is coincidental at best, and in practice, somewhat more tenuous than described here. [1] Full disclosure: He was my officemate at IBM research for a few years. [2] If you've never read up on Frances Allen, she's amazing and basically created the field of automatic program optimization. As she would tell you, it builds on a lot of pieces of work of others, but ... The papers she wrote are completely approachable and still relevant today. [3] It is usually referred to by the number of bitvevtor operations in earlier literature, and those are assumed to be constant time because they are for small bitmaps. So it's usually listed as N^2. [4] He also hated bitvectors because he is dyslexic, and trying to debug strings of 1s and 0s where the position is important was kind of a nightmare.