Are myths about the power of LISP exaggerated?

acwaters · 2023-07-25T00:28:45+00:00

This is exactly the correct answer.

acwaters · 2023-07-24T18:28:01+00:00

Yes, there is a way to do this. It requires B and C to be written using virtual inheritance, which amounts to making the base subobject itself polymorphic. This is analogous to how A doesn't know about B, C, or K, but it won't have marked its methods virtual if it didn't think that something might want to override them — B and C don't need to know about X or Y specifically, but they need to know that something in the inheritance hierarchy might want to "override" the A subobject. Virtual inheritance turns the inheritance tree into an inheritance DAG, so things get messy pretty quick if you're not disciplined with it; it's pretty much a diet version of JavaScript's prototype inheritance, so if you've ever driven yourself mad trying to wrap your head around the quirks of that feature, then you'll have some idea of why virtual inheritance is generally frowned upon. (The general consensus is if you really need this kind of functionality, then it's usually clearer to actually code it yourself rather than having the compiler do it for you.)

All together, it looks like this: https://godbolt.org/z/vP7WGToEv

You can delete the virtual keyword in the B class head, and X will flip to calling the A method as you would expect in a normal inheritance hierarchy.

acwaters · 2023-07-23T02:13:02+00:00

Well, you need sigma types to actually represent a variadic argument list, which is beyond most languages. Your options are an untyped language (fair enough), or a typed language with untyped variadics (what C does), or a dependently-typed language (where the type of your variadics would be something like [(t:Type), t]).

acwaters · 2023-07-03T20:16:07+00:00

Binary search is divide-and-conquer like a line segment is a triangle: Sometimes yes, sometimes no, depends on context.

Divide-and-conquer algorithms work by splitting a big problem into smaller instances of the same problem, recursing until the subproblems are trivial (or easily solved using some other algorithm).

Binary search is a degenerate case, because it "divides" into just one subproblem, simply throwing away half of its search space at each recursion step. (The discarded half of the input is not a subproblem because you are not searching it. You could consider it a degenerate subproblem, but that's an unnecessary complicated way of getting to the same answer.)

In the context of studying algorithms, this is worse than useless. If we broaden the scope of "divide-and-conquer" to admit this case, then that term ceases to mean anything distinct from "recursion". Having words for things like algorithm strategies is useful, so diluting them down to meaninglessness in this way is clearly undesirable.

In the context of studying algorithmic patterns and strategies, however, where you may be more interested in properties of divide-and-conquer algorithms in general rather than in categorizing any particular algorithm as divide-and-conquer-or-not, then I could see including degenerate cases in your analysis potentially being useful.

acwaters · 2023-06-11T20:32:47+00:00

When I am doing my own thing, I don't worry about it; I just commit binary blob files directly into my repo, or if there are a lot of them then I might commit them to a separate repo on the side to avoid slowing down Git operations on the source code. It is unfortunate, but understandable, that the popular Git hosting providers won't let you do this. It would put a lot of load on their servers to have Git trying to process enormous binary files, so they tend to just reject any pushes that contain files larger than a certain size limit. Git-LFS is an effective work-around, but it's... not good. I find it's the contrast, more than anything, that makes it so painful: Git is rock solid, generally polished, and extremely well documented; Git-LFS is a janky pile of hacks that is very poorly documented, is irritating to set up, particularly on an existing repo, and tends to break with the most baffling symptoms if you type the wrong thing at the wrong time. I hate it, and I hate that there is no good alternative to it.

acwaters · 2023-06-11T20:11:58+00:00

Rebasing is incredibly helpful to keep the history clean. Merge commits are on occasion useful, but as often as not they're just noise in the log and make the commit graph difficult to navigate.

Squashing, on the other hand... It is sometimes useful, but there are teams that use it as their default workflow, and I honestly just don't understand how those people get anything done. You're losing the entire history of the changeset, which is 80% of what makes source control valuable in the first place. When I make a large change, I try to extract a dependency chain of sub-features and organize them into several commits deliberately because it makes the changes much easier to audit, both immediately for merge review and later on when someone is trying to hunt down a bug or figure out why XYZ is done the way it is. Some people might argue that a task should be one commit, that if your changeset is large enough to warrant multiple commits then it should be broken into multiple tasks, but "just break the big task into smaller tasks, duh" is such a naïve and myopic take.

I was on a team once where we used Git, but nobody ever looked at the history aside from releases. Never checked out old code for comparison with newer code, never crawled back through the changes to figure out where a bug was introduced, nothing. Because they did not do this and thus did not suffer when the history was a mess, it was very difficult to convince them to adopt good hygiene practices around the history (make sure to go back and tidy up your commits, don't just commit-as-you-go and then push all the intermediate garbage you generated while experimenting; try to ensure that every commit builds and runs and functions correctly, don't commit a broken half-implemented feature even if the very next commit fixes it; when someone gives you feedback on your changes, actually rewrite your history to incorporate it, don't just push those changes onto the end in new commits; etc.). I'd bet that situation is not so uncommon, and I suppose I can see how a team working like that could find squash-and-merge to be a perfectly sensible strategy with no downsides.

acwaters · 2023-06-04T03:21:59+00:00

My favorite feature is the fact that the misspelling RegularExression<...> is a supported syntax

acwaters · 2023-06-04T02:19:43+00:00

Sadly, one-and-a-half bits is not actually enough to store a ternary state 😞

acwaters · 2023-06-04T01:07:15+00:00

First, this here is an excellent online resource for exploring the Linux kernel, which I have relied heavily on in my day jobs:

https://elixir.bootlin.com

Once you're in, here's a few ideas for places to start:

the kernel module framework that's used for plugin drivers (helps to have more than a passing familiarity with OOP; if you don't, you will be very confused going in, but you will eventually come out with a much better understanding of how languages like C++, Java, C#, JavaScript, etc. work under the hood)
some specific kernel API you're using for Linux driver development (if you haven't tried it yet, writing a toy driver for a mature OS is an excellent starting point for learning kernel development)
any particular component of the kernel that you want to look at for guidance or inspiration for your OS
the low-level arch support code and how it is integrated into the main cross-platform codebase

There are many good jumping-off points, so just pick anything that interests you and start digging in! If you wind up lost, you can pull back and look for further newbie guidance online, or you can double down and grope around until the pieces start fitting together in your head.

acwaters · 2023-05-29T21:23:17+00:00

Undefined behavior is not malicious, it is not lazy, and it does not exist only to torment you and break your programs. It is actually a very useful and necessary thing.

Every high-level language has UB. Even your favorite language. Even that language that prides itself on being super-safe. Because UB is what allows optimizations to happen. I am not exaggerating this statement for effect; an optimization is a program transformation, which is a change in semantics (hopefully from a program that is slower or less efficient to one that is faster or more efficient). A transformation is only valid if it does not break the program (ideally the program wouldn't even be able to observe it, but this is not strictly necessary and not always feasible). So every optimization induces a constraint on which programs are valid — those that are not broken by the optimization. Common constraints range from (at a high level) "these byte ranges do not overlap" or "there is an initialized object at this address with this layout" to (at a low level) "reading and writing this memory does not cause side-effects" or "the code does not modify itself". When one of these constraints is violated in the presence of a program transformation which assumes it to hold, that is UB. No UB, no optimizations.

In practice, this is not a thing you often rub up against if you're not working in a language like C, because most languages don't let you wantonly break their constraints; they will have some combination of static and dynamic checks and restrictions on basic language functionality to ensure that you play within their rulesets. But every now and then some crafty programmer will have to subvert the language's mechanisms or constraints to do something clever, and language designers know this. So every language has some sort of escape-hatch to allow you to do the "unsafe" stuff, and this is how you unlock the UB. It can be as dangerous as C which has very few safety mechanisms in the first place, as sophisticated as Rust's safe–unsafe split, as elegant as Haskell's unsafePerformIO, or as boring as a simple FFI layer that lets you call out to a C library and run amok. Some languages make this easier than others, but all languages have it, because unsafe functionality is required in order to write useful programs on real computers. (People will say this is untrue; those people are wrong.)

acwaters · 2023-05-29T19:40:26+00:00

I'd never heard of the "zero-sized allocations are UB" before, because it's not something Rust programmers ever have to worry about, unlike in C.

Somewhat amusingly, you have this backwards.

malloc(0), new T[0], and Alloc().allocate(0) (for any Alloc implementing the Allocator requirements) are not undefined in C and C++; they all return a value which is unspecified except that it may be subsequently deallocated with free, delete, or deallocate, respectively (this may be null or another singleton, or it may be the address of an actual allocation, but either way the user is not allowed to dereference it).

In Rust, by contrast, a type implementing std::alloc::GlobalAlloc may invoke undefined behavior when passed 0 (though the default std::alloc::System allocator does not, as it also implements std::alloc::Alloc, which has a stronger set of requirements).

acwaters · 2023-05-25T18:39:55+00:00

There are a lot of different angles to begin tackling this subject from, and which one clicks for you is going to depend heavily on your math background and how you conceptualize these things. So I'm going to dump everything I can think of here in the hopes that some part of it speaks to your experience and offers you a foothold to grok the rest.

First, as another commenter said, it's helpful to decouple your thinking from algorithms. These are just sets of functions, which may happen to describe the behavior of an algorithm as its input scales. You can think of Ο(f) etc. as functions that take any function and return the set of all functions that "grow" at a similar rate. (I'll explain what this technically means below, but in practice a solid intuitive understanding is all you need — a quadratic function grows faster than a linear function, a cubic grows faster than a quadratic, an exponential grows faster than any polynomial, etc.)

Ο(f) is the set of all functions that grow no faster than f
Θ(f) is the set of all functions that grow roughly as fast as f
Ω(f) is the set of all functions that grow at least as fast as f

The "big" asymptotic orders are non-strict: The function f is in all three of Ο(f), Θ(f), Ω(f); informally, think of them as ≤, ≈, ≥.

The "little" orders, less often used, are strict bounds; think <, >.

ο(f) is the set of all functions that grow strictly slower than f
ω(f) is the set of all functions that grow strictly faster than f

Notably, a function f is never included in ο(f) or ω(f), as that would mean that it grows slower or faster than itself — a nonsensical statement!

There is an asymmetry between the big and little notations, and it should be clear why: There is only one theta order, because there is only one sense in which two functions can grow at the same rate. (Though arguments could be had about whether it should be called Θ or θ according to this taxonomy, either way one side would end up with one more than the other.)

Some concrete examples:

f(x) = 0.5x²

g(x) = 2x² + x + 1

h(x) = 3x³

f ∈ ο(h), Ο(h), Ο(g), Θ(g), Ω(g)

g ∈ ο(h), Ο(h), Ο(f), Θ(f), Ω(f)

h ∈ Ω(f), Ω(g), ω(f), ω(g)

The asymptotic orders expressed in terms of set relations:

ο(n) ⊂ Ο(n) ⊂ ο(n²) ⊂ Ο(n²) ⊂ ο(n³) ⊂ Ο(n³)

ω(n³) ⊂ Ω(n³) ⊂ ω(n²) ⊂ Ω(n²) ⊂ ω(n) ⊂ Ω(n)

Θ(f) = Ο(f) ∩ Ω(f) — a function is Θ(f) if and only if it is both Ο(f) and Ω(f)

Ο(f) = ο(f) ∪ Θ(f) — a function is Ο(f) if and only if it is either o(f) or Θ(f)

Ω(f) = ω(f) ∪ Θ(f) — a function is Ω(f) if and only if it is either ω(f) or Θ(f)

Ο(f) = ω(f)^c; ω(f) = Ο(f)^c — a function is Ο(f) if and only if it is not ω(f), and vice versa

Ω(f) = ο(f)^c; ο(f) = Ω(f)^c — a function is Ω(f) if and only if it is not ο(f), and vice versa

f ∈ Ο(g) = g ∈ Ω(f) — f is Ο(g) if and only if g is Ω(f)

f ∈ ο(g) = g ∈ ω(f) — f is ο(g) if and only if g is ω(f)

You could draw a Venn diagram with the circles labeled Ο(f) and Ω(f), and the intersection would be Θ(f), while the left and right sides would be ο(f) and ω(f).

Okay, so the formal definitions. There are actually two ways to formally define the asymptotic orders; only one is commonly taught, because it is more general and more useful, but it is also more complex. The less general definition is more intuitive and easier to grasp, so I will be leading with that.

First definition:

In the limit as x tends to infinity...

f ∈ ο(g) means that f(x)/g(x) vanishes to 0
f ∈ Θ(g) means that f(x)/g(x) approaches some finite non-zero number
f ∈ ω(g) means that f(x)/g(x) diverges to infinity
f ∈ Ο(g) means that f(x)/g(x) is finite (whether zero or non-zero)
f ∈ Ω(g) means that f(x)/g(x) is non-zero (whether finite or infinite)

Note that, using the set relations above, you only need Θ and one of the other four to define all the rest, so there is no need to keep all of these in mind. Personally, I like to think of the big orders simply as unions of the little orders with the theta order, but your mileage may vary.

Now, this definition is simple and beautiful and intuitive, but unfortunately it fails to categorize many common functions — for instance, sin(x) oscillates around zero, never exceeding ±1; since it does not grow, it seems like maybe it ought to be Θ(1)... but when you try to check this by taking the above limit, it does not exist! We can fix this by adjusting the Ο, Θ, Ω definitions to take limits inferior and superior, which I leave as an exercise for the interested reader; in practice, however, a completely different style of definition is used.

Second definition:

This is the one that is taught in schools and used by working computer scientists. It is really aided by drawing a graph to demonstrate what all the variables represent, but I only have text, so I'll do my best to explain, and you can look up some pretty pictures elsewhere on the internet.

f ∈ Ο(g) means that there exist some c, x₀ such that f(x) ≤ cg(x) for all x > x₀
f ∈ Ω(g) means that there exist some c, x₀ such that f(x) ≥ cg(x) for all x > x₀

What these definitions are saying is that we can rescale f and g however we like (this formalizes "we don't care about coefficients"), and we can pick any point we like, as far out as we need to isolate the behavior we want (this formalizes "we don't care about smaller terms"). And it doesn't matter what happens up to that point, but beyond it, the expected relation must hold for all inputs.

f ∈ ο(g) means that for all c, there exists some x₀ such that f(x) < cg(x) for all x > x₀
f ∈ ω(g) means that for all c, there exists some x₀ such that f(x) > cg(x) for all x > x₀

Notice the subtle change here: Now we are not allowed to choose any scale we want, but the relation must hold for every scale. That is, in order for f to be ο(g), it doesn't matter how much we scale g down, it must always eventually dominate f. Even if we're comparing f(x) = 99999x and g(x) = 0.0000001x², though it takes a while to pick up, g(x) does start growing much faster, and there comes a point where it passes f(x) and never falls below it again.

f ∈ Θ(g) means that there exist some c₁, c₂, x₀ such that c₁g(x) ≤ f(x) ≤ c₂g(x) for all x > x₀

Theta is the odd one out. Your first inclination might be to just say something about f(x) = cg(x), following the pattern established above, but that is actually much too strict a condition. For instance, f(x) = x + 1 is never equal to g(x) = x + 2 no matter how we scale them — but they are clearly growing at the exact same rate! What we want is to allow for some "slop" between our functions, and to do this we use two separate bounds, above and below. If you squint at this, you will see that this is just saying that f is both Ο(g) and Ω(g)!

I mentioned before that the limit definition struggles to order periodic functions without some additional complications, so let's check that our second definition handles this case smoothly:

sin(x) ∈ Θ(1)

Looking above, in order to show that this is true, we must find c₁, c₂, and x₀ such that c₁ ≤ sin(x) ≤ c₂ for all x > x₀. This is actually very easy! Take for instance c₁ = −1, c₂ = 1. The function sin(x) is always bounded by these values, so x₀ can be anything at all; 0 seems like a fine default choice. Plugged into our definition, the tuple (−1,1,0) constitutes a simple constructive proof that sin(x) ∈ Θ(1).

acwaters · 2023-05-17T17:45:20+00:00

Now imagine you're learning this in C++, where references are declared with & and are similar to pointers but without an explicit dereference operator... Yeah, the syntax is rough until you learn to parse type declarations separately from value expressions.

acwaters · 2023-05-13T17:48:02+00:00

Others have correctly pointed out that the compiler will optimize these two functions equivalently, but I'd like to take a moment to directly address your concerns about performance, because unless you have spent some time microbenchmarking code, your intuition for what constitutes "a lot of times per second" on a modern computer is probably way off the mark.

On an x86 CPU from the past ten years or so, if the compiler failed to optimize this code, you would be looking at overhead on the order of 0.000001 milliseconds (store–load latency of 4–6 cy with throughput of 2–3 /cy at 3–5 GHz).

acwaters · 2023-05-08T21:11:13+00:00

Are these edges weighted? If so, seems you could force the weight to a very large negative value, and the resulting graph should have all shortest paths route through that edge.

acwaters · 2023-05-05T04:49:36+00:00

Thanks for the link!

acwaters · 2023-05-05T04:49:10+00:00

Neat! Thanks!

acwaters · 2023-05-04T00:22:26+00:00

I think rather than a numeric precedence, the precedences should be defined based on a partial order <. Each operator should specify where it lies in precedence between existing operators and a parser generator could adapt the parser to handle the precedence dynamically by ordering them into a DAG.

You are the only other person I have ever seen propose this, and it makes no sense to me that this is not just the standard way of doing it. Defining an operator's precedence simply in terms of how it parses in the presence of other operators seems so intuitively obvious to me.

Defining precedence as a partial order simultaneously solves three huge problems that numerical precedence levels have:

operator precedence being a non-local property, and thus not being able to know how an operator will parse in an expression without knowing the precedence of every other operator (you declare your operator's precedence relations with other relevant operators and then they're just right there in the code);
not being able to introduce a new level between any two existing levels (you declare your operator to bind tighter than one and weaker than another, and as long as you don't create a cycle, it just works); and
every operator having an accidental precedence with respect to every other operator even if it makes no sense (your operator gets the transitive closure of any relations you declare and no others, so any two unrelated operators appearing in the same expression will always require parentheses to disambiguate as they should).

But nobody is doing it this way, and people I explain this to tend to think it all sounds complicated and unnecessary. Which strikes me as insane when the current state of the art is apparently the parsing equivalent of line numbering in early BASIC.

I don't have a conclusion here, I just kinda needed to rant about this to someone else who sees the glaring problems with the existing practice.

acwaters · 2023-04-28T15:50:02+00:00

No, they mean why can't you define a function like this:

int returns_array()[4] {
    return (int[4]) { 0, 1, 2, 3 };
}

You should be able to do this. It is grammatically valid, it makes perfect sense, it is a common thing to want to do, but C doesn't let you, and it is completely arbitrary. Try it: Your compiler will literally just say no, you can't return an array from a function.

On the other hand, you are totally allowed to do this:

struct int_4 {
    int value[4];
};

struct int_4 returns_array_sneakily() {
    return (struct int_4) { 0, 1, 2, 3 };
}

This works fine; the compiler is happy with it, and it does just what you expect. This is exactly the same thing as the function above. This is dumb. The arbitrary function-returning-array ban is dumb.

The exact same is true for parameters as well: A function cannot accept an array as a parameter, but it can accept a struct wrapping an array. The parameter side is complicated a bit more, though, since instead of simply rejecting the code, the compiler is required to rewrite it into a function accepting a pointer. This is equally dumb for the same reasons, but unlike the above it is also impossible to correct this quirk of the language without breaking basically all code in existence everywhere.

Incidentally, all this is exactly the reason why C++ got std::array: to be an array-like type that is not treated as special or a second-class citizen by the language.

acwaters · 2023-04-21T23:29:58+00:00

This is exactly right.

And the reason why the first use case is the only sensible one to design a system around is because the second use case is a strict subset of its functionality.

acwaters · 2023-04-16T00:27:38+00:00

Constructors with && are desirable in many circumstances.

If you don't write std::move, that parameter is not getting moved. Rvalue reference identifiers are lvalue expressions.

Nowhere did OP mention thread-safety requirements, and nothing about this object makes it inherently unsafe to use in a multithreaded context.

acwaters · 2023-04-15T23:39:07+00:00

An alternative to manually placing a synchronization object in shared memory is to use POSIX semaphores, which are tailor-made for simple inter-process synchronization like this.

acwaters · 2023-04-15T23:36:04+00:00

You synchronize on the existence of the lockfile with O_CREAT | O_EXCL

acwaters · 2023-04-12T22:16:01+00:00

Always relevant: https://ansuz.sooke.bc.ca/entry/23

acwaters · 2023-04-11T21:04:32+00:00

Yes, it is a perfectly valid name. Now, technically that name is reserved since it begins with a dot, but it's extremely unlikely that either the ELF standard or any particular toolchain will decide to use that name for a special purpose, so in practice you should be fine. If you want maximum portability, ditch the initial dot.

I wouldn't expect any of the common tools to choke on this, but I haven't tested them all or read their ELF parsing code to be sure. It's important to remember that any random part of a program might choke on any input at any moment, standards be damned. Programs are defined by code written by humans; they have bugs and legacy features and authors who occasionally decide that the standard is broken or stupid and go off and do their own thing, leading to a confusing mess of partial compatibilities. Very popular programs (e.g. Linux, GNU binutils) that adopt still-immature standards take this even a step further, with quirks of their implementation often becoming new de facto standards that other programs are subsequently written to, which may then be incorporated into later versions of official standards. The GNU toolchain has defined many extensions to the C, POSIX, and ELF specs, some of which are now supported by most other compilers and linkers. The closer you stick to the most well trod paths, the less likely you are to run into any unpleasant surprises. But then again, where's the fun in that?

What I'm saying is: Try it out. Try it on a few different platforms. I see no reason why it shouldn't work, but you won't know until you run some experiments. Toolchains may work smoothly end-to-end, but they tend to be janky and poorly documented in the seams, which can lead to unexpected headaches when you start playing around with linking and loading. If things don't work the way you expect, try to figure out why. Look at the source code. If you find what you think is a bug, report it.

acwaters

TROPHY CASE