Traditional FP algorithms and side effects

[kyouko-taiga]

In Hylo there's a way to specify that a lambda shall not have side effects:

fun apply<E>(pure f: [E](Int) -> Int) -> Int {
  f(42)
}

Purity is a thorny question in PL. I'll use the following definition in this post:

A function is pure if its call operator is let.

This definition purposely doesn't take into account side effects that aren't captured by the type system (e.g., the state of memory allocators).

There are a couple of very well established operations in the FP world that we'll certainly want to bring to Hylo. One of them is mapping, which consists of applying a function on each element of a sequence. Such a function is typically called map.

Because map comes from the functional world, one may wonder whether it should accept impure functions. If it does, one could write code that may look quite puzzling to a functional programmer:

type A {
  var x: Int = 0
  fun f(_ y: Int[3]) inout -> Int[3] {
    y.map(&self.g)
  }
  fun g(_ a: Int) inout -> Int {
    (x.copy(), &a += a).0
  }
}

The above pattern does occur quite often in hc's code base. Just imagine that A is a type checker and that g is computing some property on an AST node, memoizing results in x.

If map required its argument to be pure, I think we would need another idiomatic way to apply an "effectful map" without having to use pure imperative style. Perhaps something like map(mutating:_:). We tried this approach in hc's code base. Though the result was not very convincing, I am tempted to give it a second shot in Hylo, because the type system has a way to better enforce some form of purity.

Note that the same observations apply to other traditional FP algorithms, like fold and filter.

[dabrahams]

In Hylo there's a way to specify that a lambda shall not have side effects:

Really, no. You yourself go on to say next that your notion of purity allows non-memory side-effects. And really, hylo's type system rules out arbitrary memory side-effects. What we're really left with is that it's a way to specify that a lambda is not mutated when it is called.

The fact that you are trying to show a case with implicit inout captures (in g) just makes me think that nested functions should explicitly declare their inout captures. But note your example seems to be mistaken; a is let-bound where g is trying to modify it.

I'm guessing you meant:

  fun g(_ a: Int) inout -> Int {
    (a.copy(), &x += x).0
  }

Which I might like to be written as:

  fun [inout x] g(_ a: Int) inout -> Int {
    (a.copy(), &x += x).0
  }

The point I'm trying to make here is that we're very explicit about memory side-effects in Hylo. So from that point of view, I have no problem whatsoever with the idea that functional algorithms can mutate the functions they operate on. The key is that it's the responsibility of a function not to change its return value based on internal state. It would be interesting if we could enforce that in the language.