4 ms·

Interesting, but using a dynamically typed programming language != dynamic programming. http://en.wikipedia.org/wiki/Dynamic_programming http://en.wikipedia.or

Interesting, but using a dynamically typed programming language != dynamic programming. http://en.wikipedia.org/wiki/Dynamic_programming http://en.wikipedia.org/wiki/Dynamic_programming

acangiano 17y ago
Trust me, Norvig knows about the difference.
- eru 17y ago
  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.
  - scott_s 17y ago
    "[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.
    - eru 17y ago
      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.
- viraptor 17y ago
  Does it mean he can use them in a confusing way?
- j_baker 17y ago
  It's not whether norvig knows the difference or not. It's whether the person who's reading the title knows the difference.
lispm 17y ago
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.annotated/annotated-manual.html 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.
- dkersten 17y ago
  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.
  - lispm 17y ago
    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.
    - eru 17y ago
      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 http://en.wikipedia.org/wiki/Dynamic_programming#History)
scott_s 17y ago
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.

Interesting, but using a dynamically typed programming language != dynamic programming. http://en.wikipedia.org/wiki/Dynamic_programming http://en.wikipedia.org/wiki/Dynamic_programming

acangiano 17y ago

Trust me, Norvig knows about the difference.

eru 17y ago
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.
- scott_s 17y ago
  "[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.
  - eru 17y ago
    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.
viraptor 17y ago
Does it mean he can use them in a confusing way?
j_baker 17y ago
It's not whether norvig knows the difference or not. It's whether the person who's reading the title knows the difference.

lispm 17y ago

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.annotated/annotated-manual.html 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.

dkersten 17y ago
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.
- lispm 17y ago
  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.
  - eru 17y ago
    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 http://en.wikipedia.org/wiki/Dynamic_programming#History)

scott_s 17y ago

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.