Functional programming is all about being able to compose functionality. This ability is related to the glorious category theory that emphasizes maps (arrows) over objects. Being slightly controversial, I would claim that functional programming languages should primarily strive for that simplicity to compose, i.e., linearly augment things, rather than getting bogged down in difficult to read syntax and detailed refinement.
The Prova extension for functional programming attempts to do away with the proliferation of syntactical constructs and distill that easy composability. What has been done so far is by no means complete but it offers a number of immediately useful features such as
- single- and multi-valued functions, the latter offering direct support for non-determinism and backtracking;
- functional composition with the extended derive built-in;
- partial evaluation;
- lambda functions;
- monadic functions;
- monadic bind using a composition of map and join;
- maybe, list, state, fact, and tree monads as part of the provided library with easy extensibility;
- combination of monads;
- stream fusion capability.
In order to utilize the functional extensions in Prova, you need to consult the utility library functional.prova from your rulebase. This rulebase is available in the directory rules/reloaded of the Prova source or from the rules directory of the binary distribution.
From the source code Prova distribution, you can also run the tests in ProvaFunctionalProgrammingTest.java to find out what is available.
Representing functions
Prova allows the user to define functions using facts and rules obeying a number of simple conventions.
- Functions are defined via rules for arity 2 predicates whose predicate symbol then becomes the function symbol.
- The first argument is the input and the second argument is the output of the function.
- If the input (output) is a simple term, this corresponds to a one input (output) parameter function.
- Otherwise, the input (output) is a Prova list, corresponding to multiple input (output) parameters.
- The only exceptions to rules 4 and 5 are Prova lists beginning with strings maybe, list, state or tree, in which case those are treated as a single input or output parameter.
Consider some examples.
The first two of them should be self-explanatory while the third generates a state monad representation with equal value and state. The last example is non-deterministic and defines a multi-valued function that takes a number and either echoes it back or returns its negation.
Beginning with Prova 3.0.4, functions can be specified using a direct functional syntax that reduces the number of required brackets:
For example, the above plusminus function becomes:
This is a function that computes a square:
The function calls are specified using the same pattern but obviously without the function body.
Functional composition
Remember that everything about functions is about composition. Prova currently offers two mechanisms for composing functions: simple composition and monadic composition.
In both cases, Prova currently requires a built-in predicate derive to be used for executing functional pipelines. The functional flavor of derive takes a single parameter, which is a Prova list with exactly three elements:
- functional pipeline,
- input,
- output.
Let us see some examples.
The functional pipeline is represented by a single function (double in the first example), a partially evaluated function (add(1) in the second example, note the required square brackets around it), a lambda function described later, or a list of those, executed in sequence (double,add(1) in the last example).
The input and output can be pretty much any simple or compound Prova terms. In the case when output is specified, Prova will unify the results with the provided pattern, only succeeding if there is a match, which allows for easy constraint solving using normal backtracking if there is non-determinism encountered along the way, perhaps due to multi-valued functions.
Lambda functions
We need one more building block to fully appreciate functional composition, viz., lambda functions. Lambda functions can be used directly in function pipelines for specifying a function right there as opposed to using pre-defined functions defined using rules. One advantage is immediate flexibility and the ability to define and pass around lambda expressions even between distributed agents. A more direct advantage is the ability to obtain access to data available from the previous stage of the pipeline and use them precisely in the lambda expression, as opposed to the default splicing of that data at the end of the current function arguments.
The syntax is simple:
Here Var is a variable that gets instantiated to the data coming from the input. Function is again either a single (possibly, partially evaluated) function or a list of functions representing a nested functional pipeline. Note that Function is not required to include Var. Note that lambda variables are visible and can be used in all subsequent functions in the enclosing pipeline which is a great way to pass the data downstream.
Simple functional composition
In the case of simple composition, the functional pipeline is composed of functions operating on the totality of the values being passed between them. To appreciate the power of functional composition, we would like to pass between functions compound data as opposed to single values. Consider the following function.
Whatever the X value, the function creates a two-element list with two identical copies of the same value (or structure, if X is also a list). Following is an example of its use.
What happens here? First, the simple value 3 is transformed into the list [3,3]. Then these two numbers (3 and 3) get shipped as the first two parameters to the function add, returning the result. The apparent inflexibility of always attaching the computation results to the end of the next function's arguments is nicely resolved by using lambda functions.
Now finally if the input is a list, the lambda function needs to accept more than one variable by declaring its input as a list.
Now we are completely ready for FizzBuzz, functional Prova style. We are going to show three ways to do the same thing and later do the same again using the List monad. Note that for is a multi-valued function that non-deterministically returns all integers between 1 and 100 (its definition is very simple and is part of the utility library functional.prova). prtln is a function that echoes back its input while printing it followed by newline.
Monadic functional composition
In the case of monadic composition, the functional pipeline passes around monadic data and is composed of functions operating on data in some form "contained" in the monadic data. Monadic composition in Prova is done by pattern-matching the data passed between functions in the functional pipeline.
To clarify, this approach is not directly comparable to the one used in functional programming languages. The latter is based on strong typing enforced at compile-time. Prova is obviously quite a bit more dynamic so the approach used here is data-driven. In the following discussion, we assume minimal understanding of what monads are about (see, for example, this compact post: http://www.haskell.org/haskellwiki/Monads_as_containers).
The core idea is that monadic functions produce Prova terms matching pre-defined patterns known to the functional framework.
The Maybe monad
This monad is represented by Prova terms (recall that Prova terms are represented as Prova lists with the first element equal to the term symbol) that match either of these two patterns:
It captures the intuition of a computation that either produces a result or returns a ?no-result?, for example, a NaN value resulting from a division by zero. Now consider the following monadic function (halve_f :: a->Mb in Haskell):
This function halves a number but returns a Nothing if the input is 0. The following monadic functional pipeline halves a number a few times, eventually resulting in Nothing.
The pipeline is composed of (join . map(f)) paired compositions. The map function opens monadic data and operates on its contents (the payload inside just()). This is mathematically represented as Ma->MMb function in Haskell. The join function then unwraps a double wrapped result: join: MMb->Mb so the final result is again in the Maybe monad form and can be shipped to the next computation stage. The composition of map and join is known as bind and is the key combinator allowing the monadic functions f: a->Mb to be composed into Ma->Mb thereby allowing for such transformations to continue.
The List monad
The list monad is represented as a Prova list of the form: [list,e1,e2,...,en], which is the same as list(e1,e2,...,en). The monadic functions for lists operate on individual elements and produce lists (mapping simple data to monadic data). For example, the following function duplicates an element.
Here is a pipeline that uses map followed by join (which is the concatenation operation for lists).
This is an example of a function that filters a list elements based on the filter function.
The above function wraps the input number A if it is greater than X, otherwise, it returns an empty list. Now filtering a list is as simple as:
The State monad
The state monad is represented as a Prova list of the form: [state,[Value,State]], which is the same as state([Value,State]). It captures the intuition of a function that not only transforms its input Value but also causes a change in its environment, represented by the State variable. The state monadic functions never change the initial state, instead they output a new value for the state.
Consider the following state monadic function. It flips the state and converts the input to uppercase if the initial state is true, or to lowercase, otherwise.
Now execute the following pipeline.
We recover the original value and state after executing two flips, which is not surprising. The State monad, of course, has a lot of uses that we are not discussing here.
The Fact monad
Prolog-like languages typically have problems dealing with their fact bases, in particular, as updating the existing facts is problematic. Retracting a fact and adding a new version (a) may change its position among the facts for the same predicate and (b) it is not efficient.
Prova makes use of the functional approach to provide an in-place fact editing. For this to work, we introduce monadic terms of the form: [fact,Pred] that encapsulate computations on facts (see the examples in func_fact_monad.prova). In order to modify the existing facts, one writes a monadic fact transformer function that takes a term stored in a fact (along with any additional data) and generates an updated fact term. The system then replaces the original fact on the spot. Note that the transformer function itself is a pure function. Internally it does not change the fact but just produces a new fact term.
The following example demonstrates how we can use the Fact monad.
Executing update_1 above will increment the second argument of each fact for predicate data that has 2 in the second position (the facts data(1,2) and data(3,2) are replaced with data(1,3) and data(3,3), respectively).
Combining monads
The presented data-driven monadic approach is well suited for combining different monads. It only sounds too complicated but in fact, is easy to understand and use. This is a real problem: we want to modify the facts (using the Fact monad) but also to count the number of occurred modifications. Obviously, we want to use pure (side effect-free) functions so global variables is no the solution we are looking for.
Here is the upgrade of the previous example.
This works by nesting a fact monad term inside a state monad term and passing this as the input to the pipeline. The function in the pipeline is a nested map that applies the supplied lambda function to the fact terms F(X,Y) as they are discovered by the matcher, along with auxiliary data D and the current state variable S. Both the fact term and the state variable then are transformed to new values. The pipeline that inspects the monadic data takes care of the rest: it threads the state to the possible next stages of the pipeline and updates the fact on the spot before iterating to the next fact matching the supplied pattern data(X0,2).
Stream fusion and unfoldr
Functional pipelines have a lot of value in terms of conceptual clarity and, in the monadic case, also hide appropriate combinators that are based on the types of the data passed between stages. However, if one compares what actually happens when the standard pipeline is run, one will see (this is true not only in Prova but also Scala or Haskell) that the full containers (for example, lists) get created at each stage of the pipeline. This is a lot of waste and is clearly different from the way an imperative program with loops typically would do. The latter operate on individual data one at a time passing it along the pipeline and then iterating to the other contained data.
The technique called stream fusion allows one to write functional pipelines the usual way but fuse the transformations and execute them iteratively, producing one final result at a time.
The function unfoldr is a hidden gem in the Haskell arsenal that builds streams from a seed and a step function, outputting results one by one as they are produced. It is close in spirit to stream fusion and in our approach, can be used together with other functional transformations operating on lists or streams.
Consider a Scala function:
This is what we want to compute but the way Scala does it, creating full intermediate lists, is not how we will do it. This is our code (see the example func_010.prova).
The input to our pipeline is a list list(1,-1,3,11) and a seed 0 wrapped in a State monad term. We map a composition of functions a and b to the list elements. The function a transforms the supplied value while keeping the state. The function b wraps the result value in a list monad term and increments the state variable if the value passes a test. Otherwise, the state stays the same and the generated list term is empty. The net result of running this is that the transformed elements are included in the generated list and the state is the cumulative sum of these terms.
Internally, this works very much like a pure iteration with recursion unfolded and no intermediate structures created, apart from the results used for one input element at a time.
The example func_011.prova shows how you can operate on more than data structure at a time, in this instance, zipping the two lists, while running it with a state monad. It is as simple as passing two lists inside a State monad on input and redefining the per-element functions to work on pairs of data.
The following final example func_012.prova shows how a Fibonacci series can be constructed using what closely resembles the unfoldr function.
The input is again a State monad term that wraps a list with an empty element (effectively signalling that we are not consuming elements from any actual list but simply generating a list from other available data) and a Maybe monad term with initial pair of the Fibonacci series. We output the series elements until the output element is equal to the supplied value (5). The function fibs does not require any input list elements, effectively operating indefinitely. It generates a new pair of results wrapped in a Maybe monad, in this case, always a valid value (a Just, not a Nothing). This result is shipped to the until function that only returns a Just in the case the result does not pass the completion test. Otherwise, it outputs a Nothing. The pipeline considers the computation to be complete when the state variable becomes a Nothing and the output contains the expected series (with the exception of the first two elements).