Archive for the ‘Open Source’ Category

« Older Entries

Loop macros

Friday, June 4th, 2010

I have released the latest version of Church-State here:
http://subvert-the-dominant-paradigm.net/~jewel/church/church-alpha-4.tar.gz

You can also get the source code via mercurial:

hg clone http://subvert-the-dominant-paradigm.net/repos/bootstrap

or browse it.

In the previous version of Church loop constructs were expanded in the Church compiler directly to the State “tagbody” form. I have removed this code and implemented it as a Church macro which expands to a new Church “tagbody” form.

The aim behind this is to make it easier to do optimization and flow analysis on Church code in the future.

Posted in Church, Open Source, Programming, State | No Comments »

User extensible parsing

Monday, March 29th, 2010

I have been experimenting with user-extensible parsers in Church, even though I don’t have a use for them yet.

I added a new language construct called “extend-grammar”, ie:


extend-grammar ometa testg {
test-rule = "test" ws+ cname:a -> << 42 >>
}

This test-rule will match the string “test”, followed by a name. The rule will ignore its input and return the value 42.

This grammar is processed during parse time, converted to church code and dynamically compiled and linked into the running process.

At present this happens after the whole file is parsed, so it’s currently not possible to add a new grammar rule and use it in the same source file.

To activate the rule I added another construct, “eval-when”, ie:


eval-when compile load
      church-add-parser-extension 'test-rule

What this does is to execute this code when this file is compiled (load doesn’t work yet).

In this example we add ‘test-rule to the list of ometa functions to be called by a special new grammar rule called ‘user-form.

The new version of ‘user-form is compiled and linked into the process, immediately making it available to the parser.

For this test case I then load the following file:


dotest
        print "in dotest"
        print (test notanumber)

which prints 42 because the parser has intercepted what would normally be a method call.

Posted in Church, Open Source, Programming | No Comments »

Rude repl

Sunday, March 14th, 2010

I have added eval and a repl (read eval print loop) to Church.

> + 3 4
7
> length "foobar"
6
> eval "* 19 3"
57
> load "church/test/hello.church"
true
> (main)
"hello"
true

Up to now I have only been using Church as a command-line compiler which produces executable files. Yet I have always preferred interactive language environments (lisp, smalltalk, python etc) to stop-compile-run languages.

All the machinery for writing a repl has been in Church for a while, including

  • Church parser available as a library
  • Church compiler available at runtime
  • Machine code generator and dynamic linker available at runtime
  • The ability to modify the dispatch table at runtime

This makes the repl easy to implement:

repl
        loop
                do
                        rstr = (read-line)
                        if (null? rstr)
                                return-from repl nil
                        else
                                print (eval rstr)

Eval is a little bit more messy because the compiler is designed to compile a whole method at a time and doesn’t know what to do with variables that are not either a global or local variable.

To implement eval I wrapped the eval string in a lambda that I return from a method which gets run after compilation.

set-eval-compiled-function
   eval-compiled-function = (fn -- eval_str)

This works for certain language expressions, but does not presently provide the ability to assign to “repl” variables.

Another drawback is that multiline statements are currently not possible (unlike python and lisp).

In the future I hope to experiment with a SLIME-like extension to emacs which communicates to Church across a socket, allowing interactive evaluation and compilation of source code from within the editor.

Posted in Church, Open Source, Programming, State | No Comments »

jonesforth64

Monday, July 20th, 2009

I have ported jonesforth to 64-bit x86 code.

jonesforth is a tutorial-style implementation of forth which explains in detail how the compiler and runtime is implemented. Porting the code to a slightly different assembly language helped me to think carefully about what each primitive does and about how they are used in the runtime code.

As noted in the jonesforth comments, the original advantage of using direct-threaded code on a 16-bit machine is that calling each word can be encoded in two bytes instead of three. That’s a savings of 33%. On 32-bit x86, it’s four bytes versus five, saving 20%. In my 64-bit implementation I chose to extend the 4-byte addresses to 8-byte words. This actually results in wasting space rather than saving it because on x86-64 calls and branches are usually encoded with a 5-byte instruction using relative displacement.

The port was fairly straightforward, I mostly just replaced 32-bit registers (eax, esp, esi etc) with the 64-bit equivalents (rax, rsp, rsi etc) and changed every reference to the word-size from 4 to 8.

The biggest difference is that syscalls use different registers on 64-bit linux and these registers can be clobbered during the call.

You can get the code from the mercurial repository:

hg clone http://subvert-the-dominant-paradigm.net/repos/jonesforth64/

To compile it:


gcc -m64 -nostdlib -static -Wl,-Ttext,0 -Wl,--build-id=none -o jonesforth64 jonesforth64.S

To run it:


cat jonesforth64.f - | ./jonesforth64
JONESFORTH VERSION 45
6393 CELLS REMAINING
OK
1 2 3 4
.S
4 3 2 1
ROT
.S
3 2 4 1

I’ve tested most of the code in the .f file, but I haven’t yet implemented C strings, file-io or the built-in assembler.

I’ve tried to keep the comments intact, but haven’t updated them to reflect different word sizes or registers etc.

Posted in Open Source, Programming, forth | 1 Comment »

Macros and dynamic compilation

Tuesday, February 17th, 2009

I have released the next version of my Church-State system at:

http://subvert-the-dominant-paradigm.net/~jewel/church/church-alpha-1.tar.gz.

This release adds proper Church macros and dynamic compilation to the system. In this example, a macro for moving an immediate value to a register


macro MOVLir imm reg
        <<
                _Or_L 0xb8 (_r4 \reg) \imm

>>

you can see quoted code wrapped in angular brackets and backslashes used to unquote values that must be inserted into the template.

The macro syntax is not final (like most of Church's syntax) and it should look cleaner as it matures.

To handle macros like these the system is now capable of taking Church source code parsed out of the macro body, compiling it to low-level State code and then compiling and linking the resulting machine code into the running image.

This involves resolving low level symbols (I use dlsym) and modifying the Church dispatch tables and macro rewriters to use the new macros. I also have to run an initialization function which sets up the "code vector" with constant values (interned symbols etc).

Now that I have dynamic compilation working, it should be fairly easy to add a REPL to the system.

Performance

As part of this release I have also disabled a lot of optimizations that I had worked on before. These include inline caches for method dispatch and slot access. The reason I have disabled these optimizations is that they cost too much in terms of space compared to the benefit they provide in improved speed.

I'm now pursuing a new approach which uses "class wrappers" marked with random seeds. The idea is that these seeds can be used to hash into lookup tables which memoize the effective method for dispatch. I hope to be able to incorporate these ideas plus others from contemporary implementations (of javascript vms etc) to make the system substantially faster.

Posted in Church, Open Source, State | No Comments »

Church release

Friday, February 6th, 2009

I’m proud to have reached the stage where my Church-State system can compile itself (ie the compiler is bootstrapped).

I have made the first alpha release available at:

http://subvert-the-dominant-paradigm.net/~jewel/church/church-alpha-0.tar.gz

To try it out you’ll need a 32-bit x86 linux system with “ld” installed. (Usually ld will be installed if you’ve installed something like gcc).

There are two simple test files mentioned in the README and there are also instructions for bootstrapping the system.

One thing missing from the release is a compiler that compiles the output from the OMeta parser generator to Church files. That means it’s not possible to change the grammars just yet.

Another incomplete feature is that Church and State macros are hard-coded into the compiler. If you look at church-pass1.church and state-pass1.church you’ll see the various hard-coded macros (some of which are quite complex). To be able to include these macros in the source files where they are used I need to be able to dynamically compile and load church code. I’ve completed the first step of this process, see state-dynamic.church and church-test-dynamic-alloc.church for working code that can compile a church file down to native code, allocate memory for it and link it into the running image.

Once I have Church macros working, I plan to rewrite a lot of assembler-i386.church to use macros instead of functions for emitting machine instructions. I think that this will dramatically improve compilation times. While preparing for this release I did a lot of work on performance, even removing array bounds checking and some other safety checks to make it faster. Currently the system bootstraps in 90 seconds on my laptop, but my goal is to be 2 or 3 times as fast.

Posted in Church, Open Source, Programming, State | No Comments »

Improving dispatch performance in Church

Friday, October 31st, 2008

Over the last week I have been working on performance optimizations for Church code. My basic test case is to run the OMeta parser (implemented in Church) on the “base.church” file in the Church runtime library. This file implements most of the Church runtime code. Parsing this file with the Common Lisp implementation of OMeta takes 0.5 seconds on my laptop. Initial runs of the Church code took well over a minute.

The first major change was to cache symbol lookups. Previously I was storing all symbol objects in an a-list (a linked list) and every time a symbol was used the table would be searched linearly using string comparisons. To avoid this lookup I modified the State compiler to take a (load-constant-value <raw-value>) form. When the state compiler compiles this form it creates a cell in the data segment from which to load a constant value. It also generates some initialization code which will call out to the runtime to initialize the constant.

By collecting all these initialization sequences and running them on startup we can intern all the symbols used by the program before it starts running. Each symbol reference thereafter is a simple memory load.

Using these cached symbols makes class lookup a lot easier too. Previously I stored all classes in a table keyed by symbol and searched it linearly when looking up classes. In the new implementation I store class objects in a “class” slot associated with the symbol representing the class’s name.

Similarly, the dispatch table was stored as a global list and searched first by symbol (selector) and then compared according to argument types. I moved the dispatch rules to the symbol objects, making the search much shorter.

These changes brought the instruction execution count down to about 40 billion instructions for Church (versus about 650 million for Lisp).

Further optimizations involved removing all cons’ing from the dynamic dispatch routines, inlining as many of those calls as possible to avoid function call overhead and rewriting recursive routines as tagbody loops.

I also reordered the tests in the “class-of” code to check the most common cases first.

All these optimizations brought the time down to about 4.5 seconds and the execution count to 13 billion. This is still about a factor of 10 slower than the lisp implementation. Eventually I hope to bring it to about a factor of 2, possible future optimizations are inline-caches for method lookup and optimized cons and closure allocation. Eventually I might also look at more sophisticated approaches, such as type inference, an optimizing compiler pass and runtime profiling.

To profile the code I tried two tools, Intel’s VTune and the callgrind module of valgrind. VTune was quite disappointing, besides having to paste serial numbers into an obscure installation utility (which failed the first few times) the download was 500 megabytes. After installation the sampling driver failed to work but I managed to run the call tracing module.

valgrind provides similar information to VTune, but the kcachegrind visualizer is much better, the call graph is very easy to work with and is also possible to see hot loops at the assembly level.

Posted in Church, Open Source, Programming, State | 1 Comment »

jolt-burg

Friday, June 20th, 2008

In April I posted to the fonc mailing list about my port of Ian Piumarta’s “jolt-burg”.

This is a combination of a simple lisp-like language (“jolt”) and a compiler from a tree of “instruction” objects to native machine code.

My implementation was in Common Lisp and my compiler targeted relocatable ELF object files.

From my post:

Currently I have a compiler that can read sexp input, eg:

(define |main| (lambda ()
        ((call-c |dlsym| 0 "puts") "hello, dynamic world!")))

and then compile it down to a tree of blocks and instruction objects (see instruction.lisp or Instruction.st) 

BLOCK(--- NIL ---)
| | 0(--- VOID BLOCK --- 369
| | | | | 0(+++ REG CALLI4 ---
| | | | | | 0(+++ REG CNSTP4 --- reloc ---)
| | | | | | 0(+++ REG CNSTI4 --- 0)
| | | | | | 0(+++ REG CNSTP4 --- reloc ---))
| | | | | 0(+++ REG CNSTP4 --- reloc ---))
| | 0(--- VOID BLOCK --- 369
| | | | | 0(+++ REG CALLI4 EBX
| | | | | | 0(+++ REG CNSTP4 EBX reloc ---)
| | | | | | 0(+++ REG CNSTI4 EAX 0)
| | | | | | 0(+++ REG CNSTP4 ECX reloc ---))
| | | | | 0(+++ REG CNSTP4 EAX reloc ---))                       

This tree is processed by the burg compiler to emit x86 machine code. (in the diagram we see registers being assigned to the tree nodes)

The last stage is when I collect the machine code generated by the burg compiler and combine it with data and relocation entries to generate an ELF object file.

I can then pass this to the unix linker (ld) to produce an executable.

ld --dynamic-linker=/lib/ld-linux.so.2 state/start.o state/hello.state.o -ldl  -lc -o myhello

Here you can see the disassembled elf object file with relocation entries for the "dlsym" symbol and the "puts" and "hello world" strings.

objdump -d state/hello.state.o -r

Disassembly of section .text:

00000000 
:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   53                      push   %ebx
   4:   83 ec 14                sub    $0x14,%esp
   7:   bb 00 00 00 00          mov    $0x0,%ebx
                        8: R_386_32     dlsym
   c:   b8 00 00 00 00          mov    $0x0,%eax
  11:   b9 00 00 00 00          mov    $0x0,%ecx
                        12: R_386_32    _data_286
  16:   89 4c 24 04             mov    %ecx,0x4(%esp)
  1a:   89 04 24                mov    %eax,(%esp)
  1d:   ff d3                   call   *%ebx
  1f:   89 c3                   mov    %eax,%ebx
  21:   b8 00 00 00 00          mov    $0x0,%eax
                        22: R_386_32    _data_287
  26:   89 04 24                mov    %eax,(%esp)
  29:   ff d3                   call   *%ebx
  2b:   89 c0                   mov    %eax,%eax
  2d:   89 c0                   mov    %eax,%eax
  2f:   83 c4 14                add    $0x14,%esp
  32:   5b                      pop    %ebx
  33:   5d                      pop    %ebp
  34:   c3                      ret

You can view the code at:

http://subvert-the-dominant-paradigm.net/repos/hgwebdir.cgi/bootstrap/

(see the burg directory)

(click files to see the files, or run ‘hg clone <url>’ to get a local copy)

Posted in Lisp, Open Source, Programming | No Comments »

Debian netboot install over PXE

Tuesday, May 20th, 2008

Installing Debian on an ultraportable machine (no FDD, no CD) is fairly easy, but sometimes I get stuck.

To setup the PXE host I installed dhcp3-server and tftpd-hpa.

I used the netboot images at

http://ftp.nl.debian.org/debian/dists/lenny/main/installer-amd64/current/images/netboot/

copying them to /var/lib/tftpboot and unpacking netboot.tar.gz.

I configured /etc/dhcp3/dhcpd.conf for the target machine, using its MAC address. Don’t forget the ‘next-server’ option.


subnet 192.168.2.0 netmask 255.255.255.0 {

}

host cmalu {
 hardware ethernet xa:xa:xa:xa:xa:xa ;
 filename "pxelinux.0";
 next-server 192.168.2.1;
 server-name "name";
 fixed-address 192.168.2.99;
 option routers 192.168.2.1;
 option domain-name-servers 192.168.2.1;
}

I then start tftpd like this:


 /usr/sbin/in.tftpd -v -v -v -l -s /var/lib/tftpboot

it logs to /var/log/daemon.log

The debian installer was looking for pxelinux.cfg/01-xa:xa:xa:xa:xa:xa so I copied pxelinux.cfg/default to that file.

Once the installer starts things are fairly simple.

Posted in Open Source | No Comments »

OMeta in Common Lisp

Monday, November 26th, 2007

OMeta is a parsing engine by Ian Piumarta and Alessandro Warth. It combines PEG rules with a syntax for naming matched components and executable actions that can refer to the named parts. A simple OMeta rule looks like this:

ostring ::=     $' (~$' <ochar>)*:s $' => [(coerce  s 'string)]

Here a string is matched starting with a single quote, followed by any character that is not a single quote and ending with a single quote.

The action for this rule turns the list of characters matched into a lisp string.

I created an OMeta implementation in Common Lisp by bootstrapping from the squeak implementation of OMeta.

To do this I first modified the OMeta parser to be able to read lisp forms in the action bodies. Next I modified the OMeta compiler to produce lisp forms instead of smalltalk code.

Using these generated forms in combination with hand-coded primitive rules (ometa-prim.lisp) I was able to use two new grammars ometa-parser.g and ometa-compiler.g to fully bootstrap the system.

My code is available from this mercurial repository:


hg clone http://subvert-the-dominant-paradigm.net/repos/hgwebdir.cgi/ometa/

To run it:


(load "load.lisp")

Then you can parse a grammar file into its AST:


(parser-grammar-file "grammar.g")

To create an executable parser, first declare a subclass of ometa:


(defclass dnaparser (ometa) ())

Next write the production rules in a grammar file:


base ::=
$A | $T | $G | $C^L
dsequence ::=
<base>*:s => [ (coerce s 'string) ]^L

and generate the parser from the grammar:


(generate-parser 'dnaparser "example.g" "example.lisp")

This reads the grammar file “example.g” and produces lisp defmethods for the class ‘dnaparser’. These lisp forms are written to “example.lisp”.

After loading the parser, you can run the productions like this:


CL-USER> (let ((*ometa-class-name* 'dnaparser))
(run-production 'dsequence (coerce "GGCCGGGC" 'list)))
"GGCCGGGC"

As an alternative to generate-parser, you can use install-grammar to load the rules without generating an intermediate file.

The squeak implementation of OMeta supports several extensions that I have not implemented:

- Memoization of previous parse results
- Support for left-recursive rules
- Ability to apply a rule in the super class
- Support for rules that call out to a “foreign” parser during the parse
- An optimizer to remove redundant AND and OR forms produced by the parser

Posted in Lisp, Open Source, Programming | 2 Comments »

« Older Entries