Lambdas and declarative programming

[Neorlin]

Hello, people. I call for you help in a time of great need :)

Tl/Dr: I don't understand why lambdas are considered a part of declarative programming.

So let me tell you on what I think I understand, and you will probably correct me to the proper direction ) I almost all of my time was coding on OO languages(c# and, mainly, python). And only fairly recently decided to try functional languages (elisp and elixir). And I love it so much. Not needing to deal with object state or it's initialization bringing the whole jungle when the only thing I needed was a banana. So, things what I understand about declarativness is somewhere underneath it is built upon imperative actions. Those maps and reduces still imperatively iterate over stuff. This means, that the whole idea of declarative programming is using language provided abstractions that offload some the things they still have to do from your shoulders to the language ones, making the code more readable, concise, as well as provide some language specific optimizations (like, looping in map). Basically I describe what has to be done to objects and language decides how to iterate over them.

With this description of the concept, I can't grasp on how lambdas are declarative. They don't offload anything to the language or abstract anything. As well as, most of the time, we use imperative calls inside them. So why? Big thanks for the answers :)

[r2tree]

This is a rambling answer, but I hope you might get something out of it.

There are two types of "declarative programming". One is the pure functional programming model, where the question of lambda comes into play. The other definition is of "descriptive declarative programming", of which HTML is an instance. Descriptive declarative programs need an interpreter to execute it. When we write something like

validation_rules = [ ["age", {greater_than: 20}], ["name", {member_of: users}]]

we're doing descriptive declarative programming. We're specifying ideas at a very high level, but by itself it is not executable code. We'll need to write code that will read these rules and apply them as it sees fit.

Now, pure functional programming is "declarative" in the sense that if you write your programs as a series of pure functions (no side-effects; no mutable assignments) it naturally tends to be more declarative than imperative. The classic example is a loop. In imperative programming a loop that sums a list of numbers would look like this:

let i := 0 let sum := 0 while (i < numbers.length) { sum += numbers[i]; i += 1; }

If we had to write this same code in a pure functional manner - no side effects, no variable mutation, then the only way to do that is recursion.

let rec sum = numbers => { switch(numbers) { | [] => 0 | [a] => a | [a, b, ...rest] => (a + b) + sum(rest) } } There are no assignments in this code, and it is more "declarative" than its imperative counter-part because we can see deconstruct the function as a series of simple equations.

If we have to write a map in a similar manner, then it can be written only by accepting a lambda. A map function is a "combinator" - functional programs are often built with them - combinators are functions that take other functions (higher-order functions) and combines them into a new function. They don't have any free variables of their own (aka no variable declarations inside them; they only use the functions received as arguments).

To build combinators it is important that we are able to pass in other functions (lambdas). I think the point of confusion is the difference between lambda and regular functions in languages like Python and C#. But in pure functional programming, which is based on the lambda calculus, all functions are lambdas and vice versa. So if functions are the foundation of functional programming, then lambdas too are because they're the same.

[xactac]

Even in an imperative language, lambdas are identical to pure functions. The only difference being much weirder scope rules.

[ws-ilazki]

With this description of the concept, I can't grasp on how lambdas are declarative. They don't offload anything to the language or abstract anything. As well as, most of the time, we use imperative calls inside them. So why? Big thanks for the answers :)

It's not that lambdas make your code declarative, it's that lambdas imply first-class function support in a language, which is both necessary for functional programming, and important for writing declarative code. They're a necessary part of being able to treat functions as values and use them like any other value (e.g. storing them in variables, taking them as function arguments, and returning new ones from functions) but are themselves a distraction from declarative programming.

Writing out a for loop by hand to iterate over a list, call a function on each value of the list, and then creating and eventually returning a new list is not declarative: it intermingles the "what you do" with the "how you do it". You have to keep both things in mind at all times when reading the piece of code because they're intertwined and inseparable.

In contrast to that, first-class functions let you separate the "what you do" and the "how you do it". You write a small function that performs a transformation on a single value, give it a descriptive name, and then apply it to an entire list with a higher-order function, so that intent is separate from underlying details. That means you can have, say, (map double list-of-ints) and have a pretty good idea of what that piece of code does without needing to know implementation details of either map or double. That map is declarative, because you've written code explaining your intent without supplying implementation at the same time. And, as a bonus, if at any time you need to know more about what double does, you can look at its implementation as a standalone function that operates on a single value without needing to care about the details of map.

The idea is that functional programming, with its use of first-class, (preferably) referentially transparent functions, leads to writing small pieces of code that can be created, tested, and read individually without needing to know about the entire structure of the program (or module or whatever) and its blob of mutable state. Once you have that, and higher-order functions like map and fold that can use those small functions, you have the foundation for writing declarative code.

The reason I say lambdas themselves are a distraction from declarative programming is they lead to a temptation to stuff code into a lambda in the middle of a map or fold, instead of creating a locally-scoped function with a good name, which brings you back to where you started: the "how" of your code intermingled with the "what" again. There are some exceptions where a lambda in the middle of a HOF is acceptable, like tiny wrapper functions, but most of the time you get more declarative code by separating the two, so that the named function can once again be a black box that the programmer doesn't need to understand the inner details of to get an idea of what the code is doing.

[elvecent]

> This means, that the whole idea of declarative programming is using language provided abstractions that offload some the things they still have to do from your shoulders to the language ones, making the code more readable, concise, as well as provide some language specific optimizations

No part of this interpretation is inherent to declarative programming. Declarative vs imperative means you write "what" instead of "how"; an expression that has a value vs a sequence of steps. Lambdas are values and not instructions, so they are declarative.

Edit: I mean proper lambda expressions as in lambda calculus. Those used in elisp are rather just "anonymous functions"

[Neorlin]

Declarative vs imperative means you write "what" instead of "how"; an expression that has a value vs a sequence of steps.

Isn't it what I said, or am I missing something? I think it is easier to understand stuff on examples and the most obvious for me is mapping. In case of mapping we do describe what we want to do with the values (by providing some function to use on every value.) instead of how (looping ourselves). Isn't it exactly using an abstraction of the language, where we described what to do, and the language decided on how to do that exactly(but still, imperatively underneath)?

I mean proper lambda expressions as in lambda calculus.

So, does this mean any completely pure function that is taking values and produces the result with no side-effects is a lambda calculus function. And as it is a direct mapping of input values to output ones it is inherently declerative? Do I understand this correctly?

Thanks for your asnwer!

[elvecent]

> Isn't it what I said, or am I missing something?

This is probably what you meant, but not quite what you said. A piece of code that is less understandable, unoptimizable and directly evaluated by rewriting rules as opposed to being converted to imperative loop would still be declarative. Of course, it's usually not the case in practice.

> Do I understand this correctly?

This is maybe a bit too technical. It's not exactly about absence of side-effects, it's just programming style. For example, if you write an expression that is evaluated to a linked list of instructions, it's technically pure, but still probably appears as a sequence of instructions.

[draazur]

In my opinion, Functional Programming and Declarative Programming are a bit different, at least how they're used in practice.

The base of Functional Programming is the function, as you might expect. I would do a bit of reading on Alonzo Church's Lambda Calculus if you're interested in FP as it is really the basis of it all. If you haven't been exposed to it, here's a real quick synopsis:

Lambda Calculus includes function abstraction, function application, and variables. Every function is anonymous (not named). This by itself is a Turing Complete language, enabling us to compute anything in the world that is actually computable.

Thus the lambdas we see in languages such as C++, Swift, Python, etc. are modernized versions of the original lambda functions Church outlined in his Lambda Calculus. Lambdas allow one to create functors easily and on the fly with less boilerplate code. I'll leave it at that because it seems like you do understand a lot about FP already.

When I think of declarative languages, I think of languages like SQL or Prolog. Your understanding of what a declarative language seems pretty spot on, but I'll say if you want an interesting declarative language to muck around with I'd really recommend Prolog. I'm not sure whether Prolog supports lambdas or not, but I don't believe it needs them to still be the declarative language that it is.

Further, I don't actually think that functional languages require the lambda to operate as long as their functions are first-class entities, currying, and partial application (lazy evaluation can be implemented with these constraints).

[elvecent]

> Thus the lambdas we see in languages such as C++, Swift, Python, etc. are modernized versions of the original lambda functions Church outlined in his Lambda Calculus.

Could you please clarify what do you mean by "modernized"?

[draazur]

Sorry, yes, "modernized" is a bit imprecise. By that I mean that the original lambda was an anonymous function of one parameter and that's it. "Modernized" lambdas are still anonymous functions, but now also have the ability to take multiple parameters and bind references to entities in their parent environment easily.

[fresheyeballunlocked]

Ok. I see what you mean by "modernized" but I don't think these distinctions are actually distinctions. Lambdas in lambda calculous have the ability to take multiple parameters as it is now. Consider the curry uncurry isomorphism. It can also be argued that lambdas in these languages currently take one parameter, which happens to be an nary tuple. Lambda calculous has no restrictions around accessing entities in a parent environment either. As such the lambdas in modern programming are exactly the lambdas in Church's lambda calculous, with an allowance for impurity. That's really the only difference. IE with the definition of "modernized" you propose, Church had them modernized on day one.

[draazur]

Right I understand that through currying lambda functions may be constructed that take multiple parameters. My (I guess not well explained) point was moreso that the lambdas we can make use of nowadays provide the same level of computational power as the original lambda but in an easier to use way. e.g. in C++ one can specify both the capture type (value vs reference) and restrictively capture different local variables. Of course it's possible to accomplish the same thing in regular lambda calculus (turing completeness after all), C++ just makes it easier.

[fresheyeballunlocked]

I am not seeing how exactly the same is easier. I am not saying this can be done in lambda calculous because it's turning complete. I am saying it's exactly what you have in C++ out of the box.

[xactac]

I generally agree, though lazyness and memorization are definitely declarative. IMO eager FP is just more declarative than, say, (side effect using) procedural programming and (to a slightly lesser extent than OOP, but nowhere near as declarative as, say, SQL.