LISP McCarthy

39

McCarthy 1959 LISP

Pada awal 1959, John McCarthy menulis sebuah makalah yang mendefinisikan hanya sembilan fungsi primitif yang ketika disatukan masih membentuk dasar untuk semua bahasa seperti LISP saat ini. Makalah ini tersedia secara digital di sini:

http://www-formal.stanford.edu/jmc/recursive.pdf

Tugas Anda adalah untuk sepenuhnya menerapkan parser dan interpreter untuk LISP McCarthy persis seperti yang dijelaskan pada 1960 kertas: Artinya, fungsi QUOTE, ATOM, EQ, CAR, CDR, CONS, COND, LAMBDA, dan LABELsemua harus fungsional. Makalah ini akan didahulukan dari teks tantangan ini ketika mempertimbangkan kebenaran jawaban, tetapi saya telah mencoba merangkum sembilan fungsi di bawah ini. Perhatikan bahwa bahasa akan dalam SEMUA CAPS dan tidak perlu pengecekan kesalahan, semua input harus dianggap valid.

Jenis

  • Hanya ada dua jenis dalam LISP McCarthy: Sebuah atom, dan daftar terkait, yang secara rekursif didefinisikan sebagai kepala, yang mungkin daftar atau atom, dan daftar yang ditempelkan oleh kepala (ekor). NILmemiliki sifat khusus sebagai atom dan daftar.
  • Sesuai dengan makalahnya, nama atom hanya akan terdiri dari huruf kapital, angka, dan karakter spasi, meskipun string spasi berturut-turut harus dianggap hanya satu ruang dan semua karakter spasi awal dan akhir harus dihapus. Misalnya nama atom setara (ganti garis bawah dengan karakter spasi): ___ATOM__1__ = ATOM_1. Contoh bukan nama atom yang setara:A_TOM_1 != ATOM_1
  • Daftar dinotasikan dengan tanda kurung, dan tersirat NILdi akhir setiap daftar. Elemen dalam daftar dipisahkan oleh koma dan bukan spasi putih seperti di sebagian besar Lisps modern. Jadi daftarnya (ATOM 1, (ATOM 2))akan menjadi {[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}.

QUOTE:

  • Mengambil satu argumen yang bisa berupa atom (elemen tunggal) atau daftar tertaut. Mengembalikan argumen dengan tepat.
  • Kasus uji:
  • (QUOTE, ATOM 1) -> ATOM 1
  • (QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)

ATOM:

  • Mengambil satu argumen yang bisa berupa atom (elemen tunggal) atau daftar tertaut. Mengembalikan T(benar) jika argumennya adalah atom, atau NIL(salah) jika argumennya bukan atom.
  • Kasus uji:
  • (ATOM, (QUOTE, ATOM 1)) -> T
  • (ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL

EQ:

  • Membawa dua argumen yang harus berupa atom (perilaku tidak ditentukan jika salah satu argumen bukan atom). Mengembalikan T(benar) jika kedua atom itu setara, atau NIL(salah) jika tidak.
  • Kasus uji:
  • (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T
  • (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL

CAR:

  • Mengambil satu argumen yang harus berupa daftar (perilaku tidak terdefinisi jika bukan daftar). Mengembalikan atom (kepala) pertama dari daftar itu.
  • Kasus uji:
  • (CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1

CDR:

  • Mengambil satu argumen yang harus berupa daftar (perilaku tidak terdefinisi jika bukan daftar). Mengembalikan setiap atom kecuali atom pertama dari daftar, yaitu ekor. Perhatikan bahwa setiap daftar berakhir dengan tersirat NIL, jadi menjalankan CDRdaftar yang tampaknya hanya memiliki satu elemen akan kembali NIL.
  • Kasus uji:
  • (CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)
  • (CDR, (QUOTE, (ATOM 1))) -> NIL

CONS:

  • Membawa dua argumen. Yang pertama mungkin atom atau daftar tetapi yang kedua harus daftar atau NIL. Tambahkan argumen pertama ke argumen kedua dan kembalikan daftar yang baru dibuat.
  • Kasus uji:
  • (CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)
  • (CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)

COND:

  • Ini adalah semacam pernyataan "jika-lain" LISP. Membawa jumlah variabel-panjang argumen, yang masing-masing harus daftar panjang tepat 2. Untuk setiap daftar argumen secara berurutan, mengevaluasi istilah pertama dan jika itu benar (T), kembalikan istilah kedua yang terkait dan keluar dari fungsi . Jika istilah pertama tidak benar, lanjutkan ke argumen berikutnya dan uji kondisinya, dan seterusnya hingga kondisi benar pertama tercapai. Setidaknya salah satu syarat argumen dapat dianggap benar - jika semuanya salah, ini adalah perilaku yang tidak terdefinisi. Lihat halaman 4 untuk contoh yang baik tentang perilaku fungsi ini.
  • Kasus uji:
  • (COND, ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1)), ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2))) -> 1
  • (COND, ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2)), ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1))) -> 1

LAMBDA:

  • Menentukan fungsi anonim. Membawa dua argumen, yang pertama adalah daftar atom yang mewakili argumen untuk fungsi dan yang kedua adalah setiap ekspresi-S (fungsi tubuh), yang biasanya akan menggunakan argumen.
  • Kasus uji:
  • Menentukan dan menggunakan fungsi "isNull" anonim:
  • ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> T
  • ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, ATOM 1)) -> NIL

LABEL:

  • Memberikan nama ke LAMBDAfungsi anonim , yang juga memungkinkan fungsi itu disebut secara rekursif di tubuh LAMBDA. Membawa dua argumen, yang pertama menjadi label dan yang kedua adalah LAMBDAfungsi yang harus diikat label. Mengembalikan nama yang diberikan. Cakupan semua LABELnama adalah global, dan mendefinisikan ulang LABELperilaku tidak terdefinisi.
  • Kenyataan yang menyenangkan, LABELsebenarnya tidak diperlukan untuk membuat fungsi rekursif seperti yang kita ketahui sekarang LAMBDAdapat digunakan dengan 'Y-Combinator' untuk menyelesaikan tugas ini, tetapi McCarthy tidak mengetahui metode ini ketika menulis makalah aslinya. Itu membuat program lebih mudah untuk menulis.
  • Kasus uji:
  • (LABEL, SUBST, (LAMBDA, (X, Y, Z), (COND, ((ATOM, Z), (COND, ((EQ, Y, Z), X), ((QUOTE, T), Z))), ((QUOTE, T), (CONS, (SUBST, X, Y, (CAR, Z)), (SUBST, X, Y, (CDR, Z))))))) -> SUBST
  • (setelah menjalankan hal di atas) (SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)

Untuk membantu memvisualisasikan SUBSTfungsi di atas, bisa direpresentasikan sebagai pseudocode seperti-Python ini:

def substitute(x, y, z): # substitute all instances of y (an atom) with x (any sexp) in z
    if isAtom(z):
        if y == z:
            return x
        elif True: 
            return z
    elif True:
        return substitute(x,y,z[0]) + substitute(x,y,z[1:])

KASUS UJI AKHIR:

Jika saya telah menyalinnya dengan benar, penerjemah Anda harus dapat mengartikannya EVALdengan kode ini:

(LABEL, CAAR, (LAMBDA, (X), (CAR, (CAR, X))))
(LABEL, CDDR, (LAMBDA, (X), (CDR, (CDR, X))))
(LABEL, CADR, (LAMBDA, (X), (CAR, (CDR, X))))
(LABEL, CDAR, (LAMBDA, (X), (CDR, (CAR, X))))
(LABEL, CADAR, (LAMBDA, (X), (CAR, (CDR, (CAR, X)))))
(LABEL, CADDR, (LAMBDA, (X), (CAR, (CDR, (CDR, X)))))
(LABEL, CADDAR, (LAMBDA, (X), (CAR, (CDR, (CDR, (CAR, X))))))

(LABEL, ASSOC, (LAMBDA, (X, Y), (COND, ((EQ, (CAAR, Y), X), (CADAR, Y)), ((QUOTE, T), (ASSOC, X, (CDR, Y))))))

(LABEL, AND, (LAMBDA, (X, Y), (COND, (X, (COND, (Y, (QUOTE, T)), ((QUOTE, T), (QUOTE, NIL)))), ((QUOTE, T), (QUOTE, NIL)))))
(LABEL, NOT, (LAMBDA, (X), (COND, (X, (QUOTE, NIL)), ((QUOTE, T), (QUOTE, T)))))

(LABEL, NULL, (LAMBDA, (X), (AND, (ATOM, X), (EQ, X, (QUOTE, NIL)))))

(LABEL, APPEND, (LAMBDA, (X, Y), (COND, ((NULL, X), Y), ((QUOTE, T), (CONS, (CAR, X), (APPEND, (CDR, X), Y))))))

(LABEL, LIST, (LAMBDA, (X, Y), (CONS, X, (CONS, Y, (QUOTE, NIL))))) 

(LABEL, PAIR, (LAMBDA, (X, Y), (COND, ((AND, (NULL, X), (NULL, Y)), (QUOTE, NIL)), ((AND, (NOT, (ATOM, X)), (NOT, (ATOM, Y))), (CONS, (LIST, (CAR, X), (CAR, Y)), (PAIR, (CDR, X), (CDR, Y)))))))

(LABEL, EVAL, (LAMBDA, (E, A), (COND, ((ATOM, E), (ASSOC, E, A)), ((ATOM, (CAR, E)), (COND, ((EQ, (CAR, E), (QUOTE, QUOTE)), (CADR, E)), ((EQ, (CAR, E), (QUOTE, ATOM)), (ATOM, (EVAL, ((CADR, E), A)))), ((EQ, (CAR, E), (QUOTE, EQ)), (EQ, (EVAL, (CADR, E, A)), (EVAL, (CADDR, E, A)))), ((EQ, (CAR, E), (QUOTE, COND)), (EVCON, (CDR, E), A)), ((EQ, (CAR, E), (QUOTE, CAR)), (CAR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CDR)), (CDR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CONS)), (CONS, (EVAL, (CADR, E), A), (EVAL, (CADDR, E), A))), ((QUOTE, T), (EVAL, (CONS, (ASSOC, (CAR, E), A), (EVLIS, (CDR, E), A)), A)))), ((EQ, (CAAR, E), (QUOTE, LABEL)), (EVAL, (CONS, (CADDAR, E), (CDR, E)), (CONS, (CONS, (CADAR, E), (CONS, (CAR, E), (CONS, A, (QUOTE, NIL))))))), ((EQ, (CAAR, E), (QUOTE, LAMBDA)), (EVAL, (CADDAR, E), (APPEND, (PAIR, (CADAR, E), (EVLIS, (CDR, E), A)), A))))))

(LABEL, EVCON, (LAMBDA, (C, A), (COND, ((EVAL, (CAAR, C), A), (EVAL, (CADAR, C), A)), ((QUOTE, T), (EVCON, (CDR, C), A)))))

(LABEL, EVLIS, (LAMBDA, (M, A), (COND, ((NULL, M), (QUOTE, NIL)), ((QUOTE, T), (CONS, (EVAL, (CAR, M), A), (EVLIS, (CDR, M), A))))))

Setelah menjalankan raksasa itu, baris ini akan kembali (A, B, C):

(EVAL, (QUOTE, (CONS, X, (QUOTE, (B, C)))), (QUOTE, ((X, A), (Y, B))))

Namun, mengutip John McCarthy sendiri di halaman 16, sepertinya dia kehabisan karakter di komputernya:

Jika lebih banyak karakter tersedia di komputer, itu dapat ditingkatkan ...

Oleh karena itu, tantangan ini ditandai dengan kode-golf dan jawaban terpendek dalam karakter akan menjadi pemenang. Celah standar berlaku. Semoga berhasil!

Catatan tentang String Evals : Saya mengerti bahwa beberapa berpikir mungkin untuk memenangkan tantangan ini dengan menggunakan Lisp dan memodifikasi sintaks agar sesuai dengan bahasa host dan kemudian menggunakan string (eval). Saya tidak terlalu yakin bahwa pendekatan ini akan selalu menang terutama dengan aturan penamaan pengidentifikasi, dan bahkan jika saya pikir larangan string evaldalam semua bahasa akan menjadi kemiringan subyektif dan licin. Tetapi saya tidak ingin menghukum orang karena melakukan tantangan ini dengan cara yang 'benar', jadi saya dapat mengizinkan dua pemenang untuk tantangan ini, satu dalam bahasa mirip Lisp dan satu dalam bahasa non-Lispy, jika ini menjadi masalah .

code-golf interpreter lisp Harry
sumber
1
Anda memiliki contoh Lambda yang mendefinisikan fungsi "IsNull", tetapi sepertinya Nil mengembalikan Nil, ketika bagi saya sepertinya harus mengembalikan T?
nmjcman101
1
Anda memiliki ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> NILDi mana (QUOTE NIL)pada akhirnya adalah input, jadi ini harus kembali T?
nmjcman101
1
Benar, tetapi Anda sudah menulis-> NIL
nmjcman101
1
Dalam uraian CONSAnda, ucapkan "Tambahkan argumen pertama ke argumen kedua dan kembalikan daftar yang baru dibuat," tetapi kasus uji menunjukkan argumen kedua ditambahkan ke argumen pertama. Yang mana yang benar?
Jordan
1
Saya mendasarkan implementasi saya pada tutorial lisp kjetilvalle , dan sintaksinya sedikit berbeda. Huruf kecil digunakan dan tidak ada koma. Bisakah saya menjalankan transformasi huruf kecil dan menghapus koma dari string input sehingga lebih atau kurang sesuai dengan desain juru bahasa di atas? Saya cukup baru di Lisp, tetapi ingin menjelajahi tantangan ini dalam bahasa saya sendiri. Sejauh ini saya sudah mengimplementasikan parser . (Bahasa saya terlihat seperti Lisp, tetapi diimplementasikan dalam Node.js)
Andrakis

Jawaban:

17

Python 3, 770 byte

Ini adalah REPL di stdin / stdout. Diharapkan setiap baris menjadi pernyataan lengkap atau kosong. evaldigunakan untuk mempersingkat implementasi, tetapi sebaliknya tidak diperlukan untuk logika.

import re,sys;S=re.sub
P=lambda l:eval(S("([A-Z0-9][A-Z0-9 ]*)",r"' '.join('\1'.strip().split())",S("NIL","()",S("\)",",)",l))))
d={"QUOTE":'(v,L[1])[1]',"EQ":'[(),"T"][E(L[1],v)==E(L[2],v)]',
"CDR":'E(L[1],v)[1:]',"CONS":'(E(L[1],v),)+E(L[2],v)',"CAR":'E(L[1],v)[0]',
"LAMBDA":'("#",)+L[1:]',"LABEL":'[v.update({L[1]:E(L[2],v)}),L[1]][1]'}
def E(L,v):
 if L*0=="":return v[L]
 elif L[0]in d:return eval(d[L[0]])
 elif L[0]=="COND":return next(E(l[1],v)for l in L[1:]if E(l[0],v)=="T")
 elif L[0]=="ATOM":o=E(L[1],v);return[(),"T"][o*0in["",o]]
 else:l=E(L[0],v);n=v.copy();n.update({a:E(p,v)for a,p in zip(l[1],L[1:])});return E(l[2],n)
R=lambda o:o==()and"NIL"or 0*o==()and"(%s)"%", ".join(R(e)for e in o)or o
g={}
for l in sys.stdin:
 if l.strip():print(R(E(P(l),g)))
orlp
sumber
1
@ Harry Dua test case pertama berfungsi setelah memperbaiki bug kecil yang saya perkenalkan di sentuhan akhir. Eval itu bekerja dengan sempurna. Tapi SUBSTcontohnya masih rusak (setahu saya) sebagai testcase. Salah satu dari CONDmencapai akhir sebelum menemukan a T.
orlp
1
Terima kasih telah memperbaikinya! Ini sangat mengesankan! Ini berfungsi untuk saya di semua testcases sekarang, termasuk EVAL(sangat terkejut saya mendapatkannya tepat pada percobaan pertama!) Saya akan memberi Anda hadiah dan jawaban yang diterima sekarang!
Harry
2
Saya juga suka R(E(P(l)pengaturan ;-)
Harry
2
@ Harry, aku bercanda bukan itu kecelakaan! R = repr, E = eval, P = parse, l = line.
orlp
4
Hanya ingin memberi tahu Anda, saya menulis sebuah artikel yang menyebutkan implementasi Anda di sini !
Harry