Five "laws" of programming paradigms

Now that we are close to releasing Mozart 2 (a complete redesign of the Mozart system), I have been thinking about how best to summarize the lessons we learned about programming paradigms in CTM. Here are five "laws" that summarize these lessons:

  1. A well-designed program uses the right concepts, and the paradigm follows from the concepts that are used. [Paradigms are epiphenomena]
  2. A paradigm with more concepts than another is not better or worse, just different. [Paradigm paradox]
  3. Each problem has a best paradigm in which to program it; a paradigm with less concepts makes the program more complicated and a paradigm with more concepts makes reasoning more complicated. [Best paradigm principle]
  4. If a program is complicated for reasons unrelated to the problem being solved, then a new concept should be added to the paradigm. [Creative extension principle]
  5. A program's interface should depend only on its externally visible functionality, not on the paradigm used to implement it. [Model independence principle]

Here a "paradigm" is defined as a formal system that defines how computations are done and that leads to a set of techniques for programming and reasoning about programs. Some commonly used paradigms are called functional programming, object-oriented programming, and logic programming. The term "best paradigm" can have different meanings depending on the ultimate goal of the programming project; it usually refers to a paradigm that maximizes some combination of good properties such as clarity, provability, maintainability, efficiency, and extensibility. I am curious to see what the LtU community thinks of these laws and their formulation.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

This list reminds me of

This list reminds me of Greene's cognitive dimensions of language design: they make sense but hardly provide us with much guidance beyond head nodding. I guess more context would be nice, how can these laws inform language designers when they have difficult choices to make? It might be better to document them more like patterns with use cases and such.

Guidance

The list does actually provide some guidance. For example, the fifth law is in contradiction to a widely recognized principle of functional programming. According to this principle, if your function uses mutable state internally, then this should be visible in its type signature. The fifth law says the opposite: if the function uses mutable state in its implementation, then there is no reason that should be visible externally. According to the fifth law, a pure function and a function implemented with memoization (an internal stateful table of previous results, used to speed up future calls) can have identical interfaces. Personally, I am convinced that in this case the fifth law is correct.

Fifth law

According to this principle, if your function uses mutable state internally, then this should be visible in its type signature.

You should be careful to clarify here that you're talking about persistent mutable state. Mutable state used internally to a computation certainly needn't be part of the interface.

If you intend with your fifth law that hidden persistent mutable state is a good idea, then I'm sure you'll find plenty of disagreement, including from me. The example you give of caching, where the semantics are pure and the mutable state serves only as an implementation optimization falls under the heading "the exception that proves the rule". Your previous example of logging in a multi-module system was of a similar variety: state is introduced at an implementation layer in a way that doesn't affect existing higher level abstractions. That pattern is something I'm attempting to address in my language by exposing some of the representation selection mechanism, allowing some parts of the program to be written at a lower levels of abstraction.

I read #5 as saying that if

I read #5 as saying that if the mutable state is externally visible functionality then it is allowed to be part of the interface, whereas if it is an implementation detail then it should not be. It's hard to disagree with, and I don't think it's in contradiction with functional programming wisdom (e.g. the ST monad in Haskell for internal mutable state and unsafePerformIO for external but not observable mutable state).

It certainly helps to have a concrete situation to talk about (e.g. memoization), rather than an abstract law that different people will interpret differently. Most likely each of these laws has a number of example situations encountered in the implementation of Mozart 2 that underlie it, which were then summarized in one sentence. It would help to have a concrete situation for the four others, because we cannot unambiguously reverse engineer examples from the laws.

A Program's Interface

I read "a program's interface" as broadly including:

  1. support for reflection
  2. support for live coding or direct manipulation
  3. join points and cut points for composition in AOP
  4. ambient or contextual models that adapt to environment
  5. direct arguments to a function or procedure

Interfaces can be distinct from the program's visible functionality, or in excess of the program's requirements. They can depend heavily on program model, concepts, architecture - paradigm - rather than the problem, domain model, or any explicit code. In such cases, it isn't reasonable to claim we have [model independence].

I agree with PvR's point that we can use state internal to a function where it does not impact the external semantics. From a number of such examples, one might argue the converse of #5:

A program's interface should not depend on its internal, invisible functionality

I think people won't disagree with that. But you can't reach any model independence principle from there.

Right, that's how I read it

Right, that's how I read it too, except that in some cases you may want to consider some externally visible functionality not part of the interface. For example a logger inside a module is not part of its interface from the point of view of the user of the module, but is part of it from the point of view of the administrator of the system. That is, different things may be observable from different contexts.

You can only get a model independence principle insofar as the interface does not depend on the model.

Interface as a two-way street?

My understanding is that stateful logging in a module can be considered pure, to the extent that the users of the module are proven to never access the log. Ideally, such conditions on the "calling environment" should be part of the interface, in a dual way to conditions on the module itself. As one other example where this would be useful, consider some state-depending variation in returned data, due to optimization. This might be OK, provided that the calling environment only uses the data in computations which are invariant to any such variation.

Such a principle would be quite compatible with the general paradigm of typeful functional programming.

Well...

It's hard to disagree with, and I don't think it's in contradiction with functional programming wisdom

PVR seems to, if you see the comment I was replying to. I initially read it the way you did, but when PVR elaborated, I changed my mind. Also, you can find earlier threads where he has argued that hidden mutable state is required for modularity purposes. Also, I wouldn't lump the ST monad and unsafePerformIO together. The ST monad or similar is a great way to encapsulate state, but unsafePeformIO is a terrible hack!

Well, surely he doesn't

Well, surely he doesn't disagree with his own laws? I thought maybe PvR disagrees about what is functional programming wisdom, rather than what is good programming practice, since he says that functional programming wisdom is "if your function uses mutable state internally, then this should be visible in its type signature". But maybe the other threads show differently, I don't know. It depends on what you call modularity.

I meant explicitly not to lump the ST monad with unsafePerformIO, they are two different things with different purposes. ST is for implementing quicksort with mutable state internally, unsafePerformIO is for implementing things like memoization (though in a lazy language you have other options in this case: define the entire memo table lazily, it will get cached as things get evaluated).

The list does actually

The list does actually provide some guidance.

I guess for a post, I shouldn't expect too much, but you really need to steep these laws in context for them to be more meaningful. And by guidance, I mean more examples where we had multiple choices that look reasonable and by following the laws, what we choose results in the better conclusion then what we could have chosen.

Also, I would call them principles rather than laws. This gives you some wiggle room to not be universally right, just right most of the time.

I agree with Sean,

I agree with Sean, especially for the first three points. And while the last two points do provide some concrete guidance, I disagree with both of them.

If a program is complicated for reasons unrelated to the problem being solved, then a new concept should be added to the paradigm. [Creative extension principle]

After a paradigm is 'fielded', perhaps adding to it is the only option. But I've found that points of accidental complexity are often better addressed by subtraction or restructuring - evolution of the paradigm to clean up some problematic corner cases or support some more compositional reasoning.

A program's interface should depend only on its externally visible functionality, not on the paradigm used to implement it. [Model independence principle]

I am reminded of the fallacy of the "right tool". Tools go away when the job is done. Materials stick. An IDE is a tool. A language or paradigm is material.

Any program will have various 'non-functional' properties, such as our ability to extend it with scripts or plugins, compose it into mashups or larger applications, port it to a new context, maintain it. These properties are visible, but are not explicitly part of the program's interface, and are almost entirely independent of the specific problem being solved.

I suppose you could squeeze such non-functional properties under the heading of "externally visible functionality." But I think doing so would not clarify. It instead would undermine the point, since the externally visible functionality would depend almost as much on the paradigm as on the problem.

Each problem has a best paradigm in which to program it

I find this assertion, of your third point, extremely dubious.

First, how would you ever argue that a particular paradigm is 'best' for a particular problem? Even if we agree on the precise requirements, there may be many paradigms that seem of about equivalent effectiveness - i.e. such that we cannot agree on a total order for one being 'better' than the other. Second, context plays a big role. Who is solving the problem? Which libraries already exist to solve similar problems? Where is the solution to be integrated? There is a reason we must to solve the same problems again and again, because each time the context emphasizes different qualities.

And what good serves such a principle, but to close the minds of men?

Subtraction, restructuring, and evolution

But I've found that points of accidental complexity are often better addressed by subtraction or restructuring - evolution of the paradigm to clean up some problematic corner cases or support some more compositional reasoning.

And then, after all the restructuring of your program to remove accidental complexity, you discover that you have actually reinvented exceptions, or threads, or mutable state, or something completely different. Or maybe, your restructured program does not contain any new concepts, and the original paradigm was sufficient.

Restructure the paradigm,

Restructure the paradigm, not the program.

In many cases this might not result in any 'new' concepts. For example, one might unify two existing concepts that are often used together, but by tightly coupling them one can avoid some problematic use cases. Or similarly, we might constrain the use of an existing concept.

It is an error to argue that "no new concepts" means the original paradigm was sufficient. It may have been sufficiently powerful and expressive, but not sufficiently easy to reason about.

s/problem/solution/

For rule number three, I'd phrase it as "every SOLUTION has a best paradigm to implement it in." Almost all problems admit to multiple different, equally valid, solutions.

The problem with the way it's phrased is that it allows, even requires, reasoning like "Problem X has solution S which is best solved in paradigm P, therefor problem X is best solved in paradigm P." However, it'd be equally valid to say "Problem X has solution T which is best solved in pardigm Q, therefor problem X is best solved in paradigm Q" as well, if problem X admits to solutions S and T.

As a culture, we programmers are very inclined to confuse problems with solutions (and vice versa). This is one of the advantages of knowing multiple paradigms, is it requires one to know multiple solutions to the same problem.

Problems and Solutions

I agree that this is better, and it helps explain the issue I had with it.

Seriously

Are you actually serious about this?

Paradigm vs entity

Contrast rule 4: "If a program is complicated for reasons unrelated to the problem being solved, then a new concept should be added to the paradigm." with a (folklore? common sense?) rule: "If a program is complicated, and a new entity (function, object, class) would make it simpler, then you should introduce that entity."

There's a spectrum in many applications - one end of the spectrum has to do with the technology (e.g. "we're using operating system X, and these are the parts that deal with its quirks") and other parts have to with the domain (e.g. this entity is a "deduction" in tax-preparation software). I think these ends are called "solution domain" and "problem domain".

The additional condition "for reasons unrelated to the problem being solved" simply focuses the domain of applicability of Rule 4 on the part of that spectrum far from the problem domain. That is, paradigms are solution domain entities. But the more general rule is also true, isn't it?

Tension between #2 and #3

There is an interesting interplay between the second and third laws. The second law reads as a statement that the number of concepts is a not a measure of quality (e.g. that a simpler paradigm is not better). But the third law reads as a statement that a paradigm with fewer concepts is better.

Resolving this tension seems to require some implied quantifiers; in one context reasoning over all possible problems, in the other context reasoning over all possible paradigms applied to a single problem. This is reminiscent of a No Free Lunch theorem, or possibly leads to an argument similar to Arrow's Theorem.

the third law reads as a

the third law reads as a statement that a paradigm with fewer concepts is better

How so? I assume you refer to the sentence: "a paradigm with less concepts makes the program more complicated and a paradigm with more concepts makes reasoning more complicated". I understood this as saying "somewhere in between - i.e. the alleged 'best' paradigm - there's a sweet spot (for the problem)".

Of course, it might be a local minima or maxima, rather than a global one. Or it might not even be that much: adding or removing concepts is a naive search pattern, analogous to searching a line on a surface. We might walk right by a hill or valley without noticing it. Language design is hard. There is much more to a paradigm than a set of concepts: how they are layered, composed, and baked together makes a huge difference.

Putting aside the utter wrongness of assertion #3, I do not believe there was any implicit judgement that 'fewer concepts is better'.

in one context reasoning over all possible problems, in the other context reasoning over all possible paradigms applied to a single problem

Or we could reject both principles and reason about the integration of solutions to many problems. I believe focus on individual problems, or even all possible problems (considered individually), results in languages that encourage monolithic applications and code that is painful to reuse.

whoops

I understood this as saying "somewhere in between - i.e. the alleged 'best' paradigm - there's a sweet spot (for the problem)".

Yes I misread the list - that is the problem with reading/posting in the middle of the night. Now that I've reread the list I would just disagree with #3 completely: fewer concepts can make the program more complicated. Or then again it could also make the program simpler as the issue is how well the concepts map onto parts of the program / problem, not how many there are. I think this roughly the same as your final point.

Got 2.5 Hours?

I find the word "paradigm" quite interesting in this connection. Since I usually think of computer science and software as ontology I decided to search the expression "ontological paradigm". Here are two interesting links What is your paradigm? Also this, Common Paradigms. Computer science needs this kind of discussion but I am not sure if we are ready for this.

Constructivism as a Computer Scientist

You might like Constructivism in Computer Science Education. His main point is that CS has a unique form of ontology. It's an interesting read. There are many versions not behind paywalls but Google's URL obfustication is starting to get quite annoying.

Here's one

Dummy

This goes a long way towards explaining PVR's concept of paradigm. Also the concept of named state makes the whole idea work for me. Is "named state" a new idea, or am I missing something?

Named state isn't a new

Named state isn't a new idea; it broadly includes imperative variables, addressed memory, tables or records in a database, files in the filesystem, URIs, etc.. If it has a relatively stable name over time, and you can use it to count events or accumulate observations over time, it is usable as named state.

Paradigmless

In the diagram Java is an example of object orientation. It could better be chracterized as a combination of OO paradigm and null paradigm. The latter refers to basic types programming. The big subject of basic types is little discussed. Basic types widely blur paradigmful languages and discussion of language features.

What is an overall picture of basic types in languages? ML,...,OCAML has none?

Edits:
-Commenting wrong topic, sorry, but anyway
-Basic types only blur languages with OO or all languages?