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?

Sridhar Ratnakumar
  • 81,433
  • 63
  • 146
  • 187
Cedric Martin
  • 5,945
  • 4
  • 34
  • 66
  • I'm not sure I understand the question; the *canonical* implementations of algorithms in Lisps is almost always recursive and "bottom-up". – Dave Newton Oct 19 '11 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.) – Cedric Martin Oct 19 '11 at 16:45
  • 3
    What makes you think that you can't do this in Lisp? – Rainer Joswig Oct 19 '11 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. – j_random_hacker Oct 20 '11 at 05:10
  • @j_random_hacker: I'm thinking of Common Lisp, Scheme and also Clojure (which has tail recursion and even a *recur* construct) as functional languages. I'm not sure that I buy the *"it's still just an imperative language with mutable state"*. This is not how Rich Hickley (Clojure's creator) would best describe Clojure, for example. I've actually hardly seen anyone (besides you) describe Common Lisp, Scheme and Clojure (to name some) as *"imperative language with mutable state"* [sic]. Is Haskell (not a Lisp, I know) not functional because it can access the network and write to files? – Cedric Martin Oct 22 '11 at 19:35
  • @j_random_hacker: I guess I could answer your question this way: *"Am I wrong in seeing Lisp as a functional language even though once in a while you can 'bend the rules' and do funny stuff like modifying an array"*? – Cedric Martin Oct 22 '11 at 19:38
  • 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 Oct 23 '11 at 08:36
  • @Cedric: I'm not familiar with Clojure at all, and I know only the very basics of Common Lisp and Scheme, but I've played around with Haskell a bit. Although Haskell permits mutable state (as it obviously must to be useful!), every Haskell function that manipulates state is obliged to advertise this fact by returning a value "wrapped" in a monadic type (usually the `IO` monad for "real world" state like key presses and network packets). So, in Haskell you always *know* when you're calling an impure function just from looking at its type. That's not the case in languages like CL, Scheme, or C. – j_random_hacker Oct 23 '11 at 12:38
  • @Cedric: I realise there are other possible criteria for deciding whether a language can be considered functional (e.g. support for TCO, or closures), but I think the criterion I'm proposing here ("Purity/impurity is encoded in the function's type") is useful because it directly addresses the main concern of all those who advocate FP over imperative programming -- namely, to force all code that accesses or changes state to be *deliberate* and *visible*. (BTW, if closures/first-class functions is your preferred criterion, then Perl is a functional language :) ) – j_random_hacker Oct 23 '11 at 12:49
  • @j_random_hacker: thanks for these infos... I read a bit about Haskell and is certainly looks like one of the most functional language out there. I've been particularly impressed with an example where the typesystem was so strong that the compiler (?) could detect errors that I've never seen any other language be able to detect (if was refusing to compile or something explaining that the user probably forget to deal with the case where some list only had one element or something, it was really impressive). I'll try to read more on that fascinating subject : ) – Cedric Martin Oct 23 '11 at 20:01
  • @Cedric: Haskell certainly has a powerful type system that will catch a lot of errors at compile time. Though I was surprised to find that (unlike e.g. C++) you can't parameterise types by numbers, so you can't do things like define a matrix multiply function that enforces that arg #1's width == arg #2's height at compile time. Also I eventually decided that reasoning about laziness in a nontrivial program was too hard. But it may be just what you want :) – j_random_hacker Oct 24 '11 at 04:31

4 Answers4

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.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • +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? – Cedric Martin Oct 19 '11 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 Oct 19 '11 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)))`. – Matthias Benkard Oct 19 '11 at 18:15
  • 2
    (Plus, if you really do a lot of array processing, you can always write a reader macro. :)) – Matthias Benkard Oct 19 '11 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.

Arthur Ulfeldt
  • 90,827
  • 27
  • 201
  • 284
  • *this is not very idomatic Clojure because it combines the looping with the work to be done* -- can you expand on this? – edoloughlin Oct 20 '11 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. – edoloughlin Oct 21 '11 at 10:13
  • One small question: in your last line above [`(take-while`...], where does `current-row` get its value? – edoloughlin Oct 21 '11 at 10:20
  • nowhere, you have revealed my dirty little secret! I posted this without testing! shame shame – Arthur Ulfeldt Oct 22 '11 at 01: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.

John Clements
  • 16,895
  • 3
  • 37
  • 52
  • 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"*. – Cedric Martin Oct 19 '11 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 Oct 19 '11 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). – Cedric Martin Oct 19 '11 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: http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming – wkl Oct 19 '11 at 17:13
  • Ah, excuse me, I had the article "Memoization" in front of me instead of "Dynamic programming". – Fred Foo Oct 19 '11 at 17:14
  • @CedricMartin: no idempotent method calls? what about the array references? – John Clements Oct 20 '11 at 03:55
  • Fooey, can't edit my prior comment. I was in the middle of saying: @CedricMartin: I'm afraid you're going to think of me as a pointy-headed functional programmer, but the difference you're pointing out is in my view pretty much nonexistent. To wit: take the body of the loop, make it a function of its own that takes two arguments, and turn on memoization. Voila! By the same token, you can translate a memoized solution into one that uses an array in the same way, you just need to be a bit more careful about the array bounds. – John Clements Oct 20 '11 at 04:03
  • 1
    @John Clements: no problem being pointy ; ) Here http://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. – Cedric Martin Oct 20 '11 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
Justin Kramer
  • 3,983
  • 1
  • 23
  • 23