Arc Forumnew | comments | leaders | submitlogin
Tips on implementing arc
6 points by shader 5114 days ago | 14 comments
I was thinking of writing yet another implementation of arc on a different platform - this time .net. My motivations for this are several: So far Java has been the main target for alternate implementations, I like .net and C#, I might be interested in experimenting with F#, and I'm interested in DirectX based game development.

So my question is, what have you learned from the process of re-implementing arc? Are there any tips that you have on where to start to keep the complexity down and the progress encouraging? Useful tricks or ideas you've discovered along the way? How do you handle mapping between arc and the standard library/object model and why? What features of arc have you found to be difficult to implement, and did you decide to keep them and deal with it (how?) or skip them and move on?

I'm mostly interested in the lower level of implementing arc at this point, rather than higher level design decisions concerning changes you wanted to make to the language, etc. but if they were motivated by your platform, or resulted in an easier implementation, I'm interested about them too. In fact, I'm probably interested in whatever it is you're willing to tell me, so you might as well ramble as long as you like.

So, basically consider this a thread to share/brag as much as you like about your arc implementation, with a slight eye towards helping someone else get started implementing arc on a non-lisp platform. Thanks!



3 points by jazzdev 5109 days ago | link

I started Jarc by writing an s-expression reader. Then I implemented the 9 Arc primitives in Java and then I started writing eval in Java. Then I incrementally added the missing global functions used in arc.arc - that took a while, but wasn't particularly difficult.

I spent a lot of time thinking about the Arc to Java interface. I wanted it to be as light weight as possible and as brief as possible, in keeping with the Arc goal of making programs shorter. In particular, I wanted to avoid any 'import' or 'defcall' requirements if possible.

Another important consideration is how much of your interpreter can you write in Arc. I was anxious to stop writing Java and be able to add missing global functions in Jarc as soon as possible. At last count, I have 61 functions implemented in Java and 73 in Jarc itself.

Jarc doesn't have first-class continuations or fractional numbers. The interpreter also doesn't do tail call elimination. (I did write a compiler this year to do tail call elimination in recursive functions.)

From what I learned working on Arc and talking with Conan about Rainbow, implementing a continuation passing style interpreter is the way to go if you want first-class continuations and tail call elimination.

Writing Jarc has been great fun, and I've learned a lot.

-----

2 points by shader 5108 days ago | link

"I started Jarc by writing an s-expression reader. Then I implemented the 9 Arc primitives in Java and then I started writing eval in Java. Then I incrementally added the missing global functions used in arc.arc - that took a while, but wasn't particularly difficult."

That's how I planned to start the implementation, but I've also considered writing a compiler that translates the arc code into MSIL using Reflection.Emit. That would allow me to do tail-call optimization, and possibly CPS.

So what do you have currently for your Arc/Java interface, and what are your thoughts on difficulty of implementation, ease of use, etc. associated with that choice? Are there other options that you considered and discarded, or haven't gotten around to implementing yet? I was thinking of trying to treat assemblies, namespaces, classes, and objects like hash tables, and letting (obj 'name) access the member, but I don't know how well that will work with mostly static typing.

I'm not sure what to think about fractional numbers. I don't think I've ever had a good reason for using them, so I won't bother implementing them myself until I do.

-----

1 point by evanrmurphy 5108 days ago | link

> implementing a continuation passing style interpreter is the way to go if you want first-class continuations and tail call elimination.

I'm intrigued. Is this how most languages get tail call elimination?

-----

3 points by fallintothis 5108 days ago | link

Is this how most languages get tail call elimination?

Well, more languages do TCO than use CPS -- never mind a CPS interpreter. Though CPS is functionally equivalent to the more popular SSA (Static Single Assignment) form, it remains relatively unused; see http://lambda-the-ultimate.org/node/3467. I imagine the comment about using an interpreter is rooted in http://billhails.net/Book/v10.html, a great chapter from a book that goes through writing a Scheme-like interpreter in Perl, including a CPS transform and TCO using a trampoline. (For quick info about what those mean, there's of course http://en.wikipedia.org/wiki/Continuation-passing_style and http://en.wikipedia.org/wiki/Tail_call)

In fact, CPS benefits from TCO. By converting a program into explicit CPS, every function call becomes a tail call (to the current continuation); without TCO, stack space would run out quickly. Certain TCO implementations can also use CPS; see http://en.wikipedia.org/wiki/Tail_call#Implementation_method....

A great discussion about TCO implementation is http://lambda-the-ultimate.org/classic/message1532.html. To get really into it, the master's thesis at http://users.cecs.anu.edu.au/~baueran/thesis/ talks about tail calls in GCC (I've not read it, but it looks interesting).

-----

1 point by evanrmurphy 5107 days ago | link

Wish I could upvote you more than once. Great reply.

-----

2 points by aw 5112 days ago | link

There are features that Arc gets for free when implemented on top of Scheme that may be hard on other platforms such as full continuations, tail calls, and the numeric tower e.g. exact rationals. Since you sound like you're interested primarily in a practical system (DirectX game development), you can avoid getting bogged down by not worrying about the features you don't need. (For example, you might choose to have this implementation of Arc only support escape continuations).

To keep the complexity down and the progress encouraging, I find it helpful to work on an implementation as a series of steps instead of doing everything all at once. For example, you might start by implementing just enough of the runtime so that you can load the first form in arc.arc, do. Then implement just enough more so that you can implement safeset, and so on.

-----

2 points by akkartik 5114 days ago | link

I've been itching for reasons to brag further about wart (http://arclanguage.org/item?id=12814) but sadly I have nothing useful to say here since it's built atop lisp.

I wouldn't build lisp atop a non-lisp (buggy, ad hoc, informally specified, etc. etc.) runtime. Except maybe erlang. There's lisp platforms with decent enough performance that that doesn't seem like a factor, and somehow libraries alone don't seem like a compelling enough reason. Do you have any other reasons I haven't considered?

I think another reason I steer clear of the runtime is that I know I won't have the patience. A good runtime takes 10 years to build (http://www.joelonsoftware.com/articles/fog0000000017.html).

"I'm mostly interested in the lower level of implementing arc at this point, but if [your design decisions] resulted in an easier implementation, I'm interested about them too."

Hmm, I did describe how using common lisp (rather than scheme/racket) simplified my implementation.

-----

2 points by shader 5113 days ago | link

"I wouldn't build lisp atop a non-lisp (buggy, ad hoc, informally specified, etc. etc.) runtime."

Lisp-on-lisp can be just as ad-hoc, informally specified, and buggy. I see no real reason that arc needed to be implemented at all. After all, it's "just scheme" with a few simple aliases right? I'd argue that arc is also pretty informally specified, and sometimes even buggy. Does that prevent us from using it? No. Which tools are used for developing software has little to do with how well it is written. Yes, there is a very high probability that my lisp will be all of the above, but the line you are quoting is specifically about unintentional implementations of lisp, not intentional ones. Unless you're claiming that all other non-lisp platforms are buggy ad-hoc and informally specified, in which case I don't really know what to say.

Really, I'm just taking a long time to say that not all lisps are written in lisp, and that being written in lisp is neither necessary nor sufficient for a good lisp implementation.

"somehow libraries alone don't seem like a compelling enough reason"

Libraries can be a very compelling reason when deciding which language to use. And since I mainly want to write a language that I can use, having good library support is a wonderful feature. Don't get me wrong, I love arc and its easy hackability, but several times I've tried to do something in arc for which the library support just isn't there or is somewhat deficient, and then there's not much I can do about it. Having library support can make a big difference in ease or even possibility of writing a given application. The arc challenge without arc support for web development would be a lot trickier, but an arc challenge without arc support for sockets would be nigh impossible without writing external code.

However, libraries aren't the only reason I'm writing for a non-lisp platform. I also consider it to be an interesting programming exercise, and it puts more of the system under the programmers control. Right now in arc the reader and similar low level pieces are mostly unavailable for hacking, since it's all written in scheme. As such, most of us end up using something like rlwrap for the shell, and overloading ssyntax for all of our reader modification.

As good as those reasons sound, I am not trying to implement arc on .net because I think it will improve arc. Rather, I'm implementing arc on .net because I think it will improve myself as a programmer, and .net as a platform. As far as I know, there are no implementations of lisp on .net that are even remotely usable, while on the JVM there is at least Clojure as well as half a dozen arc implementations. If I want to do any lisp based application development for .net and DirectX in particular, at this point I pretty much have to write it myself.

-----

2 points by akkartik 5113 days ago | link

I am not trying to implement arc on .net because I think it will improve arc. Rather, I'm implementing arc on .net because I think it will improve myself as a programmer, and .net as a platform.

Yeah that makes sense. I certainly didn't mean to discourage you or anything.

I see no real reason that arc needed to be implemented at all. After all, it's "just scheme" with a few simple aliases right?

_Precisely_ the point of wart. I want to maximize the 1-1 correspondence between arc and common lisp to minimize the work I have to do. I'd love to get you to take a look at the code and tell me what you think.

I wasn't claiming lisp implementations should always be atop lisp (clearly impossible), or that lisp implementations can't be buggy. Venturing down the long hard road of dealing with an immature runtime is just not for me, that's all :) (I was a systems programmer in a past life.)

having good library support is a wonderful feature

I find I can often build what I need. Or I can leverage the FFI. Or I can setup a server to provide services from other languages. All those seem relatively painless in lisp, and between them seem to cover all use cases. This is how I stay on easy street where the views are nice and the demons have been banished.

-----

1 point by evanrmurphy 5113 days ago | link

> but sadly I have nothing useful to say here since it's built atop lisp

Maybe your exploration of nil vs '() could be useful here. [1]

---

[1] http://arclanguage.org/item?id=11723

-----

1 point by shader 5113 days ago | link

That's true. Any decisions affecting the core and the reasoning behind them would be useful at this point.

In fact, it would be really interesting to hear more from pg explaining some of the cryptic comments in the original source and some of the deviations of the current arc from the designs that he outlined in his earlier essays. If the explanation for most of them turns out to be "it was easier" or "it looked better" that's ok, I just wonder some times whether shortcuts and aesthetics explain the difference, or whether there were some deeper, hard-earned insights involved.

-----

1 point by akkartik 5113 days ago | link

At least for nil vs () and a couple of other issues, I've tramped up and down over the territory and reassured myself that there aren't any huge subtleties. I've also tried to ensure (github, unit tests) that any subtleties I find are exposed to anybody following.

Arc really is that simple :)

-----

1 point by akkartik 5113 days ago | link

Ah, good point, thanks for the suggestion. Here's a more recent snapshot: http://arclanguage.org/item?id=12661

-----

1 point by evanrmurphy 5114 days ago | link

The first things that come to my mind are t/nil, conses and tail-call optimization.

Ah, I actually have to come back and finish this response later. Sorry for only leaving a teaser!

-----