Pattern match for sequences

[Xin Wang]

Hi,

Firstly, thank you for your efforts in Cell, it is fascinating!

Recently, I'm trying to write some trivial programs in Cell, I found that I frequently need to do pattern match for sequences (e.g. hd :: tl), seems that it is not supported right now, so does it planned in the future? Another similar feature is destructuring assignment.

Another question is that, quite different from other functional languages, Cell sequences are constructed by push element to back of sequence (e.g. (seq | elt)), instead of front, is there any rationale behind this design?

Regards,

Xin Wang

[cell-lang]

Hi Xin,

thanks for giving Cell a try.

I'll answer your second question first. Cell is not, and was never meant to be, a "proper" functional language like ML or Haskell. Cell is functional only in the sense that functions are pure (no side effects), referentially transparent (that is, deterministic) and that the data model includes algebraic data types (it's basically ADTs + relations) and therefore pattern matching. But it is designed for a procedural/imperative programming style, one that makes use of loops and local mutability. With that is mind, compare the implementation of a few simple functions, map, filter and scanl, in Haskell using recursion and in Cell using loops (of course both map and filter could be more easily implemented using list/sequence comprehension, but I need to compare the use of recursion and loops to explain this). This is Haskell:

  map :: (a -> b) -> [a] -> [b]
  map f []      = []
  map f [h | t] = [f h | map f t]

  filter :: (a -> Bool) -> [a] -> [a]
  filter _ []      = []
  filter p [h | t] = if p h then [h | filter p t] else filter p t

  scanl :: (a -> b -> a) -> a -> [b] -> [a]
  scanl _ y []      = [y]
  scanl f y [h | t] = [y | scanl f (f y h) t]

And this is Cell:

  Y* map(X* xs, (X -> Y) f) {
    ys = ();
    for x <- xs:
      ys = (ys | f(x));
    ;
    return ys;
  }

  X* filter(X* xs, (X -> Bool) p) {
    fxs = ();
    for x <- xs:
      fxs = (fxs | x) if p(x);
    ;
    return fxs;
  }

  X+ scanl(X x, Y* ys, (X Y -> X) f) {
    a = x;
    s = (a);
    for y <- ys:
      a = f(a, y);
      s = (s | a);
    ;
    return s;
  }

Do you see why in Cell elements are appended at the end? That's just the natural thing to do when using loops. The sequence append operation in Cell is basically a no-side-effects version of C++'s vector::push_back(). And it's implemented pretty much in the same way. In Cell, sequences are implemented as arrays at the moment, and the append operation is implemented by leaving (only when needed, of course) some extra free space at the back, where new elements can be stored.

It would be possible of course to efficiently implement insertion at either end of a sequence, by simply leaving some extra space either at the front and/or at the end of it, depending on the circumstances. That's actually on my to-do list, but it has very low priority. The most important parts of Cell are automata and the network architecture, and there's so much work to do there that I don't think I will be able to dedicate much time to the functional subset of the language anytime soon. And even when I get around to doing that, there's a whole lot of other things that I believe are more important. My first priority, for example, will be to provide an efficient implementation of array mutability.

As for the hd :: tl pattern, I just never had any need for it in my own code. Again, remember that Cell is designed for a procedural programming style. Recursion is a wonderful tool for many problems, but for for simple things like iterating through a list, it feels overkill to me: it's just easier and more efficient to use a loop.

But if you have any code that you think would benefit from having an hd :: tl pattern, or in general from a more "functional" programming style, feel free to post the code here. I'll be happy to show how I would implement it, and to discuss alternative implementations. I'm perfectly willing to make changes or to add new features to the language if it turns out there are valid use cases for them (I'm actually looking for feedback or suggestions), with the already mentioned caveat that I'm focused on automata and the network architecture at the moment, and improvements to the functional subset of the language have a lower priority.

Regards,

  Giovanni

[Xin Wang]

Hi Giovanni,

I see. I was confused by the meaning of "functional" in Cell, if what Cell goes for is an imperative programming style, that all make sense.

The hd :: tl problem is encountered when I was trying to translate a small Erlang program into Cell. But as Cell is imperative, those two languages are quite different, it is reasonable that the translation is not quite straightforward.

Thank you for your detailed explanation!

Thanks,

Xin Wang