10

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?

Improve this question
2
  • Start from the (near) beginning: assembly language?
    – Matthew Flynn
    Jan 3, 2012 at 22:50
  • 1
    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, 2012 at 22:59

6 Answers 6

Reset to default
4

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.

Improve this answer
6

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.

Improve this answer
5
  • So you think ML is more orthogonal than others? What about Lisp and Haskell?
    – Joan Venge
    Jan 5, 2012 at 16:36
  • 1
    @joan: well, lisp doesn't have any features so it satisfies the requirement in vaccuuo :)
    – Yttrill
    Jan 30, 2012 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, 2012 at 16:31
  • What you you think about Pascal. Seems loads better than C.
    – supercat
    Mar 17, 2015 at 21:35
  • I know my comment is almost 4 years late but I just came across it. This answer is wrong on just about everything. Even the whole "it's the only way!" part is simply wrong. You can easily express that without a typedef example int (*intintfunc())(int) { ... } - intintfunc is a function that takes no arguments and returns a pointer to a function that takes 1 int argument and returns an int value.
    – Wiz
    Jul 4, 2016 at 4:10
4

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.

Improve this answer
3

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.

Improve this answer
7
  • 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, 2012 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, 2012 at 22:48
  • 1
    @MatthewFlynn: Bah! They're BOTH syntactic sugar, you could just replace your iteration with a recursive function! ;)
    – FrustratedWithFormsDesigner
    Jan 3, 2012 at 22:56
  • 2
    @FrustratedWithFormsDesigner: Isn't that just syntactic sugar for GOTO's?
    – Ivan
    Jan 3, 2012 at 22:58
  • 2
    @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, 2012 at 23:09
2

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.

Improve this answer
2

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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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