loading...

Why I love learning functional programming

Kimmo Sääskilahti on August 01, 2020

This is the first part of a series on my journey in learning functional programming (FP). In this first part, I'd like to share why I spend time on... [Read Full]
markdown guide
 

Why do you consider this to be declarative?

const double = (arr) => 
    arr.filter(v => v % 2 === 0).map(v => v*v);

It looks very much like chained imperative operations to me. :)

Although generally speaking I agree with the drift of what you're saying.

The key quality of functions is that they are time-invariant relationships, which is why there are no effects to track.

Keeping track of effects gets increasingly expensive as the scope of effects increases.

Which is why writing in an algorithmic style can be a good middle-ground -- an algorithm is a procedure implementing a function.

Within an algorithm you can have whatever effects you find convenient, but since it implements a function, the scope of those effects is limited to the body of the procedure, meaning that the cost of proving global correctness does not increase.

Once you understand this, it's should be clear that the rest is just syntax, and you should pick the syntax that's most convenient for the use-case, rather than taking an ideological stance. :)

 

It looks very much like chained imperative operations to me. :)

That code is essentially piping the result of the previous computation into the next function. As Kimmo said, it doesn't modify any state, it's pure, and each function creates a new list that is returned from each function. All functions used in the example are pure. While the dot-syntax looks imperative, it follows the principles of FP in this case.

Here is the exact same code written in F#, but using the pipe instead of dot. It works the same way a pipe in Bash does, takes the result of the previous calculation and passes it to the next. The only real change I made from JS to F# was that I replaced the dots with pipes.

let double arr = 
  arr 
  |> filter (fun v -> v % 2 = 0) 
  |> map (fun v -> v * v)

(The pipes can be all on the same line, like the dots, I just formatted it to be easier to read)

So dot-syntax used correctly can be used to write functional code. As long as the higher order function here is pure and the dot-function itself is pure and returns a new instance of the data.

 

What does expressing an eagerly evaluated imperative operation in a functional style have to do with being declarative programming?

Maybe you should look up a quick definition of declarative programming.

The difference between imperative and declarative is not in the operations you use but in the constructs. The example is declarative rather than imperative because the logic is expressed without an explicit control flow.

a.b(c).d(e) has no explicit flow control?

What an interesting idea ...

It looks very explicitly defined by the semantics of ecmascript to me.

But perhaps I'm missing something -- could you explain more about how a.b(c).d(e), etc, has no explicit flow control?

Certainly. If we oversimplify it, in computer science control flow refers to statements such as ifs or fors.

As you can see, in a.b(c).d(e) there are no such statements. So there is no explicit imperative structure to control the flow of execution. There is only one execution branch explicitly stated.

By contrast, something like the following code would have explicit control flow:


if (a) {
  for (let i = 0; i < 12; i++) b(i)
} else {
  switch (c) {
    case 2:
      d(e)
      break;
    ...
  }
}

As you can see, the difference is that there are control flow starements to control the flow of execution. If you look at Wikipedia's page for control flow it even lists the control flow structures that exist.

Let us note that a.b(c).d(e) is a chain of explicit procedure calls.

Are you saying that procedures calls don't affect flow control?

This is a novel concept to me, and I look forward to reading your explanation of how this works. :)

Are you saying that procedures calls don't affect flow control?

No, I'm saying that list.filter(isEven).map(double) has no explicit control flow statements. The key here is the difference between implicit and explicit.

If you want to use the expression "control flow" in a different way than the standard definition in CS, be my guest. Just don't get surprised that everyone else means something different.

Also, a.b(c).d(e) is nothing but a bunch of letters and punctuation marks. Discussing whether that's declarative or not is like discussing whether a = 12 is declarative. The example was using filter with a predicate and map rather than using explicit control flow statements. If you want to talk code, give me a real example. a.b(c).d(e) could just be anything in any context, so there's little point in discussing that.

Let's start with list.filter(isEven).

In javascript, this is not a bunch of letters and punctuation marks, it is a method invocation.

Now, let's take a look at the Wikipedia page you referred to on flow control.

Subroutine
The terminology for subroutines varies; they may alternatively be known as routines, procedures, functions (especially if they return results) or methods (especially if they belong to classes or type classes).

Unsurprisingly, method calls are included as flow control operations.

This is unsurprising, since method calls transfer flow control to somewhere else -- the method being called.

So, list.filter(isEven) is an explicit flow control operation.

Now, if we can agree on that basic point, I suggest you go back and re-read what I've written so far, with that understanding in mind.

I have actually re-read everything you've written so far, and I'm starting to wonder if we're even talking about the same sort of stuff. So perhaps you might explain what you understand as declarative programming?

As a response to your previous comment, my take is this: list.filter(isEven).map(double) does not have an explicit description of its control flow. A runtime or compiler might run them one after the other or might lump them together in one iteration. It can do that because the construct itself is not describing step by step how the code should be evaluated. It is just describing what should happen to the data. The specifics of how (e.g. one iteration over the list or two) are left to the language's implementation. A piece of code doesn't become imperative programming, simply because there is one single primitive, especially when said primitive is a subroutine.

Also, this is an aside and not that important, but it's control flow, not flow control. Flow control refers to the management of data transmission rate between a sender and a receiver.

Then your conclusion is that wrapping anything in a procedure makes it declarative, making declarative code equivalent to procedural abstraction.

Being able to rearrange how list.filter(isEven).map(double) executes doesn't mean that the control flow is not explicit.

Let's rephrase your argument to be about for loops, and see that it holds true to the same degree.

"A for loop does not have an explicit description of its control flow. A runtime or compiler might run them one after the other or might lump them together in one iteration. It can do that because the construct itself is not describing step by step how the code should be evaluated. It is just describing what should happen to the data."

This claim is incorrect for a couple of reasons.

  1. If we understand the effects of a piece of code, regardless of how it is expressed, we can replace that piece of code with another piece of code which has the same effects. This is the basis of optimizing compilation.

  2. In javascript, list.filter(isEven).map(double) describes method calls. It is describing step by step how the code should be evaluated. It is not making declarations about how the data should be changed. In some other language this might not be the case, but we're talking about javascript.

"A piece of code doesn't become imperative programming, simply because there is one single primitive, especially when said primitive is a subroutine."

Perhaps not, but your argument hinges on "explicit control flow operations", which clearly include procedure calls.

Is your claim that "a piece of code becomes declarative, simply because it is wrapped in a procedure"? :)

Regarding flow control -- we were talking of transfer of control over the control flow, control flow is a flow, and so we can refer to this as flow control -- English is flexible, and writing out control flow control is awkward.

No, sorry, you can't change my argument and then make a rebuttal for that. That is called a strawman and is not an honest way to engage in a discussion.

 

Thanks for your comment!

Why do you consider this to be declarative?

I find it declarative because it expresses the intent of the computation instead of listing the explicit statements how to achieve the result of the computation. For example, it's not specified if the computation should proceed from left to right, if the array should be traversed in-order and if it should be traversed once or twice, or even if the computation is done in parallel or not. That's all meaningless for the declared intent.

Within an algorithm you can have whatever effects you find convenient, but since it implements a function, the scope of those effects is limited to the body of the procedure, meaning that the cost of proving global correctness does not increase.

This is a good point. With "implicit side effects", I meant functions shouldn't generally have observable side effects that are hidden from the caller. The function is allowed to do whatever it wants internally, as long as the side effects aren't observable.

Once you understand this, it's should be clear that the rest is just syntax, and you should pick the syntax that's most convenient for the use-case, rather than taking an ideological stance. :)

My number one goal for this post was to make it clear I don't have any ideological stance in any direction, so I sure hope it didn't come out looking like that! I explicitly said that one style of programming isn't better than the other and that functional programming even isn't the opposite of imperative programming. But I do think that functional programming does make the declarative style more attractive and, personally, I find declarative style easier to deal with.

 

If that's your definition of declarative, any layer of abstraction will suffice.

Are the following declarative?
They look like imperative procedure calls to me.

foo(a);
a.foo();
a.foo(b).bar(c);

Good question! I wouldn't call those declarative, because they modify state, or at least they don't return anything. I would also expect the function names to convey some intent that's understandable in the context of the program.

As long as we don't have a clear definition of declarative programming that we both agree on, I don't think we'll reach agreement of what code should be called declarative and what imperative. Maybe that's not that even so important in practice, to me it's most important that code is easy to read and understand and it has zero surprises.

Imperative code feels, though, easier to recognize when I see it 😊

Well, it's more that you don't seem to have a coherent definition for declarative programming. :)

It seems to be:

  1. Doesn't modify state.
  2. Returns things.
  3. Has meaningful names.
  4. Rejects a.foo(b).bar(c), but accepts a.map(b).reduce(c).

Whereas I recognize declarative programming as programming by making declarations about a universe and then reasoning about these declarations.

For example.

mother_child(trude, sally).

father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).

sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).

parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

Allows us to test the claim

 ?- sibling(sally, erica).

This is what I understand declarative programming to be about -- making and testing declarations.

I think that perhaps you need to work on a more coherent definition for 'declarative programming' for yourself, since it doesn't seem coherent, so far.

Thanks for the comment! It's indeed true I don't have a coherent definition of declarative programming. To me, this SO post suggests that it's really hard to define declarative programming in a coherent manner that everyone can agree on. I like this answer though, it's maybe not rigorous but seems useful to me. As for imperative programming, Functional Programming in Scala describes it as "programming with statements that modify some program state". That's also something that's quite easy to grasp.

But to be honest, I don't think it really matters what the exact definition is or which blocks of code are imperative and which declarative. Like I said, functional programs can be written in imperative style and that's fine.

Having a coherent understanding of the terms you use is important.

Otherwise how do you know what you are saying, if anything? :)

Personally, what I understand is the following.

  1. Imperative expressed as instructions to an agent.
  2. Declarative expressed as declarations about the universe.
  3. Procedural is in the form of operations that occur over time.
  4. Functional is in the form of relationships that are invariant over time.

And this gives me a coherent basis for discussion. :)

While you may not agree with these, I advise trying to make your definitions coherent.

Hi @pentacular , your definition sounds more like Prolog to me!

Thanks for your comment, I'll definitely try and make my definitions coherent! Have a nice day!

@johnkazer , well, prolog is the classic declarative programming language -- so that's unsurprising.

Rejects a.foo(b).bar(c), but accepts a.map(b).reduce(c).

Kimmo explained perfectly why a.foo(b).bar(c) may not be declarative.

Good question! I wouldn't call those declarative, because they modify state, or at least they don't return anything. I would also expect the function names to convey some intent that's understandable in the context of the program.

You presented it in a context where either the return value is ignored or there was no return value. If there was no return value then there has to be a side effect, which makes it not pure declarative code. If all functions in your example are pure and you ignore the return value then it's all declarative code, but it's also useless since the return value is the only thing you get out of it.

The Wikipedia page for Declarative Programming states that any code that has side effects is procedural.

I believe the reason Kimmo brought up the function names is that they may convey if the function has side effects or not, like map and reduce,

Sure, my point is that if a.foo(b).bar(c) isn't declarative, then it's difficult for a.map(b).reduce(c) to be declarative -- they're the same kind of expression.

a.map(b) and a.reduce(c) may have side-effects.

Does this mean that you're saying that a.map(b).reduce(c) is sometimes declarative and sometimes not declarative?

Any code that has effects is procedural, side-effects is a sub-set of effects. :)

But I'm not sure why that's relevant to being declarative.

Are you making a claim along the lines that imperative function application is declarative, and so functional programming is the same as declarative programming?

That would seem incoherent, so I'd think carefully about it. :)

I was going by the definition from Wikipedia that declarative code is referentially transparent, ie. no side effects.

I'm not familiar with just the term "effect", but this is side effects according to me:

Example side effects include modifying a non-local variable, modifying a static local variable, modifying a mutable argument passed by reference, performing I/O or calling other side-effect functions. - Side effect - Wikipedia

Does this mean that you're saying that a.map(b).reduce(c) is sometimes declarative and sometimes not declarative?

According to the above definitions, then yes. As ridiculous as that may sound.

Are you making a claim along the lines that imperative function application is declarative, and so functional programming is the same as declarative programming?

Functional programming is a subcategory of declarative programming. Logic programming, like your Prolog, is also a subcategory of declarative programming.

I'm not even sure about what you mean by "imperative function application". What makes a function application imperative?

A side-effect is an effect that escapes the local function.

An effect is a change that occurs over time.

I'm glad that you realize that it is ridiculous. :)

The reason it's ridiculous is that you're conflating functional and declarative.

Let's consider two function expressions -- one declarative and one imperative.

  1. "In this world it is raining."
  2. "Find me a world where it is raining."

Declarative programming is where the program is expressed in terms of declarations (and need not be functional -- consider that the classic declarative programming language, prolog, is not functional due to things like the cut operator).

Imperative programming is where the program is expressed in terms of instructions (which include applications, such as function applications), and these can be purely functional applications.

What it comes down to is that imperative / declarative is a matter of how you speak, rather than what you say.

What it comes down to is that imperative / declarative is a matter of how you speak, rather than what you say.

I'm very familiar with the difference between the two. But I was questioning your "imperative function application", which I still have no idea what you mean.

you're conflating functional and declarative.

This may be true, all of my experience with declarative programming is functional programming. I have never tried logic programming. But as I said, I was going by the definitions of declarative programming that I found online. The category of a.map(b).reduce(c) would depend on what the functions b and c are. If they are referentially transparent or not. The reason I found it ridiculous is that I always thought of map and reduce as being declarative (ie. referentially transparent). But I realize now that I have used them for IO sometimes.

The part that you don't seem to agree on is the referential transparency requirement for code to be declarative. If we ignore that then we are on the same page. But as someone said earlier, it can be hard to define what declarative programming is and there are conflicting opinions. So I think we can leave that for now.

I'm still curious to hear what you mean by "imperative function application" if you are willing to explain.

Let's start with the basic wikipedia definitions, that you referred to above.

Declarative programming is a non-imperative style of programming in which programs describe their desired results without explicitly listing commands or steps that must be performed.

a.map(b).reduce(c) is a list of commands that must be performed.

So it is not declarative -- regardless of if those commands have side effects of not.

The only argument that you could make here is that the flow control is perhaps more granular than with a for loop.

If you want to go in the other direction and argue that a sufficiently intelligent compiler could deconstruct the map/reduce form into whatever it likes, then I'll point out that precisely the same holds true for a for loop, which would render the for loop declarative by that definition -- and I hope that would be an excessively ridiculous conclusion. :)

Although pure functional languages are non-imperative, they often provide a facility for describing the effect of a function as a series of steps.

Pointing out that purely functional languages can have non-declarative expressions.

Referential transparency doesn't even come into it -- it is completely independent of the style of expression used.

a.map(b).reduce(c) is a list of commands that must be performed.

So it is not declarative -- regardless of if those commands have side effects of not.

So you are saying that map andreduce are not declarative? That feels odd considering they are pretty much the face of functional programming. Anyone who hears of FP will first hear of those two functions.

I think "map function b over list a" is a very declarative way of describing the code and it forms what is essentially a single expression, not a list of individual statements to execute.

Are you able to show some actually declarative JavaScript code?

What's declarative about telling the machine to transform a sequence into another sequence by applying a procedure to each element?

What's declarative about telling the machine to compute a value from a sequence by iteratively applying a procedure to each element and the value computed so far?

map and reduce aren't function -- they're just higher order operations -- that is operations parameterized by operations.

In the case of javascript, these operations are procedures, making them higher order procedures, rather than higher order functions.

Higher order operations are often used in functional programming styles, but that's because they're convenient, not because they're fundamentally functional programming mechanisms.

Javascript is a procedural language with a generally imperative style of expression.

Declarations in javascript are pretty well limited to variable, function, import and export declarations.

map and reduce aren't function -- they're just higher order operations -- that is operations parameterized by operations.

In the case of javascript, these operations are procedures, making them higher order procedures, rather than higher order functions.

So what do you consider to be the difference between a function and an operation? And a procedure is usually defined as a series of statements that do not return anything. Map and reduce obviously return something.

Higher order operations are often used in functional programming styles, but that's because they're convenient, not because they're fundamentally functional programming mechanisms.

Oh but they are fundamentally functional. Lambda calculus, the very base of functional programming, works by treating everything as a function. Defining anything useful in lambda calculus requires higher order functions. And in untyped lambda calculus everything is a higher-order fuction. :)

JavaScript is considered a multi-paradigm language. Although it's imperative-first it is very much possible writing in the style of functional programming. Although I'm not very much into JavaScript myself, the amount of functional programming that JS developers use seem to have increased very much lately. There are many libraries for it as well, eg. Immutablejs, Rambda.

Operations encompass both functions and procedures.

A function is time-invariant.

Procedures are a series of operations over time, and may include flow-control mechanisms such as return.

I wrote 'higher order operations' rather than 'higher order functions' for a reason.

It's true that lambda calculus is generally functional, but it's not fundamentally required to be so -- consider web.mit.edu/6.827/www/old/lectures... for example.

(But that's irrelevant, since your reference to lambda calculus came from confusing higher order operation with higher order function)

Certainly you can write procedures that implement functions in javascript -- I am not sure why this is relevant.

Operations encompass both functions and procedures.
A function is time-invariant.
I wrote 'higher order operations' rather than 'higher order functions' for a reason.

Regarding this, there seems to have been a miss on my part. When I was speaking of the functions map and reduce I didn't mean they had to be time-invariant (by time-invariant I assume you mean it follows the mathematical definition of a function, also known as pure or referentially transparent). The word "function" is used so widely in the programming world to just refer to what you call operation. When speaking of time-invariant functions the most common terminology is "pure function" (from what I have seen).

It's true that lambda calculus is generally functional, but it's not fundamentally required to be so -- consider web.mit.edu/6.827/www/old/lectures... for example.

From what I understand it is a requirement. The lecture you linked was very interesting. I didn't understand all of it. But they use what they call I-structures and M-structures to isolate the side effects and keeping them pure. So in a similar manner to Haskell's IO Monad, but it's not a monad. Either way, it's not the kind of "do IO anywhere" that imperative languages have. Apparently this method should let them model languages with implicit parallelization and they used it to create the language pH (Parallel Haskell), not sure about the state of that language today since this is from the late '90s. But they also lose some benefits of regular lambda calculus when expanding it like that.

I feel like this discussion has reached a point where neither of us is making any progress in convincing the other, so I'm leaving this as my last comment and will not reply any further. Below I linked some more resources on lambda calculus and side effects that I read to get a better understanding of the lecture slides. It was very fun and interesting to read. So thanks for that.

I saw that the lecture you linked was the first result on Google for "lambda calculus side effects". It's not very comprehensive and was hard to understand. Here's a paper that covers some more basic parts first.
cs.tufts.edu/~nr/cs257/archive/nea...

Here's the research paper which I believe the lecture is based off. I only read about half of the paper, but it helped me understand the lecture slides.
reader.elsevier.com/reader/sd/pii/...

Both papers are by the same researchers and it was pretty much the only resources I found on side effects in lambda calculus.

That's fine.

I suggest that you go back over the thread and look at the places where your positions have been self-inconsistent, as it may be educational.

Best of luck.

 

Other than struggling (in JavaScript) to keep track of types and data structure I enjoy functional programming because it is more relaxing. No worries about unintended consequence and more control about what's going on due to function return values instead of ceding control to mysterious procedures.

 

Hey, join the club!
I don't like learning FP because it reminds me of Maths...
I like learning it because it makes me think different than OOP & imperative programming that was shoved down my throat back in college.

Also, it makes programs simpler and easier to test and it just looks beautiful.

 

I've been dabbling in functional programming for a couple years, for fun.

What I see as the big win of functional programming over object-oriented programming is immutability, recursion, succinct syntax, pattern matching, higher-order functions, code-as-data, separation of behavior from data, and referential transparency.

When I see functional programming done in C++, it makes me sad. The syntax is awkward, immutability in C++ isn't there, recursion is a non-starter, pattern matching can be very awkwardly mimicked with lambdas and traversing a selection vector, higher-order functions are anemic, code-as-data is extremely limited, separation of behavior from data requires strict discipline, as does referential transparency.

The biggest cons against functional programming is that it tends to have a much bigger memory footprint over C++, say anecdotally on average about x4. (Your mileage may vary, based on your particular program.)

I've looked at the various how to do functional programming in language XYZ (where XYZ is one of: C++, Swift, JavaScript, Rust, Scala, Lisp, Scheme, and others), and I'm disappointed in those languages compared to functional programming first functional programming languages like OCaml, Haskell, F#, or Elm.

Yes, I include Lisp and Scheme in the "bad list". I haven't tried Clojure which adds functional programming to Lisp. Lisp programmers who haven't used a functional programming language may have trouble grokking that sentence, since Lisp has the interesting position of being a general general purpose programmer's programming language. Lots of power there! And unlike C++ token substitution macros made by The Devil™, Lisp macros are magically awesome.

Applying functional programming techniques in non-functional programming languages doesn't seem like a big win, to me. Other developers in the language will probably consider the functional programming techniques to be non-idiomatic and out of place.

 
square :: Int -> Int
square = foldl (*) 1 . replicate 2

isEven :: Int -> Bool
isEven = (== 0) . (`mod` 2)

It's not so elegant if you make it all point-free though. Point-free notation can make some code easier to read. But if you take it too far it just becomes worse. In the case of your double function, the parameter was last in the chain and nowhere else so it makes sense to remove it.

 

Thanks for the comment! I agree with everything you said :)

code of conduct - report abuse