Page 1 of 1

Lisp primitives?

Posted: Sat Jun 28, 2008 9:45 am
by icosahedron
I'm thinking of doing a Lisp of my own, something small and neat for pedagogical purposes. I've often read there are 25 or so lisp primitives, so I'm wondering where to find a list of these? Some of them are fairly "obvious", such as if and lambda. Any thoughts or links?

Re: Lisp primitives?

Posted: Sat Jun 28, 2008 9:52 am
by findinglisp
I'd read McCarthy's original paper and some of Paul Graham's writings about Arc. You can find links to both here: http://www.findinglisp.com/blog/2004/10 ... ispia.html

Re: Lisp primitives?

Posted: Sat Jun 28, 2008 10:02 am
by nklein
In an appendix of Paul Graham's ANSI Common Lisp, he implements a ton of Common Lisp from a much smaller subset: apply aref backquote block car cdr ceiling char= cons defmacro documentation eq error expt fdefinition function floor gensym get-setf-expression if imagpart labels length multiple-value-bind nth-value quote realpart symbol-function tagbody type-of typep * + - / < >

That's 36. But he still gets 57 more standard constructs from it.

Re: Lisp primitives?

Posted: Sat Jun 28, 2008 10:28 am
by jmbr
You can also take a look at http://home.pipeline.com/~hbaker1/MetaCircular.html (Metacircular Semantics for Common Lisp Special Forms)

Re: Lisp primitives?

Posted: Sat Jun 28, 2008 2:48 pm
by horia314
It depends what you mean by primitive, I guess. Theoretically you could get really small (function definition + function application) and build everything else from this two. Now, functions like + or car could be defined in such a minimal language (in fact Alonzo Church,the originator of lambda calculus and the granddad of functional programming did just that with numbers and the elementary arithmetic operations: wikipedia can probably tell you more precise information about this http://en.wikipedia.org/wiki/Church_numerals), but your interpreter/compiler will be very very slow and impractical (and heaven knows we need not give more ammo to the people who say lisp is *nice* but it doesn't have libraries and frameworks and the fluff. they'll say lisp is *nice* but it doesn't even have numbers and addition ;) ). So, you'll have to draw the line somewhere and say that some functions and identifiers are gonna be recognized as "special" and treat them that way. So, numbers, strings, booleans, +, -, *, /, %, strlen,strcat or what have you will be efficiently implemented, but transparent to the programmer. You could of course extend this to any function, regardless of complexity (or how primitive it really is). In a lisp geared toward programming games for example, you could have primitives like create-rendering-context or draw-polygon-with-texture etc.

Re: Lisp primitives?

Posted: Sun Jun 29, 2008 9:27 am
by Wodin
Perhaps Lisp in Small Pieces will help? :) I haven't read it, and I think it's more about Scheme than lisp, but I thought it was worth a mention.

Re: Lisp primitives?

Posted: Sun Jun 29, 2008 9:56 am
by dan
Yeah, after reading http://www.findinglisp.com/blog/2008/06 ... guage.html I too have added this to my todo list, and this is a helpful reference.

Re: Lisp primitives?

Posted: Sun Jun 29, 2008 10:51 am
by findinglisp
Wodin wrote:Perhaps Lisp in Small Pieces will help? :) I haven't read it, and I think it's more about Scheme than lisp, but I thought it was worth a mention.
Lisp in Small Pieces is a great resource if you're interested in implementing Lisp, and it will help even if you're interested in Lisps other than Scheme. It actually covers some of the difference. It's pretty academic, however, in its treatment. Be sure you're ready for a book that develops a multitude of interpreters, over and over again, using different techniques. If you aren't ready for that, it will seem repetitive and boring, but it will have the effect of teaching you exactly how Lisp interpreters (and compilers, actually) work.

Unfortunately, it will not answer the question of which Lisp functions are most primitive. It sort of takes as an assumption that you want to implement something Scheme-like or Lisp-like and then goes through how that would be done.

All-in-all, I highly recommend Lisp in Small Pieces, but know what you're going to get. :D

Re: Lisp primitives?

Posted: Sun Jun 29, 2008 9:22 pm
by icosahedron
Thanks everyone for the replies.

I've bookmarked the 1960 paper and so far it's a very interesting read. It sounds as if Lisp was the first language with an if/else construct, which I believe I'd read somewhere else.

I've put Lisp In Small Pieces on my Amazon wish list. Thanks for that.

As for making a lisp with only two operators, well, it sounds intriguing, but I think I'll try for a few more. :)

Thanks again. This is great material.

Re: Lisp primitives?

Posted: Mon Jun 30, 2008 7:51 pm
by hilbertastronaut
icosahedron wrote:I'm thinking of doing a Lisp of my own, something small and neat for pedagogical purposes. I've often read there are 25 or so lisp primitives, so I'm wondering where to find a list of these? Some of them are fairly "obvious", such as if and lambda. Any thoughts or links?
I'd say, if you're doing it just to teach yourself and have a good time, you could try a few iterations with different sets of primitives, and see which sets you find most orthogonal, most intuitive, result in the best performance, etc.

To me, the primitives most likely to result in a Lisp dialect I might actually use for practical work, are those which let me treat it as an embedded language:
  • * A way to manipulate the Lisp's data structures in the host language
    * An FFI (call host language functions from the Lisp)
If you have this application in mind, it might help guide your efforts to implement primitives. For example, if you'd like to use your embedded language to do algebraic transformations (as I would), you won't need to focus so much on string operations (maybe you won't need string ops at all).