> 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.
> 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
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.
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.
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).
"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.
> 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?
> 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".
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?"
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
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.
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.
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.
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
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.
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.
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.
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.
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?
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.
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).
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.
> 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.
> 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
perhaps the OP is alluding to continuation passing style conversion, q.v.,
https://en.wikipedia.org/wiki/Continuation-passing_style
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.
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.
I think OP might be talking about operational or denominational semantics or something isomorphic to them.
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).
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.
I'm not sure if I'm misunderstanding, but isn't this basically the definition of a turing machine?
"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.
> 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?
> 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".
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?"
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.
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
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.
> 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.
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.
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
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-...
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.
Is that a unary minus denoting a negative number or a binary minus yielding a function with one hole?
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)
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.
For both of you: two spaces of indentation does code formatting, for example:
https://news.ycombinator.com/formatdocUnderscores aren't special in the markup here though, so I'm not sure that's what was intended.
Does it matter?
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.
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.
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?
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.
This seminar explains how GraalVM Truffle uses partial evaluation: https://youtu.be/pksRrON5XfU
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
Combining this w/ a JIT gets you truffle/graal.
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).
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.
If you are curious how this works in Truffle. Here are some docs:
https://www.graalvm.org/latest/graalvm-as-a-platform/languag...
Doesn't Zig have a pretty nice implementation of compile-time evaluation built in?
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".
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.
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
[dead]