LINQ does Logic? Chapter 1

In the zeroth post in this series, we proposed to revisit the curious and alluring Prolog as an approach to computing over knowledge in the current age of trillion-node graphs of entities and relationships that come and go by the millions in the blink of an eye. We set up Prolog against LINQ and Term-Rewriting as alternatives for developing applications and queries and promised to dig deeply.

The beginning questions on the table are

  1. What do typical Prolog applications look like in LINQ and in Mathematica ?
  2. What are the differences in programmability, functionality, performance, scalability?
  3. What criteria can we develop for choosing one over the other in real-world applications?

More questions will certainly arise as we proceed. In this chapter, we’ll just attack question 1: the “look-like” question.

For our Prolog implementation, we choose the original, public-domain SProlog written by Henri de Feraudy circa 1989 and shipped with the Windows NT kernel. This is not hard to find on the web, but I’ve saved you the work and created a Visual-Studio-2010 package for it that you may pick up here. You need 7zip to unpack it.

For hosting our LINQ contenders, we choose the brilliant and free LINQPad. For our term-rewriting contenders, we choose Mathematica, which has a proven core language based on patterns and rules. With Mathematica, we will be able to explore a range of approaches from full-blown Prolog to plain-old pattern-matching and rules because we have Roman Maeder’s competent Prolog implementation in Mathematica.

The first order of business will be to work through Feraudy’s samples to get our feet wet. You will find these in the SPR folder of the the Visual-Studio package. Similarly, you will find Mathematica notebooks in the MMA folder and LINQPad scripts in the LINQ folder.

The first interesting sample — one with facts AND rules, is EXAMPL3.SPR [sic — I will preserve Feraudy’s original “spelling”]. The facts include a number of materials and their specific gravities (densities compared to the density of water).

(density sea_water 1.03)
(density milk 1.03)
(density ethanol 0.789)
(density olive_oil 0.92)
(density petroleum 0.80) (density almond_wood 0.99)
(density apricot_wood 0.89)
(density apple_wood 0.88)
(density walnut_wood 0.8)
(density maple 0.7)
(density poplar 0.45)
(density balsa 0.12)
(density iridium 22.64)
(density lead 11.34)
(density plutonium 19.7)
(density copper 8.94)
(density steel 7.8)
(density mercury 13.6)
(density gold 19.3)
(density diamond 3.51)
(density glass 2.5)
(density sugar 1.6)
(density fat 0.94)

Read these as “the density of sea water is 1.03 times the density of pure water” and so on. The first item (e.g., “density”) in each fact is called its predicate.

In Prolog-in-Mathematica (PiM), the differences are only syntactic. We can’t have underscores — they signify variables as opposed to symbolic constants — and we don’t just blurt out the fact on a line by itself, we must explicitly Assert each fact to PiM:

Assert[density[seaWater, 1.03]];
Assert[density[milk, 1.03]];
Assert[density[ethanol, 0.789]];
Assert[density[oliveOil, 0.92]];
Assert[density[petroleum, 0.80]];
Assert[density[almondWood, 0.99]];
Assert[density[apricotWood, 0.89]];
Assert[density[appleWood, 0.88]];
Assert[density[walnutWood, 0.8]];
Assert[density[maple, 0.7]];
Assert[density[poplar, 0.45]];
Assert[density[balsa, 0.12]];
Assert[density[iridium, 22.64]];
Assert[density[lead, 11.34]];
Assert[density[plutonium, 19.7]];
Assert[density[copper, 8.94]];
Assert[density[steel, 7.8]];
Assert[density[mercury, 13.6]];
Assert[density[gold, 19.3]];
Assert[density[diamond, 3.51]];
Assert[density[glass, 2.5]];
Assert[density[sugar, 1.6]];
Assert[density[fat, 0.94]];

In LINQ / C#, we don’t really have a native way to represent symbolic constants like “density” and “plutonium”. One approach will be to capture “density” as a class and the data for each assertion or fact as properties. We’ll represent the list of assertions as a function that returns an IEnumerable because we’re going to do EVERYTHING with functions and IEnumerables (this is Erik Meijer’s idea). Let’s put everything in strings for the time being, looking ahead to serialization, though we may undo that later.

public class Density
{
    public string Material;
    public string Value;
    public Density (string material, string value)
    {
        Material = material;
        Value = value;
    }
}
static IEnumerable<Density> densities() {return new [] {

    new Density("sea_water", "1.03"),
    new Density("milk", "1.03"),
    new Density("olive_oil", "0.92"),
    new Density("petroleum", "0.80"),
    new Density("ethanol", "0.789"),

    new Density("almond_wood", "0.99"),
    new Density("apricot_wood", "0.89"),
    new Density("apple_wood", "0.88"),
    new Density("walnut_wood", "0.8"),
    new Density("maple", "0.7"),
    new Density("poplar", "0.45"),
    new Density("balsa", "0.12"),
    new Density("iridium", "22.64"),
    new Density("lead", "11.34"),
    new Density("plutonium", "19.7"),
    new Density("copper", "8.94"),
    new Density("steel", "7.8"),
    new Density("mercury", "13.6"),
    new Density("gold", "19.3"),
    new Density("diamond", "3.51"),
    new Density("glass", "2.5"),
    new Density("sugar", "1.6"),
    new Density("fat", "0.94"),
};}

Now the fun starts. We have a rule that says that something can float on water if its density is less than 1.0.  In SProlog, we write the rule as follows

((can_float_on_water Thing)/* conclusion */
 /* if all the following premises are true */
 (density Thing Density)
 (rless Density 1.0)
)

This takes a little getting used to, but it’s always the same: you state one conclusion and then all the premises in a single list enclosed in round parens. In SProlog, variables are distinguished from symbolic constants by being capitalized: Thing and Density are variables, everything else is a symbol. Ok, we run this in SProlog as follows: fire up the console program and keyboard in the following at the ?- prompts:

    ?-(consult "SPR/EXAMPL3.SPR")
    ?-(findall Thing (can_float_on_water Thing) List)

and you should see

    yes
    List = (ethanol olive_oil petroleum almond_wood apricot_wood apple_wood 
    walnut_wood maple poplar balsa fat)

SProlog found all the Things with Density less than 1.0 and put them in our List and told us.

Great. In Mathematica, write our rule like this

    Assert[canFloatOnWater[thing_], density[thing_, d_], d_ < 1.0]

Notice the underscores telling you where you have variables! Write our query like this:

    QueryAll[canFloatOnWater[thing_]]

and get back this beautiful list of replacement rules (much more about these guys later)

{thing->ethanol}
{thing->oliveOil}
{thing->petroleum}
{thing->almondWood}
{thing->apricotWood}
{thing->appleWood}
{thing->walnutWood}
{thing->maple}
{thing->poplar}
{thing->balsa}
{thing->fat}

Suffice to say, the results are the same.

Well, it’s no problem at all to write this query in LINQ, even though we need a bit of noise to convert the strings containing numbers back into numbers, and we don’t get the privilege of using any variable names we want: we must use the property names that we baked into the class. Still, this will not even be a noticeable pain to the LINQ programmer:

void Main()
{
    CanFloatOnWater().Dump("(can_float_on_water X)");
}

IEnumerable CanFloatOnWater()
{
    var results = from d in densities()
		  where Convert.ToDouble(d.Value) < 1.0
		  select d
		  ;
    return results;
}

yielding

(can_float_on_water X) 
IEnumerable (11 items)   
Material Value 
olive_oil 0.92 
petroleum 0.80 
ethanol 0.789 
almond_wood 0.99 
apricot_wood 0.89 
apple_wood 0.88 
walnut_wood 0.8 
maple 0.7 
poplar 0.45 
balsa 0.12 
fat 0.94

We wrote our rule as a function from an IEnumerable to an IEnumerable, in keeping with LINQ’s overarching mandate as a transformation library for collections. And we have seen that these applications and queries don’t look very different at all. I wonder what’s coming up next…

Advertisements

~ by rebcabin on August 23, 2012.

2 Responses to “LINQ does Logic? Chapter 1”

  1. Added a github repo for the sources and samples in this blog at https://github.com/rebcabin/LINQdoesLogic

  2. […] the prior chapter in this series, we investigated sample 3 of Feraudy’s SProlog (resurrected) and recapitulated the […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: