Re: [Gnu-arch-users] Round III: xl and all that

[Jan Hudec]

On Fri, Jul 23, 2004 at 18:55:06 -0700, Tom Lord wrote:
>   $goal says "Our overall goal is `maybe-prime'" and $subgoal says
>   "The immediate goal is `maybe-prime'".
> 
>   The first step in the reduction has to try to reduce `two-power' in
>   the definition of `maybe-prime'.   It does that by changing the
>   $subgoal but leaving $goal alone:
>   [...]
>   The rule for what happens when $goal and $subgoal are different, and
>   $subgoal is fully reduced, is that $goal is copied to $subgoal:

Why isn't $goal a sequence of symbols? When different subgoal is needed,
it would be pushed and when finished poped again. (Terminating condition
is then that the last goal was poped).

Thinking of a case like this:

$program =
    { type => 'program
      a => 1
      b => (+ a 1)
      c => (+ b 1)
      d => (+ c 1)
      e => (+ d 1)
      f => (+ e 1)
    }
$goal = 'f                          | $goal = '(f)
$subgoal = 'f

Then when it gets to the state where:

$program = { type => 'program
    a => 1 b => (+ a 1) c => (+ b 1) d => (+ c 1) e => (+ d 1) f => (+ e 1)
}
$goal = 'f                          | $goal = '(b c d e f)
$subgoal = 'b

Now it reduces b (in two steps -- substitue a and compute the +)

$program = { type => 'program
    a => 1 b => 2 c => (+ b 1) d => (+ c 1) e => (+ d 1) f => (+ e 1)
}
$goal = 'f                          | $goal = '(b c d e f)
$subgoal = 'b 

And then with $goal and $subgoal it goes back to:

$program = { type => 'program
    a => 1 b => 2 c => (+ b 1) d => (+ c 1) e => (+ d 1) f => (+ e 1)
}
$goal = 'f
$subgoal = 'f

And has to go through 3 steps ($subgoal is, in turn, 'e, 'd and 'c)
before it can reduce again, while with stack it just pops 'b and:

$program = { type => 'program
    a => 1 b => 2 c => (+ b 1) d => (+ c 1) e => (+ d 1) f => (+ e 1)
}
$goal = '(c d e f)

and it can immediately continue reducing c.

Since it's deterministic, always when you go down a long chain of
subgoal changes and then reduces one variable, it will redo that very
same chain again except for the last element. Stack would be more
efficient for it. What is the reason not to use it?

-------------------------------------------------------------------------------
                                                 Jan 'Bulb' Hudec 
<address@hidden>

signature.asc
Description: Digital signature