diff options
Diffstat (limited to 'archive/1.vm/Readme.md')
| -rw-r--r-- | archive/1.vm/Readme.md | 449 |
1 files changed, 449 insertions, 0 deletions
diff --git a/archive/1.vm/Readme.md b/archive/1.vm/Readme.md new file mode 100644 index 00000000..a7394530 --- /dev/null +++ b/archive/1.vm/Readme.md @@ -0,0 +1,449 @@ +Mu explores ways to turn arbitrary manual tests into reproducible automated +tests. Hoped-for benefits: + +1. Projects release with confidence without requiring manual QA or causing + regressions for their users. + +1. Open source projects become easier for outsiders to comprehend, since they + can more confidently try out changes with the knowledge that they'll get + rapid feedback if they break something. Projects also become more + *rewrite-friendly* for insiders: it's easier to leave your project's + historical accidents and other baggage behind if you can be confident of + not causing regressions. + +1. It becomes easier to teach programming by emphasizing tests far earlier + than we do today. + +The hypothesis is that designing the entire system to be testable from day 1 +and from the ground up would radically impact the culture of an eco-system in +a way that no bolted-on tool or service at higher levels can replicate. It +would make it easier to write programs that can be [easily understood by newcomers](http://akkartik.name/about). +It would reassure authors that an app is free from regression if all automated +tests pass. It would make the stack easy to rewrite and simplify by dropping +features, without fear that a subset of targeted apps might break. As a result +people might fork projects more easily, and also exchange code between +disparate forks more easily (copy the tests over, then try copying code over +and making tests pass, rewriting and polishing where necessary). The community +would have in effect a diversified portfolio of forks, a “wavefront” of +possible combinations of features and alternative implementations of features +instead of the single trunk with monotonically growing complexity that we get +today. Application writers who wrote thorough tests for their apps (something +they just can’t do today) would be able to bounce around between forks more +easily without getting locked in to a single one as currently happens. + +In this quest, Mu is currently experimenting with the following mechanisms: + +1. New, testable interfaces for the operating system. Currently manual tests + are hard to automate because a file you rely on might be deleted, the + network might go down, etc. To make manual tests reproducible it suffices + to improve the 15 or so OS syscalls through which a computer talks to the + outside world. We have to allow programs to transparently write to a fake + screen, read from a fake disk/network, etc. In Mu, printing to screen + explicitly takes a screen object, so it can be called on the real screen, + or on a fake screen inside tests, so that we can then check the expected + state of the screen at the end of a test. Here's a test for a little + text-mode chessboard program in Mu (delimiting the edge of the 'screen' + with dots): + + <img alt='a screen test' src='https://github.com/akkartik/mu/html/archive/2.vm/chessboard-test.png'> + + We've built up similarly *dependency-injected* interfaces to the keyboard, + mouse, disk and network. + +1. Support for testing side-effects like performance, deadlock-freedom, + race-freeness, memory usage, etc. Mu's *white-box tests* can check not just + the results of a function call, but also the presence or absence of + specific events in the log of its progress. For example, here's a test that + our string-comparison function doesn't scan individual characters unless it + has to: + + <img alt='white-box test' src='https://github.com/akkartik/mu/html/archive/2.vm/tracing-test.png'> + + Another example: if a sort function logs each swap, a performance test can + check that the number of swaps doesn't quadruple when the size of the input + doubles. + + Besides expanding the scope of tests, this ability also allows more + radical refactoring without needing to modify tests. All Mu's tests call a + top-level function rather than individual sub-systems directly. As a result + the way the subsystems are invoked can be radically changed (interface + changes, making synchronous functions asynchronous, etc.). As long as the + new versions emit the same implementation-independent events in the logs, + the tests will continue to pass. ([More information.](http://akkartik.name/post/tracing-tests)) + +1. Organizing code and tests in layers of functionality, so that outsiders can + build simple and successively more complex versions of a project, gradually + enabling more peripheral features. Think of it as a cleaned-up `git log` + for the project. ([More information.](http://akkartik.name/post/wart-layers)) + +These mechanisms exist in the context of a low-level statement-oriented +language (like Basic, or Assembly). The language is as powerful as C for +low-level pointer operations and manual memory management, but much safer, +paying some run-time overhead to validate pointers. It also provides a number +of features usually associated with higher-level languages: strong +type-safety, function overloading, lexical scope, generic functions, +higher-order functions, and [delimited continuations](http://akkartik.name/coroutines-in-mu). + +*Taking Mu for a spin* + +Mu is currently implemented in C++ and requires a Unix-like environment. It's +been tested on Ubuntu, Mac OS X and OpenBSD; on x86, x86\_64 and ARMv7; and on +recent versions of GCC and Clang. Since it uses no bleeding-edge language +features and has no exotic dependencies, it should work with most reasonable +versions, compilers or processors. + +Running Mu will always (re)compile it if necessary: + + ```shell + $ cd mu/archives/2.vm + $ ./mu + ``` + +As a simple example, here's a program with some arithmetic: + +<img alt='code example' src='https://github.com/akkartik/mu/html/archive/2.vm/example1.png'> + +Mu functions are lists of instructions, one to a line. Each instruction +operates on some *ingredients* and returns some *products*. + + ``` + [products] <- instruction [ingredients] + ``` + +Product and ingredient *reagents* cannot contain instructions or infix +expressions. On the other hand, you can have any number of them. In +particular, you can have any number of products. For example, you can perform +integer division as follows: + + ``` + quotient:number, remainder:number <- divide-with-remainder 11, 3 + ``` + +Each reagent consists of a name and its type, separated by a colon. You only +have to specify the type the first time you mention a name, but you can be +more explicit if you choose. Types can be multiple words and even arbitrary +trees, like: + + ```nim + x:array:number:3 # x is an array of 3 numbers + y:list:number # y is a list of numbers + # ':' is just syntactic sugar + {z: (map (address array character) (list number))} # map from string to list of numbers + ``` + +Try out the program now: + + ```shell + $ ./mu example1.mu + $ + ``` + +Not much to see yet, since it doesn't print anything. To print the result, try +adding the instruction `$print a` to the function. + +--- + +Here's a second example, of a function that can take ingredients: + +<img alt='fahrenheit to celsius' src='https://github.com/akkartik/mu/html/archive/2.vm/f2c-1.png'> + +Functions can specify headers showing their expected ingredients and products, +separated by `->` (unlike the `<-` in calls). + +Once defined, functions can be called just like primitives. No need to mess +with a `CALL` instruction or push/pop arguments to the stack. + +Since Mu is a low-level VM language, it provides extra control at the cost of +verbosity. Using `local-scope`, you have explicit control over stack frames to +isolate your functions in a type-safe manner. You can also create more +sophisticated setups like closures. One consequence of this extra control: you +have to explicitly `load-ingredients` after you set up the stack. + +An alternative syntax is what the above example is converted to internally: + +<img alt='fahrenheit to celsius desugared' src='https://github.com/akkartik/mu/html/archive/2.vm/f2c-2.png'> + +The header gets dropped after checking types at call-sites, and after +replacing `load-ingredients` with explicit instructions to load each +ingredient separately, and to explicitly return products to the caller. After +this translation functions are once again just lists of instructions. + +This alternative syntax isn't just an implementation detail. It turns out to +be easier to teach functions to non-programmers by starting with this syntax, +so that they can visualize a pipe from caller to callee, and see the names of +variables get translated one by one through the pipe. + +--- + +A third example, this time illustrating conditionals: + +<img alt='factorial example' src='https://github.com/akkartik/mu/html/archive/2.vm/factorial.png'> + +In spite of how it looks, this is still just a list of instructions and +labels. Internally, the instructions `break` and `loop` get converted to +`jump` instructions to after the enclosing `}` or `{` labels, respectively. + +Try out the factorial program now: + + ```shell + $ ./mu factorial.mu + result: 120 # factorial of 5 + ``` + +You can also run its unit tests: + + ```shell + $ ./mu test factorial.mu + ``` + +Here's what one of the tests inside `factorial.mu` looks like: + +<img alt='test example' src='https://github.com/akkartik/mu/html/archive/2.vm/factorial-test.png'> + +Every test conceptually spins up a really lightweight virtual machine, so you +can do things like check the value of specific locations in memory. You can +also print to screen and check that the screen contains what you expect at the +end of a test. For example, you've seen earlier how `chessboard.mu` checks the +initial position of a game of chess (delimiting the edges of the screen with +dots): + +<img alt='screen test' src='https://github.com/akkartik/mu/html/archive/2.vm/chessboard-test.png'> + +Similarly you can fake the keyboard to pretend someone typed something: + +<img alt='fake keyboard' src='https://github.com/akkartik/mu/html/archive/2.vm/fake-keyboard.png'> + +..or clicked somewhere: + +<img alt='fake console (keyboard, mouse, ..)' src='https://github.com/akkartik/mu/html/archive/2.vm/fake-console.png'> + +Within tests you can map arbitrary paths (local files or URLs) to contents: + +<img alt='fake file-system and network' src='https://github.com/akkartik/mu/html/archive/2.vm/resources.png'> + +As we add graphics, audio, and so on, we'll augment scenarios with +corresponding abilities. + +--- + +Mu assumes that all ingredients passed in to functions are immutable by +default -- *unless* they are also products. So this program will throw an +error: + +<img alt='immutable ingredient triggering an error' src='https://github.com/akkartik/mu/html/archive/2.vm/immutable-error.png'> + +To modify `foo`'s ingredient, you have to add it to the list of products +returned: + +<img alt='mutable ingredient' src='https://github.com/akkartik/mu/html/archive/2.vm/mutable.png'> + +The names of the variables are important here: a function that takes an +(immutable) address and returns a different one is different from a function +that takes a mutable address (and also returns it). + +These immutability checks can be annoying, but the benefit they provide is +that you can always tell what a function modifies just by looking at its +header. In combination with dependency-injected hardware, they provide all the +benefits of [referential transparency](https://en.wikipedia.org/wiki/Referential_transparency) +that we typically associate with purely functional languages -- along with the +option of imperatively modifying variables willy-nilly. + +--- + +You can append arbitrary properties to reagents besides types. Just separate +them with slashes. + + ```nim + x:array:number:3/uninitialized + y:string/tainted:yes + z:number/assign-once:true/assigned:false + ``` + +Most properties are meaningless to Mu, and it'll silently skip them when +running, but they are fodder for *meta-programs* to check or modify your +programs, a task other languages typically hide from their programmers. For +example, where other programmers are restricted to the checks their type +system permits and forces them to use, you'll learn to create new checks that +make sense for your specific program. If it makes sense to perform different +checks in different parts of your program, you'll be able to do that. + +You can imagine each reagent as a table, rows separated by slashes, columns +within a row separated by colons. So the last example above would become +something like this: + + ``` + z : number / + assign-once : true / + assigned : false + ``` + +--- + +An alternative way to define factorial is by inserting labels and later +inserting code at them. + +<img alt='literate programming' src='https://github.com/akkartik/mu/html/archive/2.vm/tangle.png'> + +(You'll find this version in `tangle.mu`.) + +By convention we use the prefix '+' to indicate function-local label names you +can jump to, and surround in '<>' global label names for inserting code at. + +--- + +Another example, this time with concurrency: + +<img alt='forking concurrent routines' src='https://github.com/akkartik/mu/html/archive/2.vm/fork.png'> + + ```shell + $ ./mu fork.mu + ``` + +Notice that it repeatedly prints either '34' or '35' at random. Hit ctrl-c to +stop. + +[Yet another example](https://github.com/akkartik/mu/blob/master/archive/2.vm/channel.mu) forks +two 'routines' that communicate over a channel: + + ```shell + $ ./mu channel.mu + produce: 0 + produce: 1 + produce: 2 + produce: 3 + consume: 0 + consume: 1 + consume: 2 + produce: 4 + consume: 3 + consume: 4 + + # The exact order above might shift over time, but you'll never see a number + # consumed before it's produced. + ``` + +Channels are the unit of synchronization in Mu. Blocking on a channel is the +only way for the OS to put a task to sleep. The plan is to do all I/O over +channels. + +Routines are expected to communicate purely by message passing, though nothing +stops them from sharing memory since all routines share a common address +space. However, idiomatic Mu will make it hard to accidentally read or +clobber random memory locations. Bounds checking is baked deeply into +the semantics, and using pointers after freeing them immediately fails. + +--- + +Mu has a programming environment: + + ```shell + $ ./mu edit + ``` + +Screenshot: + +<img alt='programming environment' src='https://github.com/akkartik/mu/html/archive/2.vm/edit.png'> + +You write functions on the left and try them out in *sandboxes* on the right. +Hit F4 to rerun all sandboxes with the latest version of the code. More +details: http://akkartik.name/post/mu. Beware, it won't save your edits by +default. But if you create a sub-directory called `lesson/` under `mu/` it +will. If you turn that directory into a git repo with `git init`, it will also +back up your changes each time you hit F4. Use the provided `new_lesson` +script to take care of these details. + +Once you have a sandbox you can click on its result to mark it as expected: + +<img alt='expected result' src='https://github.com/akkartik/mu/html/archive/2.vm/expected-result.png'> + +Later if the result changes it'll be flagged in red to draw your attention to +it. Thus, manually tested sandboxes become reproducible automated tests. + +<img alt='unexpected result' src='https://github.com/akkartik/mu/html/archive/2.vm/unexpected-result.png'> + +Another feature: Clicking on the code in a sandbox expands its trace for you +to browse. To add to the trace, use `stash`. For example: + + ```nim + stash [first ingredient is], x + ``` + +Invaluable at times for understanding program behavior, but it won't clutter +up your screen by default. + +--- + +If you're still reading, here are some more things to check out: + +a) Look at the [chessboard program](https://github.com/akkartik/mu/blob/master/archive/2.vm/chessboard.mu) +for a more complex example with tests of blocking reads from the keyboard and +what gets printed to the screen -- things we don't typically associate with +automated tests. + +b) Try running the tests: + + ```shell + $ ./mu test + ``` + +c) Check out [the programming environment](https://github.com/akkartik/mu/tree/master/edit#readme), +the largest app built so far in Mu. + +d) Check out the tracing infrastructure which gives you a maps-like zoomable +UI for browsing Mu's traces: + + ```shell + $ ./mu --trace nqueens.mu # just an example + saving trace to 'last_run' + $ ./browse_trace/browse_trace last_run + # hit 'q' to exit + ``` + +For more details see the [Readme](browse_trace/Readme.md). + +e) Look at the `build` scripts. Mu's compilation process is itself designed to +support staged learning. Each of the scripts (`build0`, `build1`, `build2`, +etc.) is self-contained and can compile the project by itself. Successive +versions add new features and configurability -- and complexity -- to the +compilation process. + +f) Try skimming the source code. You should be able to get a pretty good sense +for how things work just by skimming the files in order, skimming the top of +each file and ignoring details lower down. +[Some details on my unconventional approach to organizing projects.](http://akkartik.name/post/four-repos) + +**Credits** + +Mu builds on many ideas that have come before, especially: + +- [Peter Naur](http://alistair.cockburn.us/ASD+book+extract%3A+%22Naur,+Ehn,+Musashi%22) + for articulating the paramount problem of programming: communicating a + codebase to others; +- [Christopher Alexander](http://www.amazon.com/Notes-Synthesis-Form-Harvard-Paperbacks/dp/0674627512) + and [Richard Gabriel](http://dreamsongs.net/Files/PatternsOfSoftware.pdf) for + the intellectual tools for reasoning about the higher order design of a + codebase; +- Unix and C for showing us how to co-evolve language and OS, and for teaching + the (much maligned, misunderstood and underestimated) value of concise + *implementation* in addition to a clean interface; +- Donald Knuth's [literate programming](http://www.literateprogramming.com/knuthweb.pdf) + for liberating "code for humans to read" from the tyranny of compiler order; +- [David Parnas](http://www.cs.umd.edu/class/spring2003/cmsc838p/Design/criteria.pdf) + and others for highlighting the value of separating concerns and stepwise + refinement; +- [Lisp](http://www.paulgraham.com/rootsoflisp.html) for showing the power of + dynamic languages, late binding and providing the right primitives *a la + carte*, especially lisp macros; +- The folklore of debugging by print and the trace facility in many lisp + systems; +- Automated tests for showing the value of developing programs inside an + elaborate harness; +- [Python doctest](http://docs.python.org/2/library/doctest.html) for + exemplifying interactive documentation that doubles as tests; +- [ReStructuredText](https://en.wikipedia.org/wiki/ReStructuredText) + and [its antecedents](https://en.wikipedia.org/wiki/Setext) for showing that + markup can be clean; +- BDD for challenging us all to write tests at a higher level; +- JavaScript and CSS for demonstrating the power of a DOM for complex + structured documents. +- Rust for demonstrating that a system-programming language can be safe. |