I've created a simple implementation of Arc in C. This, I hope, will someday allow Arc to be used everywhere a C compiler is available, and no longer require Racket or MzScheme or whatever it is they're calling themselves these days.
At the moment the implementation is still very raw. The byte compiler can't even handle some of the definitions in arc.arc, but I'm working on fixing that. There is a simple REPL available, which I will shortly provide with readline support once I figure out how to use it properly. A lot of the standard library functions are not available. Error handling is virtually nonexistent. It segfaults a lot. It's only been tested on Ubuntu 11.10 x86-64 so far, although I think it might work on 32-bit x86. Well, we have to start somewhere I guess...
I've finally managed to fix most of the problems with the initial release and at last arc.arc now loads cleanly. Am in the process of testing each of the functions and macros in arc.arc to see if they work as expected. Now it seems that Arcueid is getting that much closer to being complete!
New in version 0.0.2:
- Readline support in the REPL. Note that you'll need the development headers for readline (libreadline-dev on Ubuntu) for this to work. This is also the reason why the REPL is GPLed instead of LGPLed.
- All of the Arc definitions are there, though they've not all been tested and they likely don't all work.
- Tracing and disassembly. There is a (trace) function that toggles tracing. Everything run on the REPL becomes traced until it returns. (disasm <somefun>) will disassemble a function and show its bytecode definition.
It's tagged v0.0.2 and is commit 602da1f00f7937e0fcf57c71b376673c5aab3ad6
Changes in this version include:
- Optimization of compose, complement, and andf in a functional position
- Math functions, everything Arc3 has available plus quite a bit more (every math function that C99 defines, including trigonometry, hyperbolic functions, etc.). Most of them work for complex arguments just as well.
- Basic I/O functions (read, write, disp, etc.) cleaned up and implemented. Seems that call-w/stdin and similar had to be implemented like protect, which is annoying, but that had to be how it was done to get them to function in the face of continuations and exceptions.
"Seems that call-w/stdin and similar had to be implemented like protect, which is annoying, but that had to be how it was done to get them to function in the face of continuations and exceptions."
I, for one, appreciate that you're doing things the way they have to be done, lol.
Any plans to generalize 'call-w/stdout and 'call-w/stdin to 'parameterize? Now that I take a look at http://docs.racket-lang.org/reference/parameters.html, there's one more complication I hope is already on your mind: Threads.
I don't tend to care much about threads myself, but since they're on your roadmap, hopefully you have a good plan for them and the way they interact with 'call-w/std{out,in}. XD
If I understand the notion of parameters correctly from yours and Pauan's mention of them (I'd not heard of them before now), they are essentially a way to do dynamic binding in a language like Arc that normally uses static binding. This is in large part exactly what call-w/stdin does with stdin: it sets up a dynamic binding for that function. Apparently, in my attempts at implementing this functionality I've also independently kludged up a special-purpose version of what Racket calls a continuation mark, and obviously doing such a thing bothers me to no end.
Now that I think about it, implementing parameterize might actually not be that difficult, and Pauan's implicit parameters might actually be easier than explicit parameters that have to be applied in order to obtain their values. It would also get rid of the special-purpose "continuation mark" I created to support call-w/std(out|in) and replace it with a more general-purpose structure capable of storing other dynamic bindings as well.
Well, indeed threads are on my mind, but I will keep things simple for now, and make them green threads whose scheduling is controlled entirely by Arcueid's runtime. I had for a time considered using real POSIX or other OS-level threads to be able to take advantage of multiple cores but soon realized that this would introduce quite a bit of complication. Using real threads affects just about every aspect of the implementation. For instance, I am at the moment using an incremental garbage collection algorithm that ought to be amenable to multi-threaded operation in theory but in order to really use it in a multi-threaded context I'd also have to have a good multi-threaded memory allocator, and by the time I'd had a look at all the literature on such algorithms I realized that I was in way over my head.
Green threads simplify matters considerably. This means that call-w/std(out|in) and the more general notion of parameters can be handled without too much trouble. In the plan I have for Arcueid's green threads, a thread is basically a structure that contains everything that the virtual machine needs to run, including all continuations. The only thing directly shared by all threads is the global environment, and then I'd also have to make available a flattened version of the structures I used to store the call-w/std(out|in) bindings from the thread's creator, and the more general dynamic bindings created by parameterize as well.
And no, while Arcueid's main goal is to produce a version of Arc compatible with at least Paul Graham's Arc3.1, I am of course not above introducing improvements and extensions, provided that they do not also break compatibility. I'd like to be able to at least run news.arc unmodified before I release version 1.0.0. :)
"Apparently, in my attempts at implementing this functionality I've also independently kludged up a special-purpose version of what Racket calls a continuation mark, and obviously doing such a thing bothers me to no end."
Why? Are you worried your runtime will be exactly like Racket but less mature? When I looked at your call-w/std(out|in) commits, I liked your approach exactly because I noticed it was in the same vein as continuation marks. :-p
As you've noticed with complex numbers, Arc exposes lots of accidental complexity that it inherits from Racket. In fact, speaking of accidents, Arc 3.1 without modification exposes pretty much all of Racket: http://arclanguage.org/item?id=11838
When it comes to threads and parameters, I'd say Arc pretty much specifies nothing and leaves it up to Racket to provide the meaning and implementation. Arc literally defines 'call-w/stdin and 'call-w/stdout in terms of Racket's 'parameterize. If Arcueid doesn't end up with (internal) functionality equivalent to thread cells and continuation marks, there's a good chance it'll have certain corner-case inconsistencies with Arc, even if there aren't enough inconsistencies to break the programs we actually care about.
But even so, I wouldn't worry about it too much. I personally consider Arc to have shoddy support for threads (just exposing a tiny subset of Racket's functionality and imposing a GIL) and also for reentrant continuations (not defining 'dynamic-wind, implementing loops with mutation), so I don't really blame an Arc implementation for being incompatible in these areas. In some cases, full compatibility might be more harmful than not trying!
---
"I had for a time considered using real POSIX or other OS-level threads to be able to take advantage of multiple cores but soon realized that this would introduce quite a bit of complication. Using real threads affects just about every aspect of the implementation."
If you want to give an Arc program power to take advantage of those, but you're having trouble with multithreaded allocation, an alternate path might be to have the Arc namespace and most data structures be local to an OS thread but then to have other tools to write and read manually-managed shared memory. I dunno, maybe that's not very inspiring. :-p
---
"The only thing directly shared by all threads is the global environment, and then I'd also have to make available a flattened version of the structures I used to store the call-w/std(out|in) bindings from the thread's creator, and the more general dynamic bindings created by parameterize as well."
Er, local scopes and first-class data structures might need to be shared too, right?
(let foo (list nil nil)
(for n 1 10
(thread (push n foo.0) (push n foo.1)))
(def get-foo ()
foo))
"Why? Are you worried your runtime will be exactly like Racket but less mature?"
Not in the slightest. It just bothered me that I had to embed a special-purpose data structure inside Arcueid's continuations just to support one language feature. Now that I see that there is a natural generalization to this feature, that makes me feel a lot better. :)
'protect is implemented with 'dynamic-wind, so the only functionality we lose is the ability to specify a pre-thunk. Are there any areas where that would be useful?
Dynamic-wind gives us most of the ability to implement parameters ourselves. We just mutate a box upon every entry and exit of the expression. Unfortunately, it might take some crazy trampolining to get the last expression of (parameterize ...) in tail position. I'm not even sure if tail position is possible....
I think the last missing piece is thread-friendliness. In the face of threads, we'd need the box to be thread-local like Racket's parameters. But my point here is just that the pre-thunk is useful for something. ^_^
"[...] they are essentially a way to do dynamic binding in a language like Arc that normally uses static binding. This is in large part exactly what call-w/stdin does with stdin: it sets up a dynamic binding for that function."
That is correct. In fact, in Arc 3.1, std{in,out,err} are Racket parameters[1], and call-w/std{in,out} use Racket's parameterize. My point was merely that it is useful to provide parameters to Arc programmers so they can define their own parameters beyond just stdin/stdout/stderr.
* [1]: That's why you need to use (stdin), (stdout), and (stderr) rather than stdin, stdout, and stderr.
---
"And no, while Arcueid's main goal is to produce a version of Arc compatible with at least Paul Graham's Arc3.1, I am of course not above introducing improvements and extensions, provided that they do not also break compatibility."
Glad to hear it. I would just like to note that any changes whatsoever will break compatibility. For instance, if you provide a "parameterize" form, a library written in Arc might also define a "parameterize" global, etc. My feeling on such things is that there should be a social convention for specifying implementation-specific global variables.
Something like, "if a global variable starts with % it is implementation-defined, so portable Arc libraries shouldn't use or define global variables starting with %".
Then your implementation could provide "%parameterize" to Arc and there would be no problems, because Arc libraries aren't supposed to use variables starting with %, so there's no conflict.
This should be solely a social convention, not enforced by the compiler. I may want to write an Arc library that does use/define implementation-specific globals, while
understanding that such a library won't be portable and may break in the future.
"Any plans to generalize 'call-w/stdout and 'call-w/stdin to 'parameterize?"
As a side note to this, I think it would be very preferable to have a `parameterize` form which `call-w/stdin` and `call-w/stdout` would call. It should behave similarly to Racket's parameterize.
This isn't necessary for an implementation of Arc 3.1, but it's very useful in practice: you could provide a way for users to create their own parameters and then call parameterize on them. This is what ar and Nu do, and it's incredibly convenient, especially when you provide a way to make the parameters implicit[1].
It really does depend on your goals, though. Do you intend for this to be just an implementation of Arc 3.1 and nothing more? Or do you intend to provide convenient features that Arc 3.1 doesn't have? Your work on numerical functions seems to suggest that you're not entirely against extending your Arc runtime to do things that Arc 3.1 doesn't.
---
* [1]: By "implicit parameters" I mean parameters that you don't have to call to extract their value. In other words, you can just say `stdin` rather than `(stdin)` for instance.
Whew, lots of new features and fixes in this release! Highlights include:
- on-err, err, and details implemented
- ccc (call/cc) implemented (actually proved ridiculously simple, at least until protect was implemented anyway)
- protect implemented (it's astounding to see how much implementing this function complicated the implementation of ccc and exception handling)
- major bug fix: evaluation order is now left to right. Previous versions stupidly did right to left evaluation. We didn't do a lot of work with side effects before which is why it went unnoticed for so long.
I just have to wonder if there's a better way of implementing protect than the rather kludgy way that I wound up doing it.
"I just have to wonder if there's a better way of implementing protect than the rather kludgy way that I wound up doing it."
Based on a quick skim of https://github.com/dido/arcueid/commit/65a252a87fd817ec33f21..., it looks like you're doing it in a similar way as Rainbow, lol. You're collecting protect handlers on your way down and then pushing them all back onto the stack in a particular order.
I think a more natural way to do this might be to stop at the first protect handler, then enact instructions that accomplish "call this handler, pop the frame of (or otherwise exit) the protect body, then make the same continuation call again." In fact, I wonder why you and Conan Dalton didn't do this to begin with. :-p
Just to explore this a bit, to help both of us understand... if this approach were extended to dynamic-wind, if you encountered a dynamic-wind form on your way up the stack, you might stop there and enact instructions of the form "call this handler, push the frame of (or otherwise enter) the dynamic-wind body, then make the same continuation call again." Does this make sense? Part of my concern is to have clear semantics for what happens if a continuation call exits or enters a handler block.
Meanwhile, an alternate (but not necessarily better) way to do it is to define a core language without 'protect and then wrap that core in a standard library that hides the original version of 'ccc and exposes a version that consults a global stack of 'protect handlers. This Ruby library does that: https://github.com/mame/dynamicwind.
Like akkartik before me, I'm having some trouble. Here's my story:
Started from a barely used Linux Mint 12 installation.
Installed libgmp-dev, check, and git. (The packages pkg-config,
autoconf, automake, and libtool were already installed.)
Created an SSH key and set it up with GitHub.
mkdir -p ~/mine/prog/repo
cd ~/mine/prog/repo
git clone git://github.com/dido/arcueid.git
cd arcueid
autoreconf -i
./configure
make
Got the following error, among other output:
/bin/bash ../libtool --tag=CC --mode=compile gcc -DHAVE_CONFIG_H -I. -I.. -g -O2 -MT compiler.lo -MD -MP -MF .deps/compiler.Tpo -c -o compiler.lo compiler.c
libtool: compile: gcc -DHAVE_CONFIG_H -I. -I.. -g -O2 -MT compiler.lo -MD -MP -MF .deps/compiler.Tpo -c compiler.c -fPIC -DPIC -o .libs/compiler.o
compiler.c: In function 'macex':
compiler.c:81:9: error: 'debug' undeclared (first use in this function)
compiler.c:81:9: note: each undeclared identifier is reported only once for each function it appears in
make[2]: *** [compiler.lo] Error 1
Do a git pull. Oops, some debugging code I was using temporarily made it into the repo. Will try to ensure this doesn't happen again. Last commit should be: fdeb76087b48ff19d9f2666d05a4429ac4145b24
to the end of /etc/ld.so.conf and then run ldconfig -v. This is a frequent issue when it comes to shared libraries that get installed in /usr/local/lib. I have no idea why most Linux distros don't like to put /usr/local/lib in ld.so.conf by default. It is extremely irritating, since most everything one builds from source installs there by default.
Interestingly, this is what /etc/ld.so.conf looked like before:
include /etc/ld.so.conf.d/*.conf
And this was in /etc/ld.so.conf.d/libc.conf:
# libc default configuration
/usr/local/lib
The "include" line doesn't seem to do what it looks like it's supposed to do. :-p The man page for ldconfig doesn't mention "include" at all (nor #-comments...). It would be funny if Linux Mint came with this kind of ld.so.conf but its version of ldconfig thought "include" was just another directory in the list.
Another day, another release. Unit testing against arc.arc has uncovered more serious bugs and missing features in the code, and now we have version 0.0.3. Get it here:
Or clone the tag from the git repository if you prefer.
New in version 0.0.3:
- A lot of bug fixes, most notable is the fact that 'nil and nil were not the same in previous versions.
- Readline support in the REPL should be a bit cleaner
- Some feeble attempts at tail call optimization
- Some compatibility fixes for reference Arc, mainly in the behavior of the type function, e.g. (type 1+1i) => num, where Arcueid used to say (type 1+1i) => complex. The previous behavior (which I think might be more than useful) is available in the atype function.
- Tracing support now disabled by default. Can be enabled with a command line switch.
I'm a bit of an anime/manga/visual novel fan and one of my favorites is a show called Shingetsutan Tsukihime (Tsukihime, Lunar Legend). The main heroine is named Arcueid Brunestud and I thought the name was too good to pass up for this kind of project. I hope Type Moon doesn't give me problems over this later...
I haven't had a lot of time to work on it which is why it took so long. It's just a side project... In retrospect I probably should have announced it sooner but I wanted to have something a bit usable first.
I use Emacs org mode which is why the file arcueid.org is named as it is.
You'll need the autotools installed (autoconf/automake/libtool). Do an autoreconf -i in the main project directory. This should generate a configure script from the configure.in and all of the automake and libtool stuff for it. From there it should be configure / make / make install the way it normally is. You can do configure --enable-unit-tests if you have GNU Check installed so that you can run the unit tests.
I ran autoreconf -i, and then configure, and I ran into this error:
./configure: line 12048: syntax error near unexpected token `CHECK,'
./configure: line 12048: ` PKG_CHECK_MODULES(CHECK, check >= 0.9.4,'
So this means GNU check is not installed? It's not recognizing the PKG_CHECK_MODULES macro. Where can I install GNU check from? Googling found nothing.
It's the unit testing framework I'm using, and shouldn't be necessary in a tarball distribution (maybe I should make one soon...). The error looks like you also don't have pkg-config installed (http://www.freedesktop.org/wiki/Software/pkg-config).
All of these are readily available in the Debian / Ubuntu repositories. It has no dependencies that have to be built from source, at least on Debian/Ubuntu. Package name for check is just 'check' and pkg-config is just 'pkg-config'. What distro are you trying to build Arcueid under anyhow?
I'm just using ubuntu. Lucid, I think. I installed check and pkg-config, no problems. But I still see the same error.
On a second machine I'm using linux mint which tracks the debian rolling release. There:
$ ./configure
..
checking gmp.h usability... no
checking gmp.h presence... no
checking for gmp.h... no
configure: error: in `/home/akkartik/arcueid':
configure: error: Bignum (libgmp) test failed (--disable-bignum to disable)
See `config.log' for more details
$ sudo apt-get install libgmp10
libgmp10 is already the newest version.
Have you got libgmp-dev installed? It cannot find the development headers which you'll obviously need to compile it. Anyhow, you can use --disable-bignum if that still doesn't help. If you're still having problems you can download a tarball of Arcueid 0.0.1 in the files section of the github page. That has a configure script so you ought to be able to ./configure && make && make install from there. I should try building the thing on a clean install of Ubuntu to fully identify all the dependencies for building straight from the cloned sources.
Still unclear why ubuntu lucid is having trouble. It's a pretty vanilla server distro. I'll keep pottering with it, see what I can find out.
What do I do after building it? I tried running src/arcueid, both from the top-level dir, and from the arc dir. It segfaulted each time. Poking around with gdb now.. oh, do I have to make install before I can use it?
(I never realized how complex the makefiles get when you use autotools..)
Well, the arcueid binary expects to find arc.arc in /usr/local/share/arcueid, and like I said there's practically no error handling. You can either do a make install (which should copy arc.arc to that place where the arc binary can find it), or you can run it as src/arcueid arc/arc.arc (explicitly specifying the path to arc.arc on the command line). Oh, and do a git pull!
You don't, at least not for now. I found it faster to just write a version of the compiler in C using compiler.arc as a prototype (the fact that I've done this should be obvious by comparing compiler.c and compiler.arc). Seems there are a few more bugs in the compiler: the or macro seems to be expanding all wrong, and anything but nil crashes it. I need to take a closer look.
Oh, and please do a git pull now before you do anything else. I've just managed to fix the bug that was preventing arc.arc from being loaded properly, although of course arc.arc makes reference to many global functions which still aren't defined in the core and will crash the interpreter. Next step will be to find these and implement them.
