alma
alma copied to clipboard
Reasons for modules
Issue #302, that enormous discussion that hovers around fexprs and Kernel but sometimes veers out into the unknown and asks really deep and important questions about computation itself (and how it's managed to manifest itself in our timeline's history of programming languages), contains the following paragraph (by me, replying to @raiph):
This week, as I've been pondering writing this down, I've been struck by something else, which I'm at even more of a disadvantage to express clearly: namely, how practically every major innovation or focal point in computer science manages to place itself on a spectrum between lambda and process: functions, co-routines, libraries, modules, tasks, threads, OS processes, cores, processors, network nodes, services... all of them "proto-actors" in the sense that they stake out some things that are separate, and others that are shared. Actors go the whole hog, jumping to the obvious end point where everything's separate. Only asynchronous messaging remains. The proto-actors are of course still interesting to study on their own, but maybe partly because they help tease out different aspects of actor separation.
I'm on vacation, so I thought I would tackle this "tower" of abstractions, describing them one by one. I will try to do all of them justice, extracting both their angelic "essence" or perfect form of each feature — what remains, in a sense, when you don't have to be all that concerned with the inconveniences of actual implementation — and also their demonic "substance", the imperfect form of each feature — what inevitably happens when you try to trap it in a machine.
(As a concrete example: the angelic essence of functions is something like the isolation guarantees and re-use that they give you, whereas the demonic substance is what leads to stack overflows or references outliving their stack-allocated data.)
As much as possible, I will also refer to real actual languages out there, especially when they make for pure exemplars of the feature.
I will try to get through all this in a single evening, aiming for coherence of thought rather than comprehensiveness. I'm not 100% sure what I will get out of this, except that I'm hoping to have a better overview afterwards of these different rungs on the abstraction ladder:
- Functions
- Coroutines
- First-class functions
- Continuations
- Modules
- Types
- Packages
- Containers
- Components
- Communicating Sequential Processes
- Actors
There is still a clear connection with Alma: during the design of Alma I've sometimes encountered parts of the challenge of introducing these things into a language. (Maybe most keenly felt with modules and types, but also to some extent with coroutines.) I'm not saying that this issue will provide any insights that I wish I'd had earlier, but... it's something to aim towards, I guess. Or if not insights, then at least a much-needed vantage point.
This issue is called "reasons for modules", which is not a particularly good name. But it's how I've been thinking about it — modules sit somewhere towards the middle of the ladder of abstractions, and the word "module" means different things to different people, but they are the prototypical thing which helps bring structure and separation to a program. In some vague sense, all the features on the abstraction ladder are modules, of one kind or another.
Functions
I've written "Functions (units of functionality)" in my notes. I'll have "units of <noun>" written down for each of the rungs on the abstraction ladder, but I realize that those easily become just empty words, so let me try to back it up: you put code inside a function, and that code forms a unit.
In the early days of assembly code, the whole code section was a single thing, and there was no strong syntactic boundary separating a function from its outside. It all ran on convention. When you went through the motions of jumping back to what called you, that's when the function ended. It was an easy thing to jump into the function at different starting points — somewhat weakening (what we now think about as) the integrity of the function boundary.
I recall vividly that in Knuth's TAoCP books, the MIX machine uses as its calling convention a kind of self-modifying code which sets the return address of the caller on the jump instruction at the end of the function. (Yes, really!) MIX is and old standard, and that particular design decision didn't stand the test of time — indeed, the newer MMIX architecture uses a more traditional stack-based approach. More on this under "First-class functions", below.
Functions provide a rudimentary separation of concerns. Many of the programs in "BASIC Computer Games" just ran on and did what they did with GOTOs. Maybe there was the occasional GOSUB and RETURN; I'll need to go back and check. If there was, it was still not fundamentally more "bundled up" into individual functional units than assembly code.
In the paper The Use of Sub-Routines in Programmes, David Wheeler begins with this sentence: "A sub-routine may perhaps be described as a self-contained part of a programme, which is capable of being used in different programmes." Already from the start, the motivation was a kind of modularity.
The separation of concerns that functions provide takes many forms, each helped by the pure idea of a function:
-
Isolation. What happens in Vegas stays in Vegas. The added idea of lexical scope helps splendidly with this.
-
Re-use. If two parts of a program (or larger system) both want to call the same function, they can do so. The cost of more and more callers of a function scales linearly with the number of callers, and scales more slowly than (say) re-writing the function by hand at each call site. (This is true whether we refer to program size or programmer time.)
-
Coupling/cohesion. By encouraging re-use, functions can help decrease coupling. That's very abstract when put like that; sorry. I guess the coupling they remove is the kind that would have appeared in the form of duplicated code... Heaven knows different forms of coupling and other problems are still possible, though. (Wikipedia lists a large flora of couplings.) Similarly, functions encourage but do not guarantee cohesion. There's a rabid "clean code" posse out there that insist methods should be small, sometimes indefensibly so. I'm pretty sure what they're after is this kind of "do one thing" ideal, poorly expressed.
-
By existing, a function establishes a consumer/provider relation. The ideal form of a function takes parameters as input and gives a return value as output. (We'll stay silent on whether a function is "allowed" to perform side effects, by which I mean we'll skirt the issue and implicitly allow it. Part of the reason is that the story about side effects is still very much being written/explored, by languages like Rust and Koka.)
-
Building on that last point, functions are also what opens the door to Design by Contract, and specifications. Whether these are specified formally and machine-checked, or informally with documentation and targeting the human reader, the main idea is that the function is no longer just its code, but also a set of assumptions and guarantees. This idea will come back later, several times.
Why does lexical scoping (also known as "static scoping") fit so well with functions? From the angelic perspective, it's because this scoping discipline provides a form of stability, tying variable scopes to "blocks" in the code — that is, in the written program text. It doesn't get much more clearer than that: your variable lives until the }
of the block in which it was declared. From the demonic perspective, it doesn't fit particularly well, and is not the first scoping discipline that tends to come to mind — dynamic scoping is.
Or rather, dynamic scoping is the natural thing for an interpreter to adopt. The interpreter follows the control flow of the program itself; if it carries around a shallow ("one level deep") set of name bindings, then dynamic scoping is pretty much inevitable. Lexical scoping is the perspective taken by the compiler, which follows the program text rather than the control flow. It took from the late 50s to the 80s for the Lisp world to make the transition from one to the other; indeed, they started with interpreters and only gradually became keen on compilation.
Functions provide a guarantee which will be cast in a sharper light when it is broken later. It doesn't have a name in the literature that I know of, so let's call it the dynamic embedding guarantee. It has two parts:
- The entire machine has a single thread of control.
- When a function is called, the single thread of control is transferred/borrowed from caller to callee. When the function returns, it is handed back.
Think of it as a "spark" running around executing your program. (This is the entity that debugging/stepping through code makes manifest.) Calling a function means transferring that spark. Because the dynamic extent of the function's execution (the interval on the timeline when the function was active) is strictly contained in that of the caller's function's execution, the whole program run forms a perfectly nested structure, a tree of calls.
It is at this end of the spectrum that functions are perfectly oblivious, not "aware" at all of the process that's running them. Looking ahead towards the other end of the spectrum: actors are the total opposite — not only are they aware of the process running them, they've taken it over to the extent that they are the process that's running them.
Function calls compose well. This is why we can talk of call trees, because a function can take on the role both as a callee and as a caller. I'll save the discussion about re-entrant functions till the "First-class functions" section. Same goes for when functions compose in two other ways. Here I'll just note that it's interesting that the angelic nature of functions demands a lot of them, and functions, it seems, are up to the task.
There is a slight asymmetry between parameters and return values: in almost all languages, you pass 0 or more of the former, but receive exactly one of the latter. The introduction of tuples means there's a way to reconcile this apparent conflict — if what you're passing in is always a tuple, it can be both a single thing (to the implementation) and 0 or more things (to the user). It's a really nice idea, but I can't recall seeing it implemented perfectly in any language in practice. The same trick allows a language to emulate multiple return values — for some reason, I see this implemented well in many languages (C++, Perl, Raku, Bel).
Coroutines
Known under many names: fibers, green threads. (The term "green threads" comes from the fact that some part of Java implementation was called "Green" at some point.)
I've written "units of cooperative multitasking" in my notes. The operative word is "cooperative" — if one agent refuses to pass on the baton, the multitasking doesn't work.
Recall the dynamic embedding guarantee. We now weaken this in the smallest way possible: there is still only a single thread of control, but there is now a way to transfer it between active functions. ("Active" here simply means "currently being called", that is, we're "in" that function's body; there's an activation frame for it.)
This breaks the LIFO assumption of call completion: functions now get the ability to "pause" execution and hand the baton to some other active function.
In a sense, it also breaks the assumption of "single thread of control" — but it depends what you mean, actually. It does break it if you mean "we have one and only one call stack". It doesn't break it if you mean "at any given moment in time, exactly one function is executing". (Real threads break that, but not green threads.)
Interestingly, this affords a greater separation of some concerns, even though it surely feels as if we're making things more mixed-up. The reasons for this I cannot verbalize well, but it has something to do with separating concerns along producer/consumer lines.
Coroutines enable stream processing. A producer can generate data in individual sequence items, and the consumer can accept those sooner than if it had to wait for the whole sequence to be computed. The total "delay" involved is the same if we don't have real threads, but we might see partial results sooner.
Unix pipelines are an excellent example of this. (Except that they can sometimes use more than cooperative multitasking.)
Russ Cox has a good article on the original reason for CSP (communicating sequential processes) being separation of concerns. That is, just as functions help us separate some concerns, coroutines help us separate others.
A demonic implementation concern that gets mentioned here is a "spaghetti stack" (or "cactus stack"). This is just the idea that the stack is no longer a singly linked list of call frames, but a tree of them. The leaves of this tree correspond to the active-or-paused functions.
Since this is our first encounter with suspending the execution of a function, we also need to bring forth what (demonically) needs to be saved for the function to be able to resume later:
- The "instruction pointer" (which statement or part of expression we should continue on later)
- Local state (local variables if you're the human reader, local registers if you're the machine)
This is enough as far as "information that needs to be saved" goes, but there's one additional detail that matters from an angelic perspective: assume that the keyword for "cede control to caller" is yield
. What would be an appropriate value of a yield
expression? The question at first appears not to make sense — we've just ceded control. But at some point, it will be handed back to us. And at that point, it might be handed back with a value, much as a function is called with an argument.
Python implements exactly this model. I think it was Erik Meijer who said that the bidirectional aspect of yield
is what makes it especially difficult to give Python coroutines a sensible type.
Coroutines anticipate CSP (Communicating Sequential Processes) — more on which later — in the sense that you can implement the latter with the former. Or maybe better said that coroutines look like a line or a singly linked list (like Unix pipelines), but CSP looks more like a directed graph.
First-class functions
Taking a step in an orthogonal direction: given how absolutely awesome functions are, is there any way they could be made more awesome?
According to Christopher Strachey, yes: we can make functions first-class, that is, reified values in the same sense booleans and numbers are values.
"First-class" is not a complicated concept. It means we're allowed to do these things:
- Pass as a parameter
- Store as a variable
- Return as a return value
For some reason, Computer Science rewards those who make concepts first-class citizens. My best guess as to why: Denotational Semantics already talks about "valuations" of program fragments: turning a bit of syntax into an actual value. By making those values first-class, we are allowing the program to hold and refer to those valuations directly. This tends to bring more direct power into the language. I've written elsewhere about the drawbacks of making things first-class.
The Lisp family of languagues ended up being the ones who struggled with these questions. With the comfort of hindsight, it was simply a transition from dynamic scoping to lexical scoping... but in the coincidences of actual history, they were called "downward funargs" (function values passed as arguments) and "upwards funargs" (function values returned as return values). (John Shutt remarks on the fact that "funargs" implies that the "arguments"/downwards case somehow takes priority, which is indeed how the Lisp world thought of it.)
Take the "downwards funarg" case first. This is what happens when you give an anonymous function to map
. Lexical scoping and dynamic scoping actually agree on what should happen here, which is what makes this the easier case: variables accessed that were declared in the outer function should still be accessible normally. Lambda calculus and the semantics of binders makes this a non-issue; it is the demonic aspects of making this work on a machine that causes any trouble at all.
Now then, "upwards funargs". These were, historically, the real problem. Lexical scoping says it should just work: the function value returned should still have access to the outer function's variables. But from the perspective of dynamic scoping, and from the demonic perspective of "returning from a function means de-allocating its activation frame", upwards funargs are a real problem.
Upwards funargs "escape" from the function that defined them. This is the first push from the world of stack allocation to the world of heap allocation.
The historical answer to all this is closures: the joining of a function with the (lexical) environment in which it was created. The environment is what gives the closure access to the necessary outer variables.
In the history of Computer Science, there is no greater story than that of FP and OOP setting off in two different directions and yet reaching the same goal. From the point of view of closures, the story is how closures accidentally take on all the power of objects. The koan about Qc Na recounts this. From a demonic perspective, the act of returning a closure from its active function means the closure has to save the active function's environment, thus turning into something the shape of an object.
To me personally, JavaScript was the language that demonstrated this, since its first-class functions are faithful enough... but historically, Scheme was the language in which these realizations were made, and embodied.
Next up is continuations. I would say that the closures⇄objects analogy gets even stronger in the form of continuations⇄actors. But all in due time.
Continuations
I have nothing in my notes about continuations. Fortunately, I've spent the last week implementing them, again, in Bel. I needed them for my "fastfuncs" mechanism, which is a cheaty way to make the Bel interpreter faster without having a full-fledged compiler. (I had falsely believed the fastfuncs could make calls of their own freely, but this ends up interacting badly with other continuation-based Bel functionality (such as exceptions), and so in the end, the fastfuncs need to implement continuations as well.)
Continuations are what you get if you start from regular second-class functions, and then add both coroutine functionality and first-class-ness:
-
Continuations store exactly the same data as coroutines: the instruction pointer, and the environment to use at that point. (And they accept a single value as a parameter.)
-
Continuations don't have to be first-class, but when they are, they are indistinguishable from first-class functions.
Holey manoley! I've never seen anyone describe it like that in the literature, but I believe it's true: continuations are simply first-class coroutines. Categorically, they are the pushout of coroutines and first-class functions, taking plain functions as their common base.
A corollary of this is that if your languages has first-class continuations, you don't separately need it to have coroutines; they are but a special case.
My mental model is this: functions abandon their role as the fundamental unit of computation, and hand it to a smaller entity: what typically is called a "basic block", characterized by the fact that jumps/state transitions can only happen between basic blocks, never within them.
If it gives you warmth and comfort, you can think of these basic blocks as "mini-functions". They have the additional restrictions that they do not contain internal calls — a call counts as a jump, and so needs to happen at the end of a basic block.
There is a one-to-one correspondence between the "control-flow graphs" people used to draw in the 70s, and basic blocks/"mini-functions".
Continuations turn the call tree into a directed graph. In doing so, they also erase any distinction between "calling a function/passing a parameter" and "returning from a function/passing a return value" — these are both just instances of a invoking a continuation. This seems to be a difference that stems from turning coroutines first-class: by mixing "control" and "values", we destroy the idea of "caller".
Continuations are useful as a basis for advanced language features: coroutines, exceptions, finally semantics, backtracking semantics... The implementation can still choose to keep them continuations hidden and "second-class" in userspace, if it does not wish to confer such awesome power to the language implemented.
Coming from the other direction, even a language which itself does not expose first-class continuations could use a programming style which imitates them (using first-class functions). This is known as "Continuation-Passing Style" (CPS). The clearest example of this that I know about is Node.js with its callback parameters, circa 2009. It's now 12 years later, and async
/await
is recommended instead, but there was a point when CPS was your best bet.
Since I've spent the past week writing (Perl) code in continuation-passing style, I feel I'm somewhat an authority at this style, more than I ever was when I wrote Node.js code in that style. You're writing your basic blocks as functions, which either return normally, or invoke another basic block. All you need to make sure is that all the basic blocks you need from the current one are lexically in scope. You can do that like this:
- Declare all the basic blocks that mutually call each other (but don't initialize them)
- Initialize them (in any order)
- Call one of them to get things started
This covers the hardest case, that of looping and forward jumps. The cases of sequencing and choice are easier, and I won't cover them. Altogether, we can express things in such a CPS style, using calls for anything that previously required if
statements, while
loops, or even more exotic control flow.
Pro tip: if you try this at home, you should really do it in a language that implements Tail Call Optimization. The reason is that, since continuations don't believe there's a call stack at all, they will be sorely disappointed if there is one in the implementing language, and it overflows. Amusingly, the way this resolves itself in Node.js (and in my Bel fastfuncs) is that the stack gets reset regularly by async calls.
(Very Late Edit: And, whatever you do, don't mutate your local variables! (Something like a for (int i = 0; i < L; i++) { ... }
is a bit no-no.) What you want to do is emulate mutation by passing such values around, kind of like the SSA approach to variables. If you don't do this, someone will take a continuation and catch you red-handed. I learned this the hard way.)
It is perhaps here it's also worthwhile to mention that, as part of the development of Scheme, Steele and Sussman found out (by implementing it) that continuations and actors are equivalent... under certain other reasonable assumptions. More precisely, passing a value to a continuation and passing a message to an actor can be seen as equivalent in power. Perhaps the biggest difference in practice is that actors are fundamentally isolated on the process level (and therefore asynchronous), whereas continuations are agnostic in this dimension: they allow it, but don't require it. To Steele and Sussman, that didn't matter much; to Hewitt, it did.
I feel I could write a lot more about continuations. I also have literally dozens of papers queued up about continuations, most of which I have not even skimmed. It's clear to me that they are powerful and fundamental, and that I still do not understand them well enough.
The removal of the basic block's power to call other functions is significant. Here is the first time we're saying "you can do many things, but you cannot do this". Continuations do not work properly if we also allow normal function calls. It is by limiting them that we make them work as they should. This act of limitation is the start of removing control from functions, and making it a global/distributed concern rather than a local one.
This is as far as I got tonight. Looking back at my progress, I think I would need two more evenings to finish up. I'll try to rise to that challenge.
The same trick allows a language to emulate multiple return values — for some reason, I see this implemented well in many languages (C++, Perl, Raku, Bel).
That's a weird list of languages with tuple support. I'm not sure what those share in common wrt multiple return values?
That's a weird list of languages with tuple support. I'm not sure what those share in common wrt multiple return values?
Aye, I fear I did not do that bit justice. Not sure it's about tuples what I'm after. Let me unpack (pun totally intended) my given list of language examples in search of some unifying trend:
-
C++ actually does have tuples. Someone with a better understanding of compiler optimizations might do a better job explaining them, but my impression is that they are essentially zero-cost; the tuple's existence on the returning and receiving side of a return can be completely eliminated, and only the values themselves transferred. I guess this is only really true with a number of caveats involving inlining and whatnot. My main point is that under some circumstances, C++ truly allows multiple values to be returned with zero overhead.
-
Perl 5 does not have tuples, and makes none of the claims to efficiency that C++ makes. But what it does have is an admirable symmetry in its functions' inputs and outputs. The inputs are found in a dedicated array
@_
; the most general form of the outputs is a list of values. This list can easily be assigned en masse on the receiving side. Even without the efficiency, it gets full points for allowing multiple values to leave the function and be taken care of on the other side. -
Raku is much the same (although it got civilized parameter lists on the way). I honestly forget whether what
return
returns in Raku is aList
or aSeq
, but at least it can contain multiple values. What's more, the binding operator can make it absolutely clear that passing values into a function and passing them out of a function are symmetric acts. -
I can't speak for Common Lisp, which I know does something with multiple-value returns as well, but... Scheme has a mechanism called
values
which seems absolutely bizarre to me, like someone had an honest momentary lapse of language design sense. The Kernel spec similarly rips into R5RS on this point, pointing out how only a confusion of ideas could have led to something likevalues
. Interestingly, the solution both Kernel and Bel arrive on instead is just good ol' destructuring — even JavaScript has that nowadays.
Python doesn't have destructuring as such, although it does have some mitigating ways to assign from an iterator into a tuple of lvalues.
Which only leaves Java among the more popular languages. Java has absolutely nothing in this area of design space, which seems strange until you realize that Java was put on this earth to make the von Neumann bottleneck as narrow and uncomfortable as possible.
Common Lisp and Scheme share that values
mechanism. I'm not sure why they thought stealing that particular feature was a good idea, but they did nevertheless.
If you don't explicitly ask for all the return values, you only get one.
This is similar to how this happens in Lua, which is the only language with different semantics for "return values" than just unpacking (that lots of languages have):
In Lua, a multiple value is collapsed in several positions, but it "auto-splats" when used as the last argument of a function, inside an object, and is blocked by parentheses.
function f()
return 2, 3
end
function g(...) end
local x = f() -- Cannot splat: assigns x = 2
local v = { f() } -- Can splat: assigns v = {2,3}
g(f()) -- No parentheses: calls g(2, 3)
g((f()) -- Parenthesized: calls g(2)
g(1, f()) -- Last arg: calls g(1, 2, 3)
g(f(), 1) -- Not last arg: calls g(2, 1)
If you don't explicitly ask for all the return values, you only get one.
This isn't even my main beef with the feature (although that sounds like a pretty horrible default).
My main beef is that it feels like their goal was to deliberately create a second-class value in the language just for passing many values... OK in general maybe, but not in the context of a language whose central feature is to build rich tree structures out of a universal structure type. It's like the values
feature was designed by someone who hadn't used Lisp/Scheme for an entire day.
In Lua, a multiple value is collapsed in several positions
hnn 😞
but it "auto-splats" when used as the last argument of a function, inside an object
eww 😱
and is blocked by parentheses
One thing that is really really hard in language design, for some reason, is to make parentheses in expressions keep meaning "just grouping, nothing else".
It's like the
values
feature was designed by someone who hadn't used Lisp/Scheme for an entire day.
Or most programming languages, really. I'm just describing it for the sake of completeness, but I certainly won't say I like it at all.
One thing that is really really hard in language design, for some reason, is to make parentheses in expressions keep meaning "just grouping, nothing else".
It'd be better, yes. Well, the language with the worst example of this that comes to mind right away is C++ (if a function is decltype(auto)
, the deduced type is different for return 3;
and return (3);
).
I haven't forgotten about this thread, but getting back into it is going to require bigger chunks of time — realistically, the next time I'll have those will be around Spring Festival.
In the meantime, I just found From Procedures, Objects, Actors, Components, Services, to Agents – A Comparative Analysis of the History and Evolution of Programming Abstractions. It comes without a strong recommendation — I have only skimmed it very lightly, not read it in detail — but the title itself was similar enough to the thrust of this issue that I wanted to mention it.
Might as well mention Sans-Papiers as First-Class Citizens, which I will need to pick apart and review in detail at some point as well.
On Abstraction by Eric Scrivner:
Substituting a call to a subroutine for the contents of a subroutine builds a lexicon which can be used to reduce duplication and heterogeneity. Using a pointer or reference instead of a value reduces duplication and copying. Both facilitate compression of data as well as compression of semantics. Both of these give us leverage - the ability to do a lot with a little.
It is precisely here that a risk arises. We can view the whole purpose of abstraction as the dissection of a program into its conceptual categories. This was the profound error and misstep of object-oriented programming (OOP). This style of abstraction leads to the traditional problems of reason, logic, and language as thoroughly covered by Beiser. Alternatively, we can view the purpose of abstraction as compression guided by resemblance and analogy. This style of abstraction has poetry and literature as its exemplary arts. We are given these techniques of substitution in order find the boundaries and limits of resemblance and analogy in pursuit of compression. The choice of path on this fork is the momentous decision that determines the whole of the method we pursue in construction.
This reminds me of two things. One is the point about premature abstraction that sometimes pops up when discussing abstraction with @jnthn — the hard part isn't creating an abstraction, the hard part is the mental work necessary to arrive at the right/useful abstraction. In the limit, refactoring makes us brave in constantly re-evaluating and re-creating abstractions as needed.
The other point is that Bel's predicate-based type system seems to fit the description about "compression guided by resemblance and analogy". Unlike in OOP, there's not really a reified "thing" corresponding to a class or type. Just a predicate that answers t
or nil
when you give it an object.
First-class functions
I just realized one thing.
Here's a sentence from cppreference:
When a user-defined class overloads the function call operator,
operator()
, it becomes a FunctionObject type.
So, a "function object" (which I've heard people call a "functor") is an object that acts like a function, in that you can use the ()
function call operator on it.
This is approaching first-class functions from the other direction, adding "it's a function" to an object instead of (as is traditional) adding "it's a first-class value" to a function. It's first-class functions from an OO perspective.
It clicked for me when reading this SO answer:
There are a couple of nice things about functors. One is that unlike regular functions, they can contain state.
This is a very C/C++ perspective, when "regular functions" mean "lower-order functions" by default, and these don't contain state. (Um. Modulo the static
keyword, of course. The thing they don't contain is the kind of "instance-level state" that comes from evaluating a function declaration into a closure at runtime.)
Of course, I realized all this on some rough level when writing the original comment about first-class functions:
In the history of Computer Science, there is no greater story than that of FP and OOP setting off in two different directions and yet reaching the same goal.
Despite this, there's something concrete and satisfying about seeing the path actually walked in an objects-and-classes language, adding ()
to an object just because we can, and seeing a closure pop out.
JavaScript doesn't have operator overloading, but the JavaScript MOP consists only of Object
and Function
, and the only real difference is that Function
allows you to ()
on the value. Instead of directly overriding the ()
on a class, you just make sure to create it as a function
declaration, and then you can treat it as a regular object with properties. If you squint, that's actually a kind of operator overloading, too.
My mental model is this: functions abandon their role as the fundamental unit of computation, and hand it to a smaller entity: what typically is called a "basic block", characterized by the fact that jumps/state transitions can only happen between basic blocks, never within them.
I don't know if it helps in any way, but "jumps/state transitions can only happen between basic blocks, never within them" — or, equivalently, "basic blocks are stretches of sequentially executed instructions" — is a kind of quotient construction; roughly a way to decrease resolution, making the notion of "instruction" bigger and more inclusive, and the notion of "(conditional) jump" more universal. Something related happens when looking for strongly connected components in a directed graph; the result is lower-resolution, but a part of the structure remains.
If it gives you warmth and comfort, you can think of these basic blocks as "mini-functions". They have the additional restrictions that they do not contain internal calls — a call counts as a jump, and so needs to happen at the end of a basic block.
There is a one-to-one correspondence between the "control-flow graphs" people used to draw in the 70s, and basic blocks/"mini-functions".
Continuations turn the call tree into a directed graph. In doing so, they also erase any distinction between "calling a function/passing a parameter" and "returning from a function/passing a return value" — these are both just instances of a invoking a continuation. This seems to be a difference that stems from turning coroutines first-class: by mixing "control" and "values", we destroy the idea of "caller".
All of this is true, but (as I come back to re-read this) applies equally well to coroutines. I think the CPS transform has already happened, conceptually, at least, the moment we introduce yield
into a language.
The removal of the basic block's power to call other functions is significant. Here is the first time we're saying "you can do many things, but you cannot do this". Continuations do not work properly if we also allow normal function calls.
It bothers me a little bit that we need to talk about a removal of power here; continuations in general feel incredibly enabling, in that they literally enable other features like generators, exceptions, nondeterminism, and other wonderful types of control flow.
Note that in Continuation-Passing Style it is the style itself which imposes a restriction, and with basic blocks it is our definition of what a basic block is that imposes the restriction. It doesn't come from continuations themselves, which are highly unconstrained and non-constraining.
Also important that the "stack paradigm" naturally suggested by regular LIFO function calls is also very restrictive, and by introducing continuations, we're transferring to a "heap paradigm". The non-obviousness and pain of doing so was the essence of the funarg problem, especially the upwards half where the stack is insufficient.
The stack paradigm is great, not just because it's faster in practice but because it ties an important kind of RAII thinking into the structure of the code itself. One of the tricky parts of good compilation is to get enough static knowledge of data flow inside of a function to determine that nothing continuation-shaped escapes, and therefore things can be stack allocated and therefore faster. The nature of such determinations means that we can do this less often than we'd like (and even when we can, it takes a bit of work).
I'm curious if you get anything useful out of this.
(And/or a reddit discussion about that article.)
I'm curious if you get anything useful out of this.
Yes! My immediate reaction is that "substructural type systems are cool and useful" — vide Rust, and Perceus, and, I dunno, unique_ptr
(for all its flaws and weaknesses). Linear types can change the world, and all that.
But I think I'll leave it at that. There's a sense in which the whole substructural thing falls under the heading "Types", which I almost didn't even include in the abstraction ladder/table of contents/topic plan for this issue. I have an irrational fear of type systems, equal and opposite to Bob Harper's love of them. I mean, clearly the regimentation they impose ends up helping and helps us see further. But on whose authority except its own does the type checker reject my program? I'm not hating on type checkers, I just don't think we should be slaves under them.
I have more to say/write about well-foundedness, and the distinction between what Harper calls T++ and PCF++ (which mirrors what Hofstadter calls BLooP and FLooP) — it seems to me that ownership-tracking is to memory what T++/BLooP is to termination/totality/decidability. Possibly there's even a direct connection — but even if there isn't, the topics feel a little bit related.
Relevant to the way continuations generalize regular functions and the stack paradigm (from a 2012 blog post by John Shutt about guarded continuations):
When a function
f
calls another functiong
,f
gives up some of its ability to regulate the future evolution of the computation. The programmer tends to assume that not all such power has been lost — that (1) the call tog
won't terminate without control passing back through the point at whichf
called it, and (2) that particular call tog
won't return through that point more than once. In the presence of first-class continuations, though, even these weak assumptions needn't hold.
I called (1) above the "dynamic embedding guarantee". I don't think that I spelled it out that continuations obliterate the dynamic embedding guarantee.
Also note how (1) is about (returning) "at least once", while (2) is about "at most once". Continuations but with (2) are sometimes called "one-shot continuations", I think.
A quote I just ran into, which corresponds to where I was planning to make this issue end up:
"The most important problem right now in computing is — how do we deal with concurrency and distribution?" — Philip Wadler - Propositions as Types (Q&A)
Parts of this story gain a sharper edge by more carefully separating the pure/applicative/expression world from the monadic/heap-memory/sequential world, like PFPL does, which I'm currently reading with great appreciation.
On page 307 (of the paper book, second edition), a bit after the midpoint of the book, things culminate in this factorial procedure declaration:
proc (x:nat) {
dcl r := 1 in
dcl a := x in
{ while ( @ a ) {
y ← @ r
; z ← @ a
; r := (x-z+1) × y
; a := z-1
}
; x ← @ r
; ret x
}
}
Given how what we're expressing here could be written in Raku as sub ($x) { my $r = 1; for 1..$x -> $i { $r *= $i }; $r }
, some explanation of Harper's Modernized Algol syntax is in order:
-
dcl
introduces a (stack-allocated) assignable -
@
reads from an assignable (into the monadic world) -
←
binds the results of a monadic computation to a variable (in the pure world) -
:=
outside of adcl
evaluates its (pure) rhs and writes the value to an assignable -
ret
is the only way to communicate a value from the monadic world back to the pure world
Assignables only exist in the monadic part. Variables are typically associated with the pure part.
I wrote this earlier:
(We'll stay silent on whether a function is "allowed" to perform side effects, by which I mean we'll skirt the issue and implicitly allow it. Part of the reason is that the story about side effects is still very much being written/explored, by languages like Rust and Koka.)
The entire point of Harper/PFPL's separation is that side effects are locked into the monadic half of the language, letting the pure part keep many of its algebraic/equational properties. This is nothing new, of course; Haskell does exactly this with monads, and Koka does exactly this with effects.
All the talk about side effects anticipates the later talk about process isolation and actors. It's by making the side effects and the heap memory explicit (like PFPL does) that we can later isolate those things, and hide/encapsulate them inside something.
It's by making the side effects and the heap memory explicit ... that we can later isolate those things, and hide/encapsulate them inside something.
In recent years I've been thinking of 6model as "actor model ready". Do you get what I mean? Am I deluded? Have I mentioned / are you aware of Pony and ORCA?
In recent years I've been thinking of 6model as "actor model ready". Do you get what I mean?
I think so, but to the extent I do, I'm not sure I agree. I'll quickly add that this might be because you have pieces of the 6model puzzle that I lack.
In order to answer in more detail, I need to anticipate a few points from the future of this thread, specifically the last two topics in the projected list of "module-like things":
- Communicating Sequential Processes
- Actors
But as a baseline, the story must start with the status quo of shared memory, threads, and locks. I'll take all those mechanisms as given — there's oodles of literature on it — but I will mainly point out here that locks don't compose and threads don't scale. This book, specifically, spends the early parts showing how a perfectly well-designed class for single-threaded use can break under many-threaded use — it's humbling — the problem is a bit like "monsters from the 9th dimension" in that it manifests orthogonally to the correct code you wrote — and then spends the later parts advocating safer/higher-order building blocks, like atomic data, built-in cuncurrent data structures, and architectures built on the producer-consumer metaphor. (Further confirmed with BG's answer here of also covering "fork-join, parallel decomposition, and the new parallel bulk data operations".)
Communicating Sequential Processes takes the initial interesting step that assignment (to shared memory) is not a primitive operation, communication is. Specifically, this is a two-party action, so every such communication is also a synchronization point, and establishes a happened-before relation à la Lamport. This simple shift in perspective makes things scalable, and the focus now shifts to the (quite possibly dynamic) structure of communication channels between processes. Shared mutable memory is no longer a problem, because there's no global memory to share; you can only share along channels.
Actors similarly take a new primitive operation: (asynchronous) messaging. Actors are by construction so well-protected from each other that not only is the "shared mutable memory" problem completely defined away — but by themselves, actors don't seem to be able to synchronize anything between themselves. I'm still learning about this, but one solution seems to be synchronizers, which could maybe be seen as a common region in which synchronization on shared resources between actors can happen.
These two models are clearly related. In fact, we can encode either model using the building blocks of the other. Which means we can zoom out to a sufficiently high-altitude perspective where they both look the same, and present a common solution next to threads/locks: while threads and locks start out with a fundamentally un-synchronized resource (shared mutable memory) and then tries unsuccessfully to apply massive amounts of cleverness and discipline to apply synchronization in just-enough places to restore correctness, CSP and actors start out with a fundamentally synchronized resource, and then spend the rest of their lives happily ever after. (Although actors also need to add synchronizers as an extra component.)
Threads and locks are still popular despite being fundamentally unworkable, because people naturally tend to think of a solution as a concrete feature. CSP and actors start out by removing and restricting; more of a "negative feature". There's a quote about Dijkstra somewhere about how his main insight about concurrency is that it's not about adding something (such as "threading"), it's about removing a restriction/assumption (such as "the order of the statements (alone) determines the sequencing of the operations at runtime").
The story doesn't end there, either. There's something really interesting going on with what Rust and Koka are doing, basically exploiting the fact that "has a unique owner" is a necessary and sufficient condition for mutability. This is like carving out a "safe space" from the shared mutable memory, and the fact that something shaped a bit like a type system can do that is... interesting. You don't need to write actor { ... }
around things to protect them, you just show statically that unique ownership is maintained.
Tying everything back to whether 6model is "actor model ready" — it would need to be in terms of some of the above primitives, I think. CSP/channels, or asynchronous messaging with provably no sharing, or (à la Rust) just provably no sharing. I'm not sure if 6model is more or less ready for any of those than other object systems.
Have I mentioned / are you aware of Pony and ORCA?
@raiph I don't think so, on both counts.
Skimming the linked page, it sounds amazing, but it's also extremely short on specifics. I would be a thousand times less doubtful of the claims (sound + complete + concurrent) if there was a link to a paper containing algorithms and a number of proofs. Several questions arise, such as:
- How can a dedicated actor collect other actors using just message-passing?
- How, specifically, are the very different form factors of reference counting (which is usually centralized) and actor distribution (which has no built-in synchronization mechanism) reconciled?
- When the word "transitively" is used, that implies a non-local property that needs checking in non-constant time. How is that property checked in a world where a number of synchronization mechanisms are proudly enumerated as not being used as the solution? (I.e. once you have traversed the object graph in order to confirm the "transitively blocked" property, how do you know that the nodes you checked at the start are still unchanged? "Blocked" implies "has no pending messages in its queue" — what prevents new messages from arriving anywhere in the graph while we are traversing it to assert all actors have empty queues?)
MoarVM's garbage collector is pretty cool, but it's far from this design along several dimensions: it's tracing/generational, not reference-counting; and it's based around threads and condvars, not actors and a mysterious lack of a need for synchronization.
There's a quote about Dijkstra somewhere about how his main insight about concurrency is that it's not about adding something (such as "threading"), it's about removing a restriction/assumption (such as "the order of the statements (alone) determines the sequencing of the operations at runtime").
Ah; the quote I thought about is from this blog post:
Non-determinism
In 1967 R.W. Floyd had introduced non-determinism as an additional language feature. The proposal concentrated on how to implement it. For EWD it was a subtraction: by avoiding what he considered overspecification, it became a natural consequence of the semantics of the guarded-command language [footnote].
A further thrust at the question of 6model's actor-model-readiness. Here's a quote by Robin Milner from his Turing award lecture:
Now, the pure lambda-calculus is built with just two kinds of thing: terms and variables. Can we achieve the same economy for a process calculus? Carl Hewitt, with his actors model, responded to this challenge long ago; he declared that a value, an operator on values, and a process should all be the same kind of thing: an actor.
This goal impressed me, because it implies the homogeneity and completeness of expression ... But it was long before I could see how to attain the goal in terms of an algebraic calculus...
So, in the spirit of Hewitt, our first step is to demand that all things denoted by terms or accessed by names—values, registers, operators, processes, objects—are all of the same kind of thing; they should all be processes.
I think this pinpoints something important: when Hewitt says "everything is an actor", he means something concrete/specific about his imagined system. 6model can reasonably claim that "everything is an object", and back that up with evidence in terms of abstraction/encapsulation boundaries. For it to take the step to claiming that "everything is an actor", it would need to witness that in terms of process boundaries and inviolable message-passing mechanisms, as the foundation of the whole model. (But when it's put like that, I'm not sure that is, or should be, the goal of 6model.)
If what we mean is "some things can be actors" (rather than the whole system being actor-based), then I believe this was conclusively asserted with the release of jnthn's oo-actors module in 2014. :smile:
Here's another reference for future reading and incorporation into the themes of this thread: The Purely Functional Software Deployment Model (Eelco Dolstra's PhD thesis). It's the basis for the Nix package manager, whose main selling point is that identical inputs give identical outputs — that is, builds are reproducible.
As a relevant aside, it would appear to me that golang is following a convergent evolution here, independently discovering the value of reproducible builds [1] [2]. I hope to get back to both Nix and golang/vgo when I write about "Packages", listed in the OP as one of the tour destinations. The thrust of my argument will be just this, that as an abstraction, packages are not stable/usable unless they guarantee reproducible builds. It's a wonder we get anything done in mainstream software engineering, absent that guarantee.
The abstraction ladder, identified in the OP, also spans another axis: that between values and resources. Computer science tends to talk about values, but software engineering has an understandable focus on resources.
What's a resource? A database handle is a resource, a file handle is a resource — or they stand in for/represent resources, maybe. It depends how you categorize things. Threads and green threads are resources. Memory (including too-big-to-copy values in memory) is a resource. Input/output on a port is a resource (or the port itself is a resource?). Communication bandwidth is a resource. Network access is a resource. The abstract concept of compute (as in, computational throughput) is a resource. If I plugged a quantum co-processor from 2043 into my machine, it could constitute a resource.
I can give these specific examples, and I feel there is something that they have in common, but I can't clearly delineate that something. Values can avoid being about "the real world" in some sense, but resources are anchored in the real, physical world, and inherit limitations/properties from it. There are probably physicists who love that connection, whereby physics kind of bleeds into computer science.
It feels like there would be some straightforward connection to effects (and coeffects). Are effects simply about acting on a resource? The resource is the noun, the effect is the verb?
At its most pure, lambda calculus can be all about values. At their most expansive, CSP and actor systems can be all about resources. The abstraction ladder seems to straddle the values-resources axis. I wish I understood better how these things are connected.
But as a baseline, the story must start with the status quo of shared memory, threads, and locks. I'll take all those mechanisms as given — there's oodles of literature on it — but I will mainly point out here that locks don't compose and threads don't scale.
I just stumbled over the userver framework, which looks nicely designed and quite flexible/powerful. This is what met me in the first tutorial I decided to click on:
Warning
Handle*
functions are invoked concurrently on the same instance of the handler class. Use synchronization primitives or do not modify shared data inHandle*
.
In other words:
- Here be dragons (race conditions).
- By notifying you (the framework user) of these risks, we (the framework authors) have done our due diligence; race-free semantics is not part of the framework itself, it's part of a general vigilance/discipline wherein sharing/modification is always guarded by the appropriate synchronization.
- What, you thought this would be easy?
Later edit: It's all good and well to be sarcastic, but when coming back and reading the above, I didn't want that to be my main point/final word. Specifically, the authors of the userver framework are operating well within the expectations given to them. This (concurrent access) is just that big of a challenge — I think it's fair to say none of us knows the final answer — people of the Rust and Koka communities can see a bit further, sure, but in the end we're all still hunting for solutions, trying them out, and learning for the next iteration.
I want to call attention to this polemic post whose main message is this:
Provided your problem admits certain concessions that let you retreat from full-on garbage collection into reference counting, you're going to come out way ahead in the bargain.
I realized that I agree with this particular sentence because it's qualified, but then disagreed with the message of the rest of the post because I don't believe the qualification ("...your problem admits certain concessions...") applies in a general-purpose language.
In the post above about first-class functions, we showed that the special subtype of first-class function that people historically called "upwards funargs" have a tendency to escape their location of birth, thereby bringing their lexical context with them in a closure:
Upwards funargs "escape" from the function that defined them. This is the first push from the world of stack allocation to the world of heap allocation.
Of course I should have defined a static embedding guarantee that this breaks along the way:
- When a function is called, the environment of the caller is a compatible subset of the environment of the called function.
This is true (a) if there's only ever one global environment and not many small lexical ones, or (b) if functions are not first-class/mobile. I know that's a little bit abstract, so let's break the guarantee three times:
In Bel:
$ perl -Ilib bin/bel
Language::Bel 0.58 -- msys.
> (def make-closure () (let env "closure" (fn () env)))
> (let c (make-closure) (let env "caller" (c)))
"closure"
In Perl 5:
$ perl -wle'
sub make_closure {
my $env = "closure";
sub { $env }
}
my $c = make_closure;
my $env = "caller";
print($c->());
'
closure
In Alma (untested, but I have no reason to think it wouldn't work; #577):
func makeClosure() {
my env = "closure";
return func () { return env };
}
my c = makeClosure();
my env = "caller";
print(c()); // closure
Most modern mainstream languages have "given in" and introduced a mechanism that allows this kind of freedom of movement, whether via escaping first-class functions, or via heap objects being allowed to reference other heap objects. This is where the abstract graph of objects and references in memory turns from a tree into a graph, specifically one with cycles.
That's also the point where reference counting becomes problematic, and garbage collection turns into a more robust solution. The qualification in the post ("Provided your problem admits certain concessions...") is no more nor less than the static embedding guarantee: things are not allowed to escape their location of birth, or mutually reference each other, directly or transitively.
(Wait, what? Where did the "mutually reference" condition come from, weren't we talking about functions and lexical scopes? It comes from the Y combinator, which can be seen as a device that transforms firstclasshood of functions into function self-reference. Similarly, any "tying the knot" technique transforms freedom of heap reference (during object construction) into a cyclical object graph.)
The HN discussion seems pretty balanced. The top comment right now is saying that this is a never-ending and unwinnable debate. The top answer to it is reporting spectacular success with (mostly) reference counting.
The abstraction ladder also spans a spectrum between the specific (like reference counting) and the general (like garbage collection). Maybe the real lesson is that there is no one-size-fits-all point on that spectrum.
I'm getting ahead of myself here, but not by a whole lot. I realized on the way to work today that there's a great transition between the idea of functions and the idea of modules.
Briefly, it's this: thanks to lexical scoping, functions own much of their data, and it's perfectly hidden from the world. (We'll sweep complexities around stack/heap allocation, first-class closures, and escaping under the rug right now. Just assume they are appropriately taken care of.) Modules are primarily that, a "perfectly hidden" guarantee for some data, but wrapping a group of functions. Keywords like export
tend to switch off this perfect hiding; sometimes, inspired by the OO vocabulary, we'll be speaking of private
and public
instead, even though it's a module.
Various related concepts make this effect clearer. Separate compilation for optimizing the data parts that are private to the module. Types for communicating (statically) across module boundaries. Contract-based programming for refining ensure/provides relationships even further, and separation logic to reason about what memory is owned by what module.
That's it. Modules are, in this sense, a kind of "jumbo function" — the "jumbo" concept borrowed from Levy — they are the answer to the question "what is the biggest programming language feature we can imagine with the features we appreciate in functions?".