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

Exotic Programming Ideas, Part 3: Effect Systems

stephendiehl.com

Post reply on HN
Print view View original

41–50 of 95 posts

Re: Exotic Programming Ideas, Part 3: Effect Systems

#41

Post by skybrian »

daanx wrote: post #37
skybrian wrote: post #35

Earlier quoted context omitted.

I'm wondering if you've found it useful in practice to distinguish between total and possibly-diverging functions? It seems like it's the sort of thing that's useful in something like Agda, where you use the existence of a function (without running it) to prove that its result exists. (The type is inhabited.) Or so I've read; I haven't used it. But if you're going to run the program, you typically want to know if a f…

In practice , I have not (yet) found many great use cases for the distinction in Koka. It is nice to have "total" functions, but "pure" (exceptions+divergence) is still a good thing (and what Haskell gives you). And like you say, in practice we can easily have functions that just take a long long time to compute. Still, it is a good extra check and I can see more use for the `div` effect for future verification tools…

Good to know. At compile or verification time, it seems like you could get the same problem again, though? We want our compiles to finish promptly, and a slow, total predicate could hang.

Which is to say, a possibly-diverging function seems okay to use even by a verification tool, so long as it finishes quickly in practice. Having some notion of analysis-time-safe predicates seems useful but it doesn't seem to map cleanly to being able to prove termination?

Re: Exotic Programming Ideas, Part 3: Effect Systems

#42

Post by skybrian »

shthrow wrote: post #33
skybrian wrote: post #28

Earlier quoted context omitted.

You're saying it's not a problem, but let's say you didn't think ahead and want to add tracing later, and there are many intermediate function calls between top level and the place where you want to trace. You still have to change every function signature to add the colors, right?

No, think of it like checked exceptions, you only need to handle the effect _at most once_ before it reaches the top (it's up to you to let it keep getting passed up or handle it immediately), otherwise the compiler will automatically infer the effect types in the layers between.

Okay, so type inference is the vital feature here.

It can help in a closed code base. In an open code base, you could inadvertently change a public API, breaking callers that are unknown to you, if the type signature of something public is inferred.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#43

Post by AaronFriel »

skybrian wrote: post #28
AaronFriel wrote: post #21

Earlier quoted context omitted.

A properly done effects system with type-level annotation of the "color" of functions helps this, rather than hurts as you might surmise. Take for example logging or tracing - we almost always in a modern backend application want an ambient trace or span ID and a log destination. What we don't want is to have to add those as parameters to _every function_. So we want to paint these functions with the "logger" and "tr…

You're saying it's not a problem, but let's say you didn't think ahead and want to add tracing later, and there are many intermediate function calls between top level and the place where you want to trace. You still have to change every function signature to add the colors, right?

In a language and type system where the compiler infers all of the intermediate types, no.

The way effect systems are typically added to languages without this level of type system is that the effect "fails". Like making a database call in Python without "with use_database(...):" that provides the database context. In those languages and with those effects, typically the default behavior is the effect's methods are always available, but may either be a no-op/return a nullish value or throw an exception.

As an example, the way tracing works on Node.js is that you have to explicitly declare a span (or use a plugin for a framework which does that for you) and inside that span, you can do something like getSpanId() and it'll return a value. Outside a span, it returns null.

The worst case scenario is you have a language and framework where it's both difficult to annotate the types and difficult to provide some ambient context. In those cases, you're back to (essentially) passing your trace span, your logger, etc as arguments to every function again. Not ideal.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#44

Post by skybrian »

lalaithion wrote: post #39
skybrian wrote: post #27

Earlier quoted context omitted.

There is the specific issue with async functions, but that's only one example of a general problem, what I'm calling "function coloring." Workarounds are often possible, but they are still workarounds and often result in bad code. We've been there with Java. An API takes a Runnable. You need to do something that does IO, so you catch the exception... and then what? Log and suppress it? This is how bad code happens. A…

Nothing prevents having a type system capable of dealing with those problems. Yes, Java and Golang make this difficult, but if you have a language that supports it, there's nothing which prevents writing an API that says "Whatever the effects of the Callable you passed me are, I also perform those effects".

Introducing generic types doesn't make the function-coloring problem go away.

Now, instead of having a single function that has some effects, you have a family of closely-related functions, each with different effects. These functions are incompatible with each other. The function-coloring problem has gotten worse! :)

(Generic types are still useful though.)

Re: Exotic Programming Ideas, Part 3: Effect Systems

#45

Post by andrewflnr »

ianbicking wrote: post #18

I've had this idea of "dynamic returns" (akin to dynamic scope) in my head for a while. Reading this, it feels like a dynamically typed companion to effect systems. The idea of a dynamic return is just to give a formal way to accumulate things during a set of function calls, without having every function to be aware of what might be happening. In Python context managers are often used for this (e.g., contextlib.redir…

I don't even see anything essentially type-based in effect systems. You could totally have effect-style APIs in dynamic languages, they just wouldn't be tracked and checked up front. I expect this has already been done a few times in Scheme.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#46

Post by klodolph »

There's some interesting research and ideas here, but it does seem like monads "ate everything for lunch" back in the late 1990s and 2000s when it comes to encoding effects, probably because monads are a bit more ergonomic (which seems like a weird thing to say, given the reputation monads have for being abstract nonsense). So effect systems didn't get as much research as everyone was interested in monads, and now that monads have dried up a bit as a field of research for encoding effects, I'm interested to see what other systems people invent.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#47

Post by skybrian »

Quekid5 wrote: post #34
skybrian wrote: post #30

Earlier quoted context omitted.

Refactoring tools are nice so long as you are in a closed-world environment where you can see all the code and make whatever changes are needed. They don't help nearly as much in an open environment where there are many code owners and not all code is visible to you. When you publish a library, a refactoring tool isn't going to tell you everyone who uses your library, and you don't have permission to change the call…

I mean... if you're fixing a broken API, you're going to have to bite the bullet either way -- papering over it isn't going to fix anything... it just hides the problems. With a type system which understands effects, at least the compiler can give you very accurate help in fixing call sites.

It does help by telling you what's wrong. But in a way, increased precision makes the problem worse.

Suppose you have have a language with two categories of functions, those that can fail (returning an error) and those that can't.

It's nice that within the "functions that can fail" category, you don't have to worry about what kind of error it might be. Error propagation can happen in a generic way. Adding a new kind of error doesn't change any API's.

If instead, you have different kinds of errors and declare them everywhere, you end up with a situation like Java's checked exceptions. The problem is being too precise, which doesn't leave room for changes later.

Similarly, we could be very generic about effects. Maybe we could just say "this function has effects" and treat them all the same? By not being precise about what the effects might be, we aren't promising too much, so we allow ourselves room for change.

The downside is that the caller has to assume any effect is possible. This is a fundamental tradeoff between caller and callee convenience. You need to be specific enough for the caller to be able to deal effectively with the effects you declare, but not too specific, or you're painting yourself in a corner.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#48

Post by dan-robertson »

AaronFriel wrote: post #43
skybrian wrote: post #28

Earlier quoted context omitted.

You're saying it's not a problem, but let's say you didn't think ahead and want to add tracing later, and there are many intermediate function calls between top level and the place where you want to trace. You still have to change every function signature to add the colors, right?

In a language and type system where the compiler infers all of the intermediate types, no. The way effect systems are typically added to languages without this level of type system is that the effect "fails". Like making a database call in Python without "with use_database(...):" that provides the database context. In those languages and with those effects, typically the default behavior is the effect's methods are a…

In every language I’ve used where types can be inferred, almost everyone writes down the types of their top level functions (or at least the functions that are exposed to clients). I don’t think this is really a good counter argument.

The only ways I know of to reliably make this kind of change (or just about any nontrivial change) to an interface are increasing version numbers and letting clients suffer or having a monorepo and fixing all the clients yourself

Re: Exotic Programming Ideas, Part 3: Effect Systems

#49

Post by fiddlerwoaroof »

deckard1 wrote: post #38
patrec wrote: post #22

Earlier quoted context omitted.

Well, certainly no one seems to understand how e.g. syntax-case works. But my impression is that macro hygiene in itself is a solution looking for a problem. The key advantage e.g. racket's macro system has over clojure or common lisp is not hygiene but being sufficiently well structured and rich to allow proper tooling. Good error messages with accurate locations >> macro hygiene.

> macro hygiene in itself is a solution looking for a problem No. Unless you're not familiar with Lisp-1 vs Lisp-2. In Scheme, you would have to GENSYM every variable in addition to every function you call within a macro. Whereas in Common Lisp you just need to GENSYM the variables. That's the real reason Scheme doesn't use DEFMACRO. I'm not personally a fan of any hygienic macro system because learning a new languag…

The problem with Ruby’s method missing is mostly that Ruby development generally doesn’t happen in an environment where discovering the existence of that method is easy. Macros are even better and tools like the slime macrostep expander make them relatively easy to deal with.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#50

Post by no_wizard »

lalaithion wrote: post #25
skybrian wrote: post #6

I expect that, as with any other type system extension, the more granular your effects are, the more likely you are to run into a “what color is my function” problem. If you have a public API that declares certain effects, you’re stuck with those unless you break backward compatibility. In a practical system, when writing a library and especially an abstract interface, you’d want to be careful what you promise and de…

The "what color is my function" problem is insurmountable in Javascript, because the runtime does not allow you to call an async function from a non-async one. However, most effects aren't like this. If you say "this function needs randomness" then you can create a pure PRNG and call the function with the PRNG providing randomness. If you say "this function needs logging" you can tell it to log to a string and parse/…

I think the reactive/rx/observer patter might be an acceptable solution around the what color is my function problem and it tends to be very popular with the functional programming wing of the JS community from what I’ve seen.

Never understood why the browser didn’t ship a full access to something like an EventEmitter. Since you can dispatch events on window document DOM elements etc seems like being able to subscribe to events in a more arbitrary fashion that worked in parallel to the other events would have been useful and solved callback hell all the same

Post reply on HN