Mechanism to make recursive monadic functions not loop

[developedby]

Mechanism to make recursive monadic functions not loop

[developedby]

Here's a list of bind functions before and after this proposed change.
Basically, whenever we apply something to nxt we swap that for applying to (args nxt), although that might not be exactly the case for all bind functions.

type Maybe = (Some val) | None
type Result = (Ok val) | (Err val)

Maybe/bind = @val @nxt match val {
  Maybe/Some: (nxt val.val)
  Maybe/None: None
}
Maybe/bind_ = @args @val @nxt match val {
  Maybe/Some: (args nxt val.val)
  Maybe/None: None
}

Result/bind = @val @nxt match val {
  Result/Ok: (nxt val.val)
  Result/Err: (Result/Err val.val)
}
Result/bind_ = @args @val @nxt match val {
  Result/Ok: (args nxt val.val)
  Result/Err: (Result/Err val.val)
}

List/concat (List/Cons x xs) ys = (List/Cons x (List/concat xs ys))
List/concat List/Nil ys = ys

List/flatten List/Nil = List/Nil
List/flatten (List/Cons x xs) = (List/concat x (List/flatten xs))

List/map (List/Cons x xs) f = (List/cons (f x) (List/map xs f))
List/map List/Nil f = List/Nil

List/bind = @val @nxt match val {
  List/Cons: (List/flatten (List/map val nxt))
  List/Nil: None
}
List/bind_ = @args @val @nxt match val {
  List/Cons: (List/flatten (List/map val (args nxt)))
  List/Nil: None
}

State/bind = @val @nxt @state let (state, res) = (val state); (nxt res state)
State/bind_ = @args @val @nxt @state let (state, res) = (val state); (args nxt res state)

Identity/bind = @val @nxt (nxt val)
Identity/bind_ = @args @val @nxt (args nxt val)

Continuation/bind = @val @nxt @cont (val (@a (nxt a cont)))
Continuation/bind_ = @args @val @nxt @cont (val (@a (args nxt a cont)))

IO/bind_ = @args @val @nxt match val {
  IO/Done: ((args nxt) val.expr)
  IO/Call: (IO/Call IO/MAGIC val.func val.argm @x (IO/bind_ args (val.cont x) nxt))
}

[developedby]

A suggestion by @tjjfvi on discord:

another approach that I believe would solve this:

I'm going to use defer value as shorthand for @unit match unit with * { Unit: value }, and undefer value as shorthand for (value unit), where
data Unit = Unit // desugars to Unit = @x x; idk what new bend syntax is for this

a <- Val
nxt(a, free1,..., freen)

# desugars to
(bind Val (defer @a (nxt a free1 ... freen)))

# which itself desugars to
(bind Val @id (id @free1 ... @freen @a (nxt a free1 ... freen) free1 ... freen))
#                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
#                               combinator!

# bind changes from
Maybe/bind = @val @nxt match val {
  Maybe/Some: (nxt val.val)
  Maybe/None: None
}

# to
Maybe/bind_ = @val @nxt match val {
  Maybe/Some: ((undefer nxt) val.val)
  Maybe/None: None
}

# which desugars to
Maybe/bind_ = @val @nxt match val {
  Maybe/Some: (nxt Unit val.val)
  Maybe/None: None
}

defer is the inet equivalent of a lazy thunk

[developedby]

A short example where this is necessary

type Result = (Ok val) | (Err val)

Result/bind = @val @nxt match val {
  Result/Ok: ((undefer nxt) val.val)
  Result/Err: (Result/Err val.val)
}
Result/foo x y = 
  with Result {
    ask a = (Result/Ok x)
    ask b = switch y { 0: (Result/Err a); _: (Result/Ok y-1) }
    (Result/foo a b)
  }

main = (Result/foo 1 2)