Are the implementation details of declarative languages inherently imperative

Question

I'm reading 'Functional Programming' by Tomas Petricek & Jon Skeet and I understand the difference between declarative & imperative programming.

What I was wondering is how are the primitive operators & functions implemented, are declarative languages constructed from imperative operators & functions.

Cheers

AWC

Answer 1

If I understand your question correctly, I don't think that is a hard and fast rule. For example, you can use a functional language like Lisp, to create an interpreter for itself. In this case, the implementation details are implemented in a functional manner (because Lisp is a functional language).

Also, if you have a language that is Turing Complete, you can use it to implement a parser/interpreter/compiler for any other language. There are imperative Turing-Complete languages, and functional/declarative Turing-Complete languages.

But all code eventually comes done to assembly or machine code, which is inherently imperative. In theory, what I said above is true, but apparently not in practice :).

As an interesting historical aside, LISP was a completely theoretical construct; it was a mathematical notation for computer languages. It remained theoretical until LISP's eval function was implemented in machine code by Steve Russel on an IBM 704:

According to what reported by Paul Graham in Hackers & Painters, p. 185, McCarthy said: "Steve Russell said, look, why don't I program this eval..., and I said to him, ho, ho, you're confusing theory with practice, this eval is intended for reading, not for computing. But he went ahead and did it. That is, he compiled the eval in my paper into IBM 704 machine code, fixing bug , and then advertised this as a Lisp interpreter, which it certainly was. So at that point Lisp had essentially the form that it has today..." (emphasis mine)

So once again, the subtleties between theory and practice. :)

Answer 2

The low level machine (CPU, assembly language level) is imperative so obviously at some point the implementation will have to take that into account. However, Implementing certain kinds of functional languages like Haskell takes some very non-obvious approaches to create a run-time with decent performance.

Strangely enough, most imperative languages go through a phase where all the code is transformed to be more declarative:

• Single Static Assignment

Here is an example of compiling Scheme (functional) directly to C code (imperative):

• The 90 minute Scheme to C compiler