The computational DAGs of programs are usually infinite but symmetric, so the solution probably needs to leverage symmetry in the representation.
The “computational graphs” of programs are usually infinite but directed, acyclical, and “symmetric”. The solution will probably be faster/simple/more efficient if it leverages “symmetry” in the representation.
Also, existing languages have way more bells and whistles than I really want to deal with for this project, even setting aside the likely importance of simplicity for reflection.
Oracles? What level of granularity do you want for this? Do you care about what exact algorithm things are sorted with, or just that they’re sorted?
Are you pulling from a language or pushing to a language? (Converting the ‘causal DAG’ of the program into a program, or the other way around?)
As the saying goes, any sufficiently complicated software project contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp. Don’t use this as a primary programming language, folks.
Which half? If it’s the same half, then why not use that half as a universal language?
COPY OF THIS CONTEXT BUT WITH n REPLACED BY n-1
My favorite part of math: writing things like n = n-1.*
*This line of thinking “If P(x) holds for all x, P(x+1) holds for all x+1.” imposes constraints on P, like 1) that it not process “2+1″ differently than “3”, or that whatever calls it handles that pre-processing, and 2) something like “P(x) is a functional program.” or “P(x) is deterministic.”.
A computation is the actual series of steps performed when running a program. So any program specifies a computation, but most languages don’t have a nice way to do things with the computation other than get the final output (i.e. by running it). The point of this project is to work out a nice data structure for representing a computation, so we can ask questions about it other than just getting the final output.
The “computational graphs” of programs are usually infinite but directed, acyclical, and “symmetric”. The solution will probably be faster/simple/more efficient if it leverages “symmetry” in the representation.
Oracles? What level of granularity do you want for this? Do you care about what exact algorithm things are sorted with, or just that they’re sorted?
Are you pulling from a language or pushing to a language? (Converting the ‘causal DAG’ of the program into a program, or the other way around?)
What are computations—programs?
Which half? If it’s the same half, then why not use that half as a universal language?
My favorite part of math: writing things like n = n-1.*
*This line of thinking “If P(x) holds for all x, P(x+1) holds for all x+1.” imposes constraints on P, like 1) that it not process “2+1″ differently than “3”, or that whatever calls it handles that pre-processing, and 2) something like “P(x) is a functional program.” or “P(x) is deterministic.”.
A computation is the actual series of steps performed when running a program. So any program specifies a computation, but most languages don’t have a nice way to do things with the computation other than get the final output (i.e. by running it). The point of this project is to work out a nice data structure for representing a computation, so we can ask questions about it other than just getting the final output.