Yes, but I also expected something about dynamic programming. Norvig's title leads to confusion. (Or rather the older usage of the term is not very well thought-out, and should probably be replaced with "solving problems by solving all smaller problems". Alas, the other guys came first.)
Interestingly there are some nice patterns in implementing dynamic programming --- especially in relation to memoization and lazy evaluation. I should probably write an article with the same title.
"[S]olving problems by solving all smaller problems" is really just plain ol' divide-and-conquer. What makes dynamic programming algorithms different, although a subset of, divide-and-conquer algorithms is that intermediate solutions are stored for later use.
Perhaps I should have been more cleary. I meant that Dynamic Programming solves _all_ smaller problems. Divide-and-Conquer only solves smaller problems that come up as a part of the bigger problems.
So e.g. quicksort sorts sublists. A hypothetic dynamic programming solution would first sort _all_ conceivable lists of length 1, then use that to solve all lists of length 2, and so on.
But your distinction may come into it as well. Though you can also use memoization in Divide-and-conquer.
Common Lisp and Dylan were 'sold' as 'OODL', Object-oriented Dynamic Languages. Norvig argues in the context of OODLs like Common Lisp (CLOS), Dylan, and related (say, Smalltalk).
'Dynamic' in this context does not mean 'dynamically typed', but being capable of changing the language, its implementation or the program - while the software is running.
Dynamic features are:
* adding, removing, changing classes
* adding, removing, changing methods
* reflection
* introspection
* meta object protocol
* first class representations of classes, methods, ...
no, we are talking about a dynamic programming language, not a dynamically typed programming language.
And grandparents wikipedia link about Dynamic Programming is talking about neither, but rather a programming technique for efficient recursive solving of a certain class of problems, often used in mathematical optimization.
where does Norvig mention wikipedia? When Norvig wrote that presentation, there wasn't even a Wikipedia.
Some words have more than one meaning. Norvig used the words in a different meaning and context. In his context 'dynamic programming' was not referring to what Wikipedia describes as 'dynamic programming' AND he also was also not talking about dynamic typing.
Wikipedia did not invent the term dynamic programming for that particular technique. See:
"The term was originally used in the 1940s by Richard Bellman to describe the process of solving problems where one needs to find the best decisions one after another. By 1953, he had refined this to the modern meaning, which refers specifically to nesting smaller decision problems inside larger decisions,[1] and the field was thereafter recognized by the IEEE as a systems analysis and engineering topic. Bellman's contribution is remembered in the name of the Bellman equation, a central result of dynamic programming which restates an optimization problem in recursive form.
Originally the word "programming" in "dynamic programming" had no connection to computer programming, and instead came from the term "mathematical programming"[2] - a synonym for optimization. However, nowadays many optimization problems are best solved by writing a computer program that implements a dynamic programming algorithm, rather than carrying out hundreds of tedious calculations by hand. Some of the examples given below are illustrated using computer programs."
And I was replying to the part of your message where you replied to the original commenter saying that he was wrong because Norvig was talking about: dynamic programming language, not a dynamically typed programming language, but the original commenters comment still makes sense if you replace dynamically typed programming language with dynamic programming. I never said Norvig posted it, I said that the grandparent of my post - the original comment you replied to - posted it.
Norvig wrote that a decade ago. That's not arrogant, but a fact. It was not a time when people point to Wikipedia and are confused when a term has also a different meaning, which is not explained on Wikipedia.
Before that Norvig worked for Harlequin, who developed LispWorks and a commercial Dylan implementation (plus a lot of other things). At that time in the programming language community, they, and earlier Apple, talked about 'dynamic programming languages' - languages with a certain amount of runtime flexibility. The slides have some 'marketing' quality, trying to market 'dynamic languages' as simpler than, say, C++ - by demonstrating that with the mentioned patterns.
But you can bet that Norvig knew/knows the mathematical term 'dynamic programming' which is topic in any basic maths course at universities in computer science and mathematics departments - especially if you work in AI, like Norvig did. But Norvig did not make this presentation to a maths audience.
There are lots of terms with more than one meaning. I'm a Lisp programmer. At Cisco, Lisp is short for 'Locator Identifier Separation Protocol', a recent Internet protocol.
Yes, I agree about multiple concepts having similar names.
We should keep Wikipedia out of the discussion. To point to the common usage of dynamic programming in the mathematical sense, people could just as well have mentioned some textbooks (or not supplied any sources at all). Wikipedia is just a handy reference, but only tangential to the argument.
Related material: http://c2.com/cgi/wiki?AreDesignPatternsMissingLanguageFeatu...