From: =?iso-8859-1?B?SGFucyBI/GJuZXI=?=
Subject: LISP Workshop at ECOOP06
Date: 
Message-ID: <1148031054.973445.183860@g10g2000cwb.googlegroups.com>
Hi,

on the upcoming ECOOP conference in Nantes, France, the 3rd European
LISP Workshop will be held.  Part of that workshop is a breakout group
on hardware for LISP systems:

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. To participate, you should know something about the
implementation of dynamic languages, about hardware, or both. You are
not required to actually have created a LISP machine yourself, but you
should be aware of some of the associated issues in order to take part
in the discussion.

Some of the topics of interest are:

    * Implementation of LISP-friendly CPUs in hardware
    * Hardware assisted garbage collection
    * Self-Synthesis and Hardware/Software Co-Design
    * LISP based ASLs for hardware description and synthesis
    * Techniques for CPU implementation on FPGAs
    * Reengineering ancient CPUs in software or hardware

In the breakout group, time will be provided for researchers to
demonstrate their achivements and position. If you have something to
present, please let us know and we will provide you with presentation
time. You may also publish information on this web site in order to let
participants get some idea of what you are working on in advance.

We hope that the breakout group will help in advancing dynamic hardware
and provide for a place for researchers and practitioners to work
together.

3rd European LISP Workshop: http://lisp-ecoop.bknr.net/
LISP Hardware breakout group: http://vaxbusters.org/workshop/

Regards,
Hans

From: Colin Paul Gloster
Subject: Re: LISP Workshop at ECOOP06
Date: 
Message-ID: <20060519160614.L4923@docenti.ing.unipi.it>
  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

--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. [..]

[..]"
--0-1083979983-1148048178=:4923--
From: =?iso-8859-1?B?SGFucyBI/GJuZXI=?=
Subject: Re: LISP Workshop at ECOOP06
Date: 
Message-ID: <1148102042.583013.309730@i40g2000cwc.googlegroups.com>
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
From: ·········@gmail.com
Subject: Re: LISP Workshop at ECOOP06
Date: 
Message-ID: <1148135835.523749.197890@i40g2000cwc.googlegroups.com>
anlamadim
From: Tommy Thorn
Subject: Re: LISP Workshop at ECOOP06
Date: 
Message-ID: <4470ED0A.5030204@nowhere.void>
[Following up to a 3-way cross post is likely to hurt my karma, but ...]

Colin Paul Gloster wrote:
> Which features are thought of as being Lisp-friendly?
> 
> Beware of the warning in Chapter 2 on page 109 of Hennessy, John L and 
> Patterson, David A, "Computer Architecture: A Quantitative Approach", 
> second edition:
> 
> "Pitfall: Designing a "high-level" instruction set feature specifically 
> oriented to supporting a high-level language structure.

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
From: Rob Thorpe
Subject: Re: LISP Workshop at ECOOP06
Date: 
Message-ID: <1148314233.566216.87060@i40g2000cwc.googlegroups.com>
Colin Paul Gloster wrote:
> On Fri, 19 May 2006, Hans Hübner posted:
> 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
> Patterson, David A, "Computer Architecture: A Quantitative Approach",
> second edition:
>
> "Pitfall: Designing a "high-level" instruction set feature specifically
> oriented to supporting a high-level language structure.
>
> [..]
>
> [..] often the instructions are simply overkill-they are too general for
> the most frequent case, resulting in unneeded work and a slower
> instruction. [..]

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.
From: Sander Vesik
Subject: Re: LISP Workshop at ECOOP06
Date: 
Message-ID: <1155172472.123255@haldjas.folklore.ee>
In comp.arch Rob Thorpe <·············@antenova.com> wrote:
> 
> 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 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 +++
From: Frank Buss
Subject: Re: LISP Workshop at ECOOP06
Date: 
Message-ID: <uo2penwi0j1v.1jxjzvyg45i2x.dlg@40tude.net>
Hans H�bner wrote:

> LISP Hardware breakout group: http://vaxbusters.org/workshop/

I think instead of implementing the SECD machine, like described at
http://vaxbusters.org/workshop/secd.xml (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 http://www.frank-buss.de/lispcpu/

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, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Andy Glew
Subject: Re: LISP Workshop at ECOOP06
Date: 
Message-ID: <peypk68a5ba0.fsf@PXPL8591.amr.corp.intel.com>
Frank Buss <··@frank-buss.de> writes:

> Hans H�bner wrote:
> 
> > LISP Hardware breakout group: http://vaxbusters.org/workshop/
> 
> I think instead of implementing the SECD machine, like described at
> http://vaxbusters.org/workshop/secd.xml (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 http://www.frank-buss.de/lispcpu/

I go the opposite way:

Start of with a conventional machine - probably a RISC - and add
special instruction set or hardware support if the performance is
unacceptable, or if dynamic languages have special atomicity of
correctness requirements.

For example, list operations when the same data structures are being
manipulated by multiple threads of control, without locking.

Plus the usual GC read barrier, etc. See Azul's latest.

Security - if your LISP code is not assumed to be all at the same
privilege level.

---

An interpreter within an FPGA might just be a ROM containing code for
a RISC core.  You have to prove why you should any extra hardware.

---

Happy am I see to LISP hardware being talked about again, even if you
are rehashing the old ideas.  Soon we can move on to make real progress!
From: Frank Buss
Subject: Re: LISP Workshop at ECOOP06
Date: 
Message-ID: <zoss4trp6pdh$.1so9rhk4uz397.dlg@40tude.net>
Andy Glew wrote:

> Start of with a conventional machine - probably a RISC - and add
> special instruction set or hardware support if the performance is
> unacceptable, or if dynamic languages have special atomicity of
> correctness requirements.

But why using special instructions then at all? I hope that it would be
faster to execute high-level instructions, like "lambda", in hardware
instead of compiling it to RISC operations first, even if there are some
special RISC instructions for Lisp programs. But my main motivation is not
speed, but the idea to implement an interpreter in hardware.

> Plus the usual GC read barrier, etc. See Azul's latest.

Do you mean this? 

http://db.usenix.org/events/vee05/full_papers/p46-click.pdf

Another interesting concept is Metronone, which gurantess hard real time
constraints:

http://www.research.ibm.com/metronome/

Maybe I'll try something like this, after I have implemented a simple
stop-the-world GC.

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