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 us