Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Nilang.jl – A Reversible Julia DSL

github.com

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Nilang.jl – A Reversible Julia DSL

#21

Post by GiggleLiu »

e12e wrote: post #6
choeger wrote: post #4

Wait a second, does it yield an exact inverse or a numerical approximation?

Given the example of reversing over a function that calculates the first Fibonacci number greater than 100, it seems to be a bit more going on than "just" a numerical approximation: https://github.com/GiggleLiu/NiLang.jl/blob/master/examples/... Ed: after skimming the paper (that went mostly over my head) - this does indeed seem to be about "actually" running functions in reverse - given a function only defined "forw…

Graph embedding example is not missing, it in the appendix of the paper's master branch: https://github.com/GiggleLiu/nilangpaper/blob/master/invc.pd...

The source code is available here: https://github.com/JuliaReverse/NiGraphEmbedding.jl

Re: Nilang.jl – A Reversible Julia DSL

#22

Post by thisrod »

snicker7 wrote: post #2

Incredible. Given a (one-to-one) Julia function `f`, this package generates `~f`, the inverse of f. Clever use of automatic differentiation. Paper: https://arxiv.org/abs/2003.04617

That can't be entirely true. There must be some kind of continuous, convex or monotonic precondition on f. Something to stop me from implementing a cryptographic hash function, and asking for the solution to a 10000 bit challenge that is supposed to require a trillion times Earth's entire computing resources running for a million years.

Or maybe it's impossible to implement that hash function reversibly without preserving a copy of the input in the output.

Re: Nilang.jl – A Reversible Julia DSL

#23

Post by ChrisRackauckas »

cbkeller wrote: post #15
vsskanth wrote: post #11

How does this compare to zygote ?

As far as I understand it (which is not very far): Zygote calculates derivatives using source-to-source automatic differentiation. This calculates function inverses (so to stretch the analogy a bit, it's kinda like "source-to-source automatic inversion ")

Not necessarily: you can use it to build fast inverse of scalar functions. Here's an example on a vjp of an ODE f:

https://gist.github.com/GiggleLiu/0c4608f70bda050f59992f5fc0...

Re: Nilang.jl – A Reversible Julia DSL

#24

Post by cbkeller »

ChrisRackauckas wrote: post #23
cbkeller wrote: post #15

Earlier quoted context omitted.

As far as I understand it (which is not very far): Zygote calculates derivatives using source-to-source automatic differentiation. This calculates function inverses (so to stretch the analogy a bit, it's kinda like "source-to-source automatic inversion ")

Not necessarily: you can use it to build fast inverse of scalar functions. Here's an example on a vjp of an ODE f: https://gist.github.com/GiggleLiu/0c4608f70bda050f59992f5fc0...

I'm probably just missing something, but did you mean to say "fast derivatives of scalar functions" by any chance? I.e., that you can use the free inverses to get at the derivatives in some way?

Re: Nilang.jl – A Reversible Julia DSL

#25

Post by ChrisRackauckas »

cbkeller wrote: post #24
ChrisRackauckas wrote: post #23

Earlier quoted context omitted.

Not necessarily: you can use it to build fast inverse of scalar functions. Here's an example on a vjp of an ODE f: https://gist.github.com/GiggleLiu/0c4608f70bda050f59992f5fc0...

I'm probably just missing something, but did you mean to say "fast derivatives of scalar functions" by any chance? I.e., that you can use the free inverses to get at the derivatives in some way?

oh yes, I meant derivatives.

Re: Nilang.jl – A Reversible Julia DSL

#26

Post by cbkeller »

thisrod wrote: post #22
snicker7 wrote: post #2

Incredible. Given a (one-to-one) Julia function `f`, this package generates `~f`, the inverse of f. Clever use of automatic differentiation. Paper: https://arxiv.org/abs/2003.04617

That can't be entirely true. There must be some kind of continuous, convex or monotonic precondition on f. Something to stop me from implementing a cryptographic hash function, and asking for the solution to a 10000 bit challenge that is supposed to require a trillion times Earth's entire computing resources running for a million years. Or maybe it's impossible to implement that hash function reversibly without prese…

I think it's a variant of the latter -- IIUC no information can be "lost" in reversible computing, so the output of a reversible hash function might be both the hash and some number of other outputs, all of which you would have to know if you wanted to reverse the hash function.

It seems there is an analogy to be drawn to the way in which there can be no "waste heat" in a reversible thermodynamic process [1]. I thought this analogy might be a bit of a stretch at first, but looking into this a bit more it seems as though this is indeed exactly the idea with reversible computing, such that if a reversible computer could be implemented at the hardware level there would supposedly be significant energy efficiency gains on the table [2-4].

[1] https://en.wikipedia.org/wiki/Reversible_process_%28thermody...

[2] https://arxiv.org/abs/1702.08715

[3] https://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/INC19-...

[4] https://spectrum.ieee.org/computing/hardware/the-future-of-c...

Re: Nilang.jl – A Reversible Julia DSL

#27

Post by cbkeller »

sriku wrote: post #9
dlivingston wrote: post #5

Earlier quoted context omitted.

Forgive my ignorance, but what applications would this be used in where just maintaining copies of the initial parameters to f() wouldn’t work?

Very interesting. Not read the paper yet, but plan to. Reversibility is important in quantum computing. Quantum circuits must transform input to output in a "unitary" manner, which is reversible. If you consider the input to output as a linear transformation matrix (with complex values), then the complex conjugate of the matrix gives the "inverse function". This is probably useless info, but reversibility in the clas…

I was wondering about this latter point as well, and apparently this is exactly the goal if one could implement reversible computing at the hardware level [1]:

> One of the earliest proposals to reduce heat from lost bits was to make computer circuits reversible. A reversible circuit has exactly as many outputs as inputs, assigning one output pattern to every input pattern and vice versa. That means each input can be reconstructed from the output; no bits are lost, so reversible circuits will not give off heat from bit loss. Furthermore, reversible circuits can simulate standard logic functions and can therefore be used in any computer.

[1] https://www.americanscientist.org/article/computers-that-can...

Re: Nilang.jl – A Reversible Julia DSL

#28

Post by jlokier »

thisrod wrote: post #22
snicker7 wrote: post #2

Incredible. Given a (one-to-one) Julia function `f`, this package generates `~f`, the inverse of f. Clever use of automatic differentiation. Paper: https://arxiv.org/abs/2003.04617

That can't be entirely true. There must be some kind of continuous, convex or monotonic precondition on f. Something to stop me from implementing a cryptographic hash function, and asking for the solution to a 10000 bit challenge that is supposed to require a trillion times Earth's entire computing resources running for a million years. Or maybe it's impossible to implement that hash function reversibly without prese…

> Or maybe it's impossible to implement that hash function reversibly without preserving a copy of the input in the output.

Cryptographic hash functions rely on locally non-reversible non-linear operations.[1]

So you don't need to copy the original input, but you will need to copy bits here and there throughout the hash function, which allow the input to be reconstructed.

But that's not surprising, even a humble AND gate is non-reversible. So even a humble AND gate program will need to copy its inputs to the output if it's to be reversible.

[1] (As well, cryptographic hash functions are generally not reversible anyway. As in, different inputs hash to the same output value, so there's no unambiguous reversal.)

Re: Nilang.jl – A Reversible Julia DSL

#29

Post by thisrod »

jlokier wrote: post #28
thisrod wrote: post #22

Earlier quoted context omitted.

That can't be entirely true. There must be some kind of continuous, convex or monotonic precondition on f. Something to stop me from implementing a cryptographic hash function, and asking for the solution to a 10000 bit challenge that is supposed to require a trillion times Earth's entire computing resources running for a million years. Or maybe it's impossible to implement that hash function reversibly without prese…

> Or maybe it's impossible to implement that hash function reversibly without preserving a copy of the input in the output. Cryptographic hash functions rely on locally non-reversible non-linear operations.[1] So you don't need to copy the original input, but you will need to copy bits here and there throughout the hash function, which allow the input to be reconstructed. But that's not surprising, even a humble AND…

> So even a humble AND gate program will need to copy its inputs to the output if it's to be reversible.

It's been 20 years since I had to think closely about reversible computing, and I've forgotten lots of the details. When I said "implement a hash function", I actually meant "implement exclusive-or with the result of the hash function" or something similar.

> As well, cryptographic hash functions are generally not [invertible] anyway.

Good point. But aren't there one-to-one equivalents, called one-way functions, trapdoor functions or something like that? My cryptography is even rustier.

Re: Nilang.jl – A Reversible Julia DSL

#30

Post by jlokier »

thisrod wrote: post #29
jlokier wrote: post #28

Earlier quoted context omitted.

> Or maybe it's impossible to implement that hash function reversibly without preserving a copy of the input in the output. Cryptographic hash functions rely on locally non-reversible non-linear operations.[1] So you don't need to copy the original input, but you will need to copy bits here and there throughout the hash function, which allow the input to be reconstructed. But that's not surprising, even a humble AND…

> So even a humble AND gate program will need to copy its inputs to the output if it's to be reversible. It's been 20 years since I had to think closely about reversible computing, and I've forgotten lots of the details. When I said "implement a hash function", I actually meant "implement exclusive-or with the result of the hash function" or something similar. > As well, cryptographic hash functions are generally not…

> It's been 20 years since I had to think closely about reversible computing, and I've forgotten lots of the details. When I said "implement a hash function", I actually meant "implement exclusive-or with the result of the hash function" or something similar.

Well that gets a bit more interesting. If the hash is of a key K, and the hash output is exclusive-or'd with input M, then of course it's reversible with respect to M but not K.

You can think of the above as an easily reversible program with M as its only input. (If K is treated as a constant, then it's just part of the program.).

In that case, yes you can make an efficiently reversible version in Nilang.jl, and it will have all the differentiability properties etc.

But it will only have those properties under the assumption of holding K constant. The new program won't resemble the stated problem of inverting a cryptographic hash :-)

In general there will be some parts of a program which are reversible without needing to record any state, and other parts where you have to retain some state (or generally a function of the state, which might be less overhead) in order to make the whole thing reversible.

Quantum computers face this problem too. Every quantum program is fully reversible, but you can't copy qubits, so you can't translate a classical non-reversible program to quantum by retaining copies of state as described above. You have to do stranger things to translate the program.

The fact you can actually do that shows that recording internal states isn't the only way to make a program reversible. But the fact it takes exponential time to simulate the resulting program on a classical computer shows that the alternative doesn't let you invert a cryptographic hash that easily either :-)

> But aren't there one-to-one equivalents, called one-way functions, ...

In general one-way functions map multiple inputs to the same output, so they aren't reversible.

You're thinking of a rarer kind called one-way permutations.

There aren't many of these around, and they aren't what is generally intended when talking about a cryptographic hash. It would be convenient if hashes were permutations, but they generally aren't.

Post reply on HN