Hacker News
The Magic of Partial Evaluation
TuringTest
|next
[-]
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
|root
|parent
|next
[-]
Can you either expand on that one or link me to sources that do? I think I follow, but I'd like more info
tpoacher
|root
|parent
|next
|previous
[-]
deterministic
|root
|parent
|next
|previous
[-]
(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
|root
|parent
[-]
Viliam1234
|root
|parent
[-]
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.
jjtheblunt
|root
|parent
|next
|previous
[-]
IsTom
|root
|parent
|previous
[-]
TuringTest
|root
|parent
[-]
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).
amw-zero
|root
|parent
|next
|previous
[-]
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?
snackbroken
|root
|parent
|next
[-]
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?"
TuringTest
|root
|parent
|next
|previous
[-]
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".
cowlevel
|root
|parent
|next
|previous
[-]
naasking
|root
|parent
|next
|previous
[-]
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.
AlotOfReading
|root
|parent
|next
|previous
[-]
Optimizing deeply enough will eventually make any abstraction leaky though, so you'll never fully escape mechanical sympathy.
seanhunter
|root
|parent
|previous
[-]
artrax
|next
|previous
[-]
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
|next
|previous
[-]
https://labs.leaningtech.com/blog/reducing-webassembly-size-...
iFreilicht
|next
|previous
[-]
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
|root
|parent
[-]
mrgriffin
|root
|parent
|next
[-]
> abs($0 + 2 * 3 - 10)
> becomes
> abs($0 - 4)
Jtsummers
|root
|parent
|next
[-]
Izkata
|root
|parent
|next
|previous
[-]
abs(_ + 2 * 3 - 10)
https://news.ycombinator.com/formatdocUnderscores aren't special in the markup here though, so I'm not sure that's what was intended.
owlstuffing
|next
|previous
[-]
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.
measurablefunc
|next
|previous
[-]
arvyy
|root
|parent
|next
[-]
grashalm
|root
|parent
|previous
[-]
https://www.graalvm.org/latest/graalvm-as-a-platform/languag...
johntortugo
|next
|previous
[-]
p1necone
|next
|previous
[-]
airtnp
|next
|previous
[-]
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
infogulch
|next
|previous
[-]
jimmyhmiller
|root
|parent
[-]
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".