June 1, 2011 at 17:27Command and Strategy patterns in terms of functional programming
As a result of studying functional programming, some thoughts appeared in my head that I want to share with you.
In the minds of many developers who are accustomed to an object-oriented paradigm, it seems that software design, as such, is inextricably linked with OOP and everything else is heresy. UML, for the most part targeting OOP, is used as a universal language for design — although it certainly is not. And we see how the world of object-oriented programming is gradually plunging into the abyss of criminal reengineering (1).
Because of this, the question of choosing a programming paradigm is often not even raised . Nevertheless, this question is very significant, and often the correct answer provides great advantages (3). Generally speaking, this goes beyond what we used to call design - this is a question from the field of architecture.
Not so long ago I came across a very interesting study - (2). It considers the task of formalizing the concepts of "architecture", "design" and "implementation", which are most often used informally. And the authors manage to deduce a very interesting criterion: the Intension / Locality criterion. I will not go into philosophy and just give a brief description of the criterion (this part is actually a translation) and my conclusions from it.
The Intension property means the ability of a certain entity to describe an infinite number of objects: for example, the concept of a prime number. The property of extensionality is opposite to it - the essence describes a finite set of objects: for example, the concept of a country is a member of NATO.
Locality property - an entity affects only a separate part of the system. Accordingly, global - the essence affects the whole system as a whole.
Duck, given these two properties, the authors of this study compile such a table:
Using it, it is easy to determine what relates to the level of architecture, and what to the level of design. And here is my conclusion: the choice of a programming paradigm, platform, and language is a decision at the architectural level , because this choice is global (affects all parts of the system) and intensional (paradigms determine how to solve an infinite number of tasks).
However, to solve such a global problem (to find criteria for choosing a suitable paradigm) I still can not afford. Therefore, I decided to choose two already existing classes of problems and show that it is worthwhile to use for them not the usual approach for many OOs, but the functional one, which has recently gained (deservedly) increasing popularity.
I chose the classes of tasks in an unusual way - I took two OO design patterns and showed that they, in fact, are a limited implementation of a concept from the field of functional programming - a higher-order function (hereinafter: FVP). The hypothesis was that patterns are well-established solutions to certain problems.and since there are problems and their established solutions, apparently there are some weaknesses and shortcomings that have to be overcome. For the considered patterns, this is indeed so.
Incidentally, a similar approach was used in (5) and (6). In (6), the possibility of replacing most of the patterns was generally indicated, but no detailed analysis of each was performed. In (5) there was a more detailed consideration of Command and Strategy, but on a slightly different side. I decided to do something more practical than in (6), and with different accents than in (5). So let's get started.
I think almost everyone in one form or another is familiar with this idea.
A higher-order function is a function that takes as an argument or returns another function as a result.
This is made possible by the basic concept of functional programming: functions are values. It is worth noting that when we say that function and value in functional programming fully correspond to similar concepts from mathematics, we mean exactly the full correspondence. This is the same. An example of the widely used in mathematical mathematics is the differentiation, integration and composition operators (generally speaking, this is close to the concept of an operator from functional analysis). The composition operator is directly expressed in most languages that support a functional paradigm. Example on F #:
Conclusion:
Obviously, the notation f << g corresponds to the notation f (g (x)) or F ○ G.
To better understand this, I suggest paying attention to the type of composition operator:
The parts of the description of the type of function in parentheses are also types of functions. That is, it is a function that takes as arguments:
and returning a value of type 'b. In fact, it builds a function that takes a value of type 'c as an argument and returns a value of type' b, i.e. type can be rewritten like this:
FVP allow to distinguish the general behavior . Due to this, they improve code reusability.
This can be used for a variety of purposes - for example, to handle exceptions. Suppose we have many pieces of code that can cause a specific set of exceptions. We can write the error-prone code itself in the form of functions that we will pass as a parameter to another function that processes exceptions. C # example:
And here is the FEP that handles exceptions:
Then, to handle the exceptions caused by any function, it is enough to write:
This significantly reduces the code if there are a lot of exception handlers and / or many functions that can throw exceptions that need to be processed the same way.
Also a classic example of highlighting common behavior is the use of higher-order functions for sorting. Obviously, for sorting, you must be able to compare the elements of the sorted collection with each other. The function that is passed as an argument to the sorting function acts as such a “comparator” - accordingly, the sorting function must be FVP to ensure universality. In general, the ability to create FVP is a critical link in the chain of actions aimed at creating abstract generalized algorithms .
By the way, since FVP, like any functions, are values, they can be used to represent data. About this, see the article about the performance of Church .
The Command design pattern, like Strategy, refers to behavioral design patterns. Its main role is the encapsulation of a certain function. This pattern has many uses, but most often it is used to do the following:
In general, it looks like this:
I will consider an example with the implementation of undo and redo - you can see a clean OO version of the implementation of this functionality here .
The distribution of roles in this diagram:
Here Filter corresponds to Receiver 'y, LoggingInvoker - Invoker ' y, IFilterCommand - ICommand . This is how we will call operations (you can create commands both in Client 'e, passing them as a parameter to
But here's how we will cancel them:
performedOps and undoneOps are stacks that store executed and canceled teams.
However, after considering the FEP, it is quite obvious that all this behavior can be implemented in the form of FEP, if the selected language supports this feature. Indeed, the Invoker object can be replaced by the FPF, which takes as an argument a function that corresponds to a specific operation - we no longer need Command objects , because the functions themselves are values, and the ICommand interface , because its functions are performed by a system of types of language that supports a functional paradigm.
Here is a diagram of replacing this pattern with a design in a functional paradigm that can perform the same functions:
On the pseudocode (inspired by F #), the corresponding functional implementation will look like this:
We pass the function that we want to perform, FWP
This approach has some additional advantages over using the Command pattern:
In addition, if we use a multi-paradigm language, we can combine the Command pattern and the approach demonstrated here in different proportions of the OO.
Many modern languages support AFP to one degree or another. For example, C # has a delegate mechanism. An example of solving the problem of creating undo using delegates can be found in (4).
The Strategy pattern is designed to allow the client to choose one of several possible ways to solve the problem. In OOP, the following construction is created for this: The
context stores a reference to one of the implementations of the IStrategy interface , if necessary, it performs an operation using the method of this stored object. Changing objects - changing methods.
It is also easily transformed to a functional style. This time we can use the list of functions to save possible strategies:
On the pseudocode:
Functions
In addition to greatly simplifying and shortening the code, this approach gives us an additional advantage - now we can easily create functions parameterized by several strategies at once, which, with the usual OO approach, leads to a very complex program structure. We may not need to specify separate names for strategies at all with the help of such an opportunity as anonymous functions, if they are simple enough to implement. For example, to sort the data in the FP, you can use the FVP sort and pass it not the type that implements the IComparer interface, which implements the comparison method, as is done in OOP, but just the comparison operation itself:
1. The correct choice of a paradigm in accordance with the class of the problem being solved can often be a critical factor for the success of its solution. If your task belongs to the class of so-called behavior-centric, you should consider using a functional approach.
2. Command and Strategy patterns are a limited implementation of higher-order functions
3. It is not necessary to switch to a purely functional language in order to take advantage of the solution using FWP - most modern mainstream languages support FWP to one degree or another.
Recently, a large number of languages have appeared that equally combine OO and the functional paradigm; many OO languages have begun to acquire functional capabilities. I hope that this article will help someone better use the new features of their favorite programming languages. Good luck in job!
1. Criminal Overengineering
2. Architecture, Design, Implementation . Amnon H. Eden, Rick Kazman. Portland: B.Sc. 2003. 25th International Conference on Software Engineering - ICSE
3. Banking Firm Uses Functional Language to Speed Development by 50 Percent. Microsoft Case Studies. March 2010
4. Bishop, Judith. C # 3.0 Design Patterns. Sebastopol, California: O'Reilly, 2008.
5. Tomas Petricek, Jon Skeet. Functional Programming for the Real World. b.m .: Manning Publications, 2010.
6. Gabriel, Richard P. Objects Have Failed Slides DreamSongs.com.
7. Smith, Chris. Programming F #. Sebastopol, California: O'Reilly, 2010.
UDP:
alexeyromI wrote a very useful comment, with his consent I put it into the body of the post so that it can be seen:
“Norvig in 1996 examined patterns in Lisp and Dylan . Actually, the result is similar (many patterns become trivial or significantly simplified), but on richer material. ”
Design patterns and functional programming? How is this even related?
In the minds of many developers who are accustomed to an object-oriented paradigm, it seems that software design, as such, is inextricably linked with OOP and everything else is heresy. UML, for the most part targeting OOP, is used as a universal language for design — although it certainly is not. And we see how the world of object-oriented programming is gradually plunging into the abyss of criminal reengineering (1).
Because of this, the question of choosing a programming paradigm is often not even raised . Nevertheless, this question is very significant, and often the correct answer provides great advantages (3). Generally speaking, this goes beyond what we used to call design - this is a question from the field of architecture.
Lyrical digression: the difference between architecture, design and implementation
Not so long ago I came across a very interesting study - (2). It considers the task of formalizing the concepts of "architecture", "design" and "implementation", which are most often used informally. And the authors manage to deduce a very interesting criterion: the Intension / Locality criterion. I will not go into philosophy and just give a brief description of the criterion (this part is actually a translation) and my conclusions from it.
The Intension property means the ability of a certain entity to describe an infinite number of objects: for example, the concept of a prime number. The property of extensionality is opposite to it - the essence describes a finite set of objects: for example, the concept of a country is a member of NATO.
Locality property - an entity affects only a separate part of the system. Accordingly, global - the essence affects the whole system as a whole.
Duck, given these two properties, the authors of this study compile such a table:
Using it, it is easy to determine what relates to the level of architecture, and what to the level of design. And here is my conclusion: the choice of a programming paradigm, platform, and language is a decision at the architectural level , because this choice is global (affects all parts of the system) and intensional (paradigms determine how to solve an infinite number of tasks).
However, to solve such a global problem (to find criteria for choosing a suitable paradigm) I still can not afford. Therefore, I decided to choose two already existing classes of problems and show that it is worthwhile to use for them not the usual approach for many OOs, but the functional one, which has recently gained (deservedly) increasing popularity.
I chose the classes of tasks in an unusual way - I took two OO design patterns and showed that they, in fact, are a limited implementation of a concept from the field of functional programming - a higher-order function (hereinafter: FVP). The hypothesis was that patterns are well-established solutions to certain problems.and since there are problems and their established solutions, apparently there are some weaknesses and shortcomings that have to be overcome. For the considered patterns, this is indeed so.
Incidentally, a similar approach was used in (5) and (6). In (6), the possibility of replacing most of the patterns was generally indicated, but no detailed analysis of each was performed. In (5) there was a more detailed consideration of Command and Strategy, but on a slightly different side. I decided to do something more practical than in (6), and with different accents than in (5). So let's get started.
Higher-order functions
I think almost everyone in one form or another is familiar with this idea.
A higher-order function is a function that takes as an argument or returns another function as a result.
This is made possible by the basic concept of functional programming: functions are values. It is worth noting that when we say that function and value in functional programming fully correspond to similar concepts from mathematics, we mean exactly the full correspondence. This is the same. An example of the widely used in mathematical mathematics is the differentiation, integration and composition operators (generally speaking, this is close to the concept of an operator from functional analysis). The composition operator is directly expressed in most languages that support a functional paradigm. Example on F #:
let f = (+) 10
let g = (*) 2
let composition = f << g
printfn "%i" <| g 15
printfn "%i" <| f 30
printfn "%i" <| composition 15Conclusion:
30
40
40Obviously, the notation f << g corresponds to the notation f (g (x)) or F ○ G.
To better understand this, I suggest paying attention to the type of composition operator:
('a -> 'b) -> ('c -> 'a) -> 'c -> 'bThe parts of the description of the type of function in parentheses are also types of functions. That is, it is a function that takes as arguments:
- A function that takes as argument the value of the generic type 'a and returns a value of the generic type' b
- A function that takes a value of the generic type 'c as an argument and returns a value of the generic type' a
- Value of type 'c
and returning a value of type 'b. In fact, it builds a function that takes a value of type 'c as an argument and returns a value of type' b, i.e. type can be rewritten like this:
('a -> 'b) -> ('c -> 'a) -> ('c -> 'b)FVP allow to distinguish the general behavior . Due to this, they improve code reusability.
This can be used for a variety of purposes - for example, to handle exceptions. Suppose we have many pieces of code that can cause a specific set of exceptions. We can write the error-prone code itself in the form of functions that we will pass as a parameter to another function that processes exceptions. C # example:
private void CalculateAdditionalQuantityToIncreaseGain()
{
//получаем данные
var unitPrice = ExtractDecimal(gainUnitPriceEdit);
var quantityReleased = ExtractDecimal(gainQuantityEdit);
...
}And here is the FEP that handles exceptions:
private static void ExecuteErrorProneCode(Action procedure)
{
try
{
procedure(); //исполняем переданную в качестве параметра функцию
}
catch (WrongDecimalInputInTextBoxException ex)
{
MessageBox.Show(ex.Message, "Ошибка во вводе");
}
catch (Exception ex)
{
MessageBox.Show(ex.Message, "Ошибка");
}
}Then, to handle the exceptions caused by any function, it is enough to write:
ExecuteErrorProneCode(CalculateAdditionalQuantityToIncreaseGain);This significantly reduces the code if there are a lot of exception handlers and / or many functions that can throw exceptions that need to be processed the same way.
Also a classic example of highlighting common behavior is the use of higher-order functions for sorting. Obviously, for sorting, you must be able to compare the elements of the sorted collection with each other. The function that is passed as an argument to the sorting function acts as such a “comparator” - accordingly, the sorting function must be FVP to ensure universality. In general, the ability to create FVP is a critical link in the chain of actions aimed at creating abstract generalized algorithms .
By the way, since FVP, like any functions, are values, they can be used to represent data. About this, see the article about the performance of Church .
Command pattern
The Command design pattern, like Strategy, refers to behavioral design patterns. Its main role is the encapsulation of a certain function. This pattern has many uses, but most often it is used to do the following:
- Send requests to different recipients
- Line up teams, keep logs, cancel requests
- Create complex operations from simple
- Implement the Undo (undo the last action) and Redo (repeat the last undoed actions) commands
In general, it looks like this:
I will consider an example with the implementation of undo and redo - you can see a clean OO version of the implementation of this functionality here .
The distribution of roles in this diagram:
Here Filter corresponds to Receiver 'y, LoggingInvoker - Invoker ' y, IFilterCommand - ICommand . This is how we will call operations (you can create commands both in Client 'e, passing them as a parameter to
Execute()LoggingInvoker ' s method , and in LoggingInvoker 'e itself - the choice depends on the specific situation): But here's how we will cancel them:
performedOps and undoneOps are stacks that store executed and canceled teams.
However, after considering the FEP, it is quite obvious that all this behavior can be implemented in the form of FEP, if the selected language supports this feature. Indeed, the Invoker object can be replaced by the FPF, which takes as an argument a function that corresponds to a specific operation - we no longer need Command objects , because the functions themselves are values, and the ICommand interface , because its functions are performed by a system of types of language that supports a functional paradigm.
Here is a diagram of replacing this pattern with a design in a functional paradigm that can perform the same functions:
On the pseudocode (inspired by F #), the corresponding functional implementation will look like this:
//стеки для выполненных и отменённых операций
//здесь мы создаём тип - кортеж из функции и первоначальных данных
type OpType = (DataType -> DataType) * DataType
//и стеки из значений этого типа
let performedOps = Stack()
let undoneOps = Stack()
//замена LoggingInvoker - ФВП
let execute operation data =
let res = operation data //выполняем операцию
performedOps.Push(operation, data) //заносим операцию и предыдущее состояние в стек
res //возвращаем результат выполнения операции
let undo () =
if performedOps.Count > 0 then
//переносим запись об операции из стека выполненных в стек отменённых
undoneOps.Push(performedOps.Pop())
//и возвращаем состояние до выполнения операции
Some (snd undoneOps.Peek()) //здесь мы используем обобщённый тип 'a option, см. (5) или (7)
else
None
//Операции
let OperationOne data =
...
let OperationTwo data =
...
//выполняем операцию OperationOne
let mutable a = execute OperationOne data
//отменяем операцию
let b <- undo ()
We pass the function that we want to perform, FWP
execute. The function executekeeps a stack of completed operations, executes the operation, and returns the result of its execution. The undo function cancels the last operation performed. This approach has some additional advantages over using the Command pattern:
- The resulting code is more natural, shorter, and simpler.
- You can easily create macros and complex operations using composition or pipe-lining (for pipe-lining see (5) or (7)) simple operations
- You can create complex data structures containing operations, for example, to dynamically build menus.
In addition, if we use a multi-paradigm language, we can combine the Command pattern and the approach demonstrated here in different proportions of the OO.
Many modern languages support AFP to one degree or another. For example, C # has a delegate mechanism. An example of solving the problem of creating undo using delegates can be found in (4).
Strategy Pattern
The Strategy pattern is designed to allow the client to choose one of several possible ways to solve the problem. In OOP, the following construction is created for this: The
context stores a reference to one of the implementations of the IStrategy interface , if necessary, it performs an operation using the method of this stored object. Changing objects - changing methods.
It is also easily transformed to a functional style. This time we can use the list of functions to save possible strategies:
On the pseudocode:
let strategyA data = ...
let strategyB data = ...
let useStrategy strategy data =
...
strategy data
...
useStrategy strategyA dataFunctions
strategyA, strategyB... - a function that implements the strategy. A higher order function useStrategyapplies the selected strategy to the data. The strategy is passed simply as an argument to the function useStrategy.In addition to greatly simplifying and shortening the code, this approach gives us an additional advantage - now we can easily create functions parameterized by several strategies at once, which, with the usual OO approach, leads to a very complex program structure. We may not need to specify separate names for strategies at all with the help of such an opportunity as anonymous functions, if they are simple enough to implement. For example, to sort the data in the FP, you can use the FVP sort and pass it not the type that implements the IComparer interface, which implements the comparison method, as is done in OOP, but just the comparison operation itself:
let a = sort (<) dataconclusions
1. The correct choice of a paradigm in accordance with the class of the problem being solved can often be a critical factor for the success of its solution. If your task belongs to the class of so-called behavior-centric, you should consider using a functional approach.
2. Command and Strategy patterns are a limited implementation of higher-order functions
3. It is not necessary to switch to a purely functional language in order to take advantage of the solution using FWP - most modern mainstream languages support FWP to one degree or another.
Recently, a large number of languages have appeared that equally combine OO and the functional paradigm; many OO languages have begun to acquire functional capabilities. I hope that this article will help someone better use the new features of their favorite programming languages. Good luck in job!
Sources
1. Criminal Overengineering
2. Architecture, Design, Implementation . Amnon H. Eden, Rick Kazman. Portland: B.Sc. 2003. 25th International Conference on Software Engineering - ICSE
3. Banking Firm Uses Functional Language to Speed Development by 50 Percent. Microsoft Case Studies. March 2010
4. Bishop, Judith. C # 3.0 Design Patterns. Sebastopol, California: O'Reilly, 2008.
5. Tomas Petricek, Jon Skeet. Functional Programming for the Real World. b.m .: Manning Publications, 2010.
6. Gabriel, Richard P. Objects Have Failed Slides DreamSongs.com.
7. Smith, Chris. Programming F #. Sebastopol, California: O'Reilly, 2010.
UDP:
alexeyromI wrote a very useful comment, with his consent I put it into the body of the post so that it can be seen:
“Norvig in 1996 examined patterns in Lisp and Dylan . Actually, the result is similar (many patterns become trivial or significantly simplified), but on richer material. ”