Computer Science

Created: by Pradeep Gowda — Updated:Jun 13, 2023

A jumping off point for cs topics.

Curriculum

Concepts

Constructing proofs in the context of CS

via this twitter discussion

Reading Lists

Forgotten ideas of Computer science

Joe Armstrong, the creator of Erlang programming language, asked on twitter (2018/1/11):

“I’m interested in the forgotten ideas of computer science. Needed for a talk.Can you post examples of great CS ideas that have been largely forgotten. Examples: Linda tuple spaces, Boyer-Moore algorithm”. Fascinating response.

ChanningWalton:

Linda tuple spaces (cf: Fly object space by @NigeWarren, gigaspaces‘s commercial offering). “What are tuple spaces and Linda tuple spaces good for?” One use is the blackboard idea. Tuples are put into the space, processes observing the space can be notified of interesting tuples, ‘take’ one or all, perform work and ‘put’ new tuples into the space for other workers to pick up. Tuples can also be leased out from the space, this guarantees only one process can lease a tuple to do something with it. JavaSpaces is based on these ideas. [Argorak: Interesting. Has this influenced the idea of a “document based application” comes from in OS X? Which for example doesn’t close when the last window closed, ready for handling others?] Not really, that’s how OS 9 works also. The “document-based” thing in OS X is mostly about a way of structuring the OOP in your application to best take advantage of the builtin capabilities of NSDocument. The most OpenDoc-y idea in OS X is the little-used “Services” menu. Oddly OpenDoc DID massively influence Microsoft, who stripped down the basic concept to a less-ambitious, but much more practical, set of ideas around IPC/software components. Their version was called OLE, which became COM, which set the basic design of C#/.NET.

enkiv2:

Transpointing windows Regex derivatives Enfilades Cord routing

Specific tech: 9p, MUMPS, XU88, network-transparent object method forwarding, icon/unicon, APL, bitmapped keyboards, literal cranks for debugging, distributed expert systems (like the 5th generation computer project)

Plan9, Xanadu, colorforth, the legacy Amiga community, & the Squeak Smalltalk community each have a greater number of interesting ideas than the whole of the web dev & devops world combined, and all those ideas are 30+ years old.

Hillelogram:

APLs and special purpose langauges, Program Synthesis For Declarative Building Design

thompson_si:
  • Lucid
  • coroutines
rtraschke:
  • Croquet TeaTime protocol for synchronised distributed objects
    • Arena based memory allocation
    • Using make to describe artefact dependencies, instead of as a programming language
robertrodermann:

Inmos Transputer, Occam. π-calculus

mcclure111:

OpenDoc – Briefly in the mid-90s Apple and IBM collaborated on a tech that inverted the idea of a gui “application” and refocused around “documents” as the core idea. You’d be working on a piece of data, and software would exist sort of in a cloud around your document things you previously wrote as an application would be broken down into a cloud of individual features. Features could be mixed and matched from different apps, so you could be in Word using Wordperfect’s spellchecker and editing one of the graphics using Photoshop’s tools.

@andrew_j_stone:

E (programming language) (justincormack: Still alive in capnproto rpc! Directly based on E https://capnproto.org/rpc.html) (evanplaice: The capabilities sound eerily like modern JS + AJAX + Rxjs/promises/async/await. Specifically, the event-callback model to avoid deadlocking, fetchi g distributed resources asynchronously, and using promises to ensure order of execution on async code.)(KentonVarda: The concept of a Promise in both Cap’n Proto and JavaScript is derived from E’s promises, hence they all look similar. However, “capabilities” are an entirely separate concept, not directly related to promises or async event loops. On the Cap’n Proto RPC page, scroll down to “distributed objects” – that’s the part about capabilities.)

jcoplien:

1s complement arithmetic. Lissajou status trace console displays with the upper 8 address bits driving the X-axis and the lower 8 bits driving the Y-axis. Twister-card memory. BCD ALUs. ABACABAD scheduling. Leaky bucket counters. Coroutines. Buddy system. Use of XOR’ed links to traverse a list in either direction with just one link field. And, to be snarky, object-oriented programming, forgotten in about 1980 and replaced by class-oriented programming.

jminguillona:

Bresenham’s algorithm for drawing lines and other graphic primitives

GabeMoralesVR:

More on graphics side of things, but deferred tile-based rendering. Only PVR really explored it, but it makes so much more sense than traditional rasterization. Free z-culling, essentially infinite fill rate, no wasted rasterization. Sadly, apple ditched PVR, so likely dead tech.

exclamatio:

MASCOT, DARTS, all those ’80s real-time system methodologies

Kitten_tech:

The NetBLT protocol: net flow control/retransmission based on transferring blocks, rather than a stream like TCP.

DavidTWeaver:
  • The Marr Hypothesis
    • Multi-Agent Systems
    • Boids Algorithm
    • Cybernetics (or at least, it doesn’t get emphasized in CS anymore)
    • Fuzzy Logic
mhollemans:
  • self modifying code
plragde:

Treaps. Brzozowski derivatives. FKS perfect hashing. (TommyEttinger: Brzozowski derivatives and their successors in partial derivatives are still actively studied in some circles, though I think they have a ways to go to catch highly-optimized traditional regex libraries for efficiency. Great potential though.) (ysr1729: They have been used in decision problems in logic and computer science – e.g. for satisfiability of interval temporal logic using automat-theoretic methods.)

Ngnghm:

Orthogonal Persistence. Reflection. Fexprs. Lisp Machines. The Systems Paradigm. FORTH. The TUNES project. Having lots of simple connected CPUs with each unit of RAM, instead of a overly complex and securitywise hazardous central CPU behemoth (connection machine, greenarrays). (phenidone: Persistence: true and that makes me a little sad - my PhD on GC was implemented in an orthogonal-persistence storage layer. Reflection is still a big thing at least in Java-land, and there is a bit of a forth fanboy-revival in the microcontroller space.)

madrawls:

clockless flow computing

danbjson:

Analogous machines, ie solving a diffential differential equation by building an electric circuit with the same characteristics and then measuring the current over time.

KalmanReti:

Pattern matching as a primitive operation in a language SNOBOL

hypercubed:

(3) Stanford Seminar - Concatenative Programming: From Ivory to Metal - YouTube