-1

Reading Peter Van Roy's "Paradigms for Dummies", I am a bit stuck with the second footnote.

Van Roy presents a graph depicting paradigms with different combinations of attributes for state. Named and unnamed, deterministic and nondeterministic, concurrent and sequential. The footnote states that two combinations are not shown and that they may not be useful.

The missing combinations are

  • Unnamed, nondeterministic, sequential
  • Named, deterministic, concurrent

I've been looking online and not really finding much about this. I cannot convince myself that I understand either of these to be useless, and if so why. I do note that these two are exact opposites which piques my curiosity.

Is anyone able to explain the justification or refutation of either of these combinations?

Derek C.
  • 617
  • 5
  • 7

1 Answers1

3

This is a tough question (I don't have high confidence in my answer) so here goes:

Unnamed, Nondeterministic, Sequential

Let me start by flipping nondeterministic -> deterministic

An example of "unnamed, deterministic, sequential" is a pure functional language:

  • It has unnamed state because as you program in a pure functional language you can't create and manually mutate state (any state is inherently created by the runtime as it executes your code).
  • It's deterministic because the logical definitions are deterministic and there are no external conditions that can affect the outcome.
  • It is sequential because as you are programming in the paradigm, you can't express a concept of parallel execution (although the runtime would again be free to use multiple threads to evaluate your program).

So if we have a programming language that uses two of those tenants (unnamed and sequential) i.e. we don't have manually control of state and we can't imply that there are multiple threads of execution. Does nondeterministic gain us anything?

Let me come back to this point ...

Named, Deterministic, Concurrent

Again, let me flip deterministic -> nondeterministic

A lot of common languages use "Named, Nondeterministic, Concurrent".

Firstly let me qualify the Nondeterministic part of that statement, there are parts of our programs that we definitely want to be Deterministic for example, incrementing a counter from multiple threads. Hence we put locks in to ensure only one thread can touch the state at a time. However which of the multiple threads that are trying to aquire the lock succeeds first is Nondeterministic - as programmers we are aware that this will happen and that it is Nondeterministic, we just don't care which thread goes first. My interpretation of Van Roy is this is what he means when he says the state is Nondeterministic. Another example of this would be the execution order of multiple locking transactions in a database.

The Footnote:

Van Roy says:

Two of the eight possible combinations are not shown in the figure. We leave it to the reader to discover them and find out if they make any sense!

Reading between the lines, I think Van Roy is saying:

Given you are restricted to unnamed and sequential - there isn't any useful functionality you can add that results in Nondeterministic behavior.

And Given you are fully utilizing the benefits of Named and Concurrent there is no way to avoid some Nondeterministic behavior or to put it another way the Nondeterministic behavior is beneficial.

I think I will follow Van Roy's lead, and leave it to the reader to enumerate a counter example....

DavidT
  • 3,338
  • I mostly agree with this answer and I think it has helped me get a grasp on this. Flipping the one concept does help to show why we would want that version and highlights the potential downfalls of the un-flipped. Thank you. – Derek C. Dec 04 '23 at 17:29