Re: How to make a string out of a symbol?

From: Pascal Bourguignon (spam_at_thalassa.informatimago.com)
Date: 07/07/04 

Date: 07 Jul 2004 06:20:17 +0200

André Thieme <address.good.until.2004.aug.11@justmail.de> writes:

> Paul F. Dietz schrieb:
> > André Thieme wrote:
> >
> >> And how does SYMBOL-NAME implement this functionality?
> > It's a builtin function. It's not implemented in terms
> > of other lisp operators, it's a primitive.
> > Are you asking how a lisp implementation would implement this
> > primitive function?
>
> I was thinking about statements from Wikipedia:
> http://en.wikipedia.org/wiki/Lisp_programming_language
>
> Especially this interests me:
> http://en.wikipedia.org/wiki/Lisp_programming_language#Minimal_Lisp
>
>
> This means with seven "functions" (first, rest, cons, quote, eq, if,
> lambda) I can build a lisp. If I only have these, what would be the
> strategy to implement the functionality of SYMBOL-NAME?

Or ask yourself what would be your strategy to implement INTERN or
READ! Note that there are no I/O amongst these seven fundamental
functions...

To get an idea of the practical problem (but an hint of the theoretical
"beauty"):

<sorry, lots of silly code follows...>

(defun 0 () (quote ()))
(defun 1 () (cons (quote ()) 0))
(defun 2 () (cons (quote ()) 1))
(defun 3 () (cons (quote ()) 3))
;; ...

(defun + (a b) (if (eq (0) a) b (+ (cdr a) (cons (quote ()) b))))
(defun * (a b) (if (eq (0) a) (0) (if (eq (1) a) b (+ b (* (cdr a) b)))))
;; ...

Now, to encode characters, you could do as in emacs, where the
character type is the same as fixnum, and to encode strings you'd just
use lists of numbers. So "ABC" would be (in ASCII):

((() () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () () ()
  () () () () () () () ())
 (() () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () () ()
  () () () () () () () () ())
 (() () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () ()))

But you'd rather have typed values. So let's say that you tag the
values in the following way:

(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)
    "That would be a COMMON-LISP cons, not a primitive cons!"
    (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)))

Then to make COMMON-LISP number you'd have to add calls to
make-integer, get-tag and get-value in the above constant number and
operation functions.

Now of course you can't do real I/O with these primitives, but you can
imagine how you could write an emulator to do it, and implement a whole
imaginary Common-Lisp over them.

For example, once you have a string type as defined above, you could
implement files as mere named strings and a file system as a list of
named strings.

(defun file-system ()
  "Return a file system composed of two files,
     one named 'A' containing '012' and the
     other named 'B' containing 'ABC'"
  (quote (((() () () () () () () () () () () () () () () () () () ()
            () () () () () () () () () () () () () () () () () () ()
            () () () () () () () () () () () () () () () () () () ()
            () () () () () () () ())
           ((() () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () ())
            (() () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () ())
            (() () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () ())))
          ((() () () () () () () () () () () () () () () () () () ()
            () () () () () () () () () () () () () () () () () () ()
            () () () () () () () () () () () () () () () () () () ()
            () () () () () () () () ())
           ((() () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () () () () () () () () ()
             () () () () () () () ())
            (() () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () () () () () () () () ()
             () () () () () () () () ())
            (() () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () () () () () () () () () () ()
             () () () () () () () () () ()))))))

So, now you could implement a COMMON-LISP:OPEN function, and a
READ-CHAR function, and a READ-STRING, so the question of how you'd
get a string to feed INTERN is imaginarily solved.

Of course, INTERN would not create a symbol such as these primitive
car cdr cons quote et if and defun! INTERN would create a
"COMMON-LISP" symbol with this function:

(defun make-symbol (value) (cons (quote (()()()()())) value))
(defun symbolp (tagged-value) (eq (get-tag (make-symbol nil))
                                  (get-tag tagged-value)))

So now, your INTERN could look like:

(defun intern (name)
    (if (stringp name)
      (put-in-symbol-table
        (make-symbol
          (cons name ;; symbol-name
            (cons nil ;; no symbol-value (not (boundp))
              (cons nil ;; no symbol-function (not (fboundp))
                (cons nil ;; no symbol-package for now...
                      nil)))))))) ;; empty symbol-plist
                    

So now, of course an implementation of SYMBOL-NAME would be:

(defun symbol-name (symbol)
    (if (symbolp symbol)
      (car (get-value symbol))))

For example, to get the name of the symbol named "ABC", you would call:

(symbol-name (quote ((() () () () ()) ((() () ()) (() () () () () ()
 () () () () () () () () () () () () () () () () () () () () () () ()
 () () () () () () () () () () () () () () () () () () () () () () ()
 () () () () () () () () () () () () ()) (() () () () () () () () () ()
 () () () () () () () () () () () () () () () () () () () () () () ()
 () () () () () () () () () () () () () () () () () () () () () () ()
 () () () () () () () () () ()) (() () () () () () () () () () () () ()
 () () () () () () () () () () () () () () () () () () () () () () ()
 () () () () () () () () () () () () () () () () () () () () () () ()
 () () () () () () () ())) () () ())))

and of course, the result would be:

((() () ()) (() () () () () () () () () () () () () () () () () () ()
 () () () () () () () () () () () () () () () () () () () () () () ()
 () () () () () () () () () () () () () () () () () () () () () () ())
 (() () () () () () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () () () ()) (() () ()
  () () () () () () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () () () () () () ()
  () () () () () () () () () () () () () () () () () ()))

ie. the string "ABC"! 

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein

Relevant Pages