Re: A "Lisp Machine" and cons cells

From: Pascal Bourguignon (spam_at_mouse-potato.com)
Date: 08/24/04 

Date: 24 Aug 2004 19:20:39 +0200

solo88@truevine.net (neo88) writes:

> > What is "machine form"? What is "machine form" for a cons cell? Do
> > you mean you'd rather have wetware inside your computer than hardware?
>
> By Machine form I mean binary. The 1's and 0's that the Lisp code
> eventually gets translated into.
>
> > How is a cons cell reprensented in your brain?
> > How is a cons cell reprensented in your mind?
>
> What does that have to do with anything? If you are trying to say that
> our minds store symbols, I agree with you, our minds offload symbols
> into the environment, as well as keeping and manipulating millions
> more in the mind.
   
You'd better think again about it. And don't cut out too much:

> 1) Cons cells - Since I know that cons cells are the lowest form of Lisp
> that is actually what we can call Lisp, I was wondering if it was possible
> to stop the translation of cons cells into machine form. Why would I want
> to do this?

    +-----------+ +--------------+
    | cons cell |<---------(translation)----------->| machine form |
    +-----------+ +--------------+

So, you want to avoid the translation. Then how do you want the
machine to manipulate the abstract mathematical cons cell?

> > > 2) This said, is it possible to create a machine that manipulates
> > > symbols only?
> >
> > What makes you think any random processor manipulates something else?
>
> I guess the kinds of symbols I am talking about here are different
> than the binary "numbers" processors seem to manipulate now. When I
> say symbol, I mean any legal Lisp symbol (atom).

Here's your problem! An atom is not a symbol: "neo" is an atom, but
it's not a symbol! 078069079 is an atom but is not a symbol!
#((n 78) (e 69) (o 79)) IS an atom and still is not a symbol!

> So 1 2 3 4 'a
> (((('a)(('b)))('c))) are all symbols, or combinations of symbols. I
> wanted to know if we could in principle build a Lisp machine that
> would only manipulate symbols like that in the form of cons cells.

That's the basics. Just get the seven elementary special operators,
and build a full Common-Lisp system!

lambda cons car cdr eq quote cond atom

For example, (+ 3 5) could be written as:

((lambda (s x y) (s s x y))
 (lambda (s x y) (cond ((eq () x) y) ((quote ()) (s s (cdr x) (cons () y)))))
 (quote (()()()))
 (quote (()()()()()())))

[this is lisp-1 of the origins].

There have been already several threads on the subject here...

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&q=+%22minimal+lisp%22+group%3Acomp.lang.lisp&btnG=Search

> > What are symbols?
> > How are symbols implemented on any given hardware?
> >
> > In current hardware, ultimately symbols are merely bit patterns, and
> > all processors do is to manipulate bit patterns.
>
> Right. But what if they are made to be cons cells instead?

Then nothing.

You'd need special hardware to convert the binary input from the
devices into cons cells. A simple scheme could be to translate the
bits received into 0 or 1 encoded as:

  0 <=> ((())())
  1 <=> ((())(()))

So you'd need two hardware primitives (implemented in hardware):

    (inb address) --> byte (ie. list of 8 bits)
    (outb address byte)

For example, to send the letter 'A' to the device at address 16, you'd
write:

    (outb (quote ((()) ((((((((((((((((()))))))))))))))))))
          (quote (((())()) ((())(())) ((())(())) ((())())
                  ((())()) ((())(())) ((())()) ((())(())))))

Of course, once you've implemented a symbol table, you'd remplace all
these parentenses with symbols to be able to write: (outb 16 (int-to-bin 65)).

So you'd have to implement in hardware the following special operators:

  lambda cons car cdr eq quote cond atom inb outb
  + the garbage-collector

and could build the rest over them. But I hope now you have an idea
if the memory and time complexity that would be involved.

------------------------------------------------------------------------
;; scratch of an example of an implementation of a "minimal lisp" in CL.
;;
(defpackage :minimal-lisp
  (:nicknames :ml)
  (:import-from :common-lisp :car :cdr :cons :quote :eq :cond :defun)
  (:export :car :cdr :cons :quote :eq :cond :defun))

(defpackage :minimal-lisp-user
  (:nicknames :mlu)
  (:use :minimal-lisp))

(in-package :minimal-lisp-user)

(defun make-integer (value) (cons (quote (())) value))
(defun make-char (value) (cons (quote ((()))) value))
(defun make-string (value) (cons (quote (((())))) value))
(defun make-cons (value) (cons (quote ((((()))))) value))
(defun make-symbol (value) (cons (quote (((((())))))) value))

(defun get-value (tagged-value) (cdr tagged-value))
(defun get-tag (tagged-value) (car tagged-value))

(defun integerp (tagged-value) (eq (get-tag (make-integer nil))
                                    (get-tag tagged-value)))
(defun charp (tagged-value) (eq (get-tag (make-char nil))
                                    (get-tag tagged-value)))
(defun stringp (tagged-value) (eq (get-tag (make-string nil))
                                    (get-tag tagged-value)))
(defun consp (tagged-value) (eq (get-tag (make-cons nil))
                                    (get-tag tagged-value)))
(defun symbolp (tagged-value) (eq (get-tag (make-symbol nil))
                                    (get-tag tagged-value)))

(defun t () (quote (())))
(defun nil () (quote ()))
(defun null (a) (eq (nil) a))
(defun and (a b) (cond (a b) ((nil))))
(defun or (a b) (cond (a a) (b b)))
(defun not (a) (cond (a (nil)) ((t))))
(defun equiv (a b)
  (or (and (null a) (null b)) (and (not (null a)) (not (null b)))))

(defun internal-mantissa (a) (car (get-value a)))
(defun internal-sign (a) (cdr (get-value a)))

(defun error (err))

(defun abs (a)
  (cond ((integerp a) (make-integer (cons (internal-mantissa a) (nil))))
        ((error (quote applying abs to non integer)))))

(defun negate (a)
  (cond ((integerp a) (make-integer (cons (internal-mantissa a)
                                          (not (internal-sign a)))))
        ((error (quote applying negate to non integer)))))
  
(defun |0| () (make-integer (cons (nil) (nil))))
(defun |1| () (make-integer (cons (t) (nil))))
(defun |-1| () (make-integer (cons (t) (t))))

(defun zerop (a) (null (internal-matissa a)))
(defun positivep (a) (null (internal-sign a)))

(defun internal= (am bm)
  (cond ((and (null am) (null bm)))
        ((or (null am) (null bm)) (nil))
        ((internal= (car am) (car bm)))))

(defun internal< (am bm)
  (cond ((null bm) (nil))
        ((null am) (t))
        ((internal< (car am) (car bm)))))

(defun = (a b) (and (internal= (internal-matissa a) (internal-mantissa b))
                    (equiv (internal-sign a) (internal-sign b))))

(defun < (a b)
  (cond
   ((and (positivep a) (positivep b))
    (cond ((internal< (internal-matissa a)(internal-matissa b)))
          ((nil))))
   ((and (not (positivep a)) (not (positivep b)))
    (cond ((internal< (internal-matissa b)(internal-matissa a)))
          ((nil))))
   ((positivep a) (nil))
   ((t))));;<

(defun > (a b) (not (or (< a b) (= a b))))
(defun >= (a b) (not (< a b)))
(defun <= (a b) (not (> a b)))
(defun /= (a b) (not (= a b)))

(defun internal+ (al bl)
  (cond ((eq (quote ()) al) bl)
        ((internal+ (car al) (cons bl (quote ()))))))

(defun internal-reduce-value (val)
  (cond
   ((or (null (car val)) (null (cdr val))) val)
   ((internal-reduce-value (cons (car (car varl)) (car (cdr val)))))))

(defun + (a b)
  (cond ((zerop a) b)
        ((zerop b) a)
        ((and (positivep a) (positivep b))
         (make-integer (cons (internal+ (internal-mantissa a)
                                        (internal-mantissa b))
                             (nil))))
        ((and (not (positivep a)) (not (positivep b)))
         (make-integer (cons (internal+ (internal-mantissa a)
                                        (internal-mantissa b))
                             (t))))
        ((positive a)
         (cond ((internal< (internal-mantissa b) (internal-mantissa a))
                (make-integer (cons (internal- (internal-mantissa a)
                                               (internal-mantissa b))
                                    (nil))))
               ((internal= (internal-mantissa b) (internal-mantissa a))
                (|0|))
               ((make-integer (cons (internal- (internal-mantissa b)
                                               (internal-mantissa a))
                                    (t))))))
        ((cond ((internal< (internal-mantissa a) (internal-mantissa b))
                (make-integer (cons (internal- (internal-mantissa b)
                                               (internal-mantissa a))
                                    (nil))))
               ((internal= (internal-mantissa a) (internal-mantissa b))
                (|0|))
               ((make-integer (cons (internal- (internal-mantissa a)
                                               (internal-mantissa b))
                                    (t))))))));;+

(defun - (a b) (+ a (negate b)))

(defun internal* (am bm)
  (cond ((null am) am)
        ((null bm) bm)
        ((null (car am)) bm)
        ((null (car bm)) am)
        ;; a*b = b+(a-1)*b
        ((internal+ bm (internal* (car am) bm)))));;internal*

(defun * (a b)
  (cond
   ((zerop a) a)
   ((zerop b) b)
   ((= (|1|) a) b)
   ((= (|1|) b) a)
   ((= (|-1|) a) (negate b))
   ((= (|-1|) b) (negate a))
   ((make-integer (cons (internal* (internal-mantissa a) (internal-mantissa b))
                        (not (equiv (internal-sign a) (internal-sign b))))))));;*
------------------------------------------------------------------------ 

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.

Relevant Pages