LISP Workshop at ECOOP06

0-1083979983-1148048178=:4923 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE

On Fri, 19 May 2006, Hans H=FCbner posted:

"[..]

The Breakout group "Reclaim the Hardware Design Space!" on the 3rd European Lisp Workshop is about creating hardware that is suited to dynamic programming languages in general, and LISP in particular. We will be investigating current hardware technologies to find out what they have to offer for systems that are dynamic from the ground up.

The breakout group is meant to provide a meeting point for researchers and practitioners working on hardware implementation techniques for dynamic languages. [..]

[..]

Some of the topics of interest are:

• Implementation of LISP-friendly CPUs in hardware [..]"

Which features are thought of as being Lisp-friendly?

Beware of the warning in Chapter 2 on page 109 of Hennessy, John L and=20 Patterson, David A, "Computer Architecture: A Quantitative Approach",=20 second edition:

"Pitfall: Designing a "high-level" instruction set feature specifically=20 oriented to supporting a high-level language structure.

[..] [..] often the instructions are simply overkill-they are too general for=20 the most frequent case, resulting in unneeded work and a slower=20 instruction. [..] [..]"

Hennesy and Patterson do not consider reconfigurable logic and their prime concern is the raw performance of general-purpose processors. Even though the techniques they describe make sense, given this goal, reconfigurable logic makes it possible to reconsider their initial assumptions, maybe coming to different conclusions.

-Hans

anlamadim

I don't know about Lisp, but existing implementations on stock hardware of functional languages such as ML and Haskell tends to be penalized by latency on loads and unpredictable [dynamic] branches.

The same kind of support that helps speculative execution (non-trapping loads, predication, etc) is likely to help Lisp and friends. Loads which masks off part of the address (tag bits) can be help. There are lots that can be done for hardware assisted garbage collection. Finer control over the caches can help.

All of these are pretty mundane ideas however. I'd be curious for more radical ones.

Tommy

I think you're probably right. It is difficult to introduce instructions useful to Lisp in such a way that they:-

• Don't make the machine harder to design, or make it slower

• Don't fix the idea of how certain lisp idioms should be implemented

But still I'd be interested to see what people come up with. The pitfall H & P describe is that of designing an instruction set in a high-level manner, which is not the subject of the discussion. It may be possible to make a microprocessor more lisp-friendly by doing a lot less than this.

I'm not sure it's really necessary though, modern lisp compilers like CMUCL and SBCL produce fast code. Those performance faults that there are are mainly due to their weaknesses as compiler/VMs, rather than any fundamental problem converting lisp into machine language.

Hans Hübner wrote:

I think instead of implementing the SECD machine, like described at

(BTW: in Internet Explorer there are no scrollbars), with bytecodes and a compile step, it would be more interesting to implement an interpreter within a FPGA, like I've started to describe at

But using some ideas of LispKit is a good idea. First I'll implement it in software and then translating it to VHDL. Below is a first implementation of an interpreter for a modified version of LispKit lisp. Currently it is non-lazy (I think for the first version of the FPGA implementation this is easier, too). I've started with the description of the interpreter from the the book "Functional Programming" by Peter Henderson, page 120/121, but modified the syntax a bit to make it easier for people who know alreay Common Lisp:

- let and letrec uses a syntax more like Common Lisp

- numbers needs not to be quoted

And expressions are evaluated like when entered in the REPL, the expression needs not to return a callable function.

The next step will be to implement a more hardware oriented simulation of the interpreter (with my own memory management and GC, e.g. like implemented in the original Pascal implementation of the SECD machine at ftp://ftp.comlab.ox.ac.uk/pub/Packages/LispKit/ ).

#+:Lispworks (editor:setup-indent "letrec" 2 0 2)

(defun test () (loop for (result expression) in '(;; some simple tests (nil nil) (1 1) (3 (+ 1 2)) (9 (let ((square (lambda (x) (* x x)))) (square 3)))

;; creating a list ((0 1 2 3 4 5) (letrec ((i (lambda (n) (cons n (if (< n 5) (i (+ n 1))))))) (i 0)))

;; creating primes ((2 3 5 7 11 13 17 19 23 29 31 37 41 43 47) (letrec ((reverse (lambda (l) (letrec ((reverse-impl (lambda (l acc) (if (atom l) acc (reverse-impl (cdr l) (cons (car l) acc)))))) (reverse-impl l)))) (is-prime (lambda (p l) (let ((divisor (car l))) (if divisor (if (= (rem p divisor) 0) nil (is-prime p (cdr l))) p)))) (create-primes (lambda (n) (letrec ((primes-impl (lambda (test l) (let ((l (if (is-prime test l) (cons test l) l))) (if (< test n) (primes-impl (+ 1 test) l) l))))) (reverse (primes-impl 2 '())))))) (create-primes 50)))) do (assert (equalp result (secd expression)))))

(defun secd (expression) (let ((n '()) (v '())) (secd-eval expression n v)))

(defun secd-eval (e n v) (when e (let ((unary-functions '(car cdr atom)) (binary-functions '(cons eql + - * / rem < >= =))) (cond ((numberp e) e) ((atom e) (secd-assoc e n v)) ((member (car e) unary-functions) (funcall (car e) (secd-eval (cadr e) n v))) ((member (car e) binary-functions) (funcall (car e) (secd-eval (cadr e) n v) (secd-eval (caddr e) n v))) ((eql (car e) 'quote) (cadr e)) ((eql (car e) 'if) (let ((e1 (cadr e)) (e2 (caddr e)) (e3 (cadddr e))) (secd-eval (if (secd-eval e1 n v) e2 e3) n v))) ((eql (car e) 'lambda) (cons (cons (cadr e) (caddr e)) (cons n v))) ((eql (car e) 'let) (let ((y (secd-vars (cadr e))) (z (secd-eval-list (secd-exprs (cadr e)) n v))) (secd-eval (caddr e) (cons y n) (cons z v)))) ((eql (car e) 'letrec) (let* ((y (secd-vars (cadr e))) (v2 (cons nil v)) (z (secd-eval-list (secd-exprs (cadr e)) (cons y n) v2))) (secd-eval (caddr e) (cons y n) (rplaca v2 z)))) (t (let ((c (secd-eval (car e) n v)) (z (secd-eval-list (cdr e) n v))) (secd-eval (cdar c) (cons (caar c) (cadr c)) (cons z (cddr c)))))))))

(defun secd-vars (d) (when d (cons (car (car d)) (secd-vars (cdr d)))))

(defun secd-exprs (d) (when d (cons (car (cdr (car d))) (secd-exprs (cdr d)))))

(defun secd-assoc (x n v) (if n (if (member x (car n)) (secd-locate x (car n) (car v)) (secd-assoc x (cdr n) (cdr v))) (error "variable not found: ~a" x)))

(defun secd-locate (x l m) (if (eql x (car l)) (car m) (secd-locate x (cdr l) (cdr m))))

(defun secd-eval-list (l n v) (when l (cons (secd-eval (car l) n v) (secd-eval-list (cdr l) n v))))

--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

I think it depends a lot on what model you have in mind for the implementation - are you trying to make it fast for a bytecode interpreter, jit or compiled lisp? And once you pick a flavour (or several) it makes sense to see that other languages that get processed in a similar way (scheme, java, python, perl, ...) get a speed-up too.

For example, you can easily spend way too much time on modern machine in doing slow string hashes and string compares for symbol lookup (ok, not just symbol lookup). You can also speed up dynamic table lookups.

And of course, then there are tagged pointers... Which I think can be made beneficial and OoO friendly and C-neutral and not dertimental to performace in any way. Which of course means you have to treat them in a totaly RISC-y, the code knows what its doing, and not do things like harware tag checks on load / store / jump.

--
	Sander

+++ Out of cheese error +++