The Magic of Partial Evaluation

(jimmyhmiller.com)

116 points | by aray07 2 days ago ago

45 comments

  • TuringTest 2 days ago ago

    > For me, the most beautiful pieces of software are those that reveal something about the nature of programming languages.

    There are three moments that make the functional programmer evolve their understanding of how a programming language really works as a symbolic representation of human thought, beyond the metaphor taught in school of a computer program as a grinder that crunches input data and produces results.

    The first one is when you really understand recursion and how a function can be defined in terms of itself (with varying parameters for each call).

    The second is when you discover Prolog variable unification or Haskell lazy evaluation and how you can represent infinite data structures without having the program hang in an infinite loop.

    Third one is when you learn that the behavior of any imperative language (down to the working of the microprocessor data paths) can be fully represented in a pure functional rewrite language (without destructive assignment / cell state changes).

    Those insights make one realize that all programming paradigms have the nature of symbols processing in common and there's no "true description" of a program's runtime execution - the imperative, functional and logic views of the running program are all equivalent representations.

    • packetlost 2 days ago ago

      > Third one is when you learn that the behavior of any imperative language (down to the working of the microprocessor data paths) can be fully represented in a pure functional rewrite language (without destructive assignment / cell state changes).

      Can you either expand on that one or link me to sources that do? I think I follow, but I'd like more info

      • a day ago ago
        [deleted]
      • jjtheblunt 21 hours ago ago

        perhaps the OP is alluding to continuation passing style conversion, q.v.,

        https://en.wikipedia.org/wiki/Continuation-passing_style

      • tpoacher 2 days ago ago

        Not OP, and probably not what he meant, but for me the insight that any for loop can be expressed as a fully equivalent tail-recursive call and vice-versa is what I would describe as my No.3 moment.

        • packetlost 2 days ago ago

          I don't think that's what is being said. The statement is more like 'any imperative program can be represented by a purely functional representation', which goes beyond simply modeling loops with tail call elimination.

      • IsTom 2 days ago ago

        I think OP might be talking about operational or denominational semantics or something isomorphic to them.

        • TuringTest 5 hours ago ago

          Yes, that's the one. Programming theory can describe the runtime execution of any program as a series of rewrite steps of pure mathematical formulas.

          A simple example is temporal logic, when every step in a simulation is defined as a pure function of some sensors plus a parameter with the state of the whole world at the previous step. I think of it as differential equations for logic.

          The realization is when you learn that such style is not limited to temporal logic, rather it can be used for any combination of memory cell assignments (the basis for imperative programs).

      • deterministic a day ago ago

        You can represent any imperative state as a pure value and then "run" an imperative program by doing:

        (i1,s1) = step(i0,s0)

        (i2,s2) = step(i1,s1)

        ...

        (halt,sN) = step(i(N-1),s(N-1))

        where i* is the instruction(s), s* is the state(s) and halt is the "program is done" instruction.

        Think about it as a pure interpreter running an imperative program.

        It is how imperative software is proven correct using pure languages like LEAN.

        • krackers a day ago ago

          I'm not sure if I'm misunderstanding, but isn't this basically the definition of a turing machine?

          • Viliam1234 17 hours ago ago

            "The future state is a deterministic function of the present state" is how computation works in general, and its continuous version is how physics works.

            To get a Turing machine, you need to add one more constraint, which is that things only happen at one place at a time... but that "cursor" itself can (and must, if we want to do something nontrivial) walk across the working memory.

            At the end, the result is the same, it's just that the "future_state = f(current_state)" functional approach allows to e.g. rewrite all ones with zeroes in the entire memory simultaneously, while a Turing machine would have to walk from one end to the other and flip the zeroes one at a time. But if we ignore the time complexity, both approaches allow the same result.

    • amw-zero a day ago ago

      > Third one is when you learn that the behavior of any imperative language (down to the working of the microprocessor data paths) can be fully represented in a pure functional rewrite language (without destructive assignment / cell state changes).

      What no one is ever able to explain is: why is this a good thing?

      The underlying machine does destructive assignment. The whole thing is a big mutable array. Why should we represent it in another way?

      • TuringTest 4 hours ago ago

        > What no one is ever able to explain is: why is this a good thing?

        There's this thing called referential transparency in pure functional languages, which allows you to replace any part of the program with its expanded version - substituting in-place any variable with its current value, and any function call with its body.

        This allows you to analyse and transform the source code of the program as a mathematical formula in a series of steps, like you would do in a mathematical proof. You can't do that in an imperative language (unless you represent it down to the atomic level to the operational behavior of its runtime).

        It may not be the best mental model for implementing the runtime that executes the program, but it's incredibly good for reasoning about the logic of the program itself. This is great for creating very complex software (e. g. with multiple interlocking threads) and demonstrating that it works for all combinations of input data.

        > The underlying machine does destructive assignment.

        My whole OP post was about how that's not the physical reality of the hardware, but a byproduct of the mental model and symbolic language you use to represent its runtime behavior ;-)

        A declarative expression saying "the value of the cell at time t+1 is X" is as valid and accurate as "the cell is assigned to X losing its previous value".

      • snackbroken 19 hours ago ago

        Every tool we bring to bear in programming, from control flow structures to type checking comes down to grappling with the fact that global mutable state is hard to reason about.

        Viewing the CPU as a pure function from "state of the universe before a given clock cycle" to "state of the universe after said clock cycle" is not particularly helpful on its own, because you still need to care about all the state in the universe. What this change in perspective does however, is that it becomes a relatively small change to say "actually this part of the program doesn't care about the whole universe, and doesn't affect the whole resulting universe, only that tiny bit over there matters and only this tiny bit over here changes."

        The win is that the compiler can help keep you honest about handling every possible state you depend on as input and that when you call a function, it doesn't unexpectedly change some state your function depends on behind your back. All the state you ever have to care about when writing (edit: or reasoning about) a pure function is "what are my arguments, and what are the return values of functions I call?"

      • AlotOfReading a day ago ago

        The difficulty of a given problem changes depending on the perspective you're looking at it from. That's why understanding different models helps.

        Optimizing deeply enough will eventually make any abstraction leaky though, so you'll never fully escape mechanical sympathy.

      • seanhunter a day ago ago

        Well one place where I’ve found this useful practically is it makes debugging much easier because you can see the evaluation of values as you step through the program. It’s also afaics the insight behind static single assignment form and all the compiler optimisations that enables https://en.wikipedia.org/wiki/Static_single-assignment_form

      • cowlevel a day ago ago

        The described path is useful for applying mathematical thinking to a program, or for exploring several execution paths at a time (like fuzzing) or executing with backtracking, or other weird things that require seeing the program from a very abstract perspective.

      • naasking a day ago ago

        > Why should we represent it in another way?

        Because different representations have different properties which lets you perform different transformations. All compilers even for imperative languages use some variant of SSA in their intermediate languages, for example.

    • cowlevel a day ago ago

      That's one path, but it's a path that leads away from the machine towards mathematical abstraction. You can also choose the path of mechanical sympathy and learn about things like self-modifying code.

  • artrax 2 days ago ago

    We build this as a c++ library, do to query-compilation for our stream processing engine.

    https://github.com/nebulastream/nautilus

    It allows us to implement operators or functions without having to write them in terms of LLVM IR DSL (or similar). Rather, you write your functions over a wrapper type (and returning one), for which there is an overload of anything which you can overload in c++.

    You can instantiate a wrapper from some c++ value, in which case the wrapper will just forward everything to this value, which was nice for debugging in the preagentic era. But, you can also instantiate such a wrapper as a tracer, and the result of the functions evaluation will be a trace.

    For controlflow, we record whenever a wrapper type is evaluated as a bool, first return true, and when we reach the end of one branch, throw an exception to get back to the beginning, and start all over again, but evaluate it to false.

    The resulting trace we can turn into LLVM IR and compile, or run for example in wasm

  • apignotti 2 days ago ago

    We implemented a similar concept in our C++ -> JavaScript/WebAssembly compiler (Cheerp) several years ago. It was a nice challenge.

    https://labs.leaningtech.com/blog/reducing-webassembly-size-...

  • iFreilicht 2 days ago ago

    Very interesting concept! It reminds me of Hazel (https://hazel.org/) which takes the idea further and into the editor; any program written in it can be partially evaluated, even if variables or even part of the syntax are missing. Missing parts are called "holes", and those are preserved during evaluation so that something like

    abs( + 2 * 3 - 10)

    becomes

    abs( - 4)

    which is great fun. My first attempts using this showed me that if you're not used to this, it actually gets pretty confusing quite quickly, but I guess it can be learned.

    • fmbb 2 days ago ago

      Is that a unary minus denoting a negative number or a binary minus yielding a function with one hole?

      • mrgriffin a day ago ago

        I'm guessing that HN has swallowed some underscores. I've written them as $0 in the below:

        > abs($0 + 2 * 3 - 10)

        > becomes

        > abs($0 - 4)

        • Jtsummers 21 hours ago ago

          Underscores are not swallowed by HN, the only (visible) character that can get stripped out will be *, you need to explicitly escape them in regular paragraphs (in code no escaping is needed) using ** or \*. If it's a lone * surrounded by white space or the only * next to other visible characters, then it will also survive. Otherwise you get italics.

        • Izkata a day ago ago

          For both of you: two spaces of indentation does code formatting, for example:

            abs(_ + 2 * 3 - 10)
          
          https://news.ycombinator.com/formatdoc

          Underscores aren't special in the markup here though, so I'm not sure that's what was intended.

          • a day ago ago
            [deleted]
        • a day ago ago
          [deleted]
      • dullcrisp a day ago ago

        Does it matter?

  • owlstuffing 2 days ago ago

    This type of optimization is also known as compile-time constant expression folding.

    The problem with expanding it to include function calls is that it compromises binary compatibility. A code change on a function that results in a different range or has different side effects, will not be realized unless the caller is recompiled.

    • cogman10 2 days ago ago

      Which is why the second most important optimization of compilers is inlining. If the callee is small enough then hoisting it up into the caller can expose additional optimizations, including noticing that parameters in the caller to the callee are in fact constant.

  • p1necone 2 days ago ago

    All the examples in here look pretty clean, but doesn't partial application like this in practice on "average" codebases result in massive binary size explosion?

    • fjfaase 2 days ago ago

      I once tried this for an interpreting parser I wrote and it resulted in a very large program that took far longer to compile and was also slower than the original interpreter, probably due the code no longer fitting in the processor caches.

  • johntortugo 2 days ago ago

    This seminar explains how GraalVM Truffle uses partial evaluation: https://youtu.be/pksRrON5XfU

  • airtnp 2 days ago ago

    I keep thinking the partial evaluator and Futamura projection application on LLM context.

    Skill => Generic Program LLM skill optimizer => Partial evaluator Context => Env/Input Agent => Interpreter

    First projection: mix(interpreter, program) => specialized skill AOT compiling => offline skill rewriting JIT compiling => runtime specializing, defer loading

    Second projection: mix(mix, interpreter) => Agent/Model specific skill optimizer

    Third projection: mix(mix, mix) => self-improvement skill optimizer

    Whatever maybe I'm just thinking LLM as magic partial evaluator for any tasks

  • 2 days ago ago
    [deleted]
  • measurablefunc 2 days ago ago

    Combining this w/ a JIT gets you truffle/graal.

    • arvyy 2 days ago ago

      truffle is great, it's the most exciting tech in pldev domain to me. I'll just mention truffle has few other perks than just performance boost -- you get a debugger with a fairly small effort, and you get interop with other languages implemented using truffle (which does include fairly mainstream ones like python, js, and others).

      • measurablefunc 2 days ago ago

        I think they have a C interpreter as well so in theory that should allow running python modules that are wrappers for C libraries like sqlite.

    • grashalm 2 days ago ago

      If you are curious how this works in Truffle. Here are some docs:

      https://www.graalvm.org/latest/graalvm-as-a-platform/languag...

  • infogulch 2 days ago ago

    Doesn't Zig have a pretty nice implementation of compile-time evaluation built in?

    • jimmyhmiller 2 days ago ago

      Comptime in zig is definitely quite cool, but not quite the same.

      Consider this example. https://jimmyhmiller.com/split-shot/#/vm

      Make the code a comptime argument in zig and you get "store to comptime variable depends on runtime condition".

      • hansvm 2 days ago ago

        Zig isn't perfect, but I've definitely done this futamura stuff before. It's one of my favourite ways to implement a Forth in Zig (which, incidentally, is the default way that I introduce a backprop library or other DSL as I'm prototyping an idea). Interpreters are dead-simple to write, and I just write an interpreter with a comptime code argument. It definitely works, and the codegen is reasoanble out of the box.

        • speedster217 2 days ago ago

          Thanks for the input! I was thinking about trying this out in Zig. The whole article reminded me of why I was originally excited about comptime

  • dbu21 2 days ago ago

    [dead]