Wyzwanie

Wyzwanie polega na zaprojektowaniu interpretera języka przypominającego seplenienie, który odtąd zostanie ukuty: GLisp . Kod programu dla GLisp będzie składał się z dowolnej liczby zagnieżdżonych wyrażeń oznaczonych nawiasami, w następującej formie:

(func arg1 arg2 ...)

Zauważ, że interpreter musi uwzględniać zewnętrzne znaki spacji przed i po nawiasach, funkcjach i argumentach.

Rodzaje

Zaimplementujesz cztery typy: Integer, List, Boolean i Function. Wartości całkowite i logiczne można jawnie wstawiać do kodu źródłowego z ich własną składnią. Twój tłumacz musi założyć, że ciąg znaków numerycznych oznacza liczbę całkowitą (nie musisz implementować składni, aby jawnie wstawić ujemne liczby całkowite). Twój tłumacza musi również założyć, że truei falsesą wyznaczone wartości logiczne. Funkcje nie mogą być wyraźnie zdefiniowane przez użytkownika i zawsze zwracają pojedynczą wartość (Lista o dowolnej długości liczy się jako pojedyncza wartość).

Funkcje

Wymagane są następujące funkcje, które mają format Funkcja , Arity . Jeśli przed Arity nwystępuje znak plus, oznacza to nlub więcej argumentów. Możesz założyć, że wszystkie argumenty podane funkcji są tego samego typu, chyba że podano inaczej. Możesz również założyć, że jeśli nie zostanie określone zachowanie dla typu certyfikatu, możesz założyć, że żaden argument tej funkcji nigdy nie będzie tego typu. Argumenty będą nazywane jak na poniższym diagramie:

(func argument1 argument2 ... argumentn)

• + , 2+

  • Jeśli wszystkie argumenty są typu Integer , musisz zwrócić sumę argumentów
  • Jeśli wszystkie argumenty są typu List , należy zwrócić konkatenację argumentów w porządku rosnącym ( arg1+arg2+ ...)
  • Jeśli wszystkie argumenty są typu Boolean , musisz zwrócić logiczną Wszystkie sekwencje argumentów
  • (+ 1 2 3 4 5) -> 15
  • (+ (list 1 2) (list 3 4)) -> (list 1 2 3 4)
  • (+ true true true) -> true

• - , 2+

  • Jeśli wszystkie argumenty są typu Integer , musisz zwrócić różnicę argumentów ( arg1-arg2- ...)
  • Jeśli wszystkie argumenty są typu Boolean , musisz zwrócić logiczną Dowolną z sekwencji argumentów
  • (- 8 4 3) -> 1
  • (- 0 123) -> -123
  • (- true false false true false) -> true

• * , 2+

  • Jeśli wszystkie argumenty są typu Integer , musisz zwrócić iloczyn argumentów
  • Jeśli jeden argument jest typu List, a drugi jest liczbą całkowitą (możesz założyć, że będą to jedyne podane argumenty), musisz zwrócić nową Listę z elementami w arg1powtarzanych arg2czasach.
  • (* 1 2 3 4 5) -> 120
  • (* (list 1 2 3) 2) -> (list 1 2 3 1 2 3)

• / , 2+

  • Jeśli wszystkie argumenty są tego samego typu Integer , musisz zwrócić iloraz argumentów ( arg/arg2/ ...) (możesz założyć, że dzielenie jest wykonywane sekwencyjnie, a część dziesiętna na każdym kroku jest obcinana)
  • Jeśli jeden argument jest typu List, a drugi jest typu Funkcja , musisz zwrócić wynikową Listę po arg2odwzorowaniu na każdą wartość
  • (/ 100 10 3) -> 3
  • (/ (list 1 2 3) inc) -> (list 2 3 4)

• % , 2

  • Jeśli wszystkie argumenty są typu Integer , musisz zwrócić moduł argumentów
  • (% 4 2) -> 0

• = , 2+

  • Jeśli zarówno typ, jak i wartość wszystkich argumentów są takie same, musisz zwrócić wartość true. W przeciwnym razie zwróć false.
  • (= 0 0 0) -> true
  • (= 0 false (list)) -> false

• lista , 0+

  • Musisz zwrócić listę wszystkich argumentów, niezależnie od typu. Jeśli nie podano żadnych argumentów, musisz zwrócić pustą listę
  • (list 3 4 (list 5)) -> (list 3 4 (list 5))

• inc , 1

  • Jeśli argument jest typu Integer , musisz zwrócić całkowitą powiększoną o jeden
  • Jeśli argument jest typu List , musisz zwrócić listę obróconą zgodnie z ruchem wskazówek zegara o jeden obrót
  • (inc 1) -> 2
  • (inc (list 1 2 3)) -> (list 3 1 2)

• dec , 1

  • Jeśli argument jest typu Integer , musisz zwrócić całkowitą pomniejszoną o jeden
  • Jeśli argument jest typu List , musisz zwrócić listę obróconą w lewo o jeden obrót
  • (dec 1) -> 0
  • (dec (list 1 2 3)) -> (list 2 3 1)

• gdyby 3

  • Jeśli podano trzy argumenty dowolnego typu: Jeśli wartość prawdy arg1to prawda, zwróć arg2, w przeciwnym razie zwróćarg3
  • (if (not (list 1)) 8 false) -> false

• nie , 1

  • Jeśli podano argument dowolnego typu, jeśli wartość prawdy arg1to False, zwróć true, w przeciwnym razie zwróć false.
  • (not (list)) -> true

• len , 1

  • Jeśli podano argument typu List , zwróć długośćarg1
  • (len (list 4 2 true (list 3) (list))) -> 5

Tabela prawdy:, 0, (list), false -> falsegdzie (list)oznacza pustą listę. Wszystko inne jest true.

Twój interpreter może być pełnym programem, który odczytuje dane źródłowe ze standardowego wejścia lub pliku, lub funkcją, która pobiera źródło jako ciąg znaków i zwraca wartość wyjściową.

Jeśli wybierzesz to pierwsze, wynikiem dla liczb całkowitych są po prostu liczby, dla booleanów jest truelub false, a dla list jest oddzielona spacjami sekwencja wartości ujęta w nawiasy (np. (1 2 3 4 (5 6 7))Oznaczenia (list 1 2 3 4 (list 5 6 7))).

Jeśli wybierzesz ten drugi, wartość musi zostać zwrócona w odpowiednim typie języka implementacji lub, jeśli nie istnieje podobny typ, typ niestandardowy. Listy mogą być zwracane jako tablice lub wektory, jeśli język nie ma typu listy , booleany powinny być zwracane jako typ boolowski w języku lub typ niestandardowy, jeśli język ich nie obsługuje.

Przypadki testowe

(list 1 2 3 (list 4 5 true))  -> (1 2 3 (4 5 true))
(/ 4000 (+ 1 2 3 4 (* 5 8)))  -> 80
(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)  -> true
(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))  -> 5

Wyjaśnienia

• Twój tłumacz może radzić sobie z nieprawidłowymi danymi wejściowymi w dowolny sposób, ale nie może zgłaszać wyjątku (może jednak wydrukować komunikat o błędzie i wyjść płynnie)
• Funkcje zawsze oceniają argumenty od lewej do prawej
• Nieprawidłowe dane wejściowe to wszelkie dane wejściowe, które są niepoprawne pod względem składniowym. Obejmuje to między innymi niedopasowane nawiasy klamrowe, dzielenie przez zero i funkcje częściowo zastosowane (chyba że skorzystają z premii)
• W przypadku =, jeśli wartości są różne i każdy z rodzajów są różne, zwrotfalse

Bonusy

• Ocena * 0,8, jeśli wspierasz częściowo zastosowane funkcje. Na przykład ((+ 2) 3)byłoby to samo (+ 2 3), ale dopuszcza takie rzeczy jak (/ (list 1 2 3) (+ 2)). Możesz założyć, że funkcja jest częściowo zastosowana, jeśli otrzyma mniej niż minimalną liczbę argumentów
• Wynik * 0,85, jeśli nie ocenisz argumentów zastosowanych, ifchyba że zostaną zwrócone

To jest golf golfowy, więc wygrywa interpreter z najmniejszą liczbą bajtów!

Haskell, 1370 1263 1179 1128 1163 1107 1084 bajtów * 0,8 * 0,85 = 737,12

import Text.Parsec
data V=I Int|L[V]|T|F|P[V]|X|A|S|M|D|U|E|Q|J|K|C|N|W deriving Eq
m Q=0;m C=3;m f|f`elem`[J,K,N,W]=1;m _=2
l=length
x v=[n|I n<-v]
y v=[l|L l<-v]
z v=[0<1|T<-v]++[1<0|F<-v]
(&)f=l.f>>=(.l).(==)
b a|a=T|0<1=F
s(I n)=show n
s(L v)='(':tail(v>>=(' ':).s)++")"
s T=d!!0;s F=d!!1;s _="error"
i(L v)=e$i%v
i v=v
e(P v:a)=e$v++a
e(f:a)|m f>l a=P(f:a)
e(A:a)|x&a=I$sum$x a|y&a=L$concat$y a|z&a=b$and$z a
e(S:a)|x&a=I$f$x a|z&a=b$or$z a
e(M:a)|x&a=I$product$x a
e[M,v,I n]=e$A:replicate n v
e(D:a)|x&a=I$v$x a
e[D,L v,f]=L$map(\a->e[f,a])v
e[U,I a,I b]=I$a`mod`b
e(E:a:v)=b$all(==a)v
e(Q:a)=L a
e[J,I a]=I$a+1
e[J,L[]]=L[]
e[J,L v]=L$last v:init v
e[K,I a]=I$a-1
e[K,L v]=L$drop 1 v++take 1 v
e[C,a,b,c]|a`elem`[I 0,L[],F]=c|0<1=b
e[N,a]=e[C,a,F,T]
e[W,L v]=I$l v
e _=X
f(a:b)=a-sum b
v(a:b)=foldl div a b
(%)f=fmap f
p=k$choice$try%([(I .read)%many1 digit,L%between(w"(")(k$w")")(many$try p)]++zipWith((.return).(>>).w)d[T,F,A,S,M,D,U,E,Q,J,K,C,N,W])
k=(spaces>>)
w=string
d=words"true false + - * / % = list inc dec if not len"
g=either show(s.i).parse p""
main=interact g

Pełny program, czytanie stdini pisanie do stdout. gjest również wersją funkcji.

Implementuje zarówno funkcje częściowe, jak i leniwą ocenę if .

Przykładowe przebiegi (w wersji funkcji):

λ: g "(list 1 2 3 (list 4 5 true))"
(1 2 3 (4 5 true))

λ: g "(/ 4000 (+ 1 2 3 4 (* 5 8)))"
80

λ: g "(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)"
true

λ: g "(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))"
5

λ: g "(if false (/ 1 0) 5)"
5

λ: g "((+ 2) 3)"
5

λ: g "(/ (list 1 2 3) (+ 2))"
(3 4 5)

Teraz ma wszystkie testy jednostkowe z opisu:

λ: runTests 
passed: g "(+ 1 2 3 4 5)" ==> 15
passed: g "(+ (list 1 2) (list 3 4))" ==> (1 2 3 4)
passed: g "(+ true true true)" ==> true
passed: g "(- 8 4 3)" ==> 1
passed: g "(- 0 123)" ==> -123
passed: g "(- true false false true false)" ==> true
passed: g "(* 1 2 3 4 5)" ==> 120
passed: g "(* (list 1 2 3) 2)" ==> (1 2 3 1 2 3)
passed: g "(/ 100 10 3)" ==> 3
passed: g "(/ (list 1 2 3) inc)" ==> (2 3 4)
passed: g "(% 4 2)" ==> 0
passed: g "(= 0 0 0)" ==> true
passed: g "(= 0 false (list))" ==> false
passed: g "(list 3 4 (list 5))" ==> (3 4 (5))
passed: g "(inc 1)" ==> 2
passed: g "(inc (list 1 2 3))" ==> (3 1 2)
passed: g "(dec 1)" ==> 0
passed: g "(dec (list 1 2 3))" ==> (2 3 1)
passed: g "(if (not (list 1)) 8 9)" ==> 9
passed: g "(not (list))" ==> true
passed: g "(len (list 4 2 true (list 3) (list)))" ==> 5
passed: g "(list 1 2 3 (list 4 5 true))" ==> (1 2 3 (4 5 true))
passed: g "(/ 4000 (+ 1 2 3 4 (* 5 8)))" ==> 80
passed: g "(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)" ==> true
passed: g "(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))" ==> 5
passed: g "(if false (/ 1 0) 5)" ==> 5
passed: g "((+ 2) 3)" ==> 5
passed: g "(/ (list 1 2 3) (+ 2))" ==> (3 4 5)

Python 2, 1417 * 0,8 * 0,85 = 963,56

from operator import*
A=type;K="list"
def E():print"E";exit()
def R(G):
 len(G)or E();T=G.pop(0);L=[]
 if"("==T:
  G or E()
  while")"!=G[0]:L+=[R(G)];G or E()
  G.pop(0);return L
 if")"==T:E()
 try:
  x=eval(T.title())
  if Q(x)<2:return x
  E()
 except:return T
H="+ - * / = % if inc dec not len"
Z=lambda y:lambda x:reduce(y,x)
D=dict(zip(H.split(),[[sum,any,0,lambda x:sum((y[1:]for y in x),[K])],[Z(sub)],[Z(mul),all,0,lambda x:x[0][:1]+x[0][1:]*x[1]],[Z(div),lambda x:[K]+map(lambda z:S([x[1],z]if Q(x[1])==2else x[1]+[z]),x[0][1:])],[lambda x:len(set(map(str,x)))<2]*6,[lambda x:x[0]%x[1]],[lambda x:S(x[2])if S(x[0])in[0,[K]]else S(x[1])]*6,[lambda x:x[0]+1,0,0,lambda x:x[0][:1]+x[0][-1:]+x[0][1:-1]],[lambda x:x[0]-1,0,0,lambda x:x[0][:1]+x[0][2:]+[x[0][1]]],[lambda x:x[0]in[0,[K]]]*6,[0]*3+[lambda x:len(x)-1]]))
H=H[:15]+H+" if"
def Q(x):
 t=A(x);w=int,bool,str
 if t in w:return w.index(t)
 if t==list and x:return 5-(2*(x[0]==K)+(str==A(x[0])and len(x)<H.count(x[0])+1))
 E()
def S(G):
 if Q(G)<2:return G
 G or E();c=G[0];r=G[1:];c==K or r or E()
 if c!="if":r=[x if Q(x)in{2,4}else S(x)for x in r]
 if c==K:return[c]+r
 k=map(Q,r);m=min(k);M=max(k);v=[m,[-1,3][{m,M}=={4,5}]][m!=M]
 try:return D[c][v](r)
 except:E()
def C(x):return"(%s)"%" ".join(map(C,x))if A(x)==list else str(x).lower()
def I(G):
 for c in"+-*/%=()":G=G.replace(c," %s "%c)
 return C(S(R(G.strip().split())))
print I(raw_input())

Całkowity remont. Jeśli chcesz zobaczyć poprzednie wersje, sprawdź historię edycji .

Jest o wiele więcej do gry w golfa. Powoli nad tym pracuję.

Z zlib / base64 otrzymujemy 1093 * 0,8 * 0,85 = 743,24 :

import base64,zlib
exec zlib.decompress(base64.b64decode("eJx9VE1P4zAQvedXGEuV7MbttgX2kOADAtSugANbTljWKqSuNku+5Lg0BfHfd8ZJCwjt9tLpdN6bmTczXtuqIFVtbOIqS7KirqwbBufS7WoTX0uaZ42jwcqsyRXjUW2z0tErGps2c4x7/08251FAclOCARwQF9/L+biuajbh8Y1UOiDZmjIq5T0EkjnposDc/s5yQzk9knM10dFNKBXS6fhDzIHJGrexJbnxbNyz+Qhnd0jbSvOc5Ox+7DKXG8YRm63JHWv52SzqwS04Pci0qand3n0fLCQNyYgMyTciyQCBWZmSlUlJWTlsjgYPMk+Kx1VCdlFvtIBfbVLDdqLlwaVcZaljL1nNFuOmzlEhoVSzKURS7sREHFDgYmynppFeQ5s7SEVaCL3WXAv1wJrNY2cUm5yLJM8/YlsQSkVTHXoDKIatmmofvsqe+Xsg0IVFUrPe8RItmcJQ8aI7WcDmUs5M3hiCP0L1ornY02IFBy4cbmMcQ77GWeiWg6h6+P1DDAIHfS0H5xLSzDSHhGhNwCrVBDvVPu2yq+IrUTiFnv/Z9Qjq2/c/+pwQvaP/gmeAVR1Yf4EeyvMlTfTwOPysQssxISzXQi6A81SHi5DiQvpbwGWDXXTyHIx4K+FaxGNV5QJEw7UlDme93a/ddpyVK9Myx7s/pcRzI0m58qvlY05HbDb02kl5zUOUXyI9iomBXVFni3FabUrX+cMpbv9Vf6DL7kD90OcfbmEeHE4xTv0Bxha+QFv4Ka/xL3s4Q0CnR5JCo5GVqt1fVla+zsTJ236YHPe5xR6t7jBA1OdTqQ5BhCeJS3QnLI8LWWQle+LxLfhaNJ6lKgSMVxxr9VqI2zcpX0/E6ZvWqjiSt7o79r7+S2BUz5rZ93Pet3yBc+jCKBs0nA4ooeM/FaTD7Be4wFAdTqnX3HcA2oJnnFdbY3umH5142FcKfdFwNPw2kIzTaA5vnDV1nsD9p4KSQUPoIIVa+vIu2JLBYzYGUngR+P5FgE/gn1Ggtsn2V1bWG3T/BUW+qRU="))

Uwaga: jeśli zauważysz, że mój wynik rośnie, to prawdopodobnie dlatego, że znalazłem kilka błędów

Common Lisp, 868 bajtów * 0,85 = 737,8

Czy to oszustwo, aby wdrożyć Lisp z Lisp? Nadal wiele do optymalizacji.

(SETF (READTABLE-CASE *READTABLE*) :PRESERVE)(PRINC(LABELS((B(X)(FIND X'(true false)))(R(X)(IF X'true'false))(V(X)(MEMBER X'(0()false)))(A(&REST X)(R(NOTANY #'V X)))(O(&REST X)(R(NOTEVERY #'V X)))(E(X &KEY N)(IF(LISTP X)(ECASE(FIRST X)(+(APPLY(IF(EVERY'NUMBERP #1=(MAPCAR(IF N #'IDENTITY #'E)(CDR X)))'+(IF(EVERY'LISTP #1#)'APPEND #'A))#1#))(-(APPLY(IF(EVERY'NUMBERP #1#)'- #'O)#1#))(*(IF(LISTP #2=(CAR #1#))(LOOP FOR I TO(1-(CADR #1#))APPEND #2#)(APPLY'* #1#)))(/(IF(LISTP #2#)(LOOP FOR I IN #2#COLLECT(E `(,(CADR #1#),I):N T))(REDUCE'FLOOR #1#)))(%(APPLY'MOD #1#))(=(R(LOOP FOR I IN(CDR #1#)ALWAYS(EQUAL I #2#))))(list #1#)(inc(IF(LISTP #2#)(APPEND(LAST #2#)(BUTLAST #2#))(1+ #2#)))(dec(IF(LISTP #2#)(APPEND(CDR #2#)`(,(FIRST #2#)))(1- #2#)))(if(IF(V(E(CADR X)))(E(CADDDR X))(E(CADDR X))))(not(R(V #2#)))(len(LENGTH #2#)))X)))(OR(IGNORE-ERRORS(OR(E(READ))"()")):E))

Drukuje literę E w przypadku błędu wejścia. Przykładowe przebiegi:

$ sbcl --script glisp.lisp
(list 1 2 3 (list 4 5 true))
(1 2 3 (4 5 true))

$ sbcl --script glisp.lisp
(/ 4000 (+ 1 2 3 4 (* 5 8)))
80

$ sbcl --script glisp.lisp
(+ (not (- (len (list 5 6 7)) (/ 10 3))) true)
true

$ sbcl --script glisp.lisp
(if (           len (list )  ) 4 (if    (+ (= 8 8    8) (not (list 4))) 8 5))
5

$ sbcl --script glisp.lisp
(this is an error)
E

$ sbcl --script glisp.lisp
(if (% 4 2) (this is an error) 42)
42

Haskell, 972

r=fst.f
f('(':s)|(f:a,b)<-g s=(f%filter(/="")a,b)
f s=span(`notElem`" ()")s
j=dropWhile(==' ')
g""=([],"")
g s|')':l<-r=([x],l)|(y,t)<-g$j r=(x:y,t)where(x,r)=f$j s
"%"%c=show$foldr(mod.read)(maxBound::Int)c
"+"%c|t(c!!0)<1="(list "++tail(c>>=(' ':).drop 6.init)++")"|t(c!!0)<2=show$sum$map read c|0<1=i$all((=='t').head)c
"-"%c|t(c!!0)<2=show$foldl1(-)$map read c|0<1=i$any((=='t').head)c
"*"%c=fst$f$"(+ "++unwords([1..read$last c]>>init c)++")"
"="%c=i$all(==c!!0)c
"/"%c|t(c!!0)<1,[a,b]<-c="list"%map(\x->b%[x])(fst$g$drop 6 a)|0<1=show$foldl1 div$map read c
"if"%[p,a,b]|elem p["0","()","false"]=b|0<1=a
"list"%c="(list "++unwords c++")"
"len"%[c]=show$length(words c)-1
"inc"%[c]|t c>0=show$read c+1|([],_)<-g$drop 6 c="(list)"|(x,_)<-g$drop 6 c="list"%(last x:init x)
"dec"%[c]|t c<1,(x,_)<-g$drop 6 c="list"%(drop 1 x++take 1 x)|0<1=show$read c-1
"not"%[c]="if"%[c,"false","true"]
s%c="?"
i p|p="true"|0<1="false"
t('(':_)=0
t(c:s)|c<':',c>'/'=1|elem c"th"=2
t _=3

dość hacky rozwiązanie. przechowuje to wszystko jako ciągi znaków w postaci gotowej do wyjścia - ich typy można rozróżnić po pierwszej literze - 0..9dla liczb, (dla list tlub fdla boolanów i wszystko inne dla funkcji.

aby uruchomić użyj rfunkcji.