Functional RuleML

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


Version history:

2006-08-11 - Version 0.91

2013-04-29 -

Version 1.0

Latest version: ruleml.org/fun/


This page describes Functional RuleML (Fun RuleML), much of which has been incorporated into RuleML since Version 0.91. Fun RuleML develops RuleML into a Relational-Functional or Functional-Logic Markup Language (cf. RFML) that can be regarded as being composed of Relational RuleML plus definitions of generalized functions by oriented equations, either unconditionally (facts) or conditional on premises (rules).

Contents

Overview

Functional Programming (FP) has become increasing relevant in software engineering with languages like Clojure, Erlang, Haskell, Python, and Racket. Varieties of FP are also playing a prominent Web role, with MathML, XSLT, and XQuery being prime examples. We present here Functional RuleML, whose design 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 [talk (ppt)]). Functional RuleML was developed via orthogonal notions and is freely combinable with the previous Relational RuleML, including OO RuleML. This also makes RuleML a language for FP/LP-integrated programming (FLP), including OO FLP (e.g., PSOA RuleML).

RuleML, with RFML as one of its inputs, has long permitted the markup of oriented (i.e., directed) equations for defining the value(s) of a generalized function applied to arguments, optionally conditional on a body as in Horn rules. The two generalizations of functions (allowing their tight, Relfun-style integration with Prolog-style relations) are optional non-ground arguments and/or values (partial data structures) in combination with optional set/multi-valuedness (non-determinism). Later, this was extended to logics with unoriented (i.e., undirected) equality for the various languages of RuleML, but the equality element has still often utilized the left-to-right orientation of its (abridged) textual syntax.

Functional RuleML employs general expression (Expr) elements which usually apply (to zero or more arguments) a contained function (Fun) element distinguishing mainly uninterpreted (constructor, 'self-copying') vs. interpreted (user-defined, 'value-returning') functions via an XML attribute per={"copy","value"}. Another attribute likewise distinguishes the (single- vs. set-)valuedness of functions. Equations are introduced that can be used for 'testing' the value of a function application or for 'defining' the body of a function application. 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. While various subsets of the F(L)P features described here are currently embedded within the languages of the Deliberation RuleML schema family, customizations of RuleML schemas in Relax NG could be performed with the Modular sYNtax confiGurator (MYNG) to carve out the exact schemas of existing and future (OO) F(L)P languages.

Interpretedness And Valuedness

The different notions of function in LP and FP have been a continuing design issue for FLP. When applied to arguments:

For example, a function first-born(John, Mary) can be uninterpreted, so that the application first-born(John, Mary) just denotes the first-born child; or, interpreted, e.g. using equational definition first-born(John, Mary) = Jory, so that the application first-born(John, Mary) returns Jory. Interpreted and uninterpreted functions are both allowed in Functional RuleML, and are marked up here with a discriminating attribute per as follows (interpreted on the left, uninterpreted on the right):
    <Expr>
      <Fun per="value">first-born</Fun>    
      <Ind>John</Ind>
      <Ind>Mary</Ind>
    </Expr>
and
    <Expr>
      <Fun per="copy">first-born</Fun>
      <Ind>John</Ind>
      <Ind>Mary</Ind>
    </Expr>
If the per attribute is omitted, the uninterpreted per="copy" is assumed as the default. 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 languages, guaranteeing that RuleML languages without equality will not need an per="copy" attribute setting (on Functions inside Expressions) in order to preserve their meaning in RuleML languages with equality. 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 application children(John, Mary) can be interpreted in a set-valued manner using a definition children(John, Mary) = {Jory, Mahn} , so that children(John, Mary) returns {Jory,Mahn} . In Functional RuleML, the sample application is marked up thus:

<Expr>
  <Fun per="value" 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 "value" and "value", "value" and "copy", or "copy" and "copy", respectively):

<Expr>
  <Fun per="u">age</Fun>
  <Expr>
    <Fun per="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 per="value">age</Fun>
    <Expr>
      <Fun per="value">first-born</Fun>
      <Ind>John</Ind>
      <Ind>Mary</Ind>
    </Expr>
  </Expr>
  <Expr>
    <Fun per="value">subtract</Fun>
    <Expr>
      <Fun per="value">age</Fun>
      <Ind>John</Ind>
    </Expr>
    <Expr>
      <Fun per="value">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)) = Shanghai

This will be marked up as follows:

<Equal oriented="yes">
  <Expr>
    <Fun per="value">home</Fun>
    <Expr>
      <Fun per="copy">father-of</Fun>
      <Ind>John</Ind>
    </Expr>
  </Expr>
  <Ind>Shanghai</Ind>
</Equal>

Here, the Equal element represents an unconditional, oriented equation. In general, Equal permits both unoriented (i.e., undirected) and oriented (i.e., 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-proper(Earth)

In this example assume that the right-hand side expression is meant to call an interpreted function (perhaps accessing a population table of world cities). This leads to the following markup:

<Equal oriented="yes">
  <Expr>
    <Fun per="value">home</Fun>
    <Expr>
      <Fun per="copy">father-of</Fun>
      <Ind>John</Ind>
    </Expr>
  </Expr>
  <Expr>
    <Fun per="value">largest-city-proper</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 per="value">birth-year</Fun>
      <Var>P</Var>
    </Expr>
  </Equal>
  <Equal oriented="yes">
    <Expr>
      <Fun per="value">age</Fun>
      <Var>P</Var>
    </Expr>
    <Expr>
      <Fun per="value">subtract</Fun>
      <Expr>
        <Fun per="value">this-year</Fun>
      </Expr>
      <Var>B</Var>
    </Expr>
  </Equal>
</Implies>

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

<Expr>
  <Fun per="value">age</Fun>
  <Var>Jory</Var>
</Expr>

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

<Expr>
  <Fun per="value">age</Fun>
  <Expr>
    <Fun per="value">first-born</Fun>
    <Ind>John</Ind>
    <Ind>Mary</Ind>
  </Expr>
</Expr>

return 22, 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 per="value">
  <Fun per="copy">Compose</Fun>
  <Fun per="value">age</Fun>
  <Fun per="value">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 per="value">
    <Fun per="copy">Compose</Fun>
    <Fun per="value">age</Fun>
    <Fun per="value">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 (View Page Source) 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:

and

Functional RuleML DTD

<!ENTITY % term "(Data | Ind | Var | Expr)">
<!ENTITY % ateq "(Atom | Equal)">
<!ENTITY % conclusion "(%ateq;)">
<!ENTITY % condition "(And | %ateq;)">
<!ELEMENT Assert (Implies | %ateq;)*>
<!ELEMENT Implies (%condition;, %conclusion;)>
<!ELEMENT And (%ateq;)*>
<!ELEMENT Equal (%term;, %term;)>
<!ELEMENT Atom ((Rel | Expr | Lambda | Var), (%term; | Rel | Fun | Lambda)*)>
<!ELEMENT Expr ((Fun | Expr | Lambda | Var), (%term; | Rel | Fun | Lambda)*)>
<!ELEMENT Lambda ((%term;)+, %term;)>
<!ELEMENT Fun (#PCDATA)>
<!ELEMENT Rel (#PCDATA)>
<!ELEMENT Data (#PCDATA)>
<!ELEMENT Ind (#PCDATA)>
<!ELEMENT Var (#PCDATA)>
<!ATTLIST Equal oriented (yes | no) "no">
<!ATTLIST Expr	per (value | copy | open) "copy">
<!ATTLIST Rel	per (value | copy | open) "value">
<!ATTLIST Fun	per (value | copy | open) "copy"
		val (1 | 0..) "0..">
<!ATTLIST Var	ord (1 | h) "h"
		per (value | copy | open) "copy">
		

Site Contact: Harold Boley. Page Version: 2015-10-20


"Practice what you preach": XML source of this homepage at index.xml;
transformed to HTML via the adaptation of Michael Sintek's SliML XSLT stylesheet at homepage.xsl (View | Page Source)