Version 29
Created by mark.proctor on Oct 1, 2011 3:39 AM. Last modified by mfusco on Jul 10, 2012 7:35 AM.

    Introduction

     

    The purpose of this document is to explore the possibility of adding to DRL some features typically available in functional programming languages. At this stage it has to be intended just as a conceptual brain storming and not an implementation spec. Indeed all the features proposed below will need further investigations to check if they are compatible with the current DRL spec and, if they aren't, how they have to be changed in order to fit the DRL itself. For example in this document I will take for granted that arguments and returned types of drools functions support generics even if this isn't currently true. At the moment I don't see any reason why this couldn't be done and I consider this requirement necessary in order to raise the level of abstraction and reusability of the drools functions themselves. However, if that will not be feasible the biggest part of the ideas presented here will remain valid even if probably in a less general form.

     

    The first paragraphs of this document are mainly a summary of core functional programming aspects. I used them both to provide a quick recap of the theory but also to define some syntactical details (mainly borrowed from F#, Haskell and Scala) of the new functional features I want to introduce in the language. Conversely the last 2 sections are more strictly related to the existing DRL and in particular on how this functional style could improve both the syntax and the functionality of some conditional elements.

    Defining first-class functions

     

    DRL already has a function keyword allowing to declare a first-order function like that:

     

    function int countChars(String name) {
    return name.length();
}

     

    However, in this way, functions are no more than an handy way to define what is corresponding to a static Java method. Indeed it is also possible to import such a method as a DRL function as it follows:

     

    import function my.package.Foo.countChars

     

    Nevertheless this is not enough: a functional language needs first-class function, i.e. a function must be a first-class citizen and then it needs to have an its own type. For example the former countChars function, mapping a String into an int, will be an object of type:

     

    String -> int

    Higher-Order functions

     

    Since functions have their own type, it will be also possible to define higher-order functions, i.e. functions accepting other functions as arguments and/or returning a function as a result. Let me show with a straightforward example why this is useful by allowing us to write more general functions. Suppose we need two functions, both working on a list of Strings. The first one sums up the numbers of characters of all the Strings in the list:

     

    function int sumLengths(List<String> strings) {
    int counter = 0;
    for (String s : strings) {
        counter += s.length();
    }
    return counter;
}

     

    while the second one counts all the Strings starting with an uppercase letter:

     

    function int countUppercase(List<String> strings) {
    int counter = 0;
    for (String s : strings) {
        counter += (s.length() > 0 && Character.isUpperCase(s.charAt(0))) ? 1 : 0;
    }
    return counter;
}

     

    It's immediate to notice that these 2 functions share the same structure and have the same behavior except for how a single string is mapped in an int. If we encapsulate this last thing in a separate function we could abstract the two former functions in a single one:

     

    function int foldStrings(List<String> strings, String -> Int f) {
    int counter = 0;
    for (String s : strings) {
        counter += f(s);
    }
    return counter;
}

     

    After that, passing to this last function the countChars one I defined above, we can have exactly the same result of the one provided by the sumLengths one:

     

    totalLength = foldStrings(strings, countChars);

     

    and in the same way, defining a function returning 1 if a String starts with an uppercase character and 0 otherwise:

     

    function int uppercase(String s) {
    return (s.length() > 0 && Character.isUpperCase(s.charAt(0))) ? 1 : 0;
}

     

    we can count all the strings in our list starting with an uppercase character with:

     

    uppercaseStrings = foldStrings(strings, uppercase);

    Anonymous functions (lambda)

     

    In the last example the need to define the uppercase(String) function just to pass it as an argument to another function could look a bit cumbersome. That's why it could be handy to have the possibility to define an anonymous inline function. In this way the former uppercaseString value could be also obtained as it follows:

     

    uppercaseStrings = foldStrings(strings, s -> (s.length() > 0 && Character.isUpperCase(s.charAt(0))) ? 1 : 0);

     

    Anonymous functions could be also multiple statements long so, for instance, the last example could be rewritten as:

     

    uppercaseStrings = foldStrings(strings, s -> {
    if (s.length() == 0) return 0;
    char firstChar = s.charAt(0);
    Character.isUpperCase(firstChar) ? 1 : 0;
});

     

    Notice that in this last case (as in the former one-statement one) the lambda doesn't have an ending return statement so the value returned is assumed to be the one produced by the last statement of the lambda itself.

     

    Partially applied functions (currying)

     

    Now that we have our generalized foldStrings function, would be great if we could easily create specialized version of it. In other words we would like to partially apply it, by passing to it a subset of the arguments it needs and leaving the others undefined. In functional programming this operation is called curry and allows to define a function with less arguments of the original one by fixing the value of the remaining arguments. For example we could redefine the sumLengths function by currying the foldStrings one is it follows:

     

    sumLengths = foldStrings(_, countChars);

     

    where the _ is a placeholder for a missing argument. More formally this curry operation transforms a function of type:

     

    foldStrings: (List<String>, String -> int) -> int

     

    in one of type:

     

    sumLengths: List<String> -> int

     

    having left undefined the first argument (of type List) and fixed the second one (of type String -> int) to the value countChars, that is a function having exactly that requested type. Of course would be also possible to curry the foldStrings function with a lambda, so the same result could be obtained with:

     

    sumLengths = foldStrings(_, s -> s.length());

     

    We decided to not develop this feature because it will require to have functional types into the Java code of the RHS (the sumLengths curried function of the former example will be of type List<String> -> int). That will further increase the complexity of the Java parser and probably won't be compatible with the upcoming Java 8 specs. At the moement it will also conflinct with the function piping placeholder (see below), so at least a character different from _ should be chosen. Moreover it's easy to see that the same result can be obtained in a just bit more verbose way by the defining another function that invokes the one we want to curry like in:

     

    function int sumLengths(List<String> strings) {
        return foldStrings(_, s -> s.length());
    }

     

    Functions composition and function applications piping

     

    Now let's suppose we have a list of Person and we want a function that calculates the length of the name of the eldest one. We could just do something like that:

     

    function int eldestNameLength(List<Person> persons) {
    Iterator<Person> i = persons.iterator();
    Person eldest = i.next()
    while (i.hasNext()) {
        Person p = i.next();
        if (p.getAge() > eldest.getAge()) eldest = p;
    }
    String nameOfEldest = eldest.getName();
    return nameOfEldest.length();
}

     

    Anyway, for better reuse, we could also split this function in 3 smaller ones. The first retrieve the eldest person from a list:

     

    function Person findEldest(List<Person> persons) {
    Iterator<Person> i = persons.iterator();
    Person eldest = i.next()
    while (i.hasNext()) {
        Person p = i.next();
        if (p.getAge() > eldest.getAge()) eldest = p;
    }
    return eldest;
}

     

    the second that just extracts the name of a person:

     

    function int getName(Person person) {
    return person.getName();
}

     

    and we already have the third that counts the characters in a given String:

     

    function int countChars(String name) {
    return name.length();
}

     

    Of course the findEldest method itself could be rewritten in a more functional way: this will be discussed later. Now that we have these building blocks we can recreate the original function by composing them.

     

    function int eldestNameLength(List<Person> persons) {
    return countChars( getName( findEldest( persons ) ) );
}

     

    Unfortunately this resulting code is not very readable for a twofold reason: function invocations are nested one into the other and are written in a reverse order to the temporal sequence in which they are invoked. To solve this problem we introduce the pipe-forward operator, |> that allows to chain function applications by passing as first argument for a function the result of the application of the former one. In other words, the |> operator pipes the result of a function into the next one, so the eldestNameLength can be rewritten as it follows:

     

    function int eldestNameLength(List<Person> persons) {
    return persons |> findEldest |> getName |> countChars;
}

     

    More formally in this way we have achieved function composition that allowed us to define the function of type:

     

    eldestNameLength: List<Person> -> int

     

    by piping (applying in sequence) the 3 functions:

    findEldest: List<Person> -> Person
getName: Person -> String
countChars String -> int

     

    That makes evident why the function composition we defined works: the returned type of each function is the argument requested by the following one in the pipeline.

     

    In the former examples we used only single argument functions, so there is no ambiguity and it is clear that the value of that argument will be the one produced by the part of the pipeline that comes before of the invoked function. Let's now make the last example a bit more complex by requiring that we want to find the length of the name of the eldest male in our list of persons. To do that we just need one more function that filters only the males from our original list of person:

     

    function List<Person> filter(List<Person> persons, Person -> boolean condition) {
        List<Person> filtered = new ArrayList<Person>();
        for (Person p : persons) if (condition(p)) filtered.add(p);
        return filtered;
    }

     

    Note that here the filter function has been written in a bit more general way, by passing to it another function that determines the condition that has to be used to filter the list of Persons. In this way the requested task could be executed as it follows:

     

    persons |> filter(p -> p.getSex() == Sex.MALE) |> findEldest |> getName |> countChars;

     

    Here we assumed by convention that the argument coming from the former pipeline stage is the first to be passed to the filter function and used a lambda expression to define the filter's condition. If the value coming from the pipeline doesn't correspond to the first argument of the function to be invoked we can define its position with an _ as placeholder. For instance if the argument of the filter function was inverted in its signature we could still use it in our pipeline by writing:

     

    persons |> filter(p -> p.getSex() == Sex.MALE, _) |> findEldest |> getName(_) |> countChars;

     

    In this last statement we put an _ even to invoke the getName function. Of course this is not strictly necessary and can be omitted, but we used it there just to show that the _ can be used also to make clear how many arguments a given function in the pipeline has.

     

    Building a function library

     

    As we already noticed in many parts of this document, one of the biggest winning point of functional programming is reusability. That's why I believe DRL should both provide a rich library of handy and general purpose functions and give the possibility to the user to create its own library that covers her specific needs. For example we could refactor the findEldest function we defined in the former section in a more general findBiggest one, defined as:

     

    function Person findBiggest(List<Person> persons, (Person, Person) -> boolean isBigger) {
    Iterator<Person> i = persons.iterator();
    Person bigger = i.next()
    while (i.hasNext()) {
        Person p = i.next();
        if (isBigger(p, bigger)) bigger = p;
    }
    return bigger;
}

     

    Here isBigger defines the criteria through which 2 Person must be compared, being a function that takes 2 Persons as arguments and returns true if the first one is bigger than the second and false otherwise. In this way we have a more general function that, for instance, allows us to find both the eldest person:

     

    function Person findEldest(List<Person> persons) {
    return findBiggest(persons, (p1, p2) -> p1.getAge() > p2.getAge);
}

     

    and the last one in alphabetic order:

     

    function Person findLast(List<Person> persons) {
    return findBiggest(persons, (p1, p2) -> p1.getName().compareTo(p2.getName()) > 0);
}

     

    Moreover using function piping (and remembering it pipes the result of the former function, a value in the findBiggest case, as the first argument of the argument of the subsequent one) the eldestNameLength function could be now written like:

     

    function int eldestNameLength(List<Person> persons) {
    return persons |> findBiggest((p1, p2) -> p1.getAge() > p2.getAge) |> getName |> countChars;
}

     

    Of course, for being part of a general purpose library, our findBiggest function shouldn't be specialized on Persons but be reusable for any kind of object in the domain model of the user. That's where generics, that we could have safely omitted until this point in the document, becomes indispensable:

     

    function <T> T findBiggest(List<T> persons, (T, T) -> boolean isBigger) {
    Iterator<T> i = persons.iterator();
    T bigger = i.next()
    while (i.hasNext()) {
        T item = i.next();
        if (isBigger(item, bigger)) bigger = item;
    }
    return bigger;
}

     

    That allows us to use our findBiggest function for every type T of object. To give another, slightly more complex, example of that generalization process we could apply it to the foldString function we defined at the beginning of this document:

     

    function int foldStrings(List<String> strings, String -> Int f) {
    int counter = 0;
    for (String s : strings) {
        counter += f(s);
    }
    return counter;
}

     

    to obtain the more general form:

     

    function <A, B> B foldLeft(List<A> as, B zero, (A, B) -> B f) {
    B accumulator = zero;
    for (A a : as) {
        accumulator = f(a, accumulator);
    }
    return accumulator;
}

     

    so we could calculate the total length of a List of Strings by writing:

     

    totalLength = foldLeft(strings, 0, (s, acc) -> acc += s.length());

     

    Proceeding in this way we will develop a set of very general functions that every drools user could import and reuse in her DRL files. Note here that I am assuming the existence of a mechanism to infer the type of the generics used in the function, but this is not mandatory; we could decide to (optionally) specify them with a syntax like that:

     

    totalLength = foldLeft<String, int>(strings, 0, (s, acc) -> acc += s.length());

     

    At the moment we haven't been able to find a mechanism to infer the types of the object passed to a generic function, so their explicit definition, with the syntax described in the former statement, is mandatory.

    Rethinking advanced conditional elements in functional terms

     

    Given the functional features described above, we can now investigate how we could use them to improve the accumulate condition element in terms of both its functionality and syntax. Let's start with one of the simplest example taken from the drools manual:

     

    rule "Average profit"
when
    $order : Order()
    $profit : Number() 
              from accumulate( OrderItem( order == $order, $cost : cost, $price : price )
                               average( 1 - $cost / $price ) )
then
    # average profit for $order is $profit
end

     

    where $profit is the average profit on all items of an order. By using the pipe-forward operator we introduced above and considering a pattern like a source of data that can be piped into the accumulate function we could rewrite the former rule as it follows:

     

    rule "Average profit"
when
    $order : Order()
    OrderItem( order == $order, $cost : cost, $price : price ) |> accumulate( 
                        $profit : average( 1 - $cost / $price ) )
then
    # average profit for $order is $profit
end

     

    The advantages of this syntax are even more evident when, for example, you have to nest another from inside the accumulate:

     

    when
    $order : Order( $orderItems : orderItems )
    $profit : Number() 
              from accumulate( OrderItem( $cost : cost, $price : price )  from $orderItems 
                               average( 1 - $cost / $price ) )

     

    that could be replaced with:

     

    when
    $order : Order( $orderItems : orderItems )
    OrderItem( $cost : cost, $price : price )  from $orderItems |> accumulate( 
                        $profit : average( 1 - $cost / $price ) )

     

    Here the main advantage of the pipe-forward operator, as we already discussed when we introduced it, is that the sequence of how data are processed naturally flows left to right instead of being nested from the internal to the external of the statement. We could push this idea even a bit forward and replace also the from keyword with the |> operator:

     

    when
    $order : Order( $orderItems : orderItems )
    $orderItems |> OrderItem( $cost : cost, $price : price ) |> accumulate( 
                        $profit : average( 1 - $cost / $price ) )

     

    Of course the multi-function accumulates is still possible even with this new syntax, but by leveraging functional programming we could do even better:

     

    when
    $order : Order( $orderItems : orderItems )
    $orderItems |> OrderItem( $cost : cost, $price : price ) |> accumulate( 
                        $profit : average( $price - $cost ),
                        $sumPriceOfRedItems : filter( item -> item.color == "red" ) |> sum( $price ),
                        $itemsMadeInItaly : map( itemManufacturer ) |> filter( manufacturer -> manufacturer.country == "Italy") |> count() )

     

    Here filter is an high-order function accepting a list and another function T -> boolean as argument where T is the type of object on which the accumulate is working. Indeed we used 2 inline functions for our filters but we could also have defined a proper function like that:

     

    function boolean isRed(OrderItem item) {
    return item.color == "red";
}

     

    and then use it in the filter like in:

     

     

    $sumPriceOfRedItems : filter( isRed ) |> sum( $price )

     

     

    In the same way map takes as arguments a list and a function of type T -> S where S is the type of objects in which that Ts (in our case the OrderItems) has to be transformed. In other words we are supposing that there exists a function like:

     

    function Manufacturer itemManufacturer(OrderItem item) {
    if (item.type.equals("pasta")) return new Manufacturer("ThePastaMaker", "Italy");    
    if (item.type.equals("rice")) return new Manufacturer("TheRiceMaker", "China");
    return new Manufacturer("Unknown", "Unknown");
}

     

    Defining inline custom accumulate functions

     

    The functions filter and map, introduced in the former section, are then 2 higher-order functions natively provided by Drools and having the following signature:

     

    function <T> List<T> filter(List<T> items, T -> boolean filterFunc)
function <T, S> List<S> map(List<T> items, T -> S mapFunc)

     

    Once again note that in the former examples we used them with the |> operator so the first argument (the List in these cases) was passed to them as the result of the preceeding function. To allow the definition of inline custom accumulate functions, we could introduce a third, a bit more complex, drools native function acc defined as:

     

    function <S, R, T, V> R acc(List<T> items,
    T -> V toValue, 
    S zero, 
    (S, V) -> S action, 
    (S, V) -> S reverse, 
    S -> R toResult)

     

    Here S is the state of the accumulation, R its result, T the type of the objects to be accumulated each one has to be transformed in a value V before of being accumulated. This last transformation is defined by the function toValue, while zero is the initial state, the functions action and reverse respectively define how to add and remove a value to and from it and toResult finally transform the internal state of the accumulator in the result of the accumulation. This definition resembles (in a more functional style) the syntax of the currently available accumulate conditional element with inline custom code:

     

    <result pattern> from accumulate( <source pattern>,
    init( <init code> ),
    action( <action code> ),
    reverse( <reverse code> ),
    result( <result expression> ) )

     

    To give an example of this feature at work, let's suppose we don't have the predefined sum accumulate function. In this case the sum of the prices of all the OrderItems instead of being retrived as:

     

    OrderItem( $cost : cost, $price : price ) |> accumulate( 
    $sumPrice : sum( $price )
)

     

    could be calculated through the more general acc function with:

     

    OrderItem( $cost : cost, $price : price ) |> accumulate( 
    $sumPrice : acc($price, 0, (s, v) -> s + v, (s, v) -> s - v, s -> s)
}

     

    Here the variable $price actually behaves as a function transforming an OrderItem in a double by extracting the price from the OrderItem via pattern matching. Indeed, if we decided to not use the pattern matching we could achieve exactly the same result with:

     

    OrderItem( ) |> accumulate( 
    $sumPrice : acc(t -> t.price, 0, (s, v) -> s + v, (s, v) -> s - v, s -> s)
}

     

    We decided that a custom accumulate defined with anonymous lambda expressions (despite doable) will result in a quite cryptic syntax and even worse it will be very similar to the one of the already existing (and strongly discouraged) accumulate with inline custom code. Nevertheless we still want to give the possibility to define custom accumulate functions in pure DRL without the need of implementing (and registering in the configuration) a new Java class written ad hoc. For this reason it will be  just developed a new implementation of the AccumulateFunction interface that allows to pass formerly defined functions to it as in the following example:

     

    function Number minFunc(Number context, Number value) {
        return context.doubleValue() < value.doubleValue() ? context : value;
    }
    rule R1 when
        accumulate($cheese : Cheese( $price : price ),
                     $min : acc($price, Integer.MAX_VALUE, minFunc) )
    then
    end

     

    Here 'acc' is the alias of this new AccumulateFunction that is instanciated like all the other custom accumulate function (even if of course needs some special initialization). It is also possible to use a declared type as context for the accumulator and optionally pass to it a reverse and a result function as it follows:

     

    declare AvgContext
       sum : double
       count : int
    end 
    function AvgContext avgFunc(AvgContext context, Number value) {
        context.setSum(context.getSum() + value.doubleValue());
        context.setCount(context.getCount() + 1);
        return context;
    }
    function AvgContext avgReverseFunc(AvgContext context, Number value) {
        context.setSum(context.getSum() - value.doubleValue());
        context.setCount(context.getCount() - 1);
        return context;
    }
    function double avgResult(AvgContext context) {
        return context.getSum() / context.getCount();
    }
    rule R1 when
        accumulate($cheese : Cheese( $price : price ),
                   $avg : acc($price, new AvgContext(), avgFunc, avgReverseFunc, avgResult) )
    then
    end

     

    In the end note that the resulting type of this new accumulate function is automatically inferred from the type returned by the resultCalculator function. This last function (as the reverse one) is optional, so if it is not present it is assumed by default to be the identity function and in this case the result type is inferred as the type returned by the accumulator function.

    List generation, comprehension and manipulation

     

    For list generation we could just use the same syntax already provided by Haskell and F#. So to make a list containing all the natural numbers from 1 to 20, you can just write [1..20], while if you want a list with only the even number in that range you could write [2,4..20]. I don't think it would make sense to provide the possibility of generating infinite lists, until we won't have lazy evaluation at least, but when we will need it, it will be easy to define them by leaving the upper limit unspecified as in [2,4..].

     

    To have list comprehension we could still borrow the Haskell syntax, so to have the double of all the even number less or equal than 10 having a modulo 3 equal to 1 we could write:

     

    [ x*2 | x <- [0,2..10], x % 3 == 1] 

     

    and then obtain the list: [8, 20]. However I'd be more tempted to provide it as another Drools native function named yield and defined like:

     

    function <T, V> yield(List<T> ts, T -> boolean condition, T -> V map) {
    List<V> result = new ArrayList<V>();
    for (T t : ts) {
        if ( condition(t) ) {
            result.add( map(t) );
        }
    }
    return result;
}

     

    so the former comprehension could be rewritten as:

     

    yield ( [0,2..10], x -> x % 3 == 1, x -> x*2 )

     

    In my opinion this last notation has the advantage of being more uniform with what described in the former sections, allowing for example to be combined with the |> operator as in:

     

    [0,2..10] |> yield ( x -> x % 3 == 1, x -> x*2 )

     

    In the end, also list manipulation (and in particular sublist notation) could be achieved by implementing a set of convenient functions like:

     

    head(List l) : returns the first element of a list
tail(List l) : takes a list and return everything but its first element
last(List l) : returns the last element of a list
tail(List l) : takes a list and return everything but its last element
take(List l, int n) : return the first n elements in the list
drop(List l, int n) : return the list without its first n elements

     

    Once again it's worth to note that implementing these features as simple functions also allows to easily use them in conjuction with the |> operator as in:

     

    [0,2..] |> yield ( x -> x % 3 == 1, x -> x*2 ) |> take(12)
    26677 Views Categories: Tags: