Virtual Machines

There are no compilers or interpreters. In reality, there are only translators that convert one form into another.

Sometimes, the next form is shorter than the one before, so 2+2 becomes 4, That is typically called evaluation.

Sometimes, the next form is longer than the one before when all the details of the input are added to the output. This is typically called translation. Sometimes, translation is followed by some clever reorganizations (e.g. for optimization). For example, this is a language called "C" that computes the greatest common divisor:

unsigned int gcd (unsigned int a, unsigned int b)
{
    if (a == 0 &&b == 0)
        b = 1;
    else if (b == 0)
        b = a;
    else if (a != 0)
        while (a != b)
            if (a <b)
                b -= a;
            else
                a -= b;
    return b;
}

And this another language, called the "WATCOM C/C++ v10.0a assembler" that is generated by a "C" to "assembler" translator:

 gcd:   mov     ebx,eax
        mov     eax,edx
        test    ebx,ebx
        jne     L1
        test    edx,edx
        jne     L1
        mov     eax,1
        ret
 L1:    test    eax,eax
        jne     L2
        mov     eax,ebx
        ret
 L2:    test    ebx,ebx
        je      L5
 L3;    cmp     ebx,eax
        je      L5
        jae     L4
        sub     eax,ebx
        jmp     L3
 L4:    sub     ebx,eax
        jmp     L3
 L5:    ret

Sometimes translation + optimization takes so long, that it is worth while caching the translated form (so if we ever need it again, we just run the cached form). This is called compilation

Every translation is ready by an interpreter. Some interperators are actual silicon hardware. If we translate down to this form, our binary code it sloshes around, and gets translated into (say) changes to pixels on the screen or changes to the contents of a file.

We call silicon interpreters actual machines and the all the other interpreters that read all the other non-binary translations virtual machines (VM). And any computation is really a sequence of translations down a hierachy of virtual machines; e.g. example:

requirements document # translated by "human" into ..
deisgn notation       # e.g. UML, translated to "C++" by "CAD tool"
"c++"                 # older versions of "c++" translated to "c"
"c"                   # and so it goes on
assembler
machine code
binary                # and finally...
-------
silicon

Examples of virtual machines

The lambda calculus: the grand-daddy of them all: now 90+ years old. The core of LISP.
Resolution: the basis of logic programming. The code of Prolog.
The Smalltalk VM, which is quite old (1970s) and was useful for debugging VM technology.
VirtualBox, VMware, etc that let you run one operating system inside another. For example, here is LINUX running VISTA:
The JAVA virtual machine which has been used to implement over 60www languages including JAVA (naturally), Awk, TCL, JavaScript, Ruby, Lua, Scheme, PHP, Pythom.
Parrot VMwhich has been used to implement over 50 langauges including Tcl, Java, Javascript, Ruby, Lua, Scheme, PHP, Python, and Perl.

The advantages list of pros and cons of virtual machines is based on some excellent article by Wellie Chao.

VM: Disadvantages

Runtimes

Every layer of translation slows down the computer. This is less of a problem these days (faster CPUs, better optimizers) but it is something to bear in mind.

Security

I'm going to let you run any old program inside a VM on my hardware? And that program could (say) launch a denial of service of attack on China without me knowing about it? And, if that program breaks through the walls around the virtual machine, it could take all the data on my machine?

Yeah, right, that'll work.

Trust

Now, my business critical apps are running on someone else's machines. I do not control my own infrastructure. Can I live with that?

VM: Advantages

Mobility

To run N languages on P platforms, just port take a VM that runs the N languges, then port it once for each platform.

Heck, some one has probably done this already if it is a common language (like JAVA) or a poplular plaform (like Windows, Linux, Mac). Which means that, to run your code on many platforms, just make it compatiable with a VM that runs on those platforms.

Most of the virtual machine software on the market today stores a whole disk in the guest environment as a single file in the host environment. Snapshot and rollback capabilities are implemented by storing the change in state in a separate file in the host information.

Isolation

Running everything on one machine would be great if it all worked, but many times it results in undesirable interactions or even outright conflicts. The cause often is software problems or business requirements, such as the need for isolated security. Virtual machines allow you to isolate each application (or group of applications) in its own sandbox environment. The virtual machines can run on the same physical machine (simplifying IT hardware management), yet appear as independent machines to the software you are running.

If one virtual machine goes down due to application or operating system error, the others continue running, providing services your business needs to function smoothly.

CLoud Computing

Once you can run N copies on P platforms, why keep P small? Why not, instead, keep hopping your applciations around to any space CPU, whereever it appears?

VMs make it very easy for someone to sell your their spare CPU. They don' have to deal with the details of your application (which can be quirky++). Instead, they ust have to advertise that they handle a small number of virtual machines.

Ease of Testing

Virtual machines let you test scenarios easily. Most virtual machine software today provides snapshot and rollback capabilities. This means you can stop a virtual machine, create a snapshot, perform more operations in the virtual machine, and then roll back again and again until you have finished your testing.

An Example VM: LISP

Sample LISP program:

(define fib
  (lambda (n)
    (if (< n 2)
        1
        (+ (fib (- n 1))
           (fib (- n 2))))))
(fib 20)

Note that define is setting the vale "fib" to be a list whose first item is "lambda". This is the internal representation of LISP code.

Lisp evaluates expressions, which can be simple (atoms) or compound (lists).

An atom is a string of characters, which can be letters, digits, and most punctuation; the characters may -not- include spaces, quotes, parentheses, brackets, '.', '#', or ';' (the comment character). In this Lisp, case is significant ( X is different from x ).

Atoms: atom 42 1/137 + ok? hey:names-with-dashes-are-easy-to-read
Not atoms: don't-include-quotes (or spaces or parentheses)

A list is a '(', followed by zero or more objects (each of which is an atom or a list), followed by a ')'.

Lists: () (a list of atoms) ((a list) of atoms (and lists))
Not lists: ) ((()) (two) (lists)

The special object nil is both an atom and the empty list. That is, nil = (). A non-nil list is called a -pair-, because it is represented by a pair of pointers, one to the first element of the list (its -car-), and one to the rest of the list (its -cdr-). For example, the car of ((a list) of stuff) is (a list), and the cdr is (of stuff). For another example, the list (42 69 613) looks like this:

(Geek detail: It's also possible to have a pair whose cdr is not a list; the pair with car A and cdr B is printed as (A . B).)

That's the syntax of programs and data. Now let's consider their meaning. You can use Lisp like a calculator: type in an expression, and Lisp prints its value. If you type 25, it prints 25. If you type (+ 2 2), it prints 4. In general, Lisp the LISP VM translates a particular expression in a particular environment (set of variable bindings) by the following algorithm (in the following, some of the details of the operator names are specific to a particular Lisp interpreter called awklisp- but their operations are the same in all Lisps):

If the expression is a number, return that number.
If the expression is a non-numeric atom (a -symbol-), return the value of that symbol in the current environment. If the symbol is currently unbound, that's an error.
Otherwise the expression is a list.
- If its car is one of the symbols: quote, lambda, if, begin, while, set!, or define, then the expression is a -special- -form-, handled by special rules (discussed below):
- Otherwise it's just a procedure call, handled like this:
  - Evaluate each element of the list in the current environment, and then apply the operator (the value of the car) to the operands (the values of the rest of the list's elements). For example, to evaluate (+ 2 3), we
    - First evaluate each of its subexpressions:
      - the value of 2 is 2,
      - the value of 3 is 3.
    - Then we call the addition procedure with 2 and 3 as arguments, yielding 5.
    For another example, take (- (+ 2 3) 1):
    - Evaluating each subexpression gives the subtraction procedure, 5, and 1.
    - Applying the procedure to the arguments gives 4.
A user-defined procedure is represented as a list of the form (lambda <parameters> <body>), such as (lambda (x) (+ x 1)). To apply such a procedure:
- Evaluate its body in the environment obtained by extending the current environment so that the parameters are bound to the corresponding arguments. Thus, to apply the above procedure to the argument 41:
  - evaluate (+ x 1) in the same environment as the current one except that x is bound to 41.
- If the procedure's body has more than one expression -- e.g., (lambda () (write 'Hello) (write 'world!)) -- evaluate them each in turn, and return the value of the last one.

We still need the rules for special forms. They are:

The value of (quote <x>) is <x>. There's a shorthand for this form: '. E.g., the value of '(+ 2 2) is (+ 2 2), -not- 4.
(lambda <parameters> ) returns itself: e.g., the value of (lambda (x) x) is (lambda (x) x).
To evaluate (if <test-expr> <then-exp> <else-exp>):
- first evaluate <test-expr>. If the value is true (non-nil), then return the value of <then-exp>.
- Otherwise return the value of <else-exp>.
- (<else-exp> is optional; if it's left out, pretend there's a nil there.) Example: (if nil 'yes 'no) returns no.
To evaluate (progn <expr-1> <expr-2>...):
- evaluate each of the subexpressions in order
- returning the value of the last one.
To evaluate (while <test> <expr-1> <expr-2>...):
- first evaluate <test>. If it's nil, return nil.
- Otherwise, evaluate <expr-1>, <expr-2>,... in order,
- and then repeat.
To evaluate (set! <variable> <expr>):
- Evaluate <expr>, and then set the value of <variable> in the current environment to the result.
- If the variable is currently unbound, that's an error. The value of the whole set! expression is the value of <expr>.
(define <variable> <expr>) is like set!, except it's used to introduce new bindings, and the value returned is <variable>.

It's possible to define other special forms. Common special forms are:

```
(let ((<var> <expr>)...)
  <body>...)
```
Bind each <var> to its corresponding <expr> (evaluated in the current environment), and evaluate <body> in the resulting environment.
```
(cond (<test-expr> <result-expr>...)... (else <result-expr>...))
```
where the final else clause is optional. Evaluate each <test-expr> in turn, and for the first non-nil result, evaluate its <result-expr>. If none are non-nil, and there's no else clause, return nil.
```
(and <expr>...)
```
Evaluate each <expr> in order, until one returns nil; then return nil. If none are nil, return the value of the last <expr>.
```
(or <expr>...)
```
Evaluate each <expr> in order, until one returns non-nil; return that value. If all are nil, return nil.

Built-in procedures

LISP VMs often come with some pre-define procedures.

List operations:

(null? <x>) returns true (non-nil) when <x> is nil.
(atom? <x>) returns true when <x> is an atom.
(pair? <x>) returns true when <x> is a pair.
(car <pair>) returns the car of <pair>.
(cdr <pair>) returns the cdr of <pair>.
(cadr <pair>) returns the car of the cdr of <pair>. (i.e., the second element.)
(cddr <pair>) returns the cdr of the cdr of <pair>.
(cons <x> <y>) returns a new pair whose car is <x> and whose cdr is <y>.
(list <x>...) returns a list of its arguments.
(set-car! <pair> <x>) changes the car of <pair> to <x>.
(set-cdr! <pair> <x>) changes the cdr of <pair> to <x>.
(reverse! <list>) reverses <list> in place, returning the result.

Numbers:

(number? <x>) returns true when <x> is a number.
(+ <n> <n>) returns the sum of its arguments.
(- <n> <n>) returns the difference of its arguments.
(* <n> <n>) returns the product of its arguments.
(quotient <n> <n>) returns the quotient. Rounding is towards zero.
(remainder <n> <n>) returns the remainder.
(< <n1> <n2>) returns true when <n1> is less than <n2>.

I/O:

(write <x>) writes <x> followed by a space.
(newline) writes the newline character.
(read) reads the next expression from standard input and returns it.

Meta-operations:

(eval <x>) evaluates <x> in the current environment, returning the result.
(apply <proc> <list>) calls <proc> with arguments <list>, returning the result.

Miscellany:

(eq? <x> <y>) returns true when <x> and <y> are the same object. Be careful using eq? with lists, because (eq? (cons <x> <y>) (cons <x> <y>)) is false.
(put <x> <y> <z>)
(get <x> <y>) returns the last value <z> that was put for <x> and <y>, or nil if there is no such value.
(symbol? <x>) returns true when <x> is a symbol.
(gensym) returns a new symbol distinct from all symbols that can be read.
(random <n>) returns a random integer between 0 and <n>-1 (if <n> is positive).
(error <x>...) writes its arguments and aborts with error code 1.

And so...

That's it. Any program that conforms to the above VM can run on any platform that runs a LISP VM.

Now, who wants to buy shares in a computer hardware company?