Path: utzoo!attcan!uunet!husc6!mailrus!cornell!uw-beaver!teknowledge-vaxc!sri-unix!quintus!ok From: ok@quintus.uucp (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: Need style advice Message-ID: <173@quintus.UUCP> Date: 19 Jul 88 00:19:36 GMT References: <1988Jul17.003242.1874@cs.rochester.edu> Sender: news@quintus.UUCP Reply-To: ok@quintus.UUCP (Richard A. O'Keefe) Organization: Quintus Computer Systems, Inc. Lines: 169 In article <1988Jul17.003242.1874@cs.rochester.edu> stuart writes: >> Richard O'Keefe responds to my query with: ... >> Remember: a cut at the end of a clause is almost always in the wrong place. >Your reminder is appreciated, but it would be more useful if I were >also made acquainted with how things *should* be done. You put a cut at _precisely_ the point at which it becomes known that this is the right clause to use: no sooner, and no later. You take care to ensure that _only_ the conditions which are relevant to determining that this is the right clause are tested before the cut. As a special case of this, if you have a predicate p/2 where the first argument is relevant to determining the clause but the second argument is not, you should inspect/bind the second argument _after_ the cut. >> Would it be possible for you to tell us what the relation is supposed to >> _mean_... >Yes,... I have a graph... In that case, foo_value(X, Y) should only succeed when X is (the name of) a node in the graph. >I have a graph with two colors of arcs, and two kinds of colors of >nodes. foo_value/2 is to give values to nodes based on graph >connectivity and coloring. In that case, instead of forced_to_be_1/1, let's start with relations which directly express what you want to say: node_colours(Node, FirstColour, SecondColour) is to be true when Node is the name of a node in the graph, FirstColour is the first colour (black or white) which is assigned to that node, and SecondColour is the second colour (red or green) which is assigned to that node. arc_colour(?From, ?To, ?Colour) is to be true when From and To are the names of nodes in the graph, there is an arc From->To in the graph, and Colour is the colour which is assigned to that arc. For argument's sake, the arc colours are yellow "first type" and orange "second type". If I've understood the specification correctly: relation_one(From, To) :- arc_colour(From, To, yellow), node_colours(To, _, green). relation_two(From, To) :- arc_colour(From, Link, yellow), /* Link may be any colours */ arc_colour(Link, To, orange). /* 1: value_1 is assigned to black nodes */ node_value(Node, value_1) :- node_colours(Node, black, _). /* 2: value_2 is assigned to white nodes which are linked to white nodes by relation_one */ node_value(Node, value_2) :- node_colours(Node, white, _), relation_one(Node, Next), node_colours(Next, white, _). /* 3: value_2 is assigned to white nodes which are linked by relation_two to other value_2 nodes */ node_value(Node, value_2) :- node_colours(Node, white, _), relation_two(Node, Next), node_value(Next, value_2). /* 4: value_1 is assigned to white nodes which are linked by relation_one to black nodes */ node_value(Node, value_1) :- node_colours(Node, white, _), relation_one(Node, Next), node_colours(Next, black, _). /* 5: value_1 is assigned to white nodes which are linked by relation_two to other value_1 nodes */ node_value(Node, value_1) :- node_colours(Node, white, _), relation_two(Node, Next), node_value(Next, value_1). /* 6: value_3 is assigned otherwise */ /* deferred */ Let's split this up and unfold relation_one and relation_two. node_value(Node, Value) :- node_colours(Node, Colour, _), node_value_case(Colour, Node, Value). node_value_case(black, _, value_1). /* 1 */ node_value_case(white, Node, OneOrTwo) :- /* 2-5 */ white_node_value(Node, Value), !, OneOrTwo = Value. node_value_case(white, _, value_3). /* 6 */ white_node_value(Node, value_2) :- /* 2 */ arc_colour(Node, Next, yellow), node_colours(Next, white, green). white_node_value(Node, value_2) :- /* 3 */ arc_colour(Node, Link, yellow), arc_colour(Link, Next, orange), node_value(Next, value_2). white_node_value(Node, value_1) :- /* 4 */ arc_colour(Node, Next, yellow), node_colours(Next, black, green). white_node_value(Node, value_1) :- /* 5 */ arc_colour(Node, Link, yellow), arc_colour(Link, Next, orange), node_value(Next, value_1). I'm still rather unhappy about this. Why do you look for a value_2, chasing all through those orange links, and only if that fails look for a value_1? Why not just explore out from the node and pick whichever you meet first? (For example, if a white node is immediately adjacent to a green/black node, and 500 steps away from a green/white node, why is the green/white one preferable?) It seems rather odd that 'value_2' can be inherited _through_ black nodes. E.g. a-(yellow)->b-(orange)->c-(yellow)->d a: white, red [value 2, by /* 3 */] b: black, green [value 1, by /* 1 */] c: white, red [value 2, by /* 2 */] d: white, green [value 3, by /* 6 */] This is single-valued, and can solve for the Node as well as the Value. I want to stress that I am not happy with it: the idea of a "default" value value_3 bothers me (this can only be eliminated by rewriting the caller). What most bothers me is that value_2 is a simple transitive closure, but value_1 has no simple independent characterisation. >So, what is the >recommended form for simple decision trees in Prolog? This is _not_ a simple decision tree, so the answer I am about to give isn't really relevant, but here it is, for what it's worth. dt(Object, Value) :- % ROOT test_1(Object, Tag), dt_1(Tag, Object, Value). dt_1(val_1_1, Object, Value) :- % INTERNAL NODE test_1_1(Object, Tag), dt_1_1(Tag, Object, Value). ... dt_1(val_1_n, Object, Value) :- test_1_n(Object, Tag), dt_1_n(Tag, Object, Value). dt_1_2_1_2(val_1_2_1_2_1, Object, Value) :- % LEAF value_1_2_1_2_1(Object, Value). ... dt_1_2_1_2(val_1_2_1_2_m, Object, Value) :- value_1_2_1_2_m(Object, Value). The root looks like dt/2. The internal nodes look like dt_1/3. Each test_*/2 is a function which classifies the Object and returns a Tag saying which case it found. The leaf nodes look lik d1_1_2_1_2/3. Each value_*/2 is a function which computes the appropriate value for that leaf. Typically, no cuts at all are needed.