Kernel tutorial
From Omath
Firstly, if you don't already know about the javadoc documentation for the kernel, you should go investigate that. The javadocs are essential, and if you make any changes to the kernel, you should make sure these are reflected in the javadocs.
Learning the interfaces
I'm going to take you on a guided tour of the interfaces in omath. These interfaces abstract out the behaviour of all of the various subcomponents, and determine how they can talk to each other. Implementations of all the interfaces are provided separately, and are replaceable.
Expression
Firstly, expressions. Expressions in omath are represented by objects implementing the Expression interface (or one of its subinterfaces). Although there are various implementations of these interfaces provided by the Tungsten expression factory, you shouldn't assume that all instances of Expression are instances of these particular implementing classes!
The Expression interface itself has few methods: head, returning another expression, leaves, returning a list of expressions, and substituteSymbols. While head and leaves are mostly obvious (although note the contract for leaves -- this is not allowed to be null unless the Expression object is actually an instance of the RawExpression interface), substituteSymbols deserves some explanation.
substituteSymbols takes a SubstitutionsMap as its argument. SubstitutionsMap is a subtype of Map<SymbolExpression, Expression>, and you should think of it as such for now. The method substituteSymbols simply returns the current expression, with any occurences of a symbol appearing the SubstitutionsMap replaced by the corresponding Expression value. This has obvious uses; we need it when applying rules, replacing iterators in Tables, and implementing With.
Next the subtypes. All of these are subtypes of the interface RawExpression, which itself should have no direct implementations. There are four types of RawExpresssions, SymbolExpression, StringExpression, IntegerExpression and RealExpression. The last three are fairly self explanatory. It's worth taking a moment to look at the various methods on IntegerExpression, and note that RealExpression has no implementations as of yet!
SymbolExpression is more interesting! In particular, it has methods pattern, blankPattern, blankSequencePattern and blankNullSequencePattern. These return instances of the Pattern interface. If the SymbolExpression interface represents the symbol h, these Pattern instances represent the patterns h, h_, h__ and h___.
Okay, enough about the Expression interfaces for now.
(Oh -- hang on a sec -- you'll probably want to look at ExpressionFactory as well.)
Pattern
First, open Pattern in javadoc in a new tab.
You might think that Patterns should just be special types of Expressions, and in one sense you'd be correct. In fact, any Expression can be turned into a Pattern object; for this see the PatternFactory interface. However, we want to allow Patterns which don't come from Expressions at all! There are, as far as I know, no implementations demonstrating this, but perhaps you can think of an example yourself.
The Pattern interface implements quite a few methods. The most important of these is substitutions. Of the others, flexible and optional describe whether the pattern can match more than one or zero expressions respectively, and all the attachingSymbol methods identify whether there's an obvious symbol appearing in the head of the pattern, and where it appears; we use this for deciding whether rules should be stored as OwnValues, DownValues or SubValues.
Okay, onto substitutions. Have a look at its method signature. Understand everything? Good. :-)
substitutions takes two arguments -- a List of Expressions (the expressions we're trying to match the pattern against), and a SubstitutionsMap, called previousMatches. The SubstitutionsMap argument tells us which bindings have already been made. (I guess we better do some examples soon!)
(There are actually some other variations, provided as convenience methods -- some which don't require a SubstitutionsMap, and assume an empty one, and the others which take a variable number of Expression arguments, instead of a List, saving you wrapping them up in a List by hand.)
substitutions returns an Iterable of PatternMatchMaps.
What's an Iterable? Well, it's like a List, or a Set, and so on, but very primitive; all you can do is iterate through it. If you know about the Java Collections Framework, you'll know that all the Collections classes implement Iterable. There's nice support in the Java language (1.5 onwards) for Iterables; in particular, say iterable is an Iterable<T> (ie, an Iterable of T's). You can then do something like:
for(T t : iterable) {
System.out.println("I found a T! It looked like: " + t.toString());
}
There are lots of Iterables all throughout the Tungsten implementation of the kernel and pattern matcher; you might like to read my Iterable tutorial (where you can learn how to build towers of Iterable bundles, and fun stuff like that :-).
And what's a PatternMatchMap? It's an extension of SubstitutionsMap, which in turn extends Map<SymbolExpression, Expression>. The additional method it provides is Expression matchedExpression().
Okay, so what's the Iterable of PatternMatchMap's that substitutions returns? Each PatternMatchMap contains all the bindings that appeared in previousMatches (remember, both previousMatches and the PatternMatchMap's being returned are actually Maps from SymbolExpressions to Expressions). It might also contain some new bindings, if the Pattern object we're in has named subparts. Let's do some examples!
Let's say our pattern is f[x__,y__], and for now, previousMatches is an empty map (no bindings have already been made). Let's try and match this pattern against the expression f[1,2,3,4]. We call something like:
"f[x__,y__]".substitutions(Collections.singletonList("f[1,2,3,4]"]), emptySubstitutionsMap);
Here of course the two strings shouldn't really be strings, but the Pattern and Expression objects respectively that represent them. Notice that we have to hand substitutions a List (not an omath list, with braces, but a Java List) of Expressions, even when we only really have one Expression. We see this come into play for flexible patterns later.
What would this method call return? An iterable, which in this case would have 3 elements, which we might write as:
- x->Sequence[1], y->Sequence[2,3,4]
- x->Sequence[1,2], y->Sequence[3,4]
- x->Sequence[1,2,3], y->Sequence[4]
Starting to make sense? Oh - and what would each of the PatternMatchMaps return from matchingExpression? Just f[1,2,3,4] of course.
Sometime later, I'll have a go at explaining how this magic actually works; inside the Pattern object representing f[x__,y__] there are other Pattern objects (a total of 6 actually, including the outermost one -- can you see what they are?), and we recursively call substitutions on these, passing subparts of the Expression we're trying to match.
