guile-vm-0.2

[Keisuke Nishida <kxn30 at po dot cwru dot edu>]

Hello,

I've implemented some fancy stuff like a command line compiler and
a Scheme level tracer for my VM:

  % cat fib.scm 
  (define (fib n)
    (if (<= n 2)
        1
        (+ (fib (- n 1)) (fib (- n 2)))))

  % guile-compile fib.scm 
  % cat fib.scc
  ;;; Compiled from fib.scm

  (let ((vm (make-vm)))
    (define (vm-exec code)
      (vm-run vm (make-program (make-bytecode code) #f)))
  (vm-exec #(#(0 #f 0 0 #()) #(%make-program #(#(1 #f 0 0 #()) #(%pushl:0 %loadc 2 le2 %br-if-not 9 %loadc 1 %return %pushl:0 %loadc 1 sub2 %push %loadt fib %call 1 %push %pushl:0 %loadc 2 sub2 %push %loadt fib %call 1 add2 %return)) %savet fib %load-unspecified %return)))
  )

  % guile
  guile> (use-modules (vm vm))
  guile> (use-modules (vm shell))
  guile> (load "fib.scc")
  guile> (vm-trace (make-vm) '(fib 5))
  | (#<program 0x807bbfc>)
  | (fib 5)
  | | (fib 4)
  | | | (fib 3)
  | | | | (fib 2)
  | | | | 1
  | | | | (fib 1)
  | | | | 1
  | | | 2
  | | | (fib 2)
  | | | 1
  | | 3
  | | (fib 3)
  | | | (fib 2)
  | | | 1
  | | | (fib 1)
  | | | 1
  | | 2
  | 5
  5

Instruction level tracing is also possible:

  guile> (vm-step (make-vm) '(fib 2))
  VM: Starting a program #<program 0x807b7fc>:
  0x807b7fc: %loadc #<program 0x807b7d4>
  0x807b804: %call 0
  0x807b7d4: %pushc 2
  0x807b7dc: %loadt (fib . #<program fib>)
  0x807b7e4: %tail-call 1
  0x807b2d4: %pushl:0
  0x807b2d8: %loadc 2
  0x807b2e0: le2
  0x807b2e4: %br-if-not -534852638
  0x807b2ec: %loadc 1
  0x807b2f4: %return
  0x807b80c: %halt
  VM: Program terminated with the return value: 1
  1

Or,

  guile> (vm-step (make-vm) '(fib 2) #t)
  VM: Starting a program #<program 0x8072b2c>:
  --------------------------------------------------
  PC = 0x8072b2c  SP = 0x80be548  FP = 0x80be560  AC = #f
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Local variables    = #()
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0)
  0x8072b2c: %loadc #<program 0x8072b04>
  --------------------------------------------------
  PC = 0x8072b34  SP = 0x80be548  FP = 0x80be560  AC = #<program 0x8072b04>
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Local variables    = #()
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0)
  0x8072b34: %call 0
  --------------------------------------------------
  PC = 0x8072b04  SP = 0x80be534  FP = 0x80be54c  AC = #<program 0x8072b04>
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Frame = [#<program 0x8072b04> 0x80be548 0x8072b3c]
  Local variables    = #()
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0 0 #<program 0x8072b04> 134997344 134997320 134687548)
  0x8072b04: %pushc 2
  --------------------------------------------------
  PC = 0x8072b0c  SP = 0x80be530  FP = 0x80be54c  AC = #<program 0x8072b04>
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Frame = [#<program 0x8072b04> 0x80be548 0x8072b3c]
  Local variables    = #()
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0 0 #<program 0x8072b04> 134997344 134997320 134687548 2)
  0x8072b0c: %loadt (fib . #<program fib>)
  --------------------------------------------------
  PC = 0x8072b14  SP = 0x80be530  FP = 0x80be54c  AC = #<program fib>
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Frame = [#<program 0x8072b04> 0x80be548 0x8072b3c]
  Local variables    = #()
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0 0 #<program 0x8072b04> 134997344 134997320 134687548 2)
  0x8072b14: %tail-call 1
  --------------------------------------------------
  PC = 0x807b2d4  SP = 0x80be51c  FP = 0x80be534  AC = #<program fib>
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Frame = [#<program fib> 0x80be548 0x8072b3c]
  Local variables    = #(2)
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0 0 #<program 0x8072b04> 134997344 134997320 134687548 2 0 #<program fib> 134997344 134997320 134687548)
  0x807b2d4: %pushl:0
  --------------------------------------------------
  PC = 0x807b2d8  SP = 0x80be518  FP = 0x80be534  AC = #<program fib>
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Frame = [#<program fib> 0x80be548 0x8072b3c]
  Local variables    = #(2)
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0 0 #<program 0x8072b04> 134997344 134997320 134687548 2 0 #<program fib> 134997344 134997320 134687548 2)
  0x807b2d8: %loadc 2
  --------------------------------------------------
  PC = 0x807b2e0  SP = 0x80be518  FP = 0x80be534  AC = 2
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Frame = [#<program fib> 0x80be548 0x8072b3c]
  Local variables    = #(2)
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0 0 #<program 0x8072b04> 134997344 134997320 134687548 2 0 #<program fib> 134997344 134997320 134687548 2)
  0x807b2e0: le2
  --------------------------------------------------
  PC = 0x807b2e4  SP = 0x80be51c  FP = 0x80be534  AC = #t
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Frame = [#<program fib> 0x80be548 0x8072b3c]
  Local variables    = #(2)
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0 0 #<program 0x8072b04> 134997344 134997320 134687548 2 0 #<program fib> 134997344 134997320 134687548)
  0x807b2e4: %br-if-not -534852638
  --------------------------------------------------
  PC = 0x807b2ec  SP = 0x80be51c  FP = 0x80be534  AC = #t
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Frame = [#<program fib> 0x80be548 0x8072b3c]
  Local variables    = #(2)
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0 0 #<program 0x8072b04> 134997344 134997320 134687548 2 0 #<program fib> 134997344 134997320 134687548)
  0x807b2ec: %loadc 1
  --------------------------------------------------
  PC = 0x807b2f4  SP = 0x80be51c  FP = 0x80be534  AC = 1
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Frame = [#<program fib> 0x80be548 0x8072b3c]
  Local variables    = #(2)
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0 0 #<program 0x8072b04> 134997344 134997320 134687548 2 0 #<program fib> 134997344 134997320 134687548)
  0x807b2f4: %return
  --------------------------------------------------
  PC = 0x8072b3c  SP = 0x80be548  FP = 0x80be560  AC = 1
  Frame = [#<program 0x8072b2c> 0x0 0x0]
  Local variables    = #()
  External variables = #f
  Stack = (0 #<program 0x8072b2c> #f 0 0)
  0x8072b3c: %halt
  VM: Program terminated with the return value: 1
  1

This is the current snapshot:

  http://home.cwru.edu/~kxn30/guile-vm-0.2.tar.gz

It's still buggy and far from complete.  I haven't implemented either
dynamic-wind or catch/throw yet.  I changed the VM so as not to use
stack segments; now it uses a single long stack as before.  I realized
that I'd better keep the VM as simple as possible.

I guess I don't have much time to work on this any more.  Is there
anyone who wants to continue developing this?  Or could I commit the
source code in the Guile's CVS repository?  Anyway, I'll continue
developing this when I have time.

One thing I want to improve is the compiler.  The current compiler
doesn't do any optimization yet.  Is there any good Scheme compiler
written in Scheme that does a certain optimization at the Scheme level?
Like:

  (+ x 1) -> (1+ x)
  ((lambda (x y) (+ x y)) a b) -> (+ a b)

After this is done, I can translate the Scheme code into bytecodes.
(But maybe I shouldn't work on this now...)

I use the module (ice-9 syncase) for macro expansion.  This is very
convenient.  It seems ice-9/psyntax.ss doesn't include the definition
of `cond', although it has a definition of `case'.  Could I add it?

Thanks,
Keisuke Nishida