Comment by rafaelferreira | Hacker News Reader

Comment by rafaelferreira | Hacker News Reader

Parent Full thread

Your distinction appeals to physicality, to a "real world". The author comes from a purer mathematical perspective, where it does not matter whether the code runs on silicon, is emulated by another machine, or is evaluated by humans on a blackboard.

Parallelism is purely an efficiency issue; the result of a computation does not change if run sequentially or in parallel. In other words, it only affects the cost model, not the semantics.

Concurrency means adopting some non-determinism in the semantics, either for necessity (e.g. in concurrent servers) or as a program structuring mechanism. In your example, if we are concerned with the semantics of the simulator, then there is no parallelism OTOH, if we are concerned with the semantics of the simulated code, then it's likely that we would use concurrency in it's definition (even if we "really know" that there is no underlying physical nondeterminism).

Parallelism is just an optimization; and concurrency does not imply non-determinism. Concurrency means you've got more than one thing in flight at a time. Having more than one task in flight, whether you switch using coroutines, or asynchronous completions, or an OS scheduler running on a timer interrupt, or cycle counting in a virtual machine, or via higher level language constructs like futures and promises, or reactive programming, is concurrency; but not all of these things are non-deterministic.

Peter Van Roy's book defines it as "an execution is called nondeterministic if there is an execution state in which there is a choice of what to do next". I believe the only thing you mention that does not conform to this definition is co-routining, but I wouldn't categorise it as concurrency either (nor does the book).

There's a nice answer on FRP at http://stackoverflow.com/questions/1028250/what-is-functiona... - if choices in execution are not revealed to the program, you can still have concurrency without non-determinism. But again, one needs to call in to question what tasks are making progress concurrently, because depending on the level of abstraction you're looking at, you can say that there is concurrency or there isn't. In other words, you might have parallelism at a low level of abstraction, which is a physical optimization of concurrency, and at that low level it might even be non-deterministic, but that non-determinism may not be exposed at a higher level.

Take a spreadsheet implementation as an example. There may be multiple events coming in, and numbers in the sheet updating as the expressions are recalculated. It might even be a multi-user spreadsheet; so it seems there is concurrency (for some level of abstraction). But is there non-determinism?

Reply on news.ycombinator.com