Sign in to follow this  
CoffeeMug

My first function! [my lisp interpreter]

Recommended Posts

I've finally gotten my lisp dialect interpreter to a state where I can write the following piece of code
(let fib (fn (x)
	(cond
		((= x 0) 1)
		((= x 1) 1)
		(1 (+ (fib (- x 2)) (fib (- x 1)))))))


There's a lot of work left to do. I desperately need to implement macro support so I can code up something like 'defun' in order to avoid the whole '(let fib (fn' business. I also have for loops, some primitive IO, REPL, and a bunch of other cool stuff. It's surprising how fast one can add features once the basic infrastructure is in. Hooray for lisp!

Share this post


Link to post
Share on other sites
Did you name 'set' 'let'? Normally 'let' only binds that value locally, but the way you talk about macros it sounds like you've made yours global.?

Mind sharing your interpreter's source?

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
Did you name 'set' 'let'?

Yes. This thing varies across languages and seems to confuse people a lot. I might change it to something unambiguous later.
Quote:
Original post by Extrarius
Normally 'let' only binds that value locally, but the way you talk about macros it sounds like you've made yours global.?

I don't plan to introduce an equivalent of lisp 'let'. I'm actually looking for alternative ways to accomplish the same functionality. I think something like this is nicer:


(scope
(set x 1)
(set y 2)
(print (+ x y))


Of course anybody could easily do a Lisp 'let' using macros if they're so inclined.
Quote:
Original post by Extrarius
Mind sharing your interpreter's source?

I started writing the interpreter purely for educational purposes. My idea is to create a usable version of the interpreter and use it to experiment with a web framework. I was then planning to create a small content management web application on top of that and put it online along with all the sources, documents and descriptions.

Currently there is no documentation (though the code is fairly clean IMO), the interpreter is far from complete, mostly slow and buggy. Let me know if you still want it, I'll upload the source and put a link here.

Share this post


Link to post
Share on other sites
Well, really I don't want your source I'd just like to know how you implemented various things, such as:
Do you use something union-esque for typeless variables and typed values, or do you use something fancier such as polymorphism?
Do you use garbage collection, reference counting, or something else to manage the memory of temporary variables?
Do you have (or plan to have) support for read macros? If so, how did(or do) you plan on implementing them?

Things like that.

Share this post


Link to post
Share on other sites
Here's a link to the source.
Quote:
Original post by Extrarius
Do you use something union-esque for typeless variables and typed values, or do you use something fancier such as polymorphism?

Actually this is my third try. First time I experimented with boost::variant and boost::any (which essentially are union-esque variables). Didn't work out too well for me, although now that I look back I think it could have worked if I reworked the implementation. Oh well. Second time I used pure C structs (lots of void*) which also turned out to be hell. Right now I'm using polymorphism and I've progressed tremendously. I don't think there will be a fourth try.
Quote:
Original post by Extrarius
Do you use garbage collection, reference counting, or something else to manage the memory of temporary variables?

I use boost::shared_ptr everywhere. It simplifies the design immensely (it's almost like using Java) but complicates the code a bit due to various quirks. It's also slow. If I find that performance is a significant problem I'll replace it with intrusive_ptr and plain old allocation whenever I can. For now I'm interesting in getting things up and running, I don't really care about speed and it looks like booost::shared_ptr worked out great.
Quote:
Original post by Extrarius
Do you have (or plan to have) support for read macros? If so, how did(or do) you plan on implementing them?

Not at the moment. I'm thinking about how to go about doing this and so far I didn't come to a good solution that I like. Using Lisp without abbreviations for things like quote (') is for all intents and purposes impractical. On the other hand, heavily using read macros degenerates the "unified syntax" idea and makes the entry barrier much higher for beginners. I don't want to hard code things like quote because I think the beauty of lisp is exposing everything through the languages. Anyway, any ideas on this are welcome.

In terms of implementing read macros, I don't think it would be too hard. I hand coded my parser (not because of NIH syndrome or anything, it's just fun to do a recursive descent parser once in a while) so hacking it to support custom read macros should be pretty simple.

Share this post


Link to post
Share on other sites
I think it would be interesting to have a partial-evaluation special form in a lisp or scheme (or any language for that matter). It would be like curry, but would actually go through the function and perform const propagation and strip dead code paths.

I asked about this on the lispy channels on freenode and the people there explained that in most Lisps not enough of the function's structure is stored in the function objects to allow this to happen away from the function definition. I think it would need to be built into the language because if you would like to use macros, you would be stuck with something like the following (as opposed to Scheme's 'curry':

(partial-evaluate
(define (func a b c d)
;.......)
; the following are partially evaluated forms to be dispatched as multi-methods
(func ?a ?b 3 4)
(func ?a ?a 3 4)
(func 1 2 77 ?d))



It's an interesting part of language design that hasn't seen the light of day in any language I know (apart from REFAL) and I thought I would share it.

Beyond the basics, I thought it would be pretty good to also generate runtime logs of what functions are run often and tag them for partial-eval. Then you could have an LRU cache of partial-eval versions in a scope. Obviously this wouldn't be good to do everywhere, but it could definitely have it's uses in large tasks where the inputs are well known.

If this stuff interests you maybe you could use your language as an area to try these ideas out.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this