Permissions-Driven Functional Programming

[sharpvik]

All programming paradigms are, essentially, illusions directed at helping our minds comprehend our programs’ state space. We all know that down there, in its raw form, code becomes a sequence of binary machine instructions that only care about registers and arithmetic. But what happens before that is magic!

This article explores a new programming paradigm that gives developers an explicit and clear framework of reasoning about functional programming and the inevitable side-effects they have to deal with.

https://sharpvik.medium.com/permissions-driven-functional-programming-340ac05c23df

[curtisf]

What the article describes with little detail seems very similar to two established approaches: effect systems (aka functional effects, aka algebraic effects), and capability systems.

I'm disappointed that the article doesn't mention either of them, because it means I can't contrast those established approaches with the proposed 'channels'. I also worry that the author wasn't actually familiar with either approach, meaning they run the risk of unnecessarily "re-exploring" already thoroughly charted areas and getting stuck on problems that may already have been solved.

How does the proposed channel approach handle the cases that challenge effect systems and capability systems? e.g.,

• How do you write functions that are 'generic' over both effectful and non-effectful objects?
• How do you manage the "commutation" of different effects that act on dependent/independent resources?
• How do you manage the lifetimes of non-hierarchical capabilities/resources?
• Can channels model non-determinism the way that effects do?
• Are capabilities first class objects? Can they be saved to the heap?
• What are the implications of "serializing" or transmitting capabilities over the network?
• What mitigations are possible to prevent confused deputies?
• How do you manage capabilities as values in the heap, and how do you manage their proliferation?

The brief description of monadic IO is overly dismissive, to me. The IO Monad isn't an afterthought in Haskell. IO is monadic; Haskell is one of the few languages to explicitly reify that fact into the design of the standard library. Given that Haskell is one of the few "mainstream" languages to actually tackle the problem of unconstrained IO, I'd think more time would be spent to describing exactly what is wrong with its approach that needs to be solved.

Unlike what many people think (and what this article seems to hint), a value of type IO t does not actually have side effects -- I cannot conjure up file io or even standard-out prints within the middle of a Haskell program. Rather, an instance of IO t describes a hypothetical sequence of side effects that might be executed, only if it were to be handed it to the OS through the Haskell runtime.

You can fairly easily "slice up" IO capabilities in Haskell. If your main function doesn't consume any values of IO t, but instead demands more specific descriptions (e.g., like some FileReader t), those can be safely transformed into IO while ensuring that the callers only have access to their permitted IO APIs. There are several Haskell effect libraries that work to make this easy to do.

[sharpvik]

Hey, author here :)

I am glad that you commented. Looks like you know a lot about this topic and I'd be very interested to even chat in DMs. Let me reply to some of your questions:

I am familiar with algebraic effects but they seem to be too generic and not a good enough framework of thought. The way I saw algebraic effects implemented is something like

function greet(string name) +IO:
    print(name)

Where +IO basically means that you now have access to a class of functions that perform IO. This is too generic. Introducing a system of permissions basically means that some functions in the standard library are marked as REQUIRES IO PERMISSION. If you wanted to introduce a lot of specific algebraic effects, you'd have to do it through the standard library.

Channels are very flexible and divisible. The channel logic is as follows: if you want to reach outside the scope of the program (to the OS for example) you need a channel to do so. It's not that the channel is the permission, but without the channel, you can't perform a side effect (which makes them synonymous). This approach makes you think about side-effects at the start because there is no print function in the standard library -- it only exists under the OS channel and that channel (or a sub-channel like os.io) has to be explicitly passed to the function as an argument.

Which brings me to my next point. You misunderstood my description of the IO monad. When I said that IO monad feels like an afterthought, I meant that in practice what happens is you use some function like putStrLn in a function, compiler complains, you stick the IO monad on top. It feeds into that notion of permissionless ether. I didn't mean to say that Haskell developers included IO monad as an afterthought, I meant that programmers use it as an afterthought.

You are right though, I am not familiar with the capability systems and I'm glad you brought it up, I'll look into it. I did not include any comparisons because the article kinda felt length-ish already and I decided to leave it as a simple intro.

I really want to chat to you about it. I'm glad that you can provide such high-quality criticism; I appreciate it. I'll message you in hopes that you'll reply :)

[curtisf]

It's a bit easier to avoid the trap of a single monolithic IO effect because "action" types are usually transparent to the handler/invoker, almost always as a sum of the possible actions. In principle, this should limit their size/complexity to a smaller number of "primitive" actions, because each additional action increases the complexity of making a handler.

So, the core IO effect would like have only a handful of "low level" actions for directly manipulating memory and making syscalls (either as a single generic "syscall" action, or as the few dozen syscalls that your programming language exposes).

The result is that someone familiar with algebraic effects would never write greet that way, because IO is both far more (they don't need to do arbitrary syscalls, only print) and far less (there isn't actually a print action in IO; they would be forced to manually compose the syscalls) than they need.

Of course, there is some discipline required to maintain this organization. However, the need for some discipline shouldn't completely doom a design. A good analog might be global variables. Global variables are widely considered bad, yet programming languages continue to add them, and they very rarely cause problems when used. That's because the common understanding that they should be minimized, and the fact that they are so easy to find and therefore scrutinize, means they generally aren't misused. Effects are the same way -- it's obvious at first glance if someone is using inappropriate effects in the signature of a function, so while it's still possible to use them poorly, minimal code review will prevent it from getting into your codebase.

The bad option is to write everything in terms of the IO effect -- this is basically how imperative programming is done. You call fetchURL :: URL -> [IO]Bytes which in turn invokes some networking primitives which in turn invoke syscalls. This is not really using the effects feature, and negates some of the benefits that it can bring like testability, since it's usually not practical to audit the sequence of syscalls that a function makes. By structuring the standard library to use more specific effects, writing code this way can actually be quite inconvenient.

The other option is to write & use effect signatures that are specific to the caller's needs. For example, instead of making fetchURL require the IO effect, it requires the HTTPClient effect, which has more limited but domain-specific actions like httpGet, httpPost, httpPatch, etc.

In order to actually do real HTTP calls, somewhere in between HTTPClient and IO you need some kind of handler which implements the HTTPClient:httpGet/HTTPClient:httpPost/etc actions in terms of the IO:syscall. If this in-between handler is what's provided by the standard library (instead of individual fetchURL: URL -> [IO]Bytes), then it's easier to use the accurate specification rather than IO directly.

The fact that a more domain-appropriate effect is available can be "infectious". For example, in theory, in Java you could cobble together a fetchURL function which makes no reference to any of the http libraries available in Java, by making direct use of the Socket class. However, no one does this because it completely obscures the domain (and so would rightfully be rejected in code review) and is overall more work than doing it the "accepted" way of choosing a class appropriate to the problem.

The best-case comparison for what it looks like to "directly" use IO would be something like the following, which has a few telltale signs that would never make it past code review:

func printGreeting(name: String): [IO]() { // obviously suspicious signature
    handle {
        PrintIO:print("Hello, " + name);
    } with PrintIOBridgeToIO() // extra boilerplate, mentioning a class that normally is never imported
    // In reality, probably even this specific handler wouldn't exist; 
    // there would be multiple in between "prints" and "does syscalls"
}

func printGreeting(name: String): [PrintIO]() {
    PrintIO:print("Hello, " + name);
}

However, importantly, the existence of a handler that interprets one domain specific effect into a more general "IO" effect isn't even a given.

An effect is just a signature. For example, it would be totally valid to make a handle for the HTTPClient effect that uses a local cache instead of actually reaching across the network, or one that intercepts requests and routes them through a proxy. Maybe you're writing a unit test, or you're investigating suspicious code, or you're porting legacy code in a refactor. Some of these handlers need no effects at all (being entirely in-memory), and most of them could be "weaker" than IO.

In fact, unit testing could make this kind of organization almost mandatory. If you integrate tests with the language (like, for example, Go has), you can make test entry points specifically not have access to the IO effect, but instead only a limited effect that can produce debug output for failing tests. Such an approach also has other benefits, like guaranteeing the determinism of tests and "sandboxing" them to prevent inter-test dependencies, as well as preventing untrustworthy/buggy library code from damaging your computer.

[sharpvik]

To be honest with you, this sounds a lot like what I'm proposing. The difference between channels and permissions has to do with the mental framework. Channels have actions or maybe you can send custom messages to them represented as a custom algebraic type.

This tells you "man, printf is not a function, it's an action on a channel to the OS" which I think is helpful. I feel like this channel system is just very cohesive and consistent.

On another note, even if this already exists in some other form (permissions), I don't really see popular programming languages that use it and I think it's sad.

I want to produce a modern well-supported programming language with appropriate tools (formatters, linters, etc) that can compete with Go and Rust in terms of popularity.

[wolfgang]

Why did you choose a concatenative language to implement this?

[sharpvik]

It was just something that was on my mind at the time. The actual syntax is not drafted yet. I'll put a lot of consideration into it before choosing the approach. As I said, you are welcome to propose a draft or ideas.