No problem. You might be better off moving back, yes.
My understanding of immix-style collection is that it divides the heap into blocks and lines. A block is only compacted/reused if every object in it is dead, and so if you mix lifetimes (i.e. lots of short-lived requests, medium-life sessions, long-life db connections/caches/interned symbols) then you tend to fill up blocks with a mix of short and long-lived objects as users log in and make requests.
When the requests get de-allocated the session remains (because the user closed the tab but didn't log out, for example, so the session is still valid) and so you end up with a bunch of blocks that are partially occupied by long-lived objects, and this is what drives fragmentation because live objects don't get moved/compacted/de-fragged very often. Eventually you fill up your entire heap with partially-allocated blocks and there is no single contiguous span of memory large enough to fit a new allocation and the allocator shits its pants.
So if that's what the HN backend looks like architecturally (mixed lifetimes), then you'd probably benefit from the old GC because when it collects, it copies all live objects into new memory and you get defragmentation "for free" as a byproduct. Obviously it's doing more writing so pauses can be more pronounced, but I feel like for a webapp that might be a good trade-off.
Alternatively you can allocate into dedicated arenas based on lifetime. That might be the best solution, at the expense of more engineering. Profiling and testing would tell you for sure.
Dylan (originally called Ralph) was basically Scheme plus a subset of CLOS. It also had some features meant to make it easier to generate small, fast artifacts--for example, it had a module system, and separately-compiled libraries, and a concept of "sealing" by which you could promise the compiler that certain things in the library would not change at runtime, so that certain kinds of optimizations could safely be performed.
Lisp and Smalltalk were indeed used by a bunch of people at Apple at that time, mostly in the Advanced Technology Group. In fact, the reason Dylan existed was that ATG was looking for a Lisp-like or Smalltalk-like language they could use for prototyping. There was a perception that anything produced by ATG would probably have to be rewritten from scratch in C, and that created a barrier to adoption. ATG wanted to be able to produce artifacts that the rest of the company would be comfortable shipping in products, without giving up the advantages of Lisp and Smalltalk. Dylan was designed to those requirements.
It was designed by Apple Cambridge, which was populated by programmers from Coral Software. Coral had created Coral Common Lisp, which later became Macintosh Common Lisp, and, still later, evolved into Clozure Common Lisp. Coral Lisp was very small for a Common Lisp implementation and fast. It had great support for the Mac Toolbox, all of which undoubtedly influenced Apple's decision to buy Coral.
Newton used the new language to write the initial OS for its novel mobile computer platform, but John Scully told them to knock it off and rewrite it in C++. There's all sorts of gossipy stuff about that sequence of events, but I don't know enough facts to tell those stories. The switch to C++ wasn't because Dylan software couldn't run in 640K, though; it ran fine. I had it running on Newton hardware every day for a couple of years.
Alan Kay was around Apple then, and seemed to be interested in pretty much everything.
Larry Tesler was in charge of the Newton group when I joined. After Scully told Larry to make the Newton team rewrite their OS in C++, Larry asked me and a couple of other Lisp hackers to "see what we could do" with Dylan on the Newton. We wrote an OS. It worked pretty well, but Apple was always going to ship the C++ OS that Scully ordered.
Larry joined our team as a programmer for the first six weeks. I found him great to work with. He had a six-week sabbatical coming when Scully ordered the rewrite, so Larry took his sabbatical with us, writing code for our experimental Lisp OS.
Apple built a bunch of other interesting stuff in Lisp, including SK8. SK8 was a radical application builder that has been described as "HyperCard on Steroids". It was much more flexible and powerful than either HyperCard or Interface Builder, but Apple never figured out what to do with it. Heck, Apple couldn't figure out what to do with HyperCard, either.
I saw that Kilo Lisp claimed "constant space garbage collection." I understand why a project like Kilo Lisp might like this, but I was curious about how that was accomplished, so I looked through the code.
The actual GC cycle code is pretty small, and looks like a classic mark-and-sweep over a fixed heap:
int gc(void) {
int i, k;
k = 0;
for (i=0; Root[i]; i++) mark(Root[i][0]);
Freelist = NIL;
for (i=0; i<NNODES; i++) {
if (0 == (Tag[i] & MARK)) {
setcdr(i, Freelist);
Freelist = i;
k = k+1;
}
else {
Tag[i] &= ~MARK;
}
}
/* ... */
return k;
}
Cutting out the verbose GC stuff, there is a finite number of nodes and a free list. Exactly what one might expect. Even sorta feels like hardware.
The function mark is a classic algorithm, the Schorr-Waite algorithm [1], which traverses a directed graph and reverses the pointers, which modifies the heap graph as it traverses it to keep track of how much the graph has.
This is an interesting choice, and gave me pause because in a traditional large heap this would be a fantastically bad decision. But it's pretty interesting that the entire memory image of KiloLisp can exist in side the L2 cache of a raspberry pi and and in some circumstances half the memory can be hot and still reside in L1.
So actually, this is pretty clever. I suspect it's a good case of mechanical sympathy in recognizing that filling L2 will probably remove any gains that a "fancier" algorithm or a non-constant algorithm would bring. Very cool.
I agree with what you're saying, actually. I think these questions require drilling down to philosophical questions such as "what are numbers", "what is the essence of 'number'", "are numbers even real", etc. So I'll give it a go and be shamelessly long-winded about it :)
I think that numbers, set theory, programming languages, etc, are all abstractions. Forming abstractions is a mental tool associated with our ability for language: we spot a pattern and we give that pattern a name. Once we've given it a name, we can talk _about_ the abstract concept as a subject of our statements.
Perhaps the simplest form of abstraction we're capable of is "categorization". Ie we see a pointy-eared small animal that makes meowing sounds, we another one, and another one, ... and even though none of them are identical, our brain picks up on certain patterns in these creatures. We know that when we next see one of them, we can expect certain behaviors. So we give it a name, let's say, "cat", and now we can talk about the abstract concept of "cat" without referring to any specific individual cat. To see how big a deal this is, I find it useful to remember that cats aren't explicitly defined in the fabric of the universe, like they would be in a computer program (where we'd have a "Cat" data structure or object, usually), they're just emergent behavior of interacting molecules.
But we can do more, we can also abstract out properties of objects. We can see that some frogs have a similar color to the leaves of most trees, so we can give this leaf-color a name, "green", and talk about the abstract concept of "green" without referring to a specific green thing. You can just say "I like green" (no one will ask you "a green what?"), or "mixing green and blue makes cyan" (no one will ask "mixing green and blue what makes cyan what?").
And then we also have "chunking", where we can talk about sets of objects as objects themselves. So we can talk about "a herd of sheep" as a singular thing. Our ability to abstract out properties of objects also applies to these chunked concepts. One property of a set of objects is "quantity". Speculation ahead. Initially we probably only had fairly vague terms to talk about quantity, perhaps individual words for small quantities (one, two and three, maybe), and after that it's just "many". But it seems we figured out pretty fast that counting sheep, counting apples, or counting pebbles are really in some sense "the same thing", so we might have first learned to count through some unary "notation" even though we had no names for quantities. We'd make carvings into bone or carry a bag of pebbles, one carving or one pebble for each sheep in our herd. Then we notice that certain operations on these quantities are also all "the same": it doesn't matter whether you're adding pebbles, sheep, carvings, ... you're always doing the same thing. So after a while we start using these operations to define bigger numbers (the French still call the number 80 "quatre-vingts" or "four twenties"). Now all numbers become nameable, and eventually we streamline and standardize these names.
So now we have a name for every number, and we can talk about "thirty-two" without getting back a confused reply "thirty-two what?". And we can talk about operations on these numbers, like addition, multiplication, etc, but our hunger for abstraction isn't satiated at all. Since now we can talk about operations, we can also talk about properties of operations, so we notice that you can flip the arguments of additions and multiplications, and we give that property a name, commutativity, and we go on to invent abstract algebra.
After doing maths for a few thousand years we start looking into patterns into the different, disparate branches of maths at the time (geometry, number theory, logic, etc), and notice that the common pattern is that all of them are doing deductive reasoning, and that should be modellable by logic. So we abstract out the common bits and come up with set theory and proof theory and the like. And in that process we notice that number theory has unnecessarily many axioms and Peano figures out we can just use induction to define the set of natural numbers.
So yes, our intuition for numbers precedes Peano's definition by millennia or far more than millennia. But I'd say that's how it goes for _every_ definition. We always start by noticing some pattern, which initially we can't quite put our finger on (for example, Leibniz had a vague intuition that a lot of work in mathematics was in some sense so mechanical that one should be able to have a machine do it; he couldn't quite define computation yet but his hunch was spot-on), and then we try to refine our thoughts and come up with a definition.
In that sense, I don't think it's more meaningful to worry about the "true nature" of a number (the Peano definition, or some other notation?) than it is to worry about the "true nature" of the color red (is it its wavelength on the electromagnetic spectrum? but a wavelength can be expressed as a number; so is the essence of red just a number? or its RGB value, which is linked to how humans perceive color?). Both numbers and colors are abstractions, and abstractions are mental tools. They are a means to an end: to make sense of the world and communicate about it to other humans. And we use just use the tool that is most helpful given the problem at hand. For most practical applications we're going to use a notation that's compact and easily manipulated (Arabic numerals), but when we're studying the foundations of mathematics, it's more sensible to reduce everything to its smallest, most elegant definition possible. Neither view is "more true" than the other, in both cases you're doing no more than naming patterns in herds of sheep and piles of apples.
This was back in the X360/PS3 era and mostly FPS/Third-person(think unreal engine 3 and the like).
What's really ironic is the PS3 actually had the right architecture for this, the SPUs only had 256kb of directly addressable memory so you had to DMA everything in/out which forced you to think about memory locality, vectorization, cache contention, etc. However X360 hit first so everyone just wrote for its giant unified memory architecture and then got brutalized when they tried to port to PS3.
What's even funnier in hindsight is all that work you'd do to get the SPUs to hum along smoothly translated to better cache usage on the X360. Engines that went <prev gen> -> PS3 -> X360 ran somewhere between 2-5x faster than the same engine that went <prev gen> -> X360 -> PS3. We won't even talk about how bad the PC -> PS3 ports went :).
This story has been reposted many times, and I think GJS's remarks (as recorded by Andy Wingo) are super-interesting as always, but this is really not a great account of "why MIT switched from Scheme to Python."
Source: I worked with GJS (I also know Alexey and have met Andy Wingo), and I took 6.001, my current research still has us referring to SICP on a regular basis, and in 2006 Kaijen Hsiao and I were the TAs for what was basically the first offering of the class that quasi-replaced it (6.01) taught by Leslie Kaelbling, Hal Abelson, and Jacob White.
I would defer to lots of people who know the story better than me, but here's my understanding of the history. When the MIT EECS intro curriculum was redesigned in the 1980s, there was a theory that an EECS education should start with four "deep dives" into the four "languages of engineering." There were four 15-unit courses, each about one of these "languages":
- 6.001: Structure and Interpretation of Computer Programs (the "procedural" language, led by Abelson and Sussman)
- 6.002: Circuits and Electronics ("structural" language)
- 6.003: Signals and Systems ("functional" language)
These were intellectually deep classes, although there was pain in them, and they weren't universally beloved. 6.001 wasn't really about Scheme; I think a lot of the point of using Scheme (as I understood it) is that the language is so minimalist and so beautiful that even this first intro course can be about fundamental concepts of computer science without getting distracted by the language. This intro sequence lasted until the mid-2000s, when enrollment in EECS ("Course 6") declined after the dot-com crash, and (as would be expected, and I think particularly worrisome) the enrollment drop was greater among demographic groups that EECS was eager to retain. My understanding circa 2005 is that there was a view that EECS had broadened in its applications, and that beginning the curriculum with four "deep dives" was offputting to students who might not be as sure that they wanted to pursue EECS and might not be aware of all the cool places they could go with that education (e.g. to robotics, graphics, biomedical applications, genomics, computer vision, NLP, systems, databases, visualization, networking, HCI, ...).
I wasn't in the room where these decisions were made, and I bet there were multiple motivations for these changes, but I understood that was part of the thinking. As a result, the EECS curriculum was redesigned circa 2005-7 to de-emphasize the four 15-unit "deep dives" and replace them with two 12-unit survey courses, each one a survey of a bunch of cool places that EECS could go. The "6.01" course (led by Kaelbling, Abelson, and White) was about robots, control, sensing, statistics, probabilistic inference, etc., and students did projects where the robot drove around a maze (starting from an unknown position) and sensed the walls with little sonar sensors and did Bayesian inference to figure out its structure and where it was. The "6.02" course was about communication, information, compression, networking, etc., and eventually the students were supposed to each get a software radio and build a Wi-Fi-like system (the software radios proved difficult and, much later, I helped make this an acoustic modem project).
The goal of these classes (as I understood) was to expose students to a broad range of all the cool stuff that EECS could do and to let them get there sooner (e.g. two classes instead of four) -- keep in mind this was in the wake of the dot-com crash when a lot of people were telling students that if they majored in computer science, they were going to end up programming for an insurance company at a cubicle farm before their job was inevitably outsourced to a low-cost-of-living country.
6.01 used Python, but in a very different way than 6.001 "used" Scheme -- my recollection is that the programming work in 6.01 (at least circa 2006) was minimal and was only to, e.g., implement short programs that drove the robot and averaged readings from its sonar sensors and made steering decisions or inferred the robot location. It was nothing like the big programming projects in 6.001 (the OOP virtual world, the metacircular evaluator, etc.).
So I don't think it really captures it to say that MIT "switched from Scheme to Python" -- I think the MIT EECS intro sequence switched from four deep-dive classes to two survey ones, and while the first "deep dive" course (6.001) had included a lot of programming, the first of the new survey courses only had students write pretty small programs (e.g. "drive the robot and maintain equal distance between the two walls") where the simplest thing was to use a scripting language where the small amount of necessary information can be taught by example. But it's not like the students learned Python in that class.
My (less present) understanding is that >a decade after this 2006-era curricular change, the department has largely deprecated the idea of an EECS core curriculum, and MIT CS undergrads now go through something closer to a conventional CS0/CS1 sequence, similar to other CS departments around the country (https://www.eecs.mit.edu/changes-to-6-100a-b-l/). But all of that is long after the change that Sussman and Wingo are talking about here.
One of the rules I break on standard ANSI US keyboards is typing c and m with my index finger instead of my middle finger. Other keys in the bottom row are shifted out by one finger, and my pinkies are relieved of bottom row duty, besides the shift key. This makes a regular keyboard more like a linear (matrix) keyboard, with angled columns.
I do this because I keep my hands angled a little bit inward, to avoid the awkward and un-ergonomic bend in my wrist. That is, if standard position is like this:
I struggled with this problem for a long time. I sort of solved it.
The key was to realize that there is a difference between a calendar, a todo list, and an agenda.
A todo list is a list of things that need to be done but usually don’t have a specific time when they need to be done at. They can have priorities or deadlines or fuzzy target dates like “next week.”
A calendar is for storing future concretely scheduled events.
An agenda is a list of things that will happen soon.
Each day I pull things from my calendar, todo list, and prior agenda and create my daily agenda. I also keep notes, doodles, clippings, and references in my agenda.
I use Google calendar as my calendar. It meets my expectations.
For my todo list I use Notion. I break it down into “next, soon, and later”. I add ad-hoc sections like “after the vacation” when needed. Some todo items are scheduled for a specific day or “not sooner than.” I add these to my calendar with an email reminder so they don’t take up any mind space until needed.
Finally, the daily agenda. I use Notion but could probably use a physical notepad. I like being able to archive them as sometimes I need to check when I did something or pull some details from notes. With a digital agenda I can file it into an archive easily.
This is not perfect but it helped me reconcile the rigidity of calendar tools with the need to do keep things freeform in the short term.
I'm open to doing that. It would just be a nontrivial amount of work and there are many nontrivials on the list.
Yes, there's now an Arc-to-JS called Lilt, and an Arc-to-Common Lisp called Clarc. In order to to make those easier to develop, we reworked the lower depths of the existing Arc implementation to build Arc up in stages. The bottom one is called arc0, then arc1 is written in arc0, and then "real" Arc (the full language) is written in arc1. This makes reimplementation easier since you pack as much as possible in the later stages, and only arc0 needs to be written in the underlying system (Racket, JS, or CL).
It also shrank the total Arc implementation by 500 lines or so, which in pg and rtm-land is a couple enclycopedias' worth. That was satisfying, and an indication of how high-level a language Arc is.
> Yes there are some domains where going from the time from zero to a working product is critical. And there are domains where the most important thing is being able to respond to wildly changing requirements
I agree with your observations, but I'd suggest it's not so much about domain (though I see where you're coming from and don't disagree), but about volatility and the business lifecycle in your particular codebase.
Early on in a startup you definintely need to optimize for speed of finding product-market fit. But if you are successful then you are saddled with maintenance, and when that happens you want a more constrained code base that is easier to reason about. The code base has to survive across that transition, so what do you do?
Personally, I think overly restrictive approaches will kill you before you have traction. The scrappy shoot-from-the-hip startup on Rails will beat the Haskell code craftsmen 99 out of 100 times. What happens next though? If you go from 10 to 100 to 1000 engineers with the same approach, legibility and development velocity will fall off a cliff really quickly. At some point (pretty quickly) stability and maintainability become critical factors that impact speed of delivery. This is where maturity comes in—it's not about some ideal engineering approach, it's about recognition that software exists to serve a real world goal, and how you optimize that depends not only on the state of your code base but also the state of your customers and the business conditions that you are operating in. A lot of us became software engineers because we appreciate the concreteness of technical concerns and wanted to avoid the messiness of human considations and social dynamics, but ultimately those are where the value is delivered, and we can't justify our paychecks without recognizing that.
I've always found the best cloud path to stick with basic VM/VPS offerings, blob storage, DNS, CDN and IdP.
Getting into things like functions as a service has always felt a little too hot for me. I don't mind integrating with cloud services though (e.g. S3-compatible APIs).
Hybrid seems to be most compelling if you can keep the monster in the box. Sign up for something like Azure or AWS to get at their IdP, DNS and CDN but keep all your actual machines in a cheaper provider (hetzner, et. al.).
Concur on both. It sounds like we're in the same tiny statistical bucket.
By the way, there is a variant of "googleable" that I find to be a valuable property for names in a codebase, and that is "greppable". I try to make sure that the name of any important concept is a unique string in the program, so a simple grep will yield all the places it occurs. I'll even rename things that aren't as important, if their name includes this string, to preserve said uniqueness. (And no, the 'find usage' feature of IDEs doesn't come close to satisfying this need, since a concept can appear in many ways that don't yield to code analysis, such as comments.)
I think the general issue here is that you can't observe successful businesses or individuals and copy their processes to be successful, because their processes are largely a symptom of their competency, not the cause.
I’ve always thought it a little interesting—some older video games, the game Creatures, maybe some of the Final Fantasy games, possibly Myst(? I didn’t actually play it), seem to have a sort of pseudo solarpunk aesthetic. Mostly I think because they wanted to have puzzles and doodads that were sort of interactive, but also free-standing, and also they wanted to have “old stuff” littered about, so it needs to be renewably powered, to avoid hard to answer questions about who’s going around these ancient ruins fueling all this stuff up.
Or possibly solarpunk just drew inspiration from this stuff, I don’t know.
This is a big deal in the database world as delta, iceberg and hudi mean that data is being stored in an open source format, often on S3.
It means that the storage and much of the processing is being standrdised so that you can move between databases easily and almost all tools will eventually be able to work with the same set of files in a transactionally sound way.
For instance, Snowflake could be writing to a file, a data scientist could be querying the data live from a Jupyter notebook, and ClickHouse could be serving user facing analytics against the same data with consistency guarantees.
If the business then decide to switch Snowflake to Databricks then it isn’t such a big deal.
Right now it isn’t quite as fast to query these formats on S3 as a native ingestion would be, but every database vendor will be forced by the market to optimise for performance such that they tend towards the performance of natively ingested data.
It’s a great win for openness and open source and for businesses to have their data in open and portable formats.
Lakehouse has the same implications. Lots of companies have data lakes and data warehouses and end up copying data between the two. To query the same set of data and have just one system to manage is equally impactful.
It’s a very interesting time to be in the data engineering world.
I'm at Sourcegraph (mentioned in the blog post). We obviously have to deal with massive scale, but for anyone starting out adding code search to their product, I'd recommend not starting with an index and just doing on-the-fly searching until that does not scale. It actually will scale well for longer than you think if you just need to find the first N matches (because that result buffer can be filled without needing to search everything exhaustively). Happy to chat with anyone who's building this kind of thing, including with folks at Val Town, which is awesome.
Yes, for Crash Bandicoot we had to entirely skip the C SDK for everything performance-critical; pushing arguments onto the stack and the SDK popping them off for each function call used more cycles than the underlying operation in many of these SDK calls.
Sony explicitly forbade this, presumably because they envisioned the API established by the C SDK as a way to ensure future backward-compatibility. We just ignored the rules and hoped the superior performance we could achieve would overcome any bureaucratic obstacles.
We also had to reverse engineer some of the PS1’s really nice capabilities. I only learned the hardware supported vector pipelining for strip rendering by noticing the coordinate values move from one register set to the next in the debugger.
Seeing that was a revelation: when rendering a polygonal mesh, you naively have to project three coordinates for each triangle. But if you convert your mesh into sequences of polygonal strips where each triangle shares an edge with the next triangle in the mesh, you only need to project a single additional vertex for each additional polygon in the strip. Observing the behavior in the debugger, it was obvious to me that the Sony hardware had in fact been optimized for this approach. But not only were we not given any documentation on this, we were instead told to use the C SDK, which didn’t expose this capability at all.
The PS1 also had 2KB of “scratchpad” that was slower than registers but much faster than RAM. Hearsay was this was a way for the CPU designers to make use of the physical space on the die meant for floating point instructions which the MIPS CPU in the PS1 didn’t have.
I used the scratchpad to store projected 2D “stamps” of the 3D world (stored in an octree) and Crash: a kind of low-res Crash Flatland. I could then check for X/Y collisions between Crash and the world very rapidly by inspecting the flatland bitmap stored in the 2K scratchpad. This was Mark Cerny’s idea; he was our producer on the Crash games and has also been responsible for PS2 through PS5 hardware.
I’ve been using Q (built on K) for Advent of Code. It’s an amazing language that has made me reconsider what a language and programming should be. I come from a FP background and have always considered abstraction the heart of powerful and expressive programming.
In Q, abstraction is wholly unnecessary. Libraries are unnecessary. I can fit the entire language in my head and all code in the language is built out of the fundamental building blocks of it. There’s no layer after layer of abstraction, just a small base of operators and functions.
One might be tempted to compare it to other small languages, like Scheme. But for Scheme it’s intended that you build higher and higher levels of abstractions. With Q it’s both small and compact, and one rarely if ever feels the need to actually build a library of utility functions or anything really: it renders unnecessary the false prophet of code reuse.
I got interested in Q because some of my friends at other financial institutions were using it for HFT and research on historical tick data. I found it surprising at the time I that their software stacks could be so simple, essentially just a single small executable that entirely fit in the CPU cache that managed both the runtime and their entire database. At the time I thought this was impossible, but now I realize how possible and eminently reasonable this was. Instead of Kafka and Redis and SQL Dbs and Kubernetes and god knows what else, you just have Q. No DevOps bullshit, no containers, no complex shit to manage.
In the past 3 weeks I’ve had to rethink my philosophy of what software needs to be and have concluded that most of us are doing things very very wrong: we’ve created this unnecessary world of complexity that is tantamount to masturbation.
Now let’s talk about the language itself. It may look complex, but it’s actually quite simple. The only real data types are lists, dictionaries, symbols, and numbers. And surprisingly, that’s enough. When programming in it I have no desire for classes or objects or trees or whatever, in fact, just using lists and dictionaries can usually solve the problem in a better way.
Also, while Q is interpreted, it’s so goddamn fast. I’ve done some benchmarks against C and Q is about as fast, sometimes even faster. The optimizations the interpreter does are just insane. Not even joking, a single line of Q can accomplish somewhere between 100 to 1000 lines of what the equivalent C code would look like.
Another plus is that editor tooling is unnecessary, I have no need for autocomplete or inline docs because I can literally remember the entire thing. And since Q is so compact, I can view an entire program on a single screen, no scrolling, no jumping between files.
I’ve also noticed that I can remember the verbatim definition of my code. I can almost perfectly remember my exact code for each Advent of Code solution.
Anyways, good luck on Klong, I’m going to check it out. I don’t like J and wish there was a good open source K/Q like language. I don’t actually like K because the overloads on function arity creates a lot of complexity (Q does away with this), so Klong might be right up my alley!
For anyone who hasn’t tried an array based language, I highly recommend it. Q has expanded my mind more than I thought possible at this point in my career. My last really mind expanded experience in programming was when I picked up Scheme and Haskell in high school. And now after using Q, those languages aren’t that great anyways!
> Not sure I actually understand why K is pushed here almost daily. Is it just the esoterics? Alright, APL and K are expressive for array computation. Do many people here deal with array computation?
People like k for different reasons. For me, it's the right blend of fast to develop and runs fast enough. Someone recently made a database engine called okon which is designed to process HIBP and looking at their github it took 20+ days of C++ code to do. And they managed to get under 49µsec so they pat themselves on the back for it being so good.
But my k(q) solution was written in five minutes and runs in under 5µsec -- almost 10x faster. I used binary search instead of b-tree (a decision the okon author considered but eventually went the b-tree route instead), but it's otherwise the same basic strategy.
So for me, the decision is, 5 minutes, or 20 days, and that's a no-brainer.
> How does this free K from loading and writing data?
Your CPU has a shockingly small amount of directly-attached memory (around 64kb). That's been true since the 1970s, and is likely to be true for another fifty years.
This used to be called ram, but now we call anything directly addressable by the CPU as ram, and we call this thing cache (or L1 or whatever) because that's basically how most people use it.
Now what your CPU does all day, is look at a memory address, and if that's not in the cache, it sends a message to a memory controller and waits for that memory to show up (somewhat a simplification). Those instructions show up, now your CPU can execute them, and those instructions require more memory so again the CPU sends a message to the memory controller and waits for that memory to show up. All day long, alternating between these two wait states, we wait a bit for code, we wait a bit for data, and then we repeat.
Because K is small: Because the interpreter, the application source code, and all your state variables fit into that 64kb, you can see that memory waiting drops by half.
> Is K in fact a thin layer on top of assembler (specifically SIMD and other extensions), for number crunching in the vein of shaders/CUDA?
No. It's a very simple interpreted language that (in most implementations) dispatch directly on the source code (or in some cases, on the AST).
> why those techniques aren't looted for open-source languages.
If you really understand the above, the answer to this question is obvious (hint: try to think about values, not features). Until then; until you really understand the question you're asking, you're not going to find the answer very useful.
> I have heard the interpreter itself is quite small which helps of course
It helps a lot more than a lot: Small is everything.
"Main memory" is something like 1000x slower than "L1 CPU cache", so if your whole program lives in L1 you only pay to receive data, which streams in as fast as main memory can. How can you possibly go any faster than that?
The interpreter looks a lot like this[1], scan a character, do something with it. There's no scanning phase, or AST, or very much analysis at all. Being simple helps keep it small. Writing dense makes it easy to see (without scrolling) similar code which can be refactored into less space. This is how small (dense) source code can also help make small object code. This is how small (dense) source code is fast!
[1]: nsl.com/papers/origins.htm
Once you've done all that, vector instructions and multi-threading can help eke out a little bit more speed. Recognising a couple characters at a time and treating them specially can sometimes help as well, but it also can cost a lot of object size quickly, so there needs to be some balance.
Final Viewpoint Research Institute report, where the entire system (antialiasing, font rendering, svg, etc) was rendered using Nile into Frank, the word/excel/powerpoint equivalent written completely in Nile + Gezira + KScript): http://www.vpri.org/pdf/tr2012001_steps.pdf
Since Alan Kay himself is on Hacker News, maybe he can comment with more links I couldn't find. It's hard to fire up the live Frank environment, though understandably reproducing the working env might not have been a top goal. Maybe someone more cunning can merge these into a single executable repo or whatever so that I can stop playing archaeologist =)
> 1. Is a shell pipeline an appropriate analogy for what you mean by processing things in stages? And if so, do you have any tips for deciding how big to make each stage?
Yes, it's a good analogy and mental model, but not good experience to draw on, because the primitives are on such different levels. An example off the top of my head: Checking if an expression has balanced parentheses. The way you would do it in (not $APL and not $PARSER_GENERATOR) is to go character by character, increase a counter for '(', decrease it for ')' and bail out if you ever go negative. In K you'd do:
open: x='(' / vector of 1 when '(', 0 otherwise
close: x=')' / vector of 1 when ')', 0 otherwise
change: open-close / vector of +1 when '(', -1 when ')', 0 otherwise
running: +\change / running sum of change
balance: *|running / last element - "first of reverse of", this is an idiom in K
dipped: &/running / minimum over running sum of changes
good: (balance=0)&~(dipped<0) / we balanced at the end, and no close before open at any point.
You can't really break things this fine in pipes, and the "one input one output" ergonomic used in pipes tends to restrict the data passed between stages (open and close are two "streams" in the pipe model - you could use more numeric descriptors, but then you lose the elegant pipe structure - and people rarely ever do that).
And after you've grokked it, you'd just write it as two expressions:
b:*|r:+\(x='(')-(x=')') / r:running balance; b:balance at end
g:(b=0)&~(&/r)<0 / good if balanced and no close-before-open dip
Which through time, you'd likely prefer to write as the one liner function
balanced:{b:*|r:+\(x='(')-x=')';(b=0)&~(&/r)<0}
That almost everyone on HN would claim is an unreadable abomination, but would still be perfectly readable to you five years down the line after one minute of reflecting. And then you'll see that Arthur Whitney's function achieving the same is twice as short, five times as fast, but may take you 5 minutes to grok. (Yes, I can write it shorter than this, but I won't).
> 2. Is this sort of like submitting jobs to a thread pool in a more controlled manner? Is this something that APL-alikes tend to handle better than other languages?
I don't know about Dyalog, but the underlying data model and K implementations do threads and processes quite easily (K threads have more sharing limitations than you are used to from other environments, though - but processes are just as easy)
the = (group) operator returns a dictionary from key to indices; e.g.
You can now process the letters independently using "each", e.g. "#:'. group" read 'count each value of group"
#:'. group
2 4 4 2 2 1
Want to do that in parallel? Switch from each (') to parallel-each aka peach (':):
#:':. group
2 4 4 2 2 1
Except this time it was done on multiple threads (or processes on the same machine, with some setup, or even on multiple machines). I think this qualifies as "better than most languages", and is enabled by (a) being mostly functional, so synchronization is rarely needed, and (b) making all loops implicit - "each" instead of explicit "for". Order of iteration is NOT guaranteed, and unhandled exceptions can only abort the entire computation. In return you get parallelization that actually works well with a single character change.
> 3. What do you mean by gather/scatter here?
Let's say we want to implement "uniq" for letters ourselves (even though it is built in; written "?" and called "distinct" these days. Remember our "group" from before? We could take the keys - !group would give that (ordered lexicographically in this case, but that's not always the case). But let's say we want it in order of appearance - we need to take the first of each list, so {x@*:'.=x} - x at the first of each index list of the grouping of x. The "x at" accesses memory non-sequentially (it does in ascending order in this case, but random in general). This is a "gather" operation because we gather data from many places, and if the indexes read are random, is the worst case use for cache systems. By making it a separate stage, it is much easier to optimize - for both the person, and the interpreter/compiler.
The "scatter" is the opposite. Want to do counts of each letter? "c:@[&256;0+"yabba dabba doo";+;1]" read: "in an array of 256 zeros, in each index you get from converting the string to ascii, add one. (From which you can get the lex sorted range with "`c$&c>0" : convert to char those indices where c is greater than 0). But the updates are scattered inside the vector. Do note that grouping allows the "+1" for different groups to happen in parallel without more help (though you'd have to explicitly parallel-each it with the current implementation)
K1 was never available outside of Morgan Stanley AFAIK, and I’ve never seen any docs of it. So ...
APL -> A+ : opinionated (vector indices always start at 0, for example) and “electric” GUI (deserves a whole post to describe)
A+ -> K2 : significantly simplified - only ascii, no multidimensional arrays (uses nested vectors instead), much smaller vocabulary but just as effective in the basics department (e.g. the Whitney where/replicate monastic operator replaces 6 or 7 APL operators), added simple dictionaries, workspaces, dropped a lot of math from language. Simpler electric GUI. Time and date native types (as floating point)
K2 -> K3 mostly dropped GUI afaik. Added integral time and date.
k3 -> K4/kdb+: simplifies language more, comprehensive dictionary, TSDB rolled deeply into language (was previously a product written in K), native 64 bit support.
K4->K6: still more simplification, I think k6 is the kOS language. Never left dev state.
K6->k7->k9: continuous simplification, now at shakti rather than kx/firstderivatives - and with much more community involvement.
I get the same gut reaction as you, but I tried reformatting the code a little bit and it's not _that_ terrible.
From the very little APL I've learnt, I know that operators always have either one parameter (named ω) or two (named α and ω), and their inputs and outputs are always arrays.
If you need to write a lot of such functions, it makes sense to define some macros to help you:
#define V1(f) A f(w)A w; // create one-arg function
#define V2(f) A f(a,w)A a,w; // create two-arg function
#define DO(n,x) {I i=0,_n=(n);for(;i<_n;++i){x;}}
iota is the APL equivalent of Python's range function:
V1(iota) { // Define one-arg function iota.
I n = *w->p; // Get the value of the ω argument.
A z = ga(0, 1, &n); // Allocate output array.
DO(n, z->p[i] = i); // Assign increasing integers.
R z; // Return the result.
}
The plus function adds two arrays:
V2(plus) { // Define two-arg function plus.
I r = w->r, // Get the rank of ω.
*d = w->d, // Get a pointer to ω's data.
n = tr(r,d); // Get tne size of ω's data.
A z = ga(0, r, d); // Allocate output array.
DO(n, z->p[i] = a->p[i] + w->p[i]);
// Add corresponding values of α and ω
R z; // Return the result.
}
Personally I cannot tolerate the lack of whitespace, but the APL guys are known to like to see their entire programs in one screenful. I can understand that some people like to write code like this.
LLMs do not confabulate or hallucinate. They predict the next word in a sequence based on correlations derived from a lot of training data. Sometimes that data happens to be structured enough to statistically generate a word that is fluent and corresponds to what we as readers understand as reality. Sometimes, due to the unclear nature of "truth" and the necessarily incomplete data used to train the model, the word or words that are statistically generated are merely fluent but do not correspond to reality.
The answer to "What are LLMs but humans with extreme amnesia and no central coherence?" is that they are not like humans at all, and only resemble them superficially due to our anthropomorphic tendency to infer a mind upon seeing fluent and roughly correspondent text.
Ok, you guys, this isn't the first time we've heard this request (https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...). I'm willing to do it (edit: not to change the default! just to add the option). It's just that any CSS issue that goes more than a quarter-inch deep is outside both my expertise and my interest.
We can add CSS to https://news.ycombinator.com/news.css for prefers-color-scheme: dark, but that leaves open the question of specifically what CSS to put in there. Anyone who wants to make a suggestion is welcome to. Post it in this thread so others can comment, or email it to hn@ycombinator.com. I've roped Zain, YC's designer, into helping with this, and we'll come up with something.
I did this for years, but in the form of backpacking/hiking/cycling and still do it on occasion (when my family lets me).
Meaning much bigger constraints in weight.
10 years ago, it was really expensive getting the equipment, I used a solar gorilla/power gorilla pack. Very nice, but also heavy. I think around 500€.
Today I use 2 Anker 21 solar W and 3 power banks for half the price and at least triple the power.
(downside is only USB charge, meaning not possible for many laptops, unlike the power gorilla)
Also laptops really improved in battery life and power efficency, meaning, when I started doing it 10 years ago, I could only really work consistently, when I had a real power source nearby. Otherwise it was maybe 2 days of full-time working.
Today I can work forever off the grid, on my cheap rugged Asus Chromebook, as long as the sun shines from time to time and I have a safe place to put up the solar panels.
All in all my mobile office equipment is 4-5 kg.
For short trips with laptop, 1 panel and 1 powerbanks, cables,.. 2.5 kg. Which is managable, even when you carry also your tent and food.
Combining working in nature really helps my creativity and I can recommend trying this out.
The tech really is ready today, unless you want to do heavy video editing or 3D Design.
But coding, in my case mainly with chrome dev tools and node, really works fine off grid. There are new insights to be gained, from top of a mountain, tree, or next to a river, compared to your never changing office wall.
I meant "anodyne" not as a good thing but as "the best we can come up with for now", i.e. at least it wouldn't provoke a big argument about linkbait. That's why I asked readers to suggest something better. Nobody did, so maybe it was just hard.
What the HN guidelines say about titles has been the same for years:
Please use the original title unless it is misleading or linkbait.
We deliberately avoid having detailed policies, but in this case we can derive a few corollaries. What we want is the opposite of what we don't want:
1a. A good title is accurate and netural.
The reason for preferring the original title is to let the text speak for itself, so:
1b. When changing a title, try to find representative language
from the article, rather than making something up.
And since one big reason for the guideline is to minimize bikeshed-style complaining about titles:
1c. The best way to comment that a title is bad is to suggest a better one.
My understanding of immix-style collection is that it divides the heap into blocks and lines. A block is only compacted/reused if every object in it is dead, and so if you mix lifetimes (i.e. lots of short-lived requests, medium-life sessions, long-life db connections/caches/interned symbols) then you tend to fill up blocks with a mix of short and long-lived objects as users log in and make requests.
When the requests get de-allocated the session remains (because the user closed the tab but didn't log out, for example, so the session is still valid) and so you end up with a bunch of blocks that are partially occupied by long-lived objects, and this is what drives fragmentation because live objects don't get moved/compacted/de-fragged very often. Eventually you fill up your entire heap with partially-allocated blocks and there is no single contiguous span of memory large enough to fit a new allocation and the allocator shits its pants.
So if that's what the HN backend looks like architecturally (mixed lifetimes), then you'd probably benefit from the old GC because when it collects, it copies all live objects into new memory and you get defragmentation "for free" as a byproduct. Obviously it's doing more writing so pauses can be more pronounced, but I feel like for a webapp that might be a good trade-off.
Alternatively you can allocate into dedicated arenas based on lifetime. That might be the best solution, at the expense of more engineering. Profiling and testing would tell you for sure.