|
|
|
|
|
|
by nyanpasu64
1672 days ago
|
|
|
I don't think we'll ever be able to calculate program designs, like having a computer design the theoretically optimal {sorting algorithm, hashmap, SQL engine} for a given processor, for a particular performance criterion (average-case and worst-case performance), out of the exponentially exploding set of possible type and function definitions. And "the perfect system" is different on a DS, a smartphone, a desktop PC, or a GPU or supercomputer. I think it's orders of magnitude more complex than designing an optimal chess algorithm. But I'll look into the PDF you linked, since I believe "calculating a program design" would be great to have (though I doubt it's possible), and people aiming for it will hopefully create useful tools along the way. I do think we can and should define a self-consistent internal logic for the program designs we do write (eg. under a given set of valid inputs, the program is is memory-safe, is thread-safe, does not produce UB, has program-specific invariants upheld by each function's preconditions and postconditions, and produces correct results with eg. O(n log n) runtime, making O(n) allocations totaling O(n) bytes ever allocated), then verify that the code we write upholds this logic. Every program has an internal logic, correct programs have self-consistent logic, and any holes in the logic are exposed as bugs in the program. And easily understood code makes this logic self-evident to readers. |
|
|
Not talking about efficiency here. The theoretical optimal for time complexity is already done. We know how to calculate a quantitative measure for average case and worst case performance. For many problems we know the solution for how to optimize for both of the above cases.
When I refer to design I refer to the aspect of computer science we do not have theory for. How do you organize your logic? What is optimal organization of code such that it is optimal and future proof? This area I believe can be formally defined.