In J, functions have inverses (2012) | Hacker News Reader

In J, functions have inverses (2012)

prog21.dadgum.com

49 pointsrtpg52 comments

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.

[0] Or "using" in C#, for that matter.

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.

Whoops, yeah. Edit button is gone now, boooo.

Reminiscent of Haskell's bracket:

    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

to specialize bracket to specific domains.

Everything becomes neat, tidy, orthogonal, compositional.

The function bracketReadFile is itself a specialization of the library function:

    withFile :: FilePath -> IOMode -> (Handle -> IO r) -> IO r

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.)

It's actually Haskell's `over`. (Not `under`, interestingly)

http://hackage.haskell.org/package/lens-4.12.1/docs/Control-...

Over is similar, but not identical.

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.

That was exactly my thought. The pattern isn't new at all. C++ calls it RAII.

What would be the corresponding context manager for the summing example, where you use the square function and the inverse (the square root) ?

Context managers works well for files (or general relations on objects really) but less for more abstract operations, I've found.

It's ugly

  import math
  
  def sqr(x):
      return x*x
  
  class VecMag:
      def __init__(self, comp):
          self.comp = comp
      def __enter__(self):
          self.comp = map(sqr, self.comp)
          return self
      def __exit__(self, type, value, traceback):
          print  math.sqrt(self.mag)
      def sum(self):
          self.mag = sum(self.comp)
  
  comp = (1,2,3,4)
  with VecMag(comp) as squared:
      squared.sum()

  $python test.py
  5.47722557505

Looks about right to me. And in Ruby, the same general pattern is implemented with blocks:

    File.open("foo.txt", 'w') {|f| f.write("bar")}

(2012)

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.)

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.

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)

This is actually a very well known best practice in C++, so common that it has an acronynm RAII: https://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initia...

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).

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.

...and I should have said that you can replace the above by:

S \ R

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?

In math this is often called "conjugation". It's also sometimes called "commutation".

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.

I'm happy saying "file-writing conjugated by putting-a-file-into-scope".

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.)

That makes more sense.

under sounds like with in Python, e.g.

    with open('workfile', 'r') as f:
        read(f)

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].

1 - http://www.worldwizzy.com/library/Natural_transformation

2 - https://en.wikipedia.org/wiki/Endomorphism

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].

[1] http://www.cis.upenn.edu/~bcpierce/papers/lenses-etapsslides...

[2] http://www.janis-voigtlaender.eu/papers/ThreeComplementaryAp...

[3] https://github.com/ekmett/lens

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.

1 - https://wiki.haskell.org/Applicative_functor

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.

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.

http://edgeguides.rubyonrails.org/active_record_migrations.h...

> > Database schema migrations are one obvious place where the idea of reversibility is useful...

A framework agnostic tool for addressing this concern is:

https://mybatis.github.io/migrations/

For managing RDBMS schemas, it is very impressive IMHO.

Most interesting part of this is that you can link functions together in the following fashion: http://www.jsoftware.com/jwiki/Vocabulary/codot

I'm not a J expert; does anyone know if there are any other functions like this in the language?

Reminds me of Python's "with". I use it a lot for the "open the file, read, close it" idiom.

There's a beautiful example of this in the J implementation of continuous knapsack on Rosetta Code: http://rosettacode.org/wiki/Knapsack_problem/Continuous#J

Awesome pattern matching. Although, it seems like not all functions are intuitively reversible like the vector example given here.

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.

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.

This is extremely common in mathematics: To do something in domain A, convert to domain B, do it there, and convert back to domain A.

Example: a*b = exp(log(a)+log(b)).

There are many diagrams in math fields that show exactly this.

Sure. What's the inverse function of:

F(X) = X%2

Of course, not all function is invertible. The exact rule is described at: http://www.jsoftware.com/help/dictionary/d202n.htm

Python "with", C++ RAII (and ADA, D, Rust, and Vala).

This is hardly a new concept.

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.

Thx for the correction. Point understood.

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

Which is just a small subset of what he talks about.

Even the specific example he gives is NOT about recourse management (which is what the things you mention do).

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.

You missed the part where the reverse operation is inferred automatically -- not just written explicitly to run in the end.

Reply on news.ycombinator.com