Junkyard Wars: Rule-Based Programming Language

Prologue

Primary participants:
zarf: Andrew Plotkin
wilja: William Byrd
Doug: Doug Orleans
Additional commentary by the IFMud crew

zarf says, "I will be logging this channel"

zarf says, "http://docs.google.com/View?id=dxq2kkf_0dzcswpgh"

zarf says, "sorry, I'm a little ahead of you. :)"

zarf says, "let me know what address I should add to the doc access list"

yandexx asks, "that google doc should auto-update, right?"

zarf says, "yes"

wilja says, "again"

zarf says, "aha"

wilja says, "I think I've figured it out"

wilja says, "I needed a slash in front of the hash"

wilja says, "Zarf, you need my ipaddress"

wilja asks, "???"

zarf says, "your google mail address"

zarf says, "I'm sure I had it already, but some people (like me) use multiple google accounts"

zarf says, "you should get an email invite, or go to http://docs.google.com/Doc?id=dxq2kkf_0dzcswpgh"

wilja exclaims, "We're in!"

wilja asks, "Do you need to create a doc first?"

zarf asks, "are you looking at the doc page?"

wilja says, "Yep"

zarf says, "that's it. :)"

Iron Geek Language Design: Rule-Based Programming
June 12, 2010

zarf says, "so how do we want to do this? I don't have any clear working structuer in mind."

wilja says, "Neither do we."

Simple general-and-specific rules

wilja says, "Maybe we can begin with some examples"

wilja says, "Perhaps a simple program from your slides"

zarf says, "okay"

zarf says, "don't take my syntax as anything but pseudocode, though"

The format I've had in mind (for years) is:

do ATOM as CODE if CONDITION;

The ATOM can have parameters (I think?) Examples:

do Description(obj) as "Nothing special." if true;

do Description(obj) as "It's valuable."   if IsTreasure(obj);

do Description(obj) as "It's a diamond!"  if (obj is HopeDiamond);

wilja says, "Okay"

wilja says, "How about one of the longer examples"

zarf says, "I have added Cassie to the doc"

wilja says, "How about o"

wilja says, "showing the overload rule"

wilja says, "showing the overload rules"

zarf says, "oh, introductions, would be wise. This is William Byrd, author of some logical-programming books"

zarf says, "Cassie Orr is part of this but not on the mud, I guess."

wilja says, "And with me is Cassie Orr, IF fan and Schemer"

wilja says, "We've heard of Emily from your slides"

zarf says, "so, that (on doc) is the basic example of a rule with two levels of customization"

wilja asks, "So 'is' is equality?"

zarf says, "I have been nudged to introduce myself too, for the benefit of postering. I'm Andrew Plotkin"

zarf says, "er, posterity"

zarf says, "which is to say, anybody reading this as a log"

zarf says, "anyhow"

zarf says, "yes, I'm using 'is' as object identity"

wilja asks, "Are you envisioning more than one notion of equality?"

zarf says, "I figure the way most dynamic languages handle equality, with a couple different operators but you mostly stick to one of them"

zarf says, "I'm also assuming we have a run-of-the-mill type system for numbers, strings, and booleans"

wilja says, "One big question is how the system will determine specificity"

wilja says, "One big question is how the system will determine specificity"

zarf says, "yeah"

wilja asks, "How does the system know the HopeDiamond is more specific than treasure?"

zarf says, "right"

wilja asks, "Is it because IsTreausre is a predicate, whereas HopeDiamond is a specific object?"

zarf says, "yes"

zarf says, "this is where I vaguely envision saying elsewhere 'Do IsTreasure(HopeDiamond) as true'"

In this case, IsTreasure is itself a predicate:

do IsTreasure(obj)         as false;

do IsTreasure(HopeDiamond) as true;

That latter line is equivalent to:

do IsTreasure(obj) as true if (obj is HopeDiamond);

zarf says, "and letting the compiler work out that one line implies the other"

zarf asks, "is that something that software can plausibly do?"

wilja says, "Possibly"

wilja asks, "Are predicates allowed to have side-effects?"

zarf says, "I'd like to have nothing *but* predicates, so some of them will have to have effects on the state of the world."

zarf says, "hm. unless we include state-changing as a kind of override..."

zarf says, "for logical deduction purposes, we could mark some predicates as having side effects and let the rest be 'safe'"

wilja says, "If IsTreasure has a side-effect, is calling IsTreasure(HopeDiamon"

wilja asks, "If IsTreasure has a side-effect, is calling IsTreasure(HopeDiamond) safe?"

wilja says, "I would think at a minimum the side-effect would have to be idempotent"

zarf says, "I'd just call it 'unsafe'"

wilja says, "I mean, the predicate would have to be idempotent"

zarf says, "That is, if the compiler is being all clever and doing deductions at compile-time, it will have to stop deducing at predicates that involve run-time state"

zarf says, "so if IsTreasure changes during the game, the specificity checker may give up"

wilja asks, "Is it necessary that the language be efficiently compilable?"

wilja asks, "What about something extremely dynamic, like smalltalk?"

zarf says, "mind you, I don't even know how to write a "simple" specificity checker that knows that (x==3) is more specifc than (x>1)"

zarf says, "or (x && y) is more specific than (x)"

zarf says, "being efficiently compilable is... kind of hard to get out of my head, since I've been worried about Inform efficiency for years"

wilja says, "We could probably implement a simple specificity checker without much difficulty"

Digression about Inform

wilja asks, "Is Inform compiled?"

zarf says, "I'm glad to hear that"

wilja asks, "Bytecode?"

zarf says, "yes, Inform is compiled"

zarf says, "to bytecode. It's all 1980s technology"

wilja asks, "Does the compiler do any real optimizations?"

zarf says, "no"

wilja says, "We could take the Pascal approach and distiguish between side-effecting and non-side-effecting operations"

zarf says, "I'm fine with that."

wilja says, "Unless you want to go the monad route and be all Haskelly"

zarf says, "I don't know enough about Haskell to want that. (sigh)"

wilja says, "With the Pascal route, the user explicitly states if a prediate is unsafe."

zarf says, "I keep thinking that state change should be more fundamental to the system than "here, write some bytes into memory" but I don't have a better idea in mind."

zarf says, "well, I guess the 'assigning value at runtime' slide on my talk is a better idea, but I don't know if it's a *good* idea."

wilja says, "There's a notion of region-based memory access, where different memory locations are treated differently."

wilja says, "this can make analysis easier, but may be overkill."

zarf says, "(now I'm looking at a page on monads and it doesn't help.)"

wilja says, "Cassie says that is not surprising."

wilja says, "Monads are really wac."

wilja asks, "From your experience, what is slow about Inform?"

wilja says, "Because I'm thinking, for the initial language design maybe we should just be as dynamic as possible."

zarf says, "speaking most generally -- Inform is slow when too much stuff is done at runtime which ought to be set up at compile time."

wilja asks, "To what extent do you have to worry about that efficiency when you write the games?"

zarf says, "quite a bit."

wilja exclaims, "Okay, sounds like we're compiling!"

zarf says, "to indulge in a side lecture:"

zarf says, "I think of language features like "object properties" as compile-time optimizations of big boring tables (the sword weighs 20 pounds, the lamp weighs 10 pounds, ...)"

zarf says, "in a predicate-based world you have all these associations, and putting a property on the object itself is just a way to look up one associated value in constant time."

zarf says, "Inform does a lot with properties, but you can fall off into some other less efficient form (say, a *computed* associated value) and after a few days of work you realize you've got many nested loops working out this one action, and it's all n^4"

wilja asks, "Okay, so the question is, how often often does the same boring, tabular data get referenced? And is memoization or tabling desirable or efficient?"

zarf says, "that danger is probably ineradicable. My notion is that if there's one underlying mechanism which *can* be used simply, it will be simple most ofthe time"

wilja says, "*sufficient, not efficient"

zarf says, "memoization is certainly helpful. I would be delighted if it were sufficient"

Defeasible logic and specificity

wilja asks, "Why did you think that defeasible logic was a dead end? Is it too theoretical or does it not solve the problems you want to solve, or what?"

zarf says, "mm, I haven't actually look at those papers for a couple of years"

zarf says, "(I do have them piled up here...)"

Doug says, "I wrote a "simple" specificity checker..."

wilja says, "Tell us about it."

Doug says, "it was based on predicate dispatching... looking for the paper now."

Doug | http://www.cs.washington.edu/research/projects/cecil/pubs/dispatching.html

wilja asks, "Zarf, what do you think the major technical or design problem is? Is it figuring out how the specificity rules should work? Or perhaps their interaction with state?"

Doug says, "an earlier paper described the language, and a less efficient implementation. http://www.cs.washington.edu/research/projects/cecil/pubs/gud.html"

zarf says, "the major technical problem is specificity checking. The major *design* problem is coming up with predicate-based ways to express ordering (including ordering of rules for predicates!) which (a) can be implemented efficiently and (b) don't drive the author insane as the program grows."

Doug says, "the basic trick is to see if you can simplify (if P then Q) to true, in which case P is more specific than Q"

zarf says, "at least, those are the hurdles that have stopped me implementing (on the one hand) and designing (on the other)"

zarf says, "hm yeah"

wilja asks, "Doug, do you know the running time of the specificity checking algorithm?"

Doug says, "which is the same as ((not P) or Q). so in the case of P = x && y, Q = x, you get ((not (x && y)) or x) = (not x) or (not y) or x, which is a tautology because of ((not x) or x)."

zarf says, "I've been assuming that the same techniques also help with other optimization problems, like taking a set of predicates "x(O1) = 10; x(O2) = 20; ..." and recognizing "this would be a great place to build a property or a hash table"

Doug says, "it's exponential in the length of the predicates, but predicates are not usually more than a few terms."

zarf says, "right"

Doug says, "and there are some shortcuts"

zarf says, "that sounds amenable to substituting other known (safe) predicates like the IsTreasure example"

Doug says, "and yeah, the first paper I pointed to talks about building an optimal decision tree, figuring out which tests to share etc"

Doug says, "I never got around to implementing that in my project. for implication checking, I used partial evaluation"

Doug says, "one problem is if you put too much power into your predicate language, then implication checking becomes undecidable."

Doug says, "I ended up just doing simple cycle checking, i.e. it gives up on recursive predicates"

zarf says, "this is why we implement systems that give up on complex problems, rather than trying to be universal. :)"

Doug says, "yep. I'm all for that."

wilja asks, "Doug, do you know anything about defeasible logic?"

Doug says, "only what zarf may have said in his presentation."

Doug says, "and I've forgotten it"

zarf says, "one wacky corner case, which I'm not sure if it's a real-life problem: in the example I've typed into the doc, IsTreasure(obj) is actually logically equivalent to (obj is HopeDiamond), so a specificity checker should deduce that they have equal priority!"

zarf says, "you don't get a precedence until a second treasure exists."

wilja says, "The nice thing about defeasible logic is that it's weak enough to be easily analyzable."

wilja says, "*efficiently, not easily"

zarf says, "I didn't actually mention it in my presentation"

Doug asks, "so what do you do about two rules with equal precedence?"

zarf says, "compiler error, whine for help"

Doug says, "in my system, the second definition would replace the first one"

wilja says, "From a logic programming standpoint, "is" feels like unification, while IsTreasure(obj) is a predicate call, where the predicate contains a unification. Even if IsTreasure(obj) doesn't contain a disjunction, we could claim the simple unification is more direct than unification via a predicate call."

Doug says, "unless they were both "around" rules, in which case they would both coexist (and get executed in some arbitrary order)"

zarf says, "when I said 'don't drive the author insane as the program grows', that includes not driving him out of town with an unbounded series of compiler errors"

zarf says (to wilja), "that sounds good"

zarf says, "I am not willing to rely on source-code order (or arbitrary order)"

zarf says, "I like rearranging my code"

zarf says, "yeah"

wilja says, "It sounds good, but I'm not sure. I don't like that abstracting a unification with a predicate will change the behavior of the program."

Doug says, "well, the idea with "around" methods was that they would be "auxiliary" in some sense, and so having multiple with the same precedence should mean that they are independent and the order doesn't matter. but I'm not sure how much that would be true in practice."

zarf says, "ideally the compiler should recognize independent rules, not be told about them"

zarf says, "I'm still trying to get my head around what defeasible logic gets us. I think my problem is that IF wants *everything* to be defeasible, never strict."

Doug says, "well, notice I said "methods" instead of "rules"... once you allow side effects, then all bets are off about detecting independence. but that may not be applicable to your language. (now I will go and actually look at the google doc...)"

zarf says, "the doc just has some clips from my slideshow, so far"

wilja says, "Defeasible logic lets us reason about overloading rules *efficiently*. However, it may not express exactly what we want. Also, I don't know how well it works with side effects."

Doug asks, "I see a bunch of papers about defeasible logic. Do you have one you recommend to start with?"

zarf says, "the ones I have printed out are "Defeasible Logic" (Nute 2001), "Propositional Defeasible Logic has Linear Complexity" (Maher 2004)"

wilja says, "zarf has some links from Chung-chieh Shan on defeasible logic: http://www.eblong.com/zarf/rule-language.html"

zarf says, "oh, right, I linked these"

Doug says, "thanks"

wilja asks, "Shall we assume for the purposes of today's Iron Geek Language Design that we won't have time to become experts in defeasible logic?"

zarf says, "yes please. :)"

An ordering example problem

zarf says, "let me try posing a problem"

zarf says, "say that one of the things the game needs to do is list objects (this is, of course, true in IF) and the author would like to specify precedence in the list. I.e., these objects first, those objects last"

zarf asks, "can we do this with the kind of predicate declaration we've been using? Efficiently?"

wilja asks, "Is this a partial or total ordering?"

zarf says, "good question"

zarf says, "the author will be providing statements like Precedes(treasures, all); Precedes(all, rocks); Precedes(HopeDiamond, treasures)"

zarf says, "the author wants to use "classes" to simplify his job of adding these. He will certainly have some don't-cares"

wilja says, "So, partial."

zarf says, "yeah"

Gunther asks, "how about using precedence numbering?"

zarf says, "and the ground rules are, *no numbers*. :)"

zarf says, "if this is doable we snatch it up for *rule* precedence"

zarf says, "(but if I go asking authors to type 'the precedence of the can't-smooch-orcs rule is 23.5' the authors will all commit suicide)"

wilja says, "Yes, please no numbers."

wilja asks, "And why can't we smooch an orc??"

zarf says, "you can but not on this channel. :)"

Gunther says, "you can if any of the preceding 23 rules fire"

zarf asks, "so -- doable?"

Precedes(treasures, things);
Precedes(things, rocks);
Precedes(HopeDiamond, treasures);

wilja asks, "Can you give us the English translation of those Precedes rules?"

zarf says, "treasures are listed before stuff-in-general; rocks are listed after stuff-in-general; hopediamond is listed before treasures-in-general"

zarf says, "obviously it's easy to accidentally create a contradiction"

wilja asks, "Okay, and what sort of queries might we want to make? Does hopdiamond come before treasures?"

zarf says, "but if I added Precedes(rocks, StarOfIndia) that shouldn't be an error, just one diamond hanging out at the bottom of the list"

zarf says, "(there's youe defeasibility)"

zarf says, "the query is "give me the whole list, or *a* whole list that matches the constraints""

zarf says, "the player is taking inventory and all objects will be shown"

zarf says, "(or, of course, the game is being compiled and all rules must be accounted for in the rulebook)"

wilja asks, "So what does it mean to say that rocks comes before StarOfIndia? We're saying that every rock comes before StarOfIndia?"

zarf says, "yyyes"

zarf says, "but Precedes(treasures, all) means that every treasure comes before every non-treasure (treasures are a subset of all)"

wilja asks, "Can you paste the Precedes example into the doc?"

zarf says, "sure"

The player is carrying a bunch of items. He takes inventory. The game wants to list all of his items, in an appropriate order. The author has provided these ordering predicates:

Precedes(treasures, things);
Precedes(things, trash);
Precedes(HopeDiamond, treasures);

Note that this example is easy to make consistent -- it defines a partial ordering. But the author might reasonably want to add

Precedes(trash, StarOfIndia);

This should not cause an error; it should override the less-specific declaration, putting the Star of India last.

zarf says, "(changed 'rocks' to 'trash' because, after all, the Hope Diamond is a rock)"

zarf says, "I'm glossing over the problem of connecting a class "treasure" with a predicate IsTreasure"

wilja asks, "Must classes like treasures and trash be disjoint?"

zarf says, "they might be or they might not be."

zarf says, "maybe if they overlap, the compiler might have to whine for more rules."

wilja asks, "This seems like a good example. What would be an example inventory listing?"

zarf says, "'You are carrying the Hope Diamond, a gold coin, a rope, a used tissue, and the Star of India.'"

zarf says, "yep"

wilja says, "Let me think about that a minute."

Possible inventory listing:
"You are carrying the Hope Diamond, a gold coin, a rope, a used tissue, a broken baseball bat, and the Star of India."
or just as likely:
"You are carrying the Hope Diamond, a gold coin, a rope, a broken baseball bat, a used tissue, and the Star of India."

zarf says, "(yeah, I said earlier I didn't like arbitrary ordering. Obviously I didn't mean it, entirely...)"

wilja says, "I assume you want deterministic ordering, thugh"

zarf says, "yes"

wilja asks, "Although this is design day rather than implementation day, Cassie and I are tempted to try to implement this example in miniKanren to see what trouble we run into. Does this sound worthwhile?"

zarf says, "by all means"

zarf says, "and I will google miniKanren..."

zarf says, "oh, it's your thing."

Doug says, "so, I think this Precedes example is just ("just") multiple-dispatch method ordering. and I forget example how CLOS and Dylan do it (I think they do it slightly differently)."

wilja asks, "Multi-method dispatch is based on specificity of the arguments, correct?"

Doug says, "yeah"

wilja asks, "Is it clear in the Preceeds example which arguments are more specific?"

zarf says, "maybe"

zarf says, "would it help if I rewrote Precedes(treasures, things); as"

Doug says, "yes, subclasses are more specific than superclasses"

zarf asks, "Precedes(X, Y) if IsTreasure(X) ?"

I know I've shifted the predicate syntax slightly. Sorry! Assume that the CODE and CONDITION are both "true" for these examples. Or rather, to connect these examples with the previous ones:

Precedes(X, Y)           if IsTreasure(X);
Precedes(X, Y)           if IsTrash(Y);
Precedes(HopeDiamond, X) if IsTreasure(X);
Precedes(Y, StarOfIndia) if IsTrash(Y);

wilja asks, "How are conflicts and ambiguities dealt with in multi-method dispatch?"

Doug says, "that's what I'm trying to remember. (I'm coding this up in Swindle, which is an implementation of tiny-clos)"

wilja says, "Precedes(X, Y) if IsTreasure(X) looks less problematic, since we can deal with set elements rather than sets."

Doug says, "ok, pulled out my copy of The Art of the Metaobject Protocol. :) Yeah, CLOS does it with left-to-right ordering."

zarf asks, "meaning what exactly?"

Doug says, "well, hm, I just realized none of the four Precedes assertions actually overlap each other. it's only when you assume they are antisymmetric that you run into trouble."

Doug says, "so, both Precedes(StarOfIndia, UsedTissue) and Precedes(UsedTissue, StarOfIndia) are true"

Doug says, "by different rules."

Doug says, "first and fourth, respectively."

wilja asks, "How would this be resolved in CLOS?"

Doug says, "well, the way I was thinking was that Precedes would be a method that returned true or false. but then you have to figure out how to resolve this case where Precedes returns true for x,y and y,x"

zarf says, "intuitively it's "more true" for rule 4"

zarf says, "but that gets lost when you break it all down into single cases"

wilja asks, "It's more true intuitively, because StarOfIndia is a specific object rather than a (potentially singleton) set?"

zarf says, "yes"

zarf says, "let's figure there are in fact many trash and treasure objects in the game, and the compiler knows this"

Doug says, "for what it's worth, in Dylan if there are two pairs of specifiers with opposite subclass relationships, then you get an ambiguous method error. whereas in CLOS it will use left-to-right, i.e. the method whose first specifier is more specific will be more specific. I should probably come up with an example to clarify, if anyone cares."

zarf says, "so it's not a singleton set"

Doug says, "so, the other weird thing about this example is it's not transitive. rope precedes used tissue, used tissue precedes Star of India, but Star of India precedes rope."

wilja asks, "Cassie wants to know what happens if a thing is also a treasure?"

zarf says, "all treasures are things"

zarf says, "all trash are things too"

Doug says, "so if you try to topologically sort the list, you lose"

zarf says, "and yes, Doug, that's why I threw it into the example"

wilja asks, "what is a rope? A non-treasure, non-trash thing?"

Doug says, "well, it's also interesting because of the specificity thing"

Doug says, "but I think those are separate. maybe not."

zarf says (to wilja), "correct"

zarf says (to doug), "I think specificity must play into resolving the apparent contradiction."

zarf asks, "are people coding or looking baffled?"

wilja exclaims, "Both!"

Doug asks, "so why is rule 4 more specific? is it because StarOfIndia is a singleton? or would it also be so if StarsOfIndia were a class, i.e. it has something to do with the distance from descendant to ancestor?"

zarf says, "I'm open to whatever gets the job done."

zarf says, "StarOfIndia is an object. But I could further extend this example to have classes, which have a subset relationship"

zarf says, "maybe it should work by distance"

Doug says, "I think that would get you into trouble. precedence would change if you inserted a new superclass in the middle of a hierarchy"

zarf says, "true"

Doug asks, "which should ordinarily be a safe refactoring. but maybe in this language you would learn to watch out for that?"

zarf says, "I like going back to the idea to described, of working out that (x in A) implies (x in B)"

zarf says, "(you described)"

wilja asks, "huh?"

zarf says, "if one set-membership predicate logically implies another, you've found a subset, so conditions based on the first are more specific than conditions based on the second"

zarf says, "IsTreasure(X) implies IsThing(X), because IsThing is universally true."

zarf says, "but not the reverse"

wilja asks, "Are these sets all finite?"

wilja asks, "Are recursively-defined infinite sets allowed?"

zarf says, "um. Yes, and no"

Doug says, "I still think there are two separate issues here. the four Precedes rules are not ambiguous, in that the fourth is more specific than the first, so each rule (invoked as a method) gives an answer (true or false). but the set of answers is inconsistent with Precedes producing a consistent ordering."

wilja asks, "If the sets are all finite, it is possible to test subset-ness exhaustively. Otherwise, we'll need to state at the metalevel the set relationships, right?"

Doug says, "and the step that turns Precedes into a linear list isn't part of the language, or at least hasn't been defined as such yet"

zarf says, "I agree with that, which is why I said keep 'em finite"

zarf asks, "Doug: we want to invent an algorithm that uses Precedes in a way that gives the "natural" result, right?"

Doug asks, "I guess what i want to know is, what are the semantics of "Precedes(X, Y) if IsTreasure(X)". is that short for "do ... as true"?"

zarf says, "yes"

Doug asks, "does it also generate "do Precedes(Y, X) if IsTreasure(X) as false"?"

zarf says, "Hm. Maybe it's a three-value range"

zarf says, "BEFORE, NEUTRAL, AFTER"

zarf says, "(I mean the return values)"

Doug says, "you still have to worry about Precedes(X,Y) and Precedes(Y,X) giving compatible answers. not to mention X,Y / Y,Z / X,Z"

zarf says, "agreed. There could be an outright contradiction with no way to resolve it"

zarf says, "in that case, compiler error"

zarf says, "but this is not that case (yet)"

Doug asks, "so, if you have a list that does not include trash, should Star of India go with the treasures? or shoudl it still be at the end?"

zarf says, "heh. I've been taking for granted that all of these logical relationships are evaluated in the context of the whole game, not the player's current inventory"

zarf says, "this may be a prejudice induced by thinking in terms of compilers"

Doug says, "I guess what I'm saying is I don't understand your intuition. :) It seems like this rule about Star of India is just not consistent. or at least it's not well enough defined."

zarf says, "Well, imagine a case that wasn't about ordering, but just about -- I dunno -- monetary value. A one-place Price(X) predicate"

zarf says, "Price(StarOfIndia) can be declare specifically, even though that value contradicts the general Price(treasure) and Price(X) rules"

zarf says, "this is an extension of that"

zarf says, "it's not very well-defined but I'm willing to fill in the gaps any way that amkes it work"

wilja asks, "Shouldn't price be a two-place predicate?"

wilja says, "Are your predicates functions, or Prolog-style goals>"

zarf asks, "er... functions?"

zarf asks, "because I'm old?"

wilja asks, "If it's a true predicate, it should be Price(StarOfIndia, $0.20), right?"

Doug says, "well, Price(X) makes more sense. you get a real number, and real numbers have a total ordering."

Doug says, "just don't add complex currency..."

wilja asks, "So Price is a regular function, not a predicate?"

zarf says, "I don't know."

zarf says, "I've never wanted to make use of the goal-matching sorts of things, so it could be a real predicate where the final term is always a constant."

zarf says, "Doug, I think you're confusing the output of the construct from what we're doing with the construct"

Doug asks, "well, if this is meant to be an analogy for rule precedence in general, you do want to produce a total ordering of rules, right?"

zarf says, "yes"

wilja says, "The usual technical definition of a predicate in functional programming is a function that 1) always terminates and 2) returns a boolean value. In logic programming goals don't really return values, but rather succeed or fail. Either way, as a predicate I'd imagine Price as Price(socks, $1.00). For logic programming, Price(socks, Y), Price(X, $1.00), and Price(X, Y) also make sense."

Doug says, "so cycles are bad, and you have to come up with a reason that that example isn't a cycle. and I'm not coming up with one."

Doug says, "er, I mean, I haven't come up with one. not that I refuse to come up with one. :)"

wilja )

wilja says, "\:)"

zarf says, "I agree that if you go through Precedes(x,y) for every pair of objects, you get a big matrix of booleans (or trinary whatever) that cannot be reconcicled"

zarf says, "reconciled (although I like saying 'reconcycled')"

wilja asks, "Do we need to handle negation, as well?"

zarf says, "so I guess this requires working with the declarations, not just their results"

wilja says, "Sounds like"

zarf says, "in other words: "Precedes(X, StarOfIndia); Precedes(X, HopeDiamond);" is *not* equivalent to "Precedes(X, Diamonds);" -- even though there are just the two diamonds -- the former pair of declarations creates more orderiness."

zarf says, "that is my intuition"

zarf says, "and I think where it clashes with yours"

wilja says, "Or Precedes(X, Y) if IsDiamond(Y)"

wilja says, "I think this makes sense. I just don't know how easy it will be for the programmer to reason about."

zarf says, "I grant this concern"

wilja says, "In particular, adding a new abstraction or class could totally mess up the ordering."

zarf says, "I may be trying to invent the language that only I could invent, and wind up with the language that only I can use"

wilja says, "Although ugly, I might be happier if the user had to explicitly specify when a class/set is less specific than the elements in that set."

zarf says, "I suspect that if you offered that choice, in real life it would turn out be be always or never"

zarf says, "(to be practical)"

wilja says, "I suppose it's sufficient to make a distinction between a class and a member of that class"

wilja says, "This is where types are handy"

zarf says, "I7 currently has a way to declare that a rule goes first in its rulebook -- just put it first, dammit -- and that is both convenient and easy to understand."

zarf says, "(or last)"

wilja says, "It's easy to understand when you have a small number of rules, at least. In that case,"

wilja says, "From a specificity standpoint, Precedes(HopeDiamond, treasures); is superior to Precedes(HopeDiamond, X) if IsTreasure(X);"

zarf says, "I had assumed that the former was syntactic sugar for the latter"

Doug says, "yeah, a class is its predicate"

Doug says, "that's different from saying a class is not its instances."

wilja says, "Precedes(HopeDiamond, X) makes a distinction between elements and sets. It may be useful to consider it different from Precedes(HopeDiamond, X) if IsTreasure(X);, since they show different intent by the programmer."

zarf says, "it may be... I might want a different way to express that difference, though"

wilja says, "Fair enough. Still, it should probably be possible to make the distinction, for the purpose of specificity."

zarf asks, "is this sufficient to make the inventory listing work?"

Doug says, "I was thinking it might work if you replace "Precedes(Y, StarOfIndia) if IsTrash(Y)" with just "Precedes(Y, StarOfIndia)""

Doug says, "but I'm not sure if that's equivalent to your intention."

zarf says, "it gives the same result in this case"

zarf says, "but you want to be able to do what I've got"

wilja says, "Whoops! I meant Precedes(HopeDiamond, treasure) is Precedes(HopeDiamond, X) if IsTreasure(X)."

zarf says (to wilja), "I was with you"

wilja exclaims, "Having typing troubles!"

wilja asks, "Assume for a second that Preceeds(<element>, <set>) is more specific than Preceeds(<element1>, <element2>) if <blah>. Would this help?"

wilja asks, "I meant, assume for a second that Preceeds(<element>, <set>) is less specific than Preceeds(<element1>, <element2>) if <blah>. Would this help?"

zarf says, "I don't know."

wilja says, "It would clarify specificity to some extent in the example."

zarf says, "I'll happily adapt my example to use the form that gives more specificity information"

zarf says, "we still have to use it."

wilja says, "So Precedes(HopeDiamond, treasures); would be more specific than Precedes(treasures, things)"

wilja exclaims, "Hold on--that doesn't follow!"

wilja says, "I must have been thinking of another example."

wilja says, "But it does solve the abstraction problem."

wilja asks, "I think?"

Simpler ordering problems

zarf says, "I'll tell you what I *am* mixing up in this example -- transitivity and specificity"

wilja asks, "I wonder if we can factor the example into two slightly simpler examples that only demonstrate those issues?"

zarf says, "sure"

wilja asks, "Does removing rule 4 remove the transitivity issue?"

wilja says, "Ah--I see"

zarf says, "added more examples"

Transitivity:

Precedes(treasures, liquids);
Precedes(liquids, trash);

(Assume that trash, treasures, liquids are disjoint sets in this example. Result should be: StarOfIndia, Milk, BrokenStick)

Specificity:

Precedes(treasures, trash);
Precedes(trash, StarOfIndia);

(Assume that StarOfIndia is a treasure, and trash is disjoint from treasure. Result should be: GoldCoin, BrokenStick, StarOfIndia)

wilja says, "I'm thinking we could use the notion of subsumption, or perhaps unification, from logic programming to deal with the specificity problem"

zarf says, "I know unification from Prolog; not subsumption."

wilja says, "Actually, this problem looks a little different."

wilja says, "What about"

Doug says, "I still have a problem with that Specificity example. Precedes(StarOfIndia, BrokenStick) and Precedes(BrokenStick, StarOfIndia) are both going to return true there"

zarf says, "that's why I believe that we can't work jsut with the return values"

wilja says, "Yes. Seems like we have some notion of defeasibility based on specificity of arguments."

Doug says, "if you instead say "Precedes(treasures, trash) = true; Precedes(StarOfIndia, trash) = false;" then there's no problem, it's standard multi-method dispatch"

zarf says, "sure"

wilja says, "It should be the other way around in our reckoning, since StarOfIndia is more specific."

zarf says, "so standard multi-method dispatch isn't enough"

Doug says, "no, I mean, those two rule definitions (sorry, replace "=" with "as") would give you the results you want."

Doug says, "that is, Precedes(StarOfIndia, BrokenStick) would return false."

zarf says, "oh, I see -- sorry, I misread"

wilja asks, "So this rule is directly implementable in CLOS?"

Doug says, "but again we're being a little loose about whether these are assertions or functions (or something else)"

Doug says (to wilja), "sure, in this small case it's just single dispatch. Treasure.precedes(Trash x) { return true; } StarOfIndia.precedes(Trash x) { return false; }"

zarf says, "We can say that Precedes(trash, StarOfIndia) implies Precedes(StarOfIndia, trash)=false"

zarf says, "or rather the trinary form"

Doug says, "sure. many ways to do it."

zarf asks, "but that's not sufficient for my original example?"

Doug says, "the problem is trying to get a partial order out of this binary relation."

Doug says, "since it's nto transitive"

Doug says, "not"

Doug says, "so, I think this is similar to the kinds of things I was trying to solve with "around" methods. it's a way to disambiguate situations where you otherwise have non-transitivity. but it's not particularly scalable-- all "around" methods precede all "plain" methods, and that's the only distinction."

wilja asks, "Is this like 'around advice' in Emacs Lisp?"

Doug says, "so you could say that the "Star of India follows trash" rule has higher precedence than the other rules"

Doug says, "but that only gets you so far."

Doug says (to wilja), "yep"

wilja asks, "Okay--what should Preceedes(StarOfIndia, UsedTissue) and Preceedes(UsedTissue, StarOfIndia) return, respectively?"

Doug says, "false and true"

wilja asks, "What is the reasoning for the 'false'?"

Doug says, "so, again I think we're getting confused about whether these are Prolog-style assertions, or predicate functions that return values."

zarf says, "I don't think it matters if we recast everything as Precedes(StarOfIndia, UsedTissue, true)"

Doug says, "I think you want these to be assertions, and the challenge is to write an algorithm that converts the assertions into a linear order given any set of objects."

wilja says, "From a relation standpoint, Preceedes(trash, treasure) and Preceedes(treasure, trash) could both hold. It's only our interpretation of the relation that makes it yucky."

zarf says, "Yes, Obi-Wan"

wilja exclaims, "Use the Schwartz!"

Doug says, "sorry, I mean, the challenge is to write a function that takes a set of objects and returns an ordering, based on the set of assertions."

zarf says, "but I suspect doug has the right track"

Doug says, "so you're never "calling" Precedes"

zarf says, "nod"

Doug says, "or rather, the algorithm might, but it's not meant to be a user function"

zarf says, "I may come back later and squash "assertions" and "functions" into the same mold, but not until this is sorted out"

Possible solutions

wilja says, "Is it useful to think of the first rule as Precedes(X, Y) if Trash(Y) and (Treasure(X) and not(X == StarOfIndia));"

Doug says, "so this algorithm will discover a cycle, and has to figure out how to break the cycle based on... something. either differentiate assertions about objects vs. classes, or use the inheritance distance, or something else."

zarf shouts "Ranked pairs! Okay, we're done."

zarf says, "(joke)"

Doug says, "exactly."

Doug says, "yes, this is feeling Arrow's-Theorem-y. :)"

wilja asks, "Is the problem with the simple Preceedes example that the rules aren't contridictory?"

Doug asks, "I'm still not sure what your semantic intention is, by the way. Your rule is "Put Star of India after all trash", but does this mean "Put Star of India after everything" or does it mean "if there is trash, put Star of India after it"?"

zarf says, "it is a world where trash exists"

Doug says, "or rather "put Star of India after where trash would be""

Doug says, "instead of "after everything"."

zarf says, "if there were no trash, the rules would degenerate to some simpler case, but I don't currently care what it would be"

zarf asks, "so, Arrow-wise, you throw down the most specific assertion, resolve as much as possible, throw in the next-most-specific assertion, ... when you hit a contradiction ignore the cases that contradict what you've got resolved and move on. Is that coherent?"

Doug says, "well, the whole exercise is to define "most specific assertion""

zarf says, "no, that's only part of the exercise. :)"

Doug says, "actually I guess that's not the problem."

wilja says, "I just pasted some miniKanren code into the doc."

(define treasures
  (lambda (x)
    (conde
      [(== 'gold-coin x)]
      [(== 'HopeDiamond x)]
      [(== 'StarOfIndia x)])))

(define trash
  (lambda (x)
    (conde
      [(== 'used-tissue x)]
      [(== 'broken-baseball-bat x)])))

(define things
  (lambda (x)
    (conde
      [(== 'rope x)]
      [(== 'treasure-map x)]
      [(== 'delicious-Neapolitan-freeze-dried-astronaut-ice-cream x)]
      [(treasures x)]
      [(trash x)])))

(define preceeds
  (lambda (x y)
    (conde
      [(treasures x) (=/= 'StarOfIndia x) (trash y)]
      [(trash x) (== 'StarOfIndia y)])))

wilja says, "This is basically more verbose, pure Prolog with disequality constraints"

zarf says, "if we go with what I said and 'inheritance distance' as the metric, do we get an answer? Ignoring the problems with inheritance distance (refactoring)"

Doug says, "actually, I think you don't even need inheritance distance here."

Doug says, "once you get away from treating Precedes() as a function, it more or less works. you can say that Precedes(trash, StarOfIndia) is more specific than Precedes(things, trash), even though they don't overlap in the multi-method sense."

Doug says, "in fact it's also more specific than Precedes(treasure, things)"

Doug says, "and you can use either fact to break the transitivity cycle."

zarf asks, "because it has one specific object, not zero?"

Doug says, "no, just because the specifiers are subclasses (regarding a singleton as a subclass)"

zarf says, "okay"

Doug says, "it's just confusing because the argument order doesn't matter, so you're not doing pairwise comparison"

Doug says, "so yeah, you can do it like you said, add rules in order from most specific to least specific, and ignore conflicts"

zarf says, "this is encouraging"

zarf says, "I do not mean to bypass wilja's code"

wilja says, "There isn't much to my code"

Evaluating the above:

(run* (q) (exist (x y) (preceeds x y) (== `(,x ,y) q)))
=>
'((used-tissue starofindia) 
  (broken-baseball-bat starofindia)
  (gold-coin used-tissue) 
  (hopediamond used-tissue)
  (gold-coin broken-baseball-bat)
  (hopediamond broken-baseball-bat))

Doug says, "I have a suspicion that this will break down somehow. like, "more specific" isn't a total order, just a partial order"

wilja says, "We need a default rule if we want to include items, and order two treasures, for example."

Doug says, "but it might be that cycles will only involve comparable fules"

Doug says, "rules"

zarf asks (of wilja), "you said earlier 'think of the first rule as Precedes(X, Y) if Trash(Y) and (Treasure(X) and not(X == StarOfIndia))'. Is that a transformation that the compiler can do?"

wilja says, "I suspect not."

Doug says, "in order to do that transformation (to make all rules disjoint), you have to know the precedence relation anyway."

wilja says, "That's how I implemented the code"

zarf says (to doug), "it will break down, but I'm hoping that when it does, the author can come in and put in meta-precedence rules to sort it out"

zarf says, "I'm also hoping that this process converges"

wilja says, "One problem is that two two Preceeds rules don't actually"

wilja asks, "One problem is that two two Preceeds rules don't actually contradict each other, from a logical standoint. Is there an assumption that at most one rule should hold for a predicate, for a given set of (instantiated) arguments?"

zarf says, "no, I don't think so"

Doug asks, "what happens if you take out the (=/= 'StarOfIndia x) clause?"

wilja says, "You get extra answers:"

Without the (=/= 'StarOfIndia x), the run* expression returns:

'((used-tissue starofindia)
  (broken-baseball-bat starofindia)
  (gold-coin used-tissue)
  (gold-coin broken-baseball-bat)
  (hopediamond used-tissue) 
  (starofindia used-tissue)
  (hopediamond broken-baseball-bat)
  (starofindia broken-baseball-bat))

Doug says, "right, then the relation is not a partial order"

wilja says, "I've added the extra answers to the doc."

wilja says, "In pure logic programming, normally only a single rule should hold when all the arguments are fully instantiated."

wilja says, "This avoids duplicate answers, while allowing you to reorder code arbitrarily."

wilja says, "I wonder if we want a similar approach."

zarf asks, "when you say 'only a single rule should hold', do you mean that only a single rule matches the arguments, or that there's a single rule which is 'most specific' for those arguments?"

wilja says, "The first."

wilja says, "But this, in combination with the most specific notion, might work."

wilja says, "That is, only the most specific rule that matches arguments would be considered valid."

zarf says, "you'd certainly want that"

zarf says, "otherwise, if I add one specific exception, I have to go around to all the more general rules and put exceptions into them"

wilja says, "Unfortunately, this doesn't seem sufficient."

wilja says, "Since the order of arguments is swapped in the two rules."

Epilogue

zarf says, "I find I am wearing out"

Doug says, "I'm sorry if I sidetracked the conversation"

zarf says, "no no"

zarf says, "I'm sorry if I wound up using you guys as a wall to bounce my ideas off of, rather than collaborating"

Doug says, "well, I kind of fixated on that one example rather than letting you continue with language design"

zarf says, "this example is more or less the whole language in a nutshell"

zarf asks, "do you want to keep going as I bail out for dinner?"

zarf says, "(or we could go get dinner, er, those of you in Somerville, er, meaning Doug)"

wilja says, "I was thinking about dinner myself."

wilja says, "I think we've put our finger on a (the?) major problem, so I don't think we've wasted the time."

zarf says, "this is not a language design but the discussion has been enlightening"

zarf says, "yes."

wilja says, "Maybe defeasible logic is worth a second look. ;)"

zarf says, "true"

Doug says, "I'll pass on dinner, had a late lunch"

zarf says, "this "argument-based approach" paper seems apropos enough to be worth a second read"

zarf says, "off-line."

wilja says, "Or maybe there is something a little wrong with how we want to write Preceeds."

zarf says, "anyway, I should spend after-dinner working on my WIP for tomorrow's writer's workshop"

wilja asks, "WIP?"

zarf says, "work in progress"

wilja says, "Ah."

wilja says, "Well, I'll keep thinking about this problem."

zarf says, "me too"

zarf says, "I will post today's transcript soonish"

wilja asks, "Is it okay if I mention the problem to some friends at the PL summer school in Oregon?"

zarf says, "please do"

wilja says, "If any of us have a bright idea, maybe we can take another crack."

zarf says, "feel free to continue throwing stuff into the doc, too. Since it wound up being a scratchboard for the discussion, I'll paste appropriate pieces into the transcript"

wilja exclaims, "Good!"

zarf says, "thank you both for participating"

zarf says, "and everybody else who chimed in"

wilja says, "Thank you! It was fun on this end."

zarf says, "and to the silent cassie"

wilja )