3 ms·

To me the most interesting part of this article is the part that nobody else seems to be commenting on: the ability to automatically invert a function, even a p

by rntz 9y ago

To me the most interesting part of this article is the part that nobody else seems to be commenting on: the ability to automatically invert a function, even a programmer-defined function. That seems magical! What if I define a hash function? How can it possibly invert that? Clearly there's something interesting going on behind the scenes, and I wish the article discussed what it is, and how (and when) it works. Everything else in the article seems like plain old functional programming to me, with a little syntax sugar here and there.

evincarofautumn 9y ago
The only other language where I’ve seen this is Factor, with its “undo” word. I presume they work similarly, so I can speak to the general idea. It’s not that the compiler can invert a hash, or automatically derive a logarithm function from an exponentiation function, or anything like that. Essentially, if you have a composition of functions in a “pipeline” (h ∘ g ∘ f): [ f g h ] Then to get the inverse of the composition, you just invert each function and reverse the whole thing (f⁻¹ ∘ g⁻¹ ∘ h⁻¹): [ f g h ] undo [ \ h undo \ g undo \ f undo ] “undo” is defined for a set of primitive words. If there isn’t an inverse defined for some function you used in the composition, then it fails; however, you can just define a custom inverse for your function. And obviously this relies on having some kind of reified representation of functions available. “undo” can be used for things like pattern-matching: a destructuring function, which takes some value and produces its fields, is the inverse of a constructor, which takes the fields and constructs a value.
yorwba 9y ago
You could do something similar in "normal" functional programming languages, but you usually won't get the nice syntax. Basically, you can represent each invertible function by a pair of functions (pseudo-Haskell, because I don't use it very often and can't test on mobile): data Invertible a b = Invertible { forward :: a, backward :: b } apply :: Invertible (a -> b) (b -> a) -> a apply f a = forward f a invert :: Invertible (Invertible a b -> Invertible b a) (Invertible b a -> Invertible a b) invert = Invertible { forward = invert', backward = invert'} where invert' :: Invertible a b -> Invertible b a invert f = Invertible { forward = backward f, backward = forward f} Then you can for example invert invert itself by apply invert invert == invert But because there is no built-in language support, you'll end up doing lots of parallel construction of the standard library before you can even think of using it productively. Apparently someone already did that for Haskell (https://hackage.haskell.org/package/invertible https://hackage.haskell.org/package/invertible), but it likely doesn't cover everything.

by rntz 9y ago

evincarofautumn 9y ago

The only other language where I’ve seen this is Factor, with its “undo” word. I presume they work similarly, so I can speak to the general idea. It’s not that the compiler can invert a hash, or automatically derive a logarithm function from an exponentiation function, or anything like that. Essentially, if you have a composition of functions in a “pipeline” (h ∘ g ∘ f): [ f g h ] Then to get the inverse of the composition, you just invert each function and reverse the whole thing (f⁻¹ ∘ g⁻¹ ∘ h⁻¹): [ f g h ] undo [ \ h undo \ g undo \ f undo ] “undo” is defined for a set of primitive words. If there isn’t an inverse defined for some function you used in the composition, then it fails; however, you can just define a custom inverse for your function. And obviously this relies on having some kind of reified representation of functions available. “undo” can be used for things like pattern-matching: a destructuring function, which takes some value and produces its fields, is the inverse of a constructor, which takes the fields and constructs a value.

yorwba 9y ago

You could do something similar in "normal" functional programming languages, but you usually won't get the nice syntax. Basically, you can represent each invertible function by a pair of functions (pseudo-Haskell, because I don't use it very often and can't test on mobile): data Invertible a b = Invertible { forward :: a, backward :: b } apply :: Invertible (a -> b) (b -> a) -> a apply f a = forward f a invert :: Invertible (Invertible a b -> Invertible b a) (Invertible b a -> Invertible a b) invert = Invertible { forward = invert', backward = invert'} where invert' :: Invertible a b -> Invertible b a invert f = Invertible { forward = backward f, backward = forward f} Then you can for example invert invert itself by apply invert invert == invert But because there is no built-in language support, you'll end up doing lots of parallel construction of the standard library before you can even think of using it productively. Apparently someone already did that for Haskell (https://hackage.haskell.org/package/invertible https://hackage.haskell.org/package/invertible), but it likely doesn't cover everything.