I still need to respond to many things here - oh I do have responses, but I also need to post what I have been working on, as it is a prelude to discussing those very things in some depth. It is rather wordy, but that is somewhat unavoidable. So, without further adieu, here is what I have been pondering and what I have written in preparation for the development of a relevant library (note that this is more or less meant to be the start of the README of said library):
Memory: A primer
Abstract: Why Haskell needs improved memory abstractions
Most people have a simplistic view of memory, even among programmers. These days it easy to encounter someone who has never stepped foot outside of a memory-managed language. After all, why should they?
That line of thinking is to the detriment of the ecosystem.
There is an over-reliance on using the operating system to provide seemingly infinite memory through the combination of a virtual address space and swapping pages to disk, as a result making developers less than mindful or dare I say even mindless when it comes to memory considerations. This is, after all, how we’ve ended up with eg bloated video games that require 64gb of RAM, 12gb VRAM and 300gb disk space.
Such a foundational topic must not be ignored; even Haskell has fallen prey to this mode of thinking before, resulting in now-historical issues regarding unpinned ByteStrings. Indeed, owing to what amounts to an utter lack of low-level memory abstractions, the Haskell RTS system is written with 50kloc of C, which is an embarassment for what is supposedly one of the most powerful languages on the planet.
NOTE: Although we have and will use the phrase ‘memory abstractions’, that phrase is not entirely accurate. We are in some sense dealing with the mirror-opposite of abstraction, describing what is way-below instead of what could be way-above. Perhaps concretion*, or co-abstraction (contra? counter?) would be a better term - ‘what is implemented’ and ‘how it is implemented’ both become open-ended (eg, abstract-ish) just in opposite directions / as different consequences of the same reasons. If this sounds like Abstract Nonsense, it’s because it is.
However, since it is a mirror concept, the syntax of typeclasses and instances suffices to discuss and ahem implement. The distinction is really only important for relating memory management to something called displacement, which in turn helps explain the need for a finitist and constructive approach to memory ‘abstractions’, and how this is necessarily a mirror / reflection / corollary of the pure functional approach being infinitist.
If this is confusing right now, do not worry, it is not the focus, just an aside. The only really important bit is the distinction between the finitist vs infinitist approach which will come up shortly, because computers have finite memory - or do they? Argh!
* I hesitate to call it ‘implementation’ (as a reflection of ‘abstraction’) since that term is already too loaded.
So what would improved memory abstractions get us?
So far, Haskell has relied on not needing to handle memory management, instead preferring to unsafely use ByteStrings for buffers and rely on the GC (garbage collector) to clean them up - this may suffice for common use cases, but is utterly untenable for many other use cases eg embedded or kernel development.
Maybe you remember what Haskell was like before the real-time GC, the stutter of latency caused by the stop-the-world GC that made Haskell an instant no-go for developing any application needing predictable real-time behavior - who wants to work in a language that can’t even run at 30fps?
Maybe it wouldn’t have taken until literally the 2020’s with GHC 8.10 to build and release the RTGC. Would it have taken so long if Haskell had the proper tools for describing efficient memory layouts and allocators and lifetimes, which languages like Zig and Rust now enjoy even as we do not?
As Heinrich said so eloquently that I must repeat it here, once the choice has been made in favor of “I need to control memory allocation” over “I don’t care about memory allocation”, improving the API of the memory package ranks high in desirability.
Why? Because we could rewrite more of the RTS in Haskell, provide better support for non-GHC compilers, embedded systems, kernel development, improve cryptographic tooling*, or even write a performance-competative game engine*. But we can’t do that without doing the work first to provide the requisite abstractions.
* These are some of my own reasons for wanting this. I used to be a game developer, there’s a reason I’m familiar with low-level memory.
So, let us endeavor to fix that, and dive on in.
What is Memory?
In order to abstract memory, we must define it. What are some facts about memory?
- Memory is a place to access and / or store data.
This is a good start, but is vague enough as to be useless. Perhaps it would be better if we had some examples first. Then we shall try again.
What are some examples of memory?
- RAM (Random-Access Memory)
- ROM (Read-Only Memory)
- WR+ (Write-Once, Read Many)
- CPU registers and cache
- A remote database
- An (analog) audio tape
- A quantum memory bank
- A GPU
- A turing tape
- A book
- A brain
- A man in a room, with a printer, filing system, and OCR scanner
Obviously, some of these are a bit far-fetched, and yet they are undoubtedly all memory. A brain is certainly memory - the original, still made of meat - but it would be silly to try to characterize how the brain stores information right now. Not because it is impractical and useless, but because we have more basic abstractions to deal with first, before such things can become practical and useful.
Nevertheless, each of these illustrates some point or quirk of memory, and none of these are privileged; each is equally valid, because completeness is funny like that.
- RAM is your standard concept of classical binary memory, which is the most common because it is so useful
- The other types of read-write memory tell us that it isn’t just data structures that may be mutable or immutable - sometimes it is a restriction of the memory itself
- The CPU registers and cache tell us that memory addresses may be temporary or even unobservable
- The remote database shows us that memory need not be local nor synchronous
- The analog tape and quantum bank show us that the memory unit need not be binary / digital or even deterministic
- The GPU shows us that memory layouts may be complex, not directly addressable, and that units may be of indeterminate precision
- The Turing tape shows us that memory need not be finite, may have ‘units’ of indefinite complexity, and may require relative addressing
- The book, the brain, and the man show us that memory not even need be ‘part of a computer’*, only that the data be made accessible to it*.
* Or perhaps this is what it means to ‘be part of’ a computer. The answer is a matter of displacement. I am excited to write about that soon, but this comes first.
All of these types of memory have vastly different qualities / properties and thus different uses - but all are certainly ‘memory’. However it seems best to limit our focus to abstractions that are the most useful - so we will ignore the book, the brain, and the man. With the rest of these examples in mind, let us re-state our definition of memory:
- Memory is a place for us to store information in a layout of one or more of some sort of units that may be addressed later to look it up.
That is much better. It tells us who (the user), what (storing data), where (in the address space), when (from now til later), why (to look up data), and how (according to some layout)
NOTE: The 5 W’s are an excellent tools for dissecting a topic for discussion via displacement
So:
- Memory is about storing data in an address space.
- Memory stores that data at an address that points to a set of one or more units of memory
- Memory arranges that data in those units according to some layout
- Memory controls storage according to access rules
Now we are getting somewhere - we have some concepts that make meaningful distinctions between various types of memory - addresses, units, layouts, and access which we must define first in order to later be prepared for concepts like pointers and arrays and allocators.
NOTE: Addresses and layouts are duals; don’t worry about how or why just know that they are related
Note that information is always stored, but not necessarily accessed later. This is because memory is only (ever) meaningful if it is written to (at least once*), and it is nonsensical to try to access data that has not been written. A printer is an example write-only memory. Well, only if you don’t count OCR / human re-input.
* Yes, even read-only memory needs to be written to at least once to be useful. Does that make the name stupid? Also, WR+ memory becomes ROM when written to - its more or less the same thing, just a pre- vs post- write state. Now, dynamic mutability, that’s an interesting property of memory to discuss, but definitely out of scope for what is supposed to be a primer.
Alas, this is all I have written up so far, coming soon in roughly this order:
- Addresses and Address spaces
- Memory units
- Layouts
- Access
- References
- Pointers
- Arrays
- Allocators
Until next time!