Lisp is fun!

I wrote a toy Lisp interpreter this weekend. Programming is pretty much a video game!

https://bitbucket.org/dhoskin/thp

(LET ((f (LAMBDA (x) (IF (x (f (CDR x))) recursion!))))
(f (QUOTE (a b c d e))))

→ args: ((a b c d e))
→ args: ((b c d e))
→ args: ((c d e))
→ args: ((d e))
→ args: ((e))
→ args: (nil)
→ recursion!

I loled, you have humour good sir

See also http://bbs.progrider.org/prog/read/1426221258

>>2

Thanks, I hope I didn't overdo it with the epic memes.

>>1
That is absolutely beautiful. Very small and well written. Thank you. After replacing the 9front stuff and getting it to compile with an ordinary C compiler, I put it all in a single C file you can just compile and run:

http://pastebin.com/VN8CdjCZ

I'm playing with lexical scope now!

(LET (
(factory (LAMBDA (x) (LAMBDA (y) (CONS x y))))
(helloer (factory hello)))
(helloer world))
→ (hello . world)

It works, but I'm not sure if it's a sane approach.

I only had to add 15 lines of code. When a (LAMBDA (args) ...) is evaled, it is translated into a (CLOSURE (env) (args) ...), where env is the variable list maintained by the interpreter.

This is nice and simple, but on each function call I have to splice the closure's environment onto the outside environment, which is expensive. Recursion won't work without the splice, since the variable pointing to the function isn't in scope at the time of definition.

In practice, this means that the name of the function for recursion is determined dynamically. What do real Lisps do here?

Here's an example of the problem:
(LET (
(f (LAMBDA (l) (IF (l (f (CDR l))) sameF)))
(g f)
(f (LAMBDA (x) (CAR x))))
(g (QUOTE (a b c))))
→ b
i.e., when f calls f recursively, the new definition takes over.

Obviously, the solution is to use a Y combinator.

>>4

Thanks, glad you liked it!

views: 232

I didn't even know there were that many people on /prog/.

Paging through your copy reminded me that there's all sorts of dead cruft I need to remove.

>>5

A concrete example of (CLOSURE ...):
(LET ((a 10) (f (LAMBDA (x) (CAR x)))) f)
→ (CLOSURE ((a 10)) (x) (CAR x))

prime get

fibs get

>>5 >>6
In other Lisps, I think you can't refer to variables created inside the variable declaring part of LET. You need to sublet. *cough*

For example, instead of:

(let ((factory (lambda (x) (lambda (y) (cons x y))))
(helloer (factory 'hello)))
(helloer 'world))

you need to do:

(let ((factory (lambda (x) (lambda (y) (cons x y)))))
(let ((helloer (factory 'hello)))
(helloer 'world)))

>>5 >>6
Also, I'm anxious to try your new version with closures, let us know when you check it in :)

>>9,10
Optimise your quotes, 「下さい」

>>11
nice dubs
>>8
nice fibs

>>9
There is let* for that: <http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.2.2>

>>5

Why is f being defined twice in the LET?
First f is set to a recursive definition (where the if clause doesn't seem to have an else case),
Then g is set to f,
Then f is set to a simple function.

What is that thing supposed to do?

Also, according to this bit:
(IF (l (f (CDR l))) sameF)
it seems like l needs to be both a function and a list. Could you explain what this is supposed to do?

Disregard >>15, your IF syntax is different.

no gc

Re: various syntax oddities - I've now written far more lines of Lisp interpreter than I have of Lisp, so my memory of how things work wasn't always the best.

Also, it turns out my clever idea for implementing special forms in Lisp code already exists, and is ^considered_harmful.
http://en.wikipedia.org/wiki/Fexpr

>>9,13

Oh!

Thanks, that also explains why some experiments I was trying in a Scheme interpreter didn't work as I expected.

>>10

Soon.

I just realized (but didn't test yet) that there's probably another problem.

(let ((x 10)(f (lambda () x))) (something f))
will work fine, since the lambda will be evalled and turned into a closure.

(let ((x 10)) (something (lambda () x)))
won't eval the lambda before passing it into something, so it won't close over x.

I don't know if I can fix this without walking the whole tree at every depth, looking for unclosed lambdas.

>>14
To demonstrate that recursion by name is broken.

Since g is set to f, one would expect it to recurse like f did.
But f wasn't in scope when f was defined, so it isn't part of the closure.
So even though I can still reference the function as g, to recurse it picks up f dynamically, which breaks when f was redefined.

I guess that's why defun was invented.

>>15,16

Oops, I was sort of aping cond there.

>>17

GC IS SHIT

>>18

Read http://www.p-cos.net/documents/s32008.pdf

>>18
I don't think there is a version of LET in any Lisp that lets you specify more than one definition for a variable. Neither LET, LET*, LETREC or LETREC* allow you do it.

The behaviour of thp seems reasonable:
1) Set f to a recursive definition where the f in f isn't bound to anything.
2) Set g to the first f
3) Redefine f (don't allow this)
4) Call g, which calls the first f which then calls the second f because the first f's f isn't bound. What else can it do? You've allowed f to be redefined before something else that refers to an f knows what it is.

If you insist on allowing f to be redefined, then you have to do multiple passes so recursive definitions still work.

For example, what happens if you define f twice with the same recursive definition before setting g to f?

ie:
(LET (
(f (LAMBDA (l) (IF (l (f (CDR l))) sameF)))
(f (LAMBDA (l) (IF (l (f (CDR l))) sameF)))
(g f)
(f (LAMBDA (x) (CAR x))))
(g (QUOTE (a b c))))

If you post your updated version I can try some stuff out.

This is something to aim toward:
http://rosettacode.org/wiki/Man_or_boy_test

>>22

You know the drill. :)

>>19

Thanks, that looks interesting.

>>20

OK, so it's reasonable for f not to close over itself?

That's good, because so far I haven't had to make anything mutable.

If you post your updated version I can try some stuff out.

It's up on bitbucket. It depends on an updated libsexp which exports O *mka(char *c) to make atoms, which was previously used internally. That's no change for the inline Unix port some kind anon posted above.

I plan to make a proper Unix branch at some point, but I haven't yet.

This is basically all it does:

+ if(strcmp(atomstr(car(f)), "CLOSURE") == 0){
+ env = splice(car(cdr(f)), env); /* XXX expensive! especially on every function call! */
+ args = evalargs(cdr(o), env);
+ env = args2env(car(cdr(cdr(f))), args, env);
+ return eval(car(cdr(cdr(cdr(f)))), env);
+ }
/* ... */
+ if(strcmp(a, "LAMBDA") == 0){
+ return cons(mka("CLOSURE"), cons(env, cdr(o)));
+ }

>>21

Ooh, good idea!

Huh, apparently my interpreter is smarter than I am.

Something that I knew would work:
(LET ((x 10) (f (LAMBDA () x)) (g (LAMBDA (x f) (f))))
(g 20 f)
→ 10

Something that I thought would break:
(LET ((x 10) (g (LAMBDA (x f) (f))))
(g 20 (LAMBDA () x)))
→ 10

I expected it to mistakenly print 20.

Let's investigate...
(LET ((x 10) (g (LAMBDA (x f) f)))
(g 20 (LAMBDA () x)))
→ (CLOSURE ((x 10) (g (CLOSURE ((x 10)) (x f) f)) (x 10)) nil x)

Neat!

Fun note: despite adding 16-odd lines for the closures, the code is still 10 lines shorter overall because I removed the cruft that was meant for an over-engineered builtins system.

Fun note: despite adding 16-odd lines for the closures, the code is still 10 lines shorter overall because I removed the cruft that was meant for an over-engineered builtins system.

>>24-25

Heh, not my usual sort of doubles.

Doubleposting could be an obnoxious new meme though!

>>22-26
Outstanding.

I've updated the Unix port and posted it here:
http://pastebin.com/dLz29jkC

Interestingly, in the C lambda function (on line 297), only the closure block is executed, never the lambda block. The printf on line 321 never happens, only the printf on line 314.

>>27
Making the interpreter make 2 passes by defining f twice fixes the problem discussed in >>5 and >>20:

Welcome to Lisp
> (LET (
(f (LAMBDA (l) (IF (l (f (CDR l))) sameF)))
(g f)
(f (LAMBDA (x) (CAR x))))
(g (QUOTE (a b c))))
closure args: ((a b c))
closure args: ((b c))
b
> (LET (
(f (LAMBDA (l) (IF (l (f (CDR l))) sameF)))
(f (LAMBDA (l) (IF (l (f (CDR l))) sameF)))
(g f)
(f (LAMBDA (x) (CAR x))))
(g (QUOTE (a b c))))
closure args: ((a b c))
closure args: ((b c))
closure args: ((c))
closure args: (nil)
sameF
>

Results of testing the programs in >>23:

> (LET ((x 10) (f (LAMBDA () x)) (g (LAMBDA (x f) (f))))
(g 20 f))
closure args: (20 (CLOSURE ((x 10)) nil x))
closure args: nil
10
> (LET ((x 10) (g (LAMBDA (x f) (f))))
(g 20 (LAMBDA () x)))
closure args: (20 (CLOSURE ((x 10) (g (CLOSURE ((x 10)) (x f) (f))) (x 10)) nil
x))
closure args: nil
10

Results of testing the programs in the readme:

Welcome to Lisp
> (QUOTE (a b c))
(a b c)
> (LET (
(f (LAMBDA (x) (CONS goats x)))
(g (LAMBDA (x) (CDR x))))

(f (g (QUOTE (1 2 3)))))
closure args: ((1 2 3))
closure args: ((2 3))
(goats 2 3)
> (LET ((f (LAMBDA (x) (IF (x (f (CDR x))) recursion!))))
(f (QUOTE (a b c d e))))
closure args: ((a b c d e))
closure args: ((b c d e))
closure args: ((c d e))
closure args: ((d e))
closure args: ((e))
closure args: (nil)
recursion!
> (LET (
(f (LAMBDA (x) (CAR (CDR x))))
(g (LAMBDA (f x) (f (CDR x)))))

(g f (QUOTE (a b c))))
closure args: ((CLOSURE nil (x) (CAR (CDR x))) (a b c))
closure args: ((b c))
c
> (LET ((f (LAMBDA (x) (CONS x y))))
(LET ((y world))
(f hello)))
closure args: (hello)
(hello . world)
> (LET ((f (LAMBDA (x) (LAMBDA (y) (CONS x y))))
(helloer (f hello)))
(helloer world))
closure args: (hello)
closure args: (world)
(hello . world)
> (LET ((CAR CDR)) (CAR (QUOTE (a b c))))
(b c)
> ()
nil

Excellent work.

Bump because I want to talk about PROGRAMMING and LISP, not opine pointlessly about /twatter/ and whatever else that is not directly about PROGRAMS and PROGRAMMING. There is the rest of the internet for that rubbish.

THIS IS A SACRED PLACE

Do not soil it with the weltschmerz inducing detritus of a decaying world.

I've only done minor cleanups; there were a lot of crufty comments.

% wc -l thp.c ../libsexp/sexp.[ch]
163 thp.c
216 ../libsexp/sexp.c
31 ../libsexp/sexp.h
410 total

>>23

Huh, apparently my interpreter is smarter than I am.

After all, Lisp was invented for AI.

>>27

Thanks again!

Indeed, since the car of the list is evaluated unconditionally before I check to see whether it is itself a list.

If I take the lambda code out, I could easily get under 400 lines. I'm tempted to leave it in and fix eval to actually use it because closure calls are so wasteful now, but it's not like anything else about this implementation is efficient, and it's still fast enough for two-line demo programs.

>>28

That double-definition hack is cool, thanks.

>>29

A thousand blessings upon the great Prophet McCarthy.

CHECK OUT MY PRIME NUMBER !!!!!!

>>31
It's divisible by 7 you moron.

>>32
Check it again
http://www.wolframalpha.com/input/?i=Is+31+prime%3F&dataset=&asynchronous=false&equal=Submit

>>32
Learn some basic arithmetic, dumb fuck.

>>32
7 is prime

>>35
Every number is divisible by a prime. Read about the fundamental theorem of arithmetic and stop spamming your inane GET garbage.

>>36
1 is not.

Bump for Lisp and Programming

Lets bring some programming back to /prog/ by doing some talkings about Lisp.

Clojure is not a LISP.

thp is not an acceptable lisp

>>40
No lexically scoped language is a Lisp.

>>41
Its more of an acceptable Lisp than you are.

Thanks Thp.
Thp.

Sorry I disappeared. Hopefully I'll find more time to tinker with it.

Also check these.

>>44
checked.

44 Name: Alexander Dubček : 2015-06-24 02:56
Sorry I disappeared. Hopefully I'll find more time to tinker with it.

Also check these.
------
0f13d66c4f6e81b2debf139083ffa4e37f0652b739fbeaa4f1f606128c48b398