next_inactive up previous


Lisp֮��Դ

���޸��׶�ķ

Լ����������1960�귢����һƪ�Ƿ�������,������ƪ�����жԱ��̵Ĺ������� ŷ�����¶Լ��εĹ���.1 ��������չʾ��,��ֻ���������򵥵IJ�������һ�� ��ʾ�����ļǺŵĻ�����, ���ι�����һ�������ı�������. �������������� ��ΪLisp, ��ΪList Processing, ��Ϊ������Ҫ˼��֮һ����һ�ּ򵥵����� �ṹ��(list)����������������.

ֵ��ע������,�����������ķ���,�����Ǽ�����ʷ�ϻ�ʱ���Ĵ���, ������һ�� ����������ʱ������Խ��Խ������ģʽ.����ΪĿǰΪֹֻ�����������ɾ�����, ʼ����һ�ı���ģʽ:C����ģʽ��Lisp����ģʽ.�˶��߾��������ߵ�, ������ �м������������ĵ͵�.���ż���������Խ��Խǿ��,�¿���������һֱ�ڼᶨ�� ������Lispģʽ. ��ʮ����,�����±������Ե�һ�����е��ؾ���,ȡC���Եļ� ��ģʽ,�𽥵����ϼ�Lispģʽ������,��������ʱ���ͺ����õ�Ԫ�ռ�.

����ƪ�������Ҿ����������򵥵�����������Լ�������������ķ���. �ؼ����� �Dz���Ҫѧϰij������ʮ��ǰ�ó�����Ȥ���۽���, ����չʾ�������Եķ�չ�� ��. Lisp�IJ�ͬѰ��֮��--Ҳ���������ʵĶ���--�����ܹ��Լ�����д�Լ�. Ϊ������Լ���������������������ص�,���ǽ�׷�����IJ���,����������ѧ���� ת�����ܹ����е�Common Lisp����.

�߸�ԭʼ������

��ʼ�����ȶ�������ʽ.����ʽ����һ��ԭ��(atom),����һ����ĸ����(�� foo),����һ������������������ʽ���ɵ���(list), ����ʽ֮���ÿո��ֿ�, ����һ��������. ������һЩ����ʽ:

foo
()
(foo)
(foo bar)
(a b (c) d)
����һ������ʽ�����ĸ�Ԫ�����ɵı�, ������Ԫ�ر�������һ��Ԫ�����ɵı�.

�������б���ʽ 1 + 1 �ó�ֵ2. ��ȷ��Lisp����ʽҲ��ֵ. ��������ʽe�ó� ֵv,����˵e����v. ��һ�����ǽ����弸�ֱ���ʽ�Լ����ǵķ���ֵ.

����һ������ʽ�DZ�,���dzƵ�һ��Ԫ��Ϊ������,������Ԫ��Ϊ�Ա���.���ǽ� �����߸�ԭʼ(�ӹ�����������˵)������: quote,atom,eq,car,cdr,cons,�� cond.

  1. (quote x) ����x.Ϊ�˿ɶ������ǰ�(quote x)���� Ϊ'x.

    > (quote a)
    a
    > 'a
    a
    > (quote (a b c))
    (a b c)
    

  2. (atom x)����ԭ��t����x��ֵ��һ��ԭ�ӻ��ǿձ�,���򷵻�(). ��Lisp������ ��������ԭ��t��ʾ��, ���ÿձ���ʾ��.

    > (atom 'a)
    t
    > (atom '(a b c))
    ()
    > (atom '())
    t
    

    ��Ȼ����һ���Ա�����Ҫ��ֵ�IJ�����, ���ǿ��Կ�һ��quote������. ͨ���� ��(quote)һ����,���DZ���������ֵ. һ��δ�����õı���Ϊ�Ա��������� atom�����IJ�����������Ϊ����:

    > (atom (atom 'a))
    t
    

    ��֮һ�������õı�������Ϊ��, �ڴ����о���������Ԫ�صı�:

    > (atom '(atom 'a))
    ()
    

    ����������Ӣ����ʹ�����ŵķ�ʽһ��. Cambridge(����)��һ��λ���������� ����90000�˿ڵij���. ��``Cambridge''��һ����9����ĸ���ɵĵ���.

    ���ÿ���ȥ�����е�������Ϊ�������������������Ƶĸ���. ����Lisp������ ��ͬ������������ϵ:��������������ͬ�����ݽṹ����, ��������quote������ ����������.

  3. (eq x y)����t����x��y��ֵ��ͬһ��ԭ�ӻ����ǿձ�, ���򷵻�().

    > (eq 'a 'a)
    t
    > (eq 'a 'b)
    ()
    > (eq '() '())
    t
    

  4. (car x)����x��ֵ��һ�������ҷ���x�ĵ�һ��Ԫ��.

    > (car '(a b c))
    a
    

  5. (cdr x)����x��ֵ��һ�������ҷ���x�ĵ�һ��Ԫ��֮��������Ԫ��.
    > (cdr '(a b c))
    (b c)
    

  6. (cons x y)����y��ֵ��һ�������ҷ���һ���±�,���ĵ�һ��Ԫ����x��ֵ, �� ������y��ֵ�ĸ���Ԫ��.

    > (cons 'a '(b c))
    (a b c)
    > (cons 'a (cons 'b (cons 'c '())))
    (a b c)
    > (car (cons 'a '(b c)))
    a
    > (cdr (cons 'a '(b c)))
    (b c)
    
  7. (cond ($p_{1}$...$e_{1}$) ...($p_{n}$...$e_{n}$)) ����ֵ��������. p����ʽ������ֱֵ����һ�� ����t. �������ҵ�������p����ʽ,��Ӧ��e����ʽ��ֵ��Ϊ����cond����ʽ�� ����ֵ.

    > (cond ((eq 'a 'b) 'first)
            ((atom 'a)  'second))
    second
    

    ������ʽ���߸�ԭʼ�������е�������ͷʱ,�����Ա�������Ҫ��ֵ��.2 ���dz����� �IJ�����Ϊ����.

�����ı�ʾ

�������Ƕ���һ���Ǻ�����������.������ʾΪ(lambda ($p_{1}$...$p_{n}$) e),���� $p_{1}$...$p_{n}$��ԭ��(��������),e�DZ���ʽ. ��������ʽ�ĵ�һ��Ԫ����ʽ�� ��

((lambda ($p_{1}$...$p_{n}$) e) $a_{1}$...$a_{n}$)

����Ϊ��������.����ֵ��������.ÿһ������ʽ$a_{i}$����ֵ,Ȼ��e����ֵ.��e�� ��ֵ������,ÿ��������e�е�$p_{i}$��ֵ����Ӧ��$a_{i}$������һ �εĺ��������е�ֵ.

> ((lambda (x) (cons x '(b))) 'a)
(a b)
> ((lambda (x y) (cons x (cdr y)))
   'z
   '(a b c))
(z b c)
����һ������ʽ�ĵ�һ��Ԫ��f��ԭ����f����ԭʼ������

(f $a_{1}$...$a_{n}$)

����f��ֵ��һ������(lambda ($p_{1}$...$p_{n}$)),�����ϱ���ʽ��ֵ����

((lambda ($p_{1}$...$p_{n}$) e) $a_{1}$...$a_{n}$)

��ֵ. ���仰˵,�����ڱ���ʽ�в���������Ϊ�Ա���Ҳ������Ϊ������ʹ��:

> ((lambda (f) (f '(b c)))
   '(lambda (x) (cons 'a x)))
(a b c)

������һ�������Ǻ�ʹ�ú������ἰ������,�������Ǿ��ܷ����ض����ݹ麯 ��.3 �Ǻ�

(label f (lambda ($p_{1}$...$p_{n}$) e))

��ʾһ����(lambda ($p_{1}$...$p_{n}$) e)�����ĺ���,��������������: �κγ�����e�е�f����ֵΪ��label����ʽ, �ͺ���f�Ǵ˺����IJ���.

��������Ҫ���庯��(subst x y z), ��ȡ����ʽx,ԭ��y�ͱ�z������,����һ�� ��z�����ı�, ����z�г��ֵ�y(���κ�Ƕ�ײ�����)��x����.

> (subst 'm 'b '(a b (a b c) d))
(a m (a m c) d)
���ǿ���������ʾ�˺���
(label subst (lambda (x y z)
               (cond ((atom z)
                      (cond ((eq z y) x)
                            ('t z)))
                     ('t (cons (subst x y (car z))
                               (subst x y (cdr z)))))))
���Ǽ���f=(label f (lambda ($p_{1}$...$p_{n}$) e))Ϊ

(defun f ($p_{1}$...$p_{n}$) e)

����

(defun subst (x y z)
  (cond ((atom z)
         (cond ((eq z y) x)
               ('t z)))
        ('t (cons (subst x y (car z))
                  (subst x y (cdr z))))))
żȻ��������������������дcond����ʽ��ȱʡ�Ӿ�. ��һ��Ԫ����'t���Ӿ��� �ǻ��ɹ���. ����

(cond (x y) ('t z))

��ͬ��������ijЩ������д��

if x then y else z

һЩ����

��Ȼ�������˱�ʾ�����ķ���,���Ǹ����߸�ԭʼ������������һЩ�µĺ���. Ϊ�˷�����������һЩ����ģʽ�ļ��Ƿ�. ������cxr,����x��a��d������,�� ������Ӧ��car��cdr������. ����(cadr e)��(car (cdr e))�ļ���,������e�� �ڶ���Ԫ��.

> (cadr '((a b) (c d) e))
(c d)
> (caddr '((a b) (c d) e))
e
> (cdar '((a b) (c d) e))
(b)
���ǻ���(list $e_{1}$...$e_{n}$)��ʾ(cons $e_{1}$...(cons $e_{n}$'()) ...).
> (cons 'a (cons 'b (cons 'c '())))
(a b c)
> (list 'a 'b 'c)
(a b c)

�������Ƕ���һЩ�º���. ���ں������������˵�,�����������Ͷ������ǵ�ԭ ʼ����,Ҳ�������ִ���common Lisp�ĺ�����ͻ.

  1. (null. x)���������Ա����Ƿ��ǿձ�.

    (defun null. (x)
      (eq x '()))
    
    > (null. 'a)
    ()
    > (null. '())
    t
    

  2. (and. x y)����t�������������Ա�������t, ���򷵻�().

    (defun and. (x y)
      (cond (x (cond (y 't) ('t '())))
            ('t '())))
    
    > (and. (atom 'a) (eq 'a 'a))
    t
    > (and. (atom 'a) (eq 'a 'b))
    ()
    

  3. (not. x)����t���������Ա�������(),����()���������Ա�������t.

    (defun not. (x)
      (cond (x '())
            ('t 't)))
    
    > (not. (eq 'a 'a))
    ()
    > (not. (eq 'a 'b))
    t
    

  4. (append. x y)ȡ���������������ǵ�����.

    (defun append. (x y)
       (cond ((null. x) y)
             ('t (cons (car x) (append. (cdr x) y)))))
    
    > (append. '(a b) '(c d))
    (a b c d)
    > (append. '() '(c d))
    (c d)
    

  5. (pair. x y)ȡ������ͬ���ȵı�,����һ����˫Ԫ�ر����ɵı�,˫Ԫ�ر����� Ӧλ�õ�x,y��Ԫ�ض�.

    (defun pair. (x y)
      (cond ((and. (null. x) (null. y)) '())
            ((and. (not. (atom x)) (not. (atom y)))
             (cons (list (car x) (car y))
                   (pair. (cdr) (cdr y))))))
    
    > (pair. '(x y z) '(a b c))
    ((x a) (y b) (z c))
    

  6. (assoc. x y)ȡԭ��x������pair.���������صı�y,����y�е�һ������������ ���ı��ĵڶ���Ԫ��:���ĵ�һ��Ԫ����x.

    (defun assoc. (x y)
      (cond ((eq (caar y) x) (cadar y))
            ('t (assoc. x (cdr y)))))
    
    > (assoc. 'x '((x a) (y b)))
    a
    > (assoc. 'x '((x new) (x a) (y b)))
    new
    

һ����ϲ

���������ܹ����庯�������ӱ�,�滻����ʽ�ȵ�.Ҳ������һ�������ı�ʾ��, ����һ����? ���ھ�ϲ����. ���ǿ���дһ��������Ϊ�������ԵĽ�����:�˺� ��ȡ����Lisp����ʽ���Ա�������������ֵ. ������ʾ:

(defun eval. (e a)
  (cond 
    ((atom e) (assoc. e a))
    ((atom (car e))
     (cond 
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
       ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
       ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
       ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'cond)  (evcon. (cdr e) a))
       ('t (eval. (cons (assoc. (car e) a)
                        (cdr e))
                  a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
            (cons (list (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr  e) a))
                     a)))))

(defun evcon. (c a)
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        ('t (evcon. (cdr c) a))))

(defun evlis. (m a)
  (cond ((null. m) '())
        ('t (cons (eval.  (car m) a)
                  (evlis. (cdr m) a)))))
eval.�Ķ�����������ǰ�����Ķ�Ҫ��. �����ǿ�������ÿһ���������ι�����.

eval.�������Ա���: e��Ҫ��ֵ�ı���ʽ, a����һЩ����ԭ�ӵ�ֵ���ɵı�,�� Щֵ�е������������еIJ���. ��������pair.�ķ���ֵ�ı���������. ���� Ϊ�˹������������ֱ����Dz�д��pair.��assoc..

eval.�ĹǼ���һ�����ĸ��Ӿ���cond����ʽ. ���ζԱ���ʽ��ֵȡ���������� ��. ��һ���Ӿ䴦��ԭ��. ����e��ԭ��, �����ڻ�����Ѱ������ֵ:

> (eval. 'x '((x a) (y b)))
a

�ڶ����Ӿ�����һ��cond, ����������(a ...)�ı���ʽ, ����a��ԭ��. ���� �����е�ԭʼ������, ÿ����Ӧһ���Ӿ�.

> (eval. '(eq 'a 'a) '())
t
> (eval. '(cons x '(b c))
         '((x a) (y b)))
(a b c)
�⼸���Ӿ�(����quote)������eval.��Ѱ���Ա�����ֵ.

���������Ӿ�������Щ. Ϊ����cond����ʽ��ֵ���ǵ�����һ���� evcon.�ĸ�������. ���ݹ��ض�cond�Ӿ�������ֵ,Ѱ�ҵ�һ��Ԫ�ط���t���Ӿ�. �����ҵ� ���������Ӿ�, �����ش��Ӿ��ĵڶ���Ԫ��.

> (eval. '(cond ((atom x) 'atom)
                ('t 'list))
         '((x '(a b))))
list

�ڶ����Ӿ������󲿷ִ�����������. ����ԭ���滻Ϊ����ֵ(Ӧ����lambda ��label����ʽ)Ȼ�������ý�������ʽ��ֵ. ����

(eval. '(f '(b c))
       '((f (lambda (x) (cons 'a x)))))
��Ϊ
(eval. '((lambda (x) (cons 'a x)) '(b c))
       '((f (lambda (x) (cons 'a x)))))
������(a b c).

eval.������cond�����Ӿ䴦����һ��Ԫ����lambda��label�ĺ�������.Ϊ�˶�label ����ʽ��ֵ, �ȰѺ������ͺ�������ѹ�뻷��, Ȼ������eval.��һ���ڲ��� lambda�ı���ʽ��ֵ. ��:

(eval. '((label firstatom (lambda (x)
                            (cond ((atom x) x)
                                  ('t (firstatom (car x))))))
         y)
       '((y ((a b) (c d)))))
��Ϊ
(eval. '((lambda (x)
           (cond ((atom x) x)
                 ('t (firstatom (car x)))))
         y)
        '((firstatom
           (label firstatom (lambda (x)
                            (cond ((atom x) x)
                                  ('t (firstatom (car x)))))))
          (y ((a b) (c d)))))
���շ���a.

����,������((lambda ($p_{1}$...$p_{n}$) e) $a_{1}$...$a_{n}$)�ı���ʽ��ֵ,�ȵ���evlis.�� �����Ա���($a_{1}$...$a_{n}$)��Ӧ��ֵ($v_{1}$...$v_{n}$),��($p_{1}$$v_{1}$)...($p_{n}$$v_{n}$)���ӵ� ������, Ȼ����e��ֵ. ����

(eval. '((lambda (x y) (cons x (cdr y)))
         'a
         '(b c d))
       '())
��Ϊ
(eval. '(cons x (cdr y))
       '((x a) (y (b c d))))
���շ���(a c d).

����

��Ȼ������eval�����ι�����, �����ǻع�ͷ����һ������ζ��ʲô. �������� ���õ���һ���dz������ļ���ģ��. ����quote,atom,eq,car,cdr,cons,��cond, ���Ƕ����˺���eval.,����ʵ��ʵ�������ǵ�����,�������Զ����κ�������Ҫ �Ķ����ĺ���.

��Ȼ�������˸��ּ���ģ��--����������ͼ����. ����ͼ�����������Զ���. ������Ҫһ�������㷨������, ��������Ҫ��������, ��������Լ������������ Lisp��Ŀ��֮һ.

Լ����������1960�궨�������Ի�ȱ���ٶ���. ��û�и�����, û������ִ�� (���ú͸�������һ��������), û��ʵ�ʿ��õ���,4 û�ж�̬������. ����Щ���ƿ� �����˾��ȵ��ü��ٵĶ�������������. Steele��Sussman��һƪ����``������ ������''������������������������������.5

������������Լ����������eval, �����Ͳ������������˳���������ʷ�е�һ�� �׶�. ��Щ˼����������Lisp����������. ���Դ�ij��������, ѧϰԼ������ ����ԭ��������չʾ��Lisp������ʲô. ����˵Lisp��������������,����˵�� ���ķ���. ��������������һ�������˹�����, ����ԭ�Ϳ�����ͬ�Ȳ��������� ����. ��������ͼ�����������Ľ���(֮һ).

����ʱ��������, �м�����, �����м�������Աʹ�õ�����, ��һ�µ���Lisp�� ��. ����ͨ������eval���������׽�������������ģʽ����ʲô��.

ע��

��Լ���������ļǺŷ���Ϊ�����Ĺ������Ҿ����ܵ������Ķ�. ���й��ô��� �������Ķ�����ͷ, �����һ����뱣��ԭ֭ԭζ.

��Լ����������������,����f����ʾ, �����ǿձ�. ���ÿձ���ʾ����ʹ������ ��Common Lisp������. (fixme)

���Թ��˹���dotted pairs, ��Ϊ�㲻��Ҫ��������eval. ��Ҳû����apply, ��Ȼ��apply(����������ʽ, ��Ҫ�����������Ա���), ��Լ����������1960�� ��Ϊ�ձ麯��, evalֻ�Dz����DZ�apply���õ��ӳ������������еĹ���.

�Ҷ�����list��cxr����Ϊ���Ƿ���Ϊ������������ô����. ʵ���� cxr�ȿ��� ������Ϊ��ͨ�ĺ���. ListҲ��������, ���������޸�eval, ������������, �� �������Խ���������Ŀ���Ա���.

��������������ֻ������ԭʼ������. ��ʹ����cond��quote,�����ܰ������� Ϊ����Ԫ���Ե�һ����. ͬ����Ҳû�ж����߼�������and��not, �ⲻ�Ǹ�����, ��Ϊ���ǿ��Ա������ɺ��ʵĺ���.

��eval.�Ķ��������ǵ���������������pair.��assoc.,���κ�������ԭʼ���� �������ĺ������ö�������eval.������. ��

(assoc. (car e) a)
���

(eval. '((label assoc.
                (lambda (x y)
                  (cond ((eq (caar y) x) (cadar y))
                        ('t (assoc. x (cdr y))))))
         (car e)
         a)
        (cons (list 'e e) (cons (list 'a a) a)))

��������eval��һ������. ��16����(�൱��)(evlis. (cdr e) a)������(cdr e), ��ʹ���Ա�����һ�����������ĵ����б���ֵ����. ����ʾ�����ķ����� ʱ��, eval������������û����IBM 704��������ʵ��. ����֤����������ȥ�� �г���, Ҫ��֤���ܶ��̵ij�������ȷ���Ƕ�ô����.

�һ���������������������һ������. �ڶ�����eval֮��, ������������һЩ ���߼��ĺ���--��������������Ϊ�Ա����ĺ���. ��������maplist:

(label maplist
       (lambda (x f)
         (cond ((null x) '())
               ('t (cons (f x) (maplist (cdr x) f))))))
Ȼ������д��һ����΢�ֵļ򵥺���diff. ����diff����maplistһ����x���� ���ĺ���, ���������ñ�maplist�еIJ���x������.6

���ǹ��ڶ�̬������Σ���Ե��۱�֤��, ��ʹ�������ĸ��߼�����������Ҳ��Ϊ ��������. ������������1960�껹û�г�����ʶ����̬�������ĺ���. ��̬�� �������˾�������Lispʵ���д������൱����ʱ��--ֱ��Sussman��Steele�� 1975�꿪����Scheme. �ʷ�������ûʹeval�Ķ��帴�Ӷ���, ȴʹ���������� д��.

About this document ...

Lisp֮��Դ

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split=0 roots_of_lisp.tex

The translation was initiated by Dai Yuwen on 2003-10-24


Footnotes

... ŷ�����¶Լ��εĹ���.1
``Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part1.'' Communication of the ACM 3:4, April 1960, pp. 184-195.
...������ʽ���߸�ԭʼ�������е�������ͷʱ,�����Ա�������Ҫ��ֵ��.2
����������������quote��cond��ͷ�ı���ʽ�Բ�ͬ�ķ�ʽ��ֵ. �� quote����ʽ��ֵʱ, �����Ա���������ֵ,������Ϊ��������ʽ��ֵ����. �� һ����ȷ��cond����ʽ��, ֻ��L��·���ϵ��ӱ���ʽ�ᱻ��ֵ.
... ��.3
�߼������Dz���ҪΪ���ⶨ��һ���µļǺ�. �����еļǺ����� һ������Y�������ĺ����ϵĺ���, ���ǿ��Զ����ݹ麯��. ������������д ��ƪ���ĵ�ʱ�򻹲�֪��Y������; ��������, label�ɶ��Ը�ǿ.
... û��ʵ�ʿ��õ���,4
����������1960 ����Lisp��, �������ǿ��ܵ�, ������һ����n��ԭ�ӵı���ʾ��n.
... ������''������������������������������.5
Guy Lewis Steele, Jr. and Gerald Jay Sussman, ``The Art of the Interpreter, or the Modularity Complex(Parts Zero,One,and Two),'' MIT AL Lab Memo 453, May 1978.
... ���������ñ�maplist�еIJ���x������.6
������Lisp���� Ա����������mapcar����maplist. �������ӽ⿪��һ������: maplistΪʲ ô����Common Lisp��. ����������ӳ�亯��, mapcar�Ǻ������ӵ�.

next_inactive up previous
Dai Yuwen 2003-10-24