The Allocation Cancelling sounds pretty similar to the reuse tokens in Perceus. But Perceus uses refcounting, so it can shallow copy and share the subtrees, while it looks like Neut has to deep copy because every subtree is uniquely owned.
I’m curious in what situations the refcounting vs unique ownership is better. In particular, what are some cases where Neut is forced to deep copy, but a GCed language or Perceus wouldn’t?
In Neut, the “copy” and “dispose” operations are abstract: each type contains two functions that implement these operations. If you define the copy function to increment a reference count, and the dispose function to decrement a reference count and free on 0, then instances of that type will be reference counted in Neut.
So despite what the author says, I don’t think Neut forces deep copying. You could select between ref counting and deep copying on a type-by-type basis based on what gives better performance in benchmarks.
Apparently snapshot testing’s used in some front end frameworks to for component testing, but I’ve never seen anything like this before and the dev experience is literally breathtaking. What else have I been missing?
I use snapshot testing all the time, for everything! If I can’t write a fuzz/property-based test, I write snapshot-test. To the first approximation, anything more complicated than one assert(a == b) per test is worth moving to a snapshot.
Though, I don’t like the style where the snapshot is in a separate file, it makes small tests harder to read. By default, I specify snapshots inline, as a string literal, and use file only for gigantic outputs.
It’s also worth knowing that snapshot testing is very easy to implement, you don’t need a fancy library to start doing it (though, a library certainly has additional bells and whistles):
If I can’t write a fuzz/property-based test, I write snapshot-test.
Do you see property-based testing as a replacement for example-based testing?
In other words, when it’s possible to write a property-based test, do you treat that as the first line of defense against bugs in that code? This way of working appeals to me because I’d rather come up with a clear specification than a mountain of examples.
A counterargument is that it’s useful to have both: ideally you would have enough coverage from examples, but the fuzzer serves as a backstop. The examples test the (correctness of) the code, and the fuzzer tests the (completeness of) the examples.
I wonder if the best would actually be a combination:
A clear specification of what makes an output correct.
A corpus of interesting examples, which can be fed into the above spec.
An example-generator.
You could think of this as a corpus-driven property-based test. The examples make it easy to know what’s covered, and the spec makes it easy to know that the expected-outputs are actually correct.
I don’t think I can compress my full decision tree into a single commit box, but the top points are that you should thing about fuzzing/PBT/DST first, as those are high-investment/high-payoff techniques, and otherwise fallback to snapshot testing as a default low-investment technique.
Another way to refer to this technique is “golden file” testing.
I’ve used this technique for backend testing for many years, it is great, but you need to make sure your output is fully deterministic, which is a bit of pain when having generated IDs or timestamps.
The best libraries have a way to replace those values with placeholders. If not, you need to sanitize your output manually before passing it to the snapshot.
This is cool: I see it as a wrapper that encapsulates a common pattern. In OO style code I would enforce an invariant in the constructor, but then have to be careful to preserve it everywhere else (every setter, and every getter that exposes write access). I’d much rather only say “enforce this invariant”. (Reminds me of the difference between new/delete and std::unique_ptr in C++: the latter is a more declarative way to get the behavior I want.)
But I thought “refinement types” only refers to type systems that prove at compile time that the predicate is always true, like Liquid Haskell. And if I understand correctly that’s not what this utility is for: it’s a safer way to declare that a condition is dynamically enforced.
I think it depends on how much of a purist you want to be. It’s certainly not full fledged in the sense of Idris or Liquid Haskell, but it’s also much more than you’d be able to achieve in most OO languages (with the implication feature specifically of interest).
With richer support in the type system (disjunction, negation, etc.) we could get pretty close, but Rust isn’t there quite yet (and may never be!).
At the end of the day, some dynamism is needed to deal with external input though. You can’t get away from that.
Yeah, I don’t disagree with any design choices you’re showing here. I like that it encourages the “parse don’t validate” style. I hadn’t thought about the implication feature but I can see that being useful. I definitely agree with the choice to make a library rather than a separate type checker!
I’m only objecting to calling it “refinement types”, if that term has an existing narrower meaning (and I’m not an expert so I could be wrong about that). To avoid confusion it could have a different name, but one that still captures the benefit it gives you.
It is insufficient for code to be provably correct; it should be obviously, visibly, trivially correct
Some code seems to work correctly by accident, because the circumstances which could cause it to receive bad inputs and fail are ruled out by the structure of the other code surrounding it. I dislike this. Although technically the code may be free of bugs, restructuring the other code is now difficult and dangerous.
This is particularly true for security issues, or the theoretical absence of security issues. It doesn’t matter that all of the callers to this particular internal function are trustworthy right now.
(My emphasis.) This reminds me of something I’ve been trying to express recently!
Don’t look up the stack. Function bodies don’t know who is calling them. There is no “current client” or “current request”.
I think there are multiple reasons to follow this:
You want the function signature and docstring to be a communication boundary, an interface. In theory this is what people read to check that they’re calling or implementing that function correctly. A comment in a function body that “knows” something farther away than the function signature is making an assumption that nobody else has agreed to uphold.
You want functions to be understandable in isolation. The caller depends on the callee, so if the callee also depends on the caller then it’s a cycle where you need to understand both. To me this feels related to data being simpler when it’s acyclic: I can zoom in on a subpart and understand it completely.
You want functions to be testable; you want to see input/output examples. A function that knows about a “current request” has a large input, but likely ignores most of it, so you don’t know how to create a good input example. This large input also isn’t obvious from the function signature so you may forget.
If anyone else is curious, I can highly recommend the linked Ten Minute Physics tutorials. The creator, Matthias Müller, also has a ton of (fairly fundamental!) papers in the field of real-time physics simulation, and you can tell he really understands what he’s talking about. They’re some of the easiest to understand tutorials out there, in a field which can be quite overwhelming.
That looks fantastic, thank you! You should submit it as a top-level story.
I really appreciate his emphasis on keeping it simple: easy to explain and implement. When I read other game physics tutorials years ago I thought you need complex integration techniques like RK4 and I didn’t understand how that fits into the rest of the game loop. (Do you need to have multiple copies of the game state around to average them? How do you handle entities that appear or disappear during the simulation?) By contrast I think Matthias is saying you can use a smaller timestep, and don’t try to use very-stiff springs to enforce constraints.
But instead of alternating between sides, it appears that advancing on whichever side has visited the fewest nodes yet accelerates the algorithm in a lot of cases.
Would it be even better to advance whichever side’s frontier (the queue) is currently smaller? It seems like the frontier is the part you have to iterate, while the visited set is a hash lookup, so the size of the frontier would matter more.
Having tried both, there doesn’t seem to be any difference in performance. Said otherwise, the performance gain is the same whether you check the count of visited nodes or the size of the queue. I agree however that checking on queue size matches more the explanation I give later in the article, so I’ll change that.
Tree Calculus can perform program analysis without quotation
Tree Calculus [is] a great language for modeling and formal specifications
Offering more introspection means the language has fewer guarantees. In Python I can’t be sure whether, say foo(lambda x: x) and foo(lambda x: [x][0]) behave the same because foo could inspect the code of the lambda. In Haskell I know that foo (\x -> x) and foo (\x -> head [x]) are the same, because lambdas are opaque.
It seems like a language for formal specification would benefit more from limitations than flexibility: to make it easier to see, and be sure, that two programs are equivalent.
This is really cool: in the example there’s a login process which is sequential but it plays out across different machines. This language lets you express that logic sequentially.
It reminds me of the difference between callbacks and async/await: physically I need to schedule some continuation to run when an event happens, but logically I want to think about the overall sequential process.
It would be cool to have a debugger for choreography! It would let you debug a distributed-but-sequential process like any other sequential process.
So if I understand things correctly, the syntax of the object-language (SQL) is extendable from the meta-language (Go, in the post).
This makes me wonder: what if a object-language (imagine some new language, not SQL) had construct that allowed it to extend itself (from inside itself)? I suppose one would need to provide the semantics for the new syntax somehow? Even merely allowing sugar for already existing constructs seems like fun though.
From my quick read of the post, I didn’t see that the question of semantics was covered? In DuckDB’s do they always desugar into SQL or do they allow for SQLite-style extensions that provide new semantics for the new syntax?
This also reminds me of META II, which I’ve never fully understood. Is there anyone around who does and who can relate it to the post?
what if a object-language (imagine some new language, not SQL) had construct that allowed it to extend itself (from inside itself)?
In Scheme you can introduce new syntax by defining it as a macro. In some flavors like Racket, you can run arbitrary code at compile time to do the syntax transformation. The semantics (scoping, type checking, evaluation) are all defined by what your macro expands to.
Given that Scheme’s concrete syntax (the syntax that the user writes) is also its abstract syntax (the datatype that the interpreter/compiler operates on), I’d argue it’s not as impressive.
Racket’s #lang is more interesting, as it actually changes the concrete syntax. Do you know if there’s a document that describes how it’s implemented? Searching around I can only find documentation on how to use it.
It’s true that Racket macros have an easier time because the input is already nicely parenthesized. But it is pretty powerful in that you can create custom control flow or type systems. Match really is a mini-language which you can further extend with custom view patterns.
If you wanted more control over the concrete syntax, you could imagine a macro that takes a string literal and parses it, like (infix “2+3*x”) -> (+ 2 (* 3 x)). Then #lang could work by wrapping the entire file in a macro like (my-language “…file contents…”). I don’t remember if that’s the interface though. It might be more like “implement a custom (read <port>) function”.
I think the target language, rather than the source language, is the main limitation. Desugaring to Racket’s core means you inherit its flexibility (tail calls, callcc, garbage collection) and limitations (little control over memory layout, less opportunity than SQL for very high level optimization).
The #lang starts by running your custom reader, and then you return a single syntax object for the whole module. Then macro expansion continues from there.
But still merely seems to describe how to use the library rather than how the library is implemented. (What I’d really like is something minimal, like lambda calculus + the smallest possible extension that allows one to do this.)
What I’d really like is something minimal, like lambda calculus + the smallest possible extension that allows one to do this.
Oh, sounds like maybe you’re interested in the mechanics of how syntax objects are implemented? These are probably the most relevant:
Syntactic Abstraction in Scheme - This paper introduced syntax-case for and explains what’s happening inside those opaque syntax objects. Racket used to work this way.
Binding as Sets of Scopes
- This explains Racket’s newer internals for syntax objects, which is supposed to be simpler especially for things like internal definition contexts, or macros that inspect other macros.
This all makes me wonder: in what other places does precomputation pop up?
My first thought is that anything resembling a compiler is a form of precomputation. A tree-walking interpreter might do a string hash-table lookup for every local variable it visits. To precompute that, you can translate the program to something else (bytecode maybe) that has numeric offsets instead of variable names. Python’s re.compile, or Bison-style parser generators, or prepared statements in SQL are all compiler-like interfaces: they let you create a program in one step and then run it in a later step.
The re.compile example reminds me that there are some clever string-search algorithms that involve precomputing something from the search query. You wouldn’t normally think of a little string like "foo" as a program, but grep "foo" is sort of an interpreter, so internally it could “compile” that little string to some other form if that speeds up the search in a large input file.
grep “foo” is sort of an interpreter, so internally it could “compile” that little string to some other form if that speeds up the search in a large input file.
In fact it does exactly that, kinda. It does not actually compile anything but it will use boyers-moore for literal searching instead of running the regex normally.
I would rather say that interpreters are the opposite of precomputation: Instead of the computer being programmed to “do the thing” it is instead programmed to do stuff just-in-time by fetching the actual instructions later and lazily which will then “do the thing”. (which is not to say that it’s wrong or bad to do that.)
I’m not sure I understand what is concretely the problem, and what exactly is the Displayed state in this case? Is it just buggy which I find hard to believe?
What operations in general are you trying to do with 1e5 rows?
I was curious about Marimo but it looks like it still has most of this hidden state. It detects dependencies between cells when they read and write the same global variable, but it doesn’t see the dependency when they read and write the same object on the heap.
I wonder if it’s possible to design a notebook for Python that detects all the dependencies, with some kind of read and/or write barrier in the interpreter.
Related projects have tried to catch more dependencies (such as ipyflow), but inevitably fail to catch all, yielding a programming environment that makes it difficult to reason about the dataflow graph formed, and hard to predict what will run and when. Only handling global variables is at least tractable and the resulting graph is easily understood by the notebook author, and still eliminates a large class a bugs that are typically encountered in traditional notebooks; for example, deleting a cell will delete its variables in marimo and invalidate cells that use those variables, but not in traditional notebooks.
Before developing marimo (I am one of the developers), I saw this model work well for Pluto.jl (https://github.com/fonsp/Pluto.jl), which is our biggest inspiration.
Detecting all memory reads and writes sounds like an interesting research project. I am not sure it would lead to a better developer experience. But it would certainly be interesting to see it attempted.
Would it make sense to verify that no global variables outside the dataflow graph have changed after execution? If you can’t track ’em all, you could at least warn the user.
Agreed, it gets confusing which parts of my notes are still up to date. Maybe not automatic updates, but some staleness indicator could be the solution.
I consider this a feature of Mathematica, especially if you have some long running computation. I think the best way for you to get something close to is to make subgroups with headings and then when you have made the changes select the subgroup and run that part.
You can also use “Evaluate all cells” in the task bar.
It should also be noted that this is how most notebooks work. They do not dynamically update like spreadsheets.
As others have said: Mathematica is not it. It is a repl with history. Some of my notebooks take hours to recompute from scratch, I am usually carefully controlling what I am evaluating and when. Also I am vary tweaking existing expressions, since having real history of computations has saved me many times.
We should do our utmost to shorten the conceptual gap between the static program and the dynamic process.
It feels like a good way to explain and justify a bunch of approaches feel correct, but would otherwise be purely preferential. One I’m particularly fond of is arranging code in natural reading order from top to bottom rather than the opposite (C style). There the static program and dynamic process seem in sync.
What’s the natural reading order, though? If you read the top routine first, you don’t know what the subroutines do yet, so you can’t fully understand the function until much later, when you actually read the subroutines. And if you read the subroutines first, you don’t know what they are used for, and why you’re even bothering.
What happens in practice is that we start at the top level, and then constantly look up the API of each subroutine it uses (assuming it is properly documented, my condolences if you need to dig up the actual source of the subroutines).
That ultimately is the “natural reading order”. Not top down, not bottom up, but jumping around as we gather the information we need. And I don’t know of any way to write code that linearises that. The best we can do is have our IDE pop up a tool tip when we hover the subroutine name.
I think the main thing that’s missing from this article is a discussion of the value of guarantees. If I know the code doesn’t use goto, then it usually makes it much easier to read, because I don’t have to constantly be asking “but what if the flow control does something unexpected?” which is really distracting. You give up a certain amount of flexibility (the ability to jump to an arbitrary point of code) and in return you gain something much more valuable (code becomes easier to read and understand). Languages without early return offer similar advantages.
Reading order has the potential to offer a similar (but admittedly less valuable) guarantee. If you have to define something before you use it, then the answer to the question of “where is this thing I’m using defined?” is always “up”, which I have found to be very helpful. After getting used to this, I feel somewhat disoriented when reading code where it isn’t true.
Huh, I thought the consensus was that single-exit restrictions turned out to be a bad idea, because early exits allow you to prune the state space that needs to be considered in the following code. If you don’t have early exit, you have to introduce a variable to keep the state.
The main argument for single-exit was to make it easier to work with Hoare logic, but I think later formal systems were better at modelling more complicated flow control.
I haven’t heard that myself, but I should specify that I’m talking about entire languages designed around not having early returns (scheme, ocaml, erlang, etc; basically languages without statements) rather than using a language designed around having early returns and banning their use.
Yeah, the problems happen with the combination of the single-exit restriction and a statement-oriented language. Expression-oriented functional languages allow you to return a value from a nested if without having to unwind the nesting first.
In an expression oriented language, your conditionals branch out into a tree, and every branch returns a value, so there are no join points. If you need a join point, you use a (possibly local) helper function.
In a statement oriented language, you can do the same thing, where each branch of your conditionals ends in a return. If you don’t, if you let the conditionals fall through to a common statement, now you can’t “look up” and there’s no “coordinate” (loop variable) that helps you orient yourself. Doing single-return pretty much forces you to have join points.
While loops also create join points, but the loop condition helps orient you.
I think that when break and continue are confusing, it’s more about the join point (I don’t know what’s true after the jump) than the jump itself.
Huh, I thought the consensus was that single-exit restrictions turned out to be a bad idea
You can still return early without goto. As for the error handling goto enables, that’s mostly just C missing a defer statement. If you stick to the usual patterns, it’s just a variation on early returns.
To be honest your comment felt like a non sequitur: the comment you were replying to was making no mention of single-exit functions, either as a coding rule or as a language restriction, so I wasn’t quite sure why you brought it up.
Edit: reading Technomancy’s comment for the fifth time, I finally caught that little detail: “Languages without early return offer similar advantages”. Oops, my bad.
My second remark is that our intellectual powers are rather geared to master static relations and that our powers to visualize processes evolving in time are relatively poorly developed. For that reason we should do (as wise programmers aware of our limitations) our utmost to shorten the conceptual gap between the static program and the dynamic process, to make the correspondence between the program (spread out in text space) and the process (spread out in time) as trivial as possible.
For me, when I talk about natural reading order, I’m referencing the general idea that we read left to right, top to bottom (modulo non-LTR languages). In programming, we use abstractions all the time (modules, classes, methods, variables, etc.).
What’s the natural reading order, though? If you read the top routine first, you don’t know what the subroutines do yet, so you can’t fully understand the function until much later, when you actually read the subroutines. And if you read the subroutines first, you don’t know what they are used for, and why you’re even bothering.
I find that with reasonable intention revealing names, the first problem you list (that you cannot fully understand the function without reading every subroutine in it) is rarely a problem, because that’s the entire purpose of programming (to abstract unnecessary details in a way which makes it easy to understand large systems.
What the Dijkstra quote highlights succinctly to me is the idea that spatial and temporal equivalences have value in understanding software. Aligning things code which is defined spatially before with code which happens temporally before is a natural and reasonable approach. The opposite causes the need to read generally downwards when tracing the temporal nature of code, but upwards whenever it calls some sub part of the code. That to me is unnatural.
That ultimately is the “natural reading order”. Not top down, not bottom up, but jumping around as we gather the information we need. And I don’t know of any way to write code that linearises that. The best we can do is have our IDE pop up a tool tip when we hover the subroutine name.
It’s that jumping around that’s a problem. The spatial directionality of the jump being aligned with the temporal is relevant. You can make the same argument about this as an argument against inheritance in OOP. It’s effectively the same problem, temporal effects after are defined spatially before, which is inherently more difficult to visualize.
I’ve been tempted to write a clippy lint for rust that checks that methods in files are arranged topologically sorted (either top down or bottom up depending on the user’s preference). There’s nothing too difficult about the algorithm there. If A calls / references B, then the definition of A belongs before/after (per pref) B in any source code where they’re defined together.
All that is to say, I recognize that there are elements and rationales for the bottom-up (particularly long held practices, consistency, and familiarity), but where those rationales don’t exist, top-down should be preferred (in my subjective opinion - mostly based on reading / writing code for 30+ years).
For me, when I talk about natural reading order, I’m referencing the general idea that we read left to right, top to bottom (modulo non-LTR languages)
I figured that much. I just got past that, and to the problem of writing programs that match this order.
I find that with reasonable intention revealing names, the first problem you list (that you cannot fully understand the function without reading every subroutine in it) is rarely a problem
Let’s ignore my first paragraph, which I dampened in my second: “What happens in practice is that we start at the top level, and then constantly look up the API of each subroutine it uses”.
I can believe that you rarely have to look up the actual source code of the functions you use (if your code base has a good enough documentation, which in my experience has been far from systematic). But I don’t believe for a second you don’t routinely look up the documentation of the functions you use. It has been my overwhelming experience that function names are not enough to understand their semantics. We can guess the intent, but in practice I need more certainty than that: either I know the semantics of the function, or I have to look them up.
Even if all your functions are exquisitely documented, that doesn’t prevent you from having to jump around to their declaration — either manually, or by having your IDE pop up a tooltip.
because that’s the entire purpose of programming
X is true because that’s the purpose of Y is rarely a good argument. First you have to convince me that Y fulfils its purpose to begin with. As for programming specifically… I’ve seen things, and I don’t have much faith.
What the Dijkstra quote highlights succinctly to me is the idea that spatial and temporal equivalences have value in understanding software.
So far I agree.
Aligning things code which is defined spatially before with code which happens temporally before is a natural and reasonable approach.
It is above all a flat out impossible approach. Not just because of loops, but whenever you call a function, the documentation of that function is either above the current function, or below. And that’s if there’s a documentation at all: many internal subroutines (including a good portion of mine) are utterly devoid such.
Unless the name of the function is enough to reliably guess its purpose, which is often not the case at all, you have to look it up. Or down. And then you need to jump back. So unless you can write your subroutine right there where it’s called (something I actually encourage when the subroutine is called only once), you can’t avoid breaking the natural reading order. Because program flow is fundamentally non linear.
You can make the same argument about this as an argument against inheritance in OOP. It’s effectively the same problem, temporal effects after are defined spatially before, which is inherently more difficult to visualize.
Aahh, you may be conflating things a little bit. The real problem with inheritance, and many bad practices for that matter, is less the reading order than the lack of locality. I have an entire article on locality, and inheritance is fairly high on the list of things that breaks it.
Now sure, having a way to organise your program that makes it more likely that you find the code you need to read, even if it doesn’t decrease the physical distances between two related pieces of code, does decreases the mental effort you have to spend, which is the whole point of locality to begin with. I still believe though, that keeping code that is read together written together is more important than choosing which piece should be above or below — as long as it’s consistent.
“What’s the difference between concurrency and parallelism?” – a reasonable question
stupidest question ever. this is presumably just ‘regurgitate commander pike’s ontologically bankrupt definitions’
C
there is another fun thing in c (or ‘c’). standard bool/_Bool type is only ever supposed to be true/false and appropriately autoconverts on assignment. but, through various (illegal; hence ‘“c”’) abuses, you can have a register that the compiler thinks is storing a value of _Bool, but which in fact has a value other than 1 or 0 (assuming those are the representations of true and false), leading to unpredictable results
relatedly, something i have seen is to use random 32-bit (or however many you want) values for true and false, to try to protect against bitflips’ swapping one for the other. then e.g. switch (mybool) case true: case false: default: //bitflipped, idfk
What’s wrong with Rob Pike’s definition? It seems useful to distinguish between a performance technique and a code-organization technique. For example, a Datalog program can have a nice parallel cost model without any tricky concurrent semantics.
the main problem, to be clear, is that quizzing people on word definitions is not useful. the rest is window dressing on the cake:
the words do not really have consensus definitions. and insofar as they do, in the academy, ‘concurrent’ seems to agree with pike (events are concurrent if they are unordered in time), but ‘parallel’ is different—it is a more abstract property which is independence. c.f. leiserson wtf is parallelism, anyhow (though you can get fancier than DAGs). pike’s ‘parallelism’ seems to have something to do with concrete execution and scheduling, which i think makes much less sense. i would describe the relationship between events executed on different physical processors as physical concurrency (in physics nomenclature, i think it is ‘spacelike related’, as opposed to ‘timelike related’). i would say that parallel computations can always be executed concurrently, and that logically concurrent events may be physically concurrent, or not (this is a straightforward problem of refinement—it’s always legal to add extra relationships between unordered objects in a partial order). (but note that physical concurrency also applies to e.g. ILP in (a + b) + (c + d)—which in most cases will be ordered at the machine code/architectural level, but genuinely unordered at the physics level—so it’s not per se so simple as refinement always.) i would say that the problem of efficiently exploiting physical concurrency is scheduling
ofc fast and loose is morally correct… (and therefore strict languages are total too, and laziness is a bandaid since programs can still spuriously fail to terminate—but that is another rant..)
If the halting problem was solvable, then anyone with a computer could prove Goldbach’s conjecture in an afternoon.
Uh, nope. The halting problem could have been solvable with an astronomic complexity in the length of the program, and no one would have been able to afford the compute budget to run it on Goldbach.
First, write a bash script P1 that runs a SAT solver on every possible SAT problem and halts if any of them take exponential time.
This does not make any sense to me. If I tell you that SAT is in P but not what complexity it has, how can you possibly tell for any single SAT problem how long to wait to prove me wrong?
For all this I’m assuming that the halt detector runs in feasible time. It could be a galactic algorithm that provably checks halting but runs in too long a time to be usable. Even in that case, though, the existence of such an algorithm would reveal deep connections between all computable theorems, which would itself be one of the greatest developments in mathematics.
It’s not the same thing being discussed here, but y’all might like Impagliazzo’s discussion of average-case complexity, a different from the common CS focus on worse-case complexity, where we find a case where something is like another problem or is impossible. Most folks think that symmetric cryptography exists–i.e., that you can make a block cipher that doesn’t easily yield the key given known plaintext. I haven’t seen a survey of cryptographers or anything, but most probably think a successful block cipher can even be a pretty simple one. But we haven’t proven much about this at all! Then asymmetric cryptography is a whole other mess.
Where the halting problem is about stuff you can’t compute in principle, this is more about how we think it’s impractical to compute some things that are computable in principle (but haven’t proven much about it).
Worst case and average case were discussed a lot in my complexity theory courses as an undergrad. Quicksort is the canonical case of example of an algorithm that has great average-case complexity but much worse worst-case complexity. This also comes up a lot in security where an attacker will often try to find the worst case for you. For example, there are a bunch of DoS attacks that rely on sending data with a distribution that will cause collisions in hash function used for a hash table. If the hash table does secondary chaining, an attacker who can craft collisions can make the system go from the constant-time average case to the linear-time worst case.
This does not make any sense to me. If I tell you that SAT is in P but not what complexity it has, how can you possibly tell for any single SAT problem how long to wait to prove me wrong?
That’s an interesting question! The usual science answer is “measure really really carefully”, but I have no real idea how you’d do that here. Honestly, just counting the instructions consumed by each iteration as you increase input size should be able to tell you pretty quickly, but an average desktop is full of noise sources that can mess with that count. Still, with a carefully written SAT solver and a good profiler I think it’s feasible.
You are pointing out that it’s not easy to map from “how much computation steps should this take” to “how long to wait before timing out”. But I was pointing at something different:
Even if you know the precise asymptotic complexity of a problem, you cannot predict the number of computation steps it will take on any given input, because asymptotic complexity is a property “at the limit”.
If you know that something has polynomial complexity, you don’t know what the polynomial formula is to compute the number of steps (maybe the formula is 10^7 + 10^7 * x^1000), so you cannot predict the actual number of steps it should take, even at the limit.
Basically you cannot, after only a finite number of observations, disprove the claim that something has polynomial or O(n) or O(1) complexity, so I don’t see how you would turn this into a monitor to feed to the halting problem as claimed.
If you can nest calls to the halting oracle then you can do “is f in O(g)” using discrete definition of asymptotics, which is nice because there are no limits involved, just exists and forall.
Something like:
from turing import halts
def naturals():
i = 0
while True:
i += 1
yield i
def f_in_order_g(f, g):
# f in O(g) if:
# exists n,k in naturals such that
# forall i in naturals,
# f(i+k) <= n*g(i+k)
def n_machine():
for n in naturals():
def k_machine():
for k in naturals():
def i_machine():
for i in naturals():
if f(i+k)>n*g(i+k): return
if not(halts(i_machine)): return
if halts(k_machine): return
return halts(n_machine)
Note that the existence of a halting oracle is a much stronger property than the decidability of the halting problem, as summarized by 0x2ba22e11 above:
If you can nest calls to the halting oracle
(If you only assume that the halting problem is decidable, then you cannot call halt on a function that itself uses halt, only on base programs.)
Union finds can be implemented in different styles. An arena style or a refcell/pointer style.
What’s an “arena-style union find”? Is that where you use a separate dictionary that maps from node ID to the representative ID of its equivalence class? I guess that’s like an area in that you can control when that dictionary is freed.
There are a couple different styles which amount to similar things. A common style is to have pointers or a refcell and you actually pointer chase up the union find. You call malloc or new to make a new union find variable. A different style is to use a vector and push on it when you want a new union find variable. The union find ids then reference an index inside this vector. A third style uses dictionaries, which can be nice if you don’t want to have uninterpretable ids. It also maybe makes more sense in a pure functional programming context. The latter two styles are easier to traverse, eagerly compress and serialize. The first style needs something like the magic abilities of a garbage collector to do that. I personally heavily prefer the second style
“No modes” argues against the vi user interface, but I like vi
I had the same reaction when I read The Humane Interface (which provides a great explanation of why modes are bad). I came to the conclusion that modes are less bad, and possibly good, when they align with a cognitive switch. For me, writing and editing are different tasks and I want to treat them as different, in the same way that my writing improved when I started using tools that made writing and typesetting into distinct tasks.
I thought this article was interesting as another angle on the trouble a system can get into when a cache is empty. One of the greatest pieces of writing in this area is by Colm MacCárthaigh on avoiding modality by designing a system to do constant work. I’m slightly surprised it hasn’t been shared here before
But most caches have modes. So, when a cache is empty, response times get much worse, and that can make the system unstable. Worse still, when a cache is rendered ineffective by too much load, it can cause a cascading failure where the source it was caching for now falls over from too much direct load
I wish there was a date on that blog post
The other word I’ve heard for that is “metastable state”, an analogy from physics:
If cache contents are lost in the vulnerable state, the database
will be pushed into an overloaded state with elevated latency.
Unfortunately, the cache will remain empty since the web
application is responsible for populating the cache, but its
timeout will cause all queries to be considered as failed. Now
the system is trapped in the metastable failure state: the
low cache hit rate leads to slow database responses, which
prevents filling the cache. In effect, losing a cache with a 90%
hit-rate causes a 10× query amplification
That explanation is really interesting because I didn’t realize (or maybe just didn’t appreciate) that the application is part of the cause. The database+cache+application together has two stable states.
The database should help by letting some requests fail so that some can succeed with low latency. But the application could do that too: reject some http requests.
Vi modes are very different from “ok / failure” kinds of modes. In Vi they’re just different surface areas for interacting with the same thing.
In “modal software” as the article describes, failure modes are inherently unusual. Maybe some would call them “exceptional” (heh) cases.
You can bring them to the same level of normalcy by doing the same thing for the happy and sad paths, but you can also re-architect such that there’s no distinction at all. Data center on fire? Latency will go up slightly until its replaced, but still be within the bounds your QoS agreement. You get into trouble when you try to squeeze margins like this to zero. Not right away though. Sometime in the vague future when you can hope it has turned into someone else’s problem.
Well, you can always pad there as well. Since this would probably be used mostly for faster debug builds, a larger binary would not be a huge problem. So I think it could work.
Exposing current buffer / window state to external programs
Interesting! For the past couple of years, I became convinced that we are missing a “thin waist” roughly in this area, and started sketching out some design (just a very rough outline at this moment): https://github.com/matklad/abont
EDIT: reading the opening paragraph of https://research.swtch.com/acme.pdf is illuminating. Indeed, what I want is acme without mouse and with syntax highlighting.
I’ve never used acme myself, but I’ve admired it from afar.
On Unix, if you’re writing code to deal with an interactive program, you can be notified when the program produces output, but you have no idea when the program is waiting for input. You can say “if nothing has been printed in half a second, it’s probably waiting for input” but that’s about as close as you get.
On Plan9, when the interactive program calls read() on stdin, that goes via the VFS and calls your program’s read() handler. You can respond with data, you can twiddle your thumbs, you can wait for the user to type a response, whatever you like.
Because Plan9 provides this intimate connection between interacting programs, a “terminal” on Plan9 is much closer to a Unix pipe than a Unix pty, being just a log of communications in each direction. As a result, the gap between “a terminal” and “an editor buffer” is much smaller, and a tool like acme becomes a lot more straightforward.
There’s tools that try to reproduce parts of the Plan9 system on Unix, like Plan 9 from User Space, 9term, and wily. Unfortunately, because Plan9 semantics aren’t quite like POSIX semantics, either things don’t work reliably, or you’re cut off from the POSIX world and can only talk to “true” Plan9 tools.
This plus modal key bindings was what my starting point was for ad. The current state of the project is also an exercise in “how far can I get using only the standard library” which is why the only dependency other than libc is bitflags (used in the 9p implementation which has now been moved out to another crate).
I’ve had a look at the design you propose in abont and there are quite a few similarities with what I’m aiming for with ad and what I really like about acme. There is a fantastic screencast from Russ Cox that I link to in the README which does a good job of showing the sorts of things that are possible with acme. My main issue with using acme as a daily driver is the heavy focus on relying on the mouse rather than allowing you to define custom key bindings. That side of ad is all working pretty well, but I suspect there’s a fair amount left to do in terms of how the text buffers themselves are managed. I also really need to port the layout logic from Penrose to work with it at some point soon(!)
Hm interesting, yeah I’d call both the Abont proposal and Acme “exterior narrow waists” [1] – a narrow waist between processes – IPC and polyglot – rather than the “interior” Emacs Lisp model
Although I don’t understand the Rust point. Isn’t the whole idea of IPC that you can use any language? Using any language makes it more open too
And I agree that say Warp appears to be building an “app” and not an extensible architecture, which seems to be a big difference between open and closed
I think the headless protocol of Oils is naturally complementary to a UI protocol like this:
The slogan for the headless shell is that the shell UI shouldn’t be a terminal – it should have a terminal (for the subprocesses)
So you could make a shell UI in a new paradigm, but reuse the entire shell language, and all existing terminal tools. I’d say you still need a terminal in any new paradigm, unless you are OK with colors in Cargo / Clang / GCC / grep not working.
(And obviously VSCode has a terminal, I think Emacs and neovim do too. Emacs also has its own shell, eshell, but I think that’s not the right approach.)
I mentioned “addition of waists” as a powerful pattern here
I am not sure if the headless protocol is an M x N waist yet … I guess we need another shell to implement it ;) But it is an open and tiny protocol, like 200 lines. The main idea is to pass a terminal file descriptor over a Unix socket.
One issue is Windows, and I have been wondering on Zulip how you actually use the new terminal APIs on Windows. I think you can do it with native Win32, and you don’t need WSL. And I think Windows probably has some kind of FD passing between processes too?
[1] or maybe “exterior M x N waist”, because I got feedback from networking engineers about “narrow waist”. I don’t want to “stomp on” the terminology of an adjacent field
This doesn’t seem like a misuse to me—isn’t IP exactly the same kind of NxM narrow waist? Instead of web, email, video streaming etc all having to implement Ethernet, Wi-Fi, 3g separately, they all sit on top of IP which handles the differences.
I don’t feel like I grok what Abont is all about. Is it essentially that you want to create an extensible programming environment (Emacs like) but want to be able to control is via external processes with an API?
Yup, that’s basically it: emacs presentation model, but with IPC instead of mutable global lisp image. I wouldn’t want abont if emacs was good enough for me. But I think there’s a bunch of smaller things which could be done better now:
better language for internal extensibility
better ways of scaling package ecosystem with less coordination (IPC is a means to that)
The Allocation Cancelling sounds pretty similar to the reuse tokens in Perceus. But Perceus uses refcounting, so it can shallow copy and share the subtrees, while it looks like Neut has to deep copy because every subtree is uniquely owned.
I’m curious in what situations the refcounting vs unique ownership is better. In particular, what are some cases where Neut is forced to deep copy, but a GCed language or Perceus wouldn’t?
In Neut, the “copy” and “dispose” operations are abstract: each type contains two functions that implement these operations. If you define the copy function to increment a reference count, and the dispose function to decrement a reference count and free on 0, then instances of that type will be reference counted in Neut.
So despite what the author says, I don’t think Neut forces deep copying. You could select between ref counting and deep copying on a type-by-type basis based on what gives better performance in benchmarks.
I like this pictorial one “for eight year olds”: https://worrydream.com/AlligatorEggs/
I especially like how 2D it is: using horizontal vs vertical layout to stand for application vs abstraction.
Apparently snapshot testing’s used in some front end frameworks to for component testing, but I’ve never seen anything like this before and the dev experience is literally breathtaking. What else have I been missing?
I use snapshot testing all the time, for everything! If I can’t write a fuzz/property-based test, I write snapshot-test. To the first approximation, anything more complicated than one
assert(a == b)per test is worth moving to a snapshot.Though, I don’t like the style where the snapshot is in a separate file, it makes small tests harder to read. By default, I specify snapshots inline, as a string literal, and use file only for gigantic outputs.
It’s also worth knowing that snapshot testing is very easy to implement, you don’t need a fancy library to start doing it (though, a library certainly has additional bells and whistles):
https://tigerbeetle.com/blog/2024-05-14-snapshot-testing-for-the-masses/
Do you see property-based testing as a replacement for example-based testing?
In other words, when it’s possible to write a property-based test, do you treat that as the first line of defense against bugs in that code? This way of working appeals to me because I’d rather come up with a clear specification than a mountain of examples.
A counterargument is that it’s useful to have both: ideally you would have enough coverage from examples, but the fuzzer serves as a backstop. The examples test the (correctness of) the code, and the fuzzer tests the (completeness of) the examples.
I wonder if the best would actually be a combination:
You could think of this as a corpus-driven property-based test. The examples make it easy to know what’s covered, and the spec makes it easy to know that the expected-outputs are actually correct.
I don’t think I can compress my full decision tree into a single commit box, but the top points are that you should thing about fuzzing/PBT/DST first, as those are high-investment/high-payoff techniques, and otherwise fallback to snapshot testing as a default low-investment technique.
Another way to refer to this technique is “golden file” testing.
I’ve used this technique for backend testing for many years, it is great, but you need to make sure your output is fully deterministic, which is a bit of pain when having generated IDs or timestamps.
The best libraries have a way to replace those values with placeholders. If not, you need to sanitize your output manually before passing it to the snapshot.
It reminds me of ppx_expect, which is similar but saves the snapshot inline and also supports things like snapshotting stdout.
Taken to an extreme (in a good way) is Ian Henry’s My Kind of REPL (discussion).
This is cool: I see it as a wrapper that encapsulates a common pattern. In OO style code I would enforce an invariant in the constructor, but then have to be careful to preserve it everywhere else (every setter, and every getter that exposes write access). I’d much rather only say “enforce this invariant”. (Reminds me of the difference between new/delete and std::unique_ptr in C++: the latter is a more declarative way to get the behavior I want.)
But I thought “refinement types” only refers to type systems that prove at compile time that the predicate is always true, like Liquid Haskell. And if I understand correctly that’s not what this utility is for: it’s a safer way to declare that a condition is dynamically enforced.
I think it depends on how much of a purist you want to be. It’s certainly not full fledged in the sense of Idris or Liquid Haskell, but it’s also much more than you’d be able to achieve in most OO languages (with the implication feature specifically of interest).
With richer support in the type system (disjunction, negation, etc.) we could get pretty close, but Rust isn’t there quite yet (and may never be!).
At the end of the day, some dynamism is needed to deal with external input though. You can’t get away from that.
Yeah, I don’t disagree with any design choices you’re showing here. I like that it encourages the “parse don’t validate” style. I hadn’t thought about the implication feature but I can see that being useful. I definitely agree with the choice to make a library rather than a separate type checker!
I’m only objecting to calling it “refinement types”, if that term has an existing narrower meaning (and I’m not an expert so I could be wrong about that). To avoid confusion it could have a different name, but one that still captures the benefit it gives you.
(My emphasis.) This reminds me of something I’ve been trying to express recently!
Don’t look up the stack. Function bodies don’t know who is calling them. There is no “current client” or “current request”.
I think there are multiple reasons to follow this:
You want the function signature and docstring to be a communication boundary, an interface. In theory this is what people read to check that they’re calling or implementing that function correctly. A comment in a function body that “knows” something farther away than the function signature is making an assumption that nobody else has agreed to uphold.
You want functions to be understandable in isolation. The caller depends on the callee, so if the callee also depends on the caller then it’s a cycle where you need to understand both. To me this feels related to data being simpler when it’s acyclic: I can zoom in on a subpart and understand it completely.
You want functions to be testable; you want to see input/output examples. A function that knows about a “current request” has a large input, but likely ignores most of it, so you don’t know how to create a good input example. This large input also isn’t obvious from the function signature so you may forget.
If anyone else is curious, I can highly recommend the linked Ten Minute Physics tutorials. The creator, Matthias Müller, also has a ton of (fairly fundamental!) papers in the field of real-time physics simulation, and you can tell he really understands what he’s talking about. They’re some of the easiest to understand tutorials out there, in a field which can be quite overwhelming.
That looks fantastic, thank you! You should submit it as a top-level story.
I really appreciate his emphasis on keeping it simple: easy to explain and implement. When I read other game physics tutorials years ago I thought you need complex integration techniques like RK4 and I didn’t understand how that fits into the rest of the game loop. (Do you need to have multiple copies of the game state around to average them? How do you handle entities that appear or disappear during the simulation?) By contrast I think Matthias is saying you can use a smaller timestep, and don’t try to use very-stiff springs to enforce constraints.
For interactive use, sometimes I’d do this trick:
But I’d probably also complain if I saw this in code review :P
oh that’s evil but definitely a helpful tip. Thanks for sharing it!
Would it be even better to advance whichever side’s frontier (the queue) is currently smaller? It seems like the frontier is the part you have to iterate, while the visited set is a hash lookup, so the size of the frontier would matter more.
Having tried both, there doesn’t seem to be any difference in performance. Said otherwise, the performance gain is the same whether you check the count of visited nodes or the size of the queue. I agree however that checking on queue size matches more the explanation I give later in the article, so I’ll change that.
I think these two claims are at odds:
Offering more introspection means the language has fewer guarantees. In Python I can’t be sure whether, say
foo(lambda x: x)andfoo(lambda x: [x][0])behave the same becausefoocould inspect the code of the lambda. In Haskell I know thatfoo (\x -> x)andfoo (\x -> head [x])are the same, because lambdas are opaque.It seems like a language for formal specification would benefit more from limitations than flexibility: to make it easier to see, and be sure, that two programs are equivalent.
This is really cool: in the example there’s a login process which is sequential but it plays out across different machines. This language lets you express that logic sequentially.
It reminds me of the difference between callbacks and async/await: physically I need to schedule some continuation to run when an event happens, but logically I want to think about the overall sequential process.
It would be cool to have a debugger for choreography! It would let you debug a distributed-but-sequential process like any other sequential process.
So if I understand things correctly, the syntax of the object-language (SQL) is extendable from the meta-language (Go, in the post).
This makes me wonder: what if a object-language (imagine some new language, not SQL) had construct that allowed it to extend itself (from inside itself)? I suppose one would need to provide the semantics for the new syntax somehow? Even merely allowing sugar for already existing constructs seems like fun though.
From my quick read of the post, I didn’t see that the question of semantics was covered? In DuckDB’s do they always desugar into SQL or do they allow for SQLite-style extensions that provide new semantics for the new syntax?
This also reminds me of META II, which I’ve never fully understood. Is there anyone around who does and who can relate it to the post?
In Scheme you can introduce new syntax by defining it as a macro. In some flavors like Racket, you can run arbitrary code at compile time to do the syntax transformation. The semantics (scoping, type checking, evaluation) are all defined by what your macro expands to.
Given that Scheme’s concrete syntax (the syntax that the user writes) is also its abstract syntax (the datatype that the interpreter/compiler operates on), I’d argue it’s not as impressive.
Racket’s
#langis more interesting, as it actually changes the concrete syntax. Do you know if there’s a document that describes how it’s implemented? Searching around I can only find documentation on how to use it.It’s true that Racket macros have an easier time because the input is already nicely parenthesized. But it is pretty powerful in that you can create custom control flow or type systems. Match really is a mini-language which you can further extend with custom view patterns.
If you wanted more control over the concrete syntax, you could imagine a macro that takes a string literal and parses it, like (infix “2+3*x”) -> (+ 2 (* 3 x)). Then #lang could work by wrapping the entire file in a macro like (my-language “…file contents…”). I don’t remember if that’s the interface though. It might be more like “implement a custom (read <port>) function”.
I think the target language, rather than the source language, is the main limitation. Desugaring to Racket’s core means you inherit its flexibility (tail calls, callcc, garbage collection) and limitations (little control over memory layout, less opportunity than SQL for very high level optimization).
I found this: https://beautifulracket.com/explainer/lang-line.html#mechanics, although it might still not be as detailed as what you’re looking for.
The #lang starts by running your custom reader, and then you return a single syntax object for the whole module. Then macro expansion continues from there.
Found this:
But still merely seems to describe how to use the library rather than how the library is implemented. (What I’d really like is something minimal, like lambda calculus + the smallest possible extension that allows one to do this.)
Oh, sounds like maybe you’re interested in the mechanics of how syntax objects are implemented? These are probably the most relevant:
syntax-casefor and explains what’s happening inside those opaque syntax objects. Racket used to work this way.Just stumbled across this: https://seed7.sourceforge.net/faq.htm#extensible_programming
My first thought is that anything resembling a compiler is a form of precomputation. A tree-walking interpreter might do a string hash-table lookup for every local variable it visits. To precompute that, you can translate the program to something else (bytecode maybe) that has numeric offsets instead of variable names. Python’s
re.compile, or Bison-style parser generators, or prepared statements in SQL are all compiler-like interfaces: they let you create a program in one step and then run it in a later step.The
re.compileexample reminds me that there are some clever string-search algorithms that involve precomputing something from the search query. You wouldn’t normally think of a little string like"foo"as a program, butgrep "foo"is sort of an interpreter, so internally it could “compile” that little string to some other form if that speeds up the search in a large input file.Another kind of precomputation is string interning, and the more general hash consing.
In fact it does exactly that, kinda. It does not actually compile anything but it will use boyers-moore for literal searching instead of running the regex normally.
I would rather say that interpreters are the opposite of precomputation: Instead of the computer being programmed to “do the thing” it is instead programmed to do stuff just-in-time by fetching the actual instructions later and lazily which will then “do the thing”. (which is not to say that it’s wrong or bad to do that.)
I’m not sure I understand what is concretely the problem, and what exactly is the Displayed state in this case? Is it just buggy which I find hard to believe?
What operations in general are you trying to do with 1e5 rows?
i believe it is intended behaviour. a very simple example:
b will still be 6 and the second cell will still show 6
Most notebook technologies are not “reactive” the way that spreadsheets are.
(Back in the day I gave a somewhat infamous talk about this: https://www.youtube.com/watch?v=7jiPeIFXb6U )
Marimo is a reactive notebook that I believe behaves the way you’re looking for, I haven’t really used it much though:
https://marimo.io/
I enjoyed watching that talk! Humorous and well-argued with lots of examples.
Great talk!
I was curious about Marimo but it looks like it still has most of this hidden state. It detects dependencies between cells when they read and write the same global variable, but it doesn’t see the dependency when they read and write the same object on the heap.
I wonder if it’s possible to design a notebook for Python that detects all the dependencies, with some kind of read and/or write barrier in the interpreter.
Related projects have tried to catch more dependencies (such as ipyflow), but inevitably fail to catch all, yielding a programming environment that makes it difficult to reason about the dataflow graph formed, and hard to predict what will run and when. Only handling global variables is at least tractable and the resulting graph is easily understood by the notebook author, and still eliminates a large class a bugs that are typically encountered in traditional notebooks; for example, deleting a cell will delete its variables in marimo and invalidate cells that use those variables, but not in traditional notebooks.
Before developing marimo (I am one of the developers), I saw this model work well for Pluto.jl (https://github.com/fonsp/Pluto.jl), which is our biggest inspiration.
Detecting all memory reads and writes sounds like an interesting research project. I am not sure it would lead to a better developer experience. But it would certainly be interesting to see it attempted.
Would it make sense to verify that no global variables outside the dataflow graph have changed after execution? If you can’t track ’em all, you could at least warn the user.
This is mostly why I never really understood the use case for Notebooks to begin with.
Agreed, it gets confusing which parts of my notes are still up to date. Maybe not automatic updates, but some staleness indicator could be the solution.
I consider this a feature of Mathematica, especially if you have some long running computation. I think the best way for you to get something close to is to make subgroups with headings and then when you have made the changes select the subgroup and run that part.
You can also use “Evaluate all cells” in the task bar.
It should also be noted that this is how most notebooks work. They do not dynamically update like spreadsheets.
As others have said: Mathematica is not it. It is a repl with history. Some of my notebooks take hours to recompute from scratch, I am usually carefully controlling what I am evaluating and when. Also I am vary tweaking existing expressions, since having real history of computations has saved me many times.
Having said that there was a new linked cell feature in 14.1: https://writings.stephenwolfram.com/2024/07/yet-more-new-ideas-and-new-functions-launching-version-14-1-of-wolfram-language-mathematica/
I didn’t have a chance to play with it yet.
That Djijkstra quote is great.
It feels like a good way to explain and justify a bunch of approaches feel correct, but would otherwise be purely preferential. One I’m particularly fond of is arranging code in natural reading order from top to bottom rather than the opposite (C style). There the static program and dynamic process seem in sync.
What’s the natural reading order, though? If you read the top routine first, you don’t know what the subroutines do yet, so you can’t fully understand the function until much later, when you actually read the subroutines. And if you read the subroutines first, you don’t know what they are used for, and why you’re even bothering.
What happens in practice is that we start at the top level, and then constantly look up the API of each subroutine it uses (assuming it is properly documented, my condolences if you need to dig up the actual source of the subroutines).
That ultimately is the “natural reading order”. Not top down, not bottom up, but jumping around as we gather the information we need. And I don’t know of any way to write code that linearises that. The best we can do is have our IDE pop up a tool tip when we hover the subroutine name.
I think the main thing that’s missing from this article is a discussion of the value of guarantees. If I know the code doesn’t use
goto, then it usually makes it much easier to read, because I don’t have to constantly be asking “but what if the flow control does something unexpected?” which is really distracting. You give up a certain amount of flexibility (the ability to jump to an arbitrary point of code) and in return you gain something much more valuable (code becomes easier to read and understand). Languages without early return offer similar advantages.Reading order has the potential to offer a similar (but admittedly less valuable) guarantee. If you have to define something before you use it, then the answer to the question of “where is this thing I’m using defined?” is always “up”, which I have found to be very helpful. After getting used to this, I feel somewhat disoriented when reading code where it isn’t true.
Huh, I thought the consensus was that single-exit restrictions turned out to be a bad idea, because early exits allow you to prune the state space that needs to be considered in the following code. If you don’t have early exit, you have to introduce a variable to keep the state.
The main argument for single-exit was to make it easier to work with Hoare logic, but I think later formal systems were better at modelling more complicated flow control.
I haven’t heard that myself, but I should specify that I’m talking about entire languages designed around not having early returns (scheme, ocaml, erlang, etc; basically languages without statements) rather than using a language designed around having early returns and banning their use.
Yeah, the problems happen with the combination of the single-exit restriction and a statement-oriented language. Expression-oriented functional languages allow you to return a value from a nested
ifwithout having to unwind the nesting first.I think the core problem is join points.
In an expression oriented language, your conditionals branch out into a tree, and every branch returns a value, so there are no join points. If you need a join point, you use a (possibly local) helper function.
In a statement oriented language, you can do the same thing, where each branch of your conditionals ends in a return. If you don’t, if you let the conditionals fall through to a common statement, now you can’t “look up” and there’s no “coordinate” (loop variable) that helps you orient yourself. Doing single-return pretty much forces you to have join points.
While loops also create join points, but the loop condition helps orient you.
I think that when break and continue are confusing, it’s more about the join point (I don’t know what’s true after the jump) than the jump itself.
You can still return early without
goto. As for the error handlinggotoenables, that’s mostly just C missing adeferstatement. If you stick to the usual patterns, it’s just a variation on early returns.I was referring to languages with loops but without things like break or continue, and when return can only appear at the end of the function.
To be honest your comment felt like a non sequitur: the comment you were replying to was making no mention of single-exit functions, either as a coding rule or as a language restriction, so I wasn’t quite sure why you brought it up.
Edit: reading Technomancy’s comment for the fifth time, I finally caught that little detail: “Languages without early return offer similar advantages”. Oops, my bad.
The full quote in Goto Considered Harmful is:
For me, when I talk about natural reading order, I’m referencing the general idea that we read left to right, top to bottom (modulo non-LTR languages). In programming, we use abstractions all the time (modules, classes, methods, variables, etc.).
I find that with reasonable intention revealing names, the first problem you list (that you cannot fully understand the function without reading every subroutine in it) is rarely a problem, because that’s the entire purpose of programming (to abstract unnecessary details in a way which makes it easy to understand large systems.
What the Dijkstra quote highlights succinctly to me is the idea that spatial and temporal equivalences have value in understanding software. Aligning things code which is defined spatially before with code which happens temporally before is a natural and reasonable approach. The opposite causes the need to read generally downwards when tracing the temporal nature of code, but upwards whenever it calls some sub part of the code. That to me is unnatural.
It’s that jumping around that’s a problem. The spatial directionality of the jump being aligned with the temporal is relevant. You can make the same argument about this as an argument against inheritance in OOP. It’s effectively the same problem, temporal effects after are defined spatially before, which is inherently more difficult to visualize.
I’ve been tempted to write a clippy lint for rust that checks that methods in files are arranged topologically sorted (either top down or bottom up depending on the user’s preference). There’s nothing too difficult about the algorithm there. If A calls / references B, then the definition of A belongs before/after (per pref) B in any source code where they’re defined together.
All that is to say, I recognize that there are elements and rationales for the bottom-up (particularly long held practices, consistency, and familiarity), but where those rationales don’t exist, top-down should be preferred (in my subjective opinion - mostly based on reading / writing code for 30+ years).
I figured that much. I just got past that, and to the problem of writing programs that match this order.
Let’s ignore my first paragraph, which I dampened in my second: “What happens in practice is that we start at the top level, and then constantly look up the API of each subroutine it uses”.
I can believe that you rarely have to look up the actual source code of the functions you use (if your code base has a good enough documentation, which in my experience has been far from systematic). But I don’t believe for a second you don’t routinely look up the documentation of the functions you use. It has been my overwhelming experience that function names are not enough to understand their semantics. We can guess the intent, but in practice I need more certainty than that: either I know the semantics of the function, or I have to look them up.
Even if all your functions are exquisitely documented, that doesn’t prevent you from having to jump around to their declaration — either manually, or by having your IDE pop up a tooltip.
X is true because that’s the purpose of Y is rarely a good argument. First you have to convince me that Y fulfils its purpose to begin with. As for programming specifically… I’ve seen things, and I don’t have much faith.
So far I agree.
It is above all a flat out impossible approach. Not just because of loops, but whenever you call a function, the documentation of that function is either above the current function, or below. And that’s if there’s a documentation at all: many internal subroutines (including a good portion of mine) are utterly devoid such.
Unless the name of the function is enough to reliably guess its purpose, which is often not the case at all, you have to look it up. Or down. And then you need to jump back. So unless you can write your subroutine right there where it’s called (something I actually encourage when the subroutine is called only once), you can’t avoid breaking the natural reading order. Because program flow is fundamentally non linear.
Aahh, you may be conflating things a little bit. The real problem with inheritance, and many bad practices for that matter, is less the reading order than the lack of locality. I have an entire article on locality, and inheritance is fairly high on the list of things that breaks it.
Now sure, having a way to organise your program that makes it more likely that you find the code you need to read, even if it doesn’t decrease the physical distances between two related pieces of code, does decreases the mental effort you have to spend, which is the whole point of locality to begin with. I still believe though, that keeping code that is read together written together is more important than choosing which piece should be above or below — as long as it’s consistent.
Exactly. It’s different for different people, and also different depending on what you’re actually looking for in the program you’re reading.
As a mathematician, I find it much more natural to define things before using them.
guessed: ‘true/false/bot’ from the title—bang on
stupidest question ever. this is presumably just ‘regurgitate commander pike’s ontologically bankrupt definitions’
there is another fun thing in c (or ‘c’). standard bool/_Bool type is only ever supposed to be true/false and appropriately autoconverts on assignment. but, through various (illegal; hence ‘“c”’) abuses, you can have a register that the compiler thinks is storing a value of _Bool, but which in fact has a value other than 1 or 0 (assuming those are the representations of true and false), leading to unpredictable results
relatedly, something i have seen is to use random 32-bit (or however many you want) values for true and false, to try to protect against bitflips’ swapping one for the other. then e.g. switch (mybool) case true: case false: default: //bitflipped, idfk
What’s wrong with Rob Pike’s definition? It seems useful to distinguish between a performance technique and a code-organization technique. For example, a Datalog program can have a nice parallel cost model without any tricky concurrent semantics.
the main problem, to be clear, is that quizzing people on word definitions is not useful. the rest is window dressing on the cake:
the words do not really have consensus definitions. and insofar as they do, in the academy, ‘concurrent’ seems to agree with pike (events are concurrent if they are unordered in time), but ‘parallel’ is different—it is a more abstract property which is independence. c.f. leiserson wtf is parallelism, anyhow (though you can get fancier than DAGs). pike’s ‘parallelism’ seems to have something to do with concrete execution and scheduling, which i think makes much less sense. i would describe the relationship between events executed on different physical processors as physical concurrency (in physics nomenclature, i think it is ‘spacelike related’, as opposed to ‘timelike related’). i would say that parallel computations can always be executed concurrently, and that logically concurrent events may be physically concurrent, or not (this is a straightforward problem of refinement—it’s always legal to add extra relationships between unordered objects in a partial order). (but note that physical concurrency also applies to e.g. ILP in (a + b) + (c + d)—which in most cases will be ordered at the machine code/architectural level, but genuinely unordered at the physics level—so it’s not per se so simple as refinement always.) i would say that the problem of efficiently exploiting physical concurrency is scheduling
ofc fast and loose is morally correct… (and therefore strict languages are total too, and laziness is a bandaid since programs can still spuriously fail to terminate—but that is another rant..)
Uh, nope. The halting problem could have been solvable with an astronomic complexity in the length of the program, and no one would have been able to afford the compute budget to run it on Goldbach.
This does not make any sense to me. If I tell you that SAT is in P but not what complexity it has, how can you possibly tell for any single SAT problem how long to wait to prove me wrong?
The compute budget case is covered in a footnote:
It’s not the same thing being discussed here, but y’all might like Impagliazzo’s discussion of average-case complexity, a different from the common CS focus on worse-case complexity, where we find a case where something is like another problem or is impossible. Most folks think that symmetric cryptography exists–i.e., that you can make a block cipher that doesn’t easily yield the key given known plaintext. I haven’t seen a survey of cryptographers or anything, but most probably think a successful block cipher can even be a pretty simple one. But we haven’t proven much about this at all! Then asymmetric cryptography is a whole other mess.
Where the halting problem is about stuff you can’t compute in principle, this is more about how we think it’s impractical to compute some things that are computable in principle (but haven’t proven much about it).
Quick definition of his “five worlds”: https://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
And an interview: https://www.quantamagazine.org/the-researcher-who-explores-computation-by-conjuring-new-worlds-20240327/
Worst case and average case were discussed a lot in my complexity theory courses as an undergrad. Quicksort is the canonical case of example of an algorithm that has great average-case complexity but much worse worst-case complexity. This also comes up a lot in security where an attacker will often try to find the worst case for you. For example, there are a bunch of DoS attacks that rely on sending data with a distribution that will cause collisions in hash function used for a hash table. If the hash table does secondary chaining, an attacker who can craft collisions can make the system go from the constant-time average case to the linear-time worst case.
That’s an interesting question! The usual science answer is “measure really really carefully”, but I have no real idea how you’d do that here. Honestly, just counting the instructions consumed by each iteration as you increase input size should be able to tell you pretty quickly, but an average desktop is full of noise sources that can mess with that count. Still, with a carefully written SAT solver and a good profiler I think it’s feasible.
You are pointing out that it’s not easy to map from “how much computation steps should this take” to “how long to wait before timing out”. But I was pointing at something different:
Basically you cannot, after only a finite number of observations, disprove the claim that something has polynomial or O(n) or O(1) complexity, so I don’t see how you would turn this into a monitor to feed to the halting problem as claimed.
If you can nest calls to the halting oracle then you can do “is f in O(g)” using discrete definition of asymptotics, which is nice because there are no limits involved, just exists and forall.
Something like:
Amazing
The halting oracle can make a countably infinite number of observations!
Note that the existence of a halting oracle is a much stronger property than the decidability of the halting problem, as summarized by 0x2ba22e11 above:
(If you only assume that the halting problem is decidable, then you cannot call
halton a function that itself useshalt, only on base programs.)I think you meant to reply to the comment above mine?
Anyway yes that is a good explanation of the crux of why a halting oracle can solve just about any problem that we can write down. :)
What’s an “arena-style union find”? Is that where you use a separate dictionary that maps from node ID to the representative ID of its equivalence class? I guess that’s like an area in that you can control when that dictionary is freed.
There are a couple different styles which amount to similar things. A common style is to have pointers or a refcell and you actually pointer chase up the union find. You call malloc or new to make a new union find variable. A different style is to use a vector and push on it when you want a new union find variable. The union find ids then reference an index inside this vector. A third style uses dictionaries, which can be nice if you don’t want to have uninterpretable ids. It also maybe makes more sense in a pure functional programming context. The latter two styles are easier to traverse, eagerly compress and serialize. The first style needs something like the magic abilities of a garbage collector to do that. I personally heavily prefer the second style
I thought this was the Larry Tesler slogan with respect to user interfaces, and the “no modes” license plate:
https://itsthedatastupid.wordpress.com/2010/05/29/no-modes/
The distributed systems version seems a bit different, but related
“No modes” argues against the vi user interface, but I like vi :) I think that came up recently – vi is modal but still good
I had the same reaction when I read The Humane Interface (which provides a great explanation of why modes are bad). I came to the conclusion that modes are less bad, and possibly good, when they align with a cognitive switch. For me, writing and editing are different tasks and I want to treat them as different, in the same way that my writing improved when I started using tools that made writing and typesetting into distinct tasks.
I thought this article was interesting as another angle on the trouble a system can get into when a cache is empty. One of the greatest pieces of writing in this area is by Colm MacCárthaigh on avoiding modality by designing a system to do constant work. I’m slightly surprised it hasn’t been shared here before
I very much agree with the point about caches
I wish there was a date on that blog post
The other word I’ve heard for that is “metastable state”, an analogy from physics:
https://lobste.rs/s/2vujcd
Seems to be Feb 2021 judging by when web.archive.org and I first saved it. https://dotat.at/:/9P7C2.html
That explanation is really interesting because I didn’t realize (or maybe just didn’t appreciate) that the application is part of the cause. The database+cache+application together has two stable states.
The database should help by letting some requests fail so that some can succeed with low latency. But the application could do that too: reject some http requests.
Vi modes are very different from “ok / failure” kinds of modes. In Vi they’re just different surface areas for interacting with the same thing.
In “modal software” as the article describes, failure modes are inherently unusual. Maybe some would call them “exceptional” (heh) cases.
You can bring them to the same level of normalcy by doing the same thing for the happy and sad paths, but you can also re-architect such that there’s no distinction at all. Data center on fire? Latency will go up slightly until its replaced, but still be within the bounds your QoS agreement. You get into trouble when you try to squeeze margins like this to zero. Not right away though. Sometime in the vague future when you can hope it has turned into someone else’s problem.
Cool!
Could a similar technique speed up linking, too—like an even faster ‘mold’?
Very unlikely, the data offset and size must be multiple to the filesystem block
Well, you can always pad there as well. Since this would probably be used mostly for faster debug builds, a larger binary would not be a huge problem. So I think it could work.
Interesting! For the past couple of years, I became convinced that we are missing a “thin waist” roughly in this area, and started sketching out some design (just a very rough outline at this moment): https://github.com/matklad/abont
EDIT: reading the opening paragraph of https://research.swtch.com/acme.pdf is illuminating. Indeed, what I want is acme without mouse and with syntax highlighting.
I’ve never used acme myself, but I’ve admired it from afar.
On Unix, if you’re writing code to deal with an interactive program, you can be notified when the program produces output, but you have no idea when the program is waiting for input. You can say “if nothing has been printed in half a second, it’s probably waiting for input” but that’s about as close as you get.
On Plan9, when the interactive program calls
read()on stdin, that goes via the VFS and calls your program’sread()handler. You can respond with data, you can twiddle your thumbs, you can wait for the user to type a response, whatever you like.Because Plan9 provides this intimate connection between interacting programs, a “terminal” on Plan9 is much closer to a Unix pipe than a Unix pty, being just a log of communications in each direction. As a result, the gap between “a terminal” and “an editor buffer” is much smaller, and a tool like acme becomes a lot more straightforward.
There’s tools that try to reproduce parts of the Plan9 system on Unix, like Plan 9 from User Space, 9term, and wily. Unfortunately, because Plan9 semantics aren’t quite like POSIX semantics, either things don’t work reliably, or you’re cut off from the POSIX world and can only talk to “true” Plan9 tools.
This plus modal key bindings was what my starting point was for ad. The current state of the project is also an exercise in “how far can I get using only the standard library” which is why the only dependency other than libc is bitflags (used in the 9p implementation which has now been moved out to another crate).
I’ve had a look at the design you propose in abont and there are quite a few similarities with what I’m aiming for with ad and what I really like about acme. There is a fantastic screencast from Russ Cox that I link to in the README which does a good job of showing the sorts of things that are possible with acme. My main issue with using acme as a daily driver is the heavy focus on relying on the mouse rather than allowing you to define custom key bindings. That side of ad is all working pretty well, but I suspect there’s a fair amount left to do in terms of how the text buffers themselves are managed. I also really need to port the layout logic from Penrose to work with it at some point soon(!)
Hm interesting, yeah I’d call both the Abont proposal and Acme “exterior narrow waists” [1] – a narrow waist between processes – IPC and polyglot – rather than the “interior” Emacs Lisp model
Although I don’t understand the Rust point. Isn’t the whole idea of IPC that you can use any language? Using any language makes it more open too
And I agree that say Warp appears to be building an “app” and not an extensible architecture, which seems to be a big difference between open and closed
I think the headless protocol of Oils is naturally complementary to a UI protocol like this:
https://www.oilshell.org/blog/2023/12/screencasts.html#headless-protocol-oils-web_shell
https://www.oilshell.org/blog/tags.html?tag=headless#headless
The slogan for the headless shell is that the shell UI shouldn’t be a terminal – it should have a terminal (for the subprocesses)
So you could make a shell UI in a new paradigm, but reuse the entire shell language, and all existing terminal tools. I’d say you still need a terminal in any new paradigm, unless you are OK with colors in Cargo / Clang / GCC / grep not working.
(And obviously VSCode has a terminal, I think Emacs and neovim do too. Emacs also has its own shell, eshell, but I think that’s not the right approach.)
I mentioned “addition of waists” as a powerful pattern here
https://www.oilshell.org/blog/2022/03/backlog-arch.html#refinements
I am not sure if the headless protocol is an M x N waist yet … I guess we need another shell to implement it ;) But it is an open and tiny protocol, like 200 lines. The main idea is to pass a terminal file descriptor over a Unix socket.
One issue is Windows, and I have been wondering on Zulip how you actually use the new terminal APIs on Windows. I think you can do it with native Win32, and you don’t need WSL. And I think Windows probably has some kind of FD passing between processes too?
[1] or maybe “exterior M x N waist”, because I got feedback from networking engineers about “narrow waist”. I don’t want to “stomp on” the terminology of an adjacent field
How about “precise waist”? “Friendly waist”?
This doesn’t seem like a misuse to me—isn’t IP exactly the same kind of NxM narrow waist? Instead of web, email, video streaming etc all having to implement Ethernet, Wi-Fi, 3g separately, they all sit on top of IP which handles the differences.
I don’t feel like I grok what Abont is all about. Is it essentially that you want to create an extensible programming environment (Emacs like) but want to be able to control is via external processes with an API?
Yup, that’s basically it: emacs presentation model, but with IPC instead of mutable global lisp image. I wouldn’t want abont if emacs was good enough for me. But I think there’s a bunch of smaller things which could be done better now:
This is also the most appealing aspect to me. So many editors have a broken “vim mode” where what I really want is:
And with all open buffers shared. I don’t want to wrestle fs events or polling or some tcp bridge in the middle.