A complete general implementation requires some kind of static notion of an "inverse", which is hard in turing complete languages. But really this is quite a bit like RAII for a lot of practical applications.
Yeah, RAII helps encapsulate this pretty well at least for the object case, but the notion of having an "inverse" operation is useful in many other situations.
An example I've run into a lot is wanting a generalized "toggle" for DOM actions in javascript (for example, show/hide), so if some property is true, I apply a transformation, and when the property is switched off I can apply the reverse easily.
The trickiness with RAII (or things like context managers in python) is that it mainly works when you have a companion object representing the action (files are the companion object to getting handlers through opening/closing for example). But what is the object you could use for scaling?
You can, of course, build a Scaler object (or MultiplierFactory ;) ), but I find myself wanting to avoid objects and methods to instead go for plain functions as much as possible.
> A complete general implementation requires some kind of static notion of an "inverse", which is hard in turing complete languages.
I don't think it's Turing completeness that's the issue (though it is an issue, of course) so much as non-invertibility. (I've always been fascinated by https://en.wikipedia.org/wiki/Reversible_computing , but it doesn't seem, at least to my limited perspective, like it's the subject of much current research.) For example, what should the inverse of `(^2) :: Complex -> Complex` be?
Isn't what he's describing very similar to the "with" statement in Python? You can define a context manager to use with "with" that has methods that get executed on the entry and exit of the "with" block, e.g., to open/close a file or acquire/release a lock.
Yeah. it's not new.
basically every programming language that respects itself has it in the form of:
- with blah do x
- using blah do x
- try(blah) { do x }
- File.open(blah, 'w') {|f| f.write(x) }
- there are even GCC C complier extension to hook in behavior like this
It's all over the place. Everything is new and old at the same time
One of the things he suggests is resource management, though, the file example. It would also be trivial to implement his vector sum example with syntactic sugar designed for resource management. E.g. in Java's try with you would just square in the constructor of something that implements closeable, sum in the try-with block, then square root in the close method. Ruby is even easier since you would just pass a block into a method and the method could do pre and post operations before running the block. In both cases these things are usually used for resource management, but they can easily be used for this.
Some commenters are pointing out that this is similar to "with" in Python.[0] At first glance - and using the example given of reading from a file - that may be true, but consider the final example given in the article. The Pythonic way to calculate the magnitude is something like:
math.sqrt(sum((i**2 for i in numbers)))
Using "with" to calculate a magnitude would be tortuous at best and it certainly wouldn't result in idiomatic code.
The point of the article is to illustrate the idiom: perform operation A, then operation B, then the inverse of operation A. "with open(foo)" or "using (foo)" implements that idiom in certain, specific cases, but not in the general case which seems to be what J implements.
I think the issue here is that the article is talking about two things: a common resource management idiom, and the cool fact that `under(f, g) = f^1 * g * f` implements it.
`with` implements this idiom just fine, too, but `under` is a more general solution that can solve even more problems, if you're willing to be a bit more careful about `f` and `g`.
In the Read/Open case, for example, it looks like Read must return both the read result and the file handle, and Open^-1 must take the read result as input and forward it back out as output. Feasible, but unintuitive for the implementers.
If we were actually implementing this resource management idiom, I'm not sure we would use `under`, even though we could. If we want to write `f`, `f^-1`, and `g` with the more natural `with` semantics, it's clearer to define our own metafunction from scratch: `with(f, g)(x) = (g(f_result), f^-1(f_result)) where f_result = f(x)`.
edit: The follow-up post actually touches on how Read/Open really isn't a great example of `under`. Interesting. http://prog21.dadgum.com/122.html
In J, you can square a vector and get a vector of the squared entries. So "sum under square" really is doing "sqrt(sum(square(vector)))", and more generally "(a under b) x" does "b^-1(a(b(x)))".
Mm, I thought that might be what's up, but had no clue how J actually works xD Thanks!
Even without the mapping wrinkle, though, this is definitely a deviation from the examples the article provides: instead of unsquaring the vector we initially squared, we unsquare the sum.
> I think the issue here is that the article is talking about two things: a common resource management idiom, and the cool fact that `under(f, g) = f^1 * g * f` implements it.
I think that your pseudo-code for `under` should start with `f^(-1)` (as in the fourth paragraph); probably `f^1` is just a typo.
I would compare this less to with, and more to Lisp setf, or possibly a lens. Basically, the idea that when you're writing the function, you also write the dual of the function, so that meta-functions (like with) can automatically map the function to its dual (like mapping a getter to the equivalent setter, etc.)
The concept of transactions, whether it be database transactions or software transactional memory, are kind of like this. At some point if something goes wrong you need to know how to un-do all of what you've done-so-far.
We added the date to the title. We also changed the title (with its linkbait 'you') to a representative phrase from the article. We can change it again if anyone suggests a better.
Database schema migrations are one obvious place where the idea of reversibility is useful (although there's not really a "do something in the middle" step). ActiveRecord migrations (used in Ruby on Rails) have a way to define a reversible process, and they include reversible calls for basic things like creating a table or adding a column.
bracket :: IO a -- computation to run first ("acquire resource")
-> (a -> IO b) -- computation to run last ("release resource")
-> (a -> IO c) -- computation to run in-between
-> IO c
And because of the order of parameters, one may write e.g.
bracketReadFile :: FilePath -> (Handle -> IO c) -> IO c
bracketReadFile fname = bracket (openFile fname ReadMode) hClose
If you have posters of Adele Goldberg and Alan Kay in your bedroom, your bedsheets have the Smalltalk spec printed on them, you make an offering to the church of OOP every morning, and you want to push things to the max, you can do that by modeling all your functions as objects and implementing the doing/undoing in the constructor/destructor :3
(I do not advise actually doing this for anything besides being silly on HN)
Sure, but you probably shouldn't model the power function as an object (and philosophically, the point of RAII is resource management, not getting function inverses).
I came here to say the same thing. In a sentence, you might say "X is conjugated by Y", although "file-writing conjugated by file opening" sounds a bit odd. If an operation X is unchanged by conjugation of an operation Y, you say Y commutes with X.
This is also found in the Ruby hardware description language (not the same as the scripting language). A commonly-occurring pattern is:
R^~1 ; S ; R
where R and S are functions, ';' is composition ('.' in Haskell) and '^~1' is inverse. Usually this is for wiring (change order or grouping of wires to suit block S).
The wrinkle in Ruby is that R and S can be relations, not just functions, so data can flow both ways, just like actual hardware (can only flow from right to left in Haskell). Ruby won't try to guess the obverse function, unlike J.
None of these will apply a square to N items, and then the inverse (square root) to the sum of those squares.
This is really more like map-reduce, with an additional inverse step deduced from the inverse of the function that is used for the map step.
With map-reduce, we can map all the inputs individually through a square function, and then reduce with +. Okay, that brings us to sum of squares. "Under" adds one more step: to "undo" the squaring with a square root, and without being explicitly given the square root function.
If we have a zoo of functions that are all associated with inverses, we can roll this into a single operation. Say a functional combinator under(T, P) which takes a processing function P (which takes one or more arguments) and a transforming function T (one argument), and produces a new function F which is of the same arity as P, such that F(a, b, c, ...) calculates T_inverse(P(T(a), T(b), T(c), ...)).
The we have under(square, sum)(1, 2, 3) to take the norm of 1, 2 and 3.
At first, I thought (like many others) the author was speaking about a syntactic convenience for the template method pattern.
Reading various responses and closer inspection of the article made me realize that it seems what is described is more along the lines of a Natural Transformation[1] where the functors are endomorphic[2].
The author seems to be getting at something very similar to the notion of "bidirectional programming" [1][2]. It's a concept that's closely related to the indispensable "lens" library in Haskell [3].
While I definitely see your point of the concept being closely related to lenses, a key differentiator to me is the incorporation of invoking a functor with the "read part" of a lens and then submitting the result to the "write part."
It's almost like a marriage of Applicative Functor[1] with Lens in a squint-your-eyes-and-tilt-your-head kind of way.
A natural transformation between endofunctors? How exactly? That's just a family of functions
µ : F(x) -> G(x)
such that for all (f : x -> y), (F(f);µ == µ;G(f)). I don't see how that's capturing anything interesting here. If µ were a natural isomorphism with inverse µ- then there'd be laws like (F(f) == µ;G(f);µ-), but this exactly involves introducing an inverse so the natural transformation didn't buy much.
I thought of endofunctors due to morphisms remaining in the same domain (satisfying the homogeneous domain/codomain requirement of natural transformations), though perhaps a better description would have been to constrain the functors to injective arrows instead.
57 comments
[ 5.4 ms ] story [ 62.0 ms ] threadAn example I've run into a lot is wanting a generalized "toggle" for DOM actions in javascript (for example, show/hide), so if some property is true, I apply a transformation, and when the property is switched off I can apply the reverse easily.
The trickiness with RAII (or things like context managers in python) is that it mainly works when you have a companion object representing the action (files are the companion object to getting handlers through opening/closing for example). But what is the object you could use for scaling?
You can, of course, build a Scaler object (or MultiplierFactory ;) ), but I find myself wanting to avoid objects and methods to instead go for plain functions as much as possible.
I don't think it's Turing completeness that's the issue (though it is an issue, of course) so much as non-invertibility. (I've always been fascinated by https://en.wikipedia.org/wiki/Reversible_computing , but it doesn't seem, at least to my limited perspective, like it's the subject of much current research.) For example, what should the inverse of `(^2) :: Complex -> Complex` be?
Context managers works well for files (or general relations on objects really) but less for more abstract operations, I've found.
Even the specific example he gives is NOT about recourse management (which is what the things you mention do).
The point of the article is to illustrate the idiom: perform operation A, then operation B, then the inverse of operation A. "with open(foo)" or "using (foo)" implements that idiom in certain, specific cases, but not in the general case which seems to be what J implements.
[0] Or "using" in C#, for that matter.
`with` implements this idiom just fine, too, but `under` is a more general solution that can solve even more problems, if you're willing to be a bit more careful about `f` and `g`.
In the Read/Open case, for example, it looks like Read must return both the read result and the file handle, and Open^-1 must take the read result as input and forward it back out as output. Feasible, but unintuitive for the implementers.
If we were actually implementing this resource management idiom, I'm not sure we would use `under`, even though we could. If we want to write `f`, `f^-1`, and `g` with the more natural `with` semantics, it's clearer to define our own metafunction from scratch: `with(f, g)(x) = (g(f_result), f^-1(f_result)) where f_result = f(x)`.
edit: The follow-up post actually touches on how Read/Open really isn't a great example of `under`. Interesting. http://prog21.dadgum.com/122.html
Even without the mapping wrinkle, though, this is definitely a deviation from the examples the article provides: instead of unsquaring the vector we initially squared, we unsquare the sum.
I think that your pseudo-code for `under` should start with `f^(-1)` (as in the fourth paragraph); probably `f^1` is just a typo.
It seems like perhaps a more pragmatic example of this syntax is the "with" syntax in python, which provides the same benefit with more flexibility.
Previously: https://news.ycombinator.com/item?id=3422654
Don't forget to read the followup: http://prog21.dadgum.com/122.html
(and yet, people are still misunderstanding it.)
http://edgeguides.rubyonrails.org/active_record_migrations.h...
A framework agnostic tool for addressing this concern is:
https://mybatis.github.io/migrations/
For managing RDBMS schemas, it is very impressive IMHO.
Everything becomes neat, tidy, orthogonal, compositional.
The function bracketReadFile is itself a specialization of the library function:
which also builds on top of bracket in the same way. See https://hackage.haskell.org/package/base-4.8.1.0/docs/src/Sy...(Yes, I'm perfectly aware of the wrinkles that Lazy I/O causes. Assume the above are the strict equivalents.)
http://hackage.haskell.org/package/lens-4.12.1/docs/Control-...
(I do not advise actually doing this for anything besides being silly on HN)
Example: a*b = exp(log(a)+log(b)).
There are many diagrams in math fields that show exactly this.
R^~1 ; S ; R
where R and S are functions, ';' is composition ('.' in Haskell) and '^~1' is inverse. Usually this is for wiring (change order or grouping of wires to suit block S).
The wrinkle in Ruby is that R and S can be relations, not just functions, so data can flow both ways, just like actual hardware (can only flow from right to left in Haskell). Ruby won't try to guess the obverse function, unlike J.
S \ R
This is hardly a new concept.
This is really more like map-reduce, with an additional inverse step deduced from the inverse of the function that is used for the map step.
With map-reduce, we can map all the inputs individually through a square function, and then reduce with +. Okay, that brings us to sum of squares. "Under" adds one more step: to "undo" the squaring with a square root, and without being explicitly given the square root function.
If we have a zoo of functions that are all associated with inverses, we can roll this into a single operation. Say a functional combinator under(T, P) which takes a processing function P (which takes one or more arguments) and a transforming function T (one argument), and produces a new function F which is of the same arity as P, such that F(a, b, c, ...) calculates T_inverse(P(T(a), T(b), T(c), ...)).
The we have under(square, sum)(1, 2, 3) to take the norm of 1, 2 and 3.
I'm not a J expert; does anyone know if there are any other functions like this in the language?
F(X) = X%2
Reading various responses and closer inspection of the article made me realize that it seems what is described is more along the lines of a Natural Transformation[1] where the functors are endomorphic[2].
1 - http://www.worldwizzy.com/library/Natural_transformation
2 - https://en.wikipedia.org/wiki/Endomorphism
[1] http://www.cis.upenn.edu/~bcpierce/papers/lenses-etapsslides...
[2] http://www.janis-voigtlaender.eu/papers/ThreeComplementaryAp...
[3] https://github.com/ekmett/lens
It's almost like a marriage of Applicative Functor[1] with Lens in a squint-your-eyes-and-tilt-your-head kind of way.
1 - https://wiki.haskell.org/Applicative_functor