Closed Pauan closed 7 months ago
Implementation-wise, each compile-time scope would have a list of implicit
variables.
When an implicit
is looked up, it will check in the current scope.
If there is exactly one implicit
variable in the current scope which matches the type, it will use that.
If there is more than one implicit
variable which matches the type, it will error.
If there is zero implicit
variables, it will then recursively check the outer scope.
This allows an inner implicit
to shadow an outer implicit
:
implicit val foo: int = 1
fun bar(a: implicit int): int { a }
fun qux() {
// This shadows the `foo` implicit
implicit val corge: int = 2
bar()
}
fun main() {
println(bar()) // prints 1
printfn(qux()) // prints 2
}
This enables a form of "dynamically scoped variables" ala Common Lisp. Except unlike dynamically scoped variables (which use mutation), this is safe, because it gets compiled into function argument passing.
Also, there is an additional complexity when a function which has implicit
arguments is used as a value. For example, when using a higher-order function:
implicit val foo: int = 1
fun bar(a: implicit int, b: int): int { a + b }
map([1, 2, 3], bar)
In this case, the Koka compiler has to create a lambda and resolve the implicit
within the lambda:
map([1, 2, 3], fun(a) { bar(implicit foo, a) })
The same is true when storing bar
in a data structure.
For performance, it would be useful to do common subexpression removal, so that way the lambda fun(a) { bar(implicit foo, a) }
will be hoisted to the top level and reused:
fun bar_(a) { bar(implicit foo, a) }
map([1, 2, 3], bar_)
map([1, 2, 3], bar_)
There's some open questions:
implicit
is being used for three things:
Marking a variable as implicit
Marking function arguments as implicit
Explicitly passing in an implicit
to a function
I don't like this interweaving of purposes. I feel like it should be possible to split these into separate orthogonal concepts.
I'm not sure whether the syntax should be fun foo(implicit a: int) {}
or fun foo(a: implicit int) {}
implicit a: int
is better because it implies that the function argument itself has special behavior (which is correct)It also is more consistent with implicit val foo: int = 1
a: implicit int
is better because it allows you to specify implicit
in types:val foo: (implicit int, int) -> int
It also has a better intuition when using higher-order functions: when an (implicit a) -> b
is used in a context which expects a () -> b
it will coerce the function into a lambda and resolve the implicit
Also, I would really like to use special syntax for implicit int
, such as @int
, because implicit
is really verbose. But it seems like Koka already uses all of the special symbols, so there isn't any symbols available.
I thought about it some more, and I wonder if it would be better to keep implicit and non-implicit variables completely separate. In other words, it wouldn't automatically convert implicit to non-implicit.
Essentially, implicit and explicit variables would have separate types, and therefore cannot be mixed.
It is still possible to manually convert from implicit to non-implicit by using this function:
fun explicit(a: implicit a): a { a }
Now it's possible to convert from an implicit variable to an explicit value:
implicit val foo: int = 1
// The same as `val bar: int = foo`
val bar: int = explicit()
If there are many implicits in scope, you can select the one you want:
val bar: int = explicit(implicit foo)
Thinking about it further, perhaps we don't need functional dependencies. I'm not an expert on it, but it seems to me that functional dependencies were added to Haskell to prevent ambiguous type inference and to move errors to the place where the function is defined, rather than the place where the function is used.
But with my proposed implicit arguments, ambiguities are already possible (and are resolved by manually passing in an instance), and there is no implicit type inference: implicit arguments must always be manually marked as implicit
.
In addition, Haskell allows for values which contain typeclass constraints, such as foo :: (Foo a) => a
, but that would not be allowed with my proposal: only implicit function arguments can be polymorphic. In other words, variables are always monomorphic. Therefore the monomorphism restriction is not needed.
This creates a simpler mental model for the programmer, and it is also closer to the implementation: polymorphic values in Haskell are actually functions, because they can be instantiated with different typeclass instances.
With my proposal, they would actually be functions, rather than something which looks like a value but is actually a function. This preserves the mental model that using a variable is cheap, and doesn't involve arbitrary computation.
So in practice functional dependencies might not offer any advantages, and therefore we don't need to clutter up the simplicity of my proposal.
It's also interesting to note that algebraic effect handlers provide a lot of the same functionality as typeclasses.
For example, consider this Haskell typeclass:
class Add a where
add :: a -> a -> a
instance Add Int where
add left right = left + right
genericAdd :: Add a => a -> a -> a
genericAdd left right = add (add (add left right) right) right
main :: IO ()
main = print (genericAdd 1 2)
We can define that in Koka like this:
effect add<a> {
add(left: a, right: a): a
}
val add-int = handler {
add(a: int, b: int) -> resume(a + b)
}
fun generic-add(left: a, right: a): add<a> a {
add(add(add(left, right), right), right)
}
fun main(): console () {
println(add-int({ generic-add(1, 2) }))
}
However, I suspect this doesn't provide quite as much flexibility as typeclasses do, and it's a bit conceptually weird to use a "side effect" system for non-side effect polymorphism.
It's also rather clunky to use, because we have to explicitly call add-int
. But we generally only need to call add-int
at the top level of our program, because the effects will propagate downward automatically.
I also have some concerns about the efficiency of using effect handlers for this: typeclasses are quite efficient, since it simply involves the compiler automatically adding an extra argument to functions.
This means that programmers can freely use typeclasses all the time, without worrying about performance. This leads to more abstract libraries, which in turn helps reduce code duplication. I am a huge fan of Rust's motto of "zero-cost abstractions", which is one of the reasons I'm a huge fan of typeclasses.
However, despite those concerns, it may be worthwhile to explore whether it's possible to avoid adding typeclasses, and instead rely solely upon effect handlers.
As an alternative to my proposal, we could instead have "implicit effect handlers", which are the same as regular effect handlers except that they are automatically applied based upon the type context:
val add-int = implicit-handler {
add(a: int, b: int) -> resume(a + b)
}
fun main(): console () {
println(generic-add(1, 2))
}
When an effect needs to be discharged, it will search the current and parent scopes for an implicit handler and will then automatically call it. So the above code would be equivalent to this:
fun main(): console () {
println(add-int({ generic-add(1, 2) }))
}
This also answers the question of "how does Koka know to automatically apply the async-handle
handler when calling main
with an async
effect?"
I haven't thought this through, so I'm still hazy on the details, but it's an alternative to consider.
Something else I thought of: is it possible to implement the effect system using implicit parameter passing? That should offer a significant performance boost.
If it's possible, I think that would make it viable to use the effect system to implement ad-hoc polymorphism. Then the only thing missing is implicit effect handlers.
If we decide to use the effect system instead of typeclasses, I think it would be useful to rename it. It's very weird to use the word "effect", because we're not really using it for side effects, we're just using it solely for polymorphism.
I think a good suggestion is to use protocol
to create an effect, and implement
to create a handler:
protocol add<a> {
add(left: a, right: a): a
}
val add-int = implement {
add(a: int, b: int) -> resume(a + b)
}
fun generic-add(left: a, right: a): add<a> a {
add(add(add(left, right), right), right)
}
fun main(): console () {
println(add-int({ generic-add(1, 2) }))
}
This naming still works for side effects (like exn
, async
, etc.), because the purpose of the effect system is to add new effects to the language, and these new effects describe a protocol which must be implemented by handlers.
Some other good suggestions: interface / implement
, require / provide
, contract / fulfill
Another option is to use standard OOP interfaces:
interface add<a> {
add(left: a, right: a): a
}
fun generic-add<a implement add<a>>(left: a, right: a): a {
add(add(add(left, right), right), right)
}
implement add<int> {
add(a, b) -> a + b
}
struct my-int(value: int)
implement add<my-int> {
add(a, b) -> my-int(add(a.value, b.value))
}
generic-add(1, 2) // -> 7
generic-add(my-int(1), my-int(2)) // -> my-int(7)
In C# this would be compiled down to regular C# interfaces.
In JavaScript this can be implemented in a variety of ways, but here is one possibility:
Number.prototype._type = "std/core/int";
var add_vtable = {};
function add(left, right) {
return add_vtable[left._type].add(left, right);
}
function generic_add(left, right) {
return add(add(add(left, right), right), right);
}
function add_int_add(left, right) {
return left + right;
}
add_vtable["std/core/int"] = {
add: add_int_add
};
function my_int(value) {
return { _type: "path/to/my-int", value: value };
}
function add_my_int_add(a, b) {
return my_int(add_int_add(a.value, b.value));
}
add_vtable["path/to/my-int"] = {
add: add_my_int_add
};
generic_add(1, 2); // -> 7
generic_add(my_int(1), my_int(2)); // -> my_int(7)
A few things to note:
Interfaces get turned into functions + a vtable.
This is slower than typeclasses, and it's also less powerful (typeclasses can dispatch on multiple arguments, and typeclasses can dispatch on the return type).
Because the implementation is (indirectly) attached to the type rather than passed in implicit arguments, it's easy to pass a type deep down the call stack without any problems, whereas typeclasses require the implicit arguments to be threaded through the entire call stack.
This gives a bit more runtime flexibility at the cost of reduced performance and increased memory usage.
One major benefit of having the implementations attached to the type is that it's easy to create things like list<add<a>>
, which is a list
where every element implements the add
interface. This lets you combine multiple types into a single list
, as long as every type implements the appropriate interfaces. This kind of polymorphism is trickier with typeclasses (but still possible).
All types need to have a _type
property, which must be unique per type. In this case I'm just using the fully qualified name of the type.
Built-in JavaScript types can be given a _type
by abusing the prototype
(e.g. Number.prototype
, String.prototype
, etc.)
It's very tricky to create implementations for functions (e.g. implement add<(a) -> a>
), whereas it's trivial with typeclasses.
When the type is known, it doesn't need to call the add
function, instead it can call the implementation directly. Therefore the add_my_int_add
function can just call add_int_add
rather than calling add
.
This is true with typeclasses as well.
@Pauan I don't know whether you are still interested, but ...
Something else I thought of: is it possible to implement the effect system using implicit parameter passing?
Actually, this is what I do in Scala Effekt. This works really great in particular with Dotty's new implicit function types.
Also you might be interested in #68 and #69 where I started to implement implicits in Koka. There are still some barriers to use the implicits as implemented there for ad-hoc polymorphism, but it is a first step.
Actually, this is what I do in Scala Effekt.
I get a 404 for this page, but I took a look at the code, it's very cool!
Also you might be interested in #68 and #69 where I started to implement implicits in Koka
Yeah, I saw those. Nowadays I use Rust (and I'm quite happy with it), but I'm glad to see things progressing with Koka. I still like its clean, minimal design.
Thanks for letting me know about the breakage of my page! Sad to hear you moved to Rust, I would have been interested how migrating the large code base to Koka went.
@Pauan
Interestingly I separately came up with a similar system in #336, which has now been implemented in Koka by Daan. However, my approach proposed using names instead of types and explicit implicit
declarations. Your approach seems more similar to what Scala has implemented for implicits. There seems to be a wide range of approaches and ways a compiler could determine what to automatically pass in as an implicit
parameter, and these two approaches are just a few points on that spectrum.
When I talked with Daan, implicit effect handlers seemed like a bad idea after thinking it through more thoroughly. Effect handlers are dynamically scoped and can easily be intercepted, which is not really something desirable for ad-hoc polymorphism. Interestingly, sometime after your comment https://github.com/koka-lang/koka/issues/16#issuecomment-309248156 effect handlers in Koka were altered to work by passing evidence down (implicitly in the runtime), and it is very performant like you predicted https://www.microsoft.com/en-us/research/publication/generalized-evidence-passing-for-effect-handlers/.
Hope you give Koka a try again sometime soon, and leave some feedback on more issues or discussion topics! I'm also a fan of Koka's clean minimal design.
Instead of closing this issue, I'm just going to convert it to a discussion topic since I feel like there is definitely interesting (non-issue) ideas that others visiting Koka might be interested in.
The ability to have multiple functions with the same name and different types is very nice, but there are still situations where ad-hoc polymorphism is useful.
An example is a function which calls
map
, it would be nice if it worked with any type which implementsmap
There are many ways of implementing ad-hoc polymorphism: Haskell typeclasses, ML modules, and creating multiple copies of each function (used by Rust and others).
I propose a simplified typeclass mechanism for Koka.
Any variable can be marked as
implicit
:Function parameters can also be marked as
implicit
:When a function has
implicit
arguments and it is called, it will search forimplicit
variables which are in scope, and if there is animplicit
variable which matches the type, it will then automatically pass it in:It's also possible to pass in
implicit
arguments explicitly:It's also possible to convert from
implicit
variables to regular variables, and from regular variables toimplicit
variables:And that's it. That's the entire system. With this, it's possible to create Haskell typeclasses by combining
type
withimplicit
:The above code is equivalent to this Haskell program:
The Koka code is quite heavy-weight on the syntax. This can potentially be solved with the following trick:
The benefits of this light-weight typeclass system is that it is easy to implement and it's easy for the user to understand. It's the same as regular function arguments... except automatically passed in by the compiler.
It also gives a lot of the same power of ML modules, because it's possible to pass in
implicit
arguments explicitly, createimplicit
variables dynamically, and use locally scopedimplicit
variables.One downside is that it's not possible to define
union
for maps or sets, because they assume that there is only a single typeclass instance per type.Instead, you need to store the
Ord
instance in the data structure itself and useunionLeft
orunionRight
(which might be slower thanunion
). This is possible because implicits can be converted into regular values and then stored in data structures.Another downside is that I'm not sure how to define advanced features like functional dependencies or type families. But maybe the simplicity of
implicit
is more important than advanced type features.