"Arrows make the input dependence explicit" (John Hughes ).
"When we define the interface to a software component, we want it to reveal as little as possible
of its implementation" (John Hughes)
The concept of arrow
An arrow A b c is an abstract structure that represents a computation A of input type b and returns as output a type c.
Arrows are related to functions, but they are not functions. They are categories of functions: input b and output c functions. The arrows do not explain or detail how c is obtained from b. The arrows are declarative.
The concept of arrow is more general than that of morphism (also called "arrow") in category theory. A morphism is a relation between an object A toward another object B of a category and is represented as A→B.
Arrows provide a discipline for structuring programs. They use the analogy of the circuit. The Arrows language looks like a hardware definition language. Programs look static and you don't see how data is processed.
There are different types of arrows: splitters, switches, delays, integrators, arrow function converters (liftings), etc.
Arrows vs. Monads
The concept of arrow is a generalization of the concept of monad. Being more generic than monads, they solve a wider range of problems.
An arrow is defined with two types (b and c). In contrast, the monad has only one, a. The monadic type M a represents a computation M that returns a. The arrow A b c represents a computation A of input type b and returning output type c.
In arrows the dependence of the inputs is made explicit. Not so in monads. The logic of a program with arrows is made more explicit than with monads.
Monads and functions are particular cases of arrows. Arrows have input and output, like functions, but arrows can have multiple inputs. In monads there is either an input or an output or both (input and output), depending on the interpretation.
The arrows generalize the composition of functions that monads perform. In a functional language without monads and arrows, function composition is limited to a function having as input the result of the preceding function.
Arrows allow parallel computation thanks to multiple inputs. Monads only support sequential computation.
Arrows allow computations to be partially static (independent of input). Neither functions nor monads can handle static information; they only handle dynamic information.
Monads and arrows allow implementing imperative-type side-effect computations. But arrows are more flexible than monads, so they support more combinatorial forms than monads. This allows programmers to arrange a wider variety of side effects than with monads.
Arrows can route data to other arrows at runtime. They have dynamic chaining based on data. Monads have static chaining.
Combinations between arrows produce new arrows. In contrast, monads combine with functions.
Arrows are more expressive than monads, more intuitive and easier to understand. Therefore, programs with arrows are easier to debug than those with monads.
Arrows are easier to implement than monads, although arrows require more design effort than monads, since arrows must satisfy a number of laws (the arrow laws).
Compilers are better optimized with arrows than with monads.
Arrows favor code reuse more than monads.
Arrow operations
arr. It is the main constructor. It converts a function into an arrow.
If we have a function of type b → c, we can construct the arrow of type A b c (we can read it as the arrow A of source b and end c).
Definition: arr :: (b → c) → A b c
>>>. This is the arrow composition operator. It is equivalent to ">>=" (bind) of monads. It puts two arrows in sequence, connecting the output of the first arrow to the input of the second arrow.
Definition: & >>>> :: A b c → A c d → A b d
If the first arrow is of type A b c, the second arrow must be of type A c d. The resulting arrow is of type A b d.
first. Generalizes a (dynamic) arrow A b c into another arrow with a static part d (present at input and output) as the second input and output component.
Definition: first :: A b c → A (b d) (c d)
second. It is the dual operation of first. It generalizes a (dynamic) arrow A b c into another arrow with a static part d (present at input and output) as the first input and output component.
Definition: second :: A b c → A (d b) (d c)
***. Merges two arrows into one, with two types of components.
Definition: *** ::: A b c → A u v → A (b u) (c v)
&&&. Combines two arrows that have the same input into one arrow with both outputs.
Definition: &&&& :: A b c → A b d → A b (c d)
There are really only three primitive combinations, which are the first three. The other three are derived combinations. For example, *** is the combination of first and second.
Example
We have the following chart:
A x y (input arrow x and output y)
A x z (input arrow x and output z)
y+z (sum of the outputs of both arrows)
Arrow transformers.
An arrow transformer is a type of arrow parameterized over another type of arrow, so that arrows of the second type can be matched with arrows of the first type. In fact, this corresponds to the concept of a functor in category theory. With this mechanism it is possible to construct an infinite variety of arrows.
Implementation in MENTAL
In MENTAL, we can make the following considerations:
The horizontal arrow symbol is reserved for the "Condition" primitive. But we can define an arrow as follows:
For example, the arrow A as the class of functions having input a and output b is:
⟨( A(a b) = {⟨( A ←( A(a) = b) )⟩ )⟩
Descriptive expressions can be specified in many ways. For example:
By means of parameterized generic expressions. As in the case of monads, a generalization is implicit in the arrows.
By deferred substitutions (representations).
By specifying only input and output values of functions.
By means of qualifiers.
MENTAL is very suitable for reactive functional programming because every system is integrated in an environment and is part of it. It is very easy to specify interactions with the environment by means of generic expressions (parameterized or not), with changes at the internal level of the system or at the external level.
MENTAL does not introduce laws as in arrows, but degrees of freedom. MENTAL laws are relations between primitives.
The primitives of MENTAL are the universal combinators.
Monads and arrows were invented as complementary abstractions for functional programming languages. MENTAL is a universal paradigm based on primitives that represent degrees of freedom and that represent the supreme abstraction, so that from these primitives it is possible to define other abstractions of lower level. Problems are better solved the higher the level of abstraction.
When a universal language and a universal paradigm are available, there is no point in creating particular paradigm languages unless they are derived from the universal. Paradoxically, a universal language is simpler than a particular language. With a universal language (reflecting a universal paradigm) the egos of the different particular languages and paradigms dissolve.
Addenda
Origin of arrows
The arrow concept was introduced by John Hughes [2000, 2005], as a generalization of the monad concept for the Haskell functional language, motivated by the search for an efficient parser, as an alternative to monad-based parsers, which were inefficient and memory-consuming.
Hughes was particularly inspired by the syntactic parser designed by Swierstra and Duponcheel [1996], which consisted of two sequential components: a fast (static) one, which evaluated in a general way whether the input was worth parsing, and a slow (dynamic) one that performed the detail work. The notation Hughes used was point-free.
Ross Patterson [2001] introduced a new, more user-friendly notation with which some laws could be expressed directly. But this new notation turned out to be insufficient for the general treatment of arrows.
Although Hughes' paper appeared in 2000, with the parsers arrow style, a practical implementation did not become available until May 2005: PArrows, developed by Einar Karttunen.
Since Hughes published his first definition in 2000, the laws and operations have been redefined several times. Recent formalizations [Lindley et al. 2010] require only 5 laws.
Applications of arrows
Arrows are being applied in: parsers, circuit design, and metaprogramming (programs that generate programs). And also in two special fields:
Reactive functional programming. This is a type of programming in which the inputs to the system are not known a priori. The system interacts with the environment through inputs and outputs, returning a value as a response from the system after a predetermined time, and continuing its execution cycle. This programming paradigm is used for computer animation, mobile robotics, humanoid robotics, real-time systems, parallel processing and graphical user interfaces.
Point-free programming. The point-free programming style, also called "tacit programming" consists in the fact that functions do not have prefixed or identified arguments (the "points"). The expressions are formed by composing functions, among which are the combinators that manipulate the arguments. The point-free style is convenient for setting general properties, but awkward for specific definitions. Arrows provide a more natural syntax for this type of programming.
Bibliography
Asada, Kazuyuki. Arrows are strong Monads. Internet, 2010.
Flechas en Haskell y otros artículos sobre flechas. http://www.haskell.org/arrows.
Hughes, John. Generalizing Monads to Arrows. In Science of Computer Programming, 37: 67-111, May 2000. Disponible online. (El artículo clave sobre flechas. Explica también el concepto de mónada).
Hughes, John. Programming with Arrows. In 5th International Summer School on Advanced Functional Programming, LNCS 3622, pp 73-129, Springer, 2005. Disponible online. (Una introducción a las flechas y su notación).
Jacobs, Bart; Heunen, Chris; Hasuo, Ichiro. Categorical Semantics for Arrows. Journal of Functional Programming 19 (3-4): 403–438, 2009.
Lindley, Sam; Wadler, Philip; Yallop, Jeremy. The Arrow Calculus. Journal of Functional Programming 20 (1): 51–69, January 2010. Disponible online.
Lindley, Sam; Wadler, Philip; Yallop, Jeremy. Idioms are oblivious, arrows are meticulous, monadas are promiscuos. Internet, 2008.
McBride, Conor; Paterson, Ross. Applicative programming with effects. Journal of Functional Programming, 18 (1): 1-13, 2008.
Moggi, Eugenio. Notions of computations and monads. Information and Computation, 93 (1): 55-92, 1991.
Paterson, Ross. A New Notation for Arrows. In ICFP, Firence, Italy, pp. 229-240, Sep. 2001. Disponible online. (Una nueva notación para las flechas, que está disponible en el compilador Haskell de Glasgow).
Paterson, Ross. Arrows and Computation. In The Fun of Programming, pp. 201-222, Palgrave, 2003. (Presentación general sobre flechas).
Swierstra, S.D.; Duponcheel, Luc. Deterministic, error-correcting combinator parsers. In Advanced Functional Programming, 1129 of LNCS-Tutorial, pp. 184-207. Springer-Verlag, 1996.
