Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

I know the concept of orthogonality, but from a programming language point of view, is there a way to verify/prove it?

For instance in C#, one can use public or static for a method signature. You can use either or both and they wouldn't interfere with each other, so they are orthogonal to each other, right?

My question is, how do I go about the rest of features, particularly features that are not related to each other?

Do all the features have to coexist/stack together?

Is there a programming language that is 100% orthogonal?

share|improve this question

migrated from Jan 3 '12 at 22:32

This question came from our site for professional and enthusiast programmers.

Start from the (near) beginning: assembly language? – Matthew Flynn Jan 3 '12 at 22:50
To actually prove something, you need a formal definition for it. And if your definition is going to be something as big as the C# spec, proving anything will take a lot of work. – svick Jan 3 '12 at 22:59

6 Answers 6

up vote 4 down vote accepted

I am not sure that orthogonality can serve as useful or valid metric in case of general purpose high-order languages like C#, because it requires the distinction of "operations" and "operands" -- the small parts of the language that are not easily distinguishable in such high-order languages like C#.

My understanding of orthogonality is based upon the Assembler language where the orthogonality of the instruction set of a certain particular CPU or microcontroller indicated whether there are some constrains on operations performed by this CPU or controller depending upon the data types. In early times this was important because not every CPU supported operations on fractional numbers or numbers of different length etc.

In this respect I would rather check for the orthogonality of the Common Intermediate Language using Stack Machine language as the target for C# compiler, not C# itself.

If you are really interested in orthogonality of C# and I am not mistaken here (for whatevery purpose) I would suggest looking towards some genetic programming algorithms. You can use those to generate different programs from the given set of keywords (even the meaningless ones) and you can just automatically check if those are compilable. This would help you to automatically see what elements of the language can be combined together and derive some aspects of your orthogonality metric.

share|improve this answer

The term "orthogonality" is a layman's term for a precise mathematical notion: the language terms form an initial algebra (look it up in Wikipedia).

It basically means "there is a 1-1 correspondence between syntax and meaning". This means: there is exactly one way to express things, and, if you can put some expression in a particular place, then you can put any other expression there too.

Another way to think about "orthogonal" is that the syntax obeys the substitution principle. For example if you have a statement with a slot for an expression, then any expression can be put there and the result is still a syntactically valid program. Furthermore, if you replace

I want to emphasise that "meaning" does not imply computational result. Clearly, 1 + 2 and 2 + 1 both equal 3. However the terms are distinct, and imply a different calculation even if it has the same result. The meaning is different, just as two sort algorithms are different.

You may have heard of "abstract syntax tree" (AST). The word "abstract" here means precisely "orthogonal". Technically most AST's are not in fact abstract!

Perhaps you have heard of the "C" programming language? C type notation is not abstract. Consider:

int f(int);

So here is a function declaration returning type int. The type of a pointer to this function is given by:

int (*)(int)

Note, you cannot write the type of the function! C type notation sucks bigtime! It isn't abstract. It isn't orthogonal. Now, suppose we want to make a function which accepts the above type instead of int:

int (*) ( int (*)(int) )

All ok .. but .. what if we want to return it instead:

int (*)(int) (*) (int)

Woops! Invalid. Lets add parens:

(int (*)(int)) (*) (int)

Woops! That doesn't work either. We have to do this (it's the only way!):

typedef int (intintfunc*) (int);
intintfunc (*)(int)

Now its OK, but having to use a typedef here is bad. C sucks. It isn't abstract. It isn't orthogonal. Here's how you do this in ML, which is:

 int -> (int -> int)

We condemn C at the syntax level.

Ok, now lets flog C++. We can fix the stupidity above with templates and get an ML like notation (more or less):

fun<int, int>
fun< fun<int,int>, int>

but the actual type system is fundamentally flawed by references: if T is a type, then is T& a type? The answer is waffly: at the syntax level, if you have a type U = T&, then U& is allowed but it just means T&: a reference to a reference is the original reference. This sucks! It breaks the uniqueness requirement semantically. Worse: T& & is not allowed syntactically: this breaks the substitution principle. So C++ references break orthogonality in two different ways, depending on the binding time (parsing or type analysis). If you want to understand how to do this right .. there's no problem with pointers!

Almost no real languages are orthogonal. Even Scheme, which pretends great clarity of expression, isn't. However many good languages can be judged to have a "reasonably close to orthogonal feature basis" and that is a good recommendation for a language, applied both to the syntax and to the underlying semantics.

share|improve this answer
So you think ML is more orthogonal than others? What about Lisp and Haskell? – Joan Venge Jan 5 '12 at 16:36
@joan: well, lisp doesn't have any features so it satisfies the requirement in vaccuuo :) – Yttrill Jan 30 '12 at 16:29
@joan: I'm not a Haskell programmer so it's a bit hard to say, but the presence in Haskell of "extremely high level functionality" is indicative of strong orthogonality: you simply can't have a coherent implementation of Monads or Arrows unless the rest of the language has substantial "orthogonality" – Yttrill Jan 30 '12 at 16:31
What you you think about Pascal. Seems loads better than C. – supercat Mar 17 at 21:35

Proving orthogonality is proving a negative. It means you don't have any constructs that are not orthogonal, which means it's a lot easier to prove something isn't orthogonal than is.

In practice, most people talk about orthogonality of programming languages in terms of degrees rather than either being completely orthogonal or not. When knowledge from doing something in one context translates to another context and "does what you expect," that language is said to be more orthogonal. LISP is regarded as highly orthogonal because everything is a list, but I don't think it can be said it is 100% orthogonal because of some redundancies that make it easier to use. C++ is regarded as not very orthogonal because there are a lot of little "gotchas" where it doesn't quite work the way you think it would.

share|improve this answer

Warning, I don't know anything about this topic.

A quick glance at Wikipedia seems to indicate that Orthogonality is mostly directed at design patterns and systems design. In terms of programming languages, the entry indicates that instruction sets are orthogonal if there is one and only one instruction for each possible action, or rather, no instruction overlaps another.

For C#, I'd imagine that it is orthogonal, in that most syntax tricks (foreach comes to mind) are simply front-ends to specially formed versions of the base construct (foreach becomes for loops). Overall, the language only truly supports doing things in a single way, even though syntactic sugar provides additional ways to do them. And lastly, it all compiles down to MSIL (or whatever it's called these days) and MSIL is likely orthogonal.

If you make the caveat that syntactical sugar stuff is essentially a "wrapper" around doing it the "hard way" you can analyze the various features of the language, omitting sugar, and see if there are any constructs that truly overlap. If not, I'd imagine you could declare the language orthogonal.

My two cents.

share|improve this answer
I think if both for and foreach are features of a language while one is a syntactic sugar of the other(where the effects of foreach could be achieved using for), the language loses its orthogonality there. – vpit3833 Jan 3 '12 at 22:45
Can't do...while can be used to provide the same effect as for? I've never heard of either as being considered syntactic sugar. – Matthew Flynn Jan 3 '12 at 22:48
@MatthewFlynn: Bah! They're BOTH syntactic sugar, you could just replace your iteration with a recursive function! ;) – FrustratedWithFormsDesigner Jan 3 '12 at 22:56
@FrustratedWithFormsDesigner: Isn't that just syntactic sugar for GOTO's? – Ivan Jan 3 '12 at 22:58
@MatthewFlynn do while guarantees a single loop execution and checks the condition after the fact. for checks the condition first, and does not guarantee a single execution. – Digitlworld Jan 3 '12 at 23:09

My question is, how do I go about the rest of features, particularly features that are not related to each other?

You continue doing what you're doing, enumerating all the combinations that work or are forbidden.

That's all. It's quite painful to do.

Do all the features have to coexist/stack together?

If all features can partitioned into disjoint subsets that don't interfere with each other, then sure, all would be sensible.

All data structures work with all primitive types. All expression operators work with all types. Those are common definitions of orthogonality. But you may want more (or less)

Sometimes, however, there are special cases because of operating systems or legacy libraries that aren't orthogonal.

Also, some types aren't really very conformable at all. For example Python allows you to compare two dictionary objects for "ordering". But there's almost no sensible definition of "ordering" among dictionaries. Python defines one, but it's pretty debatable. Does that special case make dictionaries fail an orthogonality test?

How orthogonal is "orthogonal enough"? What do you need to see to be happy with the degree of orthogonality in your language.

share|improve this answer

The list of unorthogonal features is indeed long in most programming languages, e.g.

  • anonyous classes conflict with java reflection
  • generic and type erasure conflict with java reflection
  • arrays are somewhat different to other objects, because of their special type, even though they are objects.
  • static vs. instance methods are not the same, e.g. you can't override a static method
  • nested class are an after-thought
  • impact of dynamic vs. static typing on the message dispatch strategy (see e.g. this edge case in C#)
  • etc.

Those a just a few that comes to my mind, but there are many others, and also in other languages.

It's hard to ensure that there are not subtle interference between language features. As C.A.R. Hoare indicates in his paper "Hints on Programming Language Design":

Part of language design consists of innovation. This activity leads to new language features in isolation. The most difficult part of language design lies in integration: selecting a limited set of language features and polishing them until the result is a consistent simple framework that has no more rough edges.

Probably, a good move to increase orthogonality is to unify concepts (that goes in the direction of @karl-bielfeld answer). If everything is, say a list or an object, chances are that there will be less conflicts. Or instead of having nested class an after thought, make it a core features.

Most programming languages papers prove certain properties of the language (e.g. type soundness) on a subset (a "core") of the language that is formalized. Here we should do the opposite, prove that all features compose safely. Also, that means one should define what it means to "compose". Does it mean to "run"? (In this case, the link above about the edge case with dynamic and static typing is safe). Does it mean to be "safe"? Does it mean to be predictable from a developer point of view?

All that is very interesting--but also very challenging.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.