Saturday, March 3, 2012

One man’s Declarative is another man’s Imperative

Its just like the corporate pyramid.

One man’s what is another man’s how.  One man is the employer and the other the employee.  And that employee may himself manage employees; he takes that ‘how’ and it becomes his ‘what’ when he tells his subordinates what to do.  And so on cascading down until someone actually does it, and then its definitely finally ‘how’.

What’s “declarative" programming?  Mostly, its defined as in what its not - "imperative" ;)

That’s exactly why I don’t feel easy with the ‘declarative’ vs ‘imperative’ language labels.

Of course the declarative programming crowd have had a long time to think about what declarative may mean.  Gone are the days of citing SQL or Prolog; these days its probably a discussion about deforestation and side-effects or just fuzzy purity.

I feel a lot more comfortable thinking about what vs how.

What I read SQL, I’m reading it as how.  I am thinking about sorted lists and sets and such; I’m putting myself in the mind of the database query planner.  I’ve even played with coarse query planning i.e. reordering of a sort myself.  And when I have to tweak my SQL because the query planner isn’t clever enough, I feel disappointment.

Is C declarative or imperative?  The language - any programming language - is just a contract; a description of what to do; the compiler decides how.

The first C compilers might have been fairly literal ‘high level assemblers’ but these days you’ll likely be surprised (or disappointed) when you see the cunning reordering and shortcuts and optimisations that your normal tame C compiler does.

And the machine code it emits is most unlikely to be taken literally on the processor level.  The x86 processors are all superscalar i.e. reordering monsters and they work on an internal proprietary instruction set called microcode too.  Everyone remember how literal machine code worked in practice, right?  In a sense, the compiled C code is a what not a how.  All this comes to the ARM processors on your phone soon too.  Volatile and barriers?  Just more constraints.  Still what not how.

I’ve thought a lot about sufficiently smart compilers ;)  When I look at the code that restricted Python compilers generate I get a dangerous itch to waste a lot of free time trying to improve it.

Take your innocent for(std::vector::iterator i=v.begin(); i!=v.end(); i++) {...}  If you look into the body you can often determine that side-effects do or don’t (or can and can’t) make the iteration order important.  You can determine that whilst it says do it in order, this is not a affecting the outcome.  You’d know if you could do it in any order.  Although the programmer has specified an iteration order, the compiler can often determine that that constraint is irrelevant.  Imagine a compiler that can see that max(vector)-min(vector) can actually be done in a single pass of vector?

When you write something imperatively, it is just a rephrasing away from something someone would call functional, and they are just alternative phrasings of something unambiguously equivalent.

The programmer is the employer, and the compiler and microcode programmer his employees.


  1. williamedwardscoder posted this

 ↓ click the "share" button below!