wiki:Implementation

Implementation

Lets talk about implementation (using Wishful Thinking).

VMs

There is some logic behind the idea of abstracting out a Virtual Machine.

The logic is that there were so many different computer architectures, and rewriting the code for each one of them is a tedious task. Instead, they will write the code, once for the Virtual Machine, according to specification, and then someone else will implement the program with will emulate that Virtual Machine (basically, JIT-ed bytecode interpreter) on real hardware.

OK, nice idea (using abstractions almost always a nice idea, unless it is taken to extreme and produces an utopia) but implementation was crap, and the language itself is even worse.

This was the logic behind world-famous "Write once, run everywhere" meme. It was cool, packers were delighted, millions were spent and made. Lets forget it. We know that, like PHP, it is mere "Write once, run away!".

Abstract VM *seems* like a good idea, when your language is strict and has these typed boxes - staticly typed variables. To make it work they have a specification for that abstract virtual machine.

This is a good idea, we will have our simple specification too. The process is much more efficient when someone is explained and clarified all the "hows and whys", so we should do it for ourselves.

We need no abstract Virtual Machine because we think that a x86_64 CPU is good-enough concrete one.

In Lisp there is no variable, no boxes. Values has type tags attached to it. Symbols could be bound (temporarily or permanently) to values.

It is almost (except for tags) mimics the way a CPU works. It doesn't care about types. Any sequience of bits of appropriate size could be loades into a register, then an instruction could be execured. If the set of bits represents an appropriate encoding of a value for an operand, then the result of instruction will be correct.

Surprise, but most of CPU instructions (those which not depend of "external state" in the flag register) behave the very same way as primitive procedures in a functional language - they always procuce the same input for the same output (how else a computer supposed to work?)

This is, of course, oversimplification, an incomplete model, but, for our purposes it is OK. There are lots of issues with mutability of data and messing "calling conventions" - some instructions use one set of registers, some another, but that is OK.

We don't need all the instuctions, we need smallest good-enough subset, to encode our small but good enough set of primitive procedures.

A pointer is just an address of a byte in machine's memory. An address is just an offset, a number of a byte.

Logically, for a CPU values are typed but untagged. (We use type tags "inside Lisp" but just strip them for CPU code. JVM does the same - it strips out all the type information, but bytecode calls are typed).

It means that there is a certain encoding (rules and ordering) of values, but the values themselves are not tagged. They must be encoded in a certain way to have a meaning and to be given as arguments to CPU's instructions.

For example, a set of 64 consecutive bits could be interpreted (decoded) as an address, a signed or unsigned integer of a floating point value, or a set of bit fields.

The real power and flexibility of uniform pointers comes from the fact that it doesn't matter to what kind of bit arrangement it points to. There is no stupid "boxes" of different kinds.

As long as there are different encodings for different CPU instructions (primitive procedures) we must take care of different kind of values, but this does not mean that using labeled (named) and tagged (typed) "boxes" (variables) is the best possible way.

Lisp extents this notion by adding type tags to the values AND by doing so, allowing a value to be of more than one type, which is quite impossible with box-like variables.

This has something to do with how our minds work. We have some concepts in our mind, and we attach "labels" or "symbols" to them. "Cat" is a word associated with a concept (the meaning of this word) we have in our mind. We also could have a visual "symbol", a picture of what we associated with what we call a cat.

From the "writing" (an ability) perspective the visual image of one or more continuous glyphs of English letters (not necessarily forming a dictionary word of English language) is a symbol.

So, symbol is just a pointer to the representation of a concept, of its meaning.

What about VMs? Well, as long as we have instructions (primitive procedures) pointers, mechanism of calling procedures (a named set of instructions which produces the same output for the same input) and the call stack (which is most important "abstraction" of a CPU design), we have enough to express any algorithm. We also have a set of registers (they are more like placeholders, NOT statically typed variables) so we could use them as mere symbols.

Stack machines are good (JVM) Register machines are good (V8) JIT-ed small VMs are good (Lua-JIT) but a Haswell+ x86_64 CPU is a better machine. (a VM in silicone) (it uses uops and internal registers to execute x86 instruction set) technically, it is a RISC cpu which "interprets" x86 instruction set so it is a nice "bytecode" for us. (especially when we are using small but good-enough subset)

Lot's of resources spent on compatibility (Windows) and hardware optimizations (lame code). Let's use a good-enough subset of CPU instruction set. (strict instruction-level compatibility will be there as long as Windows)

Some sort of a "view" or "perspective" of what a CPU looks like for the compiler could be called a VM, but let's not mess eveything up. It is just a CPU.

Compiler

There are small compilers which could produce reasonable x86 code. One such compiler is included in Golang, which is based on Plan9 C compiler.

There are native compilers in every mature CL implementation - CMUCL, SBCL, CCL etc. Those compilers are complicated because they could generate code for variety of platforms, ranging from ARM (CCL) to Spark64 (CMUCL).

MIT Scheme has native compiler.

We don't need such complications. Small compiler for small set of primitive procedures.

Ideally, it is a mapping between primitive procedures and CPU instructions, a translator, a bunch of templates to be filled. (naive wishful thinking).

Optimizations later.

Simplify!

  • AMD64 Instruction set ONLY. x86_64.
  • 64bit mode ONLY.
  • lots of 64bit registers, lets use them. (memory access is expensive)
  • a-la register-based VM.
  • 64bit words, wide enough.
  • so lets use fixnums everywhere. (less complications with legacy instructions)
  • Simple fixnum arithmetic (there are specialized libraries for hardcore math)
  • flat addressing, no segmenting, no complications.
  • Stack is a fundamental feature. Lots of research, stack-based VMs.
  • We will use stack, of course.

Concurrent model

but unlike JVM we will SHARE NOTHING (only what is read-only, like code segments).

a modern OS provides reasonable process isolation (nowadays kernel runs on its own CPU protection level) so, lets use it.

What prevents us form having some loadable kernel modules for "protected" parts?

Linux AMD64 EABI (calling conventions) they are using registers and stack. nice. Functions are ordinary shared -fpic object files (like static linking in Golang)

simplified FFI - just dlload and call. need no JNI mess. should be able to say '(posix:blah blah blah) '(alien:blah blah blah)

UTF-8 as it is in Plan9 and its derivatives (Plan9, Golang). Just do it.

Native AMD64 compiler. (see above) Must be able to say (compile (lambda (x) (....))) or (compile (defun blah (..) ..)) and, of course (disassemble foo)

All the optimizations (expansion, rewriting, inlining, lifting) on a Lisp level.

Align everything for 64bit addressing, to fit into cache lines. Memory is cheap.

No complications, just fill some templates.

Transform into loops in assembly code, CPU knows how to handle them.

Arrays later. (SIMD, etc.)

Runtime

Use OS, it is here. It sits in CPU caches, it distributes resources, it messes up with address translations, task switching, iterrupts, timers..

Most importantly - *OS does I/O*. Idiots who ignore this and re-impelent eveything inside a VMs are, well.. idiots. We will delegate to OS what is supposed to do.

People who are trying to ignore an OS are just wrong. OS is there, they like it or not, right in between their VMs and CPUs. To interfere with it, by trying to manage resources by themselves, form a "unprivileged user level process" is, well, look at Java.

Runtime is hard. This is why everyone just building layers of abstractions on top of existing runtimes (Clojure on top of JRE, Arc on mzscheme, Elixir on Erlang's VM, etc.)

But there are "small and nice" runtimes, designed as a thin layer on top of an OS.. The most beautiful example is "Plan9 from user space" (lib9, libutf, libbio) used in Golang runtime.

Another one is of nginx. It just works.

Nothing prevents us from dload and call libngix-core.so or link againt lib9.

Do not malloc on each cons (simplest pool-based allocation).

Let's read more about Lisp Machines first.

GC

No "general-purpose" memory-scanning GC used for imperative code (C++, Java, etc.)

We need a "simplified", "assisted" GC for pure-functional, growing-in-timespace (increasing addresses, memory fences, you know) immutable data.


With strict functional languages with immutable data (e.g. Erlang), it is relatively easy to implement automatic memory management (garbage collection), as there are no possible cycles in variables' references.

For example in Erlang, all arguments and variables are allocated on the heap, but references to them are additionally stored on the stack. After a function returns, references are still valid. Heap cleaning is done by incremental garbage collector.

Scheme, which has an ALGOL­like lexical scope system with dynamic variables and garbage collection, lacks a stack programming model and does not suffer from the limitations of stack­based languages.

Closures are expressed naturally in Scheme. The lambda form encloses the code and the free variables of its environment, persists within the program as long as it can possibly be accessed, and can be used as freely as any other Scheme expression.

conses

lambdas

hash-tables

ports

Last modified 6 years ago Last modified on Mar 4, 2014, 6:26:24 AM
Note: See TracWiki for help on using the wiki.