# =============================================================================
# Concurrent ML `choose` type inference problem in Crystal
# =============================================================================
#
# This document describes a real-world type inference limitation encountered
# when porting John Reppy’s Concurrent ML (CML) design to Crystal language.
#
# The CML model centers on *events* (values of type `Event(T)`), which represent
# potential synchronous communications or computations. Multiple events can
# be combined using `choose_evt` (nondeterministic choice), and only one branch
# “commits” when synchronized via `sync(evt)`.
#
# The core invariant: `choose` is purely a combinator; it doesn’t perform
# until `sync` is called. This design works well in SML because its type
# inference engine easily unifies all branch result types, and events such as
# `timeout_evt` or `never_evt` can safely coexist in a single choice.
#
# In Crystal, we’re very close — but there’s a key *type inference barrier*:
#
# -----------------------------------------------------------------------------
# Problem Summary
# -----------------------------------------------------------------------------
#
# When combining heterogeneous `Event(T)` types in an `Array`, Crystal’s type
# inference produces a union of the *concrete generic instantiations* rather
# than a single polymorphic supertype. This breaks overload resolution for a
# method like:
#
# def self.choose(evts : Array(Event(T))) : Event(T) forall T
#
# Example:
#
# ch = CML::Chan(Int32).new
#
# choice = CML.choose([
# CML.wrap(ch.recv_evt) { |_| :recv }, # Event(Symbol)
# CML.wrap(CML.timeout(0.1.seconds)) { |_| :timeout }, # Event(Symbol)
# ])
#
# # ❌ Compiler error:
# # expected Array(Event(Symbol)), not Array(Event(Symbol) | TimeoutEvt)
#
# Even though all branches *conceptually* yield `Symbol`, Crystal’s invariance
# and separate generic instantiations mean it cannot unify them automatically.
#
# In SML, this works because type inference is polymorphic by default:
# val e1 : ’a event
# val e2 : unit event
# val choice = choose [wrap e1 (fn _ => #recv), wrap timeout_event (fn _ => #timeout)]
#
# -----------------------------------------------------------------------------
# Why `never` and `timeout` amplify the issue
# -----------------------------------------------------------------------------
#
# - `never_evt` is typed as `Event(T)` but never produces a value — it’s inert.
# In ML, this freely unifies with anything (like `’a event`).
# - `timeout_evt` naturally yields a `Symbol` (`:timeout`) or unit.
# In practice, most real `choose` calls race real events against a timeout.
#
# In Crystal, these must share a single `T` type parameter in
# `Array(Event(T))`, but the compiler cannot infer it when generics differ.
#
# -----------------------------------------------------------------------------
# Workarounds tried
# -----------------------------------------------------------------------------
#
# 1. Manual casting:
#
# typed_never = CML.wrap(CML.never(Int32)) { |_| :never } as CML::Event(Symbol)
# choice = CML.choose([typed_never,
# CML.wrap(ch.recv_evt) { |_| :recv },
# CML.wrap(CML.timeout(0.1.seconds)) { |_| :timeout }])
#
# ✅ Works, but ugly and non-obvious for library users.
#
# 2. Force the array literal type explicitly:
#
# choice = CML.choose([
# CML.wrap(CML.never(Int32)) { |_| :never },
# CML.wrap(ch.recv_evt) { |_| :recv },
# CML.wrap(CML.timeout(0.1.seconds)) { |_| :timeout },
# ] of CML::Event(Symbol))
#
# ✅ Works, but verbose and not ergonomic.
#
# 3. A dynamic fallback (library side):
#
# def self.choose_any(evts : Array(Event) | Tuple)
# unified = evts.map do |e|
# CML.wrap(e.as(Event)) { |x| x.as(Symbol | Nil | Int32 | String) }
# end
# ChooseEvt(Symbol | Nil | Int32 | String).new(unified)
# end
#
# ✅ Works, allows mixing `TimeoutEvt` and others.
# ⚠️ Loses static type guarantees, since all results are widened into a big union.
#
# -----------------------------------------------------------------------------
# Desired behavior
# -----------------------------------------------------------------------------
#
# Ideally, Crystal could unify the type variable `T` across generic parameters
# of `Event(T)` when placed in an array, producing something like:
#
# Array(Event(Symbol)) ← rather than Array(Event(Symbol) | TimeoutEvt)
#
# That would allow:
#
# choice = CML.choose([
# CML.wrap(ch.recv_evt) { |_| :recv },
# CML.wrap(CML.timeout(0.1.seconds)) { |_| :timeout },
# CML.never(Int32)
# ])
# result = CML.sync(choice)
#
# to compile cleanly.
#
# -----------------------------------------------------------------------------
# Minimal Repro
# -----------------------------------------------------------------------------
#
# ```crystal
# module CML
# abstract class Event(T); end
#
# class TimeoutEvt < Event(Symbol); end
# class RecvEvt(T) < Event(T); end
#
# def self.choose(evts : Array(Event(T))) : Event(T) forall T
# # no-op
# evts.first
# end
# end
#
# ch = CML::RecvEvt(Int32).new
# choice = CML.choose([ch, CML::TimeoutEvt.new])
# ```
#
# ❌ Error: expected argument #1 to 'choose' to be Array(Event(Int32)), not Array(Event(Int32) | CML::TimeoutEvt)
#
# -----------------------------------------------------------------------------
# Discussion questions for Crystal core / type system developers
# -----------------------------------------------------------------------------
#
# 1. Could Crystal’s generic unification rules be relaxed to allow
# `Array(Event(Int32) | Event(Symbol))` to unify as `Array(Event(Int32 | Symbol))`
# when the same generic base type is used?
#
# 2. Is there a way for a library to express a “variance-like” constraint
# on generic parameters for this pattern — e.g., `Event` being covariant in `T`?
#
# 3. Would a macro-level solution (`macro choose_evt(*evts)`) be able to
# introspect and compute a common union type of the block return values,
# producing an `Array(Event(common_union_type))` automatically?
#
# 4. Is there any pattern or compiler hint (`.splat`, `typeof(...)`) that can
# achieve this statically today without resorting to a huge union wrapper?
#
# -----------------------------------------------------------------------------
# The goal
# -----------------------------------------------------------------------------
#
# Bring Crystal’s ergonomics for typed event combinators closer to the
# Concurrent ML model:
#
# choose [timeout_evt, recv_evt, never_evt] |> sync
#
# should “just work” without any explicit type coercion,
# while retaining static safety and type inference fidelity.
#
# -----------------------------------------------------------------------------
# Thank you!
# -----------------------------------------------------------------------------
#
# Any insight or future direction for generic covariance, inference improvements,
# or macro-based workarounds would be incredibly valuable for Crystal libraries
# that implement higher-level concurrency abstractions like Concurrent ML.
#
# -- Dominic Sisneros (dsisnero)
# -----------------------------------------------------------------------------
You can drop the T free variable from the CML.choose method. Crystal still won’t unionize the generic T, but it will compile and correctly resolve types at compile time.
module CML
class Event(T)
getter value : T
def initialize(@value : T)
end
end
class Timeout(T) < Event(T); end
class Receive(T) < Event(T); end
class Send(T) < Event(T); end
def self.choose(evts : Array(Event)) : Event
evts.sample
end
end
ch1 = CML::Receive.new(123)
ch2 = CML::Send.new("foo")
timeout = CML::Timeout.new(:timeout)
choice1 = CML.choose([ch1])
p! typeof(choice1) # => CML::Receive(Int32)
p! typeof(choice1.value) # => Int32
choice2 = CML.choose([ch2])
p! typeof(choice2) # => CML::Send(String)
p! typeof(choice2.value) # => String
choice1_tm = CML.choose([ch1, timeout])
p! typeof(choice1_tm) # => CML::Receive(Int32) | CML::Timeout(Symbol)
p! typeof(choice1_tm.value) # => Int32 | Symbol
choice_all = CML.choose([ch1, ch2, timeout])
p! typeof(choice_all) # => CML::Receive(Int32) | CML::Send(Int32) | CML::Timeout(Symbol)
p! typeof(choice_all.value) # => Int32 | String | Symbol
I.e. we can take advantage of the compiler expanding method args with concrete types 
Here, the CML.choose will naturally be expanded into multiple methods for each kind of array of event we give it. The same would happen for CML.wrap.
1 Like
@dsisnero We’re actually interested in (Parallel) Concurrent ML. We looked a bit at the design a couple years ago, but didn’t go very far. I tried to look at your cml shard but it’s missing the `cml/core/event.cr` file 
Look at it now - dsisnero/cml . I am trying to get add easier usage with choose but still had issues. I want the choose method to let me choose a particular Event(T) but at same time let me choose on TimeOut and Nack which probably should be void types. Glad to hear you are looking at Parallel Concurrent ML - I hope we can get this abstraction into Crystal proper because it lets you choose (select) on your own Event(T) I used AI to help me with a hierarchical timer wheel for the time events .