Thursday, November 25, 2021

Futamura Projections

 I was discussing Futamura projections and made two observations.

  1. Most of it remains true when you consider that partial evaluation doesn't have a lot to do with it all. Just take an interpreter and input program, combine them, and you already have a 'compiler.' The whole partial evaluation stuff is more the icing on the cake which makes you hope you can end up with an efficient solution.
  2. Regarding the efficient solution, it's likely the case that partial evaluation in the extreme is an undecidable or NP problem. As an intuition, just take a sat solver as an interpreter. Then Futarama predicts that a sat solver plus a problem statement would give an efficient solver for that problem class,  and presto, your specializer proved P versus NP. Doesn't mean you cannot try this approach heuristically, but does imply that you have less than no guarantees at arriving at an efficient solution.
My $.02.

No comments:

Post a Comment