Lisp Interpreter

Why are you quoting t? It is normally self-evaluating.

Quote:

Original post by Roboguy Why are you quoting t? It is normally self-evaluating.

Ahh, good point and a simple change. I'm really a newbie when it comes to lisp.

Tic-Tac-Toe, ekk! That does sound challenging, as well as a great place to start, thank you.

Ratings++ for all.

Is it imperative? Have you implemented any functional features (lambdas, higher-order functions, etc)? If so, is it a Lisp-1 or Lisp-2 (a Lisp-2 has separate namespaces for functions and variables, and to use functions as data you have to prefix them with something (in Common Lisp, it's #'), a Lisp-1 has both in the same namespace).

Also. I could be wrong, but your post seems to imply that you think Lisp is a single language. It isn't (currently, the most commonly used Lisps are Scheme and Common Lisp (Scheme is a Lisp-1, Common LIsp is a Lisp-2). A lot of times, just "Lisp" refers to Common Lisp, though). Just wanted to point that out.

If you don't mind a fairly complicated project, a simple term-reducer might be a good test.

Ahh yes Roboguy, I was having a discussion with a few classmates earlier today about Common Lisp and Scheme. Unfortunatly the assignment was rather vague and was little more than a list of functions that our interpreter was required to implement. In fact, no formal language definition was given to us. Example interpreter code was given to us from this book, but I found their K&R style C syntax to be ugly decided to write it from scratch using C++. I used the CLISP 2.35 implementation as a reference and went from there. What I have is really only a very small subset of *some* lisp-like language.

Quote:

Original post by aaron_ds Ahh yes Roboguy, I was having a discussion with a few classmates earlier today about Common Lisp and Scheme. Unfortunatly the assignment was rather vague and was little more than a list of functions that our interpreter was required to implement. In fact, no formal language definition was given to us. Example interpreter code was given to us from this book, but I found their K&R style C syntax to be ugly decided to write it from scratch using C++. I used the CLISP 2.35 implementation as a reference and went from there. What I have is really only a very small subset of *some* lisp-like language.

The Lisp it seems to resemble the most is Common Lisp. What about my other questions (particularly the functional one and the namespace one)?

Quote:

Original post by Roboguy The Lisp it seems to resemble the most is Common Lisp. What about my other questions (particularly the functional one and the namespace one)?

I havn't implemented lambdas or higher-order functions. From what I found looking them up breifly, I can easily integrate them into my current setup.

I'm using (basically) two namespaces one for functions and one for variables. I further divided these into builtin functions, user defined functions, global variables and a stack for function argument values when using user-defined functions.

We were more or less told to go out and write a "Lisp Interpreter", some of the students didn't fare well. :-\

Quote:

Original post by aaron_ds Quote: Original post by Roboguy The Lisp it seems to resemble the most is Common Lisp. What about my other questions (particularly the functional one and the namespace one)? I havn't implemented lambdas or higher-order functions. From what I found looking them up breifly, I can easily integrate them into my current setup. I'm using (basically) two namespaces one for functions and one for variables. I further divided these into builtin functions, user defined functions, global variables and a stack for function argument values when using user-defined functions. We were more or less told to go out and write a "Lisp Interpreter", some of the students didn't fare well. :-\

I would recommend you implement them, they are very handy (along with some functions like map and fold). Also, I'm not sure you understand completely what I mean by Lisp-1 and Lisp-2, it really only applies to languages that have higher-order functions. Basically, in Common Lisp (a Lisp-2) to call a variable which happens to be a function, you have to prefix it with a #' and use the funcall operator:

(funcall #'f arg1 arg2 ...)

While in Scheme (a Lisp-1) it would look like:

(f arg1 arg2)

I'm personally a Lisp-1 fan.

Ekk! Yup, I'm evaluating user-defined functions as (f arg1 arg2). Now I have no clue if I'm even writing a Lisp-1 or Lisp-2 interpreter.

Lol, it would have been great if my professor had mentioned this a few months ago. Either way, it was an Algorithms and Data Structures class; I can do multiple types of linked lists in my sleep and got a decent handle on implementing hashtables both of which are used in the interpreter.

Quote:

Original post by aaron_ds Ekk! Yup, I'm evaluating user-defined functions as (f arg1 arg2). Now I have no clue if I'm even writing a Lisp-1 or Lisp-2 interpreter.

No, the Lisp-1 or Lisp-2 thing only relates to *variables* which are functions, not functions which are defined with the function definition operator (defun in this case).

Ahh, I think I'm begining to understand. So Lisp-1 has first-class functions and Lisp-2 doesn't?

I like the Lisp-1 syntax better myself and will probably go with that if I do any future development. I *really* want to do a &#106avascript interpreter.

Quote:

Original post by aaron_ds Ahh, I think I'm begining to understand. So Lisp-1 has first-class functions and Lisp-2 doesn't? I like the Lisp-1 syntax better myself and will probably go with that if I do any future development. I *really* want to do a &#106avascript interpreter.<!--QUOTE--></td></tr></table></BLOCKQUOTE><!--/QUOTE--><!--ENDQUOTE--><br><br>They both have first-class functions, but Lisp-2 puts them in a separate namespace so you have to "bring" them in the variable namespace (in Common Lisp, that's what the <tt>#'</tt> does) to assign them to variables or use them as arguments.</td></tr></table></blockquote>

That seems like a nice start. One important aspect besides the lisp-1/lisp-n is variable scoping. Do the variables have static or dynamic scope? Most modern lisps default to static scope. With static scoping, proper closures and possibly macros you could easily implement an OO system on it. Implementing a few different kinds of OO systems (Smalltalk like message passing OO, CLOS, prototype based OO etc.) might be an interesting and practical exercise.
There are numerous Scheme OO implementations to use as an example, http://www.cs.indiana.edu/scheme-repository/code.oop.html might be a good start.

Dividing is usually done with / , not with \.

Adding lambda and closures would be a nice next step.


Lisp1 vs Lisp2 is a matter of style, not of semantics:
In a lisp1 you can do this
((somefunction-that-returns-a-function) a b) or
(setq x cons)
(x a b)
while in a lisp2 that needs to be (funcall (somefunction-that-returns-a-function) a b) and
(setq x #'cons)
(funcall x a b)

In a lisp2 you can do
(defun x (cons)
(cons cons cons))
which is the same thing as
(defun x (a)
(cons a a))

If you're interested in learning more about lisp, you might find John McCarthy's Home Page interesting. Specifically, the original paper on lisp should interest you - it contains a very simple but still turing complete language. You could try implementing an interpreter for the language in that paper in your langauage - it should be very simple if you add a few functions, like 'read' which reads an object (meaning a list, number, etc in the standard format for your language) from input.

I like functional languages, but I prefer one with far less dependance on explicit structure (like brackets) than Lisp and its variants, languages like ML and Eiffel. OCaml has all the benefits of a functional language, plus static type inferrence and a very clean mathematical approach to functions.

Back to the real topic, I agree with the Dr. Evil anonymous poster; to stress-test a language, write an interpreter for it in itself, then compare that implementation to that of the bootstrap language (the one you wrote the first interpreter in). That's a good benchmark of whether or not your language is suitable for most typical programming tasks.

Of course, in some languages, writing an interpreter for the language in the language is one of the easiest things to do =-)
(do () (nil) (print (eval (read))))

Quote:

Original post by Extrarius If you're interested in learning more about lisp, you might find John McCarthy's Home Page interesting. Specifically, the original paper on lisp should interest you - it contains a very simple but still turing complete language. You could try implementing an interpreter for the language in that paper in your langauage - it should be very simple if you add a few functions, like 'read' which reads an object (meaning a list, number, etc in the standard format for your language) from input.

ESR has a good discussion of minilanguage design and implementation.