Richard Feldman (Aug 29 2024 at 13:46): Richard Feldman (Aug 29 2024 at 13:46):splitting this off from #ideas > function effectfulness syntax
Ayaz Hafiz said:
what if effectful calls are signified at the call site instead of the declaration site? So for example,
List.map ls fisList.map! ls fif f is effectful. Then there is no need for polymorphism in the declarations in the context of this use case specifically. Not saying that's definitely the way, but pushing really hard on avoiding type system complexity via polymorphism is a very valuable metric, if it can be achieved.
Richard Feldman (Aug 29 2024 at 13:46):I think I misunderstood this idea originally, and I just realized what the idea actually is
Richard Feldman (Aug 29 2024 at 13:46):let me see if I can articulate it to check my own understanding
Richard Feldman (Aug 29 2024 at 13:47):the idea is that this type:
List.map : List a, (a -> b) -> List b
...is a pure function. It is not effect-polymorphic at all, it's just straight-up pure
Richard Feldman (Aug 29 2024 at 13:47):however, I can call it like this:
List.map! list \elem -> doSomeEffect
and what the ! does is to call a version of that function where all the ->s in the type have been replaced with =>
Richard Feldman (Aug 29 2024 at 13:48):in other words, if this exists:
List.map : List a, (a -> b) -> List b
...then this automatically exists too:
List.map! : List a, (a => b) => List b
by default I always get the pure one, and if I want the effectful one, I can opt into it at the call site
Richard Feldman (Aug 29 2024 at 13:51):I'm not sure how (or whether) this would work in the context of lambdas that get stored somewhere, e.g. Parser.map
Richard Feldman (Aug 29 2024 at 13:51):like if I do Parser.map! parser \val -> doSomeEffect
Richard Feldman (Aug 29 2024 at 13:52):then in theory if that's allowed, then later on down the line when I'm actually running the parse operation, that becomes effectful because whenever it encounters the internally-stored lambda, that's effectful now
Richard Feldman (Aug 29 2024 at 13:53):but that wouldn't be represented in the type of Parser a so something would have to be different in this situation one way or another; otherwise running the annotated-as-pure parsing operation would produce an effect, which of course can never be allowed
Richard Feldman (Aug 29 2024 at 13:53):so somehow in this design, List.map! would have to Just Work but Parser.map! would have to give an error
Richard Feldman (Aug 29 2024 at 13:54):I'm not sure how the compiler would know to do that, considering the types of List.map and Parser.map are basically the same structurally :sweat_smile:
Richard Feldman (Aug 29 2024 at 13:54):but maybe I'm missing something!
Ayaz Hafiz (Aug 29 2024 at 14:02):As soon as you do p = Parser.map! parser \val -> doSomeEffect the whole parser p becomes effectful. So the only way to do anything over it is with a bang. I don't know how you make that clear in the type annotation on Parser (or if it needs to be clear), but the same problem is true in the other design - you don't know if a Parser is effectful, polymorphically effectful, or not at all without digging into the callers or opaque type definition
Richard Feldman (Aug 29 2024 at 14:17):so the current design in #ideas > function effectfulness syntax is:
-> means it's pure=> means it's effectful-var-> means it's polymorphicin this design, there would be two ways to design Parser:
-> in its definition, meaning it will only accept pure functionsParser if you want it to be polymorphic Richard Feldman (Aug 29 2024 at 14:18):I can't think of a design where taking a Parser and using it to run a parse operation inside a pure function (which of course should be able to work with a parser!) can work without one of the following being true:
either the Parser accepts only pure functions, or else it has an extra type parameter
Richard Feldman (Aug 29 2024 at 14:19):(or if not a type parameter, it's marked in some equivalent way as being effect-polymorphic)
Richard Feldman (Aug 29 2024 at 14:21):but regardless, I think the relevant point here is that going back to the original motivation:
Ayaz Hafiz said:
what if effectful calls are signified at the call site instead of the declaration site? So for example,
List.map ls fisList.map! ls fif f is effectful. Then there is no need for polymorphism in the declarations in the context of this use case specifically.
I think this idea can work in the context of List.map specifically, but I don't think it can achieve its goals in the context of Parser.map, and currently there's no way for the compiler to tell the difference (as far as I can tell) between those two cases, so I'm not sure how it would be possible to make List.map Just Work in this design without breaking Parser.map :thinking:
Agus Zubiaga (Aug 29 2024 at 14:21):Can’t the ! require the function inside the parser be polymorphic?
Richard Feldman (Aug 29 2024 at 14:28):hm, I'm not sure what that would mean in this design
Agus Zubiaga (Aug 29 2024 at 14:35):Like for Parser.map! to work, the Parser type would have to have an effect polymorphism variable that used in the internal function:
Parser a fx := (List U8 -fx-> (a, List U8))
this is the simplest example i can come up with from unison https://gist.github.com/drewolson/aa3f4c39ea7db98e3e37e24d2d5ab7ad
drew (Aug 29 2024 at 14:39):even id is effect polymorphic, but it is very obvious at the call site and the error is pretty darn obvious if you mis-use it
drew (Aug 29 2024 at 14:39):Store.get has a type that is basically {} ->{Store a} a or something
drew (Aug 29 2024 at 14:42):if you use id within other functions, it quickly becomes clear when it is effectful vs not
drew (Aug 29 2024 at 14:42):id : a -> a
id a = a
normal : Nat -> Nat
normal a = id a + 1
effectful : '{Store a} a
effectful = '(id Store.get)
⍟ These new definitions are ok to `add`:
effectful : '{Store a} a
id : a -> a
normal : Nat -> Nat
i guess maybe this isn't the best example as it isn't higher-order, but i do think it feels intuitive, and this is likely how a roc with ayaz's suggestion and a single effect type would "feel"
drew (Aug 29 2024 at 14:51):better example:
drew (Aug 29 2024 at 14:52):doStuff : (a -> a) -> a -> a
doStuff f a = f a
add : Nat -> Nat
add n = doStuff (x -> x + 1) n
addEffectful : Nat ->{Store Nat} Nat
addEffectful n = doStuff (x -> x + Store.get) n
in roc it would be like:
drew (Aug 29 2024 at 14:56):doStuff : a, (a -> a) -> a
doStuff a f = f a
add : I64 -> I64
add n = doStuff n \x -> x + 1
addTask : I64 -> Task I64 _
addTask n = doStuff n \x -> x + someTask!
(or if not a type parameter, it's marked in some equivalent way as being effect-polymorphic)
yes, this is what you have to do. if you do this then Parser.map works just as well as List.map
Sam Mohr (Aug 29 2024 at 15:36):Ayaz and Drew, do you think that Brendan's worry that functions would now need to defensively program against inconsistent code are worth this syntax simplification? That is the main cost here I can see
drew (Aug 29 2024 at 15:39):I don't totally understand how that concern plays out, psuedocode would be helpful maybe? in the case of higher-order functions, they're polymorphic on effects so they can't use effects locally anyway while remaining polymophic. at call sites, i don't understand how you'd need to be defensive, it's obvious when you're using an effect and the compiler enforces it. but ayaz clearly has a super deep understanding of the space, so i'm curious about his thoughts.
Sam Mohr (Aug 29 2024 at 15:46):Let's say I give you a function:
cachingCalcHash : Str, Dict Str U64, (Str -> U64) -> (U64, Dict Str U64)
cachingCalcHash = \input, cache, hasher ->
when Dict.get cache input is
Ok hash -> (hash, cache)
Err _err ->
hash = hasher input
updatedCache = Dict.insert cache input hash
(hash, updatedCache)
It provides an interface that implies it can avoid re-running an expensive operation for you.
Sam Mohr (Aug 29 2024 at 15:49):If I call it with cachingCalcHash! "abc" cache File.effectfulHash, then the assumption that my (Str -> U64) hasher is referentially transparent is false, and I'll retrieve an old, wrong hash for my value instead of recalculating as I should be doing
Sam Mohr (Aug 29 2024 at 15:50):So programmers can't assume caching is safe, since they can't presume determinism, nor even force purity in this system
Richard Feldman (Aug 29 2024 at 15:51):Ayaz Hafiz said:
(or if not a type parameter, it's marked in some equivalent way as being effect-polymorphic)
yes, this is what you have to do. if you do this then Parser.map works just as well as List.map
I'm still not following, sorry :sweat_smile:
so here is the type of List.map:
List.map : List a, (a -> b) -> List b
we're saying I can call this as either List.map or List.map!
suppose this is the type of Parser.map:
Parser.map : Parser a, (a -> b) -> Parser b
The type is the same as List.map except List has been replaced with Parser. So that ought to mean I can call Parser.map! - but I can't, because the implementation of Parser doesn't support that (since it stores closures, and the author of Parser did not decide to mark in the type that Parser supports effect polymorphism, instead opting to accept only pure functions.)
Sam Mohr (Aug 29 2024 at 15:51):So unless Ayaz's proposal has some way to prevent the allowance of ! usage for this function, we have problems...
Richard Feldman (Aug 29 2024 at 15:52):so unless I'm missing something, the design where you can opt into calling functions effectfully with ! means that you have to have different types for "this is an effect-polymorphic function" (like List.map) and "this accepts only pure functions" (like Parser.map)
Richard Feldman (Aug 29 2024 at 15:53):at which point from a type syntax perspective, this is actually equivalent to an earlier proposal; you still need to annotate effect-polymorphic functions differently from ones that only accept pure functions
Richard Feldman (Aug 29 2024 at 15:53):the only difference is the addition of an expression syntax requirement
Richard Feldman (Aug 29 2024 at 15:53):(again, unless I'm missing something!)
Sam Mohr (Aug 29 2024 at 15:54):That's how it seems to me. There doesn't seem to be a way to have our cake and eat it too
Ayaz Hafiz (Aug 29 2024 at 16:08):Sam Mohr said:
If I call it with
cachingCalcHash! "abc" cache File.effectfulHash, then the assumption that my(Str -> U64)hasher is referentially transparent is false, and I'll retrieve an old, wrong hash for my value instead of recalculating as I should be doing
There are derivative options here, like putting the bang on File.effectfulHash specifically. To be clear I'm not saying putting the bang on the callsite is a good idea. I'm just saying that I think avoiding polymorphism in the surface syntax is super important for the end DX.
Richard Feldman (Aug 29 2024 at 16:12):surface syntax as in the type annotations?
Ayaz Hafiz (Aug 29 2024 at 16:12):yes
Richard Feldman (Aug 29 2024 at 16:14):I think the only design we talked about which achieves that goal is the one where "all instances of -> in a function type automatically have the same effect type variable"
Ayaz Hafiz (Aug 29 2024 at 16:14):i don't think you need effect variables at all though
Ayaz Hafiz (Aug 29 2024 at 16:14):one sec
Richard Feldman (Aug 29 2024 at 16:19):but then if I put this into the repl, what's the inferred type?
\fn1, fn2 ->
(fn1, fn2, (\arg -> fn1 "$(arg)!"), (\arg -> fn "$(arg)!")))
in all the current designs, the inferred type would be:
(Str -fx1-> Str),
(Str -fx2-> Str)
-> (
(Str -fx1-> Str),
(Str -fx2-> Str),
(Str -fx1-> Str),
(Str -fx2-> Str),
)
because the outer function doesn't call either of the functions it receives, it just passes them trough and creates new functions with them, none of which are effectful
Ayaz Hafiz (Aug 29 2024 at 16:19):Richard Feldman said:
at which point from a type syntax perspective, this is actually equivalent to an earlier proposal; you still need to annotate effect-polymorphic functions differently from ones that only accept pure functions
No, I don't think you need to do this.
In my original example that was quoted in this thread, effect polymorphism is entirely hidden from the user. Every arrow -> is potentially effect polymorphic. Effectful calls are determined at the call site.
Parser.map! is totally fine if you pass an (a -> b) that is effectful. If it's not, and the parser itself is polymorphic or pure, the compiler can tell you that you should just do Parser.map because that call is either polymorphic in its effectfulness or not effectful.
Now suppose that the concrete parser being passed to map is itself effectful - not polymorphic, it definitely contains an effectful function somewhere. Okay, now the compiler can tell you again that you need to call Parser.map!, and because provenance is trivial to trace here, tell you exactly why.
Maybe there's a separate question about whether there should be a specific type annotation or something if you know a function or type alias like Parser is definitely effectful. Let's say that's signified as Parser! a or foo -> bar! if at all. But this is a tangent.
The alternative here is that you have functions that start to look like this
doSomething : Parser a fx -> ...
doSomething = \p ->
Parser.map p f
and IMO this is not better than eliding the fx type variable entirely, because fx tells me nothing - it's either effect polymorphic or it's not. Of course, the upside to that is that you will define a Parser that is only ever pure. But then I think it's really easy to end up in a world of
Parser a # this is the pure one
ParserM a fx # need effects? use this one
i mean there can be type variables but they don't need to be shown to the use
Ayaz Hafiz (Aug 29 2024 at 16:20):user*
Richard Feldman (Aug 29 2024 at 16:25):Ayaz Hafiz said:
Every arrow
->is potentially effect polymorphic. Effectful calls are determined at the call site.
Parser.map!is totally fine if you pass an(a -> b)that is effectful.
the thing I'm missing here is that if I call Parser.map! and that gives me back a Parser b, and that parser is now secretly effectful but I have no way of seeing that in the type...then later on when I call "hey actually parse some input with this Parser b that's been threaded through a bunch of functions" I'll get a surprising type error saying "hey that actually needs to be parse! and not parse because you gave me an effectful Parser even though you had no way of telling from the visible type that it was effectful"
Richard Feldman (Aug 29 2024 at 16:25):or am I misunderstanding the idea still?
Ayaz Hafiz (Aug 29 2024 at 16:26):Sure, so that's the separate question I mentioned about whether there should be a specific type annotation or whatever if something is monomorphically effectful. Like maybe Parser becomes Parser! or whatever if it's always the case it comes out with an effect
Ayaz Hafiz (Aug 29 2024 at 16:26):but you don't need this either to be honest
Richard Feldman (Aug 29 2024 at 16:27):it seems like if the type of Parser.map is:
Parser.map : Parser a, (a -> b) -> Parser b
...and that's enough to know that I'm allowed to call Parser.map! with an effectful function, resulting in an "effectful parser" which will run effects when I tell it to parse something, then that's not reflected in the type of Parser
Ayaz Hafiz (Aug 29 2024 at 16:27):because the type inference is full and the compiler can just tell you when you call something that is monomorphically effectful without a bang (or however you want to denote it at the call site)
Ayaz Hafiz (Aug 29 2024 at 16:28):Again, i'm not saying putting the effectfulness marker at the call site is a good idea, another alternative is to have -> for all functions and denote monomorphic effects only in the type, like Str -> Str!
Richard Feldman (Aug 29 2024 at 16:29):right, but then now I have my Parser b (which lets's say is Parser Foo concretely, like that's what the Parser.map returns) and I hand it off to a bunch of functions, and then much later I'm like "hey I have this pure function which wants to apply this Parser Foo to a string" and the compiler is like "nope, sorry, that's an effectful Parser Foo" and I'm like "how was I supposed to know that?" and the compiler is like "you're not, it's invisible and I'll just tell you when you make a mistake"
Richard Feldman (Aug 29 2024 at 16:29):Ayaz Hafiz said:
Again, i'm not saying putting the effectfulness marker at the call site is a good idea, another alternative is to have
->for all functions and denote monomorphic effects only in the type, likeStr -> Str!
as in like expose 2 versions of each function, one effectful and one pure? (so kinda like today with Task)
Ayaz Hafiz (Aug 29 2024 at 16:30):No, the bang is only if it's monomorphically effectful
Ayaz Hafiz (Aug 29 2024 at 16:31):I mean I hear you on the invisible-ness being weird, maybe that's a good reason to put the bang in the type. But also the fix is trivial and the compiler will tell you exactly where to do it.
Ayaz Hafiz (Aug 29 2024 at 16:31):i don't think i have the right answer here for sure
Richard Feldman (Aug 29 2024 at 16:31):Ayaz Hafiz said:
I mean I hear you on the invisible-ness being weird, maybe that's a good reason to put the bang in the type. But also the fix is trivial and the compiler will tell you exactly where to do it.
yeah I definitely don't like the idea of not being able to look at a type and know what I can do with it :sweat_smile:
Ayaz Hafiz (Aug 29 2024 at 16:32):but i think it's worth really pushing on avoid user-visible polymorphism to whatever extent possible. Having two dimensions to the type system is going to be brutal.
Richard Feldman (Aug 29 2024 at 16:32):I'm definitely a lot less concerned about that personally :big_smile:
Ayaz Hafiz (Aug 29 2024 at 16:33):I think we really need to avoid any possibility of this though
Parser a # this is the pure one
ParserM a fx # need effects? use this one
I mean it's often surprising what things turn out to be intuitive vs not to people, but it doesn't feel like "there's a type variable which tells you whether it's pure or effectful" is that complicated
Richard Feldman (Aug 29 2024 at 16:33):well yeah I mean in the case of a parser I'd just only offer the pure one personally
Richard Feldman (Aug 29 2024 at 16:33):an effectful parser sounds like a footgun to me :sweat_smile:
Ayaz Hafiz (Aug 29 2024 at 16:34):i agree, but not allowing things to splinter like this if it can be avoided is also worth pushing for
Ayaz Hafiz (Aug 29 2024 at 16:34):Richard Feldman said:
I mean it's often surprising what things turn out to be intuitive vs not to people, but it doesn't feel like "there's a type variable which tells you whether it's pure or effectful" is that complicated
I get this, but I think it's a compounding thing. With all the other features in the language, it can be a lot
Richard Feldman (Aug 29 2024 at 16:35):I think the incentives around the "only use polymorphism in the most powerful and rare cases like walk and parallel" design are good
Richard Feldman (Aug 29 2024 at 16:35):yeah it's for sure a good thing to be mindful of! :100:
Ayaz Hafiz (Aug 29 2024 at 16:35):like 100% I hear you. For me and for us, i think an extra type variable here and there isn't a big deal, and we know how to weigh off tradeoffs in walk vs map vs parallel etc. quickly
Richard Feldman (Aug 29 2024 at 16:36):yeah I think for is an important part of this
Ayaz Hafiz (Aug 29 2024 at 16:36):but if you don't want to think about these things, the pit of success should still be there
Richard Feldman (Aug 29 2024 at 16:37):because one of the things we've seen repeatedly is that if things Just Work the way people expect them to, even if they don't have a completely accurate mental model of what's happening (e.g. with open tag unions and the ! suffix) that can still be a much better experience for them than an objectively simpler design that doesn't work the way people expect it to
Ayaz Hafiz (Aug 29 2024 at 16:38):Like for could cover the List.map or walk use case, but it's still an additional piece you have to know about - and having multiple ways to do things can make it difficult to decide what you prefer. And if you are familiar with List.map, it is just as easy to write list_mapM and use that
Richard Feldman (Aug 29 2024 at 16:38):and although List.map only accepting a pure function isn't as flexible as having it be effect-polymorphic, I think a compiler error message of "hey List.map takes a pure function and you gave it a function that's doing an effect because of this call inside it: _____" is super easy to understand
Ayaz Hafiz (Aug 29 2024 at 16:39):I agree
Ayaz Hafiz (Aug 29 2024 at 16:39):But I don't want people to write List.mapM as a reaction lol
Ayaz Hafiz (Aug 29 2024 at 16:40):I just think if the basis in the type system is there to support complexity, complexity will be exploited
Richard Feldman (Aug 29 2024 at 16:40):yeah and I think if that becomes a common thing, it's a symptom that tells us the hypothesis didn't work out as hoped and we should reevaluate :big_smile:
Ayaz Hafiz (Aug 29 2024 at 16:40):e.g. Haskell, and why abilities are so constrained in Roc even though it doesn't let you do some things you might want like iterators
Richard Feldman (Aug 29 2024 at 16:40):Ayaz Hafiz said:
I just think if the basis in the type system is there to support complexity, complexity will be exploited
I would say complexity will be explored, but the most complex thing doesn't automatically become popular (let alone pervasive) just because it's possible
Richard Feldman (Aug 29 2024 at 16:41):people like ergonomic things, and that's super subjective
Richard Feldman (Aug 29 2024 at 16:41):oftentimes the simpler thing becomes the thing everyone uses because people prefer the (subjective) ergonomics of it
Richard Feldman (Aug 29 2024 at 16:41):but yeah, in the general case people will definitely experiment with pushing the complexity limits of what the type system supports :big_smile:
Sam Mohr (Aug 29 2024 at 16:44):I'm that complexity pusher with record builders. Weaver has done some super "awesome" stuff making a flow graph of required argument parsing order, but that complexity doesn't necessarily make the ecosystem better in general. Don't give us complexity, we'll use it immediately
Richard Feldman (Aug 29 2024 at 16:46):I think you could make a strong case that (because of its macro system, dynamic typing, and general permissiveness around side effects), people would make much more complicated APIs in Clojure than in Haskell
Richard Feldman (Aug 29 2024 at 16:46):but in practice it seems to be the opposite
Ayaz Hafiz (Aug 29 2024 at 16:48):I agree Richard! And we should facilitate simplicity and elegance, even when it’s really difficult (as in this case). I’m not feeling that the model of effects has the necessary complexity being described. I think a lot of it is incidental to perceived benefits.
I would encourage anyone who hasn’t used algebraic effects to try them out in Unison or OCaml, write a small project or two. i think this is the only real way to experience what they give you and how they change writing software for you. i think without similar experience with structural types and type classes in other languages we could not have come to the decisions we have today.
Notification Bot (Dec 04 2024 at 04:57):25 messages were moved from this topic to #ideas > Streaming parsers designs + Effect polymorphism by Eli Dowling.
Last updated: Jun 16 2026 at 16:19 UTC