; Mu: An exploration on making the global structure of programs more accessible. ; ; "Is it a language, or an operating system, or a virtual machine? Mu." ; (with apologies to Robert Pirsig: http://en.wikipedia.org/wiki/Mu_%28negative%29#In_popular_culture) ; ;; Motivation ; ; I want to live in a world where I can have an itch to tweak a program, clone ; its open-source repository, orient myself on how it's organized, and make ; the simple change I envisioned, all in an afternoon. This codebase tries to ; make this possible for its readers. (More details: http://akkartik.name/about) ; ; What helps comprehend the global structure of programs? For starters, let's ; enumerate what doesn't: idiomatic code, adherence to a style guide or naming ; convention, consistent indentation, API documentation for each class, etc. ; These conventional considerations improve matters in the small, but don't ; help understand global organization. They help existing programmers manage ; day-to-day operations, but they can't turn outsider programmers into ; insiders. (Elaboration: http://akkartik.name/post/readable-bad) ; ; In my experience, two things have improved matters so far: version control ; and automated tests. Version control lets me rewind back to earlier, simpler ; times when the codebase was simpler, when its core skeleton was easier to ; ascertain. Indeed, arguably what came first is by definition the skeleton of ; a program, modulo major rewrites. Once you understand the skeleton, it ; becomes tractable to 'play back' later major features one by one. (Previous ; project that fleshed out this idea: http://akkartik.name/post/wart-layers) ; ; The second and biggest boost to comprehension comes from tests. Tests are ; good for writers for well-understood reasons: they avoid regressions, and ; they can influence code to be more decoupled and easier to change. In ; addition, tests are also good for the outsider reader because they permit ; active reading. If you can't build a program and run its tests it can't help ; you understand it. It hangs limp at best, and might even be actively ; misleading. If you can run its tests, however, it comes alive. You can step ; through scenarios in a debugger. You can add logging and scan logs to make ; sense of them. You can run what-if scenarios: "why is this line not written ; like this?" Make a change, rerun tests: "Oh, that's why." (Elaboration: ; http://akkartik.name/post/literate-programming) ; ; However, tests are only useful to the extent that they exist. Think back to ; your most recent codebase. Do you feel comfortable releasing a new version ; just because the tests pass? I'm not aware of any such project. There's just ; too many situations envisaged by the authors that were never encoded in a ; test. Even disciplined authors can't test for performance or race conditions ; or fault tolerance. If a line is phrased just so because of some subtle ; performance consideration, it's hard to communicate to newcomers. ; ; This isn't an arcane problem, and it isn't just a matter of altruism. As ; more and more such implicit considerations proliferate, and as the original ; authors are replaced by latecomers for day-to-day operations, knowledge is ; actively forgotten and lost. The once-pristine codebase turns into legacy ; code that is hard to modify without expensive and stress-inducing ; regressions. ; ; How to write tests for performance, fault tolerance, race conditions, etc.? ; How can we state and verify that a codepath doesn't ever perform memory ; allocation, or write to disk? It requires better, more observable primitives ; than we currently have. Modern operating systems have their roots in the ; 70s. Their interfaces were not designed to be testable. They provide no way ; to simulate a full disk, or a specific sequence of writes from different ; threads. We need something better. ; ; This project tries to move, groping, towards that 'something better', a ; platform that is both thoroughly tested and allows programs written for it ; to be thoroughly tested. It tries to answer the question: ; ; If Denis Ritchie and Ken Thompson were to set out today to co-design unix ; and C, knowing what we know about automated tests, what would they do ; differently? ; ; To try to impose *some* constraints on this gigantic yak-shave, we'll try to ; keep both language and OS as simple as possible, focused entirely on ; permitting more kinds of tests, on first *collecting* all the information ; about implicit considerations in some form so that readers and tools can ; have at least some hope of making sense of it. ; ; The initial language will be just assembly. We'll try to make it convenient ; to program in with some simple localized rewrite rules inspired by lisp ; macros and literate programming. Programmers will have to do their own ; memory management and register allocation, but we'll provide libraries to ; help with them. ; ; The initial OS will provide just memory management and concurrency ; primitives. No users or permissions (we don't live on mainframes anymore), ; no kernel- vs user-mode, no virtual memory or process abstraction, all ; threads sharing a single address space (use VMs for security and ; sandboxing). The only use case we care about is getting a test harness to ; run some code, feed it data through blocking channels, stop it and observe ; its internals. The code under test is expected to cooperate in such testing, ; by logging important events for the test harness to observe. (More info: ; http://akkartik.name/post/tracing-tests) ; ; The common thread here is elimination of abstractions, and it's not an ; accident. Abstractions help insiders manage the evolution of a codebase, but ; they actively hinder outsiders in understanding it from scratch. This ; matters, because the funnel to turn outsiders into insiders is critical to ; the long-term life of a codebase. Perhaps authors should raise their ; estimation of the costs of abstraction, and go against their instincts for ; introducing it. That's what I'll be trying to do: question every abstraction ; before I introduce it. We'll see how it goes. ; --- ;; Getting started ; ; Mu is currently built atop Racket and Arc, but this is temporary and ; contingent. We want to keep our options open, whether to port to a different ; host language, and easy to rewrite to native code for any platform. So we'll ; try to avoid 'cheating': relying on the host platform for advanced ; functionality. ; ; Other than that, we'll say no more about the code, and focus in the rest of ; this file on the scenarios the code cares about. (selective-load "mu.arc" section-level) (ero "running tests in mu.ar.c.t (takes ~30s)") ;? (quit) (set allow-raw-addresses*) (section 20 ; Our language is assembly-like in that functions consist of series of ; statements, and statements consist of an operation and its arguments (input ; and output). ; ; oarg1, oarg2, ... <- op arg1, arg2, ... ; ; Args must be atomic, like an integer or a memory address, they can't be ; expressions doing arithmetic or function calls. But we can have any number ; of them. ; ; Since we're building on lisp, our code samples won't look quite like the ; idealized syntax above. For now they will look like this: ; ; (function f [ ; (oarg1 oarg2 ... <- op arg1 arg2 ...) ; ... ; ... ; ]) ; ; Each arg/oarg can contain metadata separated by slashes and colons. In this ; first example below, the only metadata is types: 'integer' for a memory ; location containing an integer, and 'literal' for a value included directly ; in code. (Assembly languages traditionally call them 'immediate' operands.) ; In the future a simple tool will check that the types line up as expected in ; each op. A different tool might add types where they aren't provided. ; Instead of a monolithic compiler I want to build simple, lightweight tools ; that can be combined in various ways, say for using different typecheckers ; in different subsystems. ; ; In our tests we'll define such mu functions using a call to 'add-code', so ; look for it when reading the code examples. Everything outside 'add-code' is ; just test-harness details that can be skipped at first. (reset) ;? (set dump-trace*) (new-trace "literal") (add-code '((function main [ (1:integer <- copy 23:literal) ]))) ;? (set dump-trace*) (run 'main) ;? (prn memory*) (when (~is memory*.1 23) (prn "F - 'copy' writes its lone 'arg' after the instruction name to its lone 'oarg' or output arg before the arrow. After this test, the value 23 is stored in memory address 1.")) ;? (reset) ;? 2 ;? (quit) ;? 2 ; Our basic arithmetic ops can operate on memory locations or literals. ; (Ignore hardware details like registers for now.) (reset) (new-trace "add") (add-code '((function main [ (1:integer <- copy 1:literal) (2:integer <- copy 3:literal) (3:integer <- add 1:integer 2:integer) ]))) (run 'main) ;? (prn memory*) (when (~iso memory* (obj 1 1 2 3 3 4)) (prn "F - 'add' operates on two addresses")) ;? (reset) ;? 1 ;? (quit) ;? 1 (reset) (new-trace "add-literal") (add-code '((function main [ (1:integer <- add 2:literal 3:literal) ]))) (run 'main) (when (~is memory*.1 5) (prn "F - ops can take 'literal' operands (but not return them)")) (reset) (new-trace "sub-literal") (add-code '((function main [ (1:integer <- subtract 1:literal 3:literal) ]))) (run 'main) ;? (prn memory*) (when (~is memory*.1 -2) (prn "F - 'subtract'")) (reset) (new-trace "mul-literal") (add-code '((function main [ (1:integer <- multiply 2:literal 3:literal) ]))) (run 'main) ;? (prn memory*) (when (~is memory*.1 6) (prn "F - 'multiply'")) (reset) (new-trace "div-literal") (add-code '((function main [ (1:integer <- divide 8:literal 3:literal) ]))) (run 'main) ;? (prn memory*) (when (~is memory*.1 (/ real.8 3)) (prn "F - 'divide'")) (reset) (new-trace "idiv-literal") (add-code '((function main [ (1:integer 2:integer <- divide-with-remainder 23:literal 6:literal) ]))) (run 'main) ;? (prn memory*) (when (~iso memory* (obj 1 3 2 5)) (prn "F - 'divide-with-remainder' performs integer division")) (reset) (new-trace "dummy-oarg") ;? (set dump-trace*) (add-code '((function main [ (_ 2:integer <- divide-with-remainder 23:literal 6:literal) ]))) (run 'main) (when (~iso memory* (obj 2 5)) (prn "F - '_' oarg can ignore some results")) ;? (quit) ; Basic boolean operations: and, or, not ; There are easy ways to encode booleans in binary, but we'll skip past those ; details for now. (reset) (new-trace "and-literal") (add-code '((function main [ (1:boolean <- and t:literal nil:literal) ]))) ;? (set dump-trace*) (run 'main) ;? (prn memory*) (when (~is memory*.1 nil) (prn "F - logical 'and' for booleans")) ; Basic comparison operations (reset) (new-trace "lt-literal") (add-code '((function main [ (1:boolean <- less-than 4:literal 3:literal) ]))) (run 'main) ;? (prn memory*) (when (~is memory*.1 nil) (prn "F - 'less-than' inequality operator")) (reset) (new-trace "le-literal-false") (add-code '((function main [ (1:boolean <- lesser-or-equal 4:literal 3:literal) ]))) (run 'main) ;? (prn memory*) (when (~is memory*.1 nil) (prn "F - 'lesser-or-equal'")) (reset) (new-trace "le-literal-true") (add-code '((function main [ (1:boolean <- lesser-or-equal 4:literal 4:literal) ]))) (run 'main) ;? (prn memory*) (when (~is memory*.1 t) (prn "F - 'lesser-or-equal' returns true for equal operands")) (reset) (new-trace "le-literal-true-2") (add-code '((function main [ (1:boolean <- lesser-or-equal 4:literal 5:literal) ]))) (run 'main) ;? (prn memory*) (when (~is memory*.1 t) (prn "F - 'lesser-or-equal' - 2")) ; Control flow operations: jump, jump-if
# Testable primitives for writing text to screen.
# (Mu doesn't yet have testable primitives for graphics.)
#
# Unlike the top-level, this text mode has no scrolling.
# coordinates here don't match top-level
# Here we're consistent with graphics mode. Top-level is consistent with
# terminal emulators.
type screen {
width: int
height: int
data: (handle array screen-cell)
cursor-x: int
cursor-y: int
}
type screen-cell {
data: grapheme
color: int
}
fn initialize-screen screen: (addr screen), width: int, height: int {
var screen-addr/esi: (addr screen) <- copy screen
var tmp/eax: int <- copy 0
var dest/edi: (addr int) <- copy 0
# screen->width = width
dest <- get screen-addr, width
tmp <- copy width
copy-to *dest, tmp
# screen->height = height
dest <- get screen-addr, height
tmp <- copy height
copy-to *dest, tmp
# screen->data = new screen-cell[width*height]
{
var data-addr/edi: (addr handle array screen-cell) <- get screen-addr, data
tmp <- multiply width
populate data-addr, tmp
}
# screen->cursor-x = 0
dest <- get screen-addr, cursor-x
copy-to *dest, 0
# screen->cursor-y = 0
dest <- get screen-addr, cursor-y
copy-to *dest, 0
}
# in graphemes
fn screen-size screen: (addr screen) -> _/eax: int, _/ecx: int {
var width/eax: int <- copy 0
var height/ecx: int <- copy 0
compare screen, 0
{
break-if-!=
return 0x80, 0x30 # 128x48
}
# fake screen
var screen-addr/esi: (addr screen) <- copy screen
var tmp/edx: (addr int) <- get screen-addr, width
width <- copy *tmp
tmp <- get screen-addr, height
height <- copy *tmp
return width, height
}
# testable screen primitive
# background color isn't configurable yet
fn draw-grapheme screen: (addr screen), g: grapheme, x: int, y: int, color: int {
{
compare screen, 0
break-if-!=
draw-grapheme-on-real-screen g, x, y, color, 0
return
}
# fake screen
var screen-addr/esi: (addr screen) <- copy screen
var idx/ecx: int <- screen-cell-index screen-addr, x, y
var data-ah/eax: (addr handle array screen-cell) <- get screen-addr, data
var data/eax: (addr array screen-cell) <- lookup *data-ah
var offset/ecx: (offset screen-cell) <- compute-offset data, idx
var dest-cell/ecx: (addr screen-cell) <- index data, offset
var dest-grapheme/eax: (addr grapheme) <- get dest-cell, data
var g2/edx: grapheme <- copy g
copy-to *dest-grapheme, g2
var dest-color/eax: (addr int) <- get dest-cell, color
var color2/edx: grapheme <- copy color
copy-to *dest-color, color2
}
fn screen-cell-index screen-on-stack: (addr screen), x: int, y: int -> _/ecx: int {
var screen/esi: (addr screen) <- copy screen-on-stack
var height-addr/eax: (addr int) <- get screen, height
var result/ecx: int <- copy y
result <- multiply *height-addr
result <- add x
return result
}
fn cursor-position screen: (addr screen) -> _/eax: int, _/ecx: int {
{
compare screen, 0
break-if-!=
var x/eax: int <- copy 0
var y/ecx: int <- copy 0
x, y <- cursor-position-on-real-screen
return x, y
}
# fake screen
var screen-addr/esi: (addr screen) <- copy screen
var cursor-x-addr/eax: (addr int) <- get screen-addr, cursor-x
var cursor-y-addr/ecx: (addr int) <- get screen-addr, cursor-y
return *cursor-x-addr, *cursor-y-addr
}
fn set-cursor-position screen: (addr screen), x: int, y: int {
{
compare screen, 0
break-if-!=
set-cursor-position-on-real-screen x, y
return
}
# fake screen
var screen-addr/esi: (addr screen) <- copy screen
# ignore x < 0
{
compare x, 0
break-if->=
return
}
# ignore x >= width
{
var width-addr/eax: (addr int) <- get screen-addr, width
var width/eax: int <- copy *width-addr
compare x, width
break-if-<=
return
}
# ignore y < 0
{
compare y, 0
break-if->=
return
}
# ignore y >= height
{
var height-addr/eax: (addr int) <- get screen-addr, height
var height/eax: int <- copy *height-addr
compare y, height
break-if-<
return
}
# screen->cursor-x = x
var dest/edi: (addr int) <- get screen-addr, cursor-x
var src/eax: int <- copy x
copy-to *dest, src
# screen->cursor-y = y
dest <- get screen-addr, cursor-y
src <- copy y
copy-to *dest, src
}
fn show-cursor screen: (addr screen), g: grapheme {
{
compare screen, 0
break-if-!=
show-cursor-on-real-screen g
return
}
# fake screen
var cursor-x/eax: int <- copy 0
var cursor-y/ecx: int <- copy 0
cursor-x, cursor-y <- cursor-position screen
draw-grapheme screen, g, cursor-x, cursor-y, 0 # cursor color not tracked for fake screen
}
fn clear-screen screen: (addr screen) {
{
compare screen, 0
break-if-!=
clear-real-screen
return
}
# fake screen
var space/edi: grapheme <- copy 0x20
set-cursor-position screen, 0, 0
var screen-addr/esi: (addr screen) <- copy screen
var y/eax: int <- copy 1
var height/ecx: (addr int) <- get screen-addr, height
{
compare y, *height
break-if->
var x/edx: int <- copy 1
var width/ebx: (addr int) <- get screen-addr, width
{
compare x, *width
break-if->
draw-grapheme screen, space, x, y, 0 # color=black
x <- increment
loop
}
y <- increment
loop
}
set-cursor-position screen, 0, 0
}
# there's no grapheme that guarantees to cover every pixel, so we'll bump down
# to pixels for a real screen
fn clear-real-screen {
var y/eax: int <- copy 0
{
compare y, 0x300 # screen-height = 768
break-if->=
var x/edx: int <- copy 0
{
compare x, 0x400 # screen-width = 1024
break-if->=
pixel-on-real-screen x, y, 0 # black
x <- increment
loop
}
y <- increment
loop
}
}
fn screen-grapheme-at screen-on-stack: (addr screen), x: int, y: int -> _/eax: grapheme {
var screen-addr/esi: (addr screen) <- copy screen-on-stack
var idx/ecx: int <- screen-cell-index screen-addr, x, y
var result/eax: grapheme <- screen-grapheme-at-idx screen-addr, idx
return result
}
fn screen-grapheme-at-idx screen-on-stack: (addr screen), idx-on-stack: int -> _/eax: grapheme {
var screen-addr/esi: (addr screen) <- copy screen-on-stack
var data-ah/eax: (addr handle array screen-cell) <- get screen-addr, data
var data/eax: (addr array screen-cell) <- lookup *data-ah
var idx/ecx: int <- copy idx-on-stack
var offset/ecx: (offset screen-cell) <- compute-offset data, idx
var cell/eax: (addr screen-cell) <- index data, offset
var src/eax: (addr grapheme) <- get cell, data
return *src
}
fn screen-color-at screen-on-stack: (addr screen), x: int, y: int -> _/eax: int {
var screen-addr/esi: (addr screen) <- copy screen-on-stack
var idx/ecx: int <- screen-cell-index screen-addr, x, y
var result/eax: int <- screen-color-at-idx screen-addr, idx
return result
}
fn screen-color-at-idx screen-on-stack: (addr screen), idx-on-stack: int -> _/eax: int {
var screen-addr/esi: (addr screen) <- copy screen-on-stack
var data-ah/eax: (addr handle array screen-cell) <- get screen-addr, data
var data/eax: (addr array screen-cell) <- lookup *data-ah
var idx/ecx: int <- copy idx-on-stack
var offset/ecx: (offset screen-cell) <- compute-offset data, idx
var cell/eax: (addr screen-cell) <- index data, offset
var src/eax: (addr int) <- get cell, color
var result/eax: int <- copy *src
return result
}