(original) (raw)

����;� TeX output 2005.06.22:1811����������2���7 �color push Black��� color pop�������x����!��color push Black� color pop���+��color push rgb 1 0 0�KtEo�1lcmss8�SOME�KkLISP�HISTORY�AND�SOME�PROGRAMMING��ڝ���( LANGUA��O GE�KkIDEAS� color pop�����c�John�KkMcCa��O rthy���#,�Stanfo�rd�Universit�y����֍Berlin,�Kk2002�June�19��O4䍐7 ��K� �1cmsy8�� ��I� !supp���ose�I'm�here�b�ecause�of�Lisp,� � although�I� !haven't�b�een����7 involved�Kkin�the�Lisp�communit��O y�fo�r�a�very�long�time.��9����7 �����Lisp�is�actively�used,���e.g.� �Aon�the�Deep�Space�1�spacecraft�and����7 in� �Fthe�Orbitz�airline�reservation�system,� �but�I� ��don't�kno��O w�any����7 details.����7 �� �r�F��O ritz�Kunze's�F�ranz�Inc.�+Omak�es�quite�a�go���o�d� �rcommon�Lisp,����7 called�KkAllegro�Common�Lisp.�����7 �color push Black���V,��KtEo ��lcmss8�1����� color pop����*�����2���7 �color push Black��� color pop�������x��7 �� d3�Some�imp���o��O rtant�asp�ects�of�Lisp�a��O re�not�available�in�other������7 p��O rogramming� �languages�and�systems.��VI� ܸdon't�kno�w�if�they�a�re����7 used�Kkin�the�ab���ove�applications.��8e*��7 ���;�The�o��O riginal�idea�w�as�to�combine�1956�list�p�ro���cessing�as�done����7 b��O y�ކNew�ell,��NSimon�and�Sha�w�with�ideas�from�John�Backus's�F�o�r-����7 tran.����7 ����Herb���ert�Gelernter�at�IBM���underto�ok�to�implement�Ma��O rvin�Min-����7 sky's���idea�fo��O r�a�plane�geometry�theo�rem�p�rover,��Yand�I���p�rop���osed����7 list� !�p��O ro���cessing�in�F�o�rtran.���Gelernter�and�Ca�rl�Gerb���erich�devel-����7 op���ed�KkFLPL.����7 ��/�In�1958�Lisp�w��O as�sta�rted�at�M.I.T.�using�recursion,�4�which�w�as����7 not�Kkfeasible�in�F��O o�rtran.� 9Lisp�Kkw�as�intended�fo�r�AI�p�rogramming.�����7 �color push Black��� color pop����Ƞ����2���7 �color push Black��� color pop�������x��7 �� � �Lisp�w��O as�intended�to�b���e�compiled�at� rst.��Ho�w�ever,� KqI� �wrote����7 a� �Vuniversal�Lisp�function���2�1cmmi8�ev���al� �ɹin�1959�to�sho��O w�that�Lisp�w�as�a����7 neater���language�fo��O r�computabilit�y�theo�ry�than�T���#uring�machines.����7 Steve� �Russell�p���ointed�out�that�the�universal�function�could�b�e����7 tak��O en� ��as�an�interp�reter�fo�r�pure�Lisp,� 1and�hand-compiled�it�in����7 IBM�Kk704�machine�language.�����7 �color push Black��� color pop����������2���7 �color push Black��� color pop�������x����KwV�color push Black� color pop���UwV�color push rgb 1 0 0�DIFFERENTIA���#TION|the�Kkmotivating�example� color pop��1[��7 The�Kkfollo��O wing�example�motivated��8򘍐7 ��Kk�recursion�using�conditional�exp��O ressions����7 ��Kk�lisp�notation�fo��O r�algeb�raic�exp�ressions����7 ��Kk�allo��O wing�functions�as�a�rguments�with���-exp�ression�syntax�����7 di �� ��(�e;��vv��ع)��� ���if���M�at��8U��e��Kk�then������7 [�if��m��e���=��v�� C�then��>;�1��Kkelse��5��0�Kk]�����7 else�Kkif���@u�ca��O r��d�!�e� �u�=���P�� LU��S���>�then��9Mu�P�LU�S��>:��[mapl�<sist�(�cdr�7�e;��vu:dif�1�f��(�car�u;��vv���ع))�����7 else�kkif���c�ca��o r��i�a�e�+��="���T��" i���m��e��s��="" hn�then��="">���P�LU�S� hN:�Kkmapl�<sist�(�cdr���e;��vu:t�i���m�e��s� hn:����7="" mapl�<sist�(�cdr���e;��vw���!:���ֹif��&y�u���ֹeq��0b��w��ԍ�then��=""> Ӽdif�1�f��(�car�u;��vv��ع)����else��>@�car�w��!�)))�����7 �color push Black���V,»2����� color pop���� �����2���7 �color push Black��� color pop�������x����ҳ��color push Black� color pop���ܳ��color push rgb 1 0 0�ASPECTS�KkOF�LISP� color pop��/�9��7 ����Lisp�lists�including�lists�of�list�a��O re�the�app�rop�riate�rep�resentation��JՍ�7 of�y�symb���olic�exp��O ressions�fo�r�computation|b���etter�than�strings|����7 and�Kkb���etter�than�XML.��4s4��7 ���'�Lisp�p��O rograms�a�re�Lisp�data.� �xPut�abstractly���#,��Lisp�has�functions����7 fo��O r�Kkits�o�wn����1lcmssi8�abstract�syntax.����7 �� �L�Lisp�p��O rograms,� ��most�conveniently�pure�Lisp�functional�p�ro-����7 grams,�Kka��O re�a�re�describ���ed�extensionally�b�y� rst�o�rder�sentences.����7 ����Many�imp���o��O rtant�p�rop���erties�of�the�functions�can�b�e�p��O roved�b�y����7 rst�Kko��O rder�reasoning.����7 ��Kk�Other�imp���o��O rtant�p�rop���erties�require��derived�functions.�����7 �color push Black���V,»3����� color pop����m�����2���7 �color push Black��� color pop�������x����1�r�color push Black� color pop���;�r�color push rgb 1 0 0�EXAMPLES�KkOF�LISP�FUNCTIONAL�PROGRAMS� color pop��1���7 �������7 �(defun�Kkapp���end�(u�v)����7 (if����7 (null�Kku)����7 v����7 (cons�Kk(ca��O r�u)�(app���end�(cdr�u)�v))))��9���7 �� �x�u������v� 1G� �� zo���N��q cmbx12�if��$ n��u���then��CR�v�� �P�else��;]�a��u�:��[�d��u���$7�v��ع]�is�a�pure�LISP����7 functional�Kkp��O rogram.����7 �� J��(�8�u�v��ع)(�u��/�����y��K� � cmsy8�0���(�v� �N�=�� v�if��%&�n��u���then��D:��v�� ��else��<f�a��u�:��[�d��u������y�0�� �3�v���ع])�is�an����7 0="" 1="" equation��qfo��o r�the�function�computed�b�y�the�p�rogram.�="" u�the�close����7="" co��o rresp����ondence�kkis�very�convenient�but�sometimes�confusing.�������7="" �color="" push="" black���v,»4�������="" color="" pop���������������������������������������������w�������2�����7="" black�����="" pop���������x����7="" ��a�the�pure�lisp�functional�p��o rogram�as�an�equation�p����ermits�con-������7="" venient�="" %p��o ro����ofs�in�a�="" rst�o�rder�theo�ry�that�lisp�p�rograms�meet����7="" their�="" ��sp����eci="" cations.�ύf��o o�r�example,�="" ێit�is�easy�to�p�rove�b�y�list�in-����7="" duction�kkthat��:����7="" �8�u� dkv����:�(�u�bs���v��)����w�="" �&�="�" �u����(�v�k���w���!�)),�="" �i.e.���that� dkapp����ending�lists�is�an����7="" asso����ciative�kkop�eration.�������7="" pop����������������������������������������������������2�����7="" pop���������x��������d��color="" black�="" pop�����d��color="" rgb="" 0�lisp�kkand�other�langua��o ges�="" pop��1�d��7="" ��="" #�ga��o rbage�collection,�="" zconditional�exp�ressions�and�recursive�p�ro-������7="" grams�kkhave�b����een�tak��o en�into�other�languages.��:����7="" ��kk�lisp�data�structures�have�b����een�imitated�clumsily�in�xml.����7="" (buy�kkitem1�item2�item3)����7="" �<�buy�="">�Kk�item1�item2�item3��<�/BUY�>����7 �� 0b�LISP� /�p��O rograms�having�access�to�the�abstract�syntax�of�the����7 p��O rogram��has�not�b���een�imitated.� �GThis�rep�resents�a�lack�of�imag-����7 ination,�?but��uI��^admit�I�don't�have�convincing�examples�of�its�use.�����7 �color push Black���V,»5����� color pop����9�����2���7 �color push Black��� color pop�������x�����a��color push Black� color pop����a��color push rgb 1 0 0�DERIVED�KkFUNCTIONS� color pop��1�d��7 The� e�computational�cost�of�a�Lisp�functional�recursive�p��O rogram����7 is�Kknot�determined�b��O y�the�extension�of�the�function.� 9W�e�have����7 �f�1ѹ91(�x�)��� ��+��if��#��x�>��100��Kkthen��=���x��H���10����else��>@�f��91(�f��91(�x��+�11))����7 and�Kk�f�1�f��91(�x�)��� ��+��if��#��x�>��100��then��=���x��H���10����else��>@91.��:��7 W��O e��Bhave��8�x:f�1ѹ91����y�0��G��(�x�)�wu=��f�f��91����y�0��G��(�x�)),���but��Bclea��O rly�the�functional�p�ro-����7 grams��sa��O re�di erent�computationally���#.� �PSupp���ose�w�e�a�re�interested����7 in� ��ho��O w�many�times�the�+�op���eration�is�executed�in�evaluating����7 �f�1ѹ91(�x�).� 9This�Kkis�given�b��O y��f��91�p����y�0��G��(�x�),�where����7 �f�1ѹ91�p�(�x�)� �[� ��=Ĺif��/E�x�>��100�� �ithen��D2�0�� �ielse��<t�1���+��f��91�p�(�f��91(�x��+�11))�+����7 0="" 1="" �f�1ѹ91�p�(�x��h�+�11).�������7="" �color="" push="" black���v,»6�������="" color="" pop���������������������������������������������o�������2�����7="" black�����="" pop���������x��������b�color="" black�="" pop����b�color="" rgb="" 0�elephant�kk2000:� 9a�p��o rogramming�language�fo�r�the�y�ea�r�2010�="" pop��="" ���^\www.fo��o rmal.stanfo�rd.edu="" jmc="" elephant.html��i�)��7="" ��="" +v�color="" 1�an�elephant�never�fo��o rgets.�="" pop��[an�elephant�p�rogram�can�sa�y���#,����7="" \a��="" passenger��!has�a�reservation�in�a�situation��s��if�he�has�made�a����7="" reservation��and�not�cancelled�it.�="" r�the�elephant�p��o rogram�need�not����7="" sp����ecify���a�data�structure�to�rememb�er�reservations.�="" y`the�compiler����7="" must�="" ��p��o rovide�the�necessa�ry�data�structures�so�that�whether�a����7="" passenger�kkhas�a�reservation�can�b����e�determined.��4ş8�í���􍍑���h��bas�(�passeng����er��i�;��vr���ieser�v�ation;��vs�)��������������(�9�s����y�0�� (�<��s�)�o���iccur�s�(�m��ak����es�(�passeng����er��i�;��vr�eser�v�ation�)�;��vs�)���������^:�(�9�s����y�00��="" �)(�s��<�s����y�00���="" �<�s����y�0��="" �a�^��h�o���iccur�s�(�c�hancel�<s�(�p��="" asseng����er��i�;��vr�eser�v�ation�)�;��vs����y�00��="" �)�����0:ፍ�jke�color="" black(1)�="" pop��������7="" black���v,»7�������="" pop�����������������������������������������������������2�����7="" pop���������x���4c�7="" �� `��color="" 1�an�elephant�is�faithful�one�hundred�p����ercent.�="" pop�o~a� `="" reservation��<<��7="" is�="" �!a�p��o romise�to�let�the�passenger�on�the�airplane�if�he�has�one����7="" when��fhe�sho��o ws�up.�="" �one�kind�of�elephant�output�statement�is�a����7="" p��o romise,�kkand�co�rrect�elephant�p�rograms�ful="" ll�their�p�romises.����7="" �the�elephant�language�includes�p��o rogram�statements�called����7="" commitments� �generalizing�flo��o yd�assertions,�="" ȅb����ecause�they�can����7="" refer���to�the�future,���a���co��o rrect�elephant�p�rogram�ful="" lls�its�com-����7="" mitments.��'�h����􍍑qđ(�8�s��="">�N��ow��!�)(�V��Hal�<sue�(�x�`�;��vs�)��>�V�al�<sue�(�x�`�;��vn��ow���!�))�������jke�color 0="" 1="" push="" black(2)�="" color="" pop����"�h��7="" ���ʹelephant�i-o�input�output�statments�a��o re�sp����eech�acts,�uqe.g.�="" kyques-����7="" tions,�r�requests,�acceptances�j�of�p��o rop����osals,�r�answ�ers�j�to�questions.����7="" answ��o ers�kkto�questions�should�b����e�true�and�resp�onsive.�������7="" �color="" black�����="" pop���������������������������������������������$��������2�����7="" pop���������~p��������color="" black�="" pop���="" ���color="" rgb="" 0�algol�kk48�="" pop��1�d��7="" if�="" hbw��o e�intro����duce�time�explicitly�as�distinct�from�the�p�rogram������7="" counter,�="" -�algolic�="" �bp��o rograms�can�b����e�written�as�sets�of�equations.����7="" here's�="" u�an�algol�60�p��o rogram�fo�r�computing�the�p�ro����duct��mn��of����7="" t��o w�o�kknatural�numb����ers.��+���������="" �star���it���:�����������՞�i������="" "�:="�����MK�n�;���������cv�p������" }<i���="�0�Kk�then�g����o�to�done�;���������՞�i������" black���v,»8�������="" pop���������������������������������������������)��������2�����7="" pop���������x����7="" �here's��_what�mathematicians�might�have�written�in�1948,��ab����efo��o re������7="" p��o rogramming�kklanguages�existed.��+������z�="">�pc�(0)������-�=��������0;��������B��i�(�t��H�+�1)������-�=���������if�����pc�(�t�)��=�0��Kkthen��=���n���������7 �else�Kkif��C��pc�(�t�)��=�4����then��E��i�(�t�)��H���1��Kkelse��5�ռi�(�t�);��������?W�p�(�t��H�+�1)������-�=���������if�����pc�(�t�)��=�1��Kkthen��=��0����������else�Kkif��E�~�pc�(�t�)��=�5��Kkthen��=���p�(�t�)��H+��m��Kk�else��5�ռp�(�t�)��������6.��pc�(�t��H�+�1)������-�=���������if�����pc�(�t�)��=�2��H�^��i�(�t�)��=�0��Kkthen��=��6����������Kelse�Kkif��Q�8�pc�(�t�)��=�5��Kkthen��=��2��Kkelse��5�ռpc�(�t�)��H+�1;������������color push Black(3)� color pop�������7 �color push Black��� color pop����,������2���7 �color push Black��� color pop��������if��7 �The� ڪp��O ro���of�that��9�t:�(�t�����0����^��pc�(�t�)��=�6����^��p�(�t�)��=��mn�)� ڪfollo�ws�from����7 the��#sentences�exp��O ressing�the�p�rogram�and�the�la�ws�of�a�rithmetic,����7 i.e.���no� �0theo��O ry�of�p�rogram�co�rrectness�is�needed.���Ho�w�ever,� ��the����7 p��O ro���of�7�ideas�a�re�essentially�the�same�as�those�used�to�p�rove�that����7 an� malgolic�p��O rogram�terminates�and�that�the�outputs�have�the����7 co��O rrect� :�relation�to�the�inputs.� ��Amir�Pnueli�and�Nissim�F�rancez����7 had��Kthis�idea�b���efo��O re�I��9did,��Cbut�they�mistak�enly�abandoned�it�fo�r����7 temp���o��O ral�Kklogic.�����7 �color push Black��� color pop����0i���;���7 ���N��q cmbx12���1lcmssi8��K� � cmsy8��K� �1cmsy8��2�1cmmi8�KtEo ��lcmss8�KtEo�1lcmss8�3��������</sue�(�x�`�;��vn��ow���!�))�������jke�color></sue�(�x�`�;��vs�)��></t�1���+��f��91�p�(�f��91(�x��+�11))�+����7></f�a��u�:��[�d��u������y�0�� �3�v���ع])�is�an����7></sist�(�cdr���e;��vu:t�i���m�e��s�></sist�(�cdr�7�e;��vu:dif�1�f��(�car�u;��vv���ع))�����7>