How does compositional style deal with callbacks?

[Kesanov]

It seems to me that callbacks do not fit compositional style well, yet monadic IO is built around them (as well a as lambda encoding).

For example

combinations = -- [(1,3), (2, 3)]
  flatMap [1, 2] a =>
  flatMap [3] b =>
  singleton (a, b)
io =
  prompt "What is your name?" name =>
  prompt "What is your age?" age =>
  print "Hello {name} of age {age} years."

Cannot be easily expressed with composition.

How does kitten (or concatenative languages in general) deal with it?

[suhr]

Cannot be easily expressed with composition.

It can be, but the result is not that readable:

[1, 2] {
    [3] swap { pair } uc flat_map
} flat_map

Here, uc is a combinator, such as a {f} uc ⇒ {a f}.

[Kesanov]

I think it could be solved with some syntactic sugar like

[1, 2] foo -> a b c -- not real locals, more like ( .. a b c -- .. ) in factor
body

would be rewritten into

[1, 2] [foo] body curry3

[Kesanov]

Anyway, that does not change the fact that lambda encoding feels a little bit alien in concatenative languages, which is an issue because it has some nice properties. For example all church encoded data structures fuse automatically under beta reduction.

For example

• map (+1) . map (+2) . map (+3) fuses into map (+6)
• not . not fuses into identity

But that's not the case for stack based data structures right?

[evincarofautumn]

I don’t use monads for effects in Kitten. You can encode them if you want, and you’ll be able to abstract over them when I implement higher-kinded types (which should be a fairly simple addition after my current refactoring).

For now there’s a small bit of syntactic sugar (do (f) { g } = { g } f) for passing a block as a quotation, so your example might be written:

[1, 2] do (map_concat) -> a:
  [3] do (map_concat) -> b:
    [a b pair]

This uses a combination of this do and a “lambda” which is sugar for a quotation that gives local names to its parameters (-> x { h } = { -> x; h }).

This doesn’t provide the nice properties of Haskell’s do notation (or list & monad comprehensions) where binds are implicit and the “nesting” structure is visually flattened. So I’d be willing to consider adopting some sugar for monadic (or applicative) operations, but it’s not high-priority for me because monads aren’t the primary way of representing effects in Kitten—for that there are “permissions” such as +IO and +Unsafe attached to function types.

Kitten’s built-in data structures aren’t Church-encoded anyway; the stack doesn’t really make a difference. When I get around to implementing fusion as an optimisation, it will probably be implemented similarly to GHC’s rewrite rules. { f } map { g } map will be fused into { f g } map if the permissions of f and g are commutative—that is, if f and g are pure or they perform side effects that can be reordered without changing semantics.

In Kitten, a local variable scope -> x; e is exactly the same (in terms of semantics and typechecking) as a lambda form λx. e in lambda calculus; the only difference is that in concatenative land we use composition to combine these with other functions, and the variable is a single value taken from the stack instead of the whole stack state. There’s a straightforward translation from a Kitten-like language to LC:

• e1 e2 → λs. e2 (e1 s)
• → λs. s
• → x; e → λs. (λx. e (cdr s)) (car s)
• x → λs. cons x s
• …