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.
She was in her 30s when she wrote it.
sanxiyn 1351 days ago [-]
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.
sitkack 1350 days ago [-]
> 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.
mpweiher 1350 days ago [-]
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.
scott_s 1349 days ago [-]
> 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.
MrBuddyCasino 1349 days ago [-]
So that is were this Golang rule comes from.
titzer 1350 days ago [-]
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 :-)
I can’t think of any noteworthy idea in computing that didn’t exist in 1971.
derefr 1350 days ago [-]
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. :)
aidenn0 1350 days ago [-]
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.
derefr 1350 days ago [-]
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.
titzer 1350 days ago [-]
> 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.
aidenn0 1350 days ago [-]
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.
p1necone 1349 days ago [-]
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.
tjalfi 1350 days ago [-]
VLIWs[0] and trace scheduling[1] were both from the early 1980s.
Dependence analysis, automatic vectorization, and automatic parallelization were invented after 1971.
Fast algorithms for computing dominators[2] were late-70s.
Graph coloring register allocators were introduced in the early 1980s.
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.
sli 1350 days ago [-]
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.
MarkCC 1350 days ago [-]
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.
graycat 1350 days ago [-]
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.
ricv 1339 days ago [-]
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
flippinburgers 1349 days ago [-]
Thank you for sharing! I always enjoy hearing stories about how great minds act when interacted with! She sounds like she was a pleasure to work with.
jameshart 1350 days ago [-]
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?
dang 1350 days ago [-]
"Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith."
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.
corford 1350 days ago [-]
>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.
jecel 1350 days ago [-]
> 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.
morelisp 1350 days ago [-]
While I suppose it's possible someone was writing PL/I quite recently, the more probable option is that this story is from the late 60s.
kjs3 1349 days ago [-]
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.
tkeeler 1350 days ago [-]
Why is there an assumption that graycat is male? Was there an indication of gender?
LukeShu 1350 days ago [-]
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.
selimthegrim 1350 days ago [-]
He has discussed his wife as well as being a male in graduate school in the past.
sergiotapia 1349 days ago [-]
What a nasty nasty reply. Think about why you chose to leave this comment. Is this something you really believe? Or are you just saying The Words?
jameshart 1349 days ago [-]
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.
1349 days ago [-]
sergiotapia 1349 days ago [-]
Thanks for clarifying. You are a Good Guy and an Ally.
flippinburgers 1349 days ago [-]
This is such a bleak take on an innocuous story.
samatman 1350 days ago [-]
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?
abtinf 1349 days ago [-]
> You're both reacting to a perceived slight
Are they?
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.
This kind of comment must not have a place on HN.
dang 1349 days ago [-]
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.
abtinf 1349 days ago [-]
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.
hardwaregeek 1351 days ago [-]
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.
wglb 1351 days ago [-]
It was more that C hindered optimization research. The interview was awesome as you said.
sitkack 1351 days ago [-]
C and Unix hindered a whole lot. It was the PHP of its day.
martinlaz 1350 days ago [-]
Nice analogy. Although it's very unlikely that PHP will ever be as highly regarded as are C and Unix today.
tomsmeding 1350 days ago [-]
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.
gvjddbnvdrbv 1349 days ago [-]
Have you used modern PHP? Its a great language these days.
wglb 1350 days ago [-]
I am struggling to understand your analogy here?
anitil 1350 days ago [-]
Ordered the book, but would you be willing to go in to the issues around C while I wait for it to arrive?
wglb 1349 days ago [-]
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."
gavreh 1350 days ago [-]
Looks like a great book, will read - thanks for the recommendation.
AnimalMuppet 1350 days ago [-]
How did C have negative effects on compiler dev? Did everyone else get a lobotomy, and forget how to do what they already knew?
wglb 1348 days ago [-]
It was more that C hindered optimization research.
DoreenMichele 1351 days ago [-]
First female IBM fellow.
First female winner of the Turing Award.
Lots of other notable stuff.
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.
mumblemumble 1351 days ago [-]
> 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/
formerly_proven 1350 days ago [-]
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?
pmiller2 1351 days ago [-]
Yeah. If anything, I would say it means they're not a "real computer scientist," whatever that means.
Just to put the second part of your comment in perspective, there have only been 3 female winners of the Turing award, total, by my count.
dspillett 1350 days ago [-]
> 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"
mumblemumble 1350 days ago [-]
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?
segfaultbuserr 1350 days ago [-]
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.
1351 days ago [-]
belorn 1350 days ago [-]
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.
CarbyAu 1351 days ago [-]
And it doesn't mean even that.
Many worthwhile people in the world. Not all of them are famous to the people who would love to know them.
At least we can both get to know her more starting now.
globular-toast 1350 days ago [-]
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?
DoreenMichele 1350 days ago [-]
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.
DoreenMichele 1350 days ago [-]
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.
kbenson 1350 days ago [-]
> 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.
DoreenMichele 1350 days ago [-]
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.
LargoLasskhyfv 1350 days ago [-]
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))
DoreenMichele 1350 days ago [-]
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.
LargoLasskhyfv 1350 days ago [-]
Maybe it's also because for most in the industry it amounts to sacrilege.
edit: Nothing to speak about, hush, hush, otherwise the emperors new clothes ...
rvz 1350 days ago [-]
> you'll find many examples
For example: [0]
> 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.
vaxman 1349 days ago [-]
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.
jolux 1350 days ago [-]
Wish we could get the black bar up.
finphil 1347 days ago [-]
RIP
relaunched 1351 days ago [-]
I'd love to see a black banner / bar in her honor.
hardwaregeek 1351 days ago [-]
Agreed. Any Turing Award laureate, let alone the first female Turing Award laureate, deserves a black banner
scott31 1351 days ago [-]
> Any Turing Award laureate deserves a black banner
Except for Tim Berners-Lee, who tries to make the web a proprietary platform
dang 1350 days ago [-]
"Eschew flamebait. Don't introduce flamewar topics unless you have something genuinely new to say. Avoid unrelated controversies and generic tangents."
So no black banner because you can't torrent someone else's hard work.
fb03 1351 days ago [-]
I am rooting for this also.
ixtli 1351 days ago [-]
I’d agree. I read an optimization paper by her in college.
anotherevan 1351 days ago [-]
As an aside, when there is a black bar, I would also love it to link to the reason it is there.
paublyrne 1350 days ago [-]
That's a nice idea, like how Google doodles link to some background information.
yardshop 1350 days ago [-]
Even just a "title" attribute with the name of the person being honored would help sometimes.
chaostheory 1350 days ago [-]
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.
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.
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.
> 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.
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 saw her 2007 Turing Award speech. I have tremendous respect for Fran and like your idea to name a codegen after her :-)
Vectorizing compilers have been around since at least the late 1970s; the Cray 1[0] had a vectorizing compiler in 1978.
Lamport’s Parallel Execution of DO Loops[1] was published in 1974.
[0] https://en.m.wikipedia.org/wiki/Cray-1#Software
[1] http://lamport.azurewebsites.net/pubs/do-loops.pdf
(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. :)
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.
(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.
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.
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.
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.
Dependence analysis, automatic vectorization, and automatic parallelization were invented after 1971.
Fast algorithms for computing dominators[2] were late-70s.
Graph coloring register allocators were introduced in the early 1980s.
[0] https://en.m.wikipedia.org/wiki/Very_long_instruction_word
[1] https://en.m.wikipedia.org/wiki/Trace_scheduling
[2] https://en.m.wikipedia.org/wiki/Dominator_(graph_theory)
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.
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.
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?
https://news.ycombinator.com/newsguidelines.html
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.
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.
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.
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.
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 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?
Are they?
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.
This kind of comment must not have a place on HN.
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.
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.
Optimizing Compilers for Parallel Computers, lecture by Frances E. Allen https://www.youtube.com/watch?v=Qv-wXcUxrmE
Frances Allen, 2006, ACM A.M. Turing Award Lecture, "Compiling for Performance: A Personal Tour" https://www.youtube.com/watch?v=NjoU-MjCws4
https://www.youtube.com/watch?v=xLTUvFboveM
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.
"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."
First female winner of the Turing Award.
Lots of other notable stuff.
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.
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/
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?
Just to put the second part of your comment in perspective, there have only been 3 female winners of the Turing award, total, by my count.
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"
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?
I would guess that people who work on building compilers and compiler optimization are more likely to know her name than programmers.
Many worthwhile people in the world. Not all of them are famous to the people who would love to know them.
At least we can both get to know her more starting now.
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).
https://hn.algolia.com/?q=frances+allen
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.
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.
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.
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.
edit: Nothing to speak about, hush, hush, otherwise the emperors new clothes ...
For example: [0]
> 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.
[0] https://news.ycombinator.com/item?id=24032820
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.
Except for Tim Berners-Lee, who tries to make the web a proprietary platform
https://news.ycombinator.com/newsguidelines.html
Why?
AFAICS he's doing the exact opposite:
https://contractfortheweb.org/