Kay Lack

deep in the forth mines with hacked together forth, in a hacked together virtual machine, running in a hacked together web-based forth IDE. the next video approaches

Ed is the standard unix text editor. It's also strange. This is a video about ed, why it is the way it is, and an alternative vision of computing in the world that may just be coming back. youtu.be/GoyNMFccbow

can't believe i missed this vintage shot of 80s Alfred Aho for the last video... would have been so perfect!

every day i get up, i make another clone of ed the Standard Unix Text Editor, i do my burpees, and then i study Unix v7's ed.c to figure out how on earth it works. feels like leetcode for trying to get a job at Bell Labs in 1975

new video! this datatype → [1, 2, 3] ← is a bit of a marvel. it can store items of any size, grow to any length, rarely causes performance issues, and almost every modern language has one. what is it, really? and how does it work?

and that's what it is! most of the time anyway. functional and systems languages often make different choices and then educate their users about them, while general purpose languages like JS also often try to be smart in the edge cases (like sparse arrays)

new video! this datatype → [1, 2, 3] ← is a bit of a marvel. it can store items of any size, grow to any length, rarely causes performance issues, and almost every modern language has one. what is it, really? and how does it work?

this seems to me VERY sneaky. the append operation for this data structure is mostly O(1), but will occasionally be O(n). but! if you graph out the average operations for n appends to a list, it looks like this

new video! this datatype → [1, 2, 3] ← is a bit of a marvel. it can store items of any size, grow to any length, rarely causes performance issues, and almost every modern language has one. what is it, really? and how does it work?

and neither are — these languages (typically, most of the time) use a data structure called a dynamic array. this is essentially a 'wrapper' around a static array. the runtime gives it a fairly generous initial size

new video! this datatype → [1, 2, 3] ← is a bit of a marvel. it can store items of any size, grow to any length, rarely causes performance issues, and almost every modern language has one. what is it, really? and how does it work?

the problem is — accessing elements means scanning the list until you find the item you want. this is O(n), where the array was O(1). a little worrying for a general purpose data structure everyone is using all of the time (and which people will probably embed in other loops)

new video! this datatype → [1, 2, 3] ← is a bit of a marvel. it can store items of any size, grow to any length, rarely causes performance issues, and almost every modern language has one. what is it, really? and how does it work?

the classic answer to this inflexibility is a data structure called a linked list, in which you store pairs of a value and a link to the next record

new video! this datatype → [1, 2, 3] ← is a bit of a marvel. it can store items of any size, grow to any length, rarely causes performance issues, and almost every modern language has one. what is it, really? and how does it work?

the ability to calculate the location of each item, rather than having to search for it, makes arrays very fast for access and storage. and so long as you know every size up front you can use it to store surprisingly complex types too, like 2d arrays or even trees

new video! this datatype → [1, 2, 3] ← is a bit of a marvel. it can store items of any size, grow to any length, rarely causes performance issues, and almost every modern language has one. what is it, really? and how does it work?

that's what my new video is about! link here youtu.be/kPqk07Gpj0A key ideas & some fun snippets in this thread

yes i have created my own virtual machine with its own assembly language to implement my own linked lists for the next video