- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: John Lloyd <jwl_at_cs.bris.ac.uk>

Date: Wed, 2 Jul 1997 19:48:59 +0100 (BST)

*> As you can imagine, I do not agree that the Escher model is simpler.
*

*> At a first sight, it seems to be simpler since Escher performs
*

*> only rewrite steps. However, Escher also deals with logical variables,
*

*> and in order to understand the processing of these variables,
*

*> one has to consider also all the rewrite rules in the module
*

*> Booleans. Thus, the operational model of Escher can be characterized
*

*> as "outermost reduction + all rewrite rules of Booleans".
*

*> Since the rewrite rules in Booleans describe the treatment
*

*> of logical variables, the consequences of applying the different
*

*> rules to a concrete goal is not obvious, at least for me.
*

*> For instance, the goal "exists [x] x == head []" will be reduced to
*

*> "True", whereas the goals "exists [x] head [] == head []" and
*

*> "x == head []" are not reducible. Moreover, parallel outermost
*

*> or leftmost outermost reduction may also lead to unexpected results.
*

*> For instance, consider the functions
*

*>
*

*> f [] X = []
*

*> loop = loop
*

*>
*

*> and the expression "f (head []) loop". Since "loop" is the only
*

*> outermost redex, parallel or leftmost outermost reductions run
*

*> into infinite loops, whereas an appropriate rewrite strategy
*

*> (like in Curry specified by definitional trees) immediately stops.
*

*> Maybe these examples are artificial, but they show that the
*

*> behavior of a pure rewrite model is not obvious.
*

There are several comments to make here. The first is that the rewrites in

Booleans are not complicated! Indeed I have worked very hard to reduce them

to the simplest possible set. Mostly they are rewrites just like programmers

write in their own programs and many are already in Haskell. A few have side

conditions which must be satisfied before they can be applied. I simply do not

accept that (ordinary) programmers will have a problem with these.

Second, every computational model will have problems with infinite loops

and bizarre behaviour of one kind or another in extreme cases. So Escher

suffers from this as well. The more relevant question is how such anomalies

affect the writing of practical, large-scale programs. Basically, two

things (other than straight incorrectness) can go wrong in Escher

programs: you can flounder (i.e. not reduce enough) or you can loop.

Each case requires a fix of some kind which the programmer must provide.

My own experience with Escher is that these fixes are easy to find.

Of course, the only way to confirm or refute this is to try it for yourself!

(This will be possible reasonably soon, I hope.) However, I really think we

should concentrate of actual sensible programming tasks rather than the

ones on the very edge. Hence my suggestion to Sergio. Let's discuss

some realistic programs.

BTW, there are some more technical points about your examples which will

be addressed in a separate message.

*> Here I fully agree with Sergio. What is the advantage of adding
*

*> sets to the kernel of Curry in comparison to a module implementing sets?
*

I think there is a big advantage. See my reply to Sergio (and see the set

examples in the Escher paper).

*> I am open to suggestions, but the current form of concurrency
*

*> is identical to the Goffin approach, which is considered as
*

*> more high-level than Concurrent Haskell. Moreover, if we add
*

*> a monadic form of concurrency, we have two forms of concurrency
*

*> in the language (an explicit via forkIO and an implicit
*

*> via the delay of insufficiently instantiated redexes).
*

Which Goffin paper is the best place to look? Two other points: I have already

built higher-level facilities on top of the concurrent Haskell facilities.

These are usually what the programmer wants to use. The low-level stuff is

available if needed. Second, I don't regard delay due to insufficiently

instantiated redexes as concurrency at all. It just affects the choice of

redex. The Escher concurrency is big, chunky, coarse-grained, explicit

concurrency. (I'm trying to get something written on this, so a more

detailed debate can be had.)

*> Maybe the mentioning of the value "Valid" is a bad idea.
*

*> Forget about this value, it is not accessible to the user
*

*> and only used to specify the computation model.
*

I would be pleased to see the demise of Valid.

*> The difference between constraints and Booleans are the
*

*> operations which you can apply on them. Booleans are (like
*

*> in Haskell) two values which can be arbitrarily used
*

*> (whether you call them True/False or A/B is not important).
*

*> Constraints contain more information since they have a
*

*> distinguished interpretation and a constraint solver which
*

*> tries to solve the constraint w.r.t. to this interpretation.
*

*> Currently, only strict equality is supported as a constraint.
*

*> Operations applied to constraints must be supported by
*

*> the constraint solver, thus it is not possible to allow
*

*> arbitrary operations on constraints. For instance, the
*

*> logical negation of strict equations is not supported
*

*> (I have no idea to do it). Nevertheless, you can support
*

*> disequations as constraints, like in Paco's Toy system,
*

*> but this is different from the logical negation of strict equality.
*

*> This is the reason why I think that constraints must be
*

*> distinguished from Booleans, as in the Goffin approach.
*

*> Constraints are more related to functions: functions are
*

*> intended to be applied in order to compute a value,
*

*> and constraints are intended to be solved in order
*

*> to compute a solution.
*

I'm not sure I understand well yet all the subtleties on this issue. I just

have the gut feeling that mathematicians and logicians have been solving

constraint systems for a very long time with the conventional mathematical

apparatus and therefore there ought to be a way to introduce constraint

solving in a more seamless way without all the extra Curry stuff. For me,

adding constraints means smoothly extending the facilities of the computational

model. It certainly doesn't mean adding a separate constraint solver and a

lot of extra apparatus and syntax.

In fact, as constraint solving can be very nicely formulated as finding the

"normal form" of a (complicated) constraint system, Escher already does

simple constraint solving. To do something more meaningful requires

manipulating several redexes at the same time. This doesn't require any extra

syntax - just a clever operational semantics. It's largely transparent to the

programmer.

John

Received on Wed Jul 02 1997 - 21:31:00 CEST

Date: Wed, 2 Jul 1997 19:48:59 +0100 (BST)

There are several comments to make here. The first is that the rewrites in

Booleans are not complicated! Indeed I have worked very hard to reduce them

to the simplest possible set. Mostly they are rewrites just like programmers

write in their own programs and many are already in Haskell. A few have side

conditions which must be satisfied before they can be applied. I simply do not

accept that (ordinary) programmers will have a problem with these.

Second, every computational model will have problems with infinite loops

and bizarre behaviour of one kind or another in extreme cases. So Escher

suffers from this as well. The more relevant question is how such anomalies

affect the writing of practical, large-scale programs. Basically, two

things (other than straight incorrectness) can go wrong in Escher

programs: you can flounder (i.e. not reduce enough) or you can loop.

Each case requires a fix of some kind which the programmer must provide.

My own experience with Escher is that these fixes are easy to find.

Of course, the only way to confirm or refute this is to try it for yourself!

(This will be possible reasonably soon, I hope.) However, I really think we

should concentrate of actual sensible programming tasks rather than the

ones on the very edge. Hence my suggestion to Sergio. Let's discuss

some realistic programs.

BTW, there are some more technical points about your examples which will

be addressed in a separate message.

I think there is a big advantage. See my reply to Sergio (and see the set

examples in the Escher paper).

Which Goffin paper is the best place to look? Two other points: I have already

built higher-level facilities on top of the concurrent Haskell facilities.

These are usually what the programmer wants to use. The low-level stuff is

available if needed. Second, I don't regard delay due to insufficiently

instantiated redexes as concurrency at all. It just affects the choice of

redex. The Escher concurrency is big, chunky, coarse-grained, explicit

concurrency. (I'm trying to get something written on this, so a more

detailed debate can be had.)

I would be pleased to see the demise of Valid.

I'm not sure I understand well yet all the subtleties on this issue. I just

have the gut feeling that mathematicians and logicians have been solving

constraint systems for a very long time with the conventional mathematical

apparatus and therefore there ought to be a way to introduce constraint

solving in a more seamless way without all the extra Curry stuff. For me,

adding constraints means smoothly extending the facilities of the computational

model. It certainly doesn't mean adding a separate constraint solver and a

lot of extra apparatus and syntax.

In fact, as constraint solving can be very nicely formulated as finding the

"normal form" of a (complicated) constraint system, Escher already does

simple constraint solving. To do something more meaningful requires

manipulating several redexes at the same time. This doesn't require any extra

syntax - just a clever operational semantics. It's largely transparent to the

programmer.

John

Received on Wed Jul 02 1997 - 21:31:00 CEST

*
This archive was generated by hypermail 2.3.0
: Mon Nov 18 2019 - 07:15:04 CET
*