Mark,

"Mark van Gulik" <ghoul6 at home.net> wrote:
> > Marcel Weiher <marcel at metaobject.com> wrote:
> >> [snip]
> >> 
> >> Interesting, an 'object-space' approach to backtracking / Prolog.
> >> All the approaches I've are 'code-space', and that has probably
> >> restricted my thinking in that regard, so I'd be glad to find out
> >> more.  Anyway, are you aware of the bactracking-extension to
> >> Smalltalk (without kernel support)?  It was an OOPSLA paper a while
> >> back, and I put the code in Squeak last summer.
> >
> > I have read it. I'm not sure its worth the trouble the way they did it.
> 
> Hey, the core backtracking code only took a week (4.5 days staring at the
> screen and lots of little diagrams, trying to get my head around it, and a
> Friday afternoon to code it up).  It comes in handy now and then.

No doubt you had week of happy hacking.

What I primarily mean is this:

Is this really a step forward, introducing those new concepts? Once
you have introduced that any code anywhere might concievably be affected
by that, a heavy burden. How du you know for example when changing a
collection whether it is refered to in a nondeterministic place and is not allowed
to change?

If you really want clever searches then Prolog and constraint programming
techniques can be used. They have more to offer than one weeks work, I know
people who has worked with that for 20 years. And they are not stupid.

> > To be really interesting it should be possible to backtrack on parts of
> > datastructures (composed objects:) and they didn't have a lot to say
> > about that.
> 
> I agree.

Good, lets continue from here (after my vacation)

> A while ago I tried to fit backtracking into my language Avail,
> without any primitive support.  The execution model uses continuations, and
> most objects are immutable, so this seemed like a good fit.  I hit a problem
> with variables not being "unwound" correctly in Avail.  Local variables are
> separate objects (think of a wrapper-like object with a single, mutable
> slot), which means they have the problem you mentioned.  Arguments to blocks
> and methods, on the other hand, aren't reified as first class
> variable-objects, however, so they get unwound due to the nature of
> immutable continuations.  Let's just say I was less than pleased with this
> solution.
> 
> Of course, once I have daemonic variables, this will no longer be a problem.
> In fact, since the only change-points are variables, and any variable can
> have pre-read, pre-write, and post-write daemons attached to it, *every*
> object's state could be rewound during backtracking.

Is it possible to get comprehensible information (human readable) out of
this?
Pruning like what cut does in Prolog?
Comprehensible debugging?
Clear cut semantics?
(Disk)Persistence of the history?

My experience of hooks is that it is impossible to get a birds.view of things
and that locks it in. If one should be able to shape things that cannot
be done from little peeking places.

To me the concept of bijections says it all in one word. Or call it
group theory. I have read nothing here to convince me there exists
other ways of doing this that is better in any sense.

Consider the following operation naturally expressed in C (a so callad
"low level language")

  x += 3;

This is immediately invertible (backtrack with "x -= 3;"). Compare

  x = x+3;

with daemon reads, writes and all that, do you claim that to be a step
towards clarity?

Notice that this unlike Prolog allows searching over changing state, not
only monotonically instantiating partially unknown values. And it is possible
to backtrack method calls, not only variables. That is the unit of reversibility
is not necesserarily small scale. Any bijective function will do the job.

> > That is like the simpler "prologs" like turbo prolog that
> > didn't have "real" logical variables. I will come back to this after my
> > vacation.
> 
> There was some pretty cool stuff with SolutionStreams (if I recall), that
> basically allowed backtracking "encapsulated" into a coroutine.  It didn't
> have variable unification, or any other logic programming features.  I did
> sketch out a rough algorithm for unifying finite recursive sets, but without
> resorting to hypersets it's hard to reason about what unification actually
> means in this sense.  I think this would make a terrible fit on a language
> like Smalltalk if unification occurred on message send boundaries.  The
> alternative is to do *explicit* wrapping in simple ValueHolder-like
> structures (effectively a special kind of reified variable).  Unifying two
> variables or conformant(?) lists or sets of variables would be done
> explicitly, via something like "var1 unifyWith: var2".  The unification
> itself would create a backtracking point, to allow the effects of this
> unification to be undone during failure propagation.

I agree, combining unification with OO-ideas is not trivial. One
consequence of this is to try search without unification (as the main
operation). This is what I have done. Another way is to carefully
develop the connection, this has been done and is interesting but I am
not into that, for the moment.

"the alternative" you say. Are you sure you have considered all possible
ways of organizing search? Exhaustively searched the entire space of
searching methods (if you have tell me, in private perhaps, is P=NP?)

The way I have worked with searching within stateful worlds is to change
state and change it back on backtracking. This seems to me natural and
efficient, in fact better than Prolog for some kind of search. That
remains to elaborated and seen in practical application however, as far as
I know.

> > Another use for objects with history that I forgot to mention is as
> > a starting point for scripting. That is manipulate an object until
> > it becomes what it should be. Then look at the history and try
> > to generalize. In this way ordinary work and scripting becomes
> > to aspects of the same thing.
> 
> Generalizing is tricky, especially from few samples.  Even if a tool simply
> finds *likely* dimensions along which to generalize, the list of likely
> generalizations will be huge, and filled with irrelevant stuff.  I
> considered a programming paradigm based on semi-automated generalization (to
> produce the actual code), but I read a lot of papers that scared me off that
> trail. 

Who said anything about *automatic* generalization? Reread the paragraph
above and you will see that its about producing scripts manually. Like
writing a program but with less typing and by trying it out on a sample
data from the outset. And backtracking to earlier states when it goes
wrong.

> Oh yeah, the manipulation language would have been gesture-based
> (this was long before I saw anything like Morphic).  Programming would be
> kind of like playing solitaire all day:  Put *that* argument over there,
> perform *that* previously created script with these arguments ...whoops, let
> me go drag them in... now was that thing one of the arguments or one of my
> intermediate results... and why do I want to go juggle?

There are other ways than that. I have used this experimentally for
more than a year, it works, but due to the crappy nature of the execution
environments I had access to then, (X), I never had the energy to finish it.
I hope to accomplish this within Squeak in a not to distant future.

My vision is that one works with a computer for a while and when a pattern
is recognized that is felt as boring, a history is available and if considered
worthwhile one can generalize this to a script, turning the boring pattern 
into a single act. This should be true regardless of whether the original acts
where done with a GUI or in another fashion. Achieving this entails some work
beyond what I have already tried but not beyond reach.

I hope we will continue this after the summer. Perhaps you can reshape some of
your experience with avail into concrete suggestions for changing Squeak for the
better.

/Mats