Design Patterns in Dynamic Languages | Hacker News Reader

Design Patterns in Dynamic Languages

norvig.com

37 pointspmarin18 comments

From whence came the phrase "16 of the 23 patterns in Design Patterns were 'invisible or simpler' in Lisp."

Interesting, but using a dynamically typed programming language != dynamic programming.

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

Trust me, Norvig knows about the difference.

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.

Does it mean he can use them in a confusing way?

It's not whether norvig knows the difference or not. It's whether the person who's reading the title knows the difference.

no, we are talking about a dynamic programming language, not a dynamically typed programming language.

The name of the language 'Dylan', he is using, is short for 'Dynamic Language'.

You can read about Dylan in the Foreword, Preface and Introduction of its manual:

http://lispm.dyndns.org/documentation/prefix-dylan/book.anno...

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, ...

* changing the class inheritance

* changing an object from one class to another

and more.

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."

(Stolen from http://en.wikipedia.org/wiki/Dynamic_programming#History)

Thanks, but I knew that already. Norvig used a different meaning. But not 'dynamically typed something', which was my point.

OK, "When Norvig wrote that presentation, there wasn't even a Wikipedia." just struck me as a bit arrogant. Sorry.

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.

http://en.wikipedia.org/wiki/Locator/Identifier_Separation_P...

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.

By the way, Wikipedia has disambiguation pages (like http://en.wikipedia.org/wiki/C_(disambiguation)) when there are multiple common meanings for an entry.

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.

I've made this point several times on HN. When I saw this was a presentation by Peter Norvig, I figured maybe it's not worth the effort.

Reply on news.ycombinator.com