Code golf - tiniest Lisp-like language

Jonathan50

I've decided to make this code golf:

The challenge:
Make a tiny interpreter (or compiler!) for a Lisp-like language.

Rules:
You must not use ‘eval’ or equivilant if the language you are writing in is itself a Lisp-like language.
You must provide at least these functions: ‘cons’, ‘car’, ‘cdr’, ‘cadr’, ‘+’, ‘-’, ‘*’, and ‘print’ (print a value and a newline).
'cons' must take exactly two arguments. ‘car’ and ‘cdr’ should take exactly one, and ‘-’ exactly two.
'+' and ‘*’ must be able to take two arguments. It is not required that they can take more, but you can if you like.
You must not require the user to input anything more than their code. For example you can't make a ‘compiler’ that asks the user to input the output assembly.
You must make a REPL (Read-Evaluate-Print-Loop) if interpreting, or read source from stdin (with the exception of languages that don't have stdout) if compiling.
It must use the S-expression syntax.
It must ignore unnecessary whitespace. (For simplicity, tabs aren't counted as whitespace, programs with tabs may have undefined behaviour.)
The test program below must work as expected.
It must be able to work with arbitrary input. Testing for the test program is not allowed.
It must support at least integers and lists.

Scoring:
Each byte of the program's source code (or, in Scratch or Snap!, the amount of bytes of the minimum scratchblocks2 source without ‘::’ parts) adds a point to your score.
Code that imports GNU Readline, Editline, or a compatible library, does not count points.
Each newline only counts one point, regaurdless of whether it is a LF, CR, or CRLF.
The entry with the lowest points wins.

Test program:
(print (+ 1 (+ 2 3)))
(print (car (cons 1 nil)))
(print (car (cdr (cons 1 (cons 2 (cons 3 nil))))))
(print (cadr (cons 1 (cons 2 nil))))
The first line should output 6.
The second should output 1.
The third and fourth should both output 2.

Hints/tips:
In Python, remember you can use a hard tab character instead of four spaces.
Avoid unnecessary whitespace.
What can you do with ‘eval’ and ‘replace’?
Use short variable/procedure names. Avoid using underscores in names. (fooBar or foobar is shorter than foo_bar.)
Is there a shorter way to do something?
Implementing a way to define functions, or lambda, or variables, or comments, won't be necessary. Just what is specified in the rules.
Objective-C(++)'s ‘#import’ is shorter than ‘#include’! And, since Objective-C is 100% backwards-compatible with C (and Objective-C++ with C++), maybe you could make your C(++) program into an Objective-C(++) program?
In JavaScript, 'foo=()=>{}' is much shorter than ‘function foo(){}’.
Remember LISP code is basically lists of lists.

Good luck, and enjoy!

(PS: it's not as hard as it sounds. Don't worry about being ‘correct’ very much.)

Last edited by Jonathan50 (March 20, 2016 01:34:38)

BookOwl

How should we handle nil?

gtoal

When I was a young programmer I was taught to write simple and readable and understandable code. As I learned the trade over the years, I started to write more complex code because I felt it was important to use optimal algorithms all the time, for example if searching for an item in a list I would never use a linear scan or even a binary search, I would use a hash table or a trie. Then I went through a phase of writing the most compact code I could, regardless of how understandable it would be to anyone else.

But eventually after having to come back and maintain code I wrote during those years I realised that understandability trumps smart-aleck algorithms and smart-aleck coding tweaks every time. So now I code in what looks like a naive style again except where speed is absolutely critical - which isn't very often, and then I solve the problems algorithmically if I can rather than by low-level code tweaks.

Code golf is the worst style to practice when you're young. It's all the bad habits that you'll have to unlearn later.

I would be much more enthusiastic about challenges like this if the goal were to produce the shortest most elegant and understandable lisp interpreter rather than just the shortest by byte count. Of course it's impossible to instrument a subjective measure such as elegance so I understand why they do it, but I think that the people who do these things are people who have already learned the right way to do things and are breaking the rules deliberately. It worries me that you guys might think that this stuff is smart rather than fun.

I leave you with the words of Tony Hoare - There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.

G

BookOwl

I give you OwlLISP!

import re
from functools import reduce
from operator import mul
# Dictionary of defined functions with lots of lambdas
FUNCTIONS = {"cons": lambda a, b: (a, b),
             "car": lambda a: a[0],
             "cdr": lambda a: a[1],
             "cadr": lambda a: a[1][0],
             "+": lambda *args: sum(args),
             "-": lambda a, b: a - b,
             "*": lambda *args: reduce(mul, args, 0),
             "print": lambda arg: print(arg)}
def parse(prog):
    "Parses a S-Expression by converting it into a tuple"
    # Replace every symbol (but not numbers) with the symbol enclosed in '',
    # so that when we run eval the symbols turn into strings
    prog = re.sub("[a-zA-Z+\-*]+", "'\g<0>'", prog)
    # Replace "nil" with None
    prog = prog.replace("'nil'", "None")
    # Replace all the newlines and spaces (Lisp list seperators)
    # with ", " (Python tuple seperators)
    prog = re.sub("[\n ]+", ", ", prog)
    # prog is now valid tuple syntax, so run eval to turn it into one
    return eval(prog)
def interpret(prog):
    "Recursively interprets the parsed prog"
    # If we are interpreting a literal (int or None), return it
    if type(prog) in (int, type(None)):
        return prog
    # Else, we have a tuple
    # Run the function given by the first item in the tuple
    # with arguments given by recusivly interpreting the rest of the tuple
    elif prog[0] in FUNCTIONS:
        return FUNCTIONS[prog[0]](*tuple(map(interpret, prog[1:])))
def run(prog):
    "A helper function that parses and inteprets prog"
    return interpret(parse(prog))
if __name__ == "__main__":
    print("OwlLISP REPL")
    while True:
        prog = input("Enter your program: ")
        ret = run(prog)
        if ret:
            print(ret)

gist
Not bad for only 50 lines with comments and whitespace!

I decided to start off with creating a not golfed version. I can probably golf this quite a bit.

BookOwl

I golfed it.
It's now just 8 7 4 lines and 471 434 429 321 characters!!!!

Last edited by BookOwl (March 21, 2016 23:13:29)

Jonathan50

BookOwl wrote:
I give you OwlLISP!
#-snip-
gist
Not bad for only 50 lines with comments and whitespace!

I decided to start off with creating a not golfed version. I can probably golf this quite a bit.

Nice!

Jonathan50

BookOwl wrote:
How should we handle nil?

Nil is the end of the list. (It's a list of length zero.)

(print (cons 1 nil)) ; (1)
(print (cons 1 (cons 2 nil))) ; (1 2)
(print (cdr (cons 1 nil))) ; nil

(remember comments aren't required to be implemented. this example doesn't have to work unless the comments are removed.)

Last edited by Jonathan50 (March 19, 2016 19:58:09)

BookOwl

Jonathan50 wrote:
BookOwl wrote:
I give you OwlLISP!
#-snip-
gist
Not bad for only 50 lines with comments and whitespace!

I decided to start off with creating a not golfed version. I can probably golf this quite a bit.
Nice!

Thank you!

Jonathan50 wrote:
BookOwl wrote:
How should we handle nil?
Nil is the end of the list. (It's a list of length zero.)
(print (cons 1 nil)) ; (1)
(print (cons 1 (cons 2 nil))) ; (1 2)
(print (cdr (cons 1 nil))) ; nil
(remember comments aren't required to be implemented. this example doesn't have to work unless the comments are removed.)

I'm currently using Python's None, is that OK?

Jonathan50

BookOwl wrote:
Jonathan50 wrote:
BookOwl wrote:
How should we handle nil?
Nil is the end of the list. (It's a list of length zero.)
(print (cons 1 nil)) ; (1)
(print (cons 1 (cons 2 nil))) ; (1 2)
(print (cdr (cons 1 nil))) ; nil
(remember comments aren't required to be implemented. this example doesn't have to work unless the comments are removed.)
I'm currently using Python's None, is that OK?

I don't see why not. It doesn't print lists the way I'd expect, but it doesn't matter because they work right.

Last edited by Jonathan50 (March 19, 2016 20:19:06)

Jonathan50

I removed the scoring rule about readline because it got complicated when I did this

try:import readline,operator
except:0

which imports two modules, one which counts points. Sorry :(
nvm no problem that doesn't work

Last edited by Jonathan50 (March 19, 2016 20:47:42)

Jonathan50

Python 3, 497 491 507 475 473 467 461 462 457 456 455 446 441 405 406 bytes

from operator import*;import re
def cons(x, y):return [x]+y
def car(x):return x[0]
def cdr(x):return x[1:]
def cadr(x):return x[1:][0]
nil=[];v=None;r=str.replace
def e(s):return s[0](*map(lambda a:e(a)if type(a)==tuple else a,s[1:]))
while 1:
 for s in eval("["+re.sub(",,+",",",r(r(r(r(r(r(input("-> "),")",",),")," ",","),"\n",","),"+","add"),"-","sub"),"*","mul"))+"]"):v=e(s)
 if v:print("=> "+repr(v))

(NOT FOR PRODUCTION USE.)

Last edited by Jonathan50 (March 20, 2016 03:40:56)

__init__

Python

if raw_input()=="(print (+ 1 (+ 2 3)))\n(print (car (cons 1 nil)))":print "6\n1"

Boom.

BookOwl

Updated mine.

BookOwl

__init__ wrote:

Python

if raw_input()=="(print (+ 1 (+ 2 3)))\n(print (car (cons 1 nil)))":print "6\n1"

Boom.

That's not right…

Jonathan50

__init__ wrote:

Python

if raw_input()=="(print (+ 1 (+ 2 3)))\n(print (car (cons 1 nil)))":print "6\n1"

Boom.

Sorry, updated rules.
(That doesn't even work because raw_input ends on newline!)

Jonathan50

Now my entry is 478 points because it didn't ignore unnecessary whitespace more than two spaces

Jonathan50

I've updated the test program to be a little more complicated, but it still works on everyone's entries (except for __init__'s)

Jonathan50

BookOwl wrote:
I golfed it.
It's now just 8 7 lines and 471 433 characters!

That's amazing! But it doesn't work for me, for any input:

(print 4)
Traceback (most recent call last):
  File "golfedowllisp.py", line 7, in <module>
    while 1:i(eval(re.sub("[\n ]+",",",re.sub("[a-zA-Z+-*]+","'\g<0>'",input()).replace("'nil'","None"))))
  File "/usr/lib/python3.5/re.py", line 182, in sub
    return _compile(pattern, flags).sub(repl, string, count)
  File "/usr/lib/python3.5/re.py", line 293, in _compile
    p = sre_compile.compile(pattern, flags)
  File "/usr/lib/python3.5/sre_compile.py", line 536, in compile
    p = sre_parse.parse(p, flags)
  File "/usr/lib/python3.5/sre_parse.py", line 829, in parse
    p = _parse_sub(source, pattern, 0)
  File "/usr/lib/python3.5/sre_parse.py", line 437, in _parse_sub
    itemsappend(_parse(source, state))
  File "/usr/lib/python3.5/sre_parse.py", line 575, in _parse
    raise source.error(msg, len(this) + 1 + len(that))
sre_constants.error: bad character range +-* at position 7

What's wrong? I've got Python 3.5.1.

Last edited by Jonathan50 (March 19, 2016 23:12:12)

Jonathan50

Got it down to 467 bytes (including readline code)

BookOwl

Jonathan50 wrote:

BookOwl wrote:
I golfed it.
It's now just 8 7 lines and 471 433 characters!

That's amazing! But it doesn't work for me, for any input:

(print 4)
Traceback (most recent call last):
  File "golfedowllisp.py", line 7, in <module>
    while 1:i(eval(re.sub("[\n ]+",",",re.sub("[a-zA-Z+-*]+","'\g<0>'",input()).replace("'nil'","None"))))
  File "/usr/lib/python3.5/re.py", line 182, in sub
    return _compile(pattern, flags).sub(repl, string, count)
  File "/usr/lib/python3.5/re.py", line 293, in _compile
    p = sre_compile.compile(pattern, flags)
  File "/usr/lib/python3.5/sre_compile.py", line 536, in compile
    p = sre_parse.parse(p, flags)
  File "/usr/lib/python3.5/sre_parse.py", line 829, in parse
    p = _parse_sub(source, pattern, 0)
  File "/usr/lib/python3.5/sre_parse.py", line 437, in _parse_sub
    itemsappend(_parse(source, state))
  File "/usr/lib/python3.5/sre_parse.py", line 575, in _parse
    raise source.error(msg, len(this) + 1 + len(that))
sre_constants.error: bad character range +-* at position 7

What's wrong? I've got Python 3.5.1.

Oops, I accidentally removed an escape character, add one more point to my score.

Discuss Scratch