Sat, 29 Mar 2008 23:35:53 -0700 (PDT)

Related articles |
---|

Prediction of local code modifications plfriko@yahoo.de (Tim Frink) (2008-03-27) |

Re: Prediction of local code modifications gah@ugcs.caltech.edu (glen herrmannsfeldt) (2008-03-28) |

Re: Prediction of local code modifications preston.briggs@gmail.com (preston.briggs@gmail.com) (2008-03-28) |

Re: Prediction of local code modifications max@gustavus.edu (Max Hailperin) (2008-03-28) |

Re: Prediction of local code modifications gah@ugcs.caltech.edu (glen herrmannsfeldt) (2008-03-29) |

Re: Prediction of local code modifications preston.briggs@gmail.com (preston.briggs@gmail.com) (2008-03-29) |

Re: Prediction of local code modifications plfriko@yahoo.de (Tim Frink) (2008-04-01) |

Re: Prediction of local code modifications preston.briggs@gmail.com (preston.briggs@gmail.com) (2008-04-01) |

Re: Prediction of local code modifications max@gustavus.edu (Max Hailperin) (2008-04-02) |

Re: Prediction of local code modifications cfc@shell01.TheWorld.com (Chris F Clark) (2008-04-02) |

Re: Prediction of local code modifications gah@ugcs.caltech.edu (glen herrmannsfeldt) (2008-04-03) |

Re: Prediction of local code modifications max@gustavus.edu (Max Hailperin) (2008-04-03) |

[8 later articles] |

From: | "preston.briggs@gmail.com" <preston.briggs@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Sat, 29 Mar 2008 23:35:53 -0700 (PDT) |

Organization: | Compilers Central |

References: | 08-03-105 08-03-109 08-03-110 08-03-112 08-03-114 |

Keywords: | history, theory |

Posted-Date: | 30 Mar 2008 09:54:14 EDT |

On Mar 29, 12:33 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu>

wrote:

*> In my post I had a reference to the wikipedia article referencing*

*> Richard Bellman and his development of dynamic programming. But how*

*> many people read Bellman's paper and started implementing such*

*> algorithms in the 1950's?*

A few. My recollection of Bellman was from Knuth, Art of Programming,

Volume 1, Notes on the Exercises, page xvii. The copyright is 1968.

Another example of dynamic programming, perhaps more directly relevant

to compilers, is the CYK parsing algorithm, from 1965, see

http://en.wikipedia.org/wiki/CYK_algorithm

*> Computer science conferences on pattern matching algorithms are*

*> dominated by papers on biological applications, and rarely do*

*> you see applications to compilers.*

The days I work for Google, and we do a little pattern matching too.

But I guess I don't think of dynamic programming as restricted to

pattern matching. The examples from my grad school algorithms book

(Aho, Hopcroft, and Ullman, 1974) focus on finding the product of many

matrices. And there's Aho and Johnson's paper on optimal evaluation

of expressions, from 1975. (The work you cited from LCC descends from

Aho and Johnson). And there's the BURS theory, a big favorite of

mine. Plenty of good compiler stuff!

Preston

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.