Is it possible to use functional paradigm in imperative languages?

Question

If I understand the concept correctly the goal, which functional languages are trying to achieve is to eliminate any side effects from functions and to eliminate a state. The rationale behind this is to obtain referential transparency, which leads to more predictable execution.

However, nothing prevents me from writing the code with above in mind in imperative language. I'm thinking only about classic constructs and not functional mixins.

Let's say I have following code in C.

int add(int x, int y) {
    return x + y;
}

int sqr(int x)
{
    return x*x;
}

int main()
{
    return sqr(add(3,5));
}

So, I have two functions, which do not posses any side effects. Neither program has any state. Is this code missing something exceptionally functional?

Currently, I perceive functional languages like if they had built impressive decoration made of syntactic sugar over the core concept of functional programming. Their syntax discourages slicing the code into statements, however I don't see any substantial difference that prevents me to take functional approach (and yield its fruits) in imperative language. Am I wrong? Hence my question.

Answer 1

It is certainly possible to program in a purely functional style in an imperative language. In fact, if you look at books like Effective Java or Java Concurrency in Practice, much of the advice in those books basically boils down to "don't use mutable state", "don't use side-effects", etc.

However, it may not always be a pleasant experience, and you may not be able to do everything you want to do.

You mentioned C specifically as an example. Unless I'm missing something, the purely functional subset of C is not Turing-complete, because there is no way to express iteration. C does not have Proper Tail Calls, so, you will eventually overflow the stack when trying to express something like iterating over an infinite list. You will need to use a loop for iteration, but loops rely on mutable state and side-effects.

Of course, the standard Turing-tarpit argument applies … you can do functional programming C by implementing a Haskell interpreter in C and then program in Haskell. But that's not how I interpret the OP's question.

Answer 2

If by functional programming you mean programming only with immutable values, sure, you can do that. But it's going to be painful. In a lot of cases you don't get to take advantage of:

• First-class functions with lexical scoping (a.k.a. closures)
• Functions with identifiers that are mostly special characters
• Infix functions
• Type inference
• Tail call optimizations (so no recursion as a form of looping unless you're fine with stack overflows, which means you have to use looping statements, which means you need to mutate something to get results out of a loop)
• Automatic currying
• if/else and try expressions instead of statements.
• Algebraic data types
• Pattern matching
• Not having to deal with null
• Persistent data structures (usually need to pull in external libraries for these if they're available at all)
• Advanced module systems
• Lazy evaluation (though this can be simulated using lambda expressions)

And of course a compiler for a functional language will have different optimizations than a compiler for an imperative language. A language where functions aren't a primitive type is unlikely to optimize function composition or currying as well as a language where functions are primitives and it's expected that they'll be composed and curried often.

Answer 3

I'm not an absolute expert on functional languages and paradigms; however, I do know that compilers have the job of translating their native language (C, Ada, Prolog, Java…) to a machine language (x86, JVM, sparc, amd64…). Since both functional and imperative languages can be translated to machine code, given that they are both Turing-complete and not domain specific; it follows that they can be translated to each other. So, I would think yes.

Answer 4

I'm learning Scala right now, and it allows for both. You can either write imperatively using standard curly braces like C, or you can omit the braces and write functionally. Obviously the functions you use decide whether or not you'll be able to write it purely functionally, but it is possible.

If I think of a good comparative example, I'll edit it in when I get on my laptop.

Answer 5

[...] however I don't see any substantial difference that prevents me to take functional approach (and yield its fruits) in imperative language.

My pragmatic sort of way of trying to enjoy some of those "fruits" in languages like C and C++ is not to go all out functional. It's very, very relaxed. I'm not trying to write higher-order functions all over the place or utilize closures or avoid imperative loops and local counter variables or anything like that. I'm not trying to fight these languages much. Of course there are some cases where lambdas and higher-order functions make a natural fit in certain generic C++ algorithms (including examples from the standard lib), and I do use them when they seem to flow off the fingertips that way, but I'm not trying to force a functional style in such languages so much.

Mostly I'm just trying to eliminate external side effects or, for those who feel the need to point out that real-world programs often need side effects (and sometimes a complex series of them), to centralize side effects to the fewest number of places. I try to move the external side effects towards the "bottom of a thread's call stack" which is a very crude way of describing/thinking about it but I find it practical for my purposes.

And the most practical benefit I've found of favoring that besides finding more opportunities for parallelization and having an easier time reasoning about thread safety and so forth is that I'm not being nearly as overwhelmed by the complexities of my and other's creations. It's allowing me to focus on larger-scale design concerns without feeling like my brain is on the brink of exploding from repeatedly being forced to comprehend so many details. It was one of the major missing puzzle pieces I was missing to prevent me from having to x-ray the abstractions we built to make sense of what was going on.

Because when we have a complex series of function calls or method calls between objects, and many of them have external side effects (to member variables, to parameters passed into the function, or maybe even globals, yuck, etc), then inevitably I find cases (the most glaringly obvious when things bug out and escape our tests, but also when we're trying to make changes or sandwich new functionality inside the system) where I have to try to drill deep and piece everything together to make sense of what is happening to the relevant external (ex: application) state. When a similar series of calls only input and output data without something else on the side being mutated, I find there's so much less information my brain needs to track, as well as just finding (when combined with sound testing procedure) far less mistakes flying under radar.

That said, again I am very relaxed about this. I'm okay if we do something like this:

// 'some_mesh' is passed by value (copied, not passed by ref/pointer)
static Mesh modify_mesh(Mesh some_mesh)
{
     // Transform some_mesh using imperative statements.
     ...

     // Output new, modified mesh.
     return some_mesh;
}

I'm okay with that sort of thing since some_mesh is just a local to this modify_mesh function, not being passed around and mutated elsewhere, and the function has no external side effects and has referential transparency. Maybe it calls some mutating methods like add_triangles or whatever which causes side effects/mutations to that local mesh object. I'm okay with that, as long as we're not passing this mesh around 20 levels deep in the call stack and mutating it while I'm overwhelmed trying to keep track of what's going on to it and in what precise order.

And I've actually built some persistent data structures with atomic ref-counting, immutable interfaces, builders, things of this sort, for the heftier stuff that would be very expensive to copy around and the things that I would particularly prefer the software is not mutating across a series of function calls and across threads (my central application scene which stores everything is immutable now, and the only thing operations can do is output new scenes for wholesale replacement, not mutate the existing one). But mostly it's very relaxed as you can hopefully see. I'm just trying to reduce the amount of information my brain has to keep track of, because my whole goal is to avoid this:

“The computing scientist’s main challenge is not to get confused by the complexities of his own making.” -- ― Edsger W. Dijkstra

... as we build larger and larger scale software.

As a side bonus I have also found a whole lot more opportunities to multithread things. I would have never thought in the past to even consider running physics in parallel with real-time rendering, for example, since I thought of physics as mutating a central scene and rendering as wanting to read from it at the same time in ways where locking might be more expensive than just using threads to make them individually finish faster. Now physics doesn't modify a central scene. It inputs one and outputs a new one, and it can devote a thread doing that as fast as it can, while the renderer inputs a scene, keeps a lightweight copy (since the scene is a PDS), and renders it, and it can do that as fast as it can in its own thread. Before I would have tried to use multiple threads to parallelize loops and so forth in a sequential pipeline to make all of this stuff finish faster (ex: making the physics finish faster with parallel loops while the renderer then renders it in the same thread after it's finished), but running these things in parallel without a care in the world has not only simplified the resulting code, but translated to much smoother and faster and consistent frame rates for users. But that's a side bonus -- I mostly sought out the mitigation of side effects mainly to help comprehend the system as a whole and achieve a greater sense of clarity.

On top of that exception-safety and error-handling is a no-brainer now. Before when external side effects, especially to persistent application state, was involved, the most complex part of recovering from an exception was rolling back those side effects. Now there aren't any such side effects in the vast majority of the functions in the system. If something throws there's nothing to roll back. The undo/redo system is also now ridiculously simple since it's just copying the entire scene (which doesn't take much memory at all since it's a PDS). Non-destructive editing is a piece of cake. Etc. etc. etc.