An interesting aspect of this, especially their blog post (https://malus.sh/blog.html ), is that it acknowledges a strain in our legal system I've been observing for decades, but don't think the legal system or people in general have dealt with, which is that generally costs matter.
A favorite example of mine is speed limits. There is a difference between "putting up a sign that says 55 mph and walking away", "putting up a sign that says 55 mph and occasionally enforcing it with expensive humans when they get around to it", and "putting up a sign that says 55 mph and rigidly enforcing it to the exact mph through a robot". Nominally, the law is "don't go faster than 55 mph". Realistically, those are three completely different policies in every way that matters.
We are all making a continual and ongoing grave error thinking that taking what were previously de jure policies that were de facto quite different in the real world, and thoughtlessly "upgrading" the de jure policies directly into de facto policies without realizing that that is in fact a huge change in policy. One that nobody voted for, one that no regulator even really thought about, one that we are just thoughtlessly putting into place because "well, the law is, 55 mph" without realizing that, no, in fact that never was the law before. That's what the law said, not what it was. In the past those could never really be the same thing. Now, more and more, they can.
This is a big change!
Cost of enforcement matters. The exact same nominal law that is very costly to enforce has completely different costs and benefits then that same law becoming all but free to rigidly enforce.
And without very many people consciously realizing it, we have centuries of laws that were written with the subconscious realization that enforcement is difficult and expensive, and that the discretion of that enforcement is part of the power of the government. Blindly translating those centuries of laws into rigid, free enforcement is a terrible idea for everyone.
Yet we still have almost no recognition that that is an issue. This could, perhaps surprisingly, be one of the first places we directly grapple with this in a legal case someday soon, that the legality of something may be at least partially influenced by the expense of the operation.
you're more polite than me, but that's essentially the same response as what i have to people citing chatGPT. i just say "ChatGPT told me that's wrong".
if somebody thinks that unverified LLM output is relevant to a conversation, i don't want to have to defend why it shouldn't be part of the conversion, i want to put the responsibility for justifying it back onto them.
I had the incredible good fortune to cross paths with iq at Pixar; I was an intern while he was developing the Wondermoss procedural vegetation system for Brave. A bunch of us interns were already fans of his work from the demoscene world and upon learning this, he was kind enough to put together a special lecture for the interns on procedural graphics and the work he was doing for Wondermoss. That was one of the best and most mind-blowing lectures I've ever seen- for every concept he would discuss in the lecture, he would live-code a demo in front of us (this was before ShaderToy was a thing, so live-coding was something nobody had ever really seen before), and halfway through the lecture he revealed that the text editor he was using was built on top of his realtime live editing graphics system and therefore could be live-coded as well.
One of the things he showed us was an early version of what eventually became the BeautyPi tech demo [0]; keep in mind that this still looks incredible today and iq was demoing this for us interns in realtime 14 years ago.
Wondermoss was a spectacular piece of tech. Every single forest scene and every single piece of vegetation in Brave is made using Wondermoss, and it was all procedural- when you'd open up a shot from Brave in Menv30, you'd see just the characters and groundplane and very little else, and then you'd fire up the renderer and a huge vast lush forest would appear at rendertime. The even cooler thing was that since Brave was still using REYES RenderMan, iq took advantage of the REYES algorithm's streaming behavior to make Wondermoss not only generate but also discard vegetation on-the-fly, meaning that Wondermoss used vanishingly little memory. If I remember correctly, Wondermoss only added like a few dozen MB of memory usage at most to each render, which was insane since it was responsible for like 95% of the visual complexity of each frame. One fun quirk of Wondermoss was that the default random seed was iq's phone number, and that remained for quite a number of years, meaning his phone number is forever immortalized in pretty much all of Pixar's films from the 2010s.
iq is one of the smartest and most inspiring people I've ever met.
This reminded me of this old quote from Hal Abelson:
"Underlying our approach to this subject is our conviction that "computer science" is not a science and that its significance has little to do with computers. The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology—the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects. Mathematics provides a framework for dealing precisely with notions of "what is". Computation provides a framework for dealing precisely with notions of "how to"."
- Ignore the SSA conversion algorithms that don’t use dominance frontiers. Also ignore the dominator tree generation algorithms that aren’t Langauer-Trajan. Reason: you’ll want to have a dominator tree (ie immediate dominators) anyway for a bunch of SSA optimizations. So, you’ll want Langauer-Tarjan. And if you have that, then using dominance frontiers to generate SSA is just easier.
- CPS isn’t really anything like SSA. Don’t believe that hype. Any claim in PL of two languages or forms being equivalent is not falsifiable because any two Turing complete languages are going to have some transformation between them, so really these papers are just saying “hey look I invented a translation that we all knew was going to be possible and I like my translation for aesthetic reasons”. Working with CPS is nothing like working with SSA.
- The best way I know of representing Phi in your SSA IR is a Pizlo special. I haven’t written it up except by implementing it (JavaScriptCore uses Pizlo SSA). Here’s the idea. Phi takes no arguments (no block arguments and no value arguments). Each Phi has a shadow variable (in addition to the implicit SSA variable it assigns to). Phi just loads the value out of its shadow variable and assigns it to its implicit variable. Then I have a second instruction called Upsilon that takes two args: an input variable and a Phi. It loads the input variable’s implicit value (just as any SSA use would) and stores it to the Phi’s shadow variable. The result of using this IR is that you have zero coupling between your CFG and the SSA graph. It makes CFG transforms much much easier to write. It also means much less special casing of Phi, in practice.
One challenge was that while I started working on the Xbox 360 about three years before it would ship, we knew that the custom CPU would not be available until early 2005 (first chips arrived in early February). And there was only supposed to be one hardware spin before final release.
So I had no real hardware to test any of the software I was writing, and no other chips (like the Apple G5 we used as alpha kits) had the custom security hardware or boot sequence like the custom chip would have. But I still needed to provide the first stage boot loader which is stored in ROM inside the CPU weeks before first manufacture.
I ended up writing a simulator of the CPU (instruction level), to make progress on writing the boot code. Obviously my boot code and hypervisor would run perfectly on my simulator since I wrote both!
But IBM had also had a hardware accelerated cycle-accurate simulator that I got to use. I was required to boot the entire Xbox 360 kernel in their simulator before I could release the boot ROM. What takes a few seconds on hardware to boot took over 3 hours in simulation. The POST codes would be displayed every so often to let me know that progress was still being made.
The first CPU arrived on a Friday, by Saturday the electrical engineers flew to Austin to help get the chip on the motherboard and make sure FSB and other busses were all working. I arrived on Monday evening with a laptop containing the source code to the kernel, on Tuesday I compiled and flashed various versions, working through the typical bring-up issues. By Wednesday afternoon the kernel was running Quake, including sound output and controller input.
Three years of preparation to make my contribution to hardware bring-up as short as possible, since I would bottleneck everyone else in the development team until the CPU booted the kernel.
- In general, elliptic curves are solutions of P(x, y) = 0 where P is a polynomial of degree 3 in two variables. "Points" on the curve are solutions of this equation.
- If you intersect an elliptic curve with a straight line, you end up with a polynomial in one variable, of degree 3 (in general). Since a polynomial of degree 3 has 3 solutions (in the appropriate context), this means that if you have two points on the curve, and you draw a line through these two points, there is a third aligned with them which belongs to the curve. So we have an operation on the curve, which to every pair of points associates a third point. This can be explicitly calculated.
- It can be proven (again, by explicit calculation) that this operation is associative and commutative, and that there is a "zero" element, i.e. that this operation forms a "group".
Now we want to study these elliptic curves and their associated groups with one additional condition: that the points are rational, i.e. have coordinates that are rational numbers (a/b). For each curve with rational parameters (i.e. the coefficients of the polynomial are rational), we want to study the rational points of this curve.
For some elliptic curves, there is a finite number of points, so the associated group is a finite commutative group.
For other elliptic curves, however, there are infinitely many rational points, and mathematicians have wanted to classify their structure.
A foundational result in number theory known as the Mordell-Weil theorem states that the group of rational points on an elliptic curve over a number field (such as the rationals, ℚ) is finitely generated. In other words, although there may be infinitely many points, they can be expressed as a finite set of points (known as "generators") combined under the group operation. This structure forms what is called a "finitely generated abelian group", which can be decomposed into a direct sum of a finite subgroup (called the "torsion") and a free part of rank r, where r is called the "rank" of the elliptic curve.
This rank "r" essentially measures the "size" of the free part of the group and has deep implications in both theoretical and computational number theory. For example, if r=0, the group is finite, meaning that the set of rational points on the curve is limited to a finite collection. When r>0, there are infinitely many rational points, which can be generated by combining a finite number of points.
So the challenge is to find a curve with a large number of generators. All of these computations (for a given curve at least) are quite explicit, and can be carried out with a bignum library (the numbers tend to get quite large quickly). I used PARI/GP for my thesis.
The most important operation in QNX is MsgSend, which works like an interprocess subroutine call. It sends a byte array to another process and waits for a byte array reply and a status code. All I/O and network requests do a MsgSend. The C/C++ libraries handle that and simulate POSIX semantics. The design of the OS is optimized to make MsgSend fast.
A MsgSend is to another service process, hopefully waiting on a MsgReceive. For the case where the service process is idle, waiting on a MsgReceive, there is a fast path where the sending thread is blocked, the receiving thread is unblocked, and control is immediately transferred without a trip through the scheduler. The receiving process inherits the sender's priority and CPU quantum. When the service process does a MsgReply, control is transferred back in a similar way.
This fast path offers some big advantages. There's no scheduling delay; the control transfer happens immediately, almost like a coroutine. There's no CPU switch, so the data that's being sent is in the cache the service process will need. This minimizes the penalty for data copying; the message being copied is usually in the highest level cache.
Inheriting the sender's priority avoids priority inversions, where a high-priority process calls a lower-priority one and stalls. QNX is a real-time system, and priorities are taken very seriously. MsgSend/Receive is priority based; higher priorities preempt lower ones. This gives QNX the unusual property that file system and network access are also priority based. I've run hard real time programs while doing compiles and web browsing on the same machine. The real-time code wasn't slowed by that. (Sadly, with the latest release, QNX is discontinuing support for self-hosted development. QNX is mostly being used for auto dashboards and mobile devices now, so everybody is cross-developing. The IDE is Eclipse, by the way.)
Inheriting the sender's CPU quantum (time left before another task at the same priority gets to run) means that calling a server neither puts you at the end of the line for CPU nor puts you at the head of the line. It's just like a subroutine call for scheduling purposes.
MsgReceive returns an ID for replying to the message; that's used in the MsgReply. So one server can serve many clients. You can have multiple threads in MsgReceive/process/MsgReply loops, so you can have multiple servers running in parallel for concurrency.
This isn't that hard to implement. It's not a secret; it's in the QNX documentation. But few OSs work that way. Most OSs (Linux-domain messaging, System V messaging) have unidirectional message passing, so when the caller sends, the receiver is unblocked, and the sender continues to run. The sender then typically reads from a channel for a reply, which blocks it. This approach means several trips through the CPU scheduler and behaves badly under heavy CPU load. Most of those systems don't support the many-one or many-many case.
Somebody really should write a microkernel like this in Rust. The actual QNX kernel occupies only about 60K bytes on an IA-32 machine, plus a process called "proc" which does various privileged functions but runs as a user process. So it's not a huge job.
All drivers are user processes. There is no such thing as a kernel driver in QNX. Boot images can contain user processes to be started at boot time, which is how initial drivers get loaded. Almost everything is an optional component, including the file system. Code is ROMable, and for small embedded devices, all the code may be in ROM. On the other hand, QNX can be configured as a web server or a desktop system, although this is rarely done.
There's no paging or swapping. This is real-time, and there may not even be a disk. (Paging can be supported within a process, and that's done for gcc, but not much else.) This makes for a nicely responsive desktop system.
Multiplication, rotation, and a 2nd multiplication. These are 64-bit multiplications, which is well known to mix bits well, but CPUs don't have many 64-bit multipliers. Four rounds execute in parallel (see XXH64_update_endian), which can hide the long latency (~5 cycles) associated with a 64-bit multiply.
My own experiments show that multiplication is a great function for hashing. Multiplication however only spreads the bits in "one direction" (towards the most-significant bit), and very poorly spreads bits towards the LSB.
Rotations, as well as a 2nd multiplication, are helpful at spreading the bits around better.
----------
The 64-bit version is somewhat interesting to me, but the 32-bit version probably has more potential for optimization. 32-bit vectorized multiplication exists in AVX2, so the 32-bit version probably can be vectorized. I'd expect the 32-bit version (if vectorized) would be faster, but the 64-bit version probably mixes the bits around better.
Overall looks like a decent design. Uses ILP with 4x state variables (state->v1, state->v2, etc. etc. to allow CPUs to process these multiplications in parallel). Multiply + rotation + multiplication is good from my personal experiments, but the numbers chosen need to be carefully chosen.
Prime numbers are probably not necessary: they just need to be odd numbers to ensure invertibility (Ex: I've achieved decent mixing by multiplying with 0xAAAAAAAA5, which probably isn't a prime number). I'm curious how the prime-constants were selected. There could be some potential for "better numbers" for mixing, depending on how PRIME64_1 and PRIME64_2 were chosen.
Overall checks all of my boxes with regards to good design. Nice! I'm just curious about some details.
----------
I'll note that in my experiments, multiplication seems to "mix" better with XOR, rather than with ADD. I haven't done any tests with this hash yet, but I'm curious how changing the "+=" into "^=" would have on the statistical strength of the hash function.
The downside of v8 isolates is: you have to reinvent a whole bunch of stuff to get good isolation (both security and of resources).
Here's an example. Under no circumstances should CloudFlare or anyone else be running multiple isolates in the same OS process. They need to be sandboxed in isolated processes. Chrome sandboxes them in isolated processes.
Process isolation is slightly heavier weight (though forking is wicked fast) but more secure. Processes give you the advantage of using cgroups to restrict resources, namespaces to limit network access, etc.
Once you've forked a process, though, you're not far off from just running something like Firecracker. This is both true and intense bias on my part. I work on https://fly.io, we use Firecracker. We started with v8 and decided it was wrong. So obviously I would be saying this.
Firecracker has the benefit of hardware virtualization. It's pretty dang fast. The downside is, you need to run on bare metal to take advantage of it.
My guess is that this is all going to converge. v8 isolates will someday run in isolated processes that can take advantage of hardware virtualization. They already _should_ run in isolated processes that take advantage of OS level sandboxing.
At the same time, people using Firecracker (like us!) will be able to optimize away cold starts, keep memory usage small, etc.
The natural end state is to run your v8 isolates or wasm runtimes in a lightweight VM.
The first approach (the 'It’s "obviously" the only way to go' one) is called an adjacency list.
The second (the 'vastly simpler method') i don't recall seeing before. It has some fairly obvious deficiencies, but it is clearly enough in some cases.
The third ('namespacing') is called a materialized path.
The road to hell is paved with products that pursued simplicity but ultimately couldn't afford it.
* Just Doesn't Work
* Your simplicity becomes my complexity (fussy compatibility, batching creates latency, etc)
* "One-button" interfaces where you have to learn a morse-code dialect and timing to access the necessary features
* Bonus points: the software is laggy and the one button is mechanically unreliable, compounding the difficulty of getting the timing correct
* Useless error messages that make simple problems complex
* Similar: Necessary complexity (e.g. radio reception, authentication, updates) hidden behind a featureless spinning wheel for maximum time wasting when you can't tell what the holdup is
Parenting young children taught me everything I know about bribery, threats and diversions. Negotiations get real fast when the kids don’t have the judgment to stay safe.
A fun and fairly simple project, with a surprisingly high ratio of usefullness to effort, is to write an interpreter for a concatenative language. Concatenative languages, like FORTH, can do a lot with very limited resources, making them good candidates for embedded systems.
If you want to play around with making your own concatenative language, it is actually surprisingly simple. Here is an overview of a step-by-step approach that can take you from a simple calculator to a full language with some optimization that would actually be quite reasonable to use in an embedded system.
So let's start with the calculator. We are going to have a data stack, and all operations will operate on the stack. We make a "dictionary" whose entries are "words" (basically names of functions). For each word in the dictionary, the dictionary contains a pointer to the function implementing that word.
We'll need six functions for the calculator: add, sub, mul, div, clr, and print. The words for these will be "+", "-", "x", "/", "clr", and "print". So our dictionary looks like this in C:
We need a main loop, which will be something like this (pseudocode):
while true
token = NextToken()
if token is in dictionary
call function from that dict entry
else if token is a number
push that number onto the data stack
Write NextToken, making it read from your terminal and parse into whitespace separated strings, implement add, sub, mul, div, clr, and print, with print printing the top item on the data stack on your terminal, and you've got yourself an RPN calculator. Type "2 3 + 4 5 + x print" and you'll get 45.
OK, that's fine, but we want something we can program. To get to that, we first extend the dictionary a bit. We add a flag to each entry allowing us to mark the entry as either a C code entry or an interpreted entry, and we add a pointer to an array of integers, and we add a count telling the length of that array of integers. When an entry is marked as C code, it means that the function implementing it is written in C, and the "func" field in the dictionary points to the implementing function. When an entry is marked as interpreted, it means that the pointer to an array of integers points to a list of dictionary offsets, and the function is implemented by invoking the functions of the referenced dictionary entries, in order.
A dictionary entry now looks something like this:
struct DictEntry {
char * word;
bool c_flag;
void (*func)(void);
int * def;
int deflen;
}
Firefox developer here. There are a few ways to diagnose this, depending on your setup. If everything is frozen on Linux, it's probably the parent process that is having an issue. The "parent process" is the process that oversees all the tabs, it's the top process in a Firefox process tree, the one that has lots of children.
If our crash reporter is enabled, you can also just kill the parent process with `SIGABRT`, this will produce an entry in `about:crashes` that you can look up on restart, and submit. This will then give a link to our crash reporting front-end.
If you have `gdb` and `debuginfod` on your distro, and you're using your distro's Firefox, attach `gdb` to the parent process of Firefox, let it download symbols, and do `thread all apply bt`, this will dump the stacks of all the threads of your parent process.
If you're using one of our Firefox builds, you can use https://firefox-source-docs.mozilla.org/toolkit/crashreporte..., that will integrate with our own symbol servers. Depending on your distro this might or might not work on your distro's Firefox (some distros submit their symbols to our infra to help diagnosing crashes).
Once you have some info about the crash, you can open a ticket on your distro bug tracker, or https://bugzilla.mozilla.org/enter_bug.cgi?product=Core to reach us directly, attaching the stacks, Firefox version, crash report, about:support, or anything else that you think is relevant.
Oftentimes, those freezes (on Linux) are caused by a bug between Firefox and the desktop environment, or by graphics drivers, that kind of thing, and stacks allow narrowing down the issue greatly, sometimes it's just a package update or a configuration flip away!
This reminds me of one of my former ESPN co-workers - Mike Davidson[1] - who founded of one of the first community news sites (Newsvine[2]) back in 2006.
Newsvine had comments and upvotes and link submissions and posts - it was very reddit-esque except it was focused around the news. The team had to have a way to deal with spammers and trolls. They found the most effective way was to flag a user as a troll on the Newsvine backend. If the troll flag was set to true, Newsvine would add a random 10-60 second delay to every page load for the troll's account. IIRC it solved the problem pretty effectively.
I've had enough years to become wiser, become a fanatic for configuration management, and get over the embarrassment: I'm the consultant that screwed things up. Some background: the Stat department was running a variety of systems besides the Solaris workstations, and there was, within UNC-CH, a separate support organization that was cheaper and more comfortable with Microsoft products where Stat was sending their support dollars. When that organization needed Unix support, they called my employer, Network Computing Solutions, and I showed up.
There was effectively no firewall at UNC-CH at the time (something something academic freedom something something), and the Stat Solaris machines were not being regularly patched. Uninvited guests had infested them, and it appeared the most likely entry point was sendmail - at the time, it was the most notorious vulnerability on the internet. Since my preference to wipe and reload was unacceptable - too much downtime and too many billable hours - the obvious thing to do was update sendmail. The rest is history.
Lordy, I did not expect an internal refactoring PR to end up #1 on Hacker News. Let me provide some context, since a lot of people make a lot of assumptions whenever this stuff comes up!
If you're rabidly anti-TypeScript and think that us doing this vindicates your position, I'm about to disappoint you. If you're rabidly pro-TypeScript and think we're a bunch of luddite numpties, I'm about to disappoint you as well.
Firstly: we are not abandoning type safety or anything daft like that — we're just moving type declarations from .ts files to .js files with JSDoc annotations. As a user of Svelte, this won't affect your ability to use TypeScript with Svelte at all — functions exported from Svelte will still have all the same benefits of TypeScript that you're used to (typechecking, intellisense, inline documentation etc). Our commitment to TypeScript is stronger than ever (for an example of this, see https://svelte.dev/blog/zero-config-type-safety).
I _would_ say that this will result in no changes that are observable to users of the framework, but that's not quite true — it will result in smaller packages (no need to ship giant sourcemaps etc), and you'll be able to e.g. debug the framework by cmd-clicking on functions you import from `svelte` and its subpackages (instead of taking you to an unhelpful type declaration, it will take you to the actual source, which you'll be able to edit right inside `node_modules` to see changes happen). I expect this to lower the bar to contributing to the framework quite substantially, since you'll no longer need to a) figure out how to link the repo, b) run our build process in watch mode, and c) understand the mapping between source and dist code in order to see changes.
So this will ultimately benefit our users and contributors. But it will also benefit _us_, since we're often testing changes to the source code against sandbox projects, and this workflow is drastically nicer than dealing with build steps. We also eliminate an entire class of annoying papercuts that will be familiar to anyone who has worked with the uneven landscape of TypeScript tooling. The downside is that writing types in JSDoc isn't quite as nice as writing in TypeScript. It's a relatively small price to pay (though opinions on this do differ among the team - this is a regular source of lively debate).
We're doing this for practical reasons, not ideological ones — we've been building SvelteKit (as opposed to Svelte) this way for a long time and it's been miraculous for productivity.
Ask them for a landline phone. They'll either have to run new copper or choose to install fiber. Once they run copper then get a DSL company to run through that. Generally they won't want to run copper and don't want competition so they'll go ahead and run fiber. In either case I believe the law they're constrained by is local ordinances giving them a region based monopoly for traditional landline access in exchange for ensuring everyone has a phone. If you force the issue they'll run SOMETHING to your door. And through that something you'll have more options.
I don't quite know how to put it, what follows is a rough draft of an idea, maybe someone can help me to reword it, or perhaps it's trash.
Since its inception, computer science has had two "camps": those who believe CS is engineering, and those who believe CS is mathematics. The reason why we are seeing all of this fuss around LLMs is that they are a new front of this feud. This "extends" the usual debate on emerging technologies between Thymoetes and Laocoon.
Something that works 99 times out of 100 is 99% correct from the first perspective and 100% wrong from the second.
LLMs are therefore a step forward if you take the first view, a step back if you take the second.
If you accept this interpretation, an interesting consequence of it is that your outlook on LLMs is entirely dependent on what amounts to your aesthetic judgement.
And it's very hard not to have rather strong aesthetic judgements on what we do 40 hours a week.
The reason that WebAssembly JIT code memory is still RMW (for now) is actually really unfortunate. As you might know, V8's JIT code memory for JS is only writable when the application is quiesced (i.e. JS is not running) and the JIT is either finishing a function or the garbage collector is moving JITted code. It's read-execute otherwise. It's never both writable and executable at the same time. We generally refer to this as WX protection (i.e. writeable/executable exclusive).
In the case of WebAssembly, it's asm.js that's the real culprit here. Internally in V8, asm.js code is translated to WebAssembly by a very quick custom-built parser that validates asm.js's type system while parsing and emits WebAssembly bytecode along the way. The WebAssembly bytecode is then fed to the WebAssembly engine for compilation.
Well...not so fast. In order to meet our performance goals for fast asm.js validation and startup, the WebAssembly engine does not do up-front compilation of Wasm code coming from asm.js. Instead, it does on-demand compilation of asm.js code, compiling the Wasm bytecode corresponding to each asm.js function upon first execution. We call this "lazy compilation".
We originally shipped lazy compilation cooperating with the WX mechanism executable for JS code. That is, upon every (lazy) compilation of asm.js code, we'd flip the permission bits on the code space in order to write in the little bit of machine code generated for each function. Problem is, that permission flip is expensive--like really expensive. So expensive that we had to unship WX protection because it made asm.js code unusably slow.
We're working on fixing this, as we are keenly aware of the risk exposure here.
The fundamental bug here is really slick. The static analyzer in the JIT incorrectly believes
Math.expm1(x)
can't return -0. But if x is -0, it can. That, in turn, means it believes
Object.is(Math.expm(x), -0)
must always be false. But if x is -0, it's true, not false. That, in turn, means that the JIT believes
array[Object.is(Math.expm(x), -0) * INDEX]
must be array[0], no matter what INDEX is. But if x is -0, it'll be array[INDEX]. That's a big problem, because the optimizer, guided by the static analyzer, removes the bounds check if the bounds check can't ever fail.
But it's not quite that simple, because another consequence of of the static analyzer's misperception is that
Object.is(Math.expm(x), -0) * INDEX
is the constant 0, no matter what value x takes and no matter what INDEX is, and the JIT will simply constant-fold 0 in for the whole expression, so the bounds check really won't matter.
But constant folding is an optimization, not a security boundary, and easily "defeated": replace the -0 constant in that expression with an object reference:
obj = { o: -0 }
Object.is(Math.expm(x), obj.o)
You can read that code and see that it's the constant -0, but the static analyzer needs to do escape analysis to make sure the object reference really does just evaluate to a constant, and escape analysis happens after the typing analysis, so the constant folding doesn't happen.
The end result of the bug is a sort of "black magic zero/one chimera" that, mixed into an expression, tricks the JIT into stripping bounds checks. It's an extremely cool exploit primitive. It's doubly cool because if you don't have Andrea's writeup or a really nuanced understanding of v8 internals, you could stare at that exploit for eternity and never understand why it works.
The real solution to this problem is to properly remove the left recursion. Student's often make the mistake the author did. Let's examine our favorite grammar:
E -> E + T
| E - T
| T
T -> T * F
| T / F
| F
F -> id
| number
| ( E )
The obvious way to remove left recursion in the grammar is to "flip" the non-terminals. Like so:
E -> T + E
| T - E
| T
T -> F * T
| F / T
| F
F -> id
| number
| ( E )
This is wrong. Consider the string "28 / 7 * 2". The orginal grammar produces the following parse:
E
|
T
/|\
T * F
/|\ |
T / F 2
| |
F 7
|
28
The new grammar produces:
E
|
T
/|\
F / T
| /|\
28 F * T
| |
7 F
|
2
When computing the expression. These tree produce different answers. The first gives "8", the correct answer, the second gives "2". Basically, it is parenthesized incorrectly.
To fix this problem the solution is to insert intermediate non-terminals into the grammar:
E -> T E'
E' -> + T E'
| - T E'
| e <--- standing in for epsilon, the empty string
T -> F T'
T' -> * F T'
| / F T'
| e
F -> id
| number
| ( E )
Consider the new parse tree
E
/ \
/ \
T E'
/ \ |
F T' e
| /|\
28 / | \
/ | \
/ F T'
| /|\
7 * F T'
| |
2 e
If processed correctly this tree will yield the correct expression tree.
*
/ \
/ 2
/ \
28 7
The "trick" is to swing up subtrees from the prime nodes. The operator coming up from the prime node is going to be the root of the subtree (for that precedence level) and the new operator is going to be inserted as the left most descendent.
To see how this works with code. Checkout this example recursive descent parser for this grammar.
You can read all about how to do this correctly in the "Dragon Book" Section 4.3.3 (page 212) in the second edition. "Compilers: Principles, Techniques, & Tools" by Aho et. al.
I prefer Mark Twain's “History never repeats itself, but it does often rhyme.”
It's pretty obvious that we have come to a stagnant period of online content and there's a desire to move past the glamour of the Instagram and political fights on Twitter and optimised for ad revenue videos on Youtube but I don't think that the personal websites are coming back.
Those were cool because only specific type of people were able to build websites, then the code free services for sharing content came along and everybody got online presence but because the medium is the message we are kind of getting tired of the message. There seems to be a search for a new medium. The time for the next verse feels around the corner but I don't think we have found it just yet!
I would highly recommend reading Brain of the Firm by Stafford Beer.
It’s the most fantastic layman’s introduction to cybernetics, written from the perspective of the economist behind the “Cyber” in the Chilean CyberSyn project (1970-3).
I discovered him reading People’s Republic of Walmart, another fantastic book about how effective socialist strategies for centralized government are applied in piecemeal to the largest corporations on the globe.
Highly, highly recommended—-and yes, I believe it’s valuable to learn about cybernetics. It teaches us that we don’t need more computers, or faster computers—-we need to use computers in different ways. Basically, we’ve already got the solutions to our problems, but we don’t implement them because we’re trapped by classic civilizational barriers (it’s hard to change people’s minds in the face of a culture that doesn’t want their minds to change).
A favorite example of mine is speed limits. There is a difference between "putting up a sign that says 55 mph and walking away", "putting up a sign that says 55 mph and occasionally enforcing it with expensive humans when they get around to it", and "putting up a sign that says 55 mph and rigidly enforcing it to the exact mph through a robot". Nominally, the law is "don't go faster than 55 mph". Realistically, those are three completely different policies in every way that matters.
We are all making a continual and ongoing grave error thinking that taking what were previously de jure policies that were de facto quite different in the real world, and thoughtlessly "upgrading" the de jure policies directly into de facto policies without realizing that that is in fact a huge change in policy. One that nobody voted for, one that no regulator even really thought about, one that we are just thoughtlessly putting into place because "well, the law is, 55 mph" without realizing that, no, in fact that never was the law before. That's what the law said, not what it was. In the past those could never really be the same thing. Now, more and more, they can.
This is a big change!
Cost of enforcement matters. The exact same nominal law that is very costly to enforce has completely different costs and benefits then that same law becoming all but free to rigidly enforce.
And without very many people consciously realizing it, we have centuries of laws that were written with the subconscious realization that enforcement is difficult and expensive, and that the discretion of that enforcement is part of the power of the government. Blindly translating those centuries of laws into rigid, free enforcement is a terrible idea for everyone.
Yet we still have almost no recognition that that is an issue. This could, perhaps surprisingly, be one of the first places we directly grapple with this in a legal case someday soon, that the legality of something may be at least partially influenced by the expense of the operation.