Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algebraic Effects for the Rest of Us

overreacted.io

Post reply on HN
Print view View original

51–60 of 91 posts

Re: Algebraic Effects for the Rest of Us

#51

Post by mrkeen »

tome wrote: post #42
captaincrowbar wrote: post #22

Earlier quoted context omitted.

‘Non-IO functions can't call IO functions.’ How do you handle logging then? If f() calls g(), how can I add logging to g() without having to change or recompile f() (and everything in the call stack above it)? ‘You can’t’ is not an acceptable answer.

Not sure why people are saying "you can't" when it seems to me the whole point of algebraic effects that you can. You can define g so that it has no ability to do "general IO", all it can do is yield log messages. Then f can call g in a way that turns the log messages into writes to stdout. For example, here's how you would do it in Bluefin: type Log = Yield String -- workWithLogging cannot do arbitrary IO! -- All it…

"You can't" is simpler, because the inevitable reply is "but how do I do actual logging inside g"

Re: Algebraic Effects for the Rest of Us

#52

Post by sirwhinesalot »

tome wrote: post #50
sirwhinesalot wrote: post #49

Earlier quoted context omitted.

They're really just a protocol. You can implement them in various ways. They will always be some sort of delimited continuations but a "function call" or continuation passing style or anything of the sort does not have to be involved at all. For example, let us say I don't allow "multi-shot" continuations like in your library, and I'm implementing Algebraic Effects in my own interpreted language. One way I can implem…

> They're really just a protocol. Thanks, that clarifies where you're coming from. Is it possible to specify this protocol somehow, by defining an interface for it? Or by extending lambda calculus with the bits it needs? (Maybe that's what the Koka folks do in their papers, and if so feel free to say, "yeah read their papers").

I'm thinking a less formally than that. Protocol in a very layman-y "perform is supposed to do this, resume is supposed to do this".

For example, Koka compiles handlers differently depending if they do multi-shot continuations or not. It can do this because all that matters is "perform is supposed to do this, resume is supposed to do this", not what they turn into (same as "if" turning into "cmov" in certain cases). I think it uses a continuation-passing style sort of implementation, but I can't quite remember.

Daan's libhandler implements effects for C in an entirely different manner. It captures the stack much like my example or a stackful coroutine library would.

I'm sure there a formal definitions in both the koka papers and the libhandler paper, but I just skim that stuff ;)

Re: Algebraic Effects for the Rest of Us

#53

Post by tome »

_old_dude_ wrote: post #40
bazoom42 wrote: post #15

So this looks like dynamically scoped callbacks. Instead of passing callbacks along as parameters they are declared as “handlers”, and any function down the call stack can invoke them. Is this a correct understanding?

You need more than that for the example with setTimeout(). It requires to be able to freeze the stack and then go back later. You need stackful coroutine (like goroutine) for that.

That's very interesting, thanks! It gave me a brainwave and I wondered I could implement that in Bluefin. I'm pretty sure Bluefin's Request[1] is a second class stackful coroutine, and sure enough it turns out to be possible, so I'm pleased about that.

    -- ghci> example
    -- Hello
    -- World
    -- Timed out
    example = runEff $ \io -> awaitYield (receiver io) sender
    
    receiver ::
      (e1 
      IOE e1 ->
      Await String e2 ->
      Eff es ()
    receiver io a = do
      r1  putStrLn "Timed out"
        Just r3 -> putStrLn r3
    
    sender ::
      e1 
      Yield String e1 ->
      Eff es ()
    sender y = do
      yield y "Hello"
      yield y "World"
      yield y "More"
    
    timeout ::
      e1 
      IOE e1 ->
      Int ->
      Eff es r ->
      Eff es (Maybe r)
    timeout io t m = withEffToIO
      (\effToIO -> System.Timeout.timeout t (effToIO (\_ -> useImpl m)))
      io

Re: Algebraic Effects for the Rest of Us

#54

Post by tome »

mrkeen wrote: post #51
tome wrote: post #42

Earlier quoted context omitted.

Not sure why people are saying "you can't" when it seems to me the whole point of algebraic effects that you can. You can define g so that it has no ability to do "general IO", all it can do is yield log messages. Then f can call g in a way that turns the log messages into writes to stdout. For example, here's how you would do it in Bluefin: type Log = Yield String -- workWithLogging cannot do arbitrary IO! -- All it…

"You can't" is simpler, because the inevitable reply is "but how do I do actual logging inside g"

"Actual logging" as in direct access to IO?

Re: Algebraic Effects for the Rest of Us

#55

Post by tome »

sirwhinesalot wrote: post #52
tome wrote: post #50

Earlier quoted context omitted.

> They're really just a protocol. Thanks, that clarifies where you're coming from. Is it possible to specify this protocol somehow, by defining an interface for it? Or by extending lambda calculus with the bits it needs? (Maybe that's what the Koka folks do in their papers, and if so feel free to say, "yeah read their papers").

I'm thinking a less formally than that. Protocol in a very layman-y "perform is supposed to do this, resume is supposed to do this". For example, Koka compiles handlers differently depending if they do multi-shot continuations or not. It can do this because all that matters is "perform is supposed to do this, resume is supposed to do this", not what they turn into (same as "if" turning into "cmov" in certain cases).…

> Protocol in a very layman-y "perform is supposed to do this, resume is supposed to do this".

OK, but at the very least it has two primitives "perform" and "resume"? And they're supposed to interact in some particular way?

Re: Algebraic Effects for the Rest of Us

#56

Post by mrkeen »

u1hcw9nx wrote: post #37
brabel wrote: post #27

Earlier quoted context omitted.

The CL condition system always gets brought up when people unfamiliar with effects see effects for the first time (example: https://news.ycombinator.com/item?id=38813484 , another example: https://lobste.rs/s/12m2f0/algebraic_effects_another_mistake ). But while the condition system can do many things you can also do with effects, they cannot do everything. Here's another discussion on this: https://news.ycombinator.…

CL conditions do what you actually need if you program. CL gives you deterministic state, safe resource management etc. Nondeterminism is not a feature you want. Algebraic effects treat the execution stack (continuation) as data, you have total freedom over what you do with it. This flexibility is exactly where you get nondeterminism. This is how logic solvers or probabilistic algorithms work, but you don't want it a…

> Nondeterminism is not a feature you want.

I can get behind the sentiment, but you absolutely need nondeterminism. You can separate the d from the non-d, but only Haskellish languages even attempt it. It's a coarse separation to make (IO vs non-IO), which is where effect systems come in - I guess you can categorise code into more fine-grain buckets. The 'algebraic' part is currently beyond my knowledge.

Re: Algebraic Effects for the Rest of Us

#58

Post by sirwhinesalot »

tome wrote: post #55
sirwhinesalot wrote: post #52

Earlier quoted context omitted.

I'm thinking a less formally than that. Protocol in a very layman-y "perform is supposed to do this, resume is supposed to do this". For example, Koka compiles handlers differently depending if they do multi-shot continuations or not. It can do this because all that matters is "perform is supposed to do this, resume is supposed to do this", not what they turn into (same as "if" turning into "cmov" in certain cases).…

> Protocol in a very layman-y "perform is supposed to do this, resume is supposed to do this". OK, but at the very least it has two primitives "perform" and "resume"? And they're supposed to interact in some particular way?

Yeah, there's three things you're supposed to implement: try/handle, perform, and resume. The names can vary (e.g., perform is often called "raise" or "do"). They have well defined interactions.

I don't actually know what the original paper describing what algebraic effects are supposed to do is, I just know them informally from Koka, Effekt, etc.

Re: Algebraic Effects for the Rest of Us

#59

Post by mjmas »

_old_dude_ wrote: post #40
bazoom42 wrote: post #15

So this looks like dynamically scoped callbacks. Instead of passing callbacks along as parameters they are declared as “handlers”, and any function down the call stack can invoke them. Is this a correct understanding?

You need more than that for the example with setTimeout(). It requires to be able to freeze the stack and then go back later. You need stackful coroutine (like goroutine) for that.

Or in Lua you'd wrap the initial call in a coroutine, possibly with coronest[a] or something similar to make handling the effects at the right layer easier.

And so then the outer code is a loop around coroutine.resume, and the inner code uses coroutine.yield to perform an effect.

[a]: https://github.com/saucisson/lua-coronest

Re: Algebraic Effects for the Rest of Us

#60

Post by tome »

sirwhinesalot wrote: post #58
tome wrote: post #55

Earlier quoted context omitted.

> Protocol in a very layman-y "perform is supposed to do this, resume is supposed to do this". OK, but at the very least it has two primitives "perform" and "resume"? And they're supposed to interact in some particular way?

Yeah, there's three things you're supposed to implement: try/handle, perform, and resume. The names can vary (e.g., perform is often called "raise" or "do"). They have well defined interactions. I don't actually know what the original paper describing what algebraic effects are supposed to do is, I just know them informally from Koka, Effekt, etc.

Interesting, then I wonder if anyone has distinguished them from continuation "protocols" such as shift/reset and prompt/control. Thanks!

Bringing it back to my original point, I guess I'd say that if you already have function calls, exceptions and threading built in to the language then you don't need perform/resume except in niche cases (multi-shot continuations being the only case I know of, but I don't even know of many applications of those).

Post reply on HN