What does composition mean in the context of functional programming?

Question

What do functional programmers mean when they say that a certain thing is compound or incapable?

Some of the statements I read are as follows:

• Management structures are not composite.
• Themes do not compose.
• Monadic operations are composite.

Answer 1

Marcelo Cantos gave a pretty good explanation , but I think it can be done a little more accurately.

A type of thing can be arranged when several instances can be combined in a certain way to create the same type of thing.

The combination of management structure. Languages ​​like C make a distinction between expressions that can be composed using operators to create new expressions and operators that can be composed using control structures such as if , for and the "sequence management structure" that simply follows the instructions for order. The fact is that these two categories are not on an equal footing - many control structures use expressions (for example, an expression evaluated by if to choose which branch to execute), but expressions cannot use control structures (for example, you cannot return a loop for ). Although it may seem crazy or pointless to “return a for loop,” the general idea of ​​treating control structures as first-class objects that can be stored and transmitted is not only possible, but also useful. In lazy functional languages, such as Haskell, control structures such as if and for can be represented as ordinary functions that can be manipulated in expressions, like any other term, which allows you to use functions that "build" other functions in according to the parameters they pass, and return them to the caller. Therefore, while C (for example) divides “things that the programmer may want to do” into two categories, and restricts the ways of combining objects from these categories, Haskell (for example) has only one category and does not impose such restrictions, therefore this sense, it provides great flexibility.

Possibility of thread arrangement. . I assume that Marcelo Cantos did this, that you are really talking about the compositability of threads that use locks / mutexes. This is a bit more complicated because there can be threads on his face that use multiple locks; but what’s important is that we cannot have threads that use multiple locks with the guarantees they must have.

We can define a lock as a type of thing that has certain operations that can be performed on it, that come with certain guarantees. One guarantee: suppose there is a lock object x , then, provided that every process that calls lock(x) ultimately calls unlock(x) , any call to lock(x) will eventually return successfully with x , blocked current thread / process. This guarantee greatly simplifies discussions about program behavior.

Unfortunately, if there is more than one castle in the world, this is no longer the case. If thread A calls lock(x); lock(y); lock(x); lock(y); and thread B calls lock(y); lock(x); lock(y); lock(x); , then it is possible that A locks the lock x , and B locks the y lock, and they both wait indefinitely until the other thread releases the other lock: deadlock. Thus, locks are not composite, because when you use more than one, you cannot just say that this important guarantee is still preserved - without analyzing the code in detail to see how it manages the locks . In other words, you can no longer afford to view functions as black boxes.

Things that are composite are good because they allow abstractions, which means that they allow us to reason about code without caring about all the details, and this reduces the cognitive load on the programmer.

Answer 2

A simple layout example is the Linux command line, where the channel symbol allows you to combine simple commands (ls, grep, cat, etc.) in an almost unlimited number of ways, thereby "constituting" a large number of complex behaviors from a small number of simple primitives.

There are several advantages to convenience:

• More homogeneous behavior: as an example, having one command that implements "show results on one page at a time" ( more ), you get a degree of uniformity of paging, which would not be possible if each team had to implement its own mechanisms (and command line flags) for making a paging call.
• Less re-implementation work (DRY): Instead of having meaningless different paging implementations, there is only one that is used around the world.
• Additional functionality for a given amount of implementation effort: existing primitives can be combined for a much wider range of tasks than would be the case if the same effort entered into monolithic, unconsolidated teams.

As the Linux command line example shows, linkability is not necessarily limited to functional programming, but the concept is the same: to have small pieces of code that perform limited tasks, and to create more complex functions by appropriately distributing outputs and inputs.

The fact is that functional programming is well suited for this: with immutable variables and restrictions on side effects, you can make it more easily, since you do not need to worry about what happens under the hood in the called function - for example, updating a shared variable therefore the result will be invalid for certain sequences of operations or access to a common lock, so certain sequences of calls will depend.

This functional programmability - any function depends only on its input parameters, and the output can be transferred to any function that can handle the type of the return value.

In turn, having fewer data types provides more options. Rick Hickey from Clojure said something in the lines

each new type of object is inherently incompatible with all code written

which is definitely well done.

Practical composition also depends on standardization on a small set of data types, for example, a Unix command with standard tab-based text.

Postscript

Eric Raymond wrote a book on Unix philosophy, two of the design principles that he listed were

• Modularity Rule: Write simple parts connected by clean interfaces.
• Composition rule: developing programs that need to be connected to other programs.

From http://catb.org/~esr/writings/taoup/html/ch01s06.html#id2877537

The difficulty in functional programming can be said to bring these principles to the level of individual functions.

Answer 3

Composition in computer science is the ability to assemble complex behavior by aggregating simpler behavior. Functional decomposition is an example of this, in which a complex function is broken down into smaller simple capture functions and assembled into a finite system by a top-level function. It can be said that the top-level function has “components” as a whole.

Some concepts are not easy to compose. For example, a thread-safe data structure can allow the safe installation and removal of elements, and it does this by blocking the data structure or some subset of it, so that one thread can perform the necessary manipulations without making any changes to it - and the data structure is damaged; while it works. However, for a business function, you may need to remove an item from one collection and then insert it into another and for the entire operation performed atomically. The problem is that locking occurs only on the data structure. You can safely remove an element from one, but then you may find that it cannot insert it into another due to some violation. Or you can try inserting it in one second and then removing it from the first, only to find that another thread has stolen it from under your nose. Understanding that you cannot complete the operation, you can try to return things the way they were, only to find that the reversal is failing for the same reasons, and you are now in limbo! Of course, you could implement a richer locking scheme, which covers several data structures, but this only works if everyone agrees with the new locking scheme and bear the burden of using it all the time, even when all their operations are on the same data structure .

Mutex style locking is thus a concept that does not compile. You cannot implement higher-level thread-safe behavior by simply combining lower-level thread-safe operations. The solution in this case is to use a concept that constitutes, for example, STM .

Answer 4

I agree with the answer of Marcelo Cantos, but I think that he can take on more background than some readers, which is also due to why composition in functional programming is special. The functional composition of programming functions is essentially identical to the composition of functions in mathematics. In math, you can have a function f(x) = x^2 and a function g(x) = x + 1 . Composing functions means creating a new function in which the arguments of the function are specified by the "internal" function, and the output of the "internal" function serves as input to the "external" function. Composing f outer with g inner can be written f(g(x)) . If you specified a value of 1 for x , then g(1) == 1 + 1 == 2 , so f(g(1)) == f(2) == 2^2 == 4 . More generally, f(g(x)) == f(x + 1) == (x+1)^2 . I described composition using the f(g(x)) syntax, but mathematicians often prefer a different syntax, (f . g)(x) . I think this is because it is clear that f composed with g is a function in itself that takes one argument.

Functional programs are completely created using compositional primitives. A program in Haskell may simplify a function that takes a runtime as an argument and returns the result of some manipulations with that environment. (Grokking this statement will require some understanding of monads.) Everything else is done using composition in a mathematical sense .

Answer 5

Another example: consider asynchronous programming in .NET. If you use a language such as C # and you need to make a series of asynchronous (non-blocking) I / O calls through the Begin / End API, then to call two operations Foo and Bar in sequence, you must set two methods ( BeginFooAndBar , EndFooAndBar ), where BeginFooAndBar calls BeginFoo and passes the callback to Intermediate , and Intermediate then calls the BeginBar , and you must skip the intermediate values ​​and IAsyncResult pass the status information, and if you want the block around try - catch block all this, then good luck, you need to duplicate processing code is excluded first in three places, yikes, and this is a terrible mess.

But then with F # there is an async type built on functional extensions that can be linked, and so you can write, for example.

 let AsyncFooAndBar() = async { let! x = Async.FromBeginEnd(BeginFoo, EndFoo) let! y = Async.FromBeginEnd(BeginBar, EndBar, x) return y * 2 } 

or what you have, and it's simple, and if you want to place a try - catch around it, fine, the code is all in one method, and does not spread in three, you just put a try - catch around it, and it works.

Answer 6

Here is an example of the real world. The names of all the people who live in your home are a list of the names of all the men in your home, combined with a list of all the women in your home.

This is possible, since each of these two subtasks can be solved independently and without interfering with the solution of the other.

On the other hand, many recipes are not compound, since the steps must be performed in a certain order and based on the results of other steps. You must break the eggs before you beat them!

Answer 7

Compatibility allows the developer community to constantly increase the level of abstraction, several levels, without being attached to the base layer.