Error handling

[sighoya]

@shelby3
@keean

How does your future language handle errors?
What do you prefer:

1.) Error handling over return types ala Rust/Haskell/SML/Ocaml
2.) Error handling over an Exception System ala C++/Java/C#/Python/Swift/Haskell/SML/Ocaml

[keean]

At the moment I am favouring error handling by exceptions using algebraic effects.

For me the argument is about keeping code clean to read.

[shelby3]

try-catch-finally which can be emulated with a Go transpiler.

At the moment I am favouring error handling by exceptions using algebraic effects.

I’ve soured on (even free) monads for modeling effects. Lots of tsuris of trying to arrange all ducks into a serial line.

For me the argument is about keeping code clean to read.

Why are they any cleaner in code than try-catch-finally?

Why make it abstruse for programmers who know try-catch-finally?

[sighoya]

I found exceptions to be superior to error return handling. Of course, one can create specific error return types instead of error return values but two main problems still exists:

1.) performance is decreased because of double bookkeeping errors, the one in the function itself which is also by exceptions, but the other outside the called function at the call site and this even in cases where no error happens

2.) You pollute your intended return types and more importantly you destroy the modern builder pattern aka left pipe pattern to write function applications more sequentially. And return tuples of errors and return type are not really a help.

Of course one should not overuse exceptions like in java but a balanced use of exceptions, optionals and eithers is all you need most of the time.

So I don't understand the critics from the go site

[shelby3]

@sighoya wrote:

I found exceptions to be superior to error return handling.

It’s definitely advantageous to not have to clutter the algorithm with checking the return value of every function call for errors. It’s more readable to group function calls by the commonality of the processing that will be required for any exceptions they throw, and handle that commonality in common catch and/or finally code block.

Exceptions are slower than checking every return value in the cases when there’s an error, but they’re faster in cases where there’s no an error. So for infrequent errors then exceptions are more performant.

The performance of throwing an exception can be quite high if there’s no stack cleanup required. For example if allocation of all objects that have a destructor are tracing GC, so just need to rewind the stack pointer (SP). Then just need walk backwards the list of stack activation frames which have an active try-catch-finally block. However, if there can be destructible objects stored directly on the stack or there are reference counting (RC) references stored on the stack which require decrementing refcounts on destruction of the stack activation frame, then the performance cost of rewinding the stack can be much higher. I elaborated on possible designs to avert these performance issues.

1.) performance is decreased because of double bookkeeping errors, the one in the function itself which is also by exceptions, but the other outside the called function at the call site and this even in cases where no error happens

I don’t understand what you mean about types versus values. In fact, I find that sentence very difficult to parse. What does “the one in the function itself which is also by exceptions” mean?

2.) You pollute your intended return types and more importantly you destroy the modern builder pattern aka left pipe pattern to write function applications more sequentially. And return tuples of errors and return type are not really a help.

I don’t know what this means, “modern builder pattern aka left pipe pattern to write function applications more sequentially”?

Are you referring to monads and applicatives which can seamlessly for example lift functions which accept types T to functions which accept Option[T]?

Or are you referring to the criticism that in a strongly typed PL, errors as return values have the same problem as checked exceptions in that they can be incongruent with interfaces and callbacks. A possible workaround would be if interface or callback signature would have a generic type for the possible errors that can be generated by the function that implements the interface or is supplied as the callback. Yet that would then be the analogous as punting from checked exception into unchecked exceptions because the type of the returned errors wouldn’t be enforced (by the compiler) on callers of the interface or callback.

Yet in many contexts we will know the type of the errors in the local context where the interface or callback is being deployed, so that criticism doesn’t also apply. In the cases of polymorphic recursion where it does apply (i.e. the callback requires additional typeclass bounds not supplied by caller due to its type for the callback), then typeclasses will also be incongruent.

For callbacks the alternatives are to specify on the accepted type for the callback the only checked exceptions that are allowed. And/or throw unchecked exceptions.

Of course one should not overuse exceptions like in java but a balanced use of exceptions, optionals and eithers is all you need most of the time.

A blog by Andrei Alexandrescu (one of the authors of the D language) which was linked from the bottom of one of the blogs which I cited, points out that we shouldn’t not use exceptions when their poor performance could be significant:

^{The exceptional path is slow (00:10:23). Facebook was using exceptions to signal parsing errors, which turned out to be too slow when dealing with loosely formatted input. Facebook found that using exceptions in this way increased the cost of parsing a file by 50x (00:10:42). No real surprise here, this is also a common pattern in the Java world and clearly the wrong way to do it. Exceptions are for the exceptional.}

---

Should exceptions be checked?

• checked exceptions are annoying boilerplate when the caller knows they can’t occur such as for CheckedInvalidRowNumberException.

  A possible solution is to have a suppress … exception declaration that the caller can make (perhaps far off to the right side so not cluttering the code) to assert the exception never occurs and so the system will halt if it occurs and report the broken assertion.

• exceptions that can’t be handled at the low-level caller must be explicitly bubbled up with annoying boilerplate. It can be argued that in some circumstances the low-level caller should catch the exception and merge it into an exception which adds more detail to what has failed for the each caller turtles up the call hierarchy, but in most cases the type of the exception is rather irrelevant and the higher-level logic will just undertake some generalized recovery.

  A possible solution is to have a bubble … exception declaration that the caller can make (perhaps far off to the right side so not cluttering the code) to indicate there’s nothing the caller can do about the exception. A bubble all and bubble all except … could be helpful so do not have to list every possible exception when the caller can do no recovery for any of them, which is important because of the combinatorial explosion of exceptions in a call hierarchy. Yet there’s still the problem of needing to annotate the function declaration site with all the throws for all those bubbled, unless we allow the throws to be inferred by the compiler so these are never explicitly annotated (which is necessary as aforementioned with interfaces or callbacks where the list of throws is variable until instantiated) which also reduces the need for the programmer to turn off checked exceptions with something like throws Exception and catch (Exception e) {}. I would like to throw exceptions to include some documentation, so that functions don’t have to separately document what each exception means. IDEs can be then make this documentation available in context. The bubble all should probably be some symbol to make it even more terse, because it’s argued that rarely will lower-level callers want to handle them.

  However given higher-level logic will just undertake some generalized recovery, then it can catch all exceptions and thus no need to check for specific exceptions. Yet this is what bubble all accomplishes. It still forces each caller in the turtles call hierarchy to specifically declare there’s no recovery they can do for an exception.

• It’s argued that some exceptions (i.e. the non-exogenous exceptions) need to be unchecked because they are faults which the program should not try to recover from. In the case, even the higher-level logic should notify the user and/or a log file that a general recovery was attempted for a fault that should not occur.

• There’s a problem of lack of specificity when the same type of checked exception is throw by different functions turtles down the call hierarchy from the caller, because the caller may want to handle one but bubble the other.

  The compiler could help out here by detecting duplicates and prefixing them with the function name that throws them (for anonymous function then use the hash of the function body?).

It seems to me that checked exceptions done correctly as per my proposals above are better for large-scale development than unchecked exceptions. The key seems to be minimizing the noise they create.

Thoughts?

[keean]

@shelby3 I think.we should think in terms of transactions with concurrent software. Transactions either complete successfully or roll-back (with an exception)

Exceptions can be implemented as an additional return value by writing code in the Error Monad. So there is no difference in speed between exceptions and error return values.

[sighoya]

@shelby3 wrote:

I don’t understand what you mean about types versus values. In fact, I find that sentence very difficult to parse. What does “the one in the function itself which is also by exceptions” mean?

The "one"/"other" means a check. You check at first for a condition to throw or return an error value. But for error return values you have to check for errors even in cases where no error has happened because there is no signaling mechanism for error values.

Sorry for the confusion of values vs types. I mean numbers which encode an error versus objects of some error type.

I don’t know what this means, “modern builder pattern aka left pipe pattern to write function applications more sequentially”?

I work a lot with c++ at work and they handle all errors by values of an error enum which are returned in each function requiring to pass the "normally" returned object by reference instead to return it which looks like this:

namespace::error function(OutPut& o) {...}

The drama with this is that you can't chain such expressions. Imagine you update some object with setters you could chain all those setters in one line:
o.set(a).set(b).set(c)
by returning the reference to itself (which is here o) which is called the "builder pattern" or otherwise known as the left pipe instead of the right pipe ($ in Haskell) but this is not possible because you return an error value.

Of course, one can argue to take the reference of the error value as input instead but this is in some kind awkward and I have never seen someone before who has done this.

I find checked exceptions better than unchecked exceptions, too.
Some Notes:

A possible solution is to have a suppress … exception declaration that the caller can make

I thought the same about it. Each function could throw except if it is treated not to do so for instance by the tag nothrow.

bubble all and bubble all except …

Or you solve this by subtyping with Error as union type or by composition with the enum/data type for all errors. Then you can check afterwards the specific exception you want by pattern matching over the union

unless we allow the throws to be inferred by the compiler so these are never explicitly annotated

Sounds like exception deduction :). This can become quite cumbersome if the compiler checks down all exceptions in the call hierarchy, which becomes especially problematic if functions are already compiled, sure you can put a list of possible exceptions into your program binary.
In my eyes, the user generally should annotate his functions with the exceptions important for him. And exceptions which are not important could be together mentioned by annotating the general supertype Exception.
The compiler should only look for exceptions at function signatures which are directly called in the current scope. This would be more lightweight.

(which is necessary as aforementioned with interfaces or callbacks where the list of throws is variable until instantiated)

Do you mean the number of exceptions is unbounded? Otherwise the worst case could be assumed.

Exceptions can be implemented as an additional return value by writing code in the Error Monad

Could you elaborate a bit more?
Afaics, additional return values incur a cost anyways even in non error cases.

[sighoya]

@keean, if you don't like try-catch-finally you could look onto the dlang solution with scopes. They could however not replace try-catch-finally in every case, at least in my mind.

[keean]

@sighoya My point is that the language syntax is independent of the implementation. Using the Error monad the source language syntax looks like 'throw/catch' but we translate this into normal functions with an error return value in the intermediate language in the compiler.

[sighoya]

@keean
I've understood you in this respect but it does however incur costs. Maybe you need this because of go :)

[keean]

@sighoya you mean it incurs costs on the success path (checking for the error condition), whereas exceptions implemented by stack-unwinding do not? This is true, but due to branch prediction and speculative execution, it is probably zero measurable cost on a modern CPU. You also need proper exceptions to deal with runtime problems like Out-Of-Memory, Division-By-Zero etc.

[shelby3]

@keean wrote:

This is true, but due to branch prediction and speculative execution, it is probably zero measurable cost on a modern CPU.

Have you not read my recent post that argues that speculative pipelines are going away and besides they are not cost-free. They waste CPU power.

You also need proper exceptions to deal with runtime problems like Out-Of-Memory, Division-By-Zero etc.

What is the distinction between “proper” exceptions and try-catch-finally-throw? Why can’t the latter handle those exceptions?

Using the Error monad the source language syntax looks like throw/catch but we translate this into normal functions with an error return value in the intermediate language in the compiler.

What is the advantage of that?

I think.we should think in terms of transactions with concurrent software. Transactions either complete successfully or roll-back (with an exception)

What does “transaction” mean in this context? I think of transactions as blocks of logic that must complete atomically and this leads to interleaving conflicts with other such transactions. Transactions must wait in queue for each other and this leads to livelocks and deadlocks.

[keean]

@shelby3

Have you not read my recent post that argues that speculative pipelines are going away and besides they are not cost-free. They waste CPU power.

Respectfully, I disagree. Unless they can recover the performance another way, speculative execution is not going anywhere on general purpose CPUs. They will fix the security without abandoning the concept. the gains are just too big. The Pentium was the first Intel speculative out-of-order processor, and the whole architecture relies on the RISC core being fed micro-instructions from the re-order-buffer. To abandon this architecture would mean going back to a 486 era design and re-engineering from there. Its just too expensive and we would lose too much from it. The next gen Intel chips already have fixes for Spectre and Meltdown without losing SOOO, and AMD have SOOO and may not be vulnerable.

What is the distinction between “proper” exceptions and try-catch-finally-throw? Why can’t the latter handle those exceptions?

The syntax is not the exception mechanism. We are discussing the way the compiler implements those exceptions in the generated code. It can generate extra return values and use the error monad, or it can use stack unwinding and jumps. CPU hardware exceptions will always require the unwind and jump approach as we cannot continue after a division by zero, or out of memory, for example.

What is the advantage of that?

Lower cost if there is a failure.

What does “transaction” mean in this context? I think of transactions as blocks of logic that must complete atomically and this leads to interleaving conflicts with other such transactions. Transactions must wait in queue for each other and this leads to livelocks and deadlocks.

Exactly, we can thing of a program as a state-machine. It has a state and a set of transitions. We want each transition to either complete or be as if it never happened. When you have partially completed transitions, that is one way software can go wrong. Basically we are saying that software should never be left in a partially complete state, it should either look as if the action never happened, or it has completed. In terms of the blockchain, I have either paid you a bitcoin, or I have not, any partial state would be a serious error.

[shelby3]

@keean wrote:

Unless they can recover the performance another way, speculative execution is not going anywhere on general purpose CPUs.

We can. That is one of the main points of the ACM article that I linked to. Have you read it?

And we will also stop wasting so much heat and battery power on heat.

And we will have more secure computers.

And faster, more scalable software.

And we need to design our PLs for this new reality.

And goodbye C.

I hope you take the time to read my post, Eric Raymond’s post, and the original ACM article.

They will fix the security without abandoning the concept.

They can’t.

The next gen Intel chips already have fixes for Spectre and Meltdown without losing SOOO

There are unbounded number of such leaks hiding like an iceberg because of the fundamental anti-pattern. All they can do is play Whac-A-Mole with the chaos of it.

To abandon this architecture would mean going back to a 486 era design and re-engineering from there. Its just too expensive and we would lose too much from it.

There have already been chips for the new paradigm. I suggest you read the ACM article. The major cost is the inertia in software and broken PLs such as C. Also we already have very performant GPUs, which is basically what we need.

Respectfully, I disagree.

Respectfully, I do not think you have looked at this from the correct perspective.

You’re wrong on this one. I promise you.

The upcoming rate of change in the world is going to shock you. The dam is about to burst in so many ways to disintermediate all this wrongly designed shit in the world, including 10 years of waste on shit PLs like JavaScript, 20 years of waste on C after Moore’s Law stopped scaling serially, the entire nation-state and debt paradigm is going bye-bye, the entire nation-state fiat monetary system is being disintermediated by decentralization as we speak, etc..

https://steemit.com/cryptocurrency/@anonymint/bitcoin-rises-because-land-is-becoming-worthless

https://steemit.com/money/@anonymint/countries-vulnerable-to-economic-devastation-soon

https://steemit.com/programming/@anonymint/c-is-not-a-low-level-programming-language

https://steemit.com/tax/@anonymint/taxes-destroy-all-of-us-rich-or-poor

[keean]

@shelby3

We can. That is one of the main points of the ACM article that I linked to. Have you read it?

Yes, and I disagree with it. Only certain operations are vectorisable, and we have had vector architectures since the CRAY. They have all died out in favour of parallel nodes running Intel x86 chips. Parallel architectures like GPUs are great at certain specific tasks, but are not great at general purpose computing. There is no 'new architecture', we either solve the problems, or go back to 486 (at a higher clockspeed) performance.

Intel's next generation includes fixes for these attacks. Expect to see more fixes, I really don't think the x86 juggernaught can be stopped. You have to sell huge quantities of these CPUs to afford the fabrication plants to make them. Intel invests a lot of its CPU revenue into building these billion dollar facilities, and it keeps itself ahead in the fab-technology business. In this way Intel's chips are nearly a whole generation ahead of the rest of the market. People buy CPUs on price/performance, so Intel are already at an advantage. Add to this that no other architecture has been able to come close to speculative-out-of-order (not even VLIW that was behind Intels Itanium and ment to be the next generation, only to be out-performed by AMD's 64 bit x86 variant, that forced Intel to release a 64bit x86 or risk being left behind).

https://threatpost.com/intel-details-cpu-virtual-fences-fix-as-safeguard-against-spectre-meltdown-flaws/130501/

[shelby3]

@keean wrote:

What is the distinction between “proper” exceptions and try-catch-finally-throw? Why can’t the latter handle those exceptions?

The syntax is not the exception mechanism. We are discussing the way the compiler implements those exceptions in the generated code. It can generate extra return values and use the error monad, or it can use stack unwinding and jumps.

Why do you presume that I’m writing about syntax and not about the way try-catch-finally-throw are typically implemented. Obviously taken in context of all my writings in this thread, I am referring to the difference between stack unwinding or checking return values.

CPU hardware exceptions will always require the unwind and jump approach as we cannot continue after a division by zero, or out of memory, for example.

Exactly. So that is why I asked you why you promote the other approach which has worse performance and can’t handle all genres of exceptions.

What is the advantage of that?

Lower cost if there is a failure.

How so?

We want each transition to either complete or be as if it never happened.

It is analogous trying to turn the Titanic and always get all your ducks in a line. Transactions don’t work well in the real world. They have insidious livelocks and deadlocks lurking.

It’s analogous to forcing purity everywhere and forcing all side-effects into monads. Becomes a clusterfuck of monadic transformers trying to get all ducks into a line.

Transactions will break modularity and functional composition. You have an outer layer that demands a transaction but then inner layers want a conflicting transaction.

Software will never be this perfectly ordered system that you wish for. The Second Law of Thermodynamics will never allow it. Entropy tends to maximum. Embrace the disorder. Allow the programmer the flexibility to manage the chaos as best as he/she can.

Algorithms that don’t require transactions are more robust. Attack the problem at the correct semantic level. Transactions are a fungible, low-level paradigm thus lack the semantic capability to deal properly with the issues.

[keean]

@shelby3 How so?

exceptions have a huge cost on failure, it can take 100s of clock cycles to unwind the stack, just jumping to an exception vector in hardware takes 100+ clock cycles, and it causes the instruction pipeline to stall.

Error returns have equal (low) cost on both success or failure.

Transactions will break modularity and functional composition. You have an outer layer that demands a transaction but then inner layers want a conflicting transaction.

Even simple web applications need transactional safety. What happens if I press the next page button, but before that operation completes, I press the previous page button. The async callbacks for both promise chains now interleave leaving the state in an undefined position, and probably crashing the application.

If you are going to have a reasonably robust UI you need it to be transactional, you also need network packet handling to be transactional. Basically non-transactional software is just a mess of bugs waiting to happen.

[shelby3]

@keean wrote:

We can. That is one of the main points of the ACM article that I linked to. Have you read it?

Yes, and I disagree with it. Only certain operations are vectorisable, and we have had vector architectures since the CRAY. They have all died out in favour of parallel node running Intel x86 chips.

It’s impossible to disagree. Serial is stuck in the mud and will not scale by Moore’s law. What are you disagreeing with? That you prefer to perish?

It is as if you have not even read my post. I already made that point. We have no choice but to find parallelisable algorithms. Perpetuating failure is not an option. Those who do will perish and those who don’t will flourish.

Parallel architectures like GPUs are great at certain specific tasks, but are not great at general purpose computing.

You’ve inverted the objects in the logic. The correct statement of reality is, “Parallel architectures like GPUs are great at certain parallel tasks which is the only possible future of general purpose computing, but most programmers and their PLs prefer to not be part of the only possible future of general purpose computing.”

There is no 'new architecture', we either solve the problems, or go back to 486 (at a higher clockspeed) performance.

The massively multi-core and GPU architectures are the “new” architectures. We do not go back to single-core 486. What are you smoking? You’re mind is fixated on that serial algorithms are an invariant. If that is true, then society will perish. Because there’s no plausible way that serial algorithms will not stop scaling.

Intel's next generation includes fixes for these attacks. Expect to see more fixes

It can’t be entirely fixed because it’s a broken paradigm, i.e. an anti-pattern.

It will be Whac-A-Mole as more and more statistical vulnerabilities are found. Besides the shit isn’t getting any faster. It is exponentially falling away in terms of performance compared to parallel general purpose computing. You can either board the train or fall into the abyss. What is your choice?

really don't think the x86 juggernaught can be stopped. You have to sell huge quantities of these CPUs to afford the fabrication plants to make them. Intel invests a lot of its CPU revenue into building these billion dollar facilities, and it keeps itself ahead in the fab-technology business.

You really got this one backwards. GPUs are outperforming Intel on general purpose parallel computing. Intel needs those economies-of-scale because they can barely squeeze any more serial performance improvements out of their chips. But the real elephant in the living room is as Eric Raymond pointed out in one of his comments, is that the rate of increase in performance of serial computing is decreasing. And eventually there will be no reason to buy a new Intel CPU. Intel’s business model depended on CPUs becoming obsolete every 18 months due to Moore’s law. If all you need are serial computing, then you have no reason to ever again give Intel any more money.

You intepreted the reality precisely backwards of what it is. Intel is dying!

[keean]

which is the only possible future of general purpose computing

This is not true. Only a small subset of algorithms are parallelisable, others cannot be because they require the results from previous computation stages to compute the next.

In general program flow control logic is not parallelisable, programming is all about sequences of operations, and only a few of the are parallel.

For example how could you parallelise Euclids greatest-common-divisor algorithm? How can you parallelise addition (you cannot because of the 'carry')?

Most computers already have a high performance parallel engine installed, the GPU, now look at the class of algorithms and programs that actually benefit from being implemented on the GPU. Its not general purpose software like Word or Photoshop, but it is specific algorithmic kernels, like Photoshop filters that benefit.

[shelby3]

@keean wrote:

which is the only possible future of general purpose computing

This is not true. Only a small subset of algorithms are parallelisable, others cannot be because they require the results from previous computation stages to compute the next.

What is not true? It is a fact the serial algorithms can’t keep up scaling with technological progress that nature demands. Serial algorithms can’t get any faster. Yet I repeat myself, because your replies entirely ignore that point.

You continue to force me repeat what I already wrote in my original post which you claim you read, but you clearly did not read. I already rebutted that point in my original post.

There are always ways to restructure and paradigm-shift. Just requires motivation and a clever mind.

In general program flow control logic is not parallelisable, programming is all about sequences of operations, and only a few of the are parallel.

As if you can predict all the ingenuity that can possibly be. This is the mindset of the Luddites.

So you’re resigned to failure then?

For example how could you parallelise Euclids greatest-common-divisor algorithm? How can you parallelise addition (you cannot because of the 'carry')?

Use a different algorithm that accomplishes the task from a different perspective. Paradigm-shift the context.

Besides you don’t know what math ingenuity will come forth when mankind has no other option.

For example, you apparently ignored or did not read where I suggested to Eric (although he will never read it because he censored my comment), that he try speculative parallelism. There are likely speculative versions of algorithms which are much more efficient than low-level pipelining speculation, because higher-level semantics provide more information with which to speculate.

Most computers already have a high performance parallel engine installed, the GPU, now look at the class of algorithms and programs that actually benefit from being implemented on the GPU.

For one reason because our PLs suck which is what the ACM author pointed as a first line of attack on the issue.

Its not general purpose software like Word or Photoshop, but it is specific algorithmic kernels, like Photoshop filters that benefit.

Because Word does not need the performance boost. If there are slow serial algorithms (such as search) which need acceleration, then people will put effort into finding those algorithmic gymnastics.

---

I am taking this issue into consideration while designing the new programming language Zer0. You can go along and perish if you prefer. It’s your choice. It’s a free market.

[keean]

Use a different algorithm that accomplishes the task from a different perspective.

This is not always possible.

Because Word does not need the performance boost. If there are slow serial algorithms (such as search) which need acceleration, then people will put effort into finding those algorithmic gymnastics.

A sequential algorithm is always sequential. There are reasons why problems a N, P or NP. You cannot short-circuit, its one of the fundamental results from mathematics.

You can wish for a unicorn, but that does not make it real, it just means you don't understand enough about evolution to see why there is no such thing.

So you’re resigned to failure then?

I am resigned to single threaded CPU performance always being important. In theory the GPU in your computer is capable of more FLOPS than the CPU, yet most software continues to run on the CPU. Why is this? Its not just about performance, its about the programming model, and the fact that Humans fundamentally think sequentially.

Looking at video games, the rendering is obviously parallel, and so is the physics engine (although not everyone is doing this on the GPU yet). The game state and game logic is not parallelisable. You either have the key or not, and the door only opens if you have the key etc...

So we come back to fundamentally software is driven by a state-machine, and by its very nature that you can only be in one state at any given time, and you can only transition from one state to the next, it is sequential. This relates to the fundamental nature of time itself. Its why the arrow of time points forwards, and the whole universe past, present, and future does not happen instantly all at the same time.

[shelby3]

This is not always possible.

Then choose to perish. You have no response to that fact.

I prefer the choice of not using serial algorithms (when I need performance from them and when I can’t run multiple instances of them in parallel). Just say no. Find other tasks to work on which are amenable to technological progress. Don’t waste time on failure modes.

A sequential algorithm is always sequential. There are reasons why problems a N, P or NP. You cannot short-circuit, its one of the fundamental results from mathematics.

Oh don’t take me off on that tangent. It is not fundamental. Also you just conflated “short-circuit” with speculation. The later may change the complexity classification of the algorithm.

And here follows an unarguable example that is not even speculation. The easy way to parallelise every serial algorithm is to instantiate multiple instances and run them simultaneously. I already wrote that in my original post. And I have even suggested Eric could leverage the market to sell his spare CPU cycles.

So you’re resigned to failure then?

I am resigned to single threaded CPU performance always being important.

Then respectfully and frankly your answer is both “yes” and “I’m very myopic on this issue and thus should not be allowed to design a PL for future general purpose computing (by myself) since this issue is critically important.” Or at least you should not be allowed to design one without my assistance to prevent you from making such egregious lapses of logic. And I should probably not be allowed to design one without your assistance on other areas where I will make blunders.

The game state and game logic is not parallelisable[parallelized].

ftfy.

Often because it isn’t critical to performance. I know you are aware of the Pareto principle and the 80/20 rule.

yet most software continues to run on the CPU. Why is this?

Partially because PLs suck as explained in the ACM article. And also because the users of this software not desperate enough yet. As they become desperate due to the lack of performance scaling, then vendors are forced to find parallelized solution. They will have no other choice!

You either have the key or not, and the door only opens if you have the key etc...

Sorry but that is a very closed-minded, ossified minded, and an incorrect presumption. You highly underestimate the ingenuity of mankind.

So we come back to fundamentally software is driven by a state-machine, and by its very nature that you can only be in one state at any given time, and you can only transition from one state to the next, it is sequential.

Incorrect. Presumptuous. Single-minded. Lack of creativity and imagination. Inability to think-out-of-the-box. Etc..

This relates to the fundamental nature of time itself. Its why the arrow of time points forwards, and the whole universe past, present, and future does not happen instantly all at the same time.

Misapplication of a principle. As if parallelized algorithms go backwards in time? Rather what they do is ignore time.

The universe is relativistic. Billions and trillions of events are occurring simultaneously just here on Earth. And they can’t even prove to each other that they actually all occurred at the exact same time, because the propagation of their events is not instantaneous.

Parallelism is merely the requirement that non-instantaneous and non-ordered communication (of results) is acceptable.

[shelby3]

@keean wrote:

exceptions have a huge cost on failure, it can take 100s of clock cycles to unwind the stack, just jumping to an exception vector in hardware takes 100+ clock cycles, and it causes the instruction pipeline to stall.

Error returns have equal (low) cost on both success or failure.

Worse than irrelevant. Exceptions are supposed to be exceptional events, where recovery actions will be required, which are going to consume a lot of clock cycles. Exceptional events should not be occurring often enough to have any impact on performance.

And we do not want to slow down success just to improve the performance of the rare exceptional failure events which are going to still be slow any way.

I already covered this point in my longish post up-thread. ^{_{Why is your reading comprehension so compromised today? Is it because you are too busy multitasking or reading on your tiny mobile phone screen?}}

Also in my longish post, I linked to where I have gone into greater detail about how to improve the performance of throwing exceptions.

Transactions will break modularity and functional composition. You have an outer layer that demands a transaction but then inner layers want a conflicting transaction.

Even simple web applications need transactional safety. What happens if I press the next page button, but before that operation completes, I press the previous page button. The async callbacks for both promise chains now interleave leaving the state in an undefined position, and probably crashing the application.

How is this related to transactions of exceptions (i.e. exceptional events)? Please do not tell me you were proposing to model mouse events as exceptions!

Event handling is an orthogonal issue.

Perhaps you’re thinking that an exception which fires before the drag-and-drop operation completes has to clean-up the drag-and-drop transaction?

But that is handled by having that controlling code catch the exception and do the cleanup. I don’t see why we need to model exceptions as return values for that?

If you are going to have a reasonably robust UI you need it to be transactional, you also need network packet handling to be transactional. Basically non-transactional software is just a mess of bugs waiting to happen.

But that process/control logic is orthogonal to how we throw exceptions.

And those are abortable transactions, which is the not the same thing as what I defined transactions to be. Abortable transactions can be broken out of a livelock or deadlock situation without putting the application into an incoherent state.

[sighoya]

@shelby3 wrote:

The easy way to parallelise every serial algorithm is to instantiate multiple instances and run them simultaneously

What does it gain? If you need the last result for the new computation you need either to wait or you integrate over the past in parallel requiring many clusters which remains bad joke for exponential explosions. And we currently don't know if the most popular complexity class NP is equal to EXPTIME.

More of promise are other state machines like quantum computers and dna computers from what I heard though unfortunately quantum computers can turn only NP-Intermediate into P which is mostly not of interest and the ability to turn exptime complete problems into ptime with dna computing seems to be an fake.

[shelby3]

What does it gain? If you need the last result for the new computation

You do not if you’re running multiple independent instances. Are you telling me that you can’t find any independent instances in the universe?

What happened to you guys?

And we currently don't know if the most popular complexity class NP is equal to EXPTIME.

This is irrelevant. You guys are looking at the bark on the trees instead of looking over the treetops of the forest.

Open/broaden your mind to a different way of thinking about the issue.

[sighoya]

You do not if you’re running multiple independent instances.

To reformulating a bit, what does the "running multiple independent instances" strategy exhibit for advantages against serial computation?

And we do not want to slow down success just to improve the performance of the rare exceptional failure events which are going to still be slow any way.

Agree, failure state and the rollback incur costs and because it occurs or should occur very rare it is not of much importance.

Corrected.

[shelby3]

To reformulating a bit, what does the "running multiple independent instances" strategy exhibit for advantages against serial computation?

We don’t waste CPU cycles (and electricity) as heat on speculative pipelines that abort most of the branches taken. And we continue to scale computation with Moore’s law. This should have already been extracted from what I wrote, yet I am happy to recapitulate it.

Did I misinterpret the intent of your question?

[sighoya]

Did I misinterpret the intent of your question?

To be more concrete, in which way does it help to solve a serial problem better than solving it serial?

[shelby3]

To be more concrete, in which way does it help to solve a serial problem better than solving it serial?

Ditto my prior response.

Serial isn’t going to get any faster. Might as well choose to scale and take your Moore’s law benefits where you can get them.

It is very inane¹ to presume that extracting 30% more serial performance is a good tradeoff compared to forsaking Moore’s law. Linear speedup versus exponential. That ACM article pointed out that something 80 – 90% of the transistors in an Intel CPU are for all that serial speculation crap such as register rewriting, microcode, etc.. That was an important datum, because it means they can’t scale both serial and parallelism (i.e. cores). The percentage of transistors being wasted for diminishing linear returns that forsakes exponential speedup. Do you enjoy beating you head into a wall to see that it will not get out of the way?

See how paradigm shifts work? This is why all the argumentation about NP complexity class is irrelevant. We must lift our analyses to a higher-level of holistic variables.

¹ _{Not directed at you guys. Just trying to emphasize a point.}

[shelby3]

@sighoya wrote:

unless we allow the throws to be inferred by the compiler so these are never explicitly annotated

Sounds like exception deduction :). This can become quite cumbersome if the compiler checks down all exceptions in the call hierarchy, which becomes especially problematic if functions are already compiled, sure you can put a list of possible exceptions into your program binary.

In my eyes, the user generally should annotate his functions with the exceptions important for him. And exceptions which are not important could be together mentioned by annotating the general supertype Exception.

The compiler should only look for exceptions at function signatures which are directly called in the current scope. This would be more lightweight.

When functions are compiled, the list of inferred checked exceptions would need to added to a metadata file, so that separate compilation can work.

I don’t agree that it presents any problems that should cause us to do it incompletely as you suggested.

[sighoya]

To be more concrete, in which way does it help to solve a serial problem better than solving it serial?

Ditto my prior response.

It doesn't answer my question. I'm with you that more parallelism is nice and will also be the future.

This is why all the argumentation about NP complexity class is irrelevant.

No, it is not. Parallelism does not solve it, a new computing model does. For any linear input you need exponential size of cores/clusters which quickly exceeds our galaxy in space, it is not realizable.

To the worse, if we are able to have more parallelism our needs increase as well but this is more general problem at all.

[keean]

@shelby3 Okay, so how would you parallelise the 'zerolang' compiler? Can you parallelise the grammar parser? Can you parallelise the Abstract Syntax Tree rewrites? How would you parallelise the code generation?

[shelby3]

@sighoya wrote:

To be more concrete, in which way does it help to solve a serial problem better than solving it serial?

Ditto my prior response.

It doesn't answer my question.

Disagree. I already addressed your question. I don’t understand why you guys have such difficulty with paradigm shifting your thought processes. This is a frustrating discussion. I think I have already explained my perspective several times already. I suppose you also are similarly frustrated, thinking that I am somehow missing the point. Let’s see if we can somehow cross the chasm of our respective cognitive dissonance.

This is why all the argumentation about NP complexity class is irrelevant.

No, it is not. Parallelism does not solve it, a new computing model does. For any linear input you need exponential size of cores/clusters which quickly exceeds our galaxy in space, it is not realizable.

Solve what? Nothing solves the fact that NP-complete algorithms which require superpolynomial computational complexity are not going to scale (not even heuristics can solve that). That is why I say this is an entirely irrelevant issue in a discussion about whether to prioritize diminishing linear serial speedups or continuing the exponential speedup of Moore’s law with parallelism.

Why are you guys conflating the fact that an algorithm is serial with its computational complexity when those can be orthogonal attributes. Even if an NP-complete is parallelized, it remains superpolynomial to compute each parallelized guess and verification. Unless the number of cores can be increased exponentially (or other subexponential subclasses of superpolynomially in some cases) then parallelism will not make such an algorithm scalable.

Also why do you presume that all NP complete problems are not parallelizable? In fact, the heuristics to make some such problems solvable for practical real world problem sizes (e.g. the 3-SAT) involve failures of guesses, so doing guesses in parallel may improve the overall average running time. Which is precisely what I suggested in my original post on this matter wherein I suggested attempting “speculative parallelism”. My intuition is that when such heuristics are reanalyzed from the perspective that we can waste electricity in exchange for speedups, then we’ll find that higher rates of failures for guesses have overall faster running time when highly parallelized.

The point is that for the algorithms we have which are practical, then serial speedup is not scaling by Moore’s law. So we need to prioritize algorithms (and heuristics) which scale better when parallelized. I even provided a very simple example which applies to all algorithms, which is to run multiple independent instances. Beyond that, there may be heuristics which scale a single instance as I have alluded to above.

I really do not understand why I had to write this long post. I think both of you guys are mathematicians at least at the undergraduate level for an engineering course. Am I missing something in my analysis?

[shelby3]

@keean wrote:

Okay, so how would you parallelise the 'zerolang' compiler?

You ask me to repeat myself. I already mentioned running multiple independent instances. So if files can be separately compiled, then compile multiple files in parallel.

Can you parallelise the grammar parser?

Now you’re asking me to parallelize a single instance. This isn’t absolutely required as some parallelism can be obtained simply with multiple independent instances, yet this additional parallelism would be nice to have (or at least as an option if induces significant slow down compared to not parallelizing in the case where we have sufficient independent instances).

Actually I can think of some algorithms for this which might work. For example, if we can presume no closures (such as at the top-level lexical scope), then we can speculatively (or perhaps deterministically) search for function declarations and parse these independently. Actually the requirement for independence of lexical shadowing isn’t strictly needed for the parsing, but is needed for the phase of unifying the identifiers.

Can you parallelise the Abstract Syntax Tree rewrites? How would you parallelise the code generation?

Ditto. I’ll work through the details when I am ready to work on it.

_{P.S. AFAICT, most IQ tests are unable to measure this sort of divergent and creative thinking. I found a test that seems to measure it and it placed my IQ higher (above 140) than standardized tests such as SAT and ACT respectively (which seem to place it between 128 and 137 and the latter was when I wasn’t lazy about it). I know that on mechanized computation my brain moves more slowly such as complexly folded pattern matching, and thus IQ is not so high. But on highly divergent thought processes, my creative interest kicks in and I excel. My mental energy is different when this happens. My dopamine starts firing like crazy and I am fully engaged in the mental activity.}

_{Another example of my divergent thinking is in 2009 when the self-proclaimed 167 IQ Risto Pietilä (and I verify that he can beat me in computational games) was just getting started with his silver business and the Finnish government had confiscated all his silver, he was very depressed. I suggested he sell the confiscated silver at a slight discount to many customers, so the government would have to fight many respondents. This was successful and the silver was released by the government.}

_{Another example is that I solved the problem the same way as this genius kid did:}

_{Nonetheless, a clever 6th grade student of mine, who is today a PhD student in robotics at Carnegie Melon, had a much more clever and simple idea. Every 12 hours, the minute hand passes over the hour hand exactly 11 times. Get an old clock with hands and try this if you need to see why. Thus the time between "passovers" is 12/11 hours. Three of these gets us the correct answer.}

_{EDIT: Yet another recent example of my divergent thinking.}

[keean]

@shelby3

Now you’re asking me to parallelize a single instance. This isn’t absolutely required as some parallelism can be obtained simply with multiple independent instances, yet this additional parallelism would be nice to have.

Yes, we are talking about a single instance, of course you can run on multiple files at once (providing you have good modularity, not true for all compilers).

We are talking about the fact that algorithms consist of steps that need the complete output from the previous step in order to complete. Yes we can parallelize where there are no dependencies, and yes we can pipeline where things are semi-dependent, but my point is you overestimate how much parallelism is in the average piece of software. Not all software is scientific or mathematical computation that is easily parallelizable by matrix operations. If we actually look at real code we find superscalar processors which can exploit the implicit parallelism in code using hardware can rarely get more than a 2-3 times speed up.

I think the point is that real world software is not CPU bound, and does not do a lot of computation, it tends to be IO bound, and spends a lot of time waiting for the use, or the disk, or the network. It does not need to be any faster overall (in bandwidth) but it needs to be responsive (low latency) so when the user does issue a command it responds quickly. Often distributing the data for parallel computation takes longer than just doing it sequentially in these situations (data has to be copied to each of the N cores before the calculations happen, and they the results combined back into one).

Really parallelism is only really useful in a limited number of situations, and those are already being done by the GPU on your computer, or being run on a networked supercomputer.

Also writing parallel code is harder for the programmer and more difficult to debug. As our brains have a complexity limit we have to be careful where we spend our complexity budget. If the gains are minimal, there is no point in makimg the code needlessly more complex, as it reduces the overall complexity of the application we can manage to successfully program.

Further we can see accelerating simple to write code in the CPU hardware benefits millions of programmes around the world, so for the CPU vendor it makes sense to accelerate this simple code, as that's what the majority of programmers write (and want to write) and this benefits end users by getting what they want done faster.

[sighoya]

I conjoin @keean's opinion, permanent parallelism could even harm your performance. For instance Java's concurrent map takes sometimes longer than a sequential one.

If something could be parallelized resulting in shorter execution time, then it should be but to decide it will is not always diaphanous.

[shelby3]

@keean wrote:

but my point is you overestimate how much parallelism is in the average piece of software.

You continue to ignore my point which is we have no choice but to stop being lazy and derelict about programming.

You continue to argue that we should encourage programmers to be stupid and continue down the path of self-destruction, which I already explained to you that Intel is dying and serial programming is dying.

You choose to think that there isn’t sufficient ingenuity and I am not pessimistic, because I know damn well that I am ingenious and I doubt I am the only one.

So the Russian programmers will kick our Western asses in this new paradigm:

The German: Methodical, good at details, prone to over-engineering things, careful about tests. Territorial: as a project lead, can get mightily offended if you propose to mess with his orderly orderliness. Good at planned architecture too, but doesn’t deal with novelty well and is easily disoriented by rapidly changing requirements. Rude when cornered. Often wants to run things; just as often it’s unwise to let him.
[…]
The Russian: A morose, wizardly loner. Capable of pulling amazing feats of algorithmic complexity and how-did-he-spot that debugging out of nowhere. Mathematically literate. Uncommunicative and relatively poor at cooperating with others, but more from obliviousness than obnoxiousness. Has recent war stories about using equipment that has been obsolete in the West for decades.

We Westerners are too structured in our thought processes and unable to get out of the box. I guess I never did fit in there, so that is why I left. The linked discussion is hilarious. And this is the coming death of the West and because neither politics nor opinion equates with engineering.

The fact is that serial is dying. You have no choice. End of story. So you going to continue to encourage failure or stop being so pessimistic about ingenuity?

Not all software is scientific or mathematical computation that is easily parallelizable by matrix operations. If we actually look at real code we find superscalar processors which can exploit the implicit parallelism in code using hardware can rarely get more than a 2-3 times speed up.

You’re ignoring the points I already made such as the fact that there’s more semantic information when the speculative parallel algorithm is lifted to a higher level. The Russians and Chinese will kick our asses, because they’re much less into this “you can’t” dogma you’re preaching and rather into pragmatism of rolling up their sleeves and building solutions. Goroutines were one of the first salvos into this new regime we’re headed into.

Also I already took your challenge of finding a way to structure something such that I can find parallelism. And then you just claim that I can’t find parallelism in the next set of challenges you give me. I do not have time to play this game. I have great confidence in human ingenuity. I’m not a Luddite. Didn’t the Luddites originate over there in the UK?

It is not opinion. It is because throughout antiquity when humans have no other choice, then they always do their best to find a way.

I think the point is that real world software is not CPU bound, and does not do a lot of computation, it tends to be IO bound, and spends a lot of time waiting for the use, or the disk, or the network. It does not need to be any faster overall (in bandwidth) but it needs to be responsive (low latency) so when the user does issue a command it responds quickly.

Indeed. And because of the many factors, there’s so many opportunities for parallelism that you can’t possibly be omniscient about. I equate willfully presumptuous of being omniscient with being arrogant.

Also writing parallel code is harder for the programmer and more difficult to debug. As our brains have a complexity limit we have to be careful where we spend our complexity budget.

Not everyone should be designing bridges that fall down.

If the gains are minimal

They’re not. You still insist on the incorrect mental model, even though I have attempted numerous times to explain the paradigm shift for you. Here it goes the same explanation again, repeated again…

Further we can see accelerating simple to write code in the CPU hardware benefits millions of programmes around the world, so for the CPU vendor it makes sense to accelerate this simple code, as that's what the majority of programmers write (and want to write) and this benefits end users by getting what they want done faster.

What part of “serial speedups in the CPU are hitting a wall with diminishing increases on each new iteration” do you still fail to grok after the Nth time I have repeated it?

Often distributing the data for parallel computation takes longer than just doing it sequentially in these situations (data has to be copied to each of the N cores before the calculations happen, and they the results combined back into one).

I already refuted that in my original post. It really sucks for me that you claimed you read my original post, but you clearly did not. Then you cause me to spoon feed my original post to you, because you were too preoccupied to read it. Causing me to write numerous additional posts needlessly.

Let me quote what I wrote in my original post:

So the author of the article explained that instead of complex caches (and to accommodate the large working sets that the Transputer didn’t) we perhaps need an architecture where we have so many threads running that the latency to shared memory can be offset by computation these threads have to do in between accesses to main memory such that the CPU is always fully utilized. IOW, while some threads are waiting on main memory, other threads are running computation.

Note AFAIK that most GPUs cards include a lot of shared memory with a very fast, wide bus. So perhaps they’re already close to what is optimal even for large working sets.

Also you’re essentially repeating what I already wrote:

yet this additional parallelism would be nice to have (or at least as an option if induces significant slow down compared to not parallelizing in the case where we have sufficient independent instances)

You are failing to incorporate the concept of scaling into your mental model. Even though parallelism can cause some waste, it is overall a scaling win and it is the only way to scale.

Scaling is everything. Steve Jobs was famous for killing projects early that he knew could not scale.

---

@sighoya wrote:

I conjoin @keean's opinion, permanent parallelism could even harm your performance. For instance Java's concurrent map takes sometimes longer than a sequential one.

Citing crappy software and programming done poorly is not a refutation of that fact that serial is dying and only parallelism scales.

And ingenuous programmers will not make parallel things that go slower than running the same algorithm serially.

No where did I state all algorithms must become parallel. I have made the point that all algorithms which the program depends on for scaling performance must be parallelized otherwise your program will not scale. That is simply a statement of fact.

[keean]

@shelby3

You’re ignoring the points I already made such as the fact that there’s more semantic information when the speculative parallel algorithm is lifted to a higher level.

Actually you have that backwards, there is more information about parallelism available at runtime. This is why VLIW processors failed to outperform x86.

VLIW was based on the idea that the compiler could do more to extract parallelism from the code than the CPU, so they made a highly parallel CPU with many execution units that could run multiple instructions in parallel. The compiler then created instruction bundles that contained a set of instructions to run in parallel. Essentially they stripped the speculative out or order hardware out of the CPU and used that space for extra execution units. This relied on the compiler to produce the parallel instruction.bundles. What they found was it could only outperform the x86 on very specific scientific computation tasks, and failed to be faster for general computation.

I go with evidence over speculation every time.

[shelby3]

Please kindly move further Parallelism discussion to the new Parallelism issue thread.

I replied to @keean over there at the new thread.

[sighoya]

@keean wrote:

Exceptions can be implemented as an additional return value by writing code in the Error Monad. So there is no difference in speed between exceptions and error return values.

The problem with error return values is the bottom up propagation, i.e. checking the return value in each enclosing function and jumping back multiple times to the next enclosing function.

The better it is to jump once directly to the position outside of the current function where the appropriate error is handled by exception throwing and not to check over and over again if an error has occurred.

[keean]

@sighoya

The better it is to jump once directly to the position outside of the current function where the appropriate error is handled by exception throwing and not to check over and over again if an error has occurred.

I agree, however my point was that the semantics are the same. In other words from a type system perspective you can encode the exception as an ErrorMonad, the implementation could jump directly.

[shelby3]

Both of you seem to be ignoring the discussion we already had starting at this linked post.

@sighoya wrote:

@keean wrote:

Exceptions can be implemented as an additional return value by writing code in the Error Monad. So there is no difference in speed between exceptions and error return values.

The problem with error return values is the bottom up propagation, i.e. checking the return value in each enclosing function and jumping back multiple times to the next enclosing function.

The better it is to jump once directly to the position outside of the current function where the appropriate error is handled by exception throwing and not to check over and over again if an error has occurred.

Depending on the design of the stack frames there can be an additional cost to recording the locations to jump to the point of the try-catch-finally block as compared with checking every return value. Yet checking every return value is an additional cost which the former doesn’t have. Also checking every return value is extremely noisy, although the ErrorMonad concept can make checking it optional thus emulating to some extent jumping (which is apparently what Pony does except Pony apparently doesn’t distinguish which type of error occurred which seems really lame).

@keean wrote:

I agree, however my point was that the semantics are the same. In other words from a type system perspective you can encode the exception as an ErrorMonad, the implementation could jump directly.

I fail to understand how the ErrorMonad can offer both checking the return value in user code and jumping to try-catch-finally in user code. I think it has to choose one of the two semantics?

That is unless somehow your compiler implicitly forces (provides the implicit boilerplate for) every function application to wrap its descendant code into another application of bind of the ErrorMonad.

EDIT: if the ErrorMonad is so great, then why do people still complain about Rust using it instead of try-catch?

[shelby3]

Revisiting this again, I think I was correct near the start of this thread, that we need both checked and uncheck exceptions.

Programmers can also employ return values for frequent (non-exceptional) error conditions. And even employ a monad if they wish. We should supply a standard Error return monad which can wrap any return value and force the caller to unwrap it to get the value out. This is to discourage programmers from abusing the exceptions for the non-exceptional errors. To avoid the following:

Conclusion

Exceptions in Java provided major benefits in reliability & error-handling over earlier languages. Java enabled reliable server & business software, in a way C/ C++ never could.

Checked exceptions were, in their original form, an attempt to handle contingencies rather than failures. The laudable goal was to highlight specific predictable points (unable to connect, file not found, etc) & ensure developers handled these.

What was never included in the original concept, was to force a vast range of systemic & unrecoverable failures to be declared. These failures were never correct to be declared as checked exceptions.

I think however we need a way to declare that a chain of Error monad errors can be checked only at the end of a chain, so that we can accommodate @sighoya’s chaining boilerplate point.

Pony also has exception safety but that comes at the cost of not having any exception types and not being able to optimize for truly exceptional events (as opposed to common errors). So instead Zer0 will have checked exceptions when exception safety is needed, unchecked exceptions for non-exogenous exceptions, and Error monad for exception-safe common errors.

[shelby3]

Added:

Pony also has exception safety but that comes at the cost of not having any exception types and not being able to optimize for truly exceptional events (as opposed to common errors). So instead Zer0 will have checked exceptions when exception safety is needed, unchecked exceptions for non-exogenous exceptions, and Error monad for exception-safe common errors.