3 ms·
Just content-addressability isn’t enough, there should be also canonical forms, I.e. h = hash(to_canonical_form(AST)) Preferably, there should be one-and-only
by nivertech 3y ago
Just content-addressability isn’t enough, there should be also canonical forms, I.e.
h = hash(to_canonical_form(AST))
Preferably, there should be one-and-only-one way to perform or compute things, but modern PLs plagued by flexibility syndrome.
Also, the same should be done for the binaries, since the same AST may produce different binaries, unless you take into account all the compiler options, and runtime differences.
- geysersam 3y agoI think this is impossible in theory (but maybe not in practice ;)) Determining if two programs are equivalent is generally as hard as running the programs for every input and comparing them.
- nivertech 3y agoYes, I'm talking about practical solutions, similarly like Halting Problem doesn't have a solution according to the CS, but there are practical solutions like the one used in Ethereum with its gas-based metering, or disallowing recursion or unbounded loops. Some practical solutions: - reduce code variability, by removing similar/alternative programming constructs / flexibility syndrome - stick to a single programming paradigm - remove syntactic sugar, or provide a clear rules to reduce it to a sugarless canonical form - use a rich standard library (to avoid reimplementing the same functionality in different ways) - use rich standard data types (to avoid definition of the similar types in different ways) - sort every unordered construct, similarly how AWS signature sorts the keys before calculating the API call signature - reduce the use of macros, custom eDSLs, or highly personalized code (by making writing this kind of code inconvinient) - etc.