Is functional programming a subset of imperative programming?

Question

One of the main characteristics of functional programming is the use of side-effectless functions. However, this can be done in an imperative language also. The same is true for recursion and lambda functions (for example C++0x). Therefore I wonder whether imperative programming languages are a superset of functional ones.

Sadness

Interesting question... in imperative programming, you've got more ways to "hang yourself" I believe :-) – Goggler

I agree with your thinking as far as "side-effectless functions" are concerned. A library of "side-effectless functions" can be written and used in both paradigms, while stateful imperative procedures cannot be used in functional programming. – Chalco

Answer 1

Generally speaking, no; functional programming is a subset of declarative programming (which includes logic programming languages, like Prolog). Many imperative languages borrow elements from functional programming languages, but simply having lambdas or referentially-transparent functions does not make an imperative language functional; functional programming is about more than just these elements.

Acree

Really? I've written programs in Prolog and some involved SQL stuff, and I've written purely functional programs. The two didn't seem similar to me. – Viscosity

They're similar in the sense that you're telling the computer what to do (i.e., expressing a computation's logic) rather than how to do it; that's the definition of declarative programming. – Acree

Purely functional languages are, but as impurely functional languages again overlap rather than being a proper subset. – Ible

@Acree from where do you come up that "functional programming is a subset of declarative programming"? – Truckload

@rickmed: From the definition of declarative programming. – Acree

Answer 2

I can't really say whether they are subset of one another. What I can tell, though, that (except for really esoteric languages) they are all Turing-complete, which means that in the end they're all equally powerful, but not neccesarily equally expressive.

Azpurua

So true... I wish I had more than a +1. – Goggler

Stephen Wolfram would say "capable of Universal Computation" or something of like. – Goggler

Answer 3

It is possible to implement a certain programming paradigm in a language which doesn't support the programming paradigm natively. For example its possible to write Object Oriented Code in C while it is not designed for this purpose.

Functional programming is a well developed programming paradigm of its own and is best learnt through languages like Haskell, LISP etc. And after you have learnt them well, even though you don't use these languages regularly, you may start using those principles in the day to day language you use on regular basis.

Some people may like to Google for Object oriented programming in C

Jestude

What you said about C makes no sense except in the most trivial that you can have an "object". What is the meaning of OOP without polymorphism and inheritance? – Irairacund

you can implement your own vtables in c if you wish – Equities

It's certainly possible to write object-oriented code in C; we did it on a project back in the late '80s, working on OS/2 where there were no OO languages. It did require a large (and slightly insane) set of macros to implement polymorphism and inheritance, but it worked. – Compossible

My understanding is that a standard C compiler can compile Objective-C code. Objective-C compilation can be either done natively (i.e. built in support in the compiler), or using a set of macros which translate the OO constructs into standard C - in this case, Objective-C is an object orientented language implemented as a layer on a non-OO language. Given this (and I'm sure there are other examples) IMO what he said about C does make sense – Iluminadailwain

And you could write an interpreter or compiler for an OO language in C. Often done as an exercise at universities. – Protoactinium

Yes, but to be fair to the poster, "writing object-oriented code in C" is different from "writing a compiler for an object-oriented language in C". – Acree

I once did a little work on a framework that did object-oriented C. It left me with the feeling that it was possible, but not a good idea. – Viscosity

Answer 4

A paradigm is a way of doing things, and there are two main programming paradigms: imperative and declarative. The fact that some languages allow to mix both paradigms doesn't mean that one is included in the other, but that the languages are multi-paradigm.

To clarify it a little bit more, let me continue with your analogy: if Lisp and OCaml (for example) are considered functional languages, and both of them allow imperative style... then should imperative be considered a subset of functional?

Mantissa

Lisp (Common Lisp, specifically) is usually referred to as a multi-paradigm language. You can write imperative as well as functional code with relative ease. – Soubise

Lisp is referred as multi-paradigm exactly as much as C++ is. Purists will say they're multi paradigm (and they're right), but in common usage they usually referred as functional and imperative/object oriented respectively. Anyway, my point was that if you can do both paradigms, the language is multi paradigm, so the question of the op was wrongly stated from the beginning. – Mantissa

Answer 5

Most imperative languages don't have functions as first-order types, whereas most functionald o. (As does C++, via boost::function.)

By first-order type, this meas a value/variable can be of any type, an int, a bool, a function from int->bool. It usually also includes closures or bound values as well, where you have the same function, but some arguments are already filled in.

Those two are what functional programming is mostly about, IMHO.

Caaba

Answer 6

I think it might be helpful to draw a distinction between paradigm and language.

To me, paradigms represent "ways of thinking" (concepts and abstractions such as functions, objects, recursion), whereas languages offer "ways of doing" (syntax, variables, evaluations).

All true programming languages are equivalent in the sense that they are Turing-complete and able, in theory, to compute any Turing-computable function as well as simulate or be simulated by a universal Turing machine.

The interesting thing is how difficult it is to accomplish certain tasks in certain languages or paradigms, how appropriate the tool is to the task. Even Conway's Game of Life is Turing-complete, but that does not make me want to program with it.

Many languages support a number of paradigms. C++ was designed as an object-oriented extension for C, but it is possible to write purely procedural code in it.

Some languages borrow/acquire features from other languages or paradigms over time (just look at the evolution of Java).

A few languages, like Common Lisp, are impressively multi-paradigm languages. It is possible to write code that is functional, object oriented or procedural in Lisp. Arguably, aspect-orientation is already part of the common lisp object system, and therefore "nothing special". In Lisp, it is easy to extend the language itself to do whatever you need it to do, thus it is sometimes called the "programmable programming language". (I'll point out here that Lisp describes a family of languages of which Common Lisp is only one dialect).

I think it doesn't matter which of the terms, declarative, imperative, functional or procedural, is a subset of which. What matters more is to understand the tools languages you're working with, and how those are different from other tools. Even more important is to understand the different ways of thinking that the paradigms represent, since those are your thought-tools. As with most other things in life, the more you understand, the more effective you become.

Katzenjammer

"it doesn't matter which of the terms is a subset of which": Part of the reason why I asked this was because I like some of the concepts of functional programming, but I don't like its limitations, such as the notoriously difficult way of dealing with I/O and the extensive use of recursion. – Sadness

Since when is recursion a limitation? Loops and recursion are two sides of the same coin, but one is often more appropriate than the other. Functional programming is a paradigm, the specific language (its syntax and its libraries) determines "how hard" it is to things like I/O or looping. Your use of the word "notorious" would suggest you haven't taken a good look for yourself. Please do - I found I/O quite "hard" to grasp in Java 2, but I was using only the Javadocs to figure it out. Pick a language that seems "friendly" to you and start reading about it. – Katzenjammer

Answer 7

One way to look at it (not saying it's the right way 'cos I'm not a lang designer or theorist by any means) is that if the language is essentially converted to something else then that 'something else' must be the superset of the source. So bytecode is necessarily a superset of Java. .NET IL is a superset of C# and of F#. The functional constructs in C# (i.e. LINQ) are thus a subset of the imperative constructs of IL.

Since machine language is imperative, you could take the position that, therefore, all languages are imperative, because they are just abstractions useful for humans that are then boiled away by the compiler to procedural, imperative machine code.

Conveyancer

+1 Nice remark! I'd like to upvote, but it doesn't work ("vote too old to be changed"). Sorry :( – Sadness

Answer 8

Pattern mapping like

f:: [int] -> int
f [] = 0
f (x:xs) = 1 + f(xs)

is something that is for instance one thing that is not available in imperative languages. Also constructs like curried functions:

add2 :: int -> int
add2 = (2 +)

is not available in most imperative languages

Meilhac

Currying can be done in C++ using templates: #152505 – Sadness

Answer 9

Yes, functional programming is a subset of imperative programming, but...

Yes, because there is nothing in functional programming that you can't do in imperative programming (syntax differences notwithstanding). You can "do" functional programming in an imperative language.

But... The things you can't do are the key features of functional programming. By limiting what you can do,

1. you make certain mistakes impossible,
2. you enable features (such as program analysis, simpler concurrency, simpler testing, etc).

Other benefits of functional programming are more subjective. You often hear these arguments.

3. State allows side effects. Side effects are bad. Functional programming has no state. You can't have side effects without state.

This is a dubious benefit. First, only unintended side effects are bad. Proper programming practices, such as limiting modification of state to privileged code, alleviate side effect issues. Second, functional programming only has no internal state. If the program has IO (accessing files, network, hardware) you have external state, thus the potential of side effects.

4. Functional programs are easier to debug.

In some ways yes, like knowing the explicit path to an exception. But having state to examine is a debugging benefit that functional programming does not have.

5. Functional programs are easier to understand.

This is only true if you are fluent in functional programming and not fluent in imperative programming. I for one, being more fluent in imperative programming, find this argument to be false.

Dresden