Frances Allen wrote "A Catalogue of Optimizing Transformations" in 1971. 50 years(!!!) later, they are still the backbone of optimizing compilers. I think the only major thing missing is autovectorization.
I think you should read it if you work on compilers, even now. But the reason is a bit different.
It was the survey of the state of the art at the time, but obviously it is not the state of the art now. Then why should you read it? Because it is written in two layers.
The first layer goes, we tried many optimization ideas, but only these were effective in practice: inlining, register allocation, etc. Others were not. Surprisingly, this layer is still mostly true today! This is both happy and sad depending on your view. Personally I think it testifies that compiler is a mature field, and it matured by 1970. (And that Frances Allen did lion's share of work maturing it.)
The second layer is, so here is how you should do inlining, register allocation, etc. While this layer is also full of gems, it is necessarily badly outdated. The paper predates graph coloring register allocation, for example. On the other hand, ironically, the state of the art 1970s algorithms are often a good choice today when you want an algorithm that is fast and low memory. (Ironic, because they were slow and high memory at the time!) This doesn't apply when there is an important new concern, for example cache locality, but happily it mostly doesn't affect compiler.
I think there should be a project to write the-state-of-the-art-in-1970s compiler. It would be a great simple and minimal alternative to GCC and LLVM, and it would also work great as a JIT code generator. We probably should name it Fran.
> On the other hand, ironically, the state of the art 1970s algorithms are often a good choice today when you want an algorithm that is fast and low memory.
Simple things can run at higher speeds than complex things. Simplicity should be an architectural element, not a quality, but a feature.
Your idea for the Fran compiler is excellent. Throw in METAII from Dewey Schorre and it can be language agnostic.
Maybe I should call the backend for Objective-S Fran :-)
> graph coloring register allocation
I knew some people working on linear optimization, at the time one of the most performance-intensive applications around (with real money/competitiveness in many industries riding on it). The compiler that produced the best code, by quite a bit, was the IBM FORTRAN compiler (3090 was the preferred target at the time), which also didn't do graph coloring. It just allocated the registers by loops from innermost to outermost.
¯\_(ツ)_/¯\
For a simple compiler, we should also look at Wirth's works, and Wirth's rule: an optimization has to pay for itself, that is, the compiler compiling itself with the optimization both in the executable and in the source code has to be faster than without it in both places.
> For a simple compiler, we should also look at Wirth's works, and Wirth's rule: an optimization has to pay for itself, that is, the compiler compiling itself with the optimization both in the executable and in the source code has to be faster than without it in both places.
That will result in a compiler best at optimizing programs that behave like compilers. Which may be fine for simple compilers, but it's worth keeping in mind that will not be a good compiler for domains where the programs don't behave like compilers (such as scientific computing, or even ML these days) that also want high performance.
I agree with most of your comment but I don't agree that compilers was a mature field by 1970. That was before SSA, graph coloring register allocation, and even linear scan, all three of which were pretty revolutionary.
I saw her 2007 Turing Award speech. I have tremendous respect for Fran and like your idea to name a codegen after her :-)
The Single Static Assignment form was only created in 1988, which is apparently so late that compilers are still discovering it (and the optimizations it enables) as some novelty today.
(Never even mind the Single Static Information form.)
I wonder if part of the reason SSA is not implemented from the start by many compilers, is precisely because it came too late to be included in seminal works like A Catalogue of Optimizing Transformations; so people that rely on those works as a canon of "classes of optimization techniques that work" won't even be aware of it.
-----
More snarky: the earliest dataflow analysis paper I can find is from 1972. :)
I think SSA is not implemented from the start by many compilers is because many compilers are 30+ years old.
More seriously, my recollection (having been about 20 years since I last took a compilers course) is that it took a while for even researchers to be convinced of the advantages of SSA, as the transformation causes a quadratic blowup in code size for the worst case (but it turns out to be less in real-world cases).
Also Sussman & Steele proposed CPS in 1975 which is closely related to SSA.
A 30-year-old compiler would still have come out in 1990, well after SSA-based optimizations were discovered. But maybe I'm expecting too much in thinking that the author of a flagship optimizing compiler should be up-to-date on CS research in compiler optimization, before deciding the architecture of their compiler.
(Also, plenty of the compilers and/or JITs that I'm talking about are far newer. The first attempt to get a JVM to use SSA optimization during JIT — within SafeTSA — only occurred in 2000. Such an approach was copied by pretty much every JVM implementation by 2005, suggesting that a legacy of incompatible architecture was never the problem, but rather that JVM implementors just didn't think it was a worthwhile technique until they saw it demonstrated for their particular workloads.)
CPS is closely theoretically related to SSA (it carries equivalent information across lexical boundaries) but CPS isn't a basis for optimization transforms in the same way that SSA is. You can't hoist loop invariants using CPS... as far as I know, at least.
> But maybe I'm expecting too much in thinking that the author of a flagship optimizing compiler should be up-to-date on CS research in compiler optimization, before deciding the architecture of their compiler.
In 1990 I don't think SSA was broadly considered to be the basis of a good optimizing compiler the way it is today. So the "author of a flagship optimizing compiler" would be gambling on an unknown that looked good in a couple new papers. The Cytron paper on how to efficiently compute it came out in 1991. So SSA was still a WIP.
It wasn't really until the late 1990s IMO, that SSA became widespread and into the 2000s when it became the standard.
Someone else already replied to your first paragraph, so I'll reply to your second:
The safe TSA papers from 2000-2001 were the papers that showed that SSA was practical in a JIT environment. The fact that this approach was adopted less than 5 years after those papers come out suggest that compiler authors are in fact reading research papers.
Rearchitecting a production JIT to use a different IR for theoretical gains when nobody's demonstrated those gains on a toy JIT is high risk and demonstrating those gains on a toy JIT is research, not development.
I think a lot of now big, "professional" projects started as people's non serious hobby projects.
If you just want to write a compiler for fun, I can understand not reading up on state of the art theory beforehand. And then it's accidentally actually useful to other people and it's too far into development to change the fundamental architecture.
Agree. I worked on MIMD systems in the 1980s that seemed cutting edge at the time. Then in 2001 I toured the Concrete, ND phased array radar facility where I saw a 16-cpu machine built by Western Electric in 1969 that had essentially the same architecture.
I definitely do not have the chops for this, but I would love to see some sort of visualization that traces major, seemingly-modern computing ideas to their roots.
I worked at IBM research from 1997 until 2007, after finishing my PhD in compilers and programming languages.
About two weeks after I started working there, she showed up in my office, and introduced herself. She'd heard about a new PL person joining, and she'd gone and gotten my dissertation and read it, so that she could come talk to me about it. Not that my dissertation was anything special: that's just the way that Fran was.
She was an amazing person. Brilliant, and kind, and generous. The world needs more people like her.
Fran and I were on the same floor at IBM's Watson lab. I was in an AI project doing applied math, e.g., some optimization, and mathematical statistics (for the AI work we were doing, system monitoring, i.e., anomaly detection, better than our AI work!). She was regarded as a major expert in compiling and numerical codes for scientific computing.
I heard that she was working on a software product that among many other things would do fast matrix multiplication using some parallelism.
So, just for the heck of it, I wrote and ran a little routine in PL/I that used PL/I's feature of multi-tasking to get some parallelism and showed my code to her. She was a little surprised I'd written the code, had a smile, and explained why her work closer to some hardware features (I don't recall the details) would be faster!
I wasn't surprised or disappointed that my little PL/I tasking code would be slower than what she was doing, but at least I got her to explain the hardware she was using and how she was exploiting it!
As I recall, she was married to Jack Schwartz at Courant Institute of NYU and as in
Nelson Dunford and
Jacob T. Schwartz,
Linear Operators.
Hey, I just wanted to thank you for your reply covering the two semesters of stochastics in a condensed reply nearly 11 months ago in a different thread. I got too distracted reading up on it I forgot to reply. I cant tell you how much that helped with putting it all together conceptually. Given there is no way to reply to it now or dm you I figured this was the next best thing. Also anyway to get in contact with you with any future questions outside of here? especially since you mentioned you were previously working on an AI project. Any thoughts on High-Dimensional Statistics: A Non-Asymptotic Viewpoint by A. Martin Wainwright? It's currently what I'm trudging along through. You wouldn't happen to have a graycatmathhelp@email would you? thanks again
I’m sure you are just trying to share a memory of interacting with an illustrious colleague here - and my sympathies go to you as it’s always a shock to learn of the passing of someone you worked with.
But I think you maybe need to work on how you present this anecdote - as it is, it reads like you tried to mansplain her own research to a Turing Award winner. I hope you approached with more humility than this telling suggests?
Also, you should be aware that contextualizing professional women in terms of who their husband is or what his credentials are has long been used to underplay women’s individual achievements. Again, I don’t think that’s your intent, but you could consider whether, in the case of talking about Jacob Schwartz, you would have been moved to drop in the detail of who he was married to?
graycat's comment contains several details that go against your interpretation. For example the fact that Fran "had a smile" and patiently explained to him why his "little PL/I routine" would be slower than her state-of-the-art optimization work is clearly intended to depict the narrator as naive, and Fran as the expert. The mention of PL/I means that this anecdote likely took place fifty years ago, decades before she Turing Award winner. And the story makes it perfectly clear who ended up being the explainer and who the explainee. Indeed, that seems to be its main point.
As for the marriage bit, the strongest plausible interpretation is simply that it's interesting. Anyone familiar with computer science history would be interested to find out that the two of them had been married, and certainly that goes both ways: an anecdote about Schwartz would be enhanced by mentioning his marriage to a famous compiler optimization researcher. Indeed, it's not hard to find web pages about Schwartz that do this.
I don't think your points are entirely ungrounded, but they weren't the most plausible or good-faith reading of the comment. The cost of introducing an ideological scolding into a discussion like this is non-zero, so there needs to be a bar to clear. That's one reason why we have that guideline, which has proven to work well in situations like this: it basically leads to scolding for egregious cases, forgiveness for borderline cases, and open-mindedness in unclear ones.
>I hope you approached with more humility than this telling suggests?
Why the question mark at the end? Are you expecting the poster to reply for your own benefit or is it that you'd enjoy seeing him/her apologise publicly for sharing a personal (and presumably happy, at least to them) memory of a former work colleague who has just died. A memory that you have just tortuously construed into a supposed sexist encouter with literally zero insight, context or knowledge ?
Perhaps you might wish to consider your own humility.
> Again, I don’t think that’s your intent, but you could consider whether, in the case of talking about Jacob Schwartz, you would have been moved to drop in the detail of who he was married to?
That is actually very common in my experience when people talk to me about some guy and they think I might have heard of his wife.
At least as of when I was at IBM several years ago, PL/I and derived languages are still in widespread use in the IBM ecosystem for both high-level and low-level coding.
Not who you're responding to, but: My assumption was that the user is the greycat, which is the well-known alias of the programmer Greg Wooledge.
Now that you call it out, I realize that it's probably a mistaken assumption, because Greg spells it "greycat" not "graycat". But it wasn't an unreasonable assumption for HN.
Do I really believe that people should take care about the way they tell personal anecdotes about professional interactions with women, if they do not want to be seen as perpetuating sexist tropes? Yes, I do.
If the OP was trying to share a moment when they enjoyed learning from a great mind, the way they told that story was not a good way to express that. I wanted to give them the feedback that they might want to reframe the story because, telling it the way they did they run the risk of coming across as having behaved poorly. I feel I approached that with reasonable tact and in a spirit of good faith.
I appreciate dang’s commentary back to me about exercising the principle of charity. But I don’t accept that I was nasty. And I don’t appreciate your presumption of bad faith on my part.
Imagine you were at Frances Allen's funeral, and you walked up to graycat, after he told this anecdote about his esteemed friend and colleague, and said these words to him.
Imagine the frozen look of disgust on everyone's face. Imagine the flush of shame coming to your cheeks.
That's what you did. You should apologize for that.
The irony is that your and jameshart's motivations are likely similar. You're both reacting to a perceived slight and standing up for someone who you believe deserved to be treated better. That's a positive motivation, but we need to learn to take the shame bit out. Otherwise it just escalates, and where do we end up?
The fundamental premise of jameshart's comment is that group membership is what counts. jamehart assumes graycat is a man, that men talk to women in certain (oppressive) ways, and therefore graycat must show humility--or else.
The comment is nonsensical and incoherent interpreted any other way, and it obviously uses shame as a threat. A threat such as this is only effective if graycat is actually not a misogynist; if he were, he would just ignore it.
In other words, the essential characteristic of jameshart's comment is an appeal to graycat's moral self-doubt and it relies on his fear, guilt, or ignorance. jameshart expects graycat to renounce or revise his anecdote without discussion, under threat of being considered morally unworthy.
That seems like overinterpretation to me, based on the ideological battle lines of the moment. Even if you're right, though, I think people mostly do that because they want to stand up for someone.
Edit: maybe it would be of interest to add that, from the therapeutic work I've been involved in, it is clear that people's motivations in these areas can often be traced to family dynamics—which is to say, to love. Even when it doesn't look or sound like love, love is usually the driving force. I often think of Chesterton's line, "The soldier fights not because he hates what is in front of him, but because he loves what is behind him". You can say the same thing about political and ideological battles, which after all are (quoting a different celebrity) war by other means.
This is an optimistic view, because the more we can see and acknowledge that love in each other, the less we need to be in conflict. The challenge is that such love often goes through complex transformations and distortions which can be hard to disentangle.
I believe in treating people with justice, which means to treat each person as they deserve to be treated.
So long as I believe a person is merely mistaken--that is, they lack evidence or the proper method of thinking, but are otherwise virtuous--then I will forgive them a thousand grievances and "acknowledge [the] love" in them. If they are important to me and I don't have to give up something more important, I would be willing to invest the time to bridge our differences. A relationship is the earned reward of the participants' virtues.
But if a person consciously takes a single step toward evil, they are a threat to my life. It would be self-destructive for me to try to see the love in the thug mugging me at gunpoint. It disrespects the people I admire and destroys the value of those positive relationships. Such a person might work to reform their character, but I have no obligation toward them.
I've come to the conclusion there are people in this world who act out of hatred for life and fear of living.
There are soldiers who fight for evil causes, and they are evil. Robert E Lee was offered a senior role in the Union army, but chose to fight for the Confederates. Some might say he fought for love of southern culture or his home or family or any number of other inessential factors; they evade the essential that Lee fought to preserve slavery.
There are soldiers who fight for good causes, and they are good. Sherman fought slavery and he obliterated everything in his path that supported slavery.
To equivocate between the two rewards the wicked and damns the good. Any ethical method that fails to distinguish the essential difference between the two is at best useless, and at worst a tool in the service of evil.
Minimizing conflict is a standard that is anti-life. We should be in conflict with evil. The test I apply in online discussion is to ask myself "What is this person advocating for? If this person achieved their ideal outcome, what would that look like?"
The opinion I've come to regarding comments like jameshart's is that they actively advocate for nothing--nihilism. I don't see any evidence indicating they want to replace something bad with something good. In this case, they want to replace a sentimental anecdote with silence.
By the way, I know these views are radically different. If you are curious about other applications or how it might apply to family interactions, PM me and I'd be happy to chat.
Fran gave a talk when I interned at TJ Watson one summer. Her stories of the early days of compilers were beyond fascinating and made it clear how much we all now were just building on ideas they established decades ago.
Later, my wife was the first to receive the IBM PhD fellowship established in Fran's honor. Fran awarded it to her at a conference (Grace Hopper I think) and of course was gracious, offering to help as your career moved forward. Thankful for that investment in our future.
I'd recommend reading her interview in Coders At Work. I never realized that compilers were already a flourishing field by the time C came around, and that C actually ended up having some negative effects in compiler dev.
I wanted to say that C is not really very highly regarded nowadays, but that only adds extra php-directed snark to your post, which is not wholly a bad thing.
I don't have the book in my office, but essentially
"In our conversation she talks about what that transition was like as well as why it is important to increase the diversity in the field and how C has grievously wounded the study of computer science."
Sadly, this is the first I've heard of her. Hopefully all that means is I'm not a real programmer.
Edit: To be clear, I really meant "I hope other people here are familiar with her work, even though I am not because I'm not a real programmer." I'm happy to see that some people are, in fact, familiar with her and her work.
> Hopefully all that means is I'm not a real programmer.
Sadly, no, it's not just that. Most my immediate colleagues, for example, don't know of her or her work, either. It's one heck of a field.
She had expressed some dismay, in interviews, at being the first woman to win the Turing Award. Not the Turing Award part, of course, the "first woman" part. She was far from being the first deserving candidate who didn't happen to be a dude. So I hope she wouldn't mind linking this here, even today: https://www.hillelwayne.com/important-women-in-cs/
There's a weird gap in that lineup in that practically every person on that list is pretty old (born in the 30s-40s) and their achievements usually date from around the 70s.
Is this just because achievements are usually recognized in retrospect, or is this because the 50s to 70s were the most influential portion of computer science (since all groundbreaking things were discovered in the beginning), or is this because women were pushed out more and more by the 70s?
> a "real computer scientist," whatever that means
At university we would say that computer science was the art, where programming was the craft[1]. It is probably fairer to state that programming is an application of the science.
[1] Though with less of a sneery tone than used when people said "mathematics is the art where computer science is the craft"
I think that this might be exploring the analogy's breaking point.
It can be quite easy to draw a clean line between theoreticians and implementors in other fields. Biologists and veterinarians, physicists and engineers, etc. But who was the last major computer science theoretician who wasn't also a skilled programmer or system architect (or both)? Alonzo Church?
After looking through all the Turing Award winners, my answer is Stephen Cook - a CS mathematician who did nothing on engineering, discovered the concept of NP-completeness.
I create programs professionally and I know very few winner of the Turing Award by name. If someone said "who was the first native-English speaking Turing Award winner" I would not be able to answer unless I went through each winner and manually checked. I suspect quite few programmers in the world (and people on HN) are familiar enough with Turing Award winners that they can answer questions like that.
I would guess that people who work on building compilers and compiler optimization are more likely to know her name than programmers.
Interesting. If you search for "died" on HN in the last month, say, you'll find many examples. Most have 0 or 1 comments, many have around the same as this has now, but none are about it being sad to not have heard about that person. Any idea why this one in particular made you feel that way?
Many years ago, I had a good friend named Frances who lamented the fact that people generally could not keep it straight that Frances is a girl's name and Francis is a boy's name. Rembering that friend, I clicked on the link to check the gender because people don't always follow the rules about such things and because I was short of sleep and wondering if I was even remembering that correctly.
Given my reason for clicking the link, I believe it's the first time I've seen her mentioned on HN. I likely would have clicked on any article with the name Frances in the title and remembered the name if I had ever seen it before.
Because I'm a woman, I actively keep my eye out for female role models. I have a fairly strong math background (for the world at large -- not for the HN crowd) and spent some time looking up info on Maryam Mirzakhani, the first female Fields Medalist, and even blogged about it at the time.
Given my interest in female role models and my personal association with the name Frances, I think I would have known the name had I ever seen it before. It would have likely stuck with me.
I've been here eleven years. It seems I've never seen her name before. And, in fact, if you search for it, it comes up (in the titles section, as part of a description, not really a title) only once ten years ago (until the past 24 hours).
> the fact that people generally could not keep it straight that Frances is a girl's name and Francis is a boy's name.
I literally just looked it up, because I wasn't sure. The simple rule presented is that if it's Frances with an e like in "her", then it's the name historically used for women, and if it's Francis with an i like in "him" then it's the name historically used for men.
It truly is a shame that the farther you go back in computer science, the more likely names whose traditional gendering is somewhat ambiguous are to refer to women, and how now that luminaries of the field are passing away, how much more even the field was between the sexes in the past.
We often talk about how we need to bring more women into the field of Computer Science, but I think it's important to note we're trying to bring them back into the field, because they were here from the beginning and it wouldn't be the same without their contributions.
They've now added the black bar and substantive comments about her work are finally at the top of the discussion (instead of my relatively vacuous remark). I'm happy to see her getting a proper send off appropriate to her level of contributions to the field.
I think this isn't really the time or place to get into gender issues and the field of Computer Science, especially not for me. I see things very different from most other people here and that makes communication challenging.
In this case, that would amount to a terrible derail from the focus on honoring the work and life of Frances Allen.
> I think this isn't really the time or place to get into gender issues and the field of Computer Science
It's worth noting that, according to the article, Frances Allen actually spent some time focusing on exactly that.
As important as distinguishing her work in the world of computing and programming, Fran was also committed to her team by embracing their ideas and synergies and, in particular, supporting women. She spent many years as a mentor through IBM’s mentor program.
...and later...
“Professionally, Fran spent a lifetime working to advance the field of computing and pioneer new breakthroughs. Personally, she was equally focused on inspiring and motivating young people – especially women – to do the same,” said Fran’s nephew, Ryan McKee, on the IEEE honor.
So I imagine she would be quite happy to have the topic brought up (at least in a positive manner) in discussion of her life and career.
That said, I brought that up to highlight her achievements and character, not to bring you into that conversation if you don't want to be in it, which is your choice, and I can see avoiding that topic as a useful strategy if you think it can't or won't be handled appropriately by the people involved. As such, don't feel compelled to respond about any of that if you don't want to. :)
Edit: It occurs to me now you might have been referring to something entirely different than I thought, in which case I wasn't trying to bring anything of that into the discussion at all, and my wording was purely an attempt to avoid that type of discussion as well.
The elephant in the room is that I'm probably the highest ranked woman on HN. This is likely a large part of why my relatively vacuous remark was the top comment for some hours. I know from past public remarks and private emails that some people here look to me for guidance on gender issues.
I've given my guidance for this issue today: We are here to honor the life and work of Frances Allen. Everyone please, kindly, focus on that and don't be offended that I'm trying to step away from the discussion at this point.
She has been mentioned in comments before. Mostly in the context of compiler optimization, programming models, the history of C vs. other programming languages as systems programming language, and so on. Mostly an excerpt from a book where she said in an interview something along the lines of "We had such good things, and then came C..." (implying we lost the good things(with C))
Yes, I'm aware. But it's a really large forum with a lot of traffic and I'm not a programmer, so those comments are less likely to be read by me than titles.
> Any idea why this one in particular made you feel that way?
Perhaps there's something to do with the fame of the person?
It's difficult to say but it appears that the implicit HN 'criteria' for this is in computer science is to at least be famous enough to be an ACM Turing Award winner. Maybe this is why the reception to the death of another fellow computer scientist and engineer was low. [0]
Nevertheless, they are both worthy of the HN black bar to recognise their achievements to computer science. But I would expect to see a black bar for Frances Allen's passing but unfortunately not for Bill English.
I read one of Frances’ papers on compiler optimization, and while some of it went over my head, it was still valuable information; the world is a sadder place without her.
My dad should have married her. Same story except Spartans instead of Wolverines and he went into Defense instead of IBM, and he’s older and still rockin’ Siri on his AppleWatch.
"Eschew flamebait. Don't introduce flamewar topics unless you have something genuinely new to say. Avoid unrelated controversies and generic tangents."
Going on a tangent, I think most of us missed Bill English's passing a few days ago since I think because people only noticed it on the weekend when there are less HN users active.
She was in her 30s when she wrote it.