Respect!
For me that's the 'benchmark' of understanding a language, to be able to re-implement it.
edit: by the way, it's been more than two months, but there have been a lot of things done in that time that have nothing to do with programming.
http://dl.dropbox.com/u/2083231/essential_lisp_implementatio...
I would recommend these to someone who wants to implement a functional or a Lisp language, going with nothing but basic systems programming knowledge.
Recommend prerequisites are the first 2-3 chapters of SICP, some familiarity with classic compiler construction (dragon book would do, skip the lexical analysis and parsing parts though; you wont need much of that for Lisp if you retool and existing lexer. But focus on function calling and stack discipline, lexical scope and variable visibility, and maybe learn how an Algol dialect implements runtime heap-allocation) some exposure to C and assembly, and healthy curiosity.
A suggested order might be: Ghuloum, Wilson, Dybvig, the uncredited "lisp-implementation.pdf" paper, Gudeman, Kelsey, then Shao (Shao might make a whole lot more sense if you read one of Andrew Appel's compiler books and dip a tiny bit into ML.)
I write `brave', because it implements Scheme using Haskell. And if you aren't familiar with either, the learning curve will be steep.
See http://research.microsoft.com/en-us/um/people/simonpj/papers... for some hints on writing a compiler for those (or just general amusement).
For instance, it seems to be like travelling back to the 80's just to have to live with the 'third element in the list containing the data about a person' instead of simply using person->name , I've gotten used to thinking in terms of symbols so much that I find it hard to go back to the kind of trickery that was 'normal' in say microsoft basic in the 80's because it lacked named elements in something akin to a struct.
There is a certain kind of elegance in something so minimal but it also comes with considerable mental overhead and opportunity for mistakes.
Most people don't do that, except in throwaway code. In CL you can use an alist, a plist, a struct, or CLOS.
I've gotten used to thinking in terms of symbols so much that I find it hard to go back
Given that Lisp's history with symbolic computing goes back to the beginning, something about that doesn't sound right.
Your person->name comment reminds me of something, by the way. Portions of our app run in both CL and JS (via the Parenscript library). This is relatively easy, although there are a few disagreements between the two that you have to watch out for (such as how they handle null). Anyway, there are lots of CL features we've "ported" to JS via macros, but there is also one JS feature I found myself envying so much that I finally wrote a partial implementation of it in CL. That is JS's willingness to allow you to stick any property on any object just by setting it. It's a rather Lispy feature since it's maximally dynamic and maximally flexible. I find it handy for incremental development. When you have some data about a thing that you want to associate with it, but only some of the time, it's a real pain to have to make a separate data structure to hold it and then make sure it gets passed alongside the original thing to all the appropriate places. Our CL implementation of this is pretty crude but it allows the important thing, which is that you can write (@ something :some-data) and (setf (@ something :some-data) "blah") pretty much wherever you want. So we can be said to have Greenspunned a bit of JS in Lisp!
(defstruct person
name age occupation) => PERSON
(make-person :name "Kris Kringle"
:age 71
:occupation "Santa") => #S(PERSON-1)
(person-name *) ==> "Kris Kringle"Don't worry, I realize that :)
> very real Lisp worth using has structures and objects:
That's a tricky and somewhat circular definition.
If it is worth using it is probably real and vv, but most lisp tutorials that teach 'pure' lisp do not have structures and / or objects, they rely on lists alone as their major data structure.
That also defines all lisps that do not have these items as somehow not real and there seem to be a lot of lisp people that somehow consider this 'impure'. Or is my reading material that dated ?
Go far a modern Lisp like Scheme. (You can ignore the syntax you don't want to deal with, yet.)
Usually it goes the other way around: you implement lists on top of defstruct.
But there is a danger in overusing structs and classes, too. You end up with these hugely complex ontologies for every little program, and frequently when you try to reuse code you end up with conflicts.
(car (cdr (cdr (cdr list))))
you should just do: (at list 3)The bigger problem is in code that consumes the lists item by item, every time an extra copy of the remainder of the list will be made, there it is much harder to work around this.
Very neat code by the way, thanks a ton for making this.
I'll be playing around with it for a bit, I've written a chunk of code for a small site a while ago in a 'functional' PHP style (as in, no assignments except at the highest level), I'll see if I can convert that project to your lisp dialect and get it to work.
You should even get rid of a custom type for Lisphp sequences and use PHP arrays directly. Ditto all other datatypes. Then if you use PHP's calling convention you should be able to call PHP code directly without needing USE and FROM, and more importantly PHP code can do the same to Lisphp with minimal pain. That way writing Lisphp libraries for others to use becomes viable.
Hint: via recursion, how do you advance along a sequence in a collection-agnostic way?
It is the ability to decompose an arbitrary sequential data structure efficiently that is important. It's not important because of any historical bias; it's important because it is incredibly useful.
If you can't support first/rest in an efficient manner, it is a bad sign.
It's important when you need to write your own iteration primitives. Map, fold, etc are all well and good, but sometimes they won't do because the iteration may require some unusual steps.
In your particular dialect of lisp, what does the code for writing map or fold look like? The one that doesn't copy memory egregiously, that is. And how bad must the performance of javascript linked lists be to scare you away from them so damn hard, anyways?
Or perhaps, what you're supporting is a "lispish" language that isn't really something we should directly compare to lisp, in the vein of Nu?
This is map:
(defun map (fn arr) "Call FN on each element in ARR and return the returned values in a new array." ;; In newer versions of ECMAScript, this may call Array.map, too (let ((idx 0) (result (array))) (dolist (el arr) (setf (aref result idx) (fn el)) (setf idx (1+ idx))) (return result)))
This is reduce:
(defun reduce (func list &optional init) ;; the use of init here is actually a bit broken wrt null (let* ((acc)) (do* ((i (if init -1 0) (1+ i)) (acc (if init init (elt list 0)) (func acc (elt list i)))) ((>= i (1- (length list))))) (return acc)))
What would a linked list data structure provide? Incompatibility with all other JavaScript code and a mandatory runtime library?
Thanks for introducing me to Nu btw. What makes you say that it is not a Lisp?
This is map: http://github.com/dahlia/lisphp/blob/81849070ac7ff13948786b5...
This is filter: http://github.com/dahlia/lisphp/blob/81849070ac7ff13948786b5...
This is fold: http://github.com/dahlia/lisphp/blob/81849070ac7ff13948786b5...
Lisphp respect the iterator protocol of PHP instead of Lisp tradition in the practical reason.
Uh, constant-time insertions?
Of course, because of the whole shared hosting thing you'd have to fall back to a pure PHP implementation if the extension isn't loaded.
http://www.php.net/manual/en/class.spldoublylinkedlist.php
LispHP seems to use ArrayObject, though I'm not really sure how its performance is (googling indicates iteration is slow).
It's kind of moot because if speed were a huge concern, this might not be used in the first place, but just it would be interesting to see how far such a thing could be taken.
array_slice((array)$this, 1);
I'm not sure if this will be faster though. Is the source of the slowness getArrayCopy or array_slice itself?Please correct me if this is false.
http://fupeg.blogspot.com/2009/11/persistent-data-structures...