fix other mandelbrot variants

[mu.git] / archive / 1.vm / Readme.md

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):

   &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<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:

   &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<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.