Functional RuleML

Harold Boley, David Hirtle, Doan Dai Duong, Le Thi Thu Thuy, Jie Li

Version History, 2006-08-11: Version 0.91

This page describes Functional RuleML (Fun RuleML), which has been incorporated into RuleML since version 0.91. This develops RuleML into a Relational-Functional or Functional-Logic Markup Language (cf. RFML) that can be regarded as being composed of Relational RuleML plus Transformation Rules (Oriented-Equality Definitions of Functions).

Overview
Interpretedness And Valuedness
Nestings And Testing Equations
Defining Equations
Higher-Order Functions
RFML-to-RuleML Translation
Detailed Examples
Functional RuleML DTD

Overview

Varieties of Functional Programming (FP) are playing an increasing Web role, with MathML, XSLT and XQuery being prominent examples. We present here Functional RuleML, whose design benefited from previous work on Transformational RuleML (cf. trans examples) and builds on an earlier paper (cf. Functional RuleML: From Horn Logic with Equality to Lambda Calculus, published in UPGRADE VI(6) and as part of The RuleML Family of Web Rule Languages in PPSWR 2006). Functional RuleML is developed via orthogonal notions and freely combinable with the previous Relational RuleML, including OO RuleML. This will also allow for FP/LP-integrated programming (FLP), including OO FLP.

Since its beginning in 2000, with RFML as one of its inputs, RuleML has permitted the markup of oriented (or directed) equations for defining the value(s) of a function applied to arguments, optionally conditional on a body as in Horn rules. Later, this was extended to logics with symmetric (or undirected) equality for the various sublanguages of RuleML, but the equality element has still often exploited the left-to-right orientation of its (abridged) textual syntax. It was a RuleML issue before version 0.91 that the constructor Ctor of a complex term Cterm was disjoined, as an XML element, from the user-defined function Fun of a call expression Nano, although these can be merged by proceeding to a logic with equality. In particular, while the earlier function-defining bodies needed to specify either Cterm or Nano elements for all levels of function applications, we now use a merged Expr element that carries an attribute to allow Cterm-like, Nano-like, or combined specifications. Moreover, while currently function-defining Nano patterns can contain Cterms but not Nanos, obeying the 'constructor discipline', Nanos could also be permitted within Nanos to legalize 'optimization' rules like reverse(reverse(?L)) = ?L.

Functional RuleML thus conceives both Cterms and Nanos as expression (Expr) elements and distinguishes uninterpreted (constructor) vs. interpreted (user-defined) functions just via an XML attribute interpreted={"no","yes"}. Another attribute likewise distinguishes the (single- vs. set-)valuedness of functions. Equations are introduced that can be 'testing' or 'defining'. We first proceed to the nesting of the two kinds of Expr elements and their use in testing equations. Next, for defining (interpreted) functions, unconditional (oriented) equations are introduced as defining equations. These are then extended to conditional equations, i.e. Horn logic implications with an equation as the head and possible equations in the body. Higher-order functions are finally added, currently named ones such as Compose, and later anonymous ones, i.e. 'in-place' Lambda definitions.

Interpretedness And Valuedness

The different notions of function in LP and FP have been a continuing design issue:

Uninterpreted functions denote unspecified values when applied to arguments, not using function definitions.
Interpreted functions compute specified returned values when applied to arguments, using function definitions.

For example, a function first-born(John, Mary) can be uninterpreted, so that first-born(John, Mary) just denotes the first-born child; or, interpreted, e.g. using definition first-born(John, Mary) = Jory, so the application first-born(John, Mary) returns Jory. Such interpreted and uninterpreted functions are both allowed in Functional RuleML, and are marked up here with a discriminating interpreted attribute in as follows (interpreted on the left, uninterpreted on the right):

<Expr> <Fun in="yes">first-born</Fun> <Ind>John</Ind> <Ind>Mary</Ind> </Expr>
and <Expr> <Fun in="no">first-born</Fun> <Ind>John</Ind> <Ind>Mary</Ind> </Expr>

If the interpreted attribute is omitted, in="no" is now assumed as the default, as proposed by David Hirtle (unlike proposed in the earlier paper). For example,

<Expr> <Fun>first-born</Fun> <Ind>John</Ind> <Ind>Mary</Ind> </Expr>

is equivalent to the above uninterpreted version (on the right).

The rationale here is to preserve the natural extension hierarchy of the RuleML sublanguages, guaranteeing that RuleML 0.91 sublanguages without equality will not need an in="no" attribute setting (on Functions inside Expressions) to preserve their meaning in RuleML 0.91 sublanguages with equality, just as it used to be the case (for Constructors inside Complex terms) until RuleML 0.9. This entails that, e.g., rules from hornlog rulebases can be copied and pasted unchanged into hornlogeq rulebases while preserving their original meaning.

In both XML and UML processing, interpreted functions (like relations in LP) are often set-valued (non-deterministic). This is accommodated by introducing a valued attribute with values including "1" (deterministic: exactly one) and "0.." (set-valued: zero or more). For example, the function children(John, Mary) can be interpreted in a set-valued manner using a definition children(John, Mary) = {Jory, Mahn} , so that the application children(John, Mary) returns {Jory,Mahn} . In Functional RuleML, the example is marked up thus:

<Expr> <Fun in="yes" val="0..">children</Fun> <Ind>John</Ind> <Ind>Mary</Ind> </Expr>

Nestings And Testing Equations

Nestings are permitted for all combinations of interpreted and uninterpreted functions except that inside an uninterpreted function application there can be no interpreted function application. For example, consider the function nesting age(first-born(John,Mary)), where both age and first-born can be interpreted or uninterpreted except that inside an uninterpreted age there can only be an uninterpreted first-born . The resulting three versions of the example can be marked up thus (where "u" and "v" can assume "yes" "yes", "yes" "no", or "no" "no", respectively):

<Expr> <Fun in="u">age</Fun> <Expr> <Fun in="v">first-born</Fun> <Ind>John</Ind> <Ind>Mary</Ind> </Expr> </Expr>

Testing equations can be considered as (inferential) queries performing equality tests (proofs). Nestings as above can be employed on both sides of a testing equation. For example, a fully interpreted version of the testing equation age(first-born(John,Mary)) = subtract(age(John),age(Mary)) can be marked up thus:

<Equal oriented="no"> <Expr> <Fun in="yes">age</Fun> <Expr> <Fun in="yes">first-born</Fun> <Ind>John</Ind> <Ind>Mary</Ind> </Expr> </Expr> <Expr> <Fun in="yes">subtract</Fun> <Expr> <Fun in="yes">age</Fun> <Ind>John</Ind> </Expr> <Expr> <Fun in="yes">age</Fun> <Ind>Mary</Ind> </Expr> </Expr> </Equal>

Here, the Equal element represents an unoriented equation used to test whether its left-hand side evaluates to the same value as its right-hand side does.

Defining Equations

Defining equations are used for function definitions. Let us consider an example defining a function home for a given structured argument:

home(father-of(John)) = Mexico City

This will be marked up as follows:

<Equal oriented="yes"> <Expr> <Fun in="yes">home</Fun> <Expr> <Fun in="no">father-of</Fun> <Ind>John</Ind> </Expr> </Expr> <Ind>Mexico City</Ind> </Equal>

Here, the Equal element represents an unconditional, oriented equation. In general, Equal permits both symmetric (or undirected) and oriented (or directed) equations via an oriented attribute with respective "no" and "yes" values. Since it is more general, oriented="no" is assumed as the default.

Let us consider a variant with an expression on the right-hand side of the equation:

home(father-of(John)) = largest-city(Earth)

In this example assume that the right-hand side expression is meant to call an interpreted function. This leads to the following markup:

<Equal oriented="yes"> <Expr> <Fun in="yes">home</Fun> <Expr> <Fun in="no">father-of</Fun> <Ind>John</Ind> </Expr> </Expr> <Expr> <Fun in="yes">largest-city</Fun> <Ind>Earth</Ind> </Expr> </Equal>

Conditional equations use an oriented Equal element as the conclusion of an Implies element, whose condition may employ other (testing) equations.

For example, using a unary birth-year function in the condition, a nullary this-year function on the right-hand side of the conclusion's Equal, and two variables, the conditional equation (written with a top-level "=>")

?B = birth-year(?P) => age(?P) = subtract(this-year(),?B)

employs an equational condition to test whether the birth-year of a person ?P is known, assigning it to ?B for use within the conclusion. This leads to the following markup:

<Implies> <Equal oriented="no"> <Var>B</Var> <Expr> <Fun in="yes">birth-year</Fun> <Var>P</Var> </Expr> </Equal> <Equal oriented="yes"> <Expr> <Fun in="yes">age</Fun> <Var>P</Var> </Expr> <Expr> <Fun in="yes">subtract</Fun> <Expr> <Fun in="yes">this-year</Fun> </Expr> <Var>B</Var> </Expr> </Equal> </Implies>

With the above age definition, also assuming birth-year(Jory) = 1993 and this-year() = 2006, the age call

<Expr> <Fun in="yes">age</Fun> <Var>Jory</Var> </Expr>

as well as the nested age-of-first-born call

<Expr> <Fun in="yes">age</Fun> <Expr> <Fun in="yes">first-born</Fun> <Ind>John</Ind> <Ind>Mary</Ind> </Expr> </Expr>

return 13, where we moreover assume the earlier first-born definition.

Higher-Order Functions

Higher-order functions are characteristic for FP and thus should be supported by Functional RuleML. A higher-order function permits functions to be passed to it as (actual) parameters and to be returned from it as values. For example, the composition of the age and first-born functions (introduced above), both interpreted, is performed by Compose(age,first-born). This example can be marked up thus:

<Expr in="yes"> <Fun in="no">Compose</Fun> <Fun in="yes">age</Fun> <Fun in="yes">first-born</Fun> </Expr>

Here, as in RFML, Compose itself is marked up as an uninterpreted function, while the enclosing Expr is employed as an interpreted function having the entire Compose application as its structured name. This composition can be applied to two (parental) individuals thus:

<Expr> <Expr in="yes"> <Fun in="no">Compose</Fun> <Fun in="yes">age</Fun> <Fun in="yes">first-born</Fun> </Expr> <Ind>John</Ind> <Ind>Mary</Ind> </Expr>

RFML-to-RuleML Translation

The functional part of Relfun's RFML syntax can be translated into Fun RuleML using the RFML2RuleML.xslt stylesheet, which was adapted from an earlier stylesheet for mapping a Hornlog RFML program into an older version of RuleML. The new stylesheet is designed to map the functional part of RFML into RuleML 0.91.

Detailed Examples

The following are some more detailed Functional RuleML examples, e.g. for testing the translator:

FatherOfJohn in Functional RuleML: FatherOfJohn.xml

and

RFMLFact.xml in RFML: RFMLFact.xml

RuleMLResult.xml in RuleML: RuleMLResult.xml