Design and architecture in the OP. Introduction and Part 1

Introduction

In the world of functional programming, there is one big gap, namely, the topic of high-level design of large applications is almost not covered. I decided to study this question for myself. Are there significant differences in the design of applications in the OP world from that in the imperative world? What is a “canonical opcode”? What are the development idioms, does it make sense to talk about design patterns as applied to the OP ? These and other important questions often flare up here and there , but for the time being I don’t know of a single book similar to the book of the Gang of Four. Probably, my research has already been repeated by someone, but all the better: similar results will confirm the correctness, others will indicate a place in the theory that needs to be improved.

About the material

The basis of these articles is the experience in developing the game “The Amoeba World”. The language used is Haskell. I initially made the game as part of the Ludum Dare contest # 27, but the scope was on prototyping the infrastructure for another game, more ambitious, whose name is Big Space. “The Amoeba World” is just a “cat” on which I explore approaches in “functional” game development. Competition-oriented game has become a good starting point for further thought.

The code for “The Amoeba World” is here . Documentation on the "Big Space" - here . By the way, a long time ago I did something similar. It was the Haskell Quest Tutorial , as part of which I, um, also developed the game. If you can call it that. But it was a very simple low-level material for the study of the Haskell language, but here we will deal with completely different matters. Accordingly, it is assumed that the reader is sufficiently familiar with the FP and the Haskell programming language.

Plan

At least the following topics should be covered further:
')

1. Part 1 . FP application architecture. Descending design in OP. Fighting software complexity.
2. Part 2 . Ascending design in OP. The idea is the basis of good design. Antipatterns in haskell
3. Part 3 Properties and laws. Scripts. Inversion of Control in Haskell.
4. Part 4. FRP

Also this series of articles can be found in a single document here .

Part one

FP application architecture. Descending design in OP. Fighting software complexity.

Some theory

The software development process is proceeding far and wide. We have been using standardized techniques for a long time in our practice, including various methodologies, software design techniques, and modeling tools. UML, for example, is very well known, an object-oriented (for the most part) design language. It is used for end-to-end development, starting with requirements and ending, if lucky, with code generation. And the design patterns? Today it is necessary to know them in order to solve typical problems in the OO code. And there is only one question - how applicable is this knowledge base to the functional paradigm? Is it possible to invent your own modeling language? Do you need patterns for functional languages?

It seems that the initial stages - the collection and analysis of requirements , the definition of program functionality, the writing of business scenarios - will always be present to some degree, no matter what the software is. Imagine that the requirements are already known to us, and we will skip the first stages so far, focusing on more engineering ones.

And the first truly engineering stage is the development of software architecture, or, equivalently, the architectural design of software. Here we solve the issues of high-level structure and functioning of the program in order to support all non-functional requirements collected earlier. The choice of programming paradigm is also an architectural issue. Choosing the OP, we almost completely reject the UML due to its object nature. So, class diagrams, objects and sequences almost lose their meaning. There are no classes or objects in Haskell, there is no encapsulated mutability, but there is only a data conversion process. The sequence diagram needed to describe the interactions of these very objects could somehow be used for chains of functions, but the thing is that the chains themselves will be more readable and understandable. All other diagrams, however, are quite applicable. In a large program on the OP, there are also subsystems or components, which means that diagrams of components, packages and communications remain in the system. The state diagram is universal: processes and finite automata are very common. It could be applied even in other areas, not only in software development. Finally, the use case diagram generally has little to do with software design; it associates business requirements with system requirements at the analysis stage.

But if you look closely at the "applicable" diagrams, you can come to the conclusion that they will not help much in the high-level design of the code (which is located below the architecture design), or even can harm, pushing to imperative thinking. For example, when thinking about component architecture, we recall Inversion of Control . IoC solves one of the main problems of software development - it helps to fight against complexity by highlighting abstractions. And what if you take it into service? And here we remember that there is one of the ways to implement it - Dependency Injection . It can probably be adapted to our needs - in the following parts we will look at several different solutions, such as: Existential Types, module-level abstractions, monad abstraction, and also monad state injection. But in fact, having first-class functions, we can forget about DI altogether, since this is a non-idiomatic approach , since it leads (explicitly or implicitly) to the state in the FP program. And this is not always good. Although, in fairness, you need to recognize that IoC is also present in the AF.

And what else, if not IoC, helps in dealing with the complexity of software design? From SICP, we know that there are three important techniques:

1. abstractions for hiding implementation details (“black box”);
2. public interfaces for interaction between independent systems;
3. domain-specific languages ​​(DSL, Domain Specific Languages ).

It can be assumed that the first two methods are known to us. Interfaces, abstraction, concealment of details are all about one thing, and IoC is an example. Due to the dominance of OOP languages, we have established strong associative links “abstraction” => “inheritance” and “interface” => “OOP interface”. In fact, this is only part of the truth. We too narrow the terms “interface” and “abstraction” to OOP concepts and thereby cut off “inappropriate” paradigms. However, the ideas underlying the first two methods are more general, they are valid for all worlds, and knowledge of other approaches cannot be superfluous.

Regarding the third method, we can say the following. In view of its nature, FNs have to write all kinds of subject-oriented languages ​​- internal, external. Firstly, because the binding code of parsers and translators is short, understandable and easily modified. Secondly, the syntax of FP languages ​​allows you to make embedded DSL without overloading the main code. Subject-oriented languages ​​can drastically reduce the complexity of the program and reduce the number of errors. The side effect (and maybe the main one) of the DSL implementation is a clearer understanding of the subject area. Code in a domain-specific language is much better suited for formalizing requirements than low-level approaches.

However, it should be recognized: specialized languages ​​are greatly underestimated in real life. There is a myth that it is difficult, difficult and expensive to maintain. Its reason is that an imperative programmer needs to go out of his comfort zone and imagine a different syntax, semantics, and maybe even a different paradigm to create an external DSL. Without knowing this, he will be able to come up with DSL only within his own framework, which will automatically lead him to the current code, and then to the question “Why then DSL?”. But that's not all. How to implement DSL? Dominant OOP languages ​​(with rare exceptions) do not offer an elegant solution in comparison with functional ones; Indeed, with the traditional approach, considerable effort is required so that the external DSL does not increase the risks. To remove the risks, it is necessary to study other paradigms and tighten the theory; As a result, the complexity of implementing external DSL in a familiar language is transferred to the very idea of ​​DSL. This error is for some reason considered to be a strong argument “against” ... And it is easily broken by the fact that in addition to the external DSL there is an internal one (embedded, embedded DSL, eDSL). For an external DSL, inexpressible grammar of the current language, we need at least a parser and translator, which leads to an additional serving code. But the internal DSL is within the grammar of the current language, which means that no parsers and translators are needed. However, it is still necessary to come up with a different code organization; and again we came to the conclusion that one cannot do without a broad programmer outlook. And this is a natural requirement for a modern programmer. Well, Martin Fowler to help us.

What else can you say about architecture as applied to the OP? The important point is that side effects are undesirable in AF. But in any large program it is necessary to work with the outside world; that is, there must be some mechanisms for controlling side effects. And they are. Haskell's notorious monads are a great option, but they are more likely a tool of lower design than an element of the overall architecture. So, the code of communication with an external server can be implemented within the framework of the IO monad, which will not differ much from imperative. The second solution is that the code can be declared on DSL. In this DSL there are bricks with side effects, there are bricks with pure behavior, but all of them are just a declaration, therefore, all the code will be clean and less error prone. It will probably be understandable, flexible, combinable and manageable, in essence - the constructor. Execution of this code can be entrusted to the finite state machine, working on a thin layer of monadic IO-code. And please, we received quite a good architectural solution, thanks to which we also reduced the complexity of formalizing our business processes.

To combat side effects, there is another architectural solution known as " reactive programming ." When applied to functional languages, it is worth talking about FRP, that is, about Functional Reactive Programming. This concept is mathematical, so it fits well with FP. The essence of FRP is to propagate changes to the data model. Each element of such a model is a value depending on other values ​​by the desired formulas. Thus, the “reactive model” is a tree, where leaf values ​​can vary in time, exciting a wave in terms of recalculation of higher values. Sources of values ​​can be any functions, including those with side effects. The model code will be declarative and composable.

In general, in functional programming, the code written in the combinatorial style is the most idiomatic as a constructor. The idea is simple: an arbitrarily large self-applicable system is made up of small bricks of the same type. The better the designer is designed, the more powerful and expressive the code. Usually, the combinatorial code is also some eDSL, which significantly reduces the complexity of development. Many Haskell libraries use this principle, for example: Parsec, Netwire, HaXml, Lenses ... The idea of ​​monadic parser combinators was so successful that Parsec became known outside of Haskell. There are its ports on F #, Erlang, Java, other languages. It is curious that Parsec implements as many as three ideas: combinators, DSL and monads, and all this is organically connected in a single coherent API.

Now it is not difficult to single out another very powerful method of dealing with complexity (the title is author's):

4. Domain-specific combinators.

DSC is an eDSL whose elements are combinators. The most convenient DSCs are obtained in functional languages ​​due to syntax (functions are the essence of transformation combinators), but this is also possible in ordinary languages. Of course, it is even harder to design a DSC than a simple DSL, which is why this approach is probably completely unknown in the mainstream.

Some practice

Moving from abstract thinking to practice, let's turn to the Big Space project of the big game. In short, this is a realistic, space-based 3D spacecraft with real-world scale and fully programmable game elements, and probably with the possibility of time travel. Curious can look into the design document and other related materials for a more detailed acquaintance, and this description is enough for us to think through the general architecture of the game. But first - a small digression.

The beginning of any project lies in the idea, which, being born, requires development and reflection. In the case of Big Space, the main assistants in this were memory cards , which make it possible to realize and structure the key moments of the future game in an excellent way. Starting with generalized concepts (such as "Concept", "Cosmos", "Motivation", "Exploring the Galaxy"), you can go down deeper until you get specific game elements. Memory cards also help to see and eliminate inconsistencies and inconsistencies.


Can memory cards be considered as alternative use cases? Here is an article whose author raises the same question. It follows that memory cards are a more general tool, as they can easily contain use cases. Memory cards answer the question "what is in general, and what solutions in particular," and use cases answer the question "what is allowed to be done to solve the problem." The latter is expressed in the fact that a short story (user story) is usually associated with each use case, in which high-level changes in the system are described step by step. And several of these options will be leverage for which you need to pull the user to the system took the necessary state. It can be concluded that memory cards and use cases correlate in the same way as declarative (in the Prolog style) and imperative programming correlate. In the first case, we describe what we want to get; in the second case, we describe how we want to achieve this. That is, memory cards are more suitable for functional programming, since declarative solutions are encouraged in the FP.

By replacing the use case diagram in the first step, you can go further. Concept cards — relatives of memory cards — are well-suited for displaying requirements for a draft architecture. This is achieved through three stages (the names of the author).

1. Map of need. Contains as large blocks as possible. Links are optional, the blocks are placed on the subject. The map shows what the game is based on. When designing you need to take into account the most general requirements; for example, for the requirements of “huge realistic space”, “3D graphics”, “cross-platform”, there will be Cloud Computing, OpenGL and SDL units. If you need a third-party game engine, you need to designate it here.
2. Map elements. In the free form we open the previous diagram, without worrying about the structure. The elements are such blocks: “subsystem”, “concept”, “data”, “library”, “object of the subject area”. Links show the most general idea of ​​how the system works. You can designate the nature of the relationship, for example: "uses", "implements" and others. Blocks are divided into layers. The diagram should take into account most of the conceptual requirements. It's okay if several levels of abstraction are mixed, competing options appear, or something does not look the best. The diagram only outlines the field of activity and offers possible solutions, but is not the final architecture of the program.
3. Subsystem map. In this diagram, specific architectural decisions are taken from those proposed at the second stage. Information is structured and placed in such a way as to separate the application layers. Libraries and approaches to implementation are indicated. The diagram does not describe a fully high-level design, but will show important dependencies between the subsystems and help to separate them into layers.

The last diagram shows that there are three layers in the game: Views, Game Logic, Application ( Mike McShaffry, Game Coding Complete ). The Views and Game Logic layers are separated from the main code by their own command interpreters and eDSL facades. It is assumed that all game logic, with the exception of the game state, will be implemented outside the IO monad. The game state, although it relates to the game logic, is separate because it requires shared access from the views and from the application side (for network communication, for periodic data upload, for GPGPU and cloud computing). The diagram shows that the Software Transactional Memory concept will be used to work with the game state; also includes the Netwire, SDL, Cloud Haskell, and other libraries. Almost all game logic, according to the plan, should be implemented using several internal and external languages. Of course, the proposed version of the architecture is one of a thousand, and the diagram does not say anything about the lower level of design; research and prototypes are needed to find bottlenecks or miscalculations. But in general, the architecture looks slim and neat.

After the subsystem diagram, you can proceed to the next design stage.Having knowledge of architecture, you can build two models: a data model and a type model, and paint the interfaces of all public modules. Finally, the final step will be the implementation of these interfaces and the writing of internal libraries. But these final stages are already low-level design and implementation. We will review them in part in the following chapters.

Conclusion

The approach presented in this article is downward, that is, directed from the most general to the most particular. We have seen that UML is weakly applicable to OP. Therefore, we designed a high-level architecture, inventing our own diagrams and building our own methodology. We also learned about the methods of dealing with complexity, which we will surely come in handy when designing subsystems.