Modules as Stateful Blackboxes
Much of Cat research has focused on pure Cat programs. At one point a non-trivial program is going to have to deal with the issue of side-effects.
In Cat all functions with side-effects or that are not referentially transparent are called “impure” and are labeled with “~>” instead of “->”. This is a very general meaning of “~>” which could be refined. I am experimenting with the idea that “~>” carries with it an attachment to a particular module. Modules would be stateful blackbox components of a Cat program. For example: input, output, console, instruction sequence, random number generation, date-time query, network sockets, file system, pipes, etc. Each module would be treated as a new type that is monitored by the type system and attached to the squiggle-arrow. What is relevant for me is that certain modules are hard-linked and others are completely unlinked.
Let’s say I have two modules: A and B. If they are unlinked then any code that affects A must be sequenced in order, and any code that affects B must be sequenced in relative order, but the mutual order is unimportant. Consider the following example:
define fA : ( ~> ) { A.f }
define gA : ( ~> ) { A.g }
define fB : ( ~> ) { B.f }
define gB : ( ~> ) { B.g }
define test : ( ~> ) { A.f A.g B.f B.g }
The following rewrite would be illegal:
define test : ( ~> ) { A.g A.f B.g B.f } // no good
However the following rewrite would be legal:
define test : ( ~> ) { A.f B.f A.g B.g } // good
This is not implemented yet, but looks very much like a direction I want to take Cat.
Hi, this sounds good, in fact I had a similar idea for Mog where, initially, the optimiser must not reorder functions that are not pure.
Later this could be refined by associating with every impure function a node of a DAG, and relax the reordering restriction such that two impure functions can be reordered iff they do not have a common ancestor in the DAG (perhaps trees would be sufficient).
Comment by Colin — June 22, 2007 @ 12:55 pm
This is a very good idea. One problem is that relationships behind modules are not exposed to the system (yet). What is needed is some way to express interdependencies between modules in order to draw the graph. This would require some kind of module declaration syntax, and would make for a very sophisticated type system of effects.
This is a very deep and rich area for exploration. Hopefully some simple solution will reveal itself.
I have this suspicion though that module based effect systems have already been invented, but I it is only a feeling, so any pointers to related research would be welcome.
Comment by cdiggins — June 23, 2007 @ 6:53 pm