parvis@pyr.gatech.EDU (FULLNAME) (02/24/88)
I'm looking for some interesting research in the topic of constraint logic programming or constraint satisfaction programming. I'm already familiar with Jaffar's and Lassez' work and also with the Prolog III approach. 1.) Any information about related research, esp. implementation of this paradigm for different other domains than R (as in CLP(R)) are of interest. 2.) I am also interested in applications and experience in any constraint satisfaction based language that may contribute to an evaluation of the constraint satisfaction paradigm. I appreciate any response, Thanks Parvis --- Parvis Avini parvis@gitpyr.gatech.edu
pcm@iwarpo3.intel.com (Phil C. Miller) (02/25/88)
In article <5070@pyr.gatech.EDU> parvis@pyr.gatech.EDU (FULLNAME) writes: > >I'm looking for some interesting research in the topic of constraint logic >programming or constraint satisfaction programming. I'm already familiar with >Jaffar's and Lassez' work and also with the Prolog III approach. I saw an excellent talk a couple of years ago by a man named Wm. Leler in which Wm. (pronounced Wim) discussed a constraint language called Bertrand. This language was developed by Wm. in connection with research leading to his Ph.D. His Ph.D. thesis has since been published as a distinguished thesis by one of the computer science publishers. It's called Constraint Languages. It's fairly recent. Don't know the publisher right off hand. Phil Miller
rlee@sun-oil.ads.com (Richard Lee) (02/26/88)
In article <5070@pyr.gatech.EDU> parvis@pyr.gatech.EDU (FULLNAME) writes:
<I saw an excellent talk a couple of years ago by a man named Wm. Leler
<in which Wm. (pronounced Wim) discussed a constraint language called
<Bertrand. This language was developed by Wm. in connection with research
<leading to his Ph.D. His Ph.D. thesis has since been published as a
<distinguished thesis by one of the computer science publishers. It's called
<Constraint Languages. It's fairly recent. Don't know the publisher right
<off hand.
<
<Phil Miller
_Constraint Programming Languages: Their Specification and Generation_,
by Wm Leler, Addison-Wesley, 1988, ISBN 0-201-06243-7.
Wm is short for William.
garry@batcomputer.tn.cornell.edu (Garry Wiegand) (02/26/88)
A week ago I asked about "constraint-based languages", and since then a number of people have replied. My thanks to you all - your notes have been a considerable help, and have led me to a lot of good work. A summary follows... ****************************************************************************** ** From: rich@devvax.Jpl.Nasa.Gov (Richard Pettit) ** Organization: Jet Propulsion Laboratory, Pasadena, CA. See the next to last (January edition I think) of AI Expert. They have at least one article on constraint languages in it. No doubt there will be many more to follow. Rich [There's another popular article too - in Byte, last September or so. GW] ****************************************************************************** ** From: quiroz@cs.rochester.edu Take a look at ICCP'87. Prof. Baldwin and I have a paper there (p. 389) on a parallel constraint-based language. There is a more extensive TR (number 208, "The Design of the Consul Programming Language") you might like to order by sending a message to Ms. Peggy Meeker (meeker@cs.rochester.edu). For more details, the person to contact is certainly Prof. Doug Baldwin (baldwin@cs.rochester.edu), who is conducting research on general-purpose constraint languages. Good luck with your research! Cesar -------- Cesar Augusto Quiroz Gonzalez Department of Computer Science ...allegra!rochester!quiroz University of Rochester or Rochester, NY 14627 quiroz@cs.rochester.edu ****************************************************************************** ** From: jane@CCA.CCA.COM (Jane Eisenstein) ** Organization: Computer Corp. of America, Cambridge, MA Last fall, I ran into a nice book entitled "Constraint Programming Languages, Their Specification and Generation" by Wm Leler which is published by Addison-Wesley Publishing Company. It "provides an introduction to the subject of constraint satisfaction, a survey of existing systems, and introduces a new technique that makes constraint-satisfaction systems significantly easier to create and expand" in a very readable fashion. The latter half of the book focuses on the author's general-purpose specification language called Bertrand that allows a user to describe a constraint-satisfaction system using rules. The software described is available for a "nominal charge" from the author. ****************************************************************************** ** From: bnfb@june.cs.washington.edu (Bjorn Freeman-Benson) ** Organization: U of Washington, Computer Science, Seattle A few of our Constraint Language References [Borning & Duisberg 86] Alan Borning and Robert Duisberg. Constraint-Based Tools for Building User Interfaces. _ACM_ _Transactions_on_Graphics_, 5(4), October 1986. ThingLab basics, object definer and Animus with an emphasis on MVCish things. [Borning et al. 87] Alan Borning, Robert Duisberg, Bjorn Freeman-Benson, Axel Kramer, and Micheal Woolf. Constraint H ierarchies. In _OOPSLA'87_Conference_Proceedings_, pages 48-60, ACM SIGPLAN, October 1987. [Borning 81] Alan Borning. The Programming Language Aspects of ThingLab, A Constraint-Oriented Simulation Laboratory . _TOPLAS_, 3(4):353-387, Oct 1981. The OOPSLA'87 one has a good bibliography... Bjorn N. Freeman-Benson [The work of Prof. Borning's group on a general UIMS is wonderful - very much along the lines we've started thinking about. GW] ****************************************************************************** ** From: Lindsay Errington <dlerrington%watdragon.waterloo.edu@RELAY.CS.NET> ** Organization: U. of Waterloo, Ontario Constraint Logic Programming is currently getting alot of attention at logic programming conferences. You might try: Jaffar, Joxan and Lassez, Jean-Louis, "Constraint Logic Programming", Proc of the 14th ACM Conference on Principles of Programming Languages, Munich, January 1987. Jaffar, Joxan and Michaylov, Spiro, "Methodology and Implementation of a CLP System", Proc of the 4th International Conference on Logic Programming, Melbourne Australia, May 1987, pp 196-218, MIT Press. Heintze, N.C., Michaylov, S., and Stuckey, P.J., "CLP(R) and Some Electrical Engineering Problems", Proc of the 4th International Conference on Logic Programming, Melbourne Australia, May 1987, pp 675-703, MIT Press. (I suspect that a number of people will send you the same citations) Jaffar's work is very interesting since it provides a semantic framework (if that makes any sense) for a whole family of constraint based languages. The bibliographies will point you to other work into constraints and logic programming. I hope this helps. Lindsay ****************************************************************************** ** From: uw-beaver!ssc-vax!dickey%cornell.UUCP@tcgould.TN.CORNELL.EDU (Frederick J Dickey) ** Subject: Re: "Constraint-based" languages A book has been published recently called (I think) "cobstraint- based languages." The author is William Leler or Leder (sorry, I don't have it here at work with me so I can't give you a more accurate reference). ****************************************************************************** ** From: mcvax!cwi.nl!lambert@uunet.UU.NET (Lambert Meertens) ** Organization: CWI, Amsterdam Here is a reference to a book that I haven't had an opportunity to look into yet since it is still being processed as a new acquistion by our library: W. Leler (1988). Constraint programming languages -- their specification and generation. Addison-Wesley series in computer science. Reading (MA), [etc.]. I would be interested in hearing about further references you have or may receive, and in particular in relation to UIMS. --Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl ****************************************************************************** I've also heard that at least some Prologs understand how to do arithmetic, and that there's a commercial product called TK!Solver which does interesting things. I haven't seen these myself yet. Constraint languages seem to be very much still in their infancy. Lots of room for some good work (hint hint!) - I hope we'll be able to contribute some too. Thanks again - garry wiegand (garry@oak.cadif.cornell.edu - ARPA) (garry@crnlthry - BITNET)
rogerh@arizona.edu (Roger Hayes) (03/01/88)
(Wm Leler, his book "Constraint Programming Languages", his language 'Bertrand', & his first name) No, Wm is not short for William. It's his name, pronounced "whim". Says so right on his driver's license and everything.
voda@ubc-cs.UUCP (Paul Voda) (03/01/88)
In article <5070@pyr.gatech.EDU> parvis@pyr.gatech.EDU (FULLNAME) writes: > >I'm looking for some interesting research in the topic of constraint logic >programming or constraint satisfaction programming. ... Trilogy is a logic programming language with constraints: In the domain of integers Trilogy solves arbitrary linear forms (Diophantine systems). For instance the query: x >= 0 & y >= 0 & 6*x + 8*y = 46 will solve without any backtracks to x = 5 y = 2 and x = 1 y = 5 Linear forms can can be combined into formulas involving ands, ors and existential quantifiers. Trilogy simplifies arbitrary such formulas. In other words, Trilogy implements the full decision procedure for the Presburger arithmetic. Trilogy contains arrays. In this domain it solves constraints of the form a(i) = v where an unknown (logical) array a is constrained in an unknown point i to the unknown value v. For instance the query a::[0..2]->[4..6] & a(0) < a(i) & a(i) < a(2) where a is a logical array of three elements with the values constrained to the interval [4..6] will solve without any backtracks to a = [4,5,6] & i = 1 See also the article 538 for the solution of the Triangle Puzzle in Trilogy. This contribution discusses a declarative technique which eliminates most of the uses of the "var" predicate of Prolog. The March issue of the Byte magazine contains a review of Trilogy. You can read there more about the language which integrates logic programming with procedural and data-base programming while remaining within the first order logic (that's why the name Trilogy: three languages within logic) Trilogy does not contain a single extralogical feature. You can also obtain from me two papers of mine on Trilogy: The Constraint Language Trilogy: Semantics and Computations and Types of Trilogy The papers discuss the logic foundations of computations and the types of Trilogy. The Byte review is admittedly, quite terse. Moreover, the reviewer criticized Trilogy for certain shortcomings when his programs were incorrectly programmed (for instance the Tower of Hanoi). But overall, the review is quite good considering the fact that the author never encountered another constraint language since Trilogy is the first commercially available logic language with constraints. Trilogy, which sells for $99.95 (US), was developed for the IBM-PCs and compatibles by Complete Logic Systems Inc. 741 Blueridge Ave. N. Vancouver, BC Canada V7R2J5 ph: (604) 986-3234
wm@mucs.UX.CS.MAN.AC.UK ( "temporary login") (03/03/88)
For people interested in constraint languages, I should mention that Jacques Cohen and Jean-Louiz Lassez are organizing a workshop on Languages and Constraints. For more information, try email to jc.brandeis@relay.cs.net I'd also love to hear from people working on new constraint languages. In particular, is anyone doing any work on constraint-based front ends to symbolic algebra systems (i.e., to allow the symbolic algebra system to be used as a constraint satisfier)? Wm Leler The PIX Project University of Manchester wm@r5.cs.man.ac.uk p.s. I hate to contradict an old friend of mine (sorry Roger) but Wm is, in fact, short for William. But why are we on the subject of my name anyway?
hasida@etlcom.etl.JUNET (Koiti Hasida) (03/10/88)
Posting-Front-End: GNU Emacs 18.47.144 of Wed Feb 10 1988 on etlcom (berkeley-unix) In <5070@pyr.gatech.EDU>, Parvis Avini writes: > I'm looking for some interesting research in the topic of constraint logic > programming or constraint satisfaction programming. I'm already familiar with > Jaffar's and Lassez' work and also with the Prolog III approach. See my article, entitled 'Dependency Propagation', included in IJCAI87 Proceedings, though, I'm afraid, this is not very well-written; less than half of it talks about constraint programming, and natural language is what the rest of it is about. I should work out its constraint programming part in a more complete form. A crucial difference between my DP and others (CLP, Prolog III, etc.) is that DP deals with constraints on combinatorial objects (i.e., the term structures of logic) whereas the constraints considered in the other approaches are about arithmetic objects (rational numbers or real numbers). Another difference is that in DP we look upon processing as constraint transformation. Since the constraint is the program here, processing is a sort of program transformation. Currently under way is an implementation of the interpreter according to DP. This implementation is being done in language C. The first phase of the work is supposed to be finished within one month or two, and will be applied to a natural-language parser based on a unification grammar formalism. I hope this is of some interest to you. HASIDA, Koiti ('HASIDA' is my family name) Machine Inference Section