Kazimir Majorinc's Blog (currently not in use): September 2010

; In this article, I'll show how John McCarthy's Lisp can be interpreted
; in McCarthy's Lisp, which is interpreted in McCarthy's Lisp ...
; and so on, n times.
;
; One of the reasons for harder understanding of early Lisps is
; McCarthy's decision to use same identifiers for Lisp implemented
; in machine code, and for Lisp interpreted by EVAL function.
;
; For example, if McCarthy-60 Lisp expression
;
;
;    (EVAL (QUOTE ((LAMBDA (XX) (CONS XX (CONS XX (QUOTE ()))))
;                  (QUOTE somedata)))
;          (QUOTE ()))
;
;
; is evaluated, the first and the last oocurences of QUOTE are
; evaluated as special operators defined in base language (in my
; case Newlisp, in original implementation it was machine code),
; while second and third occurence of QUOTE are interpreted
; following the rules defined in John McCarthy-60 EVAL function.
;
; McCarthy's decision isn't incorrect, but using slightly
; different symbols is not wrong either and it certainly contributes
; to easier understanding. In second article I redefined EVAL so
; it evaluates expressions containing symbols like CONS.1, QUOTE.1
; ... for example:
;
;
; (EVAL (QUOTE ((LAMBDA.1 (XX) (CONS.1 XX (CONS.1 XX (QUOTE.1 ()))))
;                (QUOTE.1 somedata)))
;        (QUOTE ()))
;
;
; If we can define LAMBDA.1, QUOTE.1, ... then, why not EVAL.1 as well?
;
; That definition was described in previous article on this topic. It is very
; dry and formal definition, because definition of EVAL.1, and
; all needed helper functions should be written in limited McCarthy-60
; Lisp EVAL interpreter, and given to EVAL in the form of quoted
; association list.
;
;
; (EVAL <quoted expression to be evaluated>
;        <quoted association list>             ;<======= HERE
; )
;
;
; If quoted association list is named McCarthy-60-interpreter.1,
; then example of such expressions is
;
;
; (EVAL (QUOTE (EVAL.1 (QUOTE.1 ((LAMBDA.2 (XX)
;                                  (CONS.2 XX (CONS.2 XX (QUOTE.2 ()))))
;                                (QUOTE.2 somedata)))
;                                     (QUOTE.1 ())
;                             )
;                      )
;        <McCarthy-60-interpreter.1>
;        )
;
;
; This is how McCarthy-60-interpreter.1 looks like:
; (McCarthy-60-Lisp in Newlisp library first.)

(load (append "http://www.instprog.com/McCarthy-60-LISP/"
              "McCarthy-60-LISP-in-Newlisp.lsp"))

(setf McCarthy-60-interpreter.1

'(QUOTE

    (
      ;-------------------------
      (EVAL.1 (LABEL.1 EVAL.1
         (LAMBDA.1 (e a)
            (COND.1
               ((ATOM.1 e) (ASSOC.1 e a))
               ;-------------------------
               ((ATOM.1 (CAR.1 e))

                (COND.1

                    ((EQ.1 (CAR.1 e) (QUOTE.1 QUOTE.2))
                           (CAR.1 (CDR.1 e)))
                    ;-------------------------
                    ((EQ.1 (CAR.1 e) (QUOTE.1 ATOM.2))
                           (ATOM.1 (EVAL.1 (CAR.1 (CDR.1 e))
                                           a)))
                    ;-------------------------
                    ((EQ.1 (CAR.1 e) (QUOTE.1 EQ.2))
                           (EQ.1 (EVAL.1 (CAR.1 (CDR.1 e))
                                         a)
                                 (EVAL.1 (CAR.1 (CDR.1 (CDR.1 e)))
                                         a)))
                    ;-------------------------
                    ((EQ.1 (CAR.1 e) (QUOTE.1 COND.2))
                           (EVCON.1 (CDR.1 e) a))
                    ;-------------------------
                    ((EQ.1 (CAR.1 e) (QUOTE.1 AND.2))
                       (EVAL.1 (CONS.1 (QUOTE.1 COND.2)
                                  (CONS.1 (CDR.1 e)
                                     (QUOTE.1 (((QUOTE.2 T)
                                                (QUOTE.2 F))))))
                               a))
                    ;-------------------------
                    ((EQ.1 (CAR.1 e) (QUOTE.1 CAR.2))
                           (CAR.1 (EVAL.1 (CAR.1 (CDR.1 e)) a)))
                    ;-------------------------
                    ((EQ.1 (CAR.1 e) (QUOTE.1 CDR.2))
                           (CDR.1 (EVAL.1 (CAR.1 (CDR.1 e)) a)))
                    ;-------------------------
                    ((EQ.1 (CAR.1 e) (QUOTE.1 CONS.2))
                           (CONS.1 (EVAL.1 (CAR.1 (CDR.1 e))
                                           a)
                                   (EVAL.1 (CAR.1 (CDR.1 (CDR.1 e)))
                                           a)))
                    ;-------------------------
                    ((QUOTE.1 T) (EVAL.1 (CONS.1 (ASSOC.1 (CAR.1 e)
                                                          a)
                                                 (CDR.1 e))
                                         a))))
               ;-------------------------
               ((EQ.1 (CAR.1 (CAR.1 e)) (QUOTE.1 LABEL.2))
                    (EVAL.1 (CONS.1 (CAR.1 (CDR.1 (CDR.1 (CAR.1 e))))
                                    (CDR.1 e))
                            (CONS.1 (LIST.1 (CAR.1 (CDR.1 (CAR.1 e)))
                                            (CAR.1 e))
                                    a)))
               ;-------------------------
               ((EQ.1 (CAR.1 (CAR.1 e)) (QUOTE.1 LAMBDA.2))
                 (EVAL.1 (CAR.1 (CDR.1 (CDR.1 (CAR.1 e))))
                         (APPEND.1 (PAIR.1 (CAR.1 (CDR.1 (CAR.1 e)))
                                           (EVLIS.1 (CDR.1 e) a))
                                   a)))

       ))))
      ;-------------------------
      (APPEND.1 (LABEL.1 APPEND.1
         (LAMBDA.1(X Y)
            (COND.1 ((NULL.1 X) Y)
               ((QUOTE.1 T)
                   (CONS.1 (CAR.1 X) (APPEND.1 (CDR.1 X) Y)))))))
      ;-------------------------
      (ASSOC.1 (LABEL.1 ASSOC.1
         (LAMBDA.1 (X Y)
            (COND.1
               ((EQ.1 (CAR.1 (CAR.1 Y)) X) (CAR.1 (CDR.1 (CAR.1 Y))))
               ((QUOTE.1 T)                (ASSOC.1 X (CDR.1 Y)))))))
      ;-------------------------
      (PAIR.1 (LABEL.1 PAIR.1
         (LAMBDA.1 (X Y)
            (COND.1 ((AND.1 (NULL.1 X) (NULL.1 Y)) (QUOTE.1 NIL))
                    ((AND.1 (NOT.1 (ATOM.1 X)) (NOT.1 (ATOM.1 Y)))
                            (CONS.1 (LIST.1 (CAR.1 X) (CAR.1 Y))
                                    (PAIR.1 (CDR.1 X) (CDR.1 Y))))))))
      ;-------------------------
      (EVLIS.1 (LABEL.1 EVLIS.1
         (LAMBDA.1 (m a)
            (COND.1 ((NULL.1 m) (QUOTE.1 NIL))
                    ((QUOTE.1 T) (CONS.1 (EVAL.1 (CAR.1 m) a)
                                         (EVLIS.1 (CDR.1 m) a)))))))
      ;-------------------------
      (EVCON.1 (LABEL.1 EVCON.1
         (LAMBDA.1 (c a)
            (COND.1 ((EVAL.1 (CAR.1 (CAR.1 c)) a)
                             (EVAL.1 (CAR.1 (CDR.1 (CAR.1 c))) a))
                    ((QUOTE.1 T)
                             (EVCON.1 (CDR.1 c) a))))))
      ;-------------------------
      (NULL.1 (LAMBDA.1 (X)
                 (AND.1 (ATOM.1 X) (EQ.1 X (QUOTE.1 NIL)))))
      ;-------------------------
      (NOT.1 (LAMBDA.1 (X)
                 (COND.1 (X          (QUOTE.1 F))
                         ((QUOTE.1 T)(QUOTE.1 T)))))
      ;-------------------------
      (LIST.1 (LAMBDA.1 (X Y) (CONS.1 X (CONS.1 Y (QUOTE.1 NIL)))))

    )
  )
)

; variable McCarthy-60-interpreter.1 cannot be used directly. It
; has to be replaced with its value first.
;
; Once McCarthy-60-interpreter.1 is defined, it is easy to generalize
; it and define McCarthy-60-interpreter.2, McCarthy-60-interpreter.3,...
; Just respective indexes should be changed.
;
; Here is Newlisp function that calculate these interpreters, for
; given n:

(define (McCarthy-60-interpreter n)

  (if (= n 1)

      McCarthy-60-interpreter.1

      (letn((symbols-in-McCarthy-60-interpreter.1
                  (difference (unique (flat McCarthy-60-interpreter.1))
                              '(T F NIL)))

            (assoc-list1
               (map (lambda(x)
                      (list x
                           (if (find x '(QUOTE e a X Y m c))

                               (sym (append "°"
                                            (string x)
                                            "."
                                            (string (- n 1))))

                               (let ((parsed-x (parse (string x) ".")))

                                   (case (last parsed-x)
                                     ("1" (sym (append "°"
                                                 (first parsed-x)
                                                  "."
                                                 (string n))))
                                     ("2" (sym (append "°"
                                                 (first parsed-x)
                                                  "."
                                                 (string (+ n 1))))))))))

                     symbols-in-McCarthy-60-interpreter.1))

             (assoc-list2
                (map (lambda(x)
                        (list (last x) (sym (rest (string (last x))))))
                     assoc-list1)))

              (local(result)
                (setf result (expand McCarthy-60-interpreter.1
                                     assoc-list1))

                (setf result (expand result assoc-list2))

                result))))

; And this is an example how these interpreters could be used

(setf McCarthy-60-interpreter.2 (McCarthy-60-interpreter 2))

(debug-wrap EVAL)

                  (eval
                    (expand
                      '(EVAL
                         (QUOTE
                           (EVAL.1
                             (QUOTE.1
                               (EVAL.2
                                 (QUOTE.2
                                   (QUOTE.3 somedata))
                                 (QUOTE.2 ())
                               )
                             )
                             McCarthy-60-interpreter.2
                           )
                         )
                         McCarthy-60-interpreter.1
                       )

                      'McCarthy-60-interpreter.1
                      'McCarthy-60-interpreter.2

                    )
                  )

; McCarthy's EVAL is, however, very inefficient - its purpose was
; purely theoretical, so, if you want to really evaluate this simple
; expression prepare yourself on long waiting. (Less than one hour
; on modern PC, however.)

Part of the output of the program

---

Kazimir Majorinc's Blog (currently not in use)

Change of The Blog Name.

McCarthy-60 Lisp in McCarthy-60 Lisp in ... in McCarthy-60 Lisp.

Newlisp Related Blogs

Newlisp Related Sites.