Since Lisp is a language that is mainly used to manipulate symbols, indeed,
I suppose you could say that that is all it really does it manipulate
symbols, I wondered if it would be possible to do a few things with this
apparent advantage of Lisp.
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? Well, I think that computers are very good at manipulating
symbols as well as a programming language is, independent of that languages
implementation. So I want to create a "Lisp Machine" I guess you could say
somewhat similar to what Frank Buss is trying to do in hardware, yet different
in the sense that I'm more concerned with the hardware processing and
manipulating symbols only (in this case Lisp symbols in the form of cons
cells).
2) This said, is it possible to create a machine that manipulates symbols only?
I suppose this is rather like a Turing Machine, yet more advanced. For
now, I'm only worryed about Lisp symbols, although I suppose it would
be an intresting extension to make the machine manipulate any symbol(s)
we wish it to. I don't really mean doing this in the sense of a concrete
computer that can do it, I don't have that kind of time or resources. I
just was looking into this as more of a thought experiment, actually to
make a point to a friend. Although, if there is an easy way to implement this
idea of a symbol-processing machine cheaply, and fast, I might look into
it a bit more. Right now, as many of you know, I am a wee bit preoccupied
with writing a bot in Lisp, and learning the language itself. Unfortanly,
school starts wedensday, which will inhibit my study of Lisp rather
annoyingly. :-(
Anyways, thanks for reading this, and please feel free to give me more
ideas and suggestions, as well as reassuring me that this is a feasible
and worthwhile thought experiment. TIA.
--
May the Source be with you.
neo88 (Philip Haddad)
······@truevine.net (neo88) writes:
> Since Lisp is a language that is mainly used to manipulate symbols, indeed,
> I suppose you could say that that is all it really does it manipulate
> symbols, I wondered if it would be possible to do a few things with this
> apparent advantage of Lisp.
>
> 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.
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?
How is a cons cell reprensented in your brain?
How is a cons cell reprensented in your mind?
> 2) This said, is it possible to create a machine that manipulates
> symbols only?
What makes you think any random processor manipulates something else?
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.
--
__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.
> 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.
>
> > 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). 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.
> 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?
--
May the Source be with you.
neo88 (Philip Haddad)
······@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.
On Tue, Aug 24, 2004 at 07:20:39PM +0200, Pascal Bourguignon wrote:
> 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 (()()()()()())))
For extra credit, do it with lambda only.
(+ 3 5) ==
(((lambda (m) (lambda (n) (lambda (x) (lambda (y) ((m x) ((n x) y))))))
(lambda (x) (lambda (y) (x (x (x y))))))
(lambda (x) (lambda (y) (x (x (x (x (x y))))))))
Church numeral addition in Lisp-1 notation. Try it out, in a Scheme,
define a variable f with the value of the above expression, and then
run ((f (lambda (x) (+ 1 x))) 0)
--
;;;; Matthew Danish -- user: mrd domain: cmu.edu
;;;; OpenPGP public key: C24B6010 on keyring.debian.org
> 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). 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.
I'm not sure I know what you mean.
Internally all symbols get translated to a number equivalent.
For keyboard symbols and control codes this is the ASCII table.
(I expect you know this.)
Lisp stores symbols as a number where the number is a index into a table.
(inaccurate as formulated but essentially correct)
Now on a computer all symbols must at some level be translated to a
sequence of binary digits.
This process if othen called Godelization after the mathematician Kurt
Goeddel who was
the one who proved that all symbolic computation could be done by applying
matematical
operations on number representaions of the symbols.
I can see no easy way to get around this.
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
On 23 Aug 2004 17:08:48 -0700, ······@truevine.net (neo88) wrote:
> Since Lisp is a language that is mainly used to manipulate symbols
That's a misconception.
Edi.
--
"Lisp doesn't look any deader than usual to me."
(David Thornley, reply to a question older than most languages)
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Edi Weitz <········@agharta.de> wrote in message news:<··············@bird.agharta.de>...
> On 23 Aug 2004 17:08:48 -0700, ······@truevine.net (neo88) wrote:
>
> > Since Lisp is a language that is mainly used to manipulate symbols
>
> That's a misconception.
How so? If you write something like:
(defun foo (list)
(and (cdr (list)
(cadr (list)))))
all the function is doing is operating on symbols (the list) provided
as input.
Similarly:
(mapcar #'+ (1 2 3) (4 5 6))
operates on the symbolic lists (1 2 3) and (4 5 6). I'm not saying
here that that is all Lisp is capible of doing. I know it can do much
more than that.
> Edi.
--
May the Source be with you.
neo88 (Philip Haddad)
On 24 Aug 2004 05:32:08 -0700, ······@truevine.net (neo88) wrote:
> Similarly:
>
> (mapcar #'+ (1 2 3) (4 5 6))
>
> operates on the symbolic lists (1 2 3) and (4 5 6).
Nonsense.
···@bird:/tmp$ perl -le 'print join ":", map {1 + $_} qw(1 2 3)'
2:3:4
So, obviously Perl is also a language that "is mainly used to
manipulate symbols." I hope Larry Wall doesn't find out.
Edi.
--
"Lisp doesn't look any deader than usual to me."
(David Thornley, reply to a question older than most languages)
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
In article <····························@posting.google.com>,
······@truevine.net (neo88) wrote:
> Edi Weitz <········@agharta.de> wrote in message
> news:<··············@bird.agharta.de>...
> > On 23 Aug 2004 17:08:48 -0700, ······@truevine.net (neo88) wrote:
> >
> > > Since Lisp is a language that is mainly used to manipulate symbols
> >
> > That's a misconception.
>
> How so? If you write something like:
>
> (defun foo (list)
> (and (cdr (list)
> (cadr (list)))))
>
> all the function is doing is operating on symbols (the list) provided
> as input.
It's not just operating on the symbols, it's operating on the
*relationships* between the symbols. And we use conses, arrays,
structures, and CLOS instances to represent various types of
relationships.
A Lisp without cons cells would be like a phone book with all the names
and phone numbers just randomly laid out, rather than being organized
into a useful table.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Christophe Rhodes
Subject: Re: A "Lisp Machine" and cons cells
Date:
Message-ID: <sqfz6drn3v.fsf@cam.ac.uk>
······@truevine.net (neo88) writes:
> Since Lisp is a language that is mainly used to manipulate symbols, indeed,
> I suppose you could say that that is all it really does it manipulate
> symbols [...]
If your premise is wrong, your conclusions will be untrustworthy no
matter your reasoning. They might still be right, and would be
Gettier counterexamples, but this group probably isn't the place for
them.
Christophe
--
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)
From: Joe Marshall
Subject: Re: A "Lisp Machine" and cons cells
Date:
Message-ID: <zn4ku0pg.fsf@ccs.neu.edu>
······@truevine.net (neo88) writes:
> Since Lisp is a language that is mainly used to manipulate symbols,
What makes you say that? I use Lisp to manipulate all sorts of
things: strings, structures, lists, trees, tables, files, bits, text,
etc.
> indeed, I suppose you could say that that is all it really does it
> manipulate symbols,
You could indeed say that. It would not make it any more true or
false.
> I wondered if it would be possible to do a few things with this
> apparent advantage of Lisp.
>
> 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.
What is that supposed to mean? Lisp is a language, cons cells are
data structures. Who is translating cons cells to machine form?
> 2) This said, is it possible to create a machine that manipulates
> symbols only?
Yes. But why would you want to?