Herausforderung

Ihre Herausforderung besteht darin, einen Dolmetscher für eine Lispel-ähnliche Sprache zu entwerfen, die von nun an geprägt wird: GLisp . Der Programmcode für GLisp besteht aus einer beliebigen Anzahl geschachtelter Ausdrücke in Klammern in der folgenden Form:

(func arg1 arg2 ...)

Beachten Sie, dass der Interpreter vor und nach eckigen Klammern, Funktionen und Argumenten zusätzliche Leerzeichen zulassen muss.

Typen

Sie implementieren vier Typen: Integer, List, Boolean und Function. Ganzzahlen und Boolesche Werte können mit ihrer eigenen Syntax explizit in den Quellcode eingefügt werden. Ihr Interpreter muss davon ausgehen, dass eine Folge von numerischen Zeichen eine Ganzzahl darstellt (Sie müssen keine Syntax implementieren, um negative Ganzzahlen explizit einzufügen). Ihr Dolmetscher muss dies auch annehmen trueund falseals Boolesche Werte bezeichnet werden. Funktionen können vom Benutzer nicht explizit definiert werden und geben immer einen einzelnen Wert zurück (eine Liste beliebiger Länge zählt als ein einzelner Wert).

Funktionen

Die folgenden Funktionen müssen implementiert werden und haben das Format Funktion , Arität . Wenn nach einer Arität nein Pluszeichen folgt, bedeutet dies noder mehrere Argumente. Sie können davon ausgehen, dass alle Argumente für eine Funktion vom selben Typ sind, sofern nicht anders angegeben. Sie können auch davon ausgehen, dass kein Argument dieser Funktion jemals von diesem Typ sein wird, wenn für einen Certian-Typ kein Verhalten angegeben ist. In der folgenden Abbildung wird auf die Argumente Bezug genommen:

(func argument1 argument2 ... argumentn)

• + , 2+

  • Wenn alle Argumente vom Typ Integer sind , müssen Sie die Summe der Argumente zurückgeben
  • Wenn alle Argumente vom Typ Liste sind , müssen Sie die Verkettung der Argumente in aufsteigender Reihenfolge ( arg1+arg2+ ...) zurückgeben.
  • Wenn alle Argumente vom Typ Boolean sind , müssen Sie die logische Folge Alle der Argumente zurückgeben
  • (+ 1 2 3 4 5) -> 15
  • (+ (list 1 2) (list 3 4)) -> (list 1 2 3 4)
  • (+ true true true) -> true

• - , 2+

  • Wenn alle Argumente vom Typ Integer sind , müssen Sie die Differenz der Argumente ( arg1-arg2- ...) zurückgeben.
  • Wenn alle Argumente vom Typ Boolean sind , müssen Sie die logische Beliebige der Argumentfolge zurückgeben
  • (- 8 4 3) -> 1
  • (- 0 123) -> -123
  • (- true false false true false) -> true

• * , 2+

  • Wenn alle Argumente vom Typ Integer sind , müssen Sie das Produkt der Argumente zurückgeben
  • Wenn ein Argument vom Typ List und das andere vom Typ Integer ist (Sie können davon ausgehen, dass nur diese Argumente angegeben werden), müssen Sie wiederholt eine neue Liste mit den Elementen zurückgeben.arg1arg2
  • (* 1 2 3 4 5) -> 120
  • (* (list 1 2 3) 2) -> (list 1 2 3 1 2 3)

• / , 2+

  • Wenn alle Argumente vom Typ Integer sind , müssen Sie den Quotienten der Argumente ( arg/arg2/ ...) zurückgeben (Sie können davon ausgehen, dass die Division nacheinander erfolgt und der Dezimalteil bei jedem Schritt abgeschnitten wird).
  • Wenn ein Argument vom Typ List und das andere vom Typ Function ist , müssen Sie die resultierende List zurückgeben, nachdem arg2jeder Wert zugeordnet wurde
  • (/ 100 10 3) -> 3
  • (/ (list 1 2 3) inc) -> (list 2 3 4)

• % , 2

  • Wenn alle Argumente vom Typ Integer sind , müssen Sie den Modul der Argumente zurückgeben
  • (% 4 2) -> 0

• = , 2+

  • Wenn sowohl die Art und Wert aller Argumente gleich ist, müssen Sie true zurück. Andernfalls geben Sie false zurück.
  • (= 0 0 0) -> true
  • (= 0 false (list)) -> false

• Liste , 0+

  • Sie müssen eine Liste aller Argumente unabhängig vom Typ zurückgeben. Wenn keine Argumente angegeben werden, müssen Sie eine leere Liste zurückgeben
  • (list 3 4 (list 5)) -> (list 3 4 (list 5))

• inc , 1

  • Wenn das Argument vom Typ Integer ist , müssen Sie die Ganzzahl um eins erhöht zurückgeben
  • Wenn das Argument vom Typ Liste ist , müssen Sie die Liste um eine Drehung im Uhrzeigersinn drehen
  • (inc 1) -> 2
  • (inc (list 1 2 3)) -> (list 3 1 2)

• Dezember , 1

  • Wenn das Argument vom Typ Integer ist , müssen Sie die um eins dekrementierte Ganzzahl zurückgeben
  • Wenn das Argument vom Typ Liste ist , müssen Sie die Liste um eine einzelne Drehung gegen den Uhrzeigersinn drehen
  • (dec 1) -> 0
  • (dec (list 1 2 3)) -> (list 2 3 1)

• wenn , 3

  • Wenn Sie drei Argumente eines beliebigen Typs angeben : Wenn der Wahrheitswert von arg1wahr ist, geben Sie zurück arg2, andernfalls geben Sie zurückarg3
  • (if (not (list 1)) 8 false) -> false

• nicht , 1

  • Wenn ein Argument eines beliebigen Typs angegeben wird und der Wahrheitswert von arg1False ist, geben Sie zurück true, andernfalls geben Sie zurück false.
  • (not (list)) -> true

• len , 1

  • Wenn Sie ein Argument vom Typ List übergeben , geben Sie die Länge von zurückarg1
  • (len (list 4 2 true (list 3) (list))) -> 5

Wahrheitstabelle: 0, (list), false -> false, wo (list)bezeichnet eine leere Liste. Alles andere ist true.

Ihr Interpreter kann entweder ein vollständiges Programm sein, das die Quelleingabe aus stdin oder einer Datei liest, oder eine Funktion, die die Quelle als Zeichenfolge verwendet und den Ausgabewert zurückgibt.

Ist ersteres der Wahl der Ausgang für Integers ist einfach Zahlen, für Boolesche Werte ist trueoder falseund für Listen ist ein Raum Folge von Werten in Klammern getrennt sind (z. (1 2 3 4 (5 6 7))Bezeichnet (list 1 2 3 4 (list 5 6 7))).

Wenn Sie Letzteres auswählen, muss der Wert in dem entsprechenden Typ der Implementierungssprache oder, falls kein ähnlicher Typ vorhanden ist, in einem benutzerdefinierten Typ zurückgegeben werden. Listen können als Arrays oder Vektoren zurückgegeben werden , wenn die Sprache nicht hat Liste Typen, Boolesche Werte sollten als Typ Boolean in der Sprache zurückgegeben werden, oder einem benutzerdefinierten Typ , wenn die Sprache nicht unterstützt werden .

Testfälle

(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

Klarstellungen

• Ihr Interpreter behandelt möglicherweise ungültige Eingaben auf eine von Ihnen gewählte Weise, darf jedoch keine Ausnahme auslösen (es kann jedoch vorkommen, dass eine Fehlermeldung ausgegeben und der Vorgang reibungslos beendet wird).
• Funktionen werten Argumente immer von links nach rechts aus
• Eine ungültige Eingabe ist eine syntaktisch falsche Eingabe. Dies beinhaltet, ohne darauf beschränkt zu sein, nicht übereinstimmende Klammern, Division durch Null und teilweise angewendete Funktionen (außer für den Bonus).
• Für =, wenn eine der Werte unterschiedlich sind oder eine der Arten unterschiedlich sind, Rückkehrfalse

Boni

• Punktzahl * 0,8, wenn Sie teilweise angewandte Funktionen unterstützen. Zum Beispiel ((+ 2) 3)wäre das das gleiche wie (+ 2 3), erlaubt aber Dinge wie (/ (list 1 2 3) (+ 2)). Sie können davon ausgehen, dass eine Funktion teilweise angewendet wird, wenn sie weniger als die Mindestanzahl von Argumenten empfängt
• Ergebnis * 0,85, wenn Sie die Argumente, auf die angewendet wird, nur bewerten, ifwenn sie zurückgegeben werden

Das ist Code-Golf, also gewinnt der Interpreter mit der niedrigsten Bytezahl!

Haskell, 1370 1263 1179 1128 1163 1107 1084 Bytes * 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

Volles Programm, lesen stdinund schreiben stdout. gist auch die Funktionsversion.

Implementiert sowohl Teilfunktionen als auch die verzögerte Auswertung von if.

Probeläufe (der Funktionsversion):

λ: 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)

Jetzt hat alle Unit-Tests aus der Beschreibung:

λ: 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())

Generalüberholung. Wenn Sie die vorherigen Versionen anzeigen möchten, lesen Sie den Bearbeitungsverlauf .

Es gibt noch viel mehr zu golfen. Ich arbeite langsam daran.

Mit zlib / base64 erhalten wir 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="))

Hinweis: Wenn Sie sehen, dass meine Punktzahl steigt, liegt das wahrscheinlich daran, dass ich einige Fehler gefunden habe

Common Lisp, 868 Bytes * 0,85 = 737,8

Betrügt es, Lisp mit Lisp zu implementieren? Hier gibt es noch viel zu optimieren.

(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))

Gibt im Falle eines Eingabefehlers ein E aus. Probeläufe:

$ 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

eine ziemlich hackige Lösung. Dies speichert alles als Zeichenfolgen in ausgabebereiter Form - ihre Typen können durch den ersten Buchstaben unterschieden werden - 0..9für Zahlen, (für Listen toder ffür Boolesche Werte und alles andere für Funktionen.

Verwenden Sie zum Ausführen die rFunktion.