Feature Algebra README

This is a brief description of a Haskell implementation of Feature Algebra.

0. Prerequisites

The Package requires a Haskell implementation; please see http://www.haskell.org for downloads and installation guides.

We will assume that users of our implementation have at least a superficial knowledge of Haskell. See here for a very brief introduction to Haskell and http://zvon.org/other/haskell/Outputglobal/index.html for a good Haskell reference.

1. Package Structure

The basic module is FeatureAlg.hs. It is a proper Haskell module that needs to be imported into the definitions of particular feature algebras. Samples of usage are provided by the files

    DVD.hs
    Robot.hs

These provide implementations of the DVD player and Robot examples discussed in the accompanying report Feature Algebra.

To use any of these examples, simply load the respective *.hs file into your Haskell interpreter or compiler, e.g.

    :l DVD.hs

2. Main Types and Functions

The main data type, describing the abstract syntax of feature expressions is the following:

   data Feature = Zero
                | One
                | Basic BaseFeature
                | Sum Feature Feature
                | Product Feature Feature
                | Excl Feature Feature

It uses the auxiliary types

   type BaseFeature = String

   type Product     = [BaseFeature] -- interpreted as a bag of BaseFeatures

   type ProdFamily  = [Product]     -- interpreted as a set of Products

One of the main tasks of the module is to normalise feature expressions into a sum-of-products form. To speed up this process, we memoize this normal form and use pairs each consisting of a feature expression and its normal form. This yields the "working type"

   type MemFeature = (Feature, ProdFamily)

To mimic the algebraic notation we introduce the following infix operators that work on objects of type MemFeature

   infixl 5  .+., .-.          -- sum, difference
   infixl 6  .*.               -- composition
   infixl 7  .^., .^<=.        -- power, sum of powers

Moreover, zero and one are the MemFeature representations of the Feature expressions Zero and One .

For abbreviation we introduce an operation for expression optionality of several features:

   opt :: [MemFeature] -> MemFeature

The expression opt [mf1,...,mfn] is equivalent to

   (mf1 .+. one) .*. ... .*. (mfn .+. one)

The refinement relation between product families is

   ref :: MemFeature -> MemFeature -> Bool

After MemFeature expressions have been built up with the above operations, there are two ways of (moderately) pretty-printing them.

The pure sum-of-products form is output by

   printfeat :: MemFeature -> IO()

In the interpreter you simply type printfeat mf , where mf is (the name of) a feature expression, followed by ENTER, to get the normal form displayed.

A more structured output where the features common to all members of a product family are printed up front is obtained by

   print_struct :: MemFeature -> IO()

3. Further Usage

For outputting the result of a normalisation into a file and the like the standard Haskell operations of result type IO() may be used; currently we do not provide special operations for this.

4. Feedback

We are very interested in hearing from users. Please send your comments to

    feature_algebra@informatik.uni-augsburg.de