11

Can a typical Lisp dialect solve problems using the bottom-up "dynamic programming" approach?

(Please note: I'm not talking about "memoization" which, as far as I understand, is trivial using any Lisp dialect. I'm really talking about bottom-up Dynamic Programming, where you build, for an example, your array bottom up and then use the elements you just introduced to compute the next ones.)

For example, using dynamic programming, the "0-1 knapsack" problem can be solved in pseudo-polynomial time for inputs on which any other method would fail.

An imperative (incomplete) solution is:

for (int k = 1; k <= a.length; k++) {
    for (int y = 1; y <= b; y++) { 
        if (y < a[k-1]) {
            knap[k][y-1] = knap[k-1][y-1];
        } else {
            if (y > a[k-1]) {
                knap[k][y-1] = Math.max(knap[k-1][y-1], knap[k-1][y-1-a[k-1]] + c[k-1]);
            } else {
                knap[k][y-1] = Math.max(knap[k-1][y-1], c[k-1]);
    }
}

Is such a thing possible to do in the various Lisp dialects? If no, why not?

11
  • I'm not sure I understand the question; the canonical implementations of algorithms in Lisps is almost always recursive and "bottom-up". Commented Oct 19, 2011 at 16:41
  • 3
    @Dave Newton: I may not be very clear... What I referred to was the "bottom up" as opposed to "top down" in the Wikipedia article about Dynamic Programming, where "memoization" (saving the result of idempotent method/function calls for later reuse) would be "top down" while working your way from the bottom would be "bottom up". Both approach are know to be able to reduce some problem to pseudo-polynomial time. But I'm not interested in memoization in this case: I'd like to know if I can build, say array, from the "bottom up" (I compute cell 1, then I use cell 1 to compute cell 2, etc.) Commented Oct 19, 2011 at 16:45
  • 3
    What makes you think that you can't do this in Lisp? Commented Oct 19, 2011 at 19:35
  • Are you thinking of Lisp as a functional language? Although you can use it in that style (especially Scheme, due to tail-recursion optimisation), and you can do a bunch of powerful and/or weird things with its syntax, it's still just an imperative language with mutable state, just like C. You could translate your C code essentially "word for word" into Lisp. Commented Oct 20, 2011 at 5:10
  • 1
    @CedricMartin: Common Lisp is a multi-paradigm language, and there is nothing wrong with using its features for full effect. Just about all real-world Common Lisp code uses mutable objects, arrays and even global variables. AFAIK Scheme programmers go to much greater lengths to avoid imperative code if at all possible.
    – han
    Commented Oct 23, 2011 at 8:36

4 Answers 4

15

Of course this is possible. The only things you need are arrays, integers and a loop construct. E.g., in Scheme, your algorithm can be transcribed using vectors. The main problem is that it becomes hard to read, since knap[k-1][y-1] becomes (vector-ref (vector-ref knap (- k 1)) (- y 1)) and

knap[k][y-1] = knap[k-1][y-1];

becomes

(vector-set! (vector-ref knap k) (- y 1)
             (vector-ref (vector-ref knap (- k 1)) (- y 1)))

(or a hairy trick with moduli), while memoized recursions just remain readable.

Speaking from experience, I recommend you stick to the memoization when programming in Lisp and similar languages. If you use hash tables, the expected asymptotic time and space complexity are the same for memoization and DP.

4
  • +1 that is very interesting. So you're saying that I should stick with memoization because it's not using that much more memory and because it's way easier to write/read? Commented Oct 19, 2011 at 16:56
  • 1
    @CedricMartin: yes. Peter Norvig proved back in 1990 that a properly memoized recursive descent parser is equivalent to the CKY algorithm (a DP-based parser) and similarly, many DP problems can be formulated as memoized recursions.
    – Fred Foo
    Commented Oct 19, 2011 at 17:00
  • 3
    +1. A side comment, though, since the OP asked about “various Lisp dialects”: Common Lisp has multi-dimensional arrays built-in, so the “hard to read” part, while still true as compared to the special indexing syntax support in C, applies a bit less strongly there. For example, knap[k][y-1] = knap[k-1][y-1]; becomes (setf (aref knap k (1- y)) (aref knap (1- k) (1- y))). Commented Oct 19, 2011 at 18:15
  • 2
    (Plus, if you really do a lot of array processing, you can always write a reader macro. :)) Commented Oct 19, 2011 at 18:26
5

the short answer is yes, Clojure can work directly with java arrays so a direct translation is very straitforward

 (for [k (range 1 (count a)) 
       y (range 1 b)]
   (if (< y (aget a (dec k)))
     (aset knap k (dec y) (aget knap (dec k) (dec y))
           (if (> y (aget a (dec k)))
             (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                       (aget knap (dec k) (+ (- y 1 (aget a (dec k)))
                                                             (aget c (dec k))))
                                       (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                                                 (aget c (dec k))))))))))

this is not very idomatic Clojure because it combines the looping with the work to be done. The resulting code will be much cleaner and easier to show correct if you seperate the elements of this loop out.

As a trivial first step, If we seperate the looping from the 'work' then we get.

(defn edit-array [k y]
   (if (< y (aget a (dec k)))
     (aset knap k (dec y) (aget knap (dec k) (dec y))
           (if (> y (aget a (dec k)))
             (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                       (aget knap (dec k) (+ (- y 1 (aget a (dec k)))
                                                             (aget c (dec k))))
                                       (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                                             (aget c (dec k))))))))))
(for [k (range 1 (count a)) y (range 1 b)]
   (edit-array k y))

Then we can test edit array from the repl and convince our selves that it works (and write a unit test perhaps). After that, perhaps you would like to start to look at edit-array more closely and decide if it is possible to break this into steps that are easier to test independently. Perhaps you could change this to use a functional style instead of mutating an array. Here I will move away from your specific problem because I have to admit that I dont understand the original problem this linear programming solution was designed to solve.

 (defn finished? [row] ... determine if we have reached the final state ...)

 (defn next-row [current-row]
    (for [y (range 1 (count current-row)]
      ... code to produce a new vector based on the previous one ...))

(take-while #(not (finished? %) (iterate next-row (initial-state)))

The basic notion of what I see Idomatic Clojure code looking like is to decompose the problem into simple (does only one thing) abstractions and then compose them to solve the main problem. Of course this must always be tailored to suit the problem at hand.

4
  • this is not very idomatic Clojure because it combines the looping with the work to be done -- can you expand on this? Commented Oct 20, 2011 at 11:08
  • Thanks, I'm trying to use Clojure having never studied FP in any formal way. I keep hearing that imperative loops are bad, without any further justification. I try to use built-in iterators when possible, but sometimes fail, e.g., when there are a number of collections involved in the iteration. Commented Oct 21, 2011 at 10:13
  • One small question: in your last line above [(take-while...], where does current-row get its value? Commented Oct 21, 2011 at 10:20
  • nowhere, you have revealed my dirty little secret! I posted this without testing! shame shame Commented Oct 22, 2011 at 1:38
4

Pardon me for saying this, but the wikipedia page you refer to is (imnsho) not very well-written. In particular, it more or less fabricates the dichotomy between top-down and bottom-up dynamic programming, and goes on to describe one as "more interesting". The only difference between the two is the order in which the table is constructed. Memoization gives rise to both of these, depending on the order in which the calls are made.

Apologies in advance to whoever wrote this section of the page; I appreciate your effort, I just think that the section needs some work.

8
  • But "memoization" is specifically defined as reusing the results of idempotent method calls on subsequent calls, as to avoid needing to compute them more than once. While building an array from scratch, starting from cell1/line1 to cell2/line1 to cell3/line1 etc. and then from cell1/line2 (reusing cells from line1 to do so) to cell2/line2 etc. is not memoization. Because here there aren't idempotent method calls being saved/reused. larsmans 's fine answer seems to be precisely what I was after and seems to agree with "my" (and the one of Wikipedia) of "memoization". Commented Oct 19, 2011 at 17:09
  • 2
    I can't find the word "interesting" in the WP article. I just scanned it quickly and its use of the terms top-down and bottom-up seem to match their use in parsing, at least as done in NLP (where the choice of parsing strategy can matter greatly).
    – Fred Foo
    Commented Oct 19, 2011 at 17:10
  • @John Clements: now I agree about the top-down/bottom-up which may be made up. But I still don't think I'd call what they call the "bottom up" approach "memoization" (because, once again, there aren't method calls being reused and, in addition to that, typically the "bottom up" approach computes lots of results that won't be necessarily used... While in the "memoized" approach only results that are actually going to be used are computed). Commented Oct 19, 2011 at 17:11
  • 1
    @larsmans - since I did read that article over the past few days to refresh myself, they used it here: "Bottom-up approach: This is the more interesting case." - from this section: en.wikipedia.org/wiki/…
    – wkl
    Commented Oct 19, 2011 at 17:13
  • 1
    @John Clements: no problem being pointy ; ) Here stackoverflow.com/questions/6184869 user aaoibe (65K rep as I write this) explains the differences between "top-down" and "bottom-up". As far as I recall, there are concrete problems where the bottom-up works better (more efficiently/space-efficiently) than the top-down approach. I wouldn't say they're identical. Maybe that "conceptually" or "mathematically" they're identical but taking into account the physical limitation of the devices we're working with, I'd tend to think they're not really the same thing. Commented Oct 20, 2011 at 15:28
2

Here's a nice bottom-up version of Fibonacci in Clojure (originally written by Christophe Grand, I believe):

(defn fib []
  (map first (iterate
              (fn [[a b]] [b (+ a b)])
              [0 1])))

This generates an infinite lazy sequence, so you can ask for as much or as little as you like:

(take 10 (fib))
=> (0 1 1 2 3 5 8 13 21 34)

(nth (fib) 1000)
=> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.