Lambda the Ultimate

Concept programming is a shift in focus. Most existing paradigms, like objects or functional programming, focus on the "mechanics" of code production (i.e. "objects are a useful code structure, let me add it to the language"). Concept programming, by contrast, focuses on the process of turning ideas into code. More precisely, the set of ideas that are relevant to the code, which is what I call "concepts". Concept programming is very programmer-centric, rather than computer-centric. There are no particular code constructs called "concepts" in a concept-oriented language. Rather, there are concept representations, and then the question becomes: "what is the best possible representation for that class of concept", from a programmer's point of view.

Under this light, object-oriented programming can be summarized as: "you transform a verb-noun relationship in the concept space into a method-object relationship in the code space". In other words, you turn "Draw - Window" into "window.draw()". This analysis immediately highlights one important truth which happens to be the cause of important and subtle errors made by users of OO languages: a concept that doesn't fit this "verb-noun" relationship won't fit well in OO without some "lateral thinking" (i.e. non-OO tools).

Case in point: the concept of "maximum". In a strict OO language (that is a language where "everything is an object" like Smalltalk), you force-fit the "maximum" concept to the existing language, in a way reminiscent of Orwell's "Newspeak" in 1984. For instance, you can have something like a "maximum" object to which you send the "compute" message, or conversely, you can send the "max" message to number objects (the Smalltalk approach), turning "max" into a verb. Both yield relatively unnatural handling of "maximum", which for instance will have trouble dealing with the actual type signature of "maximum" (which is roughly: it takes any number of arguments of any type with a less-than operator). Being forced to use an unnatural concept representation is what I call a concept cast.

Actually, the tools to represent something as simple as "maximum" are not as widespread as one might think. See the XL implementation of maximum (http://cvs.sourceforge.net/viewcvs.py/mozart-dev/mozart/xl/TESTS/instantiation/minimax_vararg_generics.xl?rev=1.7&view=markup). There are a number of features in this short piece of code that, to my understanding, are unique to XL. No, even Lisp or OCaml can't represent "maximum" as well, sorry ;-)

A pointer to the XL web site (http://xlr.sf.net) was given here before (topic: XL?). I think XL cannot be understood properly without understanding concept programming first. Furthermore, that particular implementation is still very primitive compared to the one on the mozart web site, so it is not a good way to evaluate the language. On the other hand, this is now the active branch, and if people in this community want to help, there will be enough work for everybody.

Also, concept programming has very little to do with the term "concept" as used by Stroustrup (in another recently discussed topic), although I'm hope that the mails I sent him in 2001 and 2002 on this topic were a significant influence in his thinking :-)

Added after edit: Definitions are at http://mozart-dev.sourceforge.net/cp-definitions.html

So what is a `natural' way of handling maximum?

There are a number of features in this short piece of code that, to my understanding, are unique to XL.

So what are they?

No, even Lisp or OCaml can't represent "maximum" as well, sorry ;-)

Why not?

C++ does ok:

template<typename T> struct min_impl {
 T result;
 bool init_yet;

 min operator()(T a) {
  if (!init_yet) { result = a; }
  else {
   result = (result < a) ? result : a;
  }
  init_yet = true;
  return *this;
 }

 operator T() {
 return result;
 }
};

template<typename T>
min_impl<T> min(T a) {
 min_impl<T> ans;
 return ans(a);
}

int main() {
 int i = min(1)(2)(51)(-3)(21);
}

I have implemented the Max concept in O'Caml and Common Lisp to find out.

The CL version goes like this:

;; concept
(defgeneric less-than (x y))


;; use the concept
(defun mymax (n &rest other)
  (if (null other)
      n
      (let ((result (apply #'mymax (first other) (rest other))))
          (if (less-than result n)
         n
         result))))

;; test it
(defmethod less-than ((x number) (y number))
  (< x y))
(mymax 1 2 -3 43 21) 


(defmethod less-than ((x string) (y string))
  (string< x y))
(mymax "a" "c" "b")

O'Caml:

(* concept *)
module type Ordered = sig
  type t
  val compare : t -> t -> int
end


(* use the concept *)
module Max (Ord : Ordered) = struct
  let rec mymax = function
      n :: [] -> n
    | n :: other ->
        let result = mymax other in
        if (Ord.compare result n) < 0 then
          n
        else
          result
end


(* test it with ints *)
let module M = Max (
  struct
    type t = int
    let compare = Pervasives.compare
  end
) in M.mymax [1; 21; 2; 5; 7]


(* test it with strings *)
let module M = Max (String) in M.mymax ["a"; "c"; "b"]

Yes, there is slight syntactic overhead, but what is different from this in a concept-oriented language?

So what is a `natural' way of handling maximum?

I gave a link (http://cvs.sourceforge.net/viewcvs.py/mozart-dev/mozart/xl/TESTS/instantiation/minimax_vararg_generics.xl?rev=1.7&view=markup). "Natural" is subjective, but I think the structure of the code above is close enough to an english description of the mathematical concept (line breaks to match the XL code):

A type is "ordered" if for two ordered A and B A<B is a boolean

The maximum of a single ordered value X is X Max of an ordered X and other values is given by first computing the Max of the other values if the result is less than X then the maximum is X

There are a number of features in this short piece of code that, to my understanding, are unique to XL.

So what are they?

I thought it'd be obvious to people on this site, or at least that some would try to figure it out ;-) Here are some I can think of:

- Dealing with variable argument lists based on recursive, strongly-typed, compile-time instantiation - The ability to create standalone compile-time parameterizations like "ordered". - The ability to add specifications for such parameterizations.

No, even Lisp or OCaml can't represent "maximum" as well, sorry ;-)

Why not?

They lack some of the required features. If you think I'm wrong, please show me code in another existing language that matches the structure of a mathematical definition as well as the XL example. I will address the attempts given by others in a separate post.

- It takes about 5 or 6 times as much code

- There are a number of concepts in your code that have no equivalent in the application domain.

-There is a lot of "syntactic noise", like use of < to mean something else than "less-than". Or the need for the caller of your implementation to write min(1)(2)(3) instead of min(1,2,3) which is arguably the "natural" (i.e. default for non programmers) notation.

- There is even more semantic noise, like the ugly init_yet, which means that a second call to your Max doesn't do what the normal "Max" does (but I think you could add more code like a ctor to fix that). Or the need to go through the intermediate step of creating a template class. Or the "interesting" error message you get if you try min(std::cerr)(std::cerr) (on my compiler, it's 36 lines long for a similar example, I did not test your precise code, but it's probably about as long. You are invited to find anything in there that tells you the problem is a missing less-than operator!)

In other words, your code is a very good illustration of why concept programming is needed. The fact that you consider such terrible code "OK" is a problem. If you have so much trouble coming up with decent code for something as simple as Maximum, imagine what the average code looks like for something complicated like a modern car drive-by-wire logic...

Yes, there is slight syntactic overhead, but what is different from this in a concept-oriented language?

The lack of "slight" syntactic (and semantic) overhead :-) But then, what is a factor of 5 or 6 between friends?

I have skimmed some of your papers and I do not understand what you mean by concept.

A concept is something from the application domain that is relevant to your program. So the notion of less-than comparison using a syntax like X<Y is a concept in our example. Something like "ordered" is not a necessary concept for Maximum, but a helpful one.

The idea of a "compare" (or "less-than") function, on the other hand, is not a concept. It is an artificial construct introduced because of a limitation in the tool you use. That's something I call "syntactic noise": you are forced to change syntax not because you want to but because you are forced to.

Similarly, the fact that both your Lisp and OCaml implementations somehow have to create lists is artificial. The lists in there are not concepts in the application domain. You don't need them when you define "Maximum" in the application domain. Having to introduce lists is an example of what I call "semantic noise". You don't necessarily change the syntax (well, you do in your case, but...) but you change the meaning. Another example of semantic noise: the fact that in most languages an integer wraps around at, say, 32-bits. No change in syntax, but a change in semantics.

Again, in the code, there is no "concept", only concept representations. And concept programming simply teaches that these representations better be good ;-) Your representations are not really awful, but they are far from perfect. Minimizing the amount of semantic or syntactic noise pays back in terms of maintenability, performance, etc.

I am confused as well by what exactly you mean by "concept". My running hypothesis is that a 'concept-oriented language' has two properties: (1) it has adequate expressiveness of its kernel language (as explained in appendix D of CTM), and (2) it has adequate linguistic abstractions to express a 'concept' at the application level. That is, there is a combination of semantic and syntactic support for 'concepts'. A 'concept' is then simply a linguistic abstraction that allows to express part of the application without 'irrelevant clutter' in either the syntax or the semantics. This has always been part of good language design!

template<typename T>
T min(const T & a, const T & b) {
 return (a < b) ? a : b;
}

template<... T>
tuple_element<0,T>::type min(T a) {
 return std::min(get<0>(a), apply(mymin,cdr(a)));
}

Yes, there is slight syntactic overhead, but what is different from this in a concept-oriented language?

The lack of "slight" syntactic (and semantic) overhead :-) But then, what is a factor of 5 or 6 between friends?

By my count, the lisp implementation is shorter than the XL one.

At first I thought 'concepts' are related to abstractions. Since sw abstractions are something of a hobby horse for me, I was full of hopes.

But I have to say that after looking at the site and reading your messages here that I simply don't get it. ADTs for example, are about well defined interfaces. The interface specifies the abstraction boundary. Modules implement information-hiding and protect the components from abstraction breaking. Obviously, modules are a concerete language construct (i.e, each module system has well defined semantics).

What are the corresponding cognitive tools you are offering? What do you propose to add to the ADT model (and I agree that it needs augmenting)?

I am confused as well by what exactly you mean by "concept".

What english means by "concept", with the only twist that I restrict it to concepts that are relevant to a particular program.

My running hypothesis is that a 'concept-oriented language' has two properties: (1) it has adequate expressiveness of its kernel language (as explained in appendix D of CTM), and (2) it has adequate linguistic abstractions to express a 'concept' at the application level.

It's probably correct.

That is, there is a combination of semantic and syntactic support for 'concepts'.

Not exactly. ...support for concept representations. The concept itself stays in the application domain. That's unlike "objects" or "functions" that live in the code domain.

Darn, I emphasized representation about 3 times already, but it seems very hard to pass that critical piece of information accross ;-)

A 'concept' is then simply a linguistic abstraction that allows to express part of the application without 'irrelevant clutter' in either the syntax or the semantics.

No, a concept representation is a linguistic abstraction of a concept. And I agree with the note about irrelevant clutter.

The one important thing your rephrasing doesn't cover is: there isn't a limited set of concepts, so a concept-oriented language must have these properties not only for basic concepts like integer or addition, but also for user-defined concepts like maximum, symbolic derivation or translating a statement in a compiler. I gave an example of the first one, Maximum. The other two:

Derivation (see http://cvs.sourceforge.net/viewcvs.py/mozart-dev/mozart/xl/TESTS/parser/external_pragma.xl?view=markup):

{derivation} y := dsin(x)/dx

Translation of instructions (used in the XL compiler, see http://cvs.sourceforge.net/viewcvs.py/xlr/xl2/bootstrap/xl.translator.xl?view=markup and search for "translate input"):

translate inputParseTree
  when
    if 'Condition' then 'Instructions'
  then
    TranslateIfThenStatement Condition, Instructions

This has always been part of good language design!

As illustrated by the counter-examples in C++ or OCaml above ;-) Seriously, this is common sense, so it's bewildering how badly applied it is. As soon as someone tells you, for instance, "everything is an object" or "everything is a function", they are no longer following concept programming design. There are entities in the application domain which are demonstrably non-objects ("maximum") or non-functions ("1").

I had looked at the link, but couldn't understand it till I read your explanation.

A type is "ordered" if for two ordered A and B A<B is a boolean

This is a bit confusing. Are A and B types or values? On one hand, it makes sense to say a type is ordered, but not a value so I conclude they are types. On the other hand, it makes sense to apply < to two values, but not two types (unless you're really ordering types, of course). I assume they are values, and A<B is just a verbose way of declaring the type of <. (I don't see the purpose of naming the result C either.)

They lack some of the required features.

What features?

If you think I'm wrong, please show me code in another existing language that matches the structure of a mathematical definition as well as the XL example.

This is Haskell:

class Ordered t where
  (<=) :: t -> t -> Bool


x `min` y
  | x <= y = x
  | otherwise = y


minimum = foldr1 min


instance Ordered Char where x <= y = ord x <= ord y

ex1 = 'a' `min` 'X'
ex2 = minimum ['a','X','A','v']

It says:

Type t is `Ordered' iff it supports a binary operator <= of the right type.

The min of x and y is x if x <= y, else it is y. The compiler infers the type of min as

(Ordered t) => t -> t -> t

The minimum of a non-empty list:

2 : 3 : 0 : 666 : ...

is

2 `min` (3 `min` (0 `min` (666 `min` ...)

The compiler infers the type of minimum as:

(Ordered t) => [t] -> t

([t] is the type of lists of t.)

And finally, Char is `Ordered' by comparing character codes.

There is a slight difference between my minimum and your Min; mine fails dynamically on the empty list, whereas yours presumably gives a static error. But this is easily addressed.

- Dealing with variable argument lists based on recursive, strongly-typed, compile-time instantiation

See below.

- The ability to create standalone compile-time parameterizations like "ordered".

This is possible in many languages with parametrized modules, including Ada, OBJ, ML, Haskell, ...

- The ability to add specifications for such parameterizations.

I do not recognize anything that I would call a specification in your program. To me, this would be something like a statically provable assertion that <= is transitive or reflexive.

Similarly, the fact that both your Lisp and OCaml implementations somehow have to create lists is artificial. The lists in there are not concepts in the application domain.

One could as well argue that there is no necessity for your Min to be defined for arbitrary numbers of arguments (`variadic'). The usual mathematical definition of minimum, after all, is as a binary function.

If you really insist on variadic minimum, though, what is the big difference between writing Min(1,3,7) and minimum[1,3,7]?

It looks to me like you have just built lists into XL, not avoided them. Even your recursive structure is list-like. In ML and Haskell, at least lists can be user-defined. If someone needs to support something else, like say taking the minimum of a multiset of arguments (rather than a list), then they can define that themselves, or pull in a library; with XL, to treat them in an analagous variadic way, they must wait for you to extend your language implementation.

BTW, what is the type of your Min?

Another example of semantic noise: the fact that in most languages an integer wraps around at, say, 32-bits.

If it wraps at N, it is not an integer; it is an integer modulo N. The blame here lies not with the language, but rather your conflating two distinct things. If you need an integer datatype then you should write one, or import it from a library.

What english means by "concept", with the only twist that I restrict it to concepts that are relevant to a particular program.

Well, Webster's Collegiate says: "an abstract or generic idea generalized from particular instances". This is not formal enough and not targeted enough toward programming. I think that if you want your idea to get accepted, you will have to give a better definition.

PS: I understand the distinction between 'concept' and 'concept representation'. To do it right your way would require giving a precise definition of the application domain, which you don't do!

I think you need a little more precision.

To Jim Apple:

A factor of 5 may be an exaggeration counting characters. I doubt it is much of an exaggeration in terms of the complexity. How much time do you need to explain the C++ version to another programmer? You need to explain why min_impl is there. You need to explain why you used operator (). Etc.

The Lisp implementation is not shorter. Removing all spaces and comments, and excluding all but the first example (with ints), Lisp comes at 272 chars and XL at 270. Tie, yes, shorter, no. But then, I claim that it's because the Lisp version doesn't describe "ordered" at all. And for each user of this max implementation, there is a need to add a less-than definition. So the more you use it, the more expensive it gets.

- There are a number of concepts in your code that have no equivalent in the application domain.

What does that mean?

min_impl is something in your code that a mathematician wouldn't need to describe maximum.

There is a lot of "syntactic noise", like use of < to mean something else than "less-than".

Huh? Where?

I was waiting for this one :-) template < uses a < sign for a non-< meaning :-)

Or the need for the caller of your implementation to write min(1)(2)(3) instead of min(1,2,3) which is arguably the "natural" (i.e. default for non programmers) notation.

That's a syntax/human factor, not a semantic differrence.

The "human" factor is the key focus of concept programming, so that's important to me. The fact that it's a syntactic and not semantic difference is why it was classified as syntactic noise and not semantic noise.

In any case, the intent of the code is clear enough to pass as "ok," even if not ideal.

No, the intent is not clear. The intent is clear to someone who has been simming in C++ for 10 years. Now, thought experiment. Go see an average college grad with little programming experience. Show the XL code, show the C++ code. What do you expect? I personally believe that the amount of confusion generated by the XL code will be a few times less that of C++ for that particular case.

- There is even more semantic noise, like the ugly init_yet, which means that a second call to your Max doesn't do what the normal "Max" does (but I think you could add more code like a ctor to fix that). Or the need to go through the intermediate step of creating a template class.

So, C++ functions should handle variable numbers of arguments. If this proposal gets passed by the standards committee, we could write something like:

template<typename T> T min(const T & a, const T & b) { return (a < b) ? a : b; }

template<... T> tuple_element<0,T>::type min(T a) { return std::min(get<0>(a), apply(mymin,cdr(a))); }

I have been a member of the C++ committee for 2 years. And I have written e-mail to Stroustrup, Vandevoorde and others describing my "other" implementation in XL, or the generic validation process (remember the paper about "concepts" written by Stroustrup?). It's been working in an XL compiler for at least 3 years.

I hope some ideas will pass from XL to other languages. XL is not finished, it's not backward compatible, etc. I am not trying to make it a secret. It's even open source, and has been for about 4 years. Please, take the ideas, implement them in OCaml or others, that's all I ask for.

But please, please, try to understand concept programming before implementing them. Then, the human factor will be much improved ;-) For instance, your proposal addresses only one of the 3 semantic noise instances I described.

They lack some of the required features. If you think I'm wrong, please show me code in another existing language that matches the structure of a mathematical definition as well as the XL example. I will address the attempts given by others in a separate post.
I don't know what features you require, but the algebraic specification language has Maude has stongly-typed variable lenght argument lists and parameterization. For example, the maximum operation parameterized by a totally ordered set (see the manual for the totally ordered set declaration).

(fmod MAX(T :: TOSET) is
  protecting SET(TOSET)(T) .
  op max : NeSet(TOSET)(T) -> T@Elt .
  var E : T@Elt .
  var S : NeSet(TOSET)(T) .

  eq max(E) = E .
  ceq max(E S) = E if max(S) < E .
  ceq max(E S) = max(S) if not (max(S) < E) .
endfm)

Maude has just almost every feature I've seen on the XL pages with the exception of IO and references.

I can't find a factor of 5 or 6, but nevermind.

Something like "ordered" is not a necessary concept for Maximum, but a helpful one.

What would it mean to find the maximum of things which are not ordered?

So the notion of less-than comparison using a syntax like X<Y is a concept in our example. ... The idea of a "compare" (or "less-than") function, on the other hand, is not a concept.

I have the slight feeling you are trolling. Is the "notion of less-than comparison" when written "X<Y" different from the notion when written "less-than X Y"?

I really do not understand your approach, Christophe. You want to present your ideas, but treat people that want to find about them like they were idiots. Heck, I don't want to make down your ideas by presenting the same code in other languages, but I want to find out if there's a real difference. From your comments I am unable to learn about the difference.

I doubt it is much of an exaggeration in terms of the complexity.

Good point. In that case, however, I think the O'Caml implementation has tied with you in terms of complexity.

By the way, what type of min return?  It looks like Ordered.  Can I do things with it that Ordered does not gaurentee, like addition?

- There are a number of concepts in your code that have no equivalent in the application domain.

What does that mean?

min_impl is something in your code that a mathematician wouldn't need to describe maximum.

I think that programming will always be an exercise in translation.. Is i t really feasable for one language to have enough constructs to allow a concept-for-concept translation of everything in even one field like mathematics?

How would you express in XL the idea that there is a category of all categories, for instance?

In any case, the intent of the code is clear enough to pass as "ok," even if not ideal.

No, the intent is not clear. The intent is clear to someone who has been simming in C++ for 10 years. Now, thought experiment. Go see an average college grad with little programming experience. Show the XL code, show the C++ code. What do you expect? I personally believe that the amount of confusion generated by the XL code will be a few times less that of C++ for that particular case.

I'm talking about the client code, but I see you are talking about the implemetation code, which is rather complex.

I'm very concerned about what will be included in the next standard.  Some things are obviosly needed, but unlikely to be included: Real macros, variadic templates and functions, and persistence. BTW, are XL generics really working yet?

For instance, your proposal addresses only one of the 3 semantic noise instances I described.

The three were:

• ugly init_yet - I fixed this with a constructor, as you said
• intermediate step of creating a template class - I admit this is a problem, my only solution is the C++ addition, or Boost Preprocessor
• min(std::cerr, std:::cerr) - addressed last time

It's no use comparing the Lisp implementation with an implementation in a statically typed language; Lisp cannot express the statically computable part of the semantics.

I was waiting for this one :-) template < uses a < sign for a non-< meaning :-)

Despite the smiley, I feel compelled to remark that this is a very silly criticism. There are only so many characters to go around; that is why parsing was invented. One could as easily criticize your XL syntax because it uses = or . in the import declaration. (. doesn't really have the meaning of a `full stop' there, now does it?) If I want to define a function which IMO is most naturally named return I don't think I could do it in XL either, right?

Syntax is the easiest part of a language to change; if the worst part of C++ were its syntax, we would all be using C++ with a new concrete syntax right now.

BTW, what do those programs in the other links you mention do? `derivation' (is that differentiation?) and `translate input'.

At first I thought 'concepts' are related to abstractions

They are. Abstraction is the process of turning concepts, which exist in our heads, into code, which exists in the computer. That's what I mean by the difference between concept and concept representation.

To the computer, the two following pieces of code are almost identical:

function Factorial(N : integer) return integer is
    if N = 0 then
        return 1
    else
        return N * Factorial (N-1)

and

size_t MultiplyByTwo(size_t NotACat) {
    size_t Cat;
    return !NotACat ? -~0 : MultiplyByTwo((Cat = NotACat, --Cat))*NotACat;
}

The human factor is what makes the second worse, not code efficiency or any other measure (it's probably shorter in char count). That is what concept programming focuses on.

ADTs for example, are about well defined interfaces. The interface specifies the abstraction boundary. Modules implement information-hiding and protect the components from abstraction breaking. Obviously, modules are a concerete language construct (i.e, each module system has well defined semantics).

The ideas behind ADTs are good. What concept programming highlights is how limited the implementations are. For instance, why do we need a "private" keyword in C++?

What are the corresponding cognitive tools you are offering? What do you propose to add to the ADT model (and I agree that it needs augmenting)?

The focus is on human perception of code, not on particular constructs. Constructs are only a consequence.

First, I'm not just augmenting, I'm deliberately changing things. To take another simple example, double and float model real numbers, so they are called "real" in XL. double and float are implementation details, and not even the same (one is a precision specification, "double precision", the other is a format specification, "floating-point"). What does the idea of floating have to do with numbers? Why is the "double" word not used for doubling?

For ADT specifically, the major change is that there is no "privacy" in XL, data hiding means that data is really hidden. To be honest, most of this doens't work yet, even in the more advanced Mozart compiler. But in theory, you can declare that a complex type has 4 fields, Re, Im, Rho, Theta, and then implement two as data members and two using setters and getters. To the user, it's impossible to know. Not even a "private" part will leak information on the implementation.

For abstraction construction in general, the major contribution is inspired by Lisp. Just as in Lisp, code is essentially a data structure that you can manipulate at will. So it's pretty easy to add a syntax like the "translate" statement. When you need to represent a new concept, you add a new language plug-in (call that a "macro" if that helps) that implements it. It is much like Lisp, with the difference that a lot of focus is placed on making sure it "reads right", not just that the semantics are OK. Also, it's done entirely at compile time, rather than a mix of compile-time and run-time as in Lisp. That simplifies the machine model.

I feel we are now getting to the heart of the matter ;-)

I think the structure of the code above is close enough to an english description of the mathematical concept

I had looked at the link, but couldn't understand it till I read your explanation.

Well, that's a bad mark for me. In the new compiler, I changed the declaration syntax so that it reads "A, B : ordered". I've found that it helps many people.

A type is "ordered" if for two ordered A and B A<B is a boolean

This is a bit confusing. Are A and B types or values? On one hand, it makes sense to say a type is ordered, but not a value so I conclude they are types. On the other hand, it makes sense to apply < to two values, but not two types (unless you're really ordering types, of course). I assume they are values, and A<B is just a verbose way of declaring the type of <. (I don't see the purpose of naming the result C either.)

I don't see why you are confused regarding type vs. value. When we say "two integers X and Y", "integer" is a type, but X and Y are integer values. How is it different in what I wrote above? So A and B are values of the ordered type, and I say the type is ordered if for these values I can write A<B.

Important: unlike in other languages (examples were given here), I am not declaring the type of <, I am declaring a usage pattern. I don't care about the type of <, I care that I can write A<B.

You are right that there is no purpose in naming the result C. That's the one piece of syntactic noise I acknowledge in the example :-) There is a way to remove it, but it makes the code more noisy. Similarly, there is a slight semantic difference between "can be assigned to a boolean" and "is a boolean".

They lack some of the required features.

What features?

I listed them already: the ability to declare "ordered" as I do is one. The ability to deal with the concept of "maximum" without having to introduce the concept of list is another.

This is Haskell:

This is about the best I saw so far in any language but XL :-) This is quite good from a semantic point of view, barely OK from a syntactic one in my opinion, but that's very personal.

One thing is that I don't see the relationship between "ordered" and "min". Is there a way to rewrite the example to make sure that min works only for ordered items? Another thing I'd like to understand is: how would you do if min didn't cascade the way it does (meaning that min(x,y,z)=min(x,min(y,z)), which makes your foldr1 trick possible. For instance, let's say you want "average" instead of min, how do you do?

I don't think it's compile time varargs, though. You did introduce the notion of list in there, and so the varargs are really done at run-time using list manipulations. There is a concept cast here, and this particular concept cast has a runtime performance impact. (see below)

- The ability to create standalone compile-time parameterizations like "ordered".

This is possible in many languages with parametrized modules, including Ada, OBJ, ML, Haskell, ...

Certainly not in Ada. You can't declare an "ordered" entity so that writing a function taking an ordered argument makes that function generic. Generics in Ada are always explicit.

For the other languages, every argument is generic by default, so in a sense, you are right :-) But this is done through run-time typing, with type-inference as an optional optimization. As soon as you introduce static typing, I don't think you are in a better position that Ada. Your example didn't prove me wrong (yet), since it defines a 'min' that takes any argument of any type. It's likely you can restrict 'min' to 'ordered' things, so I guess Haskell may be able to do it, from the opposite direction (i.e. starting with the 'everything is generic' by default).

- The ability to add specifications for such parameterizations.

I do not recognize anything that I would call a specification in your program. To me, this would be something like a statically provable assertion that <= is transitive or reflexive.

I don't need that when I implement Max or Min. So it's not there. You are asking for over-specification, I believe.

One could as well argue that there is no necessity for your Min to be defined for arbitrary numbers of arguments (`variadic'). The usual mathematical definition of minimum, after all, is as a binary function.

... which is why mathematicians keep writing max(u(0),u(1),...,u(n)) and things like that ;-) In other words, I disagree.

If you really insist on variadic minimum, though, what is the big difference between writing Min(1,3,7) and minimum[1,3,7]?

From a concept programming point of view, practically zero in terms of syntactic noise, relatively signficiant in terms of semantic noise. Requiring lists is practically equivalent to introduce a garbage collector in the language definition. I call that a biggie. It means my program no longer fits in a small 16-bit microcontroller ;-)

It looks to me like you have just built lists into XL, not avoided them. Even your recursive structure is list-like. In ML and Haskell, at least lists can be user-defined. If someone needs to support something else, like say taking the minimum of a multiset of arguments (rather than a list), then they can define that themselves, or pull in a library; with XL, to treat them in an analagous variadic way, they must wait for you to extend your language implementation.

You are assuming too much if you believe I can't add:

function Max(S : set of ordered) return ordered is ...

to the previous definitions. My recursive structure is not list-like at all, it is entirely evaluated at compile time. In the end, the code contains exactly what is needed to evaluate Max on the various argument combinations found in the program, nothing more, and in particular no list. Not that XL doesn't have lists, but they are a module, as optional as floating-point numbers or I/O, not some built-in language construct.

BTW, what is the type of your Min?

It's an overload set at compile time. At run-time, which function in the overloat set is being used has been determined, so talking about the "type of Min" doesn't make sense, you can only talk about the type of a particular call to "Min" or of a particular "Min" function.

Another example of semantic noise: the fact that in most languages an integer wraps around at, say, 32-bits.

If it wraps at N, it is not an integer; it is an integer modulo N. The blame here lies not with the language, but rather your conflating two distinct things. If you need an integer datatype then you should write one, or import it from a library.

Yes, but the name is "integer", not "integer_mod_32". Hence the semantic difference between the concept and the concept representation. Hence the semantic noise, aka "you'd better know about it". That's the whole point. Of course, you can create a module where "integer" is a bigint. And then, you simply push the limit slightly further (i.e. you are now limited by the size of your memory). So you didn't solve anything. In my opinion, it's better to simply stick to "integer" being a limited, 32-bit approximation of the integer concept, but know its limits.

However, reading your answer regrading ADTs, I must agree with PVR: you need more precision. I would also suggest exploring different languages. Most everything you propose is doable quite naturally using existing constructs (I'd add the ML module language to the list of of languages to check up on).

When I first started to study sw abstraction in detail I had many ideas that correspond to the things you suggest. Howeve, I soon realized most of these ideas were either naive or already implemented..

I am unsure about your remark re the private keyword. If a concept is 'abstract' (i.e, without implementation) no private part is needed. But even when it is needed, the keyword is the syntactic represenation of an essential concept of ADTs: representation hiding. An idea that you seem to endorse, so I don't understand what's bothering you.

Re moving between polar and cartesian complex numbers: A simple OO-based approach is straightforward. For more sexy approach check up on views (Wadler).

Your definition of "concept" is very precisely the definition of "concept" I use. As I said, the only restriction is that I am not interested in concepts that are not relevant to the program. For instance, the "maximum of an infinite suite" is probably not relevant to most programs, so I ignored it in my implementation. It might be relevant in a theorem-proving program, in which case my implementation of maximum would not be the correct representation. What is imprecise or wrong in using english terms in their default meaning? That we are so used to calling "objects" things that are not objects, so that when someone calls "concept" something that is a concept, he suddently becomes difficult to understand?

Definition of "application domain": the domain of application of the concept we are considering. Again, it's hard for me to phrase that otherwise. The application domain of integers is called arithmetic or math or whatever, depending on the precise "integer" concept you refer to. The important thing is that it's in your head, not in the code.

Added after edit: Please refer to the terminology given in the Mozart web pages: http://mozart-dev.sourceforge.net/cp-definitions.html.

First, all my apologies if you feel like I'm treating you like an idiot. That was not my intent at all.

Something like "ordered" is not a necessary concept for Maximum, but a helpful one.

What would it mean to find the maximum of things which are not ordered?

That's why it's helpful. But then, you can write a typeless implementation of "maximum", or an implementation where the notion of "ordered" is only implicit (in the fact that the implementation uses the < sign).

So the notion of less-than comparison using a syntax like X<Y is a concept in our example. ... The idea of a "compare" (or "less-than") function, on the other hand, is not a concept.

I have the slight feeling you are trolling. Is the "notion of less-than comparison" when written "X<Y" different from the notion when written "less-than X Y"?

Syntax. The human factor. The whole focus of concept programming, as I indicated since the beginning. This is not trolling. It's stating that writing X<Y conveys the same concept in a more concise, more natural manner. You did not write "less-than" because you wanted to. You wrote "less-than" because your language of choice wouldn't let you use the notation you are used to, < That's Newspeak at work.

I decided to focus on a factor that is largely ignored in language design, the "how well does the concept translate into code" factor. Because it has been deliberately ignored for ages, programmers are used to ignore it. A Smalltalk programmer doesn't mind that 1+2*3 is 9 and not 7. But for concept programming, that's semantic noise, because of the mismatche between the semantics of the code and the semantics of the concept that this code is supposed to represent.

I really do not understand your approach, Christophe. You want to present your ideas, but treat people that want to find about them like they were idiots.

I don't understand why you feel I'm "treating people like they were idiots". Whatever it was, I apologize for it. I am not rephrasing things and chaning angles because I feel you are idiot, but because you are telling me that you don't understand. So I try again. It's my failure, not yours.

Heck, I don't want to make down your ideas by presenting the same code in other languages, but I want to find out if there's a real difference. From your comments I am unable to learn about the difference.

So far my explanations didn't help. You have no idea how sorry I am about this, really. I know that most novel ideas need to be repeated 29 times on average, but still ;-) Look at the non-code aspect of it first. Think of a concept as the thing in your head. Then you want to turn that into code. At this point, you start deviating from the original concept left and right. I can't write <, OK, I introduce a generic named "less-than", that's good enough. I can't have variadics? That's OK, I'll work on a list instead, because the syntax for lists is convenient. I can't write min(a,b) in my language? OK, I'll write a `min` b instead, that's close enough. And so on.

That's what bugs me. If you decide that it's not necessary, then it's no longer acceptable. XL is a language where none of the above is necessary. You can write <, you can use variadics, you can write min(a,b,c). It's not perfect, but I'm trying to remove as many obstacles as I can.

I agree.

[But, remember that some syntaxes are more arbitrary than others...]

By the way, what type of min return?� It looks like Ordered.� Can I do things with it that Ordered does not gaurentee, like addition?

With the current compiler, yes. The check is done at the time some code tries to use "Max", but no check is done within Max, not even to check that it actually uses < (the one-arg Max doesn't, for instance). If it is too inflexible, the tool becomes a nuisance.

I think that programming will always be an exercise in translation.. Is i t really feasable for one language to have enough constructs to allow a concept-for-concept translation of everything in even one field like mathematics?

No. And that's not the point at all. That's where my definition of "concept" is restricted compared to the standard definition, as I wrote above, to cover only the concepts that are relevant to the program. Most of the field of mathematics is irrelevant to programming in general, even more is irrelevant for any given particular program.

How would you express in XL the idea that there is a category of all categories, for instance?

I first need a program where the category of categories would be in the application domain. Otherwise, I have no idea how to represent a "category". By the way, I probably need to punt on this example, because I don't understand "category" in this context. All I know is that there is no set of sets, so that must be different from set. Google didn't help me there...

I'm talking about the client code, but I see you are talking about the implemetation code, which is rather complex.

Ah, OK.

I'm very concerned about what will be included in the next standard.�

That's a sign of wisdom :-)

Some things are obviosly needed, but unlikely to be included: Real macros, variadic templates and functions, and persistence. BTW, are XL generics really working yet?

In the Mozart compiler, to a large extent, yes, though they don't have specialization yet. In the XLR compiler, the bootstrapped one, not yet. I bootstrapped without real generics (or even real semantics, for that matter).

After edit: the comment in the complex module you linked to was placed there at a time where generic support was not sufficient. I could rewrite that code using generics now, I think it's actually somewhere else in the test tree.

ugly init_yet - I fixed this with a constructor, as you said

You fixed the functional issue, not the fact that you need it because of a language limitation. You need to go through a class and operators for user-side syntactic convenience... There are a few dozen levels of implicit reasoning behind your implementation, and if I was not familiar with C++, your implementation would have totally puzzled me...

intermediate step of creating a template class - I admit this is a problem, my only solution is the C++ addition, or Boost Preprocessor

Well, to be honest, I think you simply need to give up on variadicity, and accept a low-bandwidth representation of the concept, like

template <typename T> T max(T a, T, b) { ... }

Much much simpler, but lower bandwidth (two args only). For that particular case, that would be my preferred representation of the concept in C++. With maybe some checking that there is a less-than using one of the many known tricks to that effect.

min(std::cerr, std:::cerr) - addressed last time

Using a third-party tool (STLfilt), and then it tells you that the problem is that it's not copiable, when it's not obvious in the code why you need to copy :-) But I think your answer is close to "state of the art" for C++.

I was confused because the code says:

ordered A, B

which I naively read as "A and B are ordered", and one does not say, for example, "2 and 73" are ordered, but rather "Char and Int are ordered".

[What features?] I listed them already: the ability to declare "ordered" as I do is one.

Yeah, but I don't see what is so special about the way you declared it.

The ability to deal with the concept of "maximum" without having to introduce the concept of list is another.

That may be your concept of "maximum", but it isn't the only one. In particular, when I think of "maximum" I always think of a binary function on pointed posets.

This is quite good from a semantic point of view, barely OK from a syntactic one in my opinion, but that's very personal.

Isn't that sort of the problem? You may find XL very intuitive because you developed it to express your worldview; but your worldview is not everybody else's. If `intuitiveness' is such an important factor that it dwarfs things like, say, static expressiveness, then no one language (for example, XL) can be possibly be very useful for more than a small group of people.

One thing is that I don't see the relationship between "ordered" and "min". Is there a way to rewrite the example to make sure that min works only for ordered items?

min already only works for Ordered types. The relationship between them is implicitly communicated by the use of <= in the definition of min. The compiler notes this, and assigns to min the type:

(Ordered t) => t -> t -> t

which says that the two inputs must be of a type t which belongs to class Ordered.

Another thing I'd like to understand is: how would you do if min didn't cascade the way it does (meaning that min(x,y,z)=min(x,min(y,z)), which makes your foldr1 trick possible. For instance, let's say you want "average" instead of min, how do you do?

To define average generically you obviously need some more operators like addition and division, so here is a really sloppy but straightforward way to do it:

class (Ordered t) => Num t where
  unit :: t
  (+) :: t -> t -> t
  (/) :: t -> t -> t


sum1 = foldr1 (+)


avg m n = m + n / (unit + unit)


average ns = sum1 ns / sum1 (map (const unit) ns)

The (Ordered t) => Num t says that for t to be a Number it must be Ordered.

The types assigned here are:

sum1 :: (Num t) => [t] -> t
avg :: (Num t) => t -> t -> t
average :: (Num t) => [t] -> t

However, this is a very lame sort of definition. First, because it is factored badly and missing some commonly essential stuff like negation. Second, because for something like <= to work right it only has to satisfy about three properties, whereas for average to work right there are about 20.

Doing this sort of thing properly requires a familiarity with some basic abstract algebra. For example, I would factor (+) out to a class Monoid, and define stuff like groups and rings as intermediaries, and rename the class that implements average to Field. But that sort of thing is not really realistic even in Haskell, and especially with standard type classes.

I don't think it's compile time varargs, though. You did introduce the notion of list in there, and so the varargs are really done at run-time using list manipulations. There is a concept cast here, and this particular concept cast has a runtime performance impact. (see below)

In practice (though the compiler can perform whatever optimization it likes) it's run-time, yes, but who really cares? Usually you only care about the minimum of two or perhaps three things (in which case you use min) or you want the minimum of a list. Do you honestly think that anyone who writes code like this:

for (i=1; i <= 1000; i++)
min(a[1][i],a[2][i],a[3][i],a[4][i],a[5][i])

will ever be able to grasp how to do `generic' programming anyway?

If you really insist on compile-time, then I might be able to do it in Generic Haskell but IMNSHO it is a real abuse of genericity.

Your example didn't prove me wrong (yet), since it defines a 'min' that takes any argument of any type.

Good grief, you almost gave me a heart attack! I would never do such a thing. Ask anyone. :)

Nononono! min only takes types which belong to class Ordered. In the program above it only takes type Char, because that was the only one I defined an instance for. (Well, and Int, whose instance I purposely left out.)

I guess Haskell may be able to do it, from the opposite direction (i.e. starting with the 'everything is generic' by default).

No, nothing is Ordered (or `generic') by default.

I don't need [transitivity or reflexivity of <=] when I implement Max or Min. So it's not there. You are asking for over-specification, I believe.

No, I am only asking Max and Min to behave like functions which actually return maxima and minima. You are the one who criticized programming languages for calling `int32' `int'; why are you willing to be so liberal with `Max' and `Min'? If <= is not at least transitive and reflexive, then `Max' cannot possibly behave `correctly'.

I wrote: The usual mathematical definition of minimum, after all, is as a binary function.

You replied: ... which is why mathematicians keep writing max(u(0),u(1),...,u(n)) and things like that ;-) In other words, I disagree.

Mathematicians are notoriously sloppy formalists. I would be the first to say programming languages should emulate mathematical notation, but this is not one of the features worth carrying over from mathematical practice. Anyway, a programming language is a formal construct, and any mathematician will tell you that that notation is meant to be informal.

BTW, why stop there? If you are going to define max and min as variadic, why not just extend every binary function with a right unit (or even without) to be variadic? That seems to me to be the uniform, logical conclusion of your approach, else the programmer has to remember which functions are variadic and which are only binary but could be extended to be variadic. In Haskell, it's easy to remember: if f is binary with right unit 0, then foldr f 0 is the `variadic' version.

You are assuming too much if you believe I can't add:

function Max(S : set of ordered) return ordered is ...

That is analagous to my minimum function, which takes a single value which is a list, but not your Max function, which takes multiple values, which are a sort of sequence. The proper analogy for XL would be a construct like:

Max{0,1,2,3}

with which you can somehow statically guarantee that, for example:

Max{m,n} = Max{n,m} = Max{m,m,n}

My recursive structure is not list-like at all, it is entirely evaluated at compile time.

What I meant by `list-like' is that it has a binary car/cdr-like structure.

[The type of Min is] an overload set at compile time. At run-time, which function in the overloat set is being used has been determined, so talking about the "type of Min" doesn't make sense, you can only talk about the type of a particular call to "Min" or of a particular "Min" function.

So what happens if I try to pass Min to a higher-order function? Then you cannot statically decide the number of arguments it will be called with.

Yes, but the name is "integer", not "integer_mod_32". Hence the semantic difference between the concept and the concept representation. Hence the semantic noise, aka "you'd better know about it"

That is not `semantic noise'; if anything it's syntactic noise, since the problem is easily resolved simply by renaming the type.

I was waiting for this one :-) template < uses a < sign for a non-< meaning :-)

Despite the smiley, I feel compelled to remark that this is a very silly criticism. There are only so many characters to go around; that is why parsing was invented.

Not so silly. That choice was made by someone who understands parsing like Dan Quayle understands quantum mechanics (quizz: where does this quote come from?)

When you write f < g && h > i (j, k) in C++, what does that mean? Answer: it depends on the definition of f. If f is a suitably defined template, this is a template instantiation. Only "by default" is it a less-than test. The point that there is a unnecessarily confusing syntax is a valid one.

One could as easily criticize your XL syntax because it uses = or . in the import declaration. (. doesn't really have the meaning of a `full stop' there, now does it?)

Well, you could, but IMHO, the criticism would not be nearly as founded. The choice of "angle brackets" in C++ creates ambiguities (like the infamous A<B<C >> issue...) My choice of syntax for import doesn't cause any ambiguity that I am aware of.

If I want to define a function which IMO is most naturally named return I don't think I could do it in XL either, right?

Actually, in the XLR version, you will ultimately be able to. That was a limitation I was not happy with, and I now know how to get rid of it. You'd better be careful with readability, though.

Syntax is the easiest part of a language to change; if the worst part of C++ were its syntax, we would all be using C++ with a new concrete syntax right now.

That's no excuse for a bad syntax full of ambiguities, is it?

BTW, what do those programs in the other links you mention do? `derivation' (is that differentiation?) and `translate input'.

Aiiiie! Thanks, I now understand why people had so much trouble with the derivation example. You are right, that's a translation mistake (from French). I did mean "differentiation".

"translate input" is an application-specific extension added to XL specifically for the compiler and compiler plug-ins. It performs the analysis of a parse tree. It's sort of a "switch" statement specialized for parse trees, with the possibility to do some pattern matching to isolate subtrees.

You stated that < and less-than are the same distance from the thing in your head. To me, it's like stating that assembly language and C++ are computationally equivalent. One notation is still more convenient than the other...

If given a real choice between writing A<B and (less-than A B), which one would you chose by default? Does your tool give you that choice?

can you make indentation significant (python, haskell)?

are there any reserved characters? can you alter the lexing? maybe i want to model a concept where ">8" is a name for some entity - is that possible?

i'm curious how you the implementation from becoming very complex.

[on edit - or code in columns/tables or right-to-left scanning?]

I was confused because the code says "ordered A, B"

Yes, this is source of confusion. Would "A, B : ordered" have confused you less?

Yeah, but I don't see what is so special about the way you declared it.

It has C++ "direct to the metal" compilation semantics, but more Haskellian concept representation capabilities.

That may be your concept of "maximum", but it isn't the only one. In particular, when I think of "maximum" I always think of a binary function on pointed posets.

How often do you need "pointed posets" in programs? Does this pass my "relevant to the program" filter for many programs you use daily?

Isn't that sort of the problem? You may find XL very intuitive because you developed it to express your worldview; but your worldview is not everybody else's. If `intuitiveness' is such an important factor that it dwarfs things like, say, static expressiveness, then no one language (for example, XL) can be possibly be very useful for more than a small group of people.

Applied relativism 101 :-) Back to facts, do you argue that XL static expressiveness is poor? Or that your problem understanding "ordered A, B" at first dooms the whole approach? I'm more interested in a positive approach, like: does "A, B : ordered" feel more natural?

min already only works for Ordered types. The relationship between them is implicitly communicated by the use of <= in the definition of min. The compiler notes this [...]

OK. I need to think more about this.

[about average]

This example is much less satisfying to me. I need more time to grok the philosophy there.

In practice (though the compiler can perform whatever optimization it likes) it's run-time, yes, but who really cares?

I do. It's a whole machine model that doesn't fit for many applications. "the compiler can perform whatever optimizations it likes": NOT. The semantics impact the possible optimizations. XL argument passing semantics give it an edge over C by a factor of 70% on some machines.

No, I am only asking Max and Min to behave like functions which actually return maxima and minima. You are the one who criticized programming languages for calling `int32' `int'; why are you willing to be so liberal with `Max' and `Min'? If <= is not at least transitive and reflexive, then `Max' cannot possibly behave `correctly'.

I see your point now. You are correct, defining Max on a partial order would be a source of trouble. I don't think I have a compile-time solution right now (there is a run-time solution), but I'll sleep on it.

Why not just extend every binary function with a right unit (or even without) to be variadic?

I think that too fails the "relevant to the program" filter for most programs.

That is analagous to my minimum function, which takes a single value which is a list, but not your Max function, which takes multiple values, which are a sort of sequence

Yes. I'm saying I can do both, depending on the actual concept you need to represent.

What I meant by `list-like' is that it has a binary car/cdr-like structure.

I see. Yes, there is a "first" and a "rest". On the other hand, I can also add a construct, like "set_function", which evaluates all arguments as a set, and passes that. That's the point of language extensibility.

set_function Max (S : set of T) return T

Now you can write Max(1,2,3,4,5) and have the set be built at compile-time.

So what happens if I try to pass Min to a higher-order function

Two-part answer.

1/ High-order functions are not a core language feature, but part of the library. There are context where they are not desirable. Optional, like floating-point, I/O, memory management, garbage collector, etc.

2/ This problem has been dealt with successfully multiple times. How does CLOS resolve multiple methods implementing the same "function"? You simply get a "larger" function that deals with the various cases. Same here.

That is not `semantic noise'; if anything it's syntactic noise, since the problem is easily resolved simply by renaming the type.

Semantic noise is a change in semantics. Saying that "integer" wraps around is a change in semantics, so it's semantic noise. The problem is not solved by renaming the type, since in doing so you also change the concept being represented.

The descriptions below apply to http://xlr.sf.net, not to the earlier http://mozart-dev.sf.net implementation.

How do you manage conflicting syntaxes?

Carefully :-) They are best avoided.

say you're using one package based on c++ template syntax and another where "<" is for ordering.

First, I'd recommend avoiding that.

Then, the general rule is "most specialized first", much like for C++ templates. If you have an expression matching A+B and another matching A+B*C, everything else being equal, you'd use A+B*C.

how does your language extension handle that? is there some kind of namespace that disambiguates the two? can you change the namespace syntax?

There are scopes and modules, so you can create local namespaces.

can you make indentation significant (python, haskell)?

Indentation is significant, but it yields to parentheses and block delimiters (that last bit is still a bit undecided).

are there any reserved characters?

Not really. Sequences of letters/digits are names, sequences of "other" chars are symbols. Some symbols are special in that they open/close blocks, like ( and ) or { and }.

So A+(B*C) parses as (infix+ (name A) (block() (infix* (name B) (name C))))

can you alter the lexing?

Yes and no. The compiler is open-source, so you can. But it's not recommended. There are no reserved keywords, "keywords" are identified by the structure. So the compiler recognizes "if A then B", but will ignore "if" in other contexts.

maybe i want to model a concept where ">8" is a name for some entity - is that possible?

Not with the current extensibility mechanism. Yes by changing the lexer, which is simple enough.

i'm curious how you the implementation from becoming very complex.

You can define pretty ugly things for sure. But then you don't have to.

[on edit - or code in columns/tables or right-to-left scanning?]

Can't do that without modifying the parser. On the other hand, all the parser needs to generate to use the rest of the compiler is the 7 node structures, so it's pretty simple to write a modified / derived parser.

The focus is on semantic extensions, not syntactic ones.

Please excuse me for my grumpy remark. I was irritated by some of your reactions to the alternative implementations.

You wrote, to Jim, "The fact that you consider such terrible code "OK" is a problem." I find this rather rude.

You repeatedly talked about a factor of "5 or 6" in code length which I cannot see. The point of having to add defmethods for new data types in the Lisp code is a moot point, because XL has to define the meaning of < somewhere, too.

You insisted on XL's approach to variadic argument lists being superior to lists, which I find a trivial issue. Moreover, the XL approach requires two function definitions for Max (one for the single argument case, one for the polyadic(?) case), which are exactly analogous to the pattern matchings (n::[] and n::other) in the O'Caml code, and the (first other) and (rest other) in Lisp.

Each of the alternative implementations is embedded in the larger framework of its language, in which it makes sense. Please accept that your approach is not the absolutely natural approach, just because you think so.

(And no, < is not more natural than less-than, and vice versa. It depends entirely on your background and what you are used to.)

This is a complete side issue, but when I think of "maximum", I think of a variadic function on a partially ordered set, not necessarily pointed. (Consequently, the maximum function may not be complete.) This cannot necessarily be computed in the pairwise function suggested either for XL or Haskell; both of these assume that the variadic arguments are fully-ordered. For example, taking subset as the comparison function, max({a}, {b}, {a, c}) will incorrectly return {a, c} if the comparisons are done left to right. In this case, max can be correctly computed by applying least-dominator pairwise over the arguments and then checking if the result is one of the arguments; that comes closer to my intuition about what maximum means.

As another example, IEEE arithmetic requires max(x, NaN), max(NaN, x), min(x, NaN) and min(NaN, x) to all return x for any x. However, x<=NaN is false for any x, and consequently max cannot easily be defined in terms of <=. (Whether this is good, bad, or just a standard is debatable, but there is a plausible explanation.)

This concept of maximum is used, for example, in Dylan's rule for method dispatch: of the applicable prototypes available, Dylan computes (at compile-time if possible) the maximum (by type dominance) and dispatches to the corresponding method, or throws an exception if there is no maximum. (The Dylan reference manual does not describe this as maximum, but it is a concept that I, at least, recognize as a maximum.)

Trying to wrestle this intervention back to the topic, I guess the point here is that sometimes trying to reduce concepts to other concepts doesn't work as well as you might think it would.

Christophe: Not exactly. ...support for concept representations. The concept itself stays in the application domain. That's unlike "objects" or "functions" that live in the code domain.

Darn, I emphasized representation about 3 times already, but it seems very hard to pass that critical piece of information across ;-)

Christophe,

I'm not clear on what a concept is. I don't want to repeat the question "What is a concept?" Because you've answered that already and I'm still confused. After much pondering, I think I am really trying to ask a different question. The real question is "What is a concept representation?" I hope the following makes it clear what I am asking.

Here are definitions of two senses of object from dictionary.com:

5. Something intelligible or perceptible by the mind.

6. In object-oriented programming, objects include data and the procedures necessary to operate on that data.

These are the two senses of object that I usually used in discussions of OOP. To be clear in this discussion, I write 'object' when I use sense 5, and when I use sense 6 I leave off the quotes and just write object.

I am using 'object' to denote something in the real world, and object to denote something in the computer (e.g. procedures bound to data). I think this is analogous to the way you use concept and concept representation, i.e., 'object' is to object, as concept is to concept representation. And it is important for later that I now point out that definition of object (sense 6) does not make any use of 'object' (sense 5).

I feel you are going against convention with the term Concept Programming. Let me give you examples:

A language that supports object-oriented programming is one that supports manipulating objects. Here the word object refers to something that exists in the computer, not 'objects' that exist in the world.

A language that supports functional programming supports manipulating functions as values. Here the word function refers to something that exists in the computer, not a mathematical function.

A language that supports aspect-oriented programming supports manipulation of aspects. Though I haven't seen a consensus on precisely how the word aspect is defined, it is always defined in terms of the code or program, and not something outside the computer.

Therefore when I read the phrase Concept Programming, I think it must mean programming with some construct called a concept, which exists inside the computer. But you have made it clear that a concept is something existing in our heads. So instead of asking the question "What is a concept?" I really mean to ask "What is a concept representation?" and I would expect that an answer would be in terms of things that exist in the computer. This is analogous to asking "What is an object?", "What is a function?", or "What is an aspect?"

Update: Objects are not usually created to be in one-to-one correspondence with 'objects' in the problem domain. So likewise could there be a concept representation that does not correspond to any concept in the problem domain and still be useful?

(Variadic? Are you sure you don't mean a function from the powerset of the underlying set of points? That is not the same as a variadic function.)

Oops, I didn't mean "pointed poset"; I was thinking of a join-semilattice. In fact, I completely botched that implementation because my <= returns a boolean, which implies the order is total. I'm not sure off the top of my head how best to fix this. If we restrict to finite or freely generated posets, then it is probably better to describe both the order and the join operation simultaneously from the primes or generators.

BTW, to me, regarding max as join seems eminently natural because a `join-semilattice' is a structure in which each pair of points has a join, and Christophe was computing them pointwise via what looked like a total function. If the order is total, then the result of binary join is always going to be one of its arguments.

The truth is, however, that I'm not really interested in what a "natural" definition of "max" is; that is a question for semiotics, not programming language theory. What I'm interested in, rather, is, given a well-defined notion of "max", whether or not I can accurately model it effectively.

I did mean a function on the power set of the underlying set, but I don't see why I can't call that variadic: binary functions do not cease to be binary just because they are commutative. However, I am not emotionally invested in the terminology.

If the order is total, then the result of binary join is always going to be one of its arguments.

True, but consider computing "maximum" on the powerset of the set of functions where the comparison is fastest computation. The pairwise computation could easily fail to terminate even on a set where the result is well-defined. Arguably, that is not a totally ordered set, but even in non-pathological shortest-path computations, solution by pairwise comparison is somewhat less than optimal. (Another interesting example is maximum defined by lexicographical comparison on long lists.)

that is a question for semiotics, not programming language theory. What I'm interested in, rather, is, given a well-defined notion of "max", whether or not I can accurately model it effectively.

I would not want to argue with that. However, it seems to me that Christophe's concept of "concept" introduces semiotics into programming language theory. Perhaps it is simply the case that "maximum" is a bad example: explaining the concept of "maximum" in terms of a concept of boolean comparison might simply be a bug. Perhaps it makes more computational sense to define binary comparison in terms of "maximum" (join)

And, for what its worth, given that streaming-media extensions natively implement max and min in the CPU, avoiding the problem of branch-prediction, it might be a good idea for programming languages to implement them as primitives as well.

Yes, I pointed out earlier this was the root cause of the confusion. There is no single representation of a concept. Look at http://xlr.sourceforge.net/info/concept.html. The same concept, "addition", is represented in a variety of ways: built-in operators, user-defined operators, functions, methods, assembly mnemonic, sequence of bits, or, if you deal with chip design, a particular organization of logic gates.

So for any particular concept, what I'm interested in is "what is a good representation of this concept" from a software engineering perspective. This means a) that I don't care about all the aspects of the concept that are irrelevant to the program (thus, for 99% of all programs, I have strictly no interest in the pointedness of sets or in the maximum of infinite series rather than of a sequence of numbers), and b) that I care about the engineering properties of the result (is it well specified, is it safe to use, is it efficient, etc).

My "maximum" example has no other point. It doesn't claim to be universal or perfect, but to have rather good engineering properties (it's reasonably readable, is reasonably specified (even if not everybody agrees with my spec, at least there is a spec), which in turns makes it reasonably safe to use, and it generates reasonably efficient code (provaly better than the other examples that were given here on my machine).

So, concept programming doesn't give you things that you can put in the code and call "concepts". At least, not at first sight, more on this later. But it does give you some interesting tangible tools to work with in selecting what tool you use to represent a concept. Notably a set of pseudo-metrics for evaluating the code. I call these pseudo-metrics, because metrics on "meanings" cannot be defined formally, yet they "make sense". For instance, consider some definitions on http://mozart-dev.sourceforge.net/cp-definitions.html. Definitions there are not strictly formal, but they probably make sense to most, just like dictionary definitions.

Syntactic noise evaluates the presence of syntactic elements in the code that don't carry signal for the program concepts. When in C you write if(a), the parentheses don't represent a concept but a tool limit (it has to be able to parse your code). This is an example of syntactic noise. Semantic noise evaluates the presence of unwanted semantic differences between a given concept representation and the concept it is modelled after. I already gave the example of "integer" size limits in any language (bigint don't solve the issue, they just push the limit farther).

Both forms of noise are very subjective, I fully realize that. Somewhere on the web site, I wrote that what is noise to one person is music to another. I also fully realize that many here are not comfortable introducing subjectivity in the otherwise formal world of programming languages. Yet that's precisely what I focus on.

Let's get back to the less-than and maximum issue. I see no difference between writing less-than and writing < in the code as long as it's a free choice. But for that particular case, it's hard for me to believe that it is a free choice, because the mathematical notation is so universal, and because less-than is significantly longer to type for no benefit in readability. So for now, bear with me if I say that choosing "less-than" was a constraint imposed by the development tool being used. If that's true, then I rightfully call that syntactic noise. For the same reason, I call "min(1)(2)(3)(4)" more noisy than "min(1,2,3,4)". And again for the same reason I call the creation of a list at run-time or the creation of a min_impl class instance more noisy than their absence, because they have semantic side effects that are not desirable (meaning that they differ observably in some cases from the semantics of "nothing").

Why does this all matter, and what does it have to do with programming? Writing code is the process of transposing ideas into code, and maintaining code is mostly the opposite. If the relationship between the code and the concept is clear, then design, implementation and maintenance are all facilitated. From a language design point of view, this means removing as many obstacles as you can from representing as many kinds of concepts are you can. And this means in some cases adding language features that would be absolutely non-obvious otherwise.

The "other" syntax is, I think, an example of such a non-obvious consequence. It first appeared to implement text I/O. Here is the rough outline of how it appeared:

• I want I/Os in my language
• The simplest I/O representation is BASIC's PRINT statement, cause I can put anything I want in there, like PRINT "A=",A. The WriteLn statement in Pascal is similar. Since it's the simplest form, I want to be free to write it that way.
• But it's built-in, which is inflexible. C proposed library-based I/Os, which are more flexible. I also want to be free to have this flexibility.
• But C I/O library is not type-safe, which is dangerous. I want to be free from errors imposed on me by limits of the tools.
• Ada and Java do run-time concatenation. String concatenation works for text I/O only, not for binary I/O or any other "variadic" for that matter. So it's just taking advantage of a special case. I want to be free from this limitation. Also, string I/Os are expensive at run-time. I want to be freed from this cost.
• C++ uses << operators in cascade, which is free and doesn't involve much runtime cost. But I've now cut a single "write" concept into tiny pieces, which prevents me for instance from writing consistent messages in a thread-safe way. I want to be free to create a thread-safe I/O facility.
• So to implement WriteLn in a library, I really need type-safe variadics. How do I do that?
• A conceptual description is to recurse on the list of arguments. So find a way to represent "extra arguments". Introduce the "other" keyword.
• And finally, validation: does the newly introduced variadic syntax allow me to define a writeln that looks and acts like Pascal's WriteLn? Yes. Is it type safe? Yes? Is it useful for representing other concepts? Yes. Is it code efficient? Yes. Is the syntax understandable with moderate explanations? Yes. Can it be made thread safe? Yes.
• OK, let's add that feature to the language.

There are a number of other features in XL that were introduces in a similar way, and with the similar objective of removing obstacles towards representing concepts. One, in particular, is interesting. It makes XL the most Lisp-ish of all C-like programming languages: XL is defined by a standardized parse tree which programs can manipulate. Despite its relatively classical syntax, it's really a simple parse tree inside (7 node types, so that's just a little more than Lisp). The concept programming reason here is that there is no finite set of concepts, so you need some language extension mechanism to be able to add concept representations for families of concept that are not easily represented by other means. A Lisp-er would call that a "macro". So if a concept can't be represented by a function, an object, an operator, a module, whatever, then you can think about adding a meta-programming capability that allows you to represent the concept in a way you are comfortable with.

That's the point of the symbolic differentiation example. There are many concepts which are really too narrow or application-specific to ever be put in a compiler. So you want the end user to be able to represent such concepts comfortably without having to request a compiler change which won't happen. That's also the point of "minority" languages such as Prolog, languages that think different.

The end result of XL allows a large number of concepts to be represented in a natural way. Arithmetic written using standard notations (including, if you want, for concepts like linear transform or "is between" represented by compound operations like A+B*C or A<B<C). I/O looks like BASIC or Pascal, yet is library-defined. Some other concepts I did not implement yet, but I know how to do it... Tasking can look like Ada, yet is library-defined, so if you want a fine-grained parallelism instead, or a syntax adapted to distributing work over a grid, you can do that as well. Logic-programming feels like Prolog, yet is library-defined, so you can also try Alpha-style equation resolution if that's a better model for you. High-order functions behave as Lisp, yet are library-defined, so you can also stick to basic C-style functions if you need to take the address of a function. You can mold the type system to have an object syntax that looks exactly like C++, despite the fact that the default semantics is much closer to CLOS (multi-methods, etc). Just as you can have multiple object models coexist, multiple exception handling mechanisms can coexist (do you want your exceptions do be throwaway as in C++, resumable as in Visual Basic, or "discsiplined" as in Eiffel?) And you can add AspectJ's aspects or Hyper/J's hyper-modules if you need them.

Now, the short answer to your question: "What is a concept representation"? The answer is: whatever you feel comfortable with. XL tries to be as much out of the way as possible and let you be creative.

In the XL compiler implementation, I have this concept of translating a statement. In my head, it does some pattern matching on a parse tree, and then executes the code with portions of the matches tree isolated. So a little XL extension was added which does just that.

translate inputParseTree
    when
       if 'Condition' then 'Statements'
    then
        CompileIfStatement Condition, Statements

The precise definition of this statement is that it matches inputParseTree with the parse tree it created for 'if [PlaceHolder] then [PlaceHolder]'. If there is a match, then it declares Condition and Statements as two variables that can hold a parse tree, and assigns to them the value of the two placeholders. Finally, it executes the code in the "then" part. Since that's what I wanted, that's exactly what this statement does. The statement is not part of XL. What is part of XL is the ability to add the statement.

That is one example of concept representation. Give it another name if you want. The most generic term, I think, is really "concept representation".

I would strongly suggest, however, that you take a different tack in promoting your activities. The grandiose language about "concepts" and "a new state of the art in programming" displays, to me at least, a lack of awareness of what is actually going on in current programming language research.

From what I can see, what you refer to as "concept programming" is simply the effort to provide appropriate tools (semantic and syntactical) to represent the programmer's intentions (their "concepts") clearly and correctly. That's the goal of every language designer, so you don't need to give it a fancy and vague name and pretend you came up with it yourself.

The only messages I get out of the max example is that 'languages should have first class functions' (==> Java sucks) and 'lots of syntax overhead for defining generics is bad' (==> C++ sucks). Fine. But 'max' and 'maximum' are pretty much a solved issue to me, in Haskell at least. (Yes, a join-semilattice version would be cute, but I'd use it infrequently enough that I don't mind the standard max being limited to total orders.)

There are reasons that current languages are limited, and none of them seem to "get everything right". If you want to join the debate constructively, it would help immeasurably to get a better appreciation for what other people have done and are trying to do. The people (here and elsewhere) involved in language design and debate are a really sharp bunch, yet we waste a lot of time when we don't synchronize our vocabularies and define our concepts. (It's funny, a lot of the best papers posted on LtU get no discussion at all -- since they're clear enough that there's nothing to debate!)

Maybe a post or page along the lines of "why I like type-safe variadic functions" or "minimal syntax for defining typeclasses" would be better met -- you'd certainly get a more focused debate, at least, and you might even learn something.

p.s. on the unifying-functional-and-object-oriented-programming front, Scala seems like a really nice effort (after a day playing with the 1.0b release). Highly recommended.

The point is not the commutativity.

The point is that there is a difference between a function which has a well-defined domain (or type) such as a list or sequence or set, and a set-or-whatever of functions indexed by some collection (an "overloaded" function). The first is just a run-of-the-mill formal object, and I would not call it variadic. If you call such a thing variadic, the concept becomes pretty trivial. For example, you would need to defend the argument that every function on the integers is variadic, since an integer can be represented as, say, a bit string, and every such function could then be regarded as a collection of functions indexed by the bit position.

True, but consider computing "maximum" on the powerset of the set of functions where the comparison is fastest computation. The pairwise computation could easily fail to terminate even on a set where the result is well-defined.

Don't you think this sort of thing is a bit of a stretch? I'm not saying that defining n-ary join in terms of binary join is always going to be the best thing to do, computationally, though I do think for most purposes it's fine. But, in fact, I don't think I ever stipulated that one must be defined in terms of the other; you could give separate implementations, for example. I only want to be sure that, denotationally, any custom implementation is the same as the one in terms of binary join; if not, then fine but just don't call it a semilattice!

Arguably, that is not a totally ordered set, but even in non-pathological shortest-path computations, solution by pairwise comparison is somewhat less than optimal. (Another interesting example is maximum defined by lexicographical comparison on long lists.)

I don't see why that would be the case; the computer has to look at every pair no matter how you implement it.

Perhaps it makes more computational sense to define binary comparison in terms of "maximum" (join)

Again, I have no problem with that provided that the denotations/behaviors agree.

Since max is associative, I am happy to write the Haskell: 3 `max` x `max` f x It's type-safe, and no lists were harmed in the filming of this example.

GCC actually has (non-standard) associative <? and >? operators for representing min and max respectively, which come in handy for writing terse and clear code in programming contests.

(trying *not* to open up the printf vs. iostreams can of worms... should be safe on LtU where C and C++ partisans run for cover...)

In addition, it would be useful to draw links to existing work in the areas of extensible languages, macros, and domain-specific languages, which share very similar (if not identical) goals, and already have well-developed vocabularies for discourse.

"Flexible-representation programming" (not as catchy, but more specific?) certainly seems like an interesting and worthwhile goal.

I can, however, foresee a couple of major pitfalls along this road:

1) Not all programmers start out with a good (consistent, mathematically plausible, etc.) set of concepts in their head! Frank and others spend a lot of time here trying to clear up conceptual errors, even among the way-above-average LtU crowd. I find that good programming languages often help clarify my thinking and improve my mental concepts by forcing me to conform to an internal mathematical discipline. Good type systems come to mind -- often people who complain about typing problems in Haskell or C++ have committed deeper design flaws they are trying to work around. If "Concept Programming" was succesful in molding the language to however individual programmers think, would better programs really be the result?

2) If I understand correctly, the XL concept is based on source-level (tree-level, whatever) language transformation tools which can arbitrarily extend or change the syntax and semantics of the language. Take a look at any discussion of macros in Lisp and scheme (or recent papers criticising AOP) for all the problems that can arise with composition of arbitrary program transformers. Macros have been around for a long time, and 'hygienic' macros for a while, and yet the jury is still out on their use. How do you address all the issues that arise when Bob decides on call-by-need and Yolanda wants call-by-value in different parts of the same application? What about when Charlie wants every computation to be reversible, and Zoe adds non-determinism?

You wrote, to Jim, "The fact that you consider such terrible code "OK" is a problem." I find this rather rude.

Point taken and, actually, perfectly valid. I did not mean to be rude, but I think it was much too easy to interpret it that way. I do find that code "terrible", because it has a very high semantic and syntactic noise. That was not meant as a statement of Jim's coding abilities.

You repeatedly talked about a factor of "5 or 6" in code length which I cannot see.

As I pointed out in another post, I was referring to code complexity. Being a compiler guy, I tend to always think in terms of generated and executed code. I won't post it here because nobody cares about assembly, but the generated assembly for the C++ "main" is 51 instructions, 6 of which are subroutine calls. The generated assembly for the XL "main" is 19 instructions, one of which is a subroutine call. So I stand by my "5 or 6" factor for that precise example, though I admit I was using a lot of implicit context that really obscured the point. Jim replied that Haskell was a tie there. I disagree, based on the little I read about Haskell (I don't see how they could achieve their semantics without a rather expensive runtime), but I don't have a Haskell compiler to prove it.

My point here is that semantic noise translates into obfuscation for the compiler, which in turns translates into inefficient execution. As I wrote elsewhere, I care a lot about engineering properties of the "idea to code" translation.

Please accept that your approach is not the absolutely natural approach, just because you think so.

I don't think it's natural at all, since I don't believe anybody else actually followed that particular track. I also don't think there's an easy way to teach it, because it runs counter to the past methodologies. See the "where are the concepts in the code" questions for an example of such difficulty. On the other hand, I do believe my approach is both productive (from an engineering point of view) and new. So it's worth sharing it, even if it means being flamed and misunderstood at times.

I would strongly suggest, however, that you take a different tack in promoting your activities. The grandiose language about "concepts" and "a new state of the art in programming" displays, to me at least, a lack of awareness of what is actually going on in current programming language research.

First, what is so "grandiose" about talking about "concepts"? Concept is really what I mean here, it's really what I'm interested in. Btw, are your ridiculing the phrase "a new state of the art in programming" from a site called "Lambda the ultimate"? ;-) See below more about a justification for this "new state of the art" phrase.

Second, how do you back your ad-hominem claims that I am not aware of other research in that area? What is true is that I rank "programming language research" according to engineering value, so I tend to consider relatively futile some research that others may hold in high esteem, and I consider important things others may see as near-trivial. On my scale, Haskell rates lower than Hyper/J. That's deliberate, not ignorance on my part.

Actually, I had enough of this attitude in this thread, so pardon me while I vent...

<VENTING> The XL design takes into account at least 25 existing programming languages, many of them functional or otherwise "bizarre" (http://citeseer.nj.nec.com/dedinechin97libraries.html for an example). I worked on commercial implementations for 3 major-league languages. I've been on the C++ Standard Committee. If you run a program compiled with a recent g++ compiler, chances are you execute some code I wrote, and more code I co-designed. Next-generation C++ proposals include at least two ideas that were tested and implemented first in XL. I can explain the advantages and drawbacks of at least 3 different exception handling mechanisms, 6 object models, 4 representations of "functions", and 4 ways to match "types". I can explain and discuss "view", "pimpl", "fragile base class", "address exposure", "class features", "elaboration", "dynamic cast", "continuation", "boxing", "closure", "category", "predicate", "come from", "disciplined exception", "multimethod", "hyperslice", "traits", "recurrence equation", "contracts", "rendez-vous", "tuple", "by-name argument passing", "coroutine", "backtracking", "thread-local storage", "intention", "forward iterator", "template meta-program", "ODR violation", "instruction group", "GC safe point", "speculative load", and "please abstain"... among others.

So... I consider as posturing any disparaging comment about my lack of research, any "been there done that" attitude or any insinuation that I should study language design a little more, in particular from anybody who has no clue about half of these, what language(s) they appear in, why they matter, and what their impact on code generation is. </VENTING>

That being out of the way, I think that it's precisely because I have a rather good idea of the diversity of what is going on out there that I came up with this "concept programming" idea.

From what I can see, what you refer to as "concept programming" is simply the effort to provide appropriate tools (semantic and syntactical) to represent the programmer's intentions (their "concepts") clearly and correctly. That's the goal of every language designer, so you don't need to give it a fancy and vague name and pretend you came up with it yourself.

First, naming is important. Why do we talk about "objects"? Why don't we talk about "structures with a pointer to a list of function pointers" (referring to the C++ object model)? What is "fancy and vague" in using the term "concept programming" for the approach of focusing on the translation of concepts into code? The only thing that makes it "vague" is your limited understanding of what it is (it improves in your next post, which is good). The only thing that makes it "fancy" is that not having understood it well enough, you believe it is "simply" trivial. I demonstrate why not below.

Second, illustrating that your understanding is still limited: one key idea missing in your description of concept programming is that any concept needs to be representable as clearly and correctly as possible (There are other things missing, like efficiency, etc).

Third, how can you claim that this is the goal of every language designer? AFAIK, Fortran was about representing expressions, Pascal about program structure. You can't write dsin(x)/dx for a differential in these languages, you can in XL. Does that mean these languages failed their goal? No, I think it means you stated as a goal something that has never been a goal, just to make my work sound obvious and easy.

The only messages I get out of the max example is that 'languages should have first class functions' (==> Java sucks) and 'lots of syntax overhead for defining generics is bad' (==> C++ sucks).

Then, you definitely got the wrong message. You have the "Java sucks" and "C++ sucks" preconceptions, and then you try to use my post as a justification. Actually, where did you see anything in my posts calling for first-class functions? They are totally unnecessary in that case. They are a non-concept for that particular problem. Did you see me claim that "languages should allow one to take the address of a function (==> Lisp sucks)"? Really :-(

But 'max' and 'maximum' are pretty much a solved issue to me, in Haskell at least. (Yes, a join-semilattice version would be cute, but I'd use it infrequently enough that I don't mind the standard max being limited to total orders.)

By one definition of "solved" (something like: "we know how to write a program that computes them"), it was solved back on Eniac. But from the point of view of concept programming, it is all but "solved", not even in XL. And I can assure you it has nothing to do with join-semilattice versions :-) Why do I claim it's not solved? Because the Haskell semantics introduces a particular run-time construct (lists) that I want to avoid because of its runtime cost, and that is not necessary in that particular case. And XL introduces a syntax that is not obvious without some learning.

There are reasons that current languages are limited, and none of them seem to "get everything right".

Can you state these reasons? My position is that most of these reasons are now obsolete. That's what "new state of the art" really means in my mind. There is a new state of the art where we can now design a language that does everything other existing language can do, and does it well, in one single unified framework. This is an extraordinary claim ("grandiose", to use your words), so it demands an extraordinary proof. The proof is that I implemented a good fraction of such a language, enough to be positive that I can implement the rest.

Doing that was not possible 15 years ago, computers were too limited. Back then, you had to create specialized languages. It was not practical to design a language totally around a meta-language (Lisp is pretty darn close, it's too bad they unified run-time and compile-time program structures). Since then, we remained in the "specialized languages" mind set, but it's no longer necessary.

Maybe a post or page along the lines of "why I like type-safe variadic functions" or "minimal syntax for defining typeclasses" would be better met -- you'd certainly get a more focused debate, at least, and you might even learn something.

Then, at the time you wrote this, you totally missed the point of concept programming. What does the 'translate' extension example have to do with variadics? What does the symbolic differentiation have to do with typeclasses?

Incidentally, I haven't seen it mentioned in this thread that frequently the ability to write binary functions infix is a good alternative to variadic functions. Since max is associative, I am happy to write the Haskell: 3 `max` x `max` f x It's type-safe, and no lists were harmed in the filming of this example.

I appreciate the "no lists were harmed" ;-)

In my case, I wanted to avoid infix notation, because that's not the standard mathematical notation (for a debatable interpretation of "standard"). As I wrote elsewhere, infix notation doesn't apply for instance to "average". It is important to realize that by writing 3 max 5, you have broken encapsulation, because the notation relies on an understanding of how max is implemented and of its properties. One of my pseudo-metrics immediately flags that, yet it was probably not obvious to you at the time you wrote the comment, otherwise you'd not have suggested it as a "good alternative".

But the point that arbitrary infix notations are important is a good one. I'd simply point out the syntactic noise of the backquotes (another not-so-obvious thing red-flagged by one of my pseudo-metrics), which XL doesn't force you to add:

function Max(A, B : ordered) return ordered written A max B
X : integer := 3 max 5 max 7

It is important to be free to use such a notation. It is also important to not be forced to just because there is no alternative.

Now, what about a concept represented by more than one infix, like a linear transform? For correctness, speed or precision, implementing A+B*C in one operation is often better than in two. How do you do that? Do you need to go without the infix notation, or can you actually write A+B*C in your language? Or do you feel satisfied with the Blitz++ approach? Here is XL:

function Linear (A, B, C: matrix) return matrix written A+B*C

If you still feel like trying, it's easy enough to prove that I didn't do my research and that my stuff has already been done. Show me a link to another language with this feature. And then show convincingly that this feature was introduced using a single global framework, such as my "grandiose" concept approach, that also led me to introduce the functionality needed for true generic types ("ordered") or for typesafe variadics ("other"), or standard program representation, or Eiffel-style contracts, or user-defined iterators. Then, you'll have something to base your "it's obvious, there's no research here" claims.

(trying *not* to open up the printf vs. iostreams can of worms... should be safe on LtU where C and C++ partisans run for cover...)

I already wrote that I/Os were actually the reason I first thought it was necessary for a language to have type-safe variadic support. Both printf and iostream are interesting. The reason discussing it is a can of worms is because there is no agreed-upon metric on what "good" means. OTOH, based on concept programming and the derived pseudo-metrics, I can quickly zoom on the problems with both printf and iostream, and come up with a solution that suffers none of them. By these metrics, the XL I/O facility is measurably superior. And it works, too, see http://cvs.sourceforge.net/viewcvs.py/mozart-dev/mozart/xl/library/xl.text_io.xs?view=markup.

Now, you already expressed the view that concept programming was trivial. I see I/O as one testimony to how non-trivial it is. Text I/O is, after all, a problem that every single programming language in the world had to address. Yet the "solutions" range from not type safe (C) to not thread-safe and code-bloating (C++) to inefficient at run-time (Ada, Java, functional languages) to not formattable (Java). And for most languages, it's not extensible for new types either. "Simple", really? Not.

Another suggestion: it sounds to me that by "concept programming" you mean "making program representations (source code) match the internal mental concepts of programmers as closely as possible, using extensible programming language tools". If I'm interpreting you correctly, perhaps you could use that or a similar sentence to precisely define your goals.

I mean roughly the first half of your sentence: "making program representations (source code) match the internal mental concepts of programmers as closely as possible. From there, the second part, using extensible programming language tools is only a consequence. It's not an axiom. It's a "theorem", derived trivially from the first axiom and the axiom/observation that the set of concepts of interest is not finite.

Now, is there general agreement here that the first part of your sentence conveys the idea better than the very first sentence on http://xlr.sourceforge.net/info/concept.html, Concept programming is initially a very simple idea: Your code should reflect the concepts in your application.? If so, I'd add it on my web site. I personally find my original formulation clearer. Notably, it adds the important notion that only the application concepts really matter. C++ programmers have an internal model for a "car" both as a thing with wheels and as a structure with function pointers, and the latter is reflected in the code. But it's not an application concept. It passes you definition, but it fails mine.

In addition, it would be useful to draw links to existing work in the areas of extensible languages, macros, and domain-specific languages, which share very similar (if not identical) goals, and already have well-developed vocabularies for discourse.

I'm afraid most of this work is incomprehensible by the majority of programmers. For instance, using the word "macro" is a blocker for 90% of the programmers who think "C macro" and get it wrong. Hence my use of the term "compiler plug-in" (there are also significant differences both in terms of implementation and usage model). The "well-developed vocabulary" you refer to is not one, it take multiple forms, depending on the community. What helps you might be an obstacle for the majority of readers. That's why I tend to try and stick with C-centric vocabulary when talking about things like "type" or "function", and sorry if that's not how you use the terms.

Similarly, if you talk about "class", what object model do you have in mind (C++, Java, Objective-C, Smalltalk, CLOS, Eiffel, to list a few which are significantly different from one another)? Don't assume I don't talk much about classes on the web site because I don't know what they are. Similarly, don't assume I don't talk much about Lisp macros because I don't know what they are. But rather because that's not my point.

You understood concept programming as mostly about Lisp macros. And you got that wrong. Macros are only a consequence; you still need to back-up a few levels before reaching the Tao of concept programming :-)

I would appreciate interesting links, however. I'm always curious and interested :-)

"Flexible-representation programming" (not as catchy, but more specific?) certainly seems like an interesting and worthwhile goal.

Not only is it less catchy, it is also somewhat wrong. The point is not to be able to write "A ! B *" for an addition. If you want to represent the concept of addition, flexibility is a counter-objective. I want people to use A+B for an addition rather than A*B, A add B, Add(A,B) or whatever notation XL would otherwise allow. Flexibility becomes an objective only for concepts that need it, basically concepts which are somewhat unique (I use the term "application-specific" on the web site).

Of course, in one sense, you are right that flexibility is a key feature (just not the root one). The same flexibility mechanism is also used to implement addition. XL programmers can represent addition using any other notation. Concept programming simply states that they shouldn't.

So concept programming is really the two sides of the coin. It allows you to write addition the way you want. It also recommends a particular notation for that particular case.

Not all programmers start out with a good (consistent, mathematically plausible, etc.) set of concepts in their head!

Ahah. You are beginning to enter a territory I find interesting. My answer to this is: not only is the problem not unique to concept programming, concept programming actually helps by forcing programmers to clarify the concepts first. Notably, one all important notion: concepts that matter to the program, and concepts that don't. The first set is what I really call "concept", it's my only alteration of the standard Webster definition.

But realize that making conceptual mistakes is not reserved to incompetent noobs. Changes in the core tasking concepts (btw, for "trivial" issues like efficiency rather than for incompleteness or mathematical plausibility) were the root cause of tasking changes between Ada-83 and Ada-95. Don't you think that having to change all compilers is a rather heavy way of solving the problem?

Good type systems come to mind -- often people who complain about typing problems in Haskell or C++ have committed deeper design flaws they are trying to work around

That is very true. On the other hand, the type system must not be an obstacle. The C++ example given above by Jim shows how the C++ type system gets in the way because it lacks variadics. The Haskell example shows how the Haskell type system (or, more generally, syntax+semantics) forces you to switch to a list (or to infix operators, or whatever other representation "fits"). Once the concept cast becomes a necessity, the programmers try to justify it as "good" (ref: the reasoning in posts above that variadicity is not needed because integers can be represented as bit strings. It's so full of logical flaws I don't even know where to begin! That puts the associated lectures on mathematics in perspective...)

If "Concept Programming" was succesful in molding the language to however individual programmers think, would better programs really be the result?

This is a serious issue. This is why it is important for XL to start with a good list of pre-implemented common concepts. My intention is to not call it "1.0" before I have at least library implementations for arithmetics (int, real, complex, matrices), text manipulation, I/Os, basic algorithms (STL-like), a couple exception handling models, object models, and tasking models. Otherwise, we'd soon be in the same situation as early C++ with the dozen incompatible "string" class implementations.

Notice, for instance, that I consider it acceptable to not have high-order functions or prolog-style logic in a 1.0. I'd expect these to be implemented anyways, by people who know this stuff better than I do, and are fully capable of implementing it. If nobody else does it, then I'd provide basic implementations for a 1.1 release, and get flamed for how sucky my implementation is ;-)

If I understand correctly, the XL concept is based on source-level (tree-level, whatever) language transformation tools which can arbitrarily extend or change the syntax and semantics of the language. Take a look at any discussion of macros in Lisp and scheme (or recent papers criticising AOP) for all the problems that can arise with composition of arbitrary program transformers.

I am aware of many of the problems, and I know they are serious. Are you advocating that since not everybody knows how to use macros, we should remove them? ;-)

What I know is that this extensibility is what allowed Lisp to survive and be a current language today, whereas Fortran is getting rather old, and object-oriented Cobol is a funny idea. CLOS is one of the best object systems around here, yet it was one of the first (the first?) to be an ANSI standard. If it weren't for Lisp flexibility, none of this would be true. Compare what it took to have objects in C (Objective-C or C++), and what it took to have objects in Lisp.

In practice, Lisp programmers tend to use these tools wisely. I trust that people will use XL tools just as wisely. But an obfuscated XL contest might be an interesting thing to watch. I'm pretty sure you could get a good INTERCAL approximation from a feature-complete XL compiler.

How do you address all the issues that arise when Bob decides on call-by-need and Yolanda wants call-by-value in different parts of the same application? What about when Charlie wants every computation to be reversible, and Zoe adds non-determinism?

Again, that is a very good question. I wish the whole discussion was at this level.

The problems of conflicting changes are what made me "abandon" the Moka approach. Moka is a Java-to-Java compiler where the value add is the ability to run plug-ins. With Moka, you can add symbolic differentiation to Java. But the granularity is entire source files, and "extensions" are specified outside of the source (on the command line).

There are many ways XL addresses the issues. XL syntax is unambiguous, and doesn't rely on semantics (unlike for C++). I tried to make it quite robust to tampering. Basic XL semantics are simple, so XL is more robust to the presence of foreign bodies. XL proposes an explicit syntax for "minority" concepts, the "pragma". "Active libraries" are interacting with the compiler in such a way that they understand the intent enough to be able to give meaningful, domain specific error messages like "This piece of code is not reversible" (which would probably be emitted for the piece of code that introduces non-determinism).

In short, this is one area where I definitely don't have the full answer, because it's not fully explored yet. But I tried to address it using common sense.

To start with, in order to check that I'm on the right track I would like to repeat back to you my understanding so far of XL and concept programming.

[Concept Programming] does give you some interesting tangible tools to work with in selecting what tool you use to represent a concept. Notably a set of pseudo-metrics for evaluating the code. I call these pseudo-metrics, because metrics on "meanings" cannot be defined formally, yet they "make sense".

I think you are saying that any code fragment, function, object, macro, etc., which embodies a concept can be a concept representation. What differentiates them is how well they satisfy your pseudo-metrics, taking into consideration both the elegance of a representation's definition, and the elegance of the code that uses them. So I conclude you can do concept programming in any language, some are just (much) better at it than others.

Everybody has their own sense of what is "right and good" code. What you've done is tried to put yours into your pseudo-metrics. You acknowledge that this is subjective and others may have there own opinions. As a shorthand I will describe code as having lots of noise if it does poorly according to your pseudo-metrics. Conversely I will describe code as elegant if it does well.

You state that you want to provide tools for creating low-noise concept representations. This is how I break the problem down (not implying anything about how you do it). I see two parts to the problem. The first part is creating a sufficiently expressive language, the second part is creating a standard library.

1. Obviously the language must be able to express important concept representations, but initially it is ok if their definitions contain noise; at this point it is only important how well their interfaces match the concepts they embody. The standard library is what will facilitate more elegant definitions.

2. The standard library must include concepts that make it possible to write low-noise definitions. After deciding which concepts are needed I would create representations of them. This is possible when part (1) is correct, i.e. the language is expressive enough to write good representations for important concepts. The standard library should also contain concepts that enable one to write low-noise definitions of concepts in other application domains.

Part (2) is naturally iterative. The definitions in the standard library start out with a lot of noise. Then as you add representations for more useful concepts, you can use them to make the definitions in the rest of the library more elegant. Also, the process as a whole is iterative. As you try to define concept representations you might go back and change the language to make it more expressive.

--------------------------------

You have two conflicting requirements. You want to be able to be able to express any representation for a concept, but you also want people to be able to reuse code via libraries. The first requirement implies that programmers needs to be able to write arbitrary lexers/parsers for their code. The second requirement means that these different parsers need to be composable somehow so they can co-exist. How do you address this issue?

With your current pattern matching scheme are any of the following representations possible?

1. Matlab style matrices: Matrix enclosed in square brackets, with values in a row separated by commas, and rows separated by semi-colons. And having the same number of values in all the rows of a matrix is required.

2. ML/Haskell style combinator libraries (point-free style): Requires higher-order functions. Function application that is the juxtaposition of a function and its arguments, no parentheses. Also currying must be the default when a function is applied to fewer arguments than it requires.

3. Perl style regular expressions.

-------------------------------

Given the high standards you have set for concept representations, ASCII is insufficient for expressing the concepts from many (well most) application domains. For example, the natural representation of GUI concepts is in graphical form. The natural representation of mathematical formulas is in something like Mathematica. When you want to express dataflow, a linear encoding is lacking. And there are many others.

The point of this is that you often need some form of artificial encoding to fit a program into ASCII. So when you need to encode so much else, what difference does it make if there are parentheses, square brackets, or nothing around a function's arguments?

--------------------------------

Another personal opinion on terminology. A metric is a measurement. Calling something a metric (or even pseudo-metric) that you can't use to determine a number contradicts the apparent meaning of the word. Also I would like to point out that subjectivity and formality are not opposites, or even exclusive of one another.

-------------------------------

Here I will mention a few things that I think are missing from the previous discussion of XL and Haskell. (Forgive the argumentative tone of the following, but it is difficult to avoid in this sort of comparison.)

You criticize Haskell because of the performance impact of processing the list at runtime versus compile time.

This doesn't hold water. First of all, in the min function processing the list at runtime or compile time does not change the algorithmic complexity of the function. Both ways of expressing min and max are linear. So I would be dubious of any performance claims without some measurement. Second, a compiler could easily perform the same optimization on the Haskell version as the XL version. The only additional complexity is a rule which says if a function recurses over the structure of a list, and it is applied to a list with a known length at compile time, then the recursion can be unrolled (or whatever sort of optimization you want to perform). If I understand XL correctly, this is more flexible than XL. For example you could do the following and still use same the optimization:

foo = [x, 3, 5, 2]


i = minimum foo
j = maximum foo

But in XL you would need to do this:

i := Min(x, 3, 5, 2)
j := Max(x, 3, 5, 2)

The point is, you don't always need special syntax to guarentee that an optimization is possible.

The Haskell version of min actually has much higher "bandwidth" than the XL version.

1. It can be applied to a list with a length that is only determined at runtime, while the XL version cannot.

2. The Haskell method can be extended to support structures other than lists. In Haskell, lists are no different than any user define data type. Argument lists in XL are not so flexible. For example, in XL can you define a function the same way as Min that recurses over a binary tree?

3. In order to define Max and Min in XL, you need to repeat what is essentially the same algorithm twice. In Haskell you can make a single function that expresses the algorithm and is parameterized by the comparison function.

aggregate f x y
    | f x y     = x
    | otherwise = y


'min' = aggregate (<=)
'max' = aggregate (>=)

(forgive me if that is not exactly valid Haskell...it's been a while)

Next, one of the requirements you stated for min is a mathematical-like definition. Nobody specified (or agreed on) what form a mathematical definition of min would take, but I'm pretty certain it would not be a recursive definition. Given the constraints of ASCII, I would write a mathematical definition of min like this:

min(A) = x, such that x is in A, and for all y in A then x <= y

Neither XL nor Haskell seem particularly close to that. (Though I suspect Haskell could get closer using list comprehensions).

Wow. This is good. This is really what I expected from this site. More detailed answer in a moment. But you wrote a lot of interesting stuff, so it may take some time.

I do apologise for being harsh in my initial post, your goals (once I finally understood them) do seem worthwhile. For various reasons your presentation rubbed me the wrong way.

I think you are saying that any code fragment, function, object, macro, etc., which embodies a concept can be a concept representation. What differentiates them is how well they satisfy your pseudo-metrics, taking into consideration both the elegance of a representation's definition, and the elegance of the code that uses them. So I conclude you can do concept programming in any language, some are just (much) better at it than others.

Right on.

The first part is creating a sufficiently expressive language, the second part is creating a standard library.

Yes.

initially it is ok if [the library] definitions contain noise; at this point it is only important how well their interfaces match the concepts they embody. The standard library is what will facilitate more elegant definitions.

Yes.

The standard library should also contain concepts that enable one to write low-noise definitions of concepts in other application domains.

Yes.

Also, the process as a whole is iterative. As you try to define concept representations you might go back and change the language to make it more expressive.

Actually, I think I reached the point where most of what you'd call language changes would really be library changes. But that's an implementation detail.

You have two conflicting requirements. You want to be able to be able to express any representation for a concept, but you also want people to be able to reuse code via libraries. The first requirement implies that the programmer needs to be able to write an arbitrary lexer/parser for his code. The second requirement means that these different parsers need to be composable somehow so they can co-exist. How do you address this issue?

This was important enough to warrant the use of bold font :-)

My approach is to not give freedom for the lexer and "level-0" syntax. There is a lexical syntax, with integers, reals, text ("ABC" or 'ABC'), names (ABC or ++-, but not mixed like -A or A-B), blocks (parentheses, braces, indent), infix operators (A+B, A else B), prefix operators (-A, not Z). This, with proper precedence rules, defines XL0. XL0 parses really almost anything, including "data".

So far, it's quite simple, isn't it? Barely more complicated than Lisp, despite the Algolish look. The output tree you get obviously depends on the precise precedences of operators like comma, colon, new-line, and so on. So the next level, XL1, defines some standard precedences, so that A+B*C always parses as A+(B*C), and "if A then B" parses as (then (if A) B).

The next step up the ladder is semantics, which is almost 100% library-based. The lowest level is "translate" statements. That's how you tell the compiler how to translate if-then-else or function declarations. Naturally, there is a whole infrastructure behind this, that deals with name lookup, scopes, symbol tables, overload resolution or type-guided tree pattern matching. All this has been validated and tested in the Mozart version. It's only a matter of time before it's been all transcoded from C++ to XL.

So now you end up with the problem of composition, but limited to composing tools that work on trees, rather than arbitrary lexers. In other words, you need define the semantics of various tree functions, and try to make sure they operate in your compiler non-conflicting ways. It's trivial to show that there is no general way to prevent a conflict. Example: one operation could rewrite X+0 as X, the other X as X+0. It can take a long time to have both fight one another. Simonyi did interesting work on this kind of problem as part of the easly intentional programming research. Unfortunately, the links I had are invalid now.

But the problems as stated now is not more complicated than the problem of ensuring forward progress in computations. In other words, it's probably not computable in most cases, yet we deal with it.

With your current pattern matching scheme are any of the following [matrix representations] representations possible?

The three representations you asked for clearly show that you grok concept programming quite well ;-) Representation 1 is a natural fit given the default parsing priorities, though testing for the sizes would be something to add in the corresponding 'translate' statement.

% cat ./test.xl
[
1, 2, 3, 4;
5, 6, 7, 8;
9, 10, 11, 12
]
% ./xl -tparse ./test.xl
(PAREN [(((((1 , 2) , 3) , 4) ; (((5 , 6) , 7) , 8)) ; (((9 , 10) , 11) , 12))] PAREN)


The natural currying of functions is there too from a parsing point of view, but not necessarily from a semantic point of view. That is, 1 2 3 is actually parsed as (1 (2 3)), but it doesn't mean that 1 is seen as a high-order function, or that applying an int to an int actually means anything.


Your example 3 about regexp I'm not sure. Are you referring to the existence of a "default" matrix akin to $_, to the fact that regexps don't need specific quoting characters in Perl, or to something else?


Finally, unless your code really deals intensely with matrices, I'd suggest none of the above. Precisely in the interest of lowering ambiguity, I'd suggest something like Matlab, but with some prefix.


% cat test.xl
matrix [1, 2, 3; 4, 5, 6; 7, 8, 9]
% ./xl -tparse ./test.xl
[matrix (PAREN [((((1 , 2) , 3) ; ((4 , 5) , 6)) ; ((7 , 8) , 9))] PAREN)]


Given the high standards you have set for concept representations, ASCII is insufficient for expressing the concepts from many (well most) application domains.


This is music to my ears. You showed here that intentional programming is a straightforward consequence of concept programming. Thanks. Yet, I think intentional programming mixes two things, one being the concept representation for code transformations, the second being rendering / data entry. It's not that I don't like their approach, it's that I think we are not quite ready for it yet. Yet, the notion of multiple rendering / data entry is there in Mozart, and it will be there in XL. See http://mozart-dev.sourceforge.net/moka-pretty.html.



The point of this is that you often need some form of artificial encoding to fit a program into ASCII. So when you need to encode so much else, what difference does it make if there are parentheses, square brackets, or nothing around a function's arguments?


None. That's why the semantics of XL is defined based on its parse tree. But then, it is useful to have a standard way to enter / display the parse tree.


Another personal opinion on terminology. A metric is a measurement. Calling something a metric (or even pseudo-metric) that you can't use to determine a number contradicts the apparent meaning of the word. 


I agree. Do you suggest a better word? This was the best term I could come up with.



The argument regarding Haskell requires a separate post. Another day.

The natural currying of functions is there too from a parsing point of view, but not necessarily from a semantic point of view. That is, 1 2 3 is actually parsed as (1 (2 3)), but it doesn't mean that 1 is seen as a high-order function, or that applying an int to an int actually means anything.

Your example 3 about regexp I'm not sure. Are you referring to the existence of a default matrix akin to $_, to the fact that regexps don't need specific quoting characters in Perl, or to something else?

I'm afraid I wasn't totally clear. I was not asking about three representations of a matrix, but representations of three different concepts.

The first is indeed a matrix, and that appears to be within the scope of what XL can parse.

The second in a combinator library like the DSL for finacial contracts mentioned here a few weeks ago.

The third is just Perl's text matching facility. e.g.

/data(base|mart|store)?/

You were perfectly clear, but I was tired and misunderstood your question. No wonder I was confused as to how the hell you wanted to use a combinator library to build matrices :-)

I have trouble understanding the syntactic problem with the combinator library. And I think I disagree with your statement that a combinator library requires high-order functions (if that's what you meant). I could not find a precise definition for "combinator library", but in based on the examples I saw, most operators in Blitz++ would qualify (http://www.oonumerics.org/blitz/examples). The whole notation in your example paper can almost be used in C++, and can definitely be used in XL as well (except that you don't need the backquotes around 'and'). Maybe I'm confused and misunderstood what people call combinator library.

function And (C1, C2: contract) return contract written C1 and C2
function Give (C1 : contract) return contract
X, Y, Z : contract
X := Y and give Z

The Perl syntax for regexp is an excellent exemple. There is a syntactic difficulty, and a semantic one. The syntactic difficulty I punt on using something like:

regexp "data(base|mart|store)?"

It is possible to do it differently, but in my opinion at the expense of clarity for readers not familiar with the concept, or of ease of integration with non-regexp concepts. In particular, XL makes it a bit difficult to get rid of the quotes, and that's on purpose. Note that a similar approach is taken in Boost regexps (http://www.boost.org/libs/regex/index.htm).

The semantic difficulty I find more interesting. Perl for instance has this notion of default input. So you can write something like:

while (<STREAM>) {
    next unless /([[:xdigit:]]+)(s*)([[:alnum:]]+)/;
    my ($number, $name) = ($1, $3)
}

Pardon me if I made a mistake there, my Perl is a bit rusty. The two interesting things related to the regexp in the example are that 1/ it is used as a loop exit condition, which from a semantic point of view is taken as referring to a match with the STREAM, used as a default input (the STREAM is itself used as a loop control, and has a different effect...); and 2/ that it also sets $1, $2, $3 on a match because there are parentheses inside.

There are a number of XL semantics you may use to match this conciseness. In order to preserve some compatibility with other concepts (notably the possibility that this is one thread among many, so we don't want implicit globals), and using the redefinable 'for' loop, I'd suggest something like:

number, name : text
while not eof STREAM loop
    exit unless (STREAM match "([[:xdigit:]]+)(\s*)([[:alnum:]]+)" read (number,name))
    // do something with number, text

The above can be made to work without even resorting to meta-programming. For that case, there is no real need to use the 'regexp' prefix, because the [stream]match[text]read[tuple] tree structure is probably unique enough to not introduce conflicts. The words 'match' or 'read' might not be the best choices there... Anyway, the declaration of the notation above would be:

function RegexpMatch(Stream : istream; Pattern : text; Output : variable_tuple)
    return boolean
    written Stream match Pattern read Output

Meta-programming could improve performance by allowing the regexp to be constructed only once in the loop, things like that.

An alternative notation for "matching a pattern in a stream" could use redefinable for loops (see http://cvs.sourceforge.net/viewcvs.py/mozart-dev/mozart/xl/TESTS/semantics/for_loop.xl?view=markup). You might end up with something like:

for (number, name) in STREAM matching "/.../" loop
    // Do something with number and name

This is a more specialized concept. Whether is it frequent enough to justify a separate implementation is an open question.