You are viewing lukego

Luke's Weblog - CIRCL [entries|archive|friends|userinfo]
Luke Gorrie

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

CIRCL [Oct. 23rd, 2008|12:52 am]
Previous Entry Add to Memories Share Next Entry
[Tags|, ]

On the way to bed I started pondering a virtual machine that executes SEXPs directly. Suppose you programmed it with a debugger that was able to inspect and modify its own structure. Then you'd have the interesting situation of the program source code and the executing machine code being one and the same thing. Do you know a system like this?
;;; circl.lisp -- a lisp for self-modifying programs
;;; Written in September 2008 by Luke Gorrie <lukego@gmail.com>

(declaim (optimize (debug 3)))

;;; This is a toy-Lisp dialect in which the running program is itself
;;; a first-class object. The builtin variable SELF evaluates to the
;;; program currently running. This allows the program to inspect and
;;; modify itself during execution. If you had a little structure
;;; editor you could almost say that the source code and the running
;;; program were one and the same thing.
;;;
;;; Lacks almost but not quite every feature of Lisp. See below for an
;;; example.

(defvar *program* nil "The currently executing program.")

(defun @circl (exp)
  (let ((*program* exp))
    (@eval *program*)))

(defun @eval (exp)
  (cond ;; SELF returns the program itself
        ((eq exp 'SELF) *program*)
        ;; Other symbols, numbers, strings, etc are self-evaluating
	((atom exp) exp)
        ;; (WHILE CONDITION BODY...)
	((eq (first exp) 'WHILE)
	 (loop while (@eval (second exp))
	       do (@begin (rest exp))))
        ;; Function application uses the host Lisp's functions
	((consp exp)
	 (apply (@eval (first exp)) (mapcar #'@eval (rest exp))))))

(defun @begin (exp-list)
  (loop for exp in exp-list
        for value = (@eval exp)
        finally (return value)))

;; Here's an example program that terminates by using SELF to replace
;; its own loop condition during execution.

#|
CL-USER>
  (@circl '(while T
	     ;; show original program
	     (print ORIG) (print self)
	     ;; Now replace the T above with NIL to terminate the loop
	     (rplaca (cdr self) nil)
	     ;; show hacked program
	     (print MODIFIED) (print self)))
#|
LinkReply

Comments:
From: (Anonymous)
2008-10-23 10:08 am (UTC)

tsk tsk

(Link)

You're modifying a (CL) constant, Luke. Bad boy, no cookie.

Here's a fix:
(@circl (list* 'while t 
               '((print ORIG) (print self)
                 (rplaca (cdr self) nil)
                 (print MODIFIED) (print self))))

Have a nice day,

Christophe

(You may now accuse me of missing the point)
[User Picture]From: lukego
2008-10-23 03:32 pm (UTC)

Re: tsk tsk

(Link)

Good point! You know I nearly thought I'd get away with writing the whole program like this:
(defvar *self* nil "The currently executing program.")

(defun @circl2 (exp)
  (let ((*self* exp)) (eval exp)))

(circl2 '(loop while T do (setf (car *self*) 'DONE)))
but god knows what happens if you go (SETF (CAR ..))'ing data structures that EVAL is using. So I was trying to be good :-) I suppose that a COPY-TREE would get me out of trouble too.

Edited at 2008-10-23 03:39 pm (UTC)
[User Picture]From: yosemitesam
2008-10-23 01:14 pm (UTC)

(Link)

It reminds me of the reflective interpreters that Friedman has written some good papers about. There are several good ones here.

http://library.readscheme.org/page11.html

The Friedman & Jefferson paper is one of the most enlightening (to me anyways) because it is very simple, and potentially very powerful.
From: (Anonymous)
2008-10-23 02:13 pm (UTC)

NTHCDR FTW!

(Link)

Shouldn't that be:
(loop while (@eval (second exp))
      do (@begin (nthcdr 2 exp)))

From: (Anonymous)
2008-10-23 03:43 pm (UTC)

3-Lisp

(Link)

Enough said... ;)

Pascal Costanza

[User Picture]From: lukego
2008-10-23 03:50 pm (UTC)

Re: 3-Lisp

(Link)

Oh no! I hadn't considered that this line of thinking could bring you and I into agreement, I'll have to be more careful in the future :-)

I'll check 3-Lisp out properly, thanks!
[User Picture]From: darius
2008-10-23 05:58 pm (UTC)

(Link)

You'll surely want to check out Guy Steele's Scheme chip sometime -- maybe after working through the TECS hardware chapters.

Smalltalk gave me pretty much the same line of thought about a VM that executes s-expressions. It was one of the ideas in the back of my mind while writing http://github.com/darius/squerm -- which interprets s-expressions, with an explicit control state instead of host-language stack, but I haven't yet exposed the control state to the user. So the 'squ' part of the name, from Squeak, is more hope than reality. :)

A system I did make with fully reified state is Hypercode. (You need Hypercard to run it or even view the source, though, and that's a 'classic' program (OS 9).)
From: (Anonymous)
2008-10-23 09:23 pm (UTC)

REFAL

(Link)

Have you ever seen REFAL (REcursive Functional Algorithmic Language)? It purported to be the AI language of Russia in the '80s.

Program and results were one and the same. The VM was a window which displayed the text of the program. If the beginning of the window contained an executable statement, it executed causing the entire text to be replaced and displayed in the window. When the window contained something non-executable the program was done and became the result of the computation.

http://en.wikipedia.org/wiki/Refal

jay

From: (Anonymous)
2008-10-24 07:11 am (UTC)

Lisp Machine

(Link)

The Lisp Machine (http://en.wikipedia.org/wiki/Lisp_machine) developed at MIT did run SEXPs natively; but, it was a real computer instead of a virtual machine. Several vendors went on to commercialize the technology. All of them have left that business.

Recently, however, Mr. Bill blogged on getting an OpenGenera (http://weblog.mrbill.net/archives/2008/05/18/finally-got-open-genera-running/) port up and running in a VMWare image! Is that close enough?
[User Picture]From: lukego
2008-10-25 06:44 pm (UTC)

(Link)

Incidentally, can you write a program like this in Clojure? I'd have tried it but didn't really know how to express that RPLACA. So I downloaded ClozureCL and used that instead.

I'm *very* impressed with the SLIME support in both ClozureCL and Clojure by the way.