News for hackers. Stuff that matters.
Re:Lisphp is a Lisp dialect written in PHP. by jacquesm on Monday July 05, 2010 @10:43AM (#1488285)
Minor nitpick, the cdr implementation is (out of need, as far as I can see) terribly slow for larger datasets, it uses array_slice($this->getArrayCopy(), 1) .
Re:Lisphp is a Lisp dialect written in PHP. by mahmud on Monday July 05, 2010 @12:13PM (#1488519)
Well done jacquesm! It's only been what since you first looked at Lisp? 2 months? Already you know your way around typical primitive implementations.

Respect!

Re:Lisphp is a Lisp dialect written in PHP. by jacquesm on Monday July 05, 2010 @12:18PM (#1488530)
I've been studying it so I can go and write a little lisp interpreter in C just to make sure I really 'got' it.

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.

Re:Lisphp is a Lisp dialect written in PHP. by mahmud on Monday July 05, 2010 @01:13PM (#1488637)
I wrote a few long-winded posts on HN listing Lisp implementation bibliographies. There are a few essential papers that you need to read to get the full picture; Here they are collected in an archive. Nearly all of them assume nothing more than rudimentary familiarity with Lisp, some functional programming (Scheme and tiny bit of ML) and they're geared towards someone with some C, machine-org and assembly knowledge.

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.)

Re:Lisphp is a Lisp dialect written in PHP. by eru on Monday July 05, 2010 @04:59PM (#1489086)
For the brave, I can also recommend "Write Yourself a Scheme in 48 Hours" (http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H...).

I write `brave', because it implements Scheme using Haskell. And if you aren't familiar with either, the learning curve will be steep.

Re:Lisphp is a Lisp dialect written in PHP. by eru on Monday July 05, 2010 @01:11PM (#1488632)
For a challenge: Try a lazy language next.

See http://research.microsoft.com/en-us/um/people/simonpj/papers... for some hints on writing a compiler for those (or just general amusement).

Re:Lisphp is a Lisp dialect written in PHP. by jacquesm on Monday July 05, 2010 @01:15PM (#1488640)
Lisp is enough of a challenge for me at the moment.

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.

Re:Lisphp is a Lisp dialect written in PHP. by gruseom on Monday July 05, 2010 @01:40PM (#1488686)
third element in the list containing the data about a person

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!

Re:Lisphp is a Lisp dialect written in PHP. by mahmud on Monday July 05, 2010 @01:30PM (#1488671)
You're still in the pedagogy sandbox; every real Lisp worth using has structures and objects:

  (defstruct person
    name age occupation)  => PERSON

  (make-person :name "Kris Kringle" 
               :age 71 
               :occupation "Santa") => #S(PERSON-1)

  (person-name *) ==> "Kris Kringle"
Re:Lisphp is a Lisp dialect written in PHP. by jacquesm on Monday July 05, 2010 @02:11PM (#1488736)
> You're still in the pedagogy sandbox;

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 ?

Re:Lisphp is a Lisp dialect written in PHP. by jules on Monday July 05, 2010 @02:28PM (#1488765)
If your reading material Lisp doesn't have some form of defstruct then it certainly is dated, or they are avoiding it on purpose. Every non-toy Lisp has it.
Re:Lisphp is a Lisp dialect written in PHP. by jacquesm on Monday July 05, 2010 @02:42PM (#1488800)
Ok, thanks. That helps. I started 'from the ground up', I figured that the best way to study a language is by looking at the way it was in the beginning since that's the most pure form of it. If 'lists' are as great as they are said to be you'd expect that things like structs and classes are optimizations, not essentials.
Re:Lisphp is a Lisp dialect written in PHP. by eru on Monday July 05, 2010 @04:46PM (#1489058)
Don't do that for Lisp. You will be stuck with the dynamic scoping that Lisp used to be plagued with in the beginning.

Go far a modern Lisp like Scheme. (You can ignore the syntax you don't want to deal with, yet.)

Re:Lisphp is a Lisp dialect written in PHP. by jules on Monday July 05, 2010 @04:27PM (#1489024)
Yeah, you can view it as an optimization: you can build defstruct & co on top of lists with macros. However, using ca(d)*r by hand is not advisable in any case...

Usually it goes the other way around: you implement lists on top of defstruct.

Re:Lisphp is a Lisp dialect written in PHP. by mahmud on Monday July 05, 2010 @03:44PM (#1488930)
Restricting yourself to Pure Lisp is like insisting on only dating virgins.
Re:Lisphp is a Lisp dialect written in PHP. by jacquesm on Monday July 05, 2010 @03:48PM (#1488939)
I have a very snappy comeback to that one but I highly doubt it will pass the censor ;)
Re:Lisphp is a Lisp dialect written in PHP. by eru on Tuesday July 06, 2010 @09:22AM (#1490867)
How about: "If she wasn't good enough for the other people, she won't be good enough for me."
Re:Lisphp is a Lisp dialect written in PHP. by KirinDave on Monday July 05, 2010 @01:53PM (#1488703)
Instead we all just use associative arrays.

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.

Re:Lisphp is a Lisp dialect written in PHP. by dahlia on Monday July 05, 2010 @11:56AM (#1488475)
I implemented cdr just to respect a Lisp tradition. Lisphp's Lisphp_List type isn't a linked list but a subtype of ArrayObject, which supports random access. So instead of doing:

  (car (cdr (cdr (cdr list))))
you should just do:

  (at list 3)
Re:Lisphp is a Lisp dialect written in PHP. by jacquesm on Monday July 05, 2010 @12:02PM (#1488493)
Yes, that's what I thought, and I don't see a real way around it.

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.

Re:Lisphp is a Lisp dialect written in PHP. by Scriptor on Monday July 05, 2010 @12:34PM (#1488554)
It could be mitigated in some cases as long as the garbage collector is working fine. For example, in a tail-recursive function that uses a first/rest pattern to go through an array a new copy would normally be allocated with each recurse. If LispHP can do some form of tail recursion elimination, it will theoretically take up constant memory and hopefully the GC takes care of the practical part.
Re:Lisphp is a Lisp dialect written in PHP. by jules on Monday July 05, 2010 @01:45PM (#1488694)
Even if memory usage weren't a problem you still have O(n) time for cdr. This may not be a problem if you implement the higher level functions (map, filter, etc.) efficiently.
Re:Lisphp is a Lisp dialect written in PHP. by eru on Tuesday July 06, 2010 @09:24AM (#1490871)
Yes, higher order functions (especially foldr (resp. reduce)) are the way to go.
Re:Lisphp is a Lisp dialect written in PHP. by sedachv on Monday July 05, 2010 @12:50PM (#1488586)
Since Lisphp is a new dialect, you don't need to worry about backward-compatibility. You should get rid of car/cdr entirely. There is no inherent reason for using linked lists for anything - even s-expressions. For example, no one has ever complained about the lack of car/cdr in Parenscript (although to be fair, Parenscript is not homoiconic, just a translator from CL to JS). Having a good backquote-comma templating syntax is more valuable.

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.

Re:Lisphp is a Lisp dialect written in PHP. by jacquesm on Monday July 05, 2010 @12:54PM (#1488595)
I think it's actually quite neat that it tries to stay close to the lisp code that you see in examples and books about lisp.
Re:Lisphp is a Lisp dialect written in PHP. by sedachv on Monday July 05, 2010 @03:19PM (#1488882)
What's the point of sacrificing something like platform integration for car/cdr? Anyone who is going to want to use Lisphp for real work is not going to have a problem writing their code to use arrays. Anyone who thinks that car/cdr is more valuable than platform integration is not going to use Lisphp for real work. And everyone else will come by and say "Lisphp has those weird car/cdr and it can't even work with PHP libraries without glue code, Lisp is a toy."
Re:Lisphp is a Lisp dialect written in PHP. by KirinDave on Monday July 05, 2010 @04:28PM (#1489028)
Call them what you want. First/car & rest/cdr are the classic tool for writing code that iterates across datasets.
Re:Lisphp is a Lisp dialect written in PHP. by sedachv on Monday July 05, 2010 @11:03PM (#1489818)
Recursion, map, and fold can be used for iteration. car/cdr is just one way to access elements of a sequence.
Re:Lisphp is a Lisp dialect written in PHP. by KirinDave on Tuesday July 06, 2010 @02:44AM (#1490193)
Think about what you just said and why it's not a valid rebuttal. I know you know better.

Hint: via recursion, how do you advance along a sequence in a collection-agnostic way?

Re:Lisphp is a Lisp dialect written in PHP. by sedachv on Tuesday July 06, 2010 @11:35AM (#1491264)
So now iterators mean car/cdr is "classic" so it should be present in all Lisp dialects from here to eternity?
Re:Lisphp is a Lisp dialect written in PHP. by KirinDave on Tuesday July 06, 2010 @12:37PM (#1491486)
Again, you can call them "first" and "rest" if you like.

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.

Re:Lisphp is a Lisp dialect written in PHP. by sedachv on Tuesday July 06, 2010 @04:11PM (#1492202)
So all those other programming languages that come with arrays and not linked lists are completely useless? Mildly useless? Only kind of useless? Or is it the case that it really doesn't matter?
Re:Lisphp is a Lisp dialect written in PHP. by KirinDave on Tuesday July 06, 2010 @05:05PM (#1492377)
Most of them DO provide a way to do this. For example, Ruby is array based but provides a way to do this through enum. The lispish way is first/rest. Clojure, a lisp with very novel data structures, does this just fine even with associative arrays and vectors. It introduces a seq abstraction to support it.

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?

Re:Lisphp is a Lisp dialect written in PHP. by sedachv on Tuesday July 06, 2010 @11:46PM (#1493245)
I don't have a dialect of Lisp. I work on a translator from a subset of Common Lisp to JavaScript (http://common-lisp.net/project/parenscript/). In particular, this subset does not have car/cdr, or any other list manipulation functions. No one has ever complained about this.

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?

Re:Lisphp is a Lisp dialect written in PHP. by dahlia on Wednesday July 07, 2010 @06:48AM (#1493864)
Lisphp's map/filter/reduce functions are implemented in the same manner that Parentscript does.

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.

Re:Lisphp is a Lisp dialect written in PHP. by jrockway on Monday July 05, 2010 @08:03PM (#1489488)
There is no inherent reason for using linked lists for anything

Uh, constant-time insertions?

Re:Lisphp is a Lisp dialect written in PHP. by sedachv on Monday July 05, 2010 @11:01PM (#1489814)
Did you read the parent post?
Re:Lisphp is a Lisp dialect written in PHP. by arghnoname on Monday July 05, 2010 @12:47PM (#1488578)
I immediately went to see how he implemented lists too with this kind of concern in mind. One way around the list issue is to write/use a C extension that provides a true linked list data type. I checked and there is such a thing in PECL, though who knows about quality.

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.

Re:Lisphp is a Lisp dialect written in PHP. by Scriptor on Monday July 05, 2010 @12:50PM (#1488587)
FWIW, there's an implementation of a doubly linked list in the SPL.

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).

Re:Lisphp is a Lisp dialect written in PHP. by arghnoname on Monday July 05, 2010 @01:02PM (#1488613)
Is that written in C? Implementing a linked list in PHP isn't difficult, but I'd imagine memory use would be prohibitively expensive. If that is not written as a C extension, and perhaps even if it is, presumably you'd get a big speedup if you implemented a list with common lisp operations in mind as an extension for a project like this. It could fall back to a PHP implementation if the extension is not/can not be loaded.

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.

Re:Lisphp is a Lisp dialect written in PHP. by jonursenbach on Monday July 05, 2010 @01:30PM (#1488670)
All SPL classes/methods are written in PHP. They're essentially PEAR classes that just come preinstalled.
Re:Lisphp is a Lisp dialect written in PHP. by Scriptor on Monday July 05, 2010 @01:39PM (#1488684)
Incorrect. The SPL is entirely implemented in C.
Re:Lisphp is a Lisp dialect written in PHP. by jonursenbach on Monday July 05, 2010 @03:06PM (#1488854)
Huh interesting.
Re:Lisphp is a Lisp dialect written in PHP. by salathe on Monday July 05, 2010 @03:36PM (#1488913)
s/entirely/also/
Re:Lisphp is a Lisp dialect written in PHP. by arghnoname on Monday July 05, 2010 @04:51PM (#1489069)
Ah, that's why my memory was fuzzy. I downloaded PHP and as of 5.3, the SPL does come with a double linked list, and a userland and C implementation are both in the tarball. Why is there a PHP version also?
Re:Lisphp is a Lisp dialect written in PHP. by jacquesm on Monday July 05, 2010 @07:26PM (#1489413)
Maybe as a fallback in case the extension isn't loaded ?
Re:Lisphp is a Lisp dialect written in PHP. by Scriptor on Monday July 05, 2010 @11:44AM (#1488446)
An alternative syntax for that is to cast $this as an array:

    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?
Re:Lisphp is a Lisp dialect written in PHP. by jimbokun on Monday July 05, 2010 @11:37AM (#1488423)
Is there a way to implement cdr more efficiently? (I don't know PHP.)
Re:Lisphp is a Lisp dialect written in PHP. by koenigdavidmj on Monday July 05, 2010 @12:13PM (#1488517)
In more traditional lists, the main data structure over which car and cdr munched was a linked list. car and cdr were just accessors for the two fields (usually used as a data container and a 'next' pointer).
Re:Lisphp is a Lisp dialect written in PHP. by jimbokun on Monday July 05, 2010 @02:55PM (#1488831)
I mean, is there any way to get that efficiency from PHP data structures? I guess you could implement a linked list data structure from scratch, but that would likely limit inter-operability with the rest of PHP.
Re:Lisphp is a Lisp dialect written in PHP. by tiles on Monday July 05, 2010 @04:26PM (#1489019)
cdr could return an array "object" where it references the entire array, and a pointer where it should start indexing. Instead of using linked-lists as the fundamental datatype, it could use array subsets.
Re:Lisphp is a Lisp dialect written in PHP. by koenigdavidmj on Tuesday July 06, 2010 @01:08AM (#1490028)
If I recall correctly, Clojure does something like this on most of its basic types. Since it wants users to avoid in-place modifications, it provides data structures that have modification functions that return new instances of the data structure with the changes made. These also do not regenerate the whole structure; they only use memory to point to the one modified/added element.

Please correct me if this is false.

Re:Lisphp is a Lisp dialect written in PHP. by gtani on Tuesday July 06, 2010 @02:22AM (#1490151)
Re:Lisphp is a Lisp dialect written in PHP. by Scriptor on Monday July 05, 2010 @10:48PM (#1489796)
Something like this could be very feasible, especially when combined with the array interfaces so that the fact it's an object with a moving pointer isn't even noticed.