how I think when I think about programming

a schematic overview of charles babbage's analytical engine

this is a post I've wanted to write for some time. in it, I attempt to explain, on a very basic level, how I think about programming. my hope is to give newer programmers some background knowledge and bigger-picture context. to help give form and structure to what is often presented as just a bunch of shit to remember

I don't attempt to teach programming per se. I don't cover all the details needed to write a program that compiles and runs. there are very many guides for that. I don't discuss computer science, nor do I get into type theory, though both of these topics can serve as a highly eluciditory basis for understanding programming. I talk about "fundamentals" a lot, but my fundamentals aren't a set of overarching theories. just a bag of tools

my goal is to impart some general heuristics about how to think about programming for the subset of people who happen to think like me

I got started programming by just messing around. making tiny modifications to existing javascript twitter bots to fashion my own, with a "fuck it, whatever works" kind of attitude. gradually my modifications got more ambitious, and after a couple months I could write the programs myself. a couple months after that, I found someone doing freelance webdev willing to take me on as a junior partner. and then from there I just kinda learned on the job

I generally consider theory to be useful background knowledge but fastidious study a poor substitute for firsthand experience. I "learn with my hands," is the way I've always put it. it has its upsides and downsides

getting up to "working knowledge" on something is usually trivial for me. I can speedrun in weeks what might take others months, or months what could take them years. I just bang my head on the problem until it (the problem, ideally) breaks

on the other hand, it means that I usually power through things in manic bursts. I easily get bored once progress becomes more incremental, when patience and diligence pay higher dividends than brashness and force. I go back and forth on whether I can and should train myself to be more disciplined, or if I am just a natural crosspollinator-type human and should just embrace it

anyway, if this description of how I learn feels familiar to you, it is likely that the way I think about this stuff will be useful. if you learn better in a formal classroom setting, or with guided mentorship, or through diligent study, or by leaning on carefully composed theoretical foundations, then it's possible the only value this post can provide is a voyeur's glimpse into how the fauves live

I've given bits and pieces of these lectures to at least a dozen people who've come to me at various times for advice about how to get started with programming. I deliver a rundown of the fundamental abstractions used in imperative programming. then I give a glimpse above, at abstractions that can be constructed out of them, and a peek below, at what they themselves abstract over

"abstraction" in mathematics means to use a higher-level concept that carries fewer assumptions but covers a broader superset of cases. complexity is removed for the sake of generalizability. "abstraction" in programming means to paper over the underlying workings of a system with shorthands or conveniences. complexity is added so you can pretend it isn't there. no matter how you dress it up, when you're using a computer, you are always somewhere in the jenga pagoda

master the fundamentals, understand how they're composed into abstractions, and you can pick almost anything up as you go. I've gotten hired for jobs where I didn't know the language I'd be writing, expecting to learn it on their dime in the first couple days. it's easy once you stop seeing syntax and features like "so what does this thing do..." and start seeing "ah, this is what they call that." not a ubiquitous skill in software, but not an uncommon one

the volume of software in existence is massive. hundreds of ecosystems, thousands of tools, millions of libraries. if you tried to learn them all as individual things, it would be impossible. but they're all built out of the same basic parts

I remember when I first started programming, looking at job postings and seeing dozens of languages, tools, acronyms, jargon rattled off as necessary requirements. java c# php perl js ajax ruby go mysql postgres angular react agile scrum aws azure. it was daunting! I barely knew one thing, how was I going to learn 10 or 15, just to get started working?

now I roll my eyes at these lists. I know what they all are, I've dabbled in many, I can easily learn any of them to professional proficiency. a lot of them are particular cases of general things, a lot of them are different words for the same thing, a lot of them are just bullshit. but all of them can be comprehended at a glance and learned by doing

learning a new technology, for an experienced programmer, usually doesn't look like concerted study, thwarted attempts, struggle and triumph. it looks like reading a three-paragraph summary of it, coding in or against it based on vibes, checking documentation for syntax, and bitching about how dumb the guy who designed it must have been

the title of the post is "how I think about programming," not "how you should think about programming." therefore I will brook no criticism. I'm a strong believer in learning styles, and I think people should naturally adopt what is most comfortable. if everything that follows rings false, we probably just have different perspectives

the material should be reasonably accessible to anyone who possesses general familiarity with a curlybrackets language. I admit sometimes I may move too fast, and other times I may get bogged down in detail. I do my best to explicitly introduce technical terminology before making it load-bearing. but pedagogy is hard, and unless you're constantly working with new learners, it's very difficult to keep in mind all the little quirks and customs that you've come to take for granted

if this post feels valuable, but parts are inaccessible, it may be worth revisiting as you gain more experience. I'm trying to bridge gaps between concepts, more than I am trying to actually teach the concepts themselves. form, rather than content

I've been programming for about six years now. before that, I cooked pancakes for a living. don't believe anyone who says you need a fancy degree, specialized training, or exposure since childhood to code. you can pick up programming just by being clever and stubborn

❧

kata one

variables, flow control, scope, functions

the first set of basics are assignment, flow control, and scope. all examples are in c unless otherwise stated. don't be scared if you're used to python or js. c is very easy to write. it's only hard to write correctly

assignment is conceptually very simple. you are storing a value in some named piece of storage:

int a = 2;

here, the value 2 is being stored in a, an integer variable. you can access the value via the name you've given your storage:

printf("%d\n", a); // prints 2

and you can use it for further assignments:

int b = 3;
b = b + a; // b is now 5

the algebraically confusing second line is not an equation. the value of a, then 2, is loaded out of its storage space, and added to the value of b. the sum is stored back in the space b, replacing the 3 that used to be there

the thing to remember is that a and b are not objects. they are names of boxes in which we deposit objects

normally a program proceeds top to bottom, line by line, executing each statement and moving on to the next. it does this forever, until it encounters a statement that tells it to stop, or a kind of error that forces it to stop. but a program that can only proceed or halt cannot do much that is really interesting

programs become truly expressive once you have a way to change the future order of execution based on some present state. mechanisms that do this are called control-flow constructs, and the two most common are branches and loops

this is a branch:

if(a > 2) {
    a = 3;
}
else {
    a = 4;
}

the condition is checked, and based on the result, one of two different blocks will be executed. the code in the blocks can be arbitrarily complex. you can have several conditions checked in sequence, or more complicated constructs with fallthrough rules, but they are computationally equivalent

this is a loop:

int a = 0;
do {
    a++;
} while(a < 10);

the block is executed once unconditionally, then the condition is checked, and based on the result, the block will either be run again, or flow will proceed past the loop to continue as normal. depending on what condition you set, the loop can execute arbitrarily many times, possibly indefinitely. there are other loop forms that check the condition at the top, or lack a condition and force you to explicitly abort inside a nested branch, but they are computationally equivalent

in c, coherent units of execution are grouped together in blocks. blocks are self-contained, enclosed in curlybrackets, and can have their own isolated storage space. when the end of a block is reached, program flow continues in the context it was contained in. in this way, blocks are nested inside each other, ultimately all nested in the main function. a block can access storage areas from its outer containers, but once execution moves outside of a block, all of that block's storage is lost, though changes it made to outside storage is kept

the area of influence a block has, including storage it owns and storage it can access, is called its scope. a block that has a name and can be invoked from somewhere else and passed information is called a function

int timestwo(int n) {
    int x = n * 2;
    return x;
}

for(int i = 0; i < 10; i++) {
    int x = timestwo(i);
    printf("%d\n", x);
}

here, the increasing values of i generated by the for loop are passed in as an argument to the function int timestwo(int). an x is calculated inside the scope of the function and returned to its caller. it then is assigned to x outside, a completely different storage location which just happens to share a name. the storage that was internal to int timestwo(int) is now gone

it's worth noting that other languages, notably javascript, have a somewhat different notion of scope than c. the point I would make is that scope, like many things in programming, is a convention, not a fact of reality. most of the rules don't really "mean" anything on a deep level. they don't transcend the contexts in which they were implemented

type theorists, computer scientists, and category theorists would have a very different view on such an assertion. but that isn't relevant to us right now. we fuck around and find out

learn the rules, how to play within their bounds, and how any when to break them. existentially meaningless but internally consistent is the way to approach. if you obsess over what everything "really means," you will get lost. this is useful for navigating many systems designed by humans besides programming languages

❧

digression one

what is "kata"

I like to think of basic programming concepts as akin to martial arts kata. those of us who tried karate as kids probably remember going in expecting to be doing flips and flying kicks from day one. we were instead instructed to perform the same punch, over and over, without variation. this is kata: the most elementary building block of technique

kata is, I think, the secret to how you actually get good at programming. learning the big fancy stuff—baroque libraries, sprawling plugin ecosystems, towering frameworks—to a very deep level is the province of domain specialists. I respect what they do when they're good at it, but it is not how I work

the way I see it, to be really good, you don't need to study any particular big thing. you need to practice and understand the small things, over and over, until they're second nature. a 100ms lag time on an interface is the limit below which response will feel instantaneous. you want to be able to work that fast with the absolute basics. fast enough that you don't have to think about them at all

there is a wonderful quote by bruce lee that I love to deploy whenever appropriate:

Before I learned the art, a punch was just a punch, and a kick, just a kick. After I learned the art, a punch was no longer a punch, a kick, no longer a kick. Now that I understand the art, a punch is just a punch and a kick is just a kick.

before you understand a field, you are mired in sameness. everything is opaque and undifferentiated. as you learn more, you begin to distinguish elements, group them into classes, construct a taxonomy. when you really, deeply understand something, it gets harder to hold to such strict distinctions, but easier to feel. you can discuss and build models, but you hold those models as contingent and insufficient

there is something deep in the tension between analysis and synthesis that goes way beyond this topic. I feel like that tension is one of the really important ideas about thought, people, cultures, the world. I can't really articulate the weight of it properly. it's just a feeling

having only holism, you are a rube, a sitting duck. you know not. armed with reason, the ability to categorize, to distinguish and dissect, you are dangerous, a weapon. you think you know, but you still don't. it is essential to relearn holism with a grounding in reason to be able to move past this, to feel the world without turning what you touch into ash

there's a stereotype that a scholar-bureaucrat adheres to confucian doctrine in his working years, then indulges in daoism upon retiring. it is probably true that pushing past petty analysis makes it harder to tolerate bullshit, to be a cog in an ugly system, to accept duty and sacrifice. but it also makes you frighteningly effective at work, for those things you do deem valuable enough to work on

that is the higher goal I'm setting here, for this one little field, that itself has remarkably little to say about life. don't get stuck in the models. see past them. and then you can see, a kick is just a kick

❧

memory semantics one

stack and heap

we've been talking about variables in terms of placing values into boxes that we access with convenient names. the place where all those boxes reside is called memory

memory has no inherent structure or meaning to it. it is a very long series of one-byte (eight binary bits, max value 255) boxes, numbered starting from 0, all the way up into the billions. all meaning that the sequences of bytes in memory contain is imposed by the programmer, and thus the programs they write and run on top of

when a program is started, the operating system provides it with the illusion that it is the only program on the machine. its address space starts from the special 0 address—unwritable and used as a standard null value—and nothing else tramples upon its preserve

it needn't be this way: msdos famously passed full control of all memory to any program, meaning everything ran as root and multitasking didn't exist. but unix-style virtual memory allows each program to arrange its own memory however it sees fit while protecting other programs and the os from misbehavior. by convention, usually memory has a handful of read-only sections, plus two major writable sections, called stack and heap

the stack is a last-in, first-out queue that starts at the last address in memory, and grows downward, toward the lower addresses. every time you call a function, one stack frame is added on top of the stack. a stack frame is a chunk of space where one function's arguments and internal storage live. when a function returns, its stack frame is disregarded, and the new top of the stack is once again the function that originally called it

the heap starts from somewhere after the 0 address and grows up toward higher addresses. it is persistent storage, controlled by the programmer directly, and unrelated to where in the function stack you are. you directly ask the operating system for a chunk of memory of a specific size via the function malloc:

int *a = malloc(sizeof(int) * 16);

here, enough space for 16 integers is allocated. each integer is multiple bytes, needed to store numbers larger than 255. our chunk of memory is called a "buffer," and malloc returns a pointer to its first byte

unless released, our buffer will persist for the entire life of the program. when we're done with it, we tell the operating system, so it can recycle the space back into the pool it allocates memory from:

free(a);

the reason why stack and heap grow in opposite directions (towards each other) is so programs have use of all memory available to them if they need to allocate much more on one than the other

❧

kata two

indirection and recursion

as we've seen, every location in memory has an address, and the named boxes we've been storing data in are really just pieces of memory. we can take any of our boxes and get the address its storage starts at as a value we can then store somewhere else:

int i = 3;
int *p = &i;

the asterisk in the type of p indicates that this variable stores a pointer, ie a memory address. the ampersand is the address-of operator, returning the address of the storage used by a variable

the address can then be dereferenced, ie the pointer can be followed and the value at the address it points to retrieved:

printf("%p: %d\n", p, *p); // prints something like "0x7ffd12bd3958: 3"

the function malloc returns the type void *, that is, a pointer that could point to anything. traversing pointers to use or manipulate values stored at their address is often called "indirection" because it is an indirect mechanism of data access

pointers can nest arbitrarily deep. you can have pointers to pointers, and so on, forming large, abstract graphs. the don't truly "nest." fundamentally pointers are just numbers, stored in memory, like large integers. it's only because they're interpreted as memory addresses that they have any meaning

because strings in c are just continuous series of characters, a collection of strings may be represented by the double pointer char **. it's useful to use double pointers to resizable containers so functions can reallocate storage implicitly when needed without breaking references. complex objects are typically represented by structures that point to structures which themselves point to structures. and so on

recursion is the idea of a function calling itself, effecting sequential repeated execution in a manner not unlike a loop. the classic examples of this are the factorial and fibonacci functions, where any result depends on all previous results of the same calculation. this allows them to be expressed succinctly and naturally (albeit often horrifically inefficiently) via recursion:

int factorial(int n) {
    if(n == 0) {
        return 1;
    }
    else {
        return n * factorial(n - 1);
    }
}

here, if you were to call factorial(5), the function would fall into the else branch, and attempt to calculate 5 * factorial(4). this would necessitate another call into the function, and another, until hitting the "base case" of n == 0. then a series of returns effectively unwind all the function calls made thus far, producing the result 120

clever use of recursion allows you to iterate in much more complex ways than a simple loop. it is much easier, for instance, to continuously subdivide a group to perform some task on the subsets with recursion than with looping. various means of sorting collections, or searching for items in complicated nested hierarchies, are naturally suited to being subdivided or accumulated in this manner

things get even more interesting in a language with first-class functions. that is, functions that can be assigned to variables, passed as values, and constructed at runtime (crucially, capturing the environments in which they are constructed). c has the first two properties but not the third. moreover, its syntax for function pointers is notoriously cumbersome, and the language is just not suited for this kind of programming. javascript, being at its core the worst dialect of scheme, has all the necessary features

in a language with first-class functions, you can easily construct functions that accept and apply other functions as arguments, recursively. these, being functions of functions, are called higher-order functions

hofs allow you to very simply express concepts like "apply this operation to all members of a list," "remove all members from the list that fail some boolean test," or "combine all the elements of a list into a result using some specified operation." there are various reasons one would want to do this, but the most obvious is they allow iteration that depends on the structure of what is being iterated over, in a way that doesn't require explicitly tracking position or mutating existing data

these functions are also "pure," meaning they operate data-in, data-out, with no side effects. this makes it very easy to chain operations together into pipelines, and even to regard those pipelines as objects in their own right. stream programming, which regards the pipelines as the units of concern, and data merely as what flows through them, offers a drastically different perspective on what's really "happening" in a program

it is absolutely essential to have an intuitive grasp on indirection and recursion. this is perhaps the most important factor distinguishing a clumsy programmer from a deft one. indirection and recursion are harder at first than storage and flow because their usage forms conceptual graph structures that you must be able to see in your head to manipulate and traverse

remember, the golden rule is to know the basics so well that you shift from conscious thought to reflex action. it took me a long time after learning about these concepts before I could properly feel them. there's no shortcut around repeated exposure

❧

memory semantics two

structs, arrays, enums

a struct is a blueprint for a composite datatype, consisting of a series of named fields of particular types:

struct User {
    char *username;
    int pin;
    bool active;
};

struct User user = { "alice", 1234, true };

on the surface, a struct is a way of grouping together several variables into one structure that can be accessed and passed around as a unit. underneath, a struct is just a buffer. it is just enough space for the sum of its field sizes, allocated contiguously in memory. every type you include in a struct must have a fixed size known at compile time. this means that the struct itself is of a fixed size

because all field sizes are known in advance, you can access struct fields by fixed offsets. the struct itself can be reduced to a pointer to its first field, or, equivalently, the memory address of the start of the buffer. you can use this plus the offsets to access particular fields:

assert(user.pin == &user + sizeof(char *)); // true

it's worth noting the word "struct" is pulling double duty. it may refer either to the definition of the fields that constitute the type. or it may refer to an instantiation of that definition, a particular buffer somewhere in memory. the definition is just a blueprint for making any number of separate buffers

a struct is very conceptually similar to a tuple, an idea more common in functional programming, which is just a specific sequence of datatypes without any field names. in fact, some languages only have tuples, and provide a struct-like record syntax that desugars to simple tuple member access

an array is a series of boxes all of the same datatype, backed by a single buffer (which is, as always, contiguous in memory): a series of integers can be represented by an int array. strings in c are represented by an array of chars, terminated by a null symbol

int evens[] = { 2, 4, 6, 8 };
char name[] = { 'a', 'l', 'i', 'c', 'e', '\0' };

an array can be reduced to a pointer to its first element, ie the start of the buffer. with this, you can do pointer math to access arbitrary elements. because every slot is the same size, an item is just an offset multiplied by the slot size:

assert(evens[3] == evens + 3 * sizeof(int)); // true

arrays are not the same concept as lists, although people will sometimes refer to them offhand as that. a list is a noncontinguous series of boxes, each of which contains a value and a pointer to the next box:

struct Node {
    int x;
    struct Node *next;
};

the last box in the list points to the null address to indicate the end. lists are convenient if you want to add new items without having to reallocate existing storage, because you just have to fix up some pointers. to access any particular item, however, you have to traverse pointers from the start until you find it

if you change both fields in such a struct to void pointers, you get the humble cons cell, the famously versatile lisp primitive:

struct Cons {
    void *car;
    void *cdr;
};

cons cells are flexible enough to construct essentially arbitrary data structures. the elegance of lisp comes from the fact that it represents its own code with cons cells, which are in and of themselves working parse trees. because lisp can manipulate and run lisp code as easily as it can manipulate any data, the language is perhaps uniquely suited for metaprogramming

enums are a way of representing a very simple set of mutually exclusive choices, where any enum value is one of those choices:

enum Color {
    Red,
    Green,
    Blue,
};

underneath, an enum is represented as a single integer. there is a more complex construct, called the union, which can represent choices between two different concrete datatypes, which may include structs. a common pattern, called a tagged union, combines the two, using an enum to indicate which struct variant a union represents

to step back from c, it should be appreciated that these concepts represent something more fundamental than some language's arbitrary mechanism for declaring datatypes. a struct or tuple represents a collection of different types grouped together in a particular order. a tagged union, or equivalently an enum that can carry a value (as it can in some languages), represents a mutually exclusive choice between different types. these are called product types and sum types respectively, and can be nested recursively to make types of arbitrary complexity

to wit, our c types in haskell:

data User = User { username :: String
                 , pin :: Int
                 , active :: Bool
                 }

data List = Node { x :: Int
                 , next :: Node
                 } | Nil

data Cons a b = Cons a b

data Color = Red | Green | Blue

❧

paradigms

imperative and oop

the point of all that was to show the simple primitives that everything builds on top of. variables, functions, arrays, structs, loops, branches, pointers, and recursion. whatever complicated concepts you encounter in higher-level languages, they are more or less composed of these basic elements. often quite literally: the primary implementation language for higher-level languages is c. understanding what building blocks an author had to work with often makes it much easier to draw conclusions about how their work is likely put together

with this in mind, we will explore how to assemble a stripped-down version of the core abstractions of another style of programming, using our simple imperative toolbox

object-oriented programming is a paradigm that is easily accessible to imperative programmers because most of the popular languages for it now can be summed up as "imperative programming plus some extra stuff." there is no reason why it had to be this way. if languages like simula, smalltalk, and eiffel (especially eiffel, google "design by contract" sometime) had become the foundation of modern oop, we would be having a very different conversation right now. but, as it turned out, these first oop languages ended up serving as sources of ideas for languages otherwise grounded in the imperative paradigm

all mainstream object-oriented programming derives from c++. c++ was created as the successor to a language called "c with classes" and might itself be appropriately named "c with everything not in c." c++ is not a strict superset of c, but most reasonable c programs are valid c++ as well

java descends directly from c++, originally written to replace it in contexts where it was too unwieldy, and adopts its curlybrackets syntax and many of its basic assumptions. javascript was heavily inspired by scheme, but had a curlybrackets syntax bolted onto it, and now has oop-friendly class-based inheritance syntax to hide its more unique prototype-based internals. c#, don't let the name fool you, is microsoft java. objective c was the only language in common use that followed the spirit of smalltalk, but it was criticized and eventually deprecated in part because people found it "too weird"

if you are a new programmer, don't feel you have to understand any of the previous three paragraphs. it is more an apologia for the sweeping generalizations I'm about to make

there was a period in the 90s and 00s when java was the standard teaching language for intro cs students. this was always contentious and criticized, and I think that taking oop abstractions as a baseline truth, rather than grounding yourself in the kata I've presented, is a mistake. I usually deliver this example of oop abstractions built from imperative fundamentals as a corrective to people with "everything's an object" brainworms. the object abstraction is totalizing in oop, but once you slice it open and flip it inside out, it's easier to see as a simple organizational tool

going between seeing objects as organization schemes and objects as objects is kind of like watching the optical illusion dancer gif spin one way or the other. declarative programming, functional programming, continuation-passing style, and various other formalisms have this same kind of feel, once you know them well. you can think in them, or about them, at will, and feel that shift in your perception as you go from one to the other

fundamentally, an object is a... thing... that bundles state (variables) and functionality (functions) together. a class is a blueprint for a type of object, describing what state variables it has, and what functions, called methods, can operate on that state. and then an object is a concrete instantiation of that class, with its own storage, independent from all others

no outside entities can read from or write to an object's internal state. it is, as the parlance goes, encapsulated. methods are the sole means of access or mutation. the point of all this is to force all stateful computation through a small set of gatekeeper functions, implemented all in one place, so the program is easier to refactor (rearrange) and reason about

unfortunately, we don't have anything like classes or methods in our imperative language. we only have structs and functions

oop examples are always like, corporate database stuff, or cars for some reason, so I'm consciously fighting that impulse:

typedef struct Android Android;
struct Android {
    char *name;
    char *secret_name;
    unsigned int kills;
    bool on_mission;
};

the typedef is just cute syntax to let us write the type as Android instead of struct Android

then with that struct definition, we can initialize new instances of such a struct:

Android a_two = { "A2", "No2", 972, true };

again, a struct is nothing special. it's syntax for reserving the correct amount of space for a series of variables, accessing fields via pointer offsets, and some compile-time type safety checks

if we want to frequently make androids, and especially if we want to persist them and pass them around, we may want a function that does the setup for us:

Android* make_android(char *name, char *secret_name) {
    Android *a = malloc(sizeof(Android));

    a->name = name;
    a->secret_name = secret_name;
    a->kills = 0;
    a->on_mission = false;

    return a;
}

Android *two_b = make_android("2B", "2E");
Android *nine_s = make_android("9S", NULL);

when you want to make a new android, you just pass in its names. the rest is standard and only needs to be written once

note that a_two is a stack-allocated struct, which means it will go out of scope when the block it was created in is exited. two_b and nine_s are stack-allocated pointers to heap-allocated structs. they can be accessed as long as a copy of the pointer is retained somewhere and are never deallocated unless explicitly freed. the strings likewise never scope out. their data is compiled directly into the binary, and the char pointers are just the address where that data resides

struct data can be modified anywhere with no constraints:

// send 2B on a mission
two_b->on_mission = true;

// 2B scores a kill
two_b->kills++;

this can make it hard to track down bugs, if your program is passing around pointers to these structs and mutating their contents anywhere. it becomes a thousand times worse if concurrency is involved because then things might get changed in the middle of other things using them

one solution to this is to be very strict with ourselves that we'll never touch struct data except in special functions written for this purpose. this gives us one place to put correctness checks so we never forget them, and one place to put debug logging when trying to diagnose a problem

we only need to write each function once. we have them accept a pointer to a struct, and then we modify whichever struct is given to us:

int go_on_mission(Android *a) {
    if(a->on_mission) {
        fprintf(stderr, "%s is already on a mission!\n", a->name);
        return 1;
    }

    a->on_mission = true;
    return 0;
}

void score_kill(Android *a, bool was_friendly) {
    if(was_friendly) {
        printf("redacting combat logs...\n");
    }
    else {
        a->kills++;
    }
}

go_on_mission(two_b);
score_kill(two_b, false);

we have now invented the basics of object-oriented programming. by enshrining our formalism in the language, we can stop viewing it as a handful of conventions employed when working with structs and functions. we can instead roll all the pieces into a single abstraction, hide the details under syntax, and think of the abstraction as the agent:

class android {
    string name;
    string secret_name;
    unsigned int kills;
    bool on_mission;

    public:
        android(string name, string secret_name) {
            this->name = name;
            this->secret_name = secret_name;
            this->kills = 0;
            this->on_mission = false;
        }

        int go_on_mission() {
            if(this->on_mission) {
                fprintf(stderr, "%s is already on a mission!\n", this->name.c_str());
                return 1;
            }

            this->on_mission = true;
            return 0;
        }

        void score_kill(bool was_friendly) {
            if(was_friendly) {
                printf("redacting combat logs... %d corrected kills\n", this->kills);
            }
            else {
                this->kills++;
            }
        }
};

android *two_b = new android("2B", "2E");

two_b->go_on_mission();
two_b->score_kill(false);

the above code is c++. despite that, there is nothing truly new. all the functionality is, from a user's perspective, largely the same as the preceding snippets of c

the c++ class contains both the fields of our c struct and the functions we wrote that accept a pointer to the struct as a parameter. the c++ function android is a constructor, and identical to the c function make_android, except the heap allocation is now implicit. the class constructor is invoked implicitly via the new keyword

the functions go_on_mission and score_kill likewise are the same, except now they are methods. they still take a pointer as their first argument! but this argument is hidden from the function signature, and its value is accessed by the this identifier

and finally, because the data fields are not marked public like the methods, nothing outside of the class can access them. if we were to write something like two_b->kills, it would result in a compiler error

there is so, so much more in oop, but none of it is truly fundamental. I don't mean to pick on the paradigm, but for various reasons it tends to be the worst in terms of making simple things complicated. java, in particular, became in the 00s a way to deskill programming and render the programmer fungible, and so accumulated slogans and stereotypes meant to make it easier to cycle engineers through projects

inheritance, interfaces, and abstract classes are ways to add more methods to things implicitly. operator overloading, generics, (subtype) polymorphism, overrides, and reflection are ways to make functions more flexible or mess with function dispatch. there is an entire cult of "design patterns" drawn from an ominously named book people just call "gang of four" that has an entire eldritch taxonomy of things your enterprise company boss wants you to memorize for half of an entry-level tech salary. visitor patter, observer pattern, decorator pattern, singleton, factory beans factory factory

you do not need to learn any of this shit unless a client is paying you for it. and even then, consider it an occupational hazard

all these details are not really important, and if you are already familiar with oop, this may be horribly long-winded. my actual point is this: there is nothing special about the object abstraction. it's just built up out of our fundamental kata. but when you come up with an abstraction, and you roll it up to be watertight, it lets you stop thinking about the details underneath. none of what we do as programmers would work if we had to think about the implementation details of everything all the time

the danger is that people who come along later may not know what happens underneath. they come to think in terms of the abstraction alone. so when the abstraction fails them, as it always inevitably does, they don't have the context to even understand what is happening

oop is the worst culprit of this kind of thinking because objects present themselves as literal objects. it is very seductive to see them as real things that actually exist. people come to think in the metaphor and the metaphor becomes real

I wanted to do a similar construction of functional programming. start with simple recursion, build up to maps and folds, restrict ourselves to single-assignment (immutability). but it would be another tour like this, and I hope I've made my point. no abstraction is magic, they are almost always conceptually very simple, and it can all be learned, easily, if you know the basics

the last thing I will say about oop is, if you absolutely must niche into it, go for c++, not java. java engineers are made to be replaceable. learn template metaprogramming and give yourself job security until you die

❧

digression two

odds and ends

before getting into the last major technical section, I wanted to share some practical advice on a variety of topics in no particular order. in other words, I want to ramble

I said this is not a tutorial on how to program. so, how the hell do you learn to program?

first, I would say pick a language and stick with it until you are at least at an intermediate level. some are better than others, but in the long run it doesn't matter. there is an idea held by some that starting with java ruins you, or starting with basic ruins you, or whatever. this is not true, unless you niche into it and refuse to broaden your understanding as you broaden your experience

the most important thing I want to get across with this entire article is that "programming" is nothing special. it's a form of applied abstract symbol manipulation. different programming languages do the same things in different ways, and once you get good, you can move fluidly between them. if you have a faculty, whether innate or acquired, for abstract symbol manipulation, you can learn to program

an important collorary to this is that if you can learn to program, you can learn tons of other things just as easily. there are thousands of opinionated programmers online who every day insist on presenting themselves as living counterexamples to this assertion, but nevertheless I am resolute. the only reason why programming is so commonly self-taught is because it is a system that is unusually suited to trial and error by people with no specialized knowledge or specialized equipment. once you master your learning style, as long as you are bright and curious and determined, you can learn anything

so, get reasonably good at one language before branching out. but, do branch out! when you know a language, you think in terms of that language. once you know several in one paradigm, you think in terms of the paradigm. once you know the paradigms, you can just think in programming

this attitude does not come for free. you need to be able to actively relate material across the conceptual gaps, or you will be stuck in these specialized silos like so many people are. this is how college teaches you to think: in terms of tracks and prerequisites

maybe some people really do think best like this. maybe most! I don't want to make any normative claims. but if you have stuck with my bullshit this long, we are probably enough alike that I can be a bit presumptuous

the way I catalog knowledge is more like one big graph. giant, sprawling, with no organization to it, interlinked loosely in some places and tightly in others. when I encounter new topics, I never really worry if I "don't get" most of it. I just look for ways I can relate it back to my graph. if I read a text outside of my depth and barely understand it, it still lays groundwork, a skeleton structure that I can later flesh out with more material

I think the root of creativity is not inventing novel ideas out of nothing, but simply drawing novel edges on a large graph. I think a lot of adult loss of neuroplasticity, adult retreat to conservatism, adult inability to enjoy new art or music, all these various hatreds of newness are just people who decided to stop learning, to stop adapting, and thus lost the ability to do so

I think the "software engineer" sans specialty is gradually losing ground and will be relegated to low status clerical labor within our lifetimes. tooling has made great strides toward the deskilling of rote implementation and maintenance work, and human-in-the-loop systems may well finish the job. the world will always need more crud apps and saas platforms, and it gets easier for the average dev to 80/20 their way to something serviceable enough every day. many professional programmers actually contribute negative value to their orgs. it's just, in a large enough company, it's hard to tell who they are, and no one has incentive to care anyway

but that's for making more versions of things that basically already exist. for new things, for science and art and novel engineering, I think the norms surrounding programming will become more like writing. a tool of expression, a tool you use to enact your knowledge about some procedural or scientific topic. the means, not the end

it can already be used this way, of course, even if the majority of code now written is shitwork. code is not the next mass literacy. most people will never learn, although they may learn just enough to stumble through running the machines that others invented. my expectation, or maybe my hope, is that it can at least be the next latin, the next classical chinese. a tool for a minority, but a large minority, to express their wills in a way that transcends their native culture

the 21st century will have two lingae francae. english, to say. and code, to do

I think the future belongs to people who can use code to gain leverage on the world and to create new things that are more than just software. I think being a domain expert who can program well will be more valuable than a great programmer with no other talents, or a specialist who is incompetent in software. I think being a great programmer, but also able to work across multiple fields, bridge gaps, draw novel inferences, is and will continue to be a superpower

so be good to your graph

anyway. the overarching theme I have been trying to impart with the kata idea is simple: feedback, response. the tighter you make the feedback-response loop, the faster you can work, the faster you can think, the more natural and effortless everything feels. the exact same principle applies to debugging

no one really teaches you how to debug. you just kind of have to figure it out. this is a shame, because debugging is conceptually pretty simple

I think what happens is people learn to program, work by themselves on programs small enough to keep in their heads, and can get by debugging most things just by thinking really hard. then, eventually, they get a job working on a large codebase, or their projects get too big for them to track, or attract contributors, and they are suddenly forced to sink or swim. they then throw together the basic principles of debugging from scratch to solve their problem and then forget they ever didn't know it

there is a remarkable story by dan luu that I think about often, about a computer engineering class. this was infamous as a weed-out class, separating the men from the boys, and was feared for its legendary difficulty. the author breezed through most of it on talent, while students failed left and right at each turn, until the class final which overwhelmed him as well. struggling into the night before the deadline, making no progress, eventually it turned out the only real challenge was to invent debugging. in effect, the kids who realized in time you could systematically test every connection to find the one that needed to be fixed, passed. the rest failed. no one had ever taught them to do this

there are all kinds of fancy tools for debugging, and many of them are quite good, but the basic principle is again: feedback, response. for this, the easiest place to start without having to learn anything new is the humble print statement

my first "real" job, after writing little crud toys in the single-digit-thousands of lines of codes, was a 1.5 million line, 15-year-old, object-oriented perl codebase. if that means nothing to you, know that everyone else winced. printf was my best friend. just put that shit anywhere. print the value that's changing but shouldn't, that should change but doesn't, just scatter prints until you find where it happens. when you find it, print more

change stuff just to see what changes as a result. and you can see if it changes by printing it. imagine you are the world's dumbest scientist. you don't need a strong hypothesis if you can run a new experiment every 20 seconds. feedback, response

don't try to analyze code if it feels overwhelming. the most important skill you learn on your first big codebase is how to not read code that isn't important. just relax, focus on the one thing you care about, and do anything that gives you more information about it

if building and running the code takes too long, try and find a simpler case that produces the same error. print stack traces so you can see where things are coming from. just iterate, focus on getting more information, faster, and narrowing your focus. feedback, response

use version control. that means use git. you can develop niche opinions about weird version control systems when you are old and wizened. (hopefully by that time the pijul rewrite will be usable, and we can share a beer over that...)

git is very simple. in your code directory, git init makes a repository. git add FILENAME stages a file for commit, ie does nothing but you have to do it anyway. git commit creates a new commit with your staged files, which is like a checkpoint of where you're at. git remote add origin URL sets up the place where your repository get stored for safekeeping/sharing. git push origin BRANCH where branch is probably main or master puts your repository on the internet. if you ever have problems, copy the entire project directory somewhere for safekeeping before you fuck around with it. you now know more about version control than the typical cs undergrad who didn't just self-teach already

version control is a gamechanger for various reasons and I don't understand how nontechnicals live without it. you have backups of everything, files are error-checked for consistency, you can see when changes were made, you can describe why you made those changes, you can experiment with changes and back them out trivially. use it

text editors. you can learn vim or emacs if you want. I use vim and would die without it. but honestly at this point sublimetext and vscode are fine and don't have the same steep learning curve. people rag on ides partly out of elitism and partly because ides used to be horrible monolithic corporate shit. sublimetext and vscode are fine

use linux. ok, ok, you can use osx if you really insist, but don't blame me when getting software to work is annoying. don't use windows, you're making your life hell for no reason. in software, we distinguish between normal places, and "windows shops." everything important targets linux first, so everything on windows is completely different, and almost always inferior

as for what distro, ubuntu is fine. I could bitch endlessly about it, but if you're new to unix, ubuntu is fine. you can develop strong opinions about linux distros much earlier than you can about version control, don't worry

this is not to say linux is strictly the best os for everything. linux sucks for most people. telling designers to get off osx or non-tech business guys to get off windows is nonsense. their platforms work better for them, they have mass adoption, they have all the best tools for those workflows. switching would give them a vastly inferior experience, for what, bragging rights? among people they don't have any reason to want to impress? but for software work, linux is just the best. there's no debate here

learn the command line. it's a fucking pain in the ass to get started, everything is inscrutable because all this stuff was thrown together by a group of guys in the 70s at one company for one machine, not expecting it to be the basis of all modern computing. the original unix clock ran at 60hz and would have rolled over after 2.5 years if they hadn't changed it, that's how far ahead they were thinking. sorry, this is just how it is. the command line is too useful to neglect

the best way to learn to program, I think, is by coming up with some small project that seems tractable and figuring out whatever you need to solve it. this is easier said than done, because new programmers have the hardest time of anyone at thinking up things to attempt and judging whether they're doable. once you are are good at programming, you will have literally hundreds of ideas of things to do but lack the time to do more than two or three at once. so enjoy it while it lasts

javascript or python are probably the most reasonable beginner languages. they both have their quirks, but they have a wealth of learning material, and most importantly, comprehensive library support for anything you might want to do. following examples in a book to make the console print sunny or cloudy based on random number rolls bores most people to tears. you want to build something that you enjoy, that makes you feel like you've created something of value, no matter how silly or small. and then just build up from there. feedback, response

❧

kata three

registers, jumps, calling convention

it was fun to take apart the object-oriented paradigm and see how someone raised in its bosom may be seduced by it abstractions. unfortunately, we have been seduced as well. objects, methods, inheritance, and design patterns are not real things. but neither are variables, loops, structs, or functions. it's abstractions all the way down

programming languages are a set of techniques provided for the benefit of the human programmer. but to run them, they must be compiled to machine code, which is nothing but a long sequence of binary digits. interpreting these number streams is famously difficult for humans, though not impossible. programmers who wrote raw binary or could read coredumps in hex are part of the lore of the field. our culture-heroes

a set of human-readable mnemonics for machine code, plus a handful of simple labor-saving shortcuts, is called an assembly language. assembly was one of the first inventions for making programming more efficient for human operators, before compilers and before high-level languages. examples in assembly suffice to demonstrate what is "really" going on underneath the code, to further develop intuitions on what is possible in computers, and to develop more flexibility in adapting to new systems

I firmly believe every high-level programmer worth their salt needs to understand c, and every c programmer needs to understand assembly. the mediocre dive into their abstraction and make a career out of it and it alone, shutting their eyes to anything outside their walled garden. but to actually be good, you need to know what's happening underneath your feet

machine code is not the last abstraction in the pile. but below there you get into hardware engineering, and below that electrical engineering. these abstractions are not airtight either. but they're outside my paygrade. google "rowhammer attack" or "spectre attack" or "acoustic cryptanalysis" sometime if you want to peer into the void

on a basic level, a computer can be thought of as a cpu that executes instructions, a set of boxes called registers that hold one value each, and a long, homogeneous series of bytes that constitute main memory

"arrays" are a shorthand for manipulating sections of memory that happen to be laid out in a particular way. "structs" are likewise a convention imposed on homogenous and undifferentiated memory. "stack" and "heap" are conventions. "buffers" are conventions too: malloc and free get sections of memory from the operating system, and annotate them with metadata, but writing outside of them is exploitable, not impossible. even "code" is just bytes in memory

when you invoke a program, an operating system program called the loader puts all its data into memory. the program has an entrypoint, which is an address to start interpreting code from. instructions are executed in sequence, one after the other, with the current execution address being stored as a value in a register called the instruction pointer (ip) or program counter (pc). the cpu executes whatever is pointed at and moves the pointer to the next instruction. branch instructions simply modify the ip register, indirectly causing the cpu to execute instructions somewhere else instead

the distinction between "code" and "data" is arbitrary, only enforced as a safety mechanism after a series of famous exploits that revolved around tricking programs into executing user-supplied data as code. taking control of the instruction pointer is the same as taking control of the entire program. it's all just bytes in memory

revisiting our original c examples, we can see how some simple operations compile (with optimizations disabled) down to assembly:

int a = 2;
int b = 3;
b = b + a; // b is now 5

corresponding to:

40110b:   c7 45 f8 02 00 00 00    mov    DWORD PTR [rbp-0x8],0x2
401112:   c7 45 f4 03 00 00 00    mov    DWORD PTR [rbp-0xc],0x3
401119:   8b 45 f4                mov    eax,DWORD PTR [rbp-0xc]
40111c:   03 45 f8                add    eax,DWORD PTR [rbp-0x8]
40111f:   89 45 f4                mov    DWORD PTR [rbp-0xc],eax

there is a lot new here to understand

values in assembly are typically rendered in hexadecimal, for human convenience. hex is a base-16 counting system, with digits ranging 0-9 followed by a-f. that is, 0x9 is 9, 0xa is 10, 0xf is 15, and 0x10 is 16. the 0x prefix is a convention indicating what counting system we're using. hex is convenient because a digit represents exactly four bits, so two digits is always a byte

the numbers in the first column are addresses. just the number of bytes from some fixed 0 address, much like main memory. the second column with individual hex digit pairs is the exact machine code in the binary. note the third line has three bytes in the second column and an address ending in 19. the address on the next line ends in 1c, three bytes higher

the third and fourth columns are mnemonics for the machine code. there's only two kinds of instruction in this simple example, mov and add

mov is an entire spectrum of instructions that (contrary to the name) copy data from one location to another. in this syntax, the destination is to the left of the comma, much as the assigned variable in c is to the left of the equals. the first two lines move the hardcoded values 2 and 3 into particular locations on the stack, identified by offsets from the base pointer, rbp, a register that contains the address of the bottom of the current stack frame

the third line copies the value of b into a general-purpose register called eax. the reason for this is add can only operate on a register. the next line adds the value of a into the eax register, and the final line copies that value back to b on the stack

aside from the instructions themselves, we also use three different kinds of operands. the source operands on lines one three and five are 0x2, DWORD PTR [rbp-0xc], and eax respectively. the first is an immediate, ie the number 0x2 simply represents the value 2. the second is an indirect memory access: indirect in the exact same way as indirection. an address is calculated as an offset from the base pointer and dereferenced to produce a value. the third is a register name, and the value is retrieved from that register

and finally, note that this and all assembly examples are in what's called intel syntax. there is an alternate syntax called at&t that looks rather different, and has operands in the opposite order. but it is just a way to display machine code for human convenience. the machine code bytes are exactly the same

blocks and higher-level flow-control constructs don't exist in assembly. all flow control compiles down to simple jumps:

if(a > 2) {
    a = 3;
}
else {
    a = 4;
}

corresponding to:

401119:   83 7d f8 02             cmp    DWORD PTR [rbp-0x8],0x2
40111d:   0f 8e 0c 00 00 00       jle    40112f 
401123:   c7 45 f8 03 00 00 00    mov    DWORD PTR [rbp-0x8],0x3
40112a:   e9 07 00 00 00          jmp    401136 
40112f:   c7 45 f8 04 00 00 00    mov    DWORD PTR [rbp-0x8],0x4

here, on the first line, a comparison is performed between the value in a and the number 2. this comparison sets a bit in a special register called the status register, which is evaluated by the jle instruction. jle is a conditional jump, "jump if less or equal," which skips to the assignment of 4 on the last line of the assembly. if the jump is not taken, ie if a's value is greater than 2, control simply proceeds to the next line. the assignment of 3 is performed, and then an unconditional jump skips past the assignment of 4

a loop looks roughly similar:

int a = 0;
do {
    a++;
} while(a < 10);

corresponding to:

40110b:   c7 45 f8 00 00 00 00    mov    DWORD PTR [rbp-0x8],0x0
401112:   8b 45 f8                mov    eax,DWORD PTR [rbp-0x8]
401115:   83 c0 01                add    eax,0x1 
401118:   89 45 f8                mov    DWORD PTR [rbp-0x8],eax
40111b:   83 7d f8 0a             cmp    DWORD PTR [rbp-0x8],0xa
40111f:   0f 8c ed ff ff ff       jl     401112

the loop begins on line two, and three instructions perform the add, and a comparision and conditional jump determine whether to repeat the action. a while loop, by contrast, would perform the comparison up top and jump past the end if it failed

it is worth noting that c actually has a jump of its own, called goto. it is unfairly maligned

the last thing to understand here is that the function, just like the branch or the loop, is just another kind of jump:

int timestwo(int n) {
    int x = n * 2;
    return x;
}

int a = 5;
int x = timestwo(a);

corresponding to:

40112f:	c7 45 f8 05 00 00 00 	mov    DWORD PTR [rbp-0x8],0x5
401136:	8b 7d f8             	mov    edi,DWORD PTR [rbp-0x8]
401139:	e8 c2 ff ff ff       	call   401100 
40113e:	89 45 f4             	mov    DWORD PTR [rbp-0xc],eax

the main block is straightforward. 5 is stored on the stack, then copied to the register edi for argument passing, and then our timestwo function is called. call is a special kind of unconditional jump that first pushes a return address onto the stack

and this is the assembly for the timestwo function, in its entirety, including setup/teardown I've been skipping:

401100:	55                   	push   rbp
401101:	48 89 e5             	mov    rbp,rsp
401104:	89 7d fc             	mov    DWORD PTR [rbp-0x4],edi
401107:	8b 45 fc             	mov    eax,DWORD PTR [rbp-0x4]
40110a:	c1 e0 01             	shl    eax,0x1
40110d:	89 45 f8             	mov    DWORD PTR [rbp-0x8],eax
401110:	8b 45 f8             	mov    eax,DWORD PTR [rbp-0x8]
401113:	5d                   	pop    rbp
401114:	c3                   	ret

the first thing a function does is store the current base pointer on the stack and reset the base pointer to the current stack pointer. it then copies the value in edi to the stack. in other words, function arguments are just normal stack variables. so far, this has all been standard setup for a function to execute. how this is done is basically arbitrary, as long as everything does it the same way. the set of steps taken to set up and tear down a function call on a particular platform is known as its "calling convention"

from there, the actual computation proceeds. the multiplication by 2 is performed by a left shift operator, moving all bits to the left by one, effectively doubling the number. that is, multiplication by 2 in decimal is equivalent to multiplication by 10 in binary. the result is moved into eax, the register used for a function's single return value. and then the caller's base pointer is restored to rbp and the address stored on the stack is popped and jumped back to with ret

as an aside, every function call adds a stack frame, and if you run out of space, the program will either preemptively crash, or attempt to write past its bounds and be killed by the operating system with an error like "segmentation violation." overrunning the stack space is called a stack overflow, and in general invalid memory access is called a segfault. but, interestingly, some functional programming languages have a feature called tail-call optimization. these languages can detect that some recursive sequences don't actually need their stack frames, and optimize them to a simple loop. a series of jumps modifying a value in a register. it's all just jumps

this has been a lot of information to dump. if there is any section of this rather long post that is ok not to grasp, it's this one. but with this knowledge of the underlying systems, we can demystify the abstractions above, and also understand why certain things work the way they do

a machine register typically holds a single machine word. on x64 this is a qword, which is eight bytes. sometimes programmers from higher-level languages wonder if you can return a struct, or an array, or multiple values in c. this makes it obvious why you cannot: a register is used, so the only possible return is a single value. if a higher-level language wants to return something special, it probably returns a pointer and fixes up some things behind the scenes, just as call and ret fix up things of their own

it also explains why data does not persist on the stack, and why arguments are primitive values or pointers, and why the maximum addressable memory of a system is determined by its word size. again, I hammer one of my central points: it's not about understanding the particular details of a particular system. it's about simultaneously being able to think in terms of an abstraction which is inherently meaningless, and look beyond it at lower abstractions which are themselves meaningless

to not get trapped in the web, but to glide over it, as the spider, and in due time spin your own

❧

alice maz

how I think when I think about programming

kata one

variables, flow control, scope, functions

digression one

what is "kata"

memory semantics one

stack and heap

kata two

indirection and recursion

memory semantics two

structs, arrays, enums

paradigms

imperative and oop

digression two

odds and ends

kata three

registers, jumps, calling convention

further reading