Thinking Through Some Functional Ideas

I'm working through some ideas on how to move the Utukku/Fabulator expression language more into a descriptive, functional style.  I want to be able to have the programming be exposed as an editorial statement showing how certain calculations are done or inferences are drawn.  The computer's interpretation of the data can be as important as a person's, and knowing what the person was expecting the computer to do can be as important as knowing what the person thought they wanted the computer to do.

With that in mind, I want to walk through a few possible ways of constructing phrases and inference rules to see how they go.  Since my stereotypical example seems to be a concordance, that's where I hope to end up.

The first thing I want to do is describe placeholder variables.  These are slots that will hold values once we start trying to produce actual calculations.  If two slots have the same name, then they need to have the same value.  If a slot is used in a particular way, then we expect that use to introduce a constraint on what values that slot can hold.  Let's call these placeholders something that ends in an underscore (_).  I think we'll need two types.  The first with a single underscore can represent a particular value.  The second, with two underscores, can represent a set of values.  We can also say that, for example, 'x_' is a single value from the set represented by 'x__'.

In Utukku/Fabulator, I've used ':=' to say that the thing on the left is being set to the thing on the right.  The ':' breaks the symmetry so that they aren't identical, but for what we're doing here, I want to say that ':=' allows us to move from the right to the left if we're doing symbolic manipulation of the code.  This might be useful later if we want to allow the humanities equivalent of symbolic math such as we see in Mathematica.  To show that we can't go back from the right hand side to the left side in symbolic manipulations, we can use ':>' which means that when we see the left hand side, we can substitute in the right hand side, but that it's a one-way trip.

Finally, we want the notion of mappings, consolidations, and reductions.  We'll see in a bit how we can fold general functions into these concepts.  A mapping is an expression that can be applied to an element of a set without regarding the entire set.  A consolidation takes a set of values of a particular type and results in a single value of the same type.  A consolidation also has some other properties we'll see in a bit.  A reduction takes a set of values in one type and returns a value in another type, either actual computational type or semantic type (e.g., taking a set of numbers and returning the summation of the numbers).

With this, we can define some simple example functions:

These examples are simple, but the illustrate almost everything that goes into the notation.  Let's walk through each one.

In (1), we say that the sum of a single value is that value.  If we are trying to match a pattern that has a sum of a single value as part of the pattern, and we have a single value, then we can substitute the left hand side for the right hand side (:=).  If this was the only definition of f:sum, then we would also say that f:sum was a mapping.  The 'x_' expects a single value and won't allow in a set of values.  With a mapping, the system will automatically divide up the set and apply the mapping to each value individually.  If we wanted to say that we allowed a set, but that it could only have one value, then we would write it as 'f:sum(x_|)' which says that we expect a set and that we want the first value in x_ and the rest to be empty (there's nothing to match the rest of it).

In (2), we say that we can find the sum of two values (x_ and y_) by adding them together. This is reversible as well, but it will result in a constraint on a set of two values.  This constraint will result in an iterator that generates all pairs of numbers that add to the sum.  In a real system, we probably don't want this since it doesn't generalize well.  Note that (2) only works for sets with two values and won't work with three or one.

In (3), we find the generalization for any size set with more than two elements, though it could work with a set of two elements if we didn't have (2).  This introduces the concept of consolidations as well.  Consolidations are designed so that (3) and (6) are valid.  That is, given a series of results from calling f on a series of sets, the consolidation f* will return the same result as if a single call to the function f had been made with a single set representing all of the sets that f had been called on: f_(x__|y__) :> f_*( f_(x__) | f_(y__) ) for any function f_ for which f_* is defined.

With (4), we see that the way to consolidate a set of sums is simply to sum them.  The summation function is its own consolidation function.

We can then start with counting.  Equation (5) tells us how to count a single item, (6) tells us how to count many items, and (7) tells us how to consolidate multiple counts as a summation.

We could have added several other equations.  f:sum() := 0 and f:count() := 0 are two.

The pattern we have is that we specify how to handle zero, one, many, and consolidation:

That pattern can give us everything we need to handle reductions.

If you're familiar with languages such as Prolog, then you're probably wondering how we know what a function returns.  Prolog doesn't use return values, but instead uses other function arguments to manage the return value.  The result is that a single function can serve multiple purposes.  Of course, they aren't really functions in Prolog, but assertions.  Still, we're using that pattern here as a way to define functions.



Let's explore the idea of a histogram now.

This is a histogram of a single word.  The ({ ... }) notation is used to create a set of named values.  It's a bit like a hash or associative array, but multiple entries can have the same key name and any particular node can have children.  In this case, the result of the histogram function will be a single node with the value passed in as the name and a value of 1.

This transforms the f:histogram from a mapping into a reduction.  Since x__ is a set, x_ is a value in the set.  The result is that the function represents a set of nodes whose names are the values in x__ and values are the number of times the value appears in x_.

The system unifies the two instances of x_ so that they point to the same slot.  A constraint is placed on the slot that it must be a value in the set x__.  If that is the only constraint, then the system will pass each value from x__ through the slot and accumulate the result.

For (2) to work as we want it to, x_ will need to be equal to every instance of the value simultaneously.  This means that when x_ is used on the left of the colon, we need to make it a set of unique values while we allow it to have multiple copies of a value otherwise.

Another option is to not have (2) at all, but keep (1) and use a consolidation to make it work with a set:

The consolidation in (4) illustrates better how constraints are introduced.  The variable y_ can be anything, but it only makes sense if it names a child of x__, which is a set of histograms.  Thus, the system constrains y_ to being the name of a child of x__.  The f:count*(...) consolidates the counts from the histograms that have such a child.



Now we can start looking at what we need to do to create a concordance.  We'll need to create a few functions that can give us the information we need to feed into the concordance calculation.  Then, we can see how we can put everything together.

The first thing we need is a way to retrieve a set of documents.  We can call it 'cms:fetch' and it takes the name of a document.  If we assume a hierarchical arrangements of documents like we might have with Radiant, then we can assume that a document will have child documents.

So far, this looks like we're just doing a histogram of words in the documents, but a concordance is more sophisticated than a simple word frequency analysis.  We need to track where the words appear as well as how often they appear.  To do this, we can add a bit to (1):

What we've done here is added an annotation to the entries in the histogram that denotes the location of the document.  The problem though is that we expect the histogram to produce a set, so we have to make sure that the location annotation is applied to each value in the set.  We also need to make sure that annotations are cumulative across any operations we might do.  We might write this as follows:

That looks like a lot of line noise at this point, but remember that the part between ':>' and '\' is just the way we calculated the consolidation of a histogram.  The part after the '\' keeps any annotations that might have accumulated.  The caret (^) is what I'm using here to note that z_ is an annotation.  This is similar to using an at sign (@) in XPath to denote an attribute.  I'm not sure yet if we want annotations to be different than attributes.



The next thing we can do is a prosopography.

Notice how similar this is to the concordance? The primary difference is that we use 'my:people' instead of 'my:words' in (1). Otherwise, they are identical.

Instead of having two completely different functions, we could have the following set:

Here, t_ is the name of the tokenizer and l_ provides the annotations.  Thus:


The piece in (2) and (5) with the ampersand (&) suffix is a lamda or anonymous function. The single underscore represents the item that it will be applied to at the appropriate time.

Do I expect humanists to be clamoring for this type of notation?  Probably not, unless they also enjoy using Mathematica, but it's a start at building a system that might help us see more clearly the patterns in humanities computing.


Enhanced by Zemanta

2 thoughts on “Thinking Through Some Functional Ideas”

Comments are closed.