4 ms·
> describing a richer and richer space of computation So, changing the compiler from targeting a stack / finite state machine (no register allocation - see zer
by downvotetruth 4y ago
> describing a richer and richer space of computation
So, changing the compiler from targeting a stack / finite state machine (no register allocation - see zero address format) to registers (NP complete to allocate the registers)?
Alternatively, changing the available static / compiled features of a language is usually offered with compiler flags or keywords. Concatenative languages are already Turing complete up the restrictions on functions as such to being total.
- thechao 4y agoWhy would using registers make it NP complete? Is there a reason concatenative languages aren't (naturally) primal chordal graphs? I mean other than the conservative approximation being to assume it is not?
- downvotetruth 4y agoWhy would using registers make it NP complete? If there are no registers to allocate, then there is no Core Register Allocation (NP complete) problem. Is there a reason concatenative languages aren't (naturally) primal chordal graphs? "Naturally" is not distinctive, but concatenative languages can be compiled to registers & induce the Core Register Allocation problem that was proven NP complete by use of primal chordal graphs.