Expression Pattern Language (eXPL)

A Practical Mix of Two Programming Paradigms

Expression Pattern Language (eXPL) combines two programming paradigms: Logic and Imperative. This fits well with how the mind works using patterns to find and shape soutions to problems. The Logic paradigm is manifest in the following ways:

  • A query defines the program goal
  • Data structures combine when logically equivalent
  • A solution is found by chaining together modular evaluation stages

However, eXPL is not like a logic programming language in that it allows procedural instructions to be used to arrive at the solution. This in contrast to the expectation that the program declares a problem which the underlying system works out how to solve.

The mix of paradigms started as an experiment, with inspiration from the "Logikus" logic programming language developed for the book "Building Parsers with Java" by the late Steven John Metsker, published in 2001. Here is a eXPL example of a simple query, originally implemented in Logikus. It selects from a list, cities at elevation above 5,000 feet:

axiom city()
{"bilene", 1718}
{"addis ababa", 8000}
{"denver", 5280}
{"flagstaff", 6970}
{jacksonville", 8}
{"leadville", 10200}
{"madrid", 1305}
{"richmond",19}
{"spokane", 1909}
{"wichita", 1305};

template high_city(name ? altitude > 5000, altitude);

query<axiom> high_cities (city : high_city);

The console output when the query is run is:

high_city(name = addis ababa, altitude = 8000)
high_city(name = denver, altitude = 5280)
high_city(name = flagstaff, altitude = 6970)
high_city(name = leadville, altitude = 10200)

The query, named "high_cities" unifies "city" axioms with the high_city" template to create a solution as a list of axioms. Both axioms and templates are unification structures, but are polarized so axioms can only interact with templates. The query format declares unification pairing using the (axiom:template) notation. As can be seen in the solution, each successful pairing results in an axiom being created with the same name as the the template and containing terms copied from the template.

Now taking a closer look at the high_city template, you can see the first term is this expression: name ? altitude > 5000. This reads as "name of city at altitude greater than 5,000 (ft)". and does 2 things:

  1. Gives the template term an identity = name
  2. Short cuts if altitude > 5000 is false

Short cutting is like error recovery by going back to a previous point in the program where the last axiom was read, then reading the next axiom and moving forward again. When unification proceeds all the way to a solution, the same mechanism is employed but, in this case, it is called "backtracking".

Resources

Open Source License

GPLv3 license

Support
classy_tools@aapt.net.au