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

61–70 of 95 posts

Re: Exotic Programming Ideas, Part 3: Effect Systems

#61

Post by karlicoss »

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".

And indeed, JS Flow detects such async issues pretty well

Re: Exotic Programming Ideas, Part 3: Effect Systems

#62

Post by jhgb »

merelydev wrote: post #5
siraben wrote: post #3

I highly recommend Oleg Kiselyov's talk titled "Having an Effect"[0] in which he talks about - purely functional model of computation and its pitfalls - Actor model, effectful programming with requests and responses and an implementation in Haskell. - denotational semantics and combining effects. Once you have a model of your language, what if you want to extend it by adding another effect? It forces you to rewrite t…

Source: https://www.reddit.com/r/programming/comments/7wbtg/who_is_o... - Oleg eats lambdas for breakfast - The Y combinator fears Oleg - Oleg knows all the programs that halt on a Turing machine - Oleg is the guy that Chuck Norris goes to when he has an algorithm complexity question - Oleg reprograms his own DNA with Scheme macros - All of Oleg's Haskell programs are well-typed by definition - Oleg can read C++ comp…

  - Oleg can read C++ compiler error messages.
Oh, come on. You were doing so great until this point.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#63

Post by skybrian »

lambda_obrien wrote: post #57
skybrian wrote: post #47

Earlier quoted context omitted.

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…

Honestly, in the Haskell world, no one really complains about broken APIs, it's actually pretty common for a library to change things in a breaking way. People tend to either use Nix or stack to deal with versioning or they just plan to refactor when they have to. I personally just started with Haskell, but I've switched a small tool from one streaming library to another and it was super easy even though each had a v…

Yes, there are easier and harder ways to deal with api migrations. But even in Haskell, isn't "Cabal hell" a thing? And the type of the standard prelude's head function is wrong but it can never be changed.

Dependency migration is the sort of thing that's easy enough in small examples and gets harder as you scale up.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#64

Post by kazinator »

patrec wrote: post #51
kazinator wrote: post #36

Earlier quoted context omitted.

Macro hygiene is a solution to the problem of functions being in the same namespace as variables, together with standard, oft-needed library functions having short names that are easily chosen as variable names.

Well, that's the standard Common Lisper opinion. I don't buy it though -- I don't get the impression that it's a problem in clojure (which does not have scheme-style hygenic macros, but shares the single namespace for variables and functions) either.

The hygiene problem has multiple aspects. One issue is that the user's code can bind identifiers which the macro expansion expects to be predefined.

In a Lisp-1, we have to worry about this:

  (let ((list ...))
    (mac ...)) ;; expansion of mac wants to call (list ...)
Since the macro is not defining anything (its expansion is not introducing a binding for list), the ordinary gensym approach is not applicable.

THe problem persists into a Lisp-2 like Common Lisp, in this form:

  (flet ((list (...) ....)) ;; binding in function namespace
     (mac ...))             ;; wants to use (list ...)
Since local functions are rarer than local variables, and extra care can be taken in how hey are named, Lisp-2 mitigates the problem. Common Lisp goes a step further and makes it undefined behavior if code redefines a standard function (lexically or otherwise).

Hygienic macros solve this aspect of the issue as well. A hygienic (mac ...) can use (list ...) in its expansion. The hygiene mechanism ensures that this calls that list which is lexically visible at the macro definition (probably the global one in the library) even if the target site shadows list with its own definition.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#65

Post by creata »

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?

As Quekid5 said, isn't that the way things should be? Adding tracing is a breaking change, and adding logging inside a deeply nested layer is a breaking change to all the outer layers, too.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#66

Post by ledauphin »

siraben wrote: post #3

I highly recommend Oleg Kiselyov's talk titled "Having an Effect"[0] in which he talks about - purely functional model of computation and its pitfalls - Actor model, effectful programming with requests and responses and an implementation in Haskell. - denotational semantics and combining effects. Once you have a model of your language, what if you want to extend it by adding another effect? It forces you to rewrite t…

I'm way out of my depth here, but interested in trying to understand a few of these things, particularly because I've long wondered how functional programmers reason about the "effects" that happen under the hood when dealing with Turing machines which are essentially 100% state.

Specifically:

1) do you consider variable reference to be an effect because you're getting a value from memory/disk/network? Or is it effectful simply because you're replacing a name with a value somehow? I'd love to understand the point of view here.

2) Relatedly, why do you say that creating a lexical closure is effectful (I assume here that we are storing an immutable memory address, or at least a value which represents a way to reliably find another value in the future), but using it (dereferencing that address/value) is not? I can see why you'd say that creating a dynamic closure is not effectful (the code is essentially unattached to anything at the time of creation and can easily be represented by a pure value), but using it is (it now inhabits a scope and will act differently depending on that scope).

Having typed that out, I wonder if what you mean is that creating the lexical closure in a language with immutable data means that at the time of creating the closure, you are (one way or another) making a copy of that data, which is an input "effect" in a sense. That isn't, of course, how things actually work in most non-functional (e.g. OO) languages - the lexical closure only binds the name, but the value represented by the name could in fact change if the data itself is mutable.

Anyway, I'm still curious about #1 above. These are the sorts of comments I come to Hacker News to read, so thank you. :)

Re: Exotic Programming Ideas, Part 3: Effect Systems

#67

Post by ledauphin »

daanx wrote: post #19
SomeHacker44 wrote: post #8

Earlier quoted context omitted.

...that cannot be determined by the system (and must be specified by the user).

Just to add to this: Koka can (obviously :-)) not always determine if a function will terminate or not so it generally adds a `div` effect whenever there is the possibility of infinite recursion. However, since most data types in Koka are inductive, any recursion over such inductive data types are still inferred to be always terminating. In practice, it looks like about 70% of a typical program can usually be `total`…

these numbers are very useful to me even as a Python programmer, as they (somewhat) line up with my intuitions about how much of our programs can be expected to be written as (Python-) pure transforms, vs imperative shells. It's cool to think about a language being able to tell me this directly.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#68

Post by jiggawatts »

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…

A lot of people are saying that function coloring is essentially an unsolved problem, and this is true. However, coloring of individual functions is not strictly speaking necessary.

Think of the classic "zlib" style C libraries. Often they can't assume anything about the target platform, even basic stuff like memory allocation or I/O, because there's such a huge variety compilers, standard libraries, and restrictions.

So just about every such library exports an "API context" struct, full of function pointers. These then allow the caller to pass in implementations for malloc, free, threading, I/O, etc...

The trick is that these can have default implementations. So the function pointer in the context for allocation can simply point to "malloc()". This can of course be overriden, so the capability is there, but the caller need not do anything by default.

Features like logging and tracing can be similarly sent through to default implementations that do nothing or call standard APIs in some naive (but sufficient) way.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#69

Post by siraben »

ledauphin wrote: post #66
siraben wrote: post #3

I highly recommend Oleg Kiselyov's talk titled "Having an Effect"[0] in which he talks about - purely functional model of computation and its pitfalls - Actor model, effectful programming with requests and responses and an implementation in Haskell. - denotational semantics and combining effects. Once you have a model of your language, what if you want to extend it by adding another effect? It forces you to rewrite t…

I'm way out of my depth here, but interested in trying to understand a few of these things, particularly because I've long wondered how functional programmers reason about the "effects" that happen under the hood when dealing with Turing machines which are essentially 100% state. Specifically: 1) do you consider variable reference to be an effect because you're getting a value from memory/disk/network? Or is it effec…

> 1) do you consider variable reference to be an effect because you're getting a value from memory/disk/network? Or is it effectful simply because you're replacing a name with a value somehow? I'd love to understand the point of view here.

To give an example, say you have int* x. When the expression (*x) is used later on, it is the dereference that is effectful. In other words, the expression lacks referential transparency.

Going further, Oleg says that "an expression is effectful if it sends a message to its context". The example he gives is x+1 being impure, since it sends a request to the context to look up the value of x, whereas (λx. x+1) is pure because λ provides a handler for the request to look up the value of x, and the whole expression can be evaluated without sending anything more to the context.

> 2) Relatedly, why do you say that creating a lexical closure is effectful (I assume here that we are storing an immutable memory address, or at least a value which represents a way to reliably find another value in the future), but using it (dereferencing that address/value) is not? I can see why you'd say that creating a dynamic closure is not effectful (the code is essentially unattached to anything at the time of creation and can easily be represented by a pure value), but using it is (it now inhabits a scope and will act differently depending on that scope).

Creating a lexical closure (see 1:22:30 of the video) involves capturing the environment in which the closure was created. As in #1, the effectful part comes from a request to the context, which is collecting the free variables in the body of the lambda and building the closure. OTOH for dynamic closures you can create them without sending any request to the context, but when you apply it you have to request from the context.

The discussion on the Actor model is very relevant to understand what it means for expressions to send requests to contexts.

Re: Exotic Programming Ideas, Part 3: Effect Systems

#70

Post by codebje »

jahewson wrote: post #15
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…

I always found IOException in Java to suffer from this problem.

Java's checked exceptions aren't (usefully) polymorphic. You can't write, for example:

    R process(ThrowingFunction processor) throws E { ... }
You could write "process" to the Exception base class, but it still can't handle a "processor" that doesn't throw at all.

Checked exceptions a "bolted on" effect that sits outside the usual type system in Java, and their presence on a method signature "colours" it in a way that an effect described inside a type system would not. More of a stain than a tint, if you will.

Java 8 resolved it by quietly pretending checked exceptions never happened, which works fine until (1) you get unhandled unchecked exceptions in all their glory at runtime, and (2) you want to use one of the Java 7 or earlier methods as a "processor" but, oh no, it throws an exception.

(It's a deeper colouring than JavaScript's async/await keyword, which is just syntactic sugar around continuations in callbacks and returning promises - you can pass an async "processor" function to a "process" function that has no idea what it's getting and get back the promise you'd expect from it.)

Post reply on HN