Cat-Language.com

Google Code Host External

MetaCat

MetaCat is a macro language for term rewriting based on Manfred von Thun's paper: A Rewriting System for Joy. The primary purpose of MetaCat is as a system for writing optimization rules (such as for function fusion and deforestation). The MetaCat rewriting rules are similar to, but more powerful than the GHC rewriting rules.

A MetaCat macro has the form:

  macro { source_pattern } => { target_pattern }
Some examples of MetaCat macros are:
  macro { swap swap } => { }
  macro { dup pop } => { }
  macro { quote eval } => { }
  macro { [$B] curry } => { quote [$B] compose }
  macro { map $a map } => { $a compose map }
  macro { and } => { quote [false] if }
  macro { or } => { quote [true] swap if }
  macro { unit rev } => { unit }
  macro { unit $a filter } => { $a apply [unit] [pop nil] if }
MetaCat patterns may contain literal names, value variables which start with a lower-case letter (e.g $a or $bOB), and expression variables which start with an upper-case letter (e.g. $A or $Bob).

The current Cat release comes with over 200 optimizing rewriting rules. These can be viewed at http://cat-language.googlecode.com/svn/trunk/macros.cat.

Matching

A macro expresses a valid rewriting rule that can be applied to a program. If some section of code (before or after inline expansion of code) matches the source pattern it may be replaced by the target pattern. This rule may or may not be applied depending on the implementation.

Captured Variables

A value variable matches an expression without side-effects that consumes no values and produces a single value. The macro matcher will typically try to match the smallest expression possibl.

Expression variables are always enclosed in square brackets [ and ], and match the entire expression within the brackets. This will likely be extended in later versions.

Comparing the Cat Macros to GHC Rewrite Rules

Here is an example of the GHC rewrite rule for map-map fusions:

  forall f,g.  map f . map g = map (f.g)
The Cat version is:
  macro { map $a map } => { $a compose map }
Notice that only one captured variable is needed. This means that the Cat macro will still be applied to a wider range of patterns, such as:
  define map_then_inc_all { map [1 +] map }

It is important to note that unlike the GHC rewrite rules, function inline expansion is not prevented by defining rules. A typical optimization heuristic would include alternating phases of macro expansion and inline expansion, mixed with sub-expression evaluation.

Using Macros in the Interpreter

For details on how to enable and use macros with the Cat interpreter see the Cat wiki.

The Cat Programming Language by Christopher Diggins