Imperative vs. Declarative (2013) | Hacker News Reader

Imperative vs. Declarative (2013)

latentflip.com

72 pointsactraub41 comments

I'd been enough in to these battles so my 2 cents. I'm not saying that declarative mode is bad, in fact I love it, but the problem is that people tend to over do it in undesirable way. I've seen "architects" designing declarative language on top XML and asking programmers to code in it. There are also examples in likes of WPF which is perhaps the ugliest fattiest hairiest thing out there that lot of people have to fight with to get their job done.

1. Declarative languages or constructs are much harder to debug when things are not working as expected. There are no breakpoints to put or no debug statements to write or no watch to put. It was supposed to do that and you just can't tell why it's doing this.

2. Performance issues are much harder to resolve with declarative constructs. When you get in hotspot, there is no way to run. You would be fortunate if your language/platform allows you to fall back to imperative mode but there are platforms/languages out there which insist in 100% declarative styles.

3. There is lot of bad declarative syntax that is not designed to be composable. Lot of time, it's just is not extensible or allows to take advantage of modern programming language constructs such as inheritance, functional patterns, etc.

Can't say it's surprising. The von-Neumann architecture computers and their assembly languages are imperative. Functional programming language structs are just unnatural. Being computationally universal, one can simulate one using the other. But to me, it feels like an unwanted abstraction layer.

Analogy #1: if I were going to write a game for PC, I would directly write a game for PC, not a GBA ROM + GBA emulator for PC and make-believe that it's a PC game.

Analogy #2: if I want to write a novel in Spanish, it will not be possible to achieve the quality of a text written in Spanish from the beginning, by say, writing it in Japanese and using a translator (no matter how much you may like Japanese). Some idioms and culture-dependent things will be lost in translation. (Italian or Portuguese might be better, however)

The von-Neumann level nature of the machine really doesn't enter into it, though. I mean, ultimately, yes, somehow your solution has to be run in an imperative way. At the high level "looking at the declarative solution," though, it is irrelevant.

So, to your analogy #1. If such an emulator already existed and was in wide use, you would not be doing any harm to your system to target it.

To extend your analogy to the absurd, it doesn't make sense to write your program out symbolically in a programming language, because at the end of the day it is electrical values in a processor.

> The von-Neumann level nature of the machine really doesn't enter into it, though.

It does enter when you try to execute the code; which is a translation from declarative to imperative (assembly).

> To extend your analogy to the absurd, it doesn't make sense to write your program out symbolically in a programming language, because at the end of the day it is electrical values in a processor.

Care to tell me one single example of a declarative computer?

I'm more of a hardware engineer than a programmer, and I can't think of any universal logical circuit with memory that is not imperative. Even at the transistor layer, everything is imperative. This includes gate-model quantum computers and biological computers. There are some analog models that work for specific problems, but there certainly are nowhere near being declarative.

And the point was, at the high level, declarative -> imperative translation (which is done by a compiler) will typically be worse that an imperative -> imperative translation.

This is why a very written compute kernels in C outperforms its, say, Haskell equivalent, typically by orders. It's also the reason why scientific computation, signal processing, transcoding software etc. (when raw CPU performance outweighs everything) is typically written in Fortran/C/C++ with a mixture of assembly.

The reason is simple; they map to the underlying hardware well. It is also the reason why assembly languages are imperative.

Apologies, I'm not sure what it is you are trying to say. :(

The fact that the underlying system is von-Neumann seems just completely non sequitor. That is my only point. Every point you make afterwards is just as true of the "Harvard architecture" as it is of the von-Neumann one.

In the rest of what you are saying, it honestly sounds like we agree.

Good points.

To someone not familiar with the practice, I'd say that imperative programming is like manufacturing a car step by step, attaching parts to the engine, building the frame and so on. There are a plethora of tasks involved but it's usually clear how to finish them if you know the principles.

Declarative programming is like finding a magic incantation that makes a car pop into existence. It feels great when the default incantation works and you deliver a finished car in five minutes, but things tend to get confusing quickly if you decide that the car needs a customized transmission, a new row of seats, or (heaven forbid) a different number of wheels. Soon you're poring over arcane texts on GearChangeCommands and CabinPresenters and WheelLocators and potentially spending longer than you would have by just building the car in the slow, predictable way.

That said, I can't help but like the declarative style too, and would still prefer it much of the time to build user interfaces.

All good points. However...

1. Declarative expressions are much easier to spot for defects (and much easier to not introduce defects). So do you want easier interaction w/ your debugger or do you want less bugs?

2. "There is no way to run" is an overstatement, I think. You have to run toward understanding the abstractions you're using. (E.g., if I have GC issues in the JVM, it's not that I have no where to run, it's just that now I have to go understand the GC abstraction.)

3. There is a lot of bad imperative code out there that is just as inflexible to work with.

I can really only cede point one if you qualify it with a "per line of code" or some such. I have seen plenty of "declarative" solutions that are no easier to spot errors in then the much more compact imperative version.

This is the difference between closed form versus summation problems. Sure, short closed form problems are much easier to understand than infinite sums. However, sometimes the closed form is borderline alien compared to the sum.

There are concise declarative solutions in languages such as Ocaml and Haskell.

Depends entirely on what solutions we are talking about.

Show me a nice concise solution to the N-Queens problem in those languages.

Now add performance as a requirement. :)

Here you go!

C (http://rosettacode.org/wiki/N-queens_problem#C)

Program 1 (compiled with gcc -O3 c1.c -o bin/c1)[0]

    real	0m0.003s
    user	0m0.000s
    sys	        0m0.002s

Program 2: (compiled with gcc -O3 c2.c -o bin/c2)[1]

Same as above, second code listing (faster while still readable,excluded unreadable fastest c version)

    real	0m0.001s
    user	0m0.000s
    sys	        0m0.001s

Haskell (http://rosettacode.org/wiki/N-queens_problem#Haskell)

Program 1 (modified to do 8 queens like the c versions, compiled with: ghc -O2 -threaded haskell2.hs -o bin/haskell2)[2]

    real	0m0.010s
    user	0m0.005s
    sys	        0m0.005s

Program 2 (modified to do 8 queens like the c version, compiled with: ghc -O2 -threaded haskell2.hs -o bin/haskell2)[3] (word of warning, this program is only 52% efficient according to ghc and has a lot of optimization that could be done)

    real	0m0.006s
    user	0m0.006s
    sys	        0m0.000s

Note that the fastest Haskell solution was also the shortest by quite a bit. Are you convinced yet?

EDIT: Found an ATS solution, but I'm not setup to compile it: http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?m...

0: C, solution 1

    #include <stdio.h>
    #include <stdlib.h>
 
    int count = 0;
    void solve(int n, int col, int *hist)
    {
    	if (col == n) {
    		printf("\nNo. %d\n-----\n", ++count);
    		for (int i = 0; i < n; i++, putchar('\n'))
    			for (int j = 0; j < n; j++)
    				putchar(j == hist[i] ? 'Q' : ((i + j) & 1) ? ' ' : '.');
     
    		return;
    	}
     
    #	define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)
    	for (int i = 0, j = 0; i < n; i++) {
    		for (j = 0; j < col && !attack(i, j); j++);
    		if (j < col) continue;
     
    		hist[col] = i;
    		solve(n, col + 1, hist);
    	}
    }
     
    int main(int n, char **argv)
    {
    	if (n <= 1 || (n = atoi(argv[1])) <= 0) n = 8;
    	int hist[n];
    	solve(n, 0, hist);
    }

1: c solution 2

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdint.h>
     
    typedef uint32_t uint;
    uint full, *qs, count = 0, nn;
     
    void solve(uint d, uint c, uint l, uint r)
    {
    	uint b, a, *s;
    	if (!d) {
    		count++;
    #if 0
    		printf("\nNo. %d\n===========\n", count);
    		for (a = 0; a < nn; a++, putchar('\n'))
    			for (b = 0; b < nn; b++, putchar(' '))
    				putchar(" -QQ"[((b == qs[a])<<1)|((a + b)&1)]);
    #endif
    		return;
    	}
     
    	a = (c | (l <<= 1) | (r >>= 1)) & full;
    	if (a != full)
    		for (*(s = qs + --d) = 0, b = 1; b <= full; (*s)++, b <<= 1)
    			if (!(b & a)) solve(d, b|c, b|l, b|r);
    }
     
    int main(int n, char **argv)
    {
    	if (n <= 1 || (nn = atoi(argv[1])) <= 0) nn = 8;
     
    	qs = calloc(nn, sizeof(int));
    	full = (1U << nn) - 1;
     
    	solve(nn, 0, 0, 0);
    	printf("\nSolutions: %d\n", count);
    	return 0;
    }

2: Haskell solution 1 (comments stripped out for comparison)

    import           Control.Monad
    import           Data.List
    
    queens :: Int -> [[Int]]
    queens n = map fst $ foldM oneMoreQueen ([],[1..n]) [1..n]  where
      oneMoreQueen (y,d) _ = [(x:y, delete x d) | x <- d, safe x]  where
        safe x = and [x /= c + n && x /= c - n | (n,c) <- zip [1..] y]
    printSolution y = do
         let n = length y
         mapM_ (\x -> putStrLn [if z == x then 'Q' else '.' | z <- [1..n]]) y
         putStrLn ""
    
    main = mapM_ printSolution $ queens 8

3: Haskell solution 2

    import           Control.Monad (foldM)
    import           Data.List     ((\\))
    
    main :: IO ()
    main = mapM_ print $ queens 8
    
    queens :: Int -> [[Int]]
    queens n = foldM f [] [1..n]
        where
          f qs _ = [q:qs | q <- [1..n] \\ qs, q `notDiag` qs]
          q `notDiag` qs = and [abs (q - qi) /= i | (qi,i) <- qs `zip` [1..]]

What is the speed of this on N of 16 to 20? At 8, any implementation should suffice nowdays.

Edit: Also, apologies for the possibly ninja edit. This is ultimately somewhat silly. I am not going to lie and say that the these are easily readable. I fully cede that this could just be a training thing. I picked this particular example because I had fun with it using the DLX algorithm. Which is admittedly far above my understanding in many ways. :) Just the naive recursive solution was much easier to read, but much much slower to execute. To the point that it was laughable. (If interested, I can post my code.)

This example is bizarre, because a fast implementation is probably going to rely on a SAT solver, at which point the "queens code" (in any language) becomes a declarative specification of the solution!

Also, I don't think that Haskell, OCaml, (or Prolog) are that much declarative: They have a very clear evaluation model, which you need to know in order to write any code. They also have debuggers as a result.

That was what my point was supposed to be. Just like saying that "foo.sorted()" is more declarative than looking at the implementation of quicksort. However, the implementation of quicksort (that is actually fast) is much easier to understand in most imperative implementations than it is otherwise.

Regardless, I do apologize for the noise.

> They have a very clear evaluation model, which you need to know in order to write any code.

What programming languages don't require you knowing their evaluation model?

Declarative language on top of XML... Are you talking about this one? http://thedailywtf.com/articles/We-Use-BobX

Oh god, this one hits way too close to home for me.

Or maybe XSLT?

Exercise: are the type systems of functional languages in the vein of Haskell declarative in the sense that is associated with the disadvantages you mention?

Isn't the hallmark of good API design essentially moving from the imperative to the declarative?

We abstract the "how" into declarative statements of "what" and "how many".

Thinking about SQL which I use quite a lot (and the only real declarative programming I do):

1. I would not say that SQL is harder to debug than imperative code. I have also noticed that I get less bugs and they take less time to solve when I push as much as possible to SQL. Usually something either works properly or it doesn't. I personally find SQL is one of the few languages where reading the code is easier than writing it.

2: Database optimizations must be some of the most well known ways to improve performance in the tech field.

3: SQL syntax isn't great (I wouldn't say it is terrible either).

Yes, way too imperative. "map" and "reduce" are imperative; they order something done.

With true declarative forms, you can treat them as data and do something other than execute them. It's hard to do much with an imperative form other than execute it. A scene graph or a game level file is a declarative form; you can view it from different angles and positions. The programs that plan actions for NPCs look at a game level and decide what to do. CAD files are declarative. Spreadsheets are mostly declarative.

The usual problem with declarative forms is lack of expressive power. If you need to express something the declarative form can't handle, it's tempting to bolt on some kind of imperative gimmick. This is how we ended up with Javascript.

> Yes, way too imperative. "map" and "reduce" are imperative; they order something done.

Well how would you write these snippets the right way then?with the language of your choice, so it fits the declaritive way a 100% ?

I'm not saying those things should be written in a declarative form, just that what the author is calling "declarative" isn't.

If you wanted to do something like that in a declarative way, though, consider a spreadsheet with an intelligent evaluator. The spreadsheet is a declaration of a dependency relationship. When a number is changed, the numbers depending upon it change. It's not always just a recalculation, either. There are spreadsheets that let you work backwards (change a total, watch the inputs change), and cloud-based spreadsheets that sync (one of YCombinator's companies, Fivetran, has one).

Spreadsheets also suffer from imperative creep. People try to use Excel spreadsheets for iterative work, which gets away from the declarative design.

Spreadsheets also suffer from imperative creep. People try to use Excel spreadsheets for iterative work, which gets away from the declarative design.

...which is how we ended up with VBA macros.

> If you wanted to do something like that in a declarative way, though, consider a spreadsheet with an intelligent evaluator. The spreadsheet is a declaration of a dependency relationship. When a number is changed, the numbers depending upon it change.

Seems like you're talking about functional reactive programming (or reactive programming in general).

"map" and "reduce" are imperative; they order something done.

Well, in JS, sure, but what about if you could do:

  a = 13
  b = map(function(x){ return x; }, [1, 2, 8, a])
  print b
  >  [1, 2, 8, 13]
  a = 26
  print b
  > [1, 2, 8, 26]

(While I'm representing it as a sequential program, the idea would be to plug "a" and "b" to some IO channels.)

What I'm trying to say is that the concept of map is not necessarily imperative, just JS's version.

> "map" and "reduce" are imperative; they order something done.

So maybe it's my age showing, but I was taught that imperative was using explicit variables to control the "looping" (e.g. for with an index a la C style programming) whereas using "higher order functions" was not imperative. And I tend to agree with that. So I disagree that map and reduce are imperative because they don't explicitly control how the looping is done.

Can anyone cite where map and reduce are imperative? Must be some new-fangled text book that I'm not aware of ;)

And I get that someone could impose on me to cite references that map and reduce are not imperative. Point taken and I'm thinking that I got this from SICP in the first place so I'm looking it up now. Will report back if I find anything.

EDIT: First quote from SICP:

"In contrast to functional programming, programming that makes extensive use of assignment is known as imperative programming. In addition to raising complications about computational models, programs written in imperative style are susceptible to bugs that cannot occur in functionalprograms."

If I may try to answer for Animats, I think the point is that you're still using the map in an imperative way. You set a variable to some list, then you apply a map to that list and assign that to another variable. If you then change the first variable, the latter doesn't change - that means the order of execution matters for the application of the map.

That said, that's mostly a specificity of Javascript than a property of the map operation. There's no reason you can't have a map on an FRP that truly declares a relationship between entities.

I think (perhaps unknowingly) you're just playing a semantic game. By your definition everything is imperative, even if it is also totally declarative. All programs are imperative in your sense. Even if you could tell the computer "Do what I want" and expect it to be psychic, that would still be imperative by your definition.

But the difference between imperative programming and declarative programming is not drawn by "ordering something done" (even if the article didn't define things precisely enough to prevent confusion on this point). It's basically a level-of-abstraction/level-of-detail thing. Saying "double each number in this list" is significantly different than saying "follow this step-by-step algorithm to double each number in the list".

The boundaries can get fuzzy; arguments can be made about where to draw the lines. But your approach lumps everything on one side of the line, and therefore becomes incapable of saying anything very useful.

Hasn't it been fairly well established that imperative and declarative are not necessarily duals? That is, !imperative is not the same as declarative. And vice versa.

That is, the base generalization here is invalid.

Further, there are plenty of things where imperative just makes sense. It is why we have plenty of imperatives in every day usage. I mean, sure, you could tell your kids "I want a clean room." Likely, they will look at you and wonder, if that is what you want, why don't you clean it. :)

So, sure, if there is a nice clean concise declarative way to specify something, do so. However, I think it is a fool's errand to think that can be the universal case. Even in an ideal sense. It is why you don't hear people trying to drop imperatives from daily life. (Or... do you?)

Still waaay too imperative, how about this:

func [1,2,3,4,5] => [2,4,6,8,10] //Calculation inferred by compiler.

console.log (func [6,7,8,9,10]) //=> [12,14,16,18,20]

What algorithms are there for inferring the calculation?

I'm playing around with a tool for building touch gestures visually, and I have some problems that look a bit like that (want to infer a function from some examples) but I don't yet know how.

This calculation is underdetermined, and there isn't any algorithm that would specify "it", since there are many functions that would satisfy the requirements. In general this is a hard problem of induction. In a more limited context you might think about adding regularizations that will make the function better determined. Choosing these and implementing them may not be trivial.

If you are talking paths generated from touch gestures there is some research on that topic.

People working on program synthesis consider the Occam razor "the shortest/simplest code" to be a good heuristic of the intended function (given a good test case.) Their main problem is the exponential space search.

Sounds like a regression problem? The actual algorithm will depend on how well you need to approximate the function, the nature and amount of example data.

http://en.wikipedia.org/wiki/Machine_learning#Approaches

One practical way to implement this would be a “...” operator which would look at the syntax of the surrounding expression and attempt to infer an inductive definition from that, based on some assumptions about e.g. the structure of lists or the values of integers.

    double xs => [xs[0] * 2, ..., xs[xs.length - 1] * 2]

    map f xs => [f(xs[0]), ..., f(xs[xs.length - 1])]

    sum xs => xs[0] + ... + xs[xs.length - 1]

    foldl f z xs => f(f(..., f(z, xs[0])), xs[xs.length - 1])

    foldr f z xs => f(xs[0], f(..., f(xs[xs.length - 1], z)))

Not practical, there are infinitely many functions that could produce such result

here is such psuedo code foo(x) { if (x <= 5) { x * 2 } else { x } } foo1(x) { if (x <= 6) { x * 2 } else { x+1 } } foo1(x) { if (x <= 7) { x * 2 } else { x+2 } }

Awwww, all that an no mention of Prolog or Mecury? Prolog is a declarative language that is being used in the real world and being used often to solve interesting problems too. There is always a joke about how folks tend to reinvent lisp while trying to extend their language. Same can be said for any program that has rules, there is always a half ass prolog engine poorly implemented.

Good Explanation

I disagree, it could be improved: imperative|declarative is not a binary state but a continuous line. For example, you could use foreach instead of for in the imperative solution and the loop would become closer to the declarative one.

Reply on news.ycombinator.com