Skip to content

being and doing and ports and pegs

February 28, 2015

I’ve been thinking…

…about components of computations. A component *does* something, given i inputs, to produce o outputs. That is, a component has i ports and o pegs, ordered spatially “left-to-right”, and I shall think of data flowing downward, into ports at the top and out from pegs at the bottom. When working one dimensionally, I’ll put top on the right and bottom on the left, as per usual with functional notation, and I’ll be a Bird-style rebel about types. Suppose I have two components, o0 <- c0 i0 and o1 = x.

Now define o0 + (o1 – i0) <- c0 c1 (i1 + (i0 – o1)) to be the component constructed by plugging c0's ports with c1's pegs, left-to-right: any overright inputs (overright is the spatial dual of leftover) remain active inputs of the composite and any overright output become outputs of the composite. We have one of the two pictures, below.

   |..i1..| |.i0  |      |......i1......|
  [___c1___]|  -  |     [_______c1_______]
   |..o1..| |  o1.|      |..i0..| |.o1  |
  [_______c0_______]    [___c0___]|  -  |
   |......o0......|      |..o0..| |  i0.|

Entertainingly, this composition is associative, with neutral element the portless pegless blank space. We obtain a parenthesis-free notation for building computations which degenerates to prefix-Polish in the case where every component has one peg.

We can also consider the regular horizontal juxtaposition, (o0 + o1) <- (c0 + c1) (i0 + i1), which makes no connections. We do need some parentheses to delimit the extent of +. We might write

(List S) (List T) <- unzip (List (Pair S T))
unzip nil                    = nil nil
unzip (cons (pair s t) sts)  = (cons s + cons t) unzip sts

I have taken the liberty of elaborating the 2 <- 1 arity of unzip with types. Note that the pattern variables s, t, sts are *values* with arity 1 <- 0. I have also included gratuitous parentheses on the left.

If we want to write higher-order functions, we shall need turn "doing" into "being". I'll write {..} to suspend computations (insert stock joke about braces being British for suspenders). Forcing a suspension requires some notation, and some means to identify the arity of the thing, which might be by type or by explicit annotation. A lot of the time, it might be more convenient to be explicit that a parameter to a function is for "doing", not "being". We might write

(List T) <- map {T <- (S)} (List S)
map f nil         = nil
map f (cons s ss) = cons (f s) (map f ss)

the point being that f need neither be forced when applying it to s, nor re-suspended when passing it recursively to map.

It’s kind of funny. If f and g are both 1 <- 1, then f g means their *composition*. To apply f to g, you write f {g}.

I think I'll stop for now. I don't think I've solved all the problems which are bugging me, but I think it's worth playing around with notational ideas which we can work with if we're just that little bit less reliant on inferring types and willing to check a bit more. I'm also trying to be more explicit about the value-computation distinction, in order to clean up the notation for managing effects. For example, that thing I called map just now. It's not what Haskellers call "map" (well, it is, but…); it's what Haskellers call "traverse". But that's another story.

Advertisements
7 Comments leave one →
  1. February 28, 2015 4:23 pm

    Why does storing pairs in lists still need a Pair constructor? This destroys the nice symmetry of unzip.

    • February 28, 2015 5:09 pm

      I suspect that lists of pairs, seen as a specific instance of lists of things, will need to box the pairs somehow. Mightn’t need to look like that. Might look more like lisp pairs. It might also be fun to write unzip (cons st sts) = (cons + cons) ixi (out st) (unzip sts), where 4 <- ixi 4 swaps the middle two of four things and 2 <- out 1 does fst and snd at once. But that begins to look better as an actual diagram, like I inflict on my unfortunate first years, learning circuit design.

  2. February 28, 2015 8:33 pm

    Replying below, because there seems to be a depth restriction. The question is ungrammatical (as, perhaps, are some parts of my post, because I’m getting used to this, too). Lists store *values*, which plug in the same way as computations of arity 1 <- 0, but are pure. Arities are for *computations*. A list can, of course, store a value which *suspends* a computation of arity 2 <- 0. But it's a mistake to think of a computation as an "entity": it's something that *does*, not something that *is*.

  3. March 1, 2015 11:45 am

    What breaks if you’d also have values which plug in the same way as computations of arity n <- 0?

    • March 2, 2015 12:32 am

      Nothing. But if we choose (List X) <- cons (X) (List X), then we are not free to treat cons as of arity 3 whenever we want to make lists of pairs. It's still important to ensure that polymorphic functions can be implemented once, for all. We're still going to have to box tuples from time to time. Of course, one could consider abstraction over the entire family of list-like definitions where each cell stores n heads and a tail…

  4. March 2, 2015 3:01 am

    This is extremely reminiscent of my dissertation work, though I go further by incorporating restricted forms of commutativity as well. (The commutativity being the goal for my particular problem domain.) I don’t think I talked much about my dissertation when we met in Copenhagen a few ICFPs ago. If you’re interested, we should chat sometime.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: