That's almost Lisp!

Question

Challenge

Your challenge is to design an interpreter for a lisp-like language, which will from hence forth be coined: GLisp. The program code for GLisp will consist of an arbitrary amount of nested expressions denoted by brackets, in the following form:

(func arg1 arg2 ...)

Note that the interpreter must allow for extraneous whitespace characters before and after brackets, functions, and arguments.

Types

You will implement four types, Integer, List, Boolean, and Function. Integers and Boolean values can be explicitly inserted into source code with their own syntax. Your interpreter must assume that a run of numeric characters denotes an Integer (you do not have to implement a syntax to explicitly insert negative integers). Your interpreter must also assume that true and false are designated Boolean values. Functions can not be explicitly defined by the user, and will always return a single value (a List of any length counts as a single value).

Functions

The following functions are required to be implemented, and are in the format Function, Arity. If an Arity n is proceeded by a plus sign, then that denotes n or more arguments. You may assume that all arguments given to a function are of the same type, unless specificed otherwise. You may also assume that if no behaviour is specified for a certian type, then you may assume that no argument of that function will ever be of that type. Arguments will be referred to as in the following diagram:

(func argument1 argument2 ... argumentn)

• +, 2+

  • If all arguments are of the type Integer, you must return the sum of the arguments
  • If all arguments are of the type List, you must return the concatenation of the arguments in ascending order (arg1+arg2+ ...)
  • If all arguments are of the type Boolean, you must return the logical All of the sequence of arguments
  • (+ 1 2 3 4 5) -> 15
  • (+ (list 1 2) (list 3 4)) -> (list 1 2 3 4)
  • (+ true true true) -> true

• -, 2+

  • If all arguments are of the type Integer, you must return the difference of the arguments (arg1-arg2- ...)
  • If all arguments are of the type Boolean, you must return the logical Any of the sequence of arguments
  • (- 8 4 3) -> 1
  • (- 0 123) -> -123
  • (- true false false true false) -> true

• *, 2+

  • If all arguments are of type Integer, you must return the product of the arguments
  • If one argument is of type List and the other is of type Integer (you may assume that these will only be the only arguments given), you must return a new List with the items in arg1 repeated arg2 times.
  • (* 1 2 3 4 5) -> 120
  • (* (list 1 2 3) 2) -> (list 1 2 3 1 2 3)

• /, 2+

  • If all arguments are of the type Integer, you must return the quotient of the arguments (arg/arg2/ ...) (you may assume that division is done sequentially, and that the decimal portion at every step is truncated)
  • If one argument is of type List and the other is of type Function, then you must return the resulting List after arg2 has been mapped over every value
  • (/ 100 10 3) -> 3
  • (/ (list 1 2 3) inc) -> (list 2 3 4)

• %, 2

  • If all arguments are of the type Integer, you must return the modulus of the arguments
  • (% 4 2) -> 0

• =, 2+

  • If both the type and value of all arguments is the same, you must return true. Otherwise, return false.
  • (= 0 0 0) -> true
  • (= 0 false (list)) -> false

• list, 0+

  • You must return a list of all arguments, regardless of type. If no arguments are given, then you must return an empty list
  • (list 3 4 (list 5)) -> (list 3 4 (list 5))

• inc, 1

  • If argument is of type Integer, you must return the Integer incremented by one
  • If argument is of type List, you must return the List rotated clockwise a single rotation
  • (inc 1) -> 2
  • (inc (list 1 2 3)) -> (list 3 1 2)

• dec, 1

  • If argument is of type Integer, you must return the Integer decremented by one
  • If argument is of type List, you must return the List rotated counter-clockwise a single rotation
  • (dec 1) -> 0
  • (dec (list 1 2 3)) -> (list 2 3 1)

• if, 3

  • If given three arguments of any type: If the truth value of arg1 is true, return arg2, else return arg3
  • (if (not (list 1)) 8 false) -> false

• not, 1

  • If given an argument of any type, if the truth value of arg1 is False, return true, else return false.
  • (not (list)) -> true

• len, 1

  • If given an argument of type List, return the length of arg1
  • (len (list 4 2 true (list 3) (list))) -> 5

Truth table: 0, (list), false -> false, where (list) denotes an empty list. Everything else is true.

Your interpreter can either be a full program that reads the source input from stdin or a file, or a function which takes the source as a string and returns the output value.

If choosing the former, the output for Integers is simply numbers, for Booleans is true or false, and for lists is a space separated sequence of values enclosed in brackets (eg. (1 2 3 4 (5 6 7)) denotes (list 1 2 3 4 (list 5 6 7))).

If choosing the latter, the value must be returned in the implementation language's corresponding type, or, if no similar type exists, a custom type. Lists can be returned as Arrays or Vectors if the language doesn't have a List type, Booleans should be returned as a Boolean type in the language, or a custom type if the language does not support them.

Test cases

(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

Clarifications

• Your interpreter may deal with invalid input in any way you choose, but it must not throw an exception (though, it may print an error message and exit smoothly)
• Functions will always evaluate arguments left to right
• Invalid input is any input which is syntactically incorrect. This includes, but is not limited to, mismatched brackets, division by zero, and partially applied functions (unless going for the bonus)
• For =, if any of the values are different or any of the types are different, return false

Bonuses

• Score * 0.8 if you support partially applied functions. For example, ((+ 2) 3) would be the same as (+ 2 3), but allows for things such as (/ (list 1 2 3) (+ 2)). You may assume that a function is partially applied if it receives less than its minimum number of arguments
• Score * 0.85 if you do not evaluate the arguments applied to if unless they are going to be returned

This is code-golf, so the interpreter with the lowest byte count wins!

Answer 1

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

Full program, reading stdin and writing to stdout. g is the function version, as well.

Implements both partial functions, and lazy evaluation of if.

Sample runs (of the function version):

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

Now has all unit tests from the description:

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

Answer 2

Common Lisp, 868 bytes * 0.85 = 737.8

Is it cheating to implement Lisp with Lisp? Lots to optimize here, still.

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

Prints out an E in case of an error in input. Sample runs:

$ 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

Answer 3

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

Complete overhaul. If you want to see the previous versions, check out the edit history.

There's a lot more to be golfed. I'm slowly working on it.

With zlib/base64 we get 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="))

Note: If you see my score going up, it's probably because I found a few bugs

Answer 4

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

quite a hacky solution. this stores everything as strings in output-ready form - their types can be distinguished by their first letter - 0..9 for numbers, ( for lists, t or f for booleans, and everything else for functions.

to run use the r function.