Lambda the Ultimate

inactiveTopic Chameleon
started 6/21/2002; 9:31:24 AM - last post 6/27/2002; 10:28:22 PM
Bryn Keller - Chameleon  blueArrow
6/21/2002; 9:31:24 AM (reads: 2964, responses: 4)
Chameleon is a Haskell-style language which provides a flexible overloading mechanism based on Constraint Handling Rules (CHRs). The user can impose conditions on overloaded identifiers via CHRs. For example, consider the functional dependency

class Collects ce e | ce -> e where ...

In Chameleon, we would provide instead the following CHR:

rule Collects ce e, Collects ce e' ==> e=e'


Also available are three papers

  • "Beyond Type Classes", describing the connection and differences compared to Haskell-style type classes.
  • "A Theory of Overloading", describing the theoretical machinery behind the Chameleon language.
  • "A Theory of Overloading Part II: Semantics and Coherence", describing an implementation scheme which we yet have to implement.

Posted to functional by Bryn Keller on 6/21/02; 9:33:41 AM

Bryn Keller - Re: Chameleon  blueArrow
6/21/2002; 2:11:44 PM (reads: 1277, responses: 0)
After reading "Beyond Type Classes" from the publications page, it seems that CHR rules are a very useful and general system, yet still decidable, unlike (e.g.) Cayenne's dependent type system. Would any one who knows more about this care to present the pros and cons here? Are the CHR rules unwieldy or difficult in practice? Is this an unqualified step forward, or are there tradeoffs?

Ehud Lamm - Re: Chameleon  blueArrow
6/27/2002; 4:59:04 AM (reads: 1157, responses: 0)
Where did all the knowledgeable people go?

Paul Snively - Re: Chameleon  blueArrow
6/27/2002; 11:11:46 AM (reads: 1217, responses: 0)
I don't know where all of the knowledgeable people went, so here's an opinionated one to misrepresent them.

My admittedly informal sense is that, broadly speaking, the constraint folks are onto something, and the concurrent constraint folks in particular. I'm extremely impressed with how Oz manages to subsume the object-oriented, functional, logic, and imperative paradigms within the concurrent constraint paradigm.

Moving more specifically to Constraint Handling Rules, perhaps the most impressive aspects of them are their scope of coverage and their breadth of implementation. On the first point, from the CHR home page:

CHR are a high-level language to write constraint systems. CHR make it easy to define constraint reasoning: simplification and propagation as well as incremental solving (satisfaction) of constraints. Also, CHR can be used
  • as general purpose concurrent constraint language with ask and tell,
  • as fairly efficient production rule system,
  • as special kind of theorem prover with constraints,
  • as system combining forward and backward chaining,
  • for bottom-up evaluation with integrity constraints
  • for top-down evaluation with tabulation

  • for combining deduction, abduction and constraints
  • as high-level language for manipulating attributed variables
  • for parsing with executable grammars

On the latter point, please see the "How to get CHR for free" section at the end of the home page.

As a professional server-side Java developer facing some applications that have definite configuration/optimization characteristics, I think CHR as expressed through tools such as JCK are quite exciting.

I hasten to add, however, that this is in the absence of any evaluation of the relative merits of their theoretical underpinnings or of any personal experience with their application. Caveat emptor.

Patrick Logan - Re: Chameleon  blueArrow
6/27/2002; 10:28:22 PM (reads: 1004, responses: 0)
Wow. More good links from Paul. Thanks.