Both Haskell & Arc quicksort are functional (they don't mutate their input), which means they can't have quicksort's usual O(1) additional space overhead. Their time complexity is the same, though.
In-place quicksort is most easily done with an array-like datastructure, so vectors for Arc (if they're mutable, which I think they are). It's probably possible to do it by mutating conses as well, but it would be tricky.
I think OO is overblown but contains several useful concepts. I like functional programming, type theory, lisp (duh), macros, monads, etc.
I like type theory, abstract algebra, set theory, logic, category theory. I mildly dislike continuous math, especially standard analysis. Nonstandard analysis is interesting --- because it takes an algebraic approach (axiomatise infinitesimals!) to a problem that usually uses limits.
This is not a good primitive. It can be built using assign, and having this instead of assign be primitive complicates the arc compiler, instead of merely introducing another macro.
- A maintained, portable, stable, widely-available implementation.
- I'm iffy on whether Racket is widely-available enough for a Racket-based implementation to satisfy me.
- A module system.
- A package-distribution system.
- Better and more libraries, or a good, standard way to hook into racket's libraries.
- Depending on the project, a reasonably fast implementation.
On looking into the matter, it seems Racket is available on Windows and OS X, so that's basically taken care of. Hopefully its source compiles on non-x86{,_64} platforms as well, but I don't really develop for those.
I'd suggest just trying to compile it on whatever machine you might have in mind.
git clone http://git.racket-lang.org/plt.git
cd plt/src
./configure
make
make install # this builds executables and docs in place; takes a longish while
Turning arc into racket is exactly how the arc compiler works internally. See the ac function in ac.scm, which takes an arc expression and turns it into a racket expression, and acompile, which takes an arc file and turns it into a racket file.
There are nonetheless a few issues with using arc code in racket, such as the arc runtime, interaction with racket's require system, and the fact that arc alters the reader to allow for square-bracket anonymous fn syntax. I haven't worked with arc in a while, so I don't remember them in full. Hopefully someone else will chime in with details. But basically, yes, with a little work, you can use arc code from racket.
I can't say I'm surprised that breaking the abstraction of cons cells that way ended up being a problem. This new implementation, if anything, breaks the abstraction even more (exploiting the fact that viewing a cons cell as a vector happens to result in mutating certain parts of the "vector" having the desired effect on the cons). Arc (anarki at least) really should switch over to using racket's mutable pairs.
Actually, speaking of that, why not just use unsafe-set-mcar! and unsafe-set-mcdr!? I find it far more likely that the representation of mutable pairs will continue to coincide with that of pairs than that the representation of vectors will, and a quick examination at the mzscheme prompt seems to confirm my suspicion. unsafe-set-mcar! and unsafe-set-mcdr! work just fine on cons cells. I'm using plt scheme 4.2.2, not racket, though.
Egad, you are thoroughly right and I have rewritten the post. mentally smacks myself on the head Thank you, that is a much better implementation. I'm a little bit disappointed that it's so easy...
Uh-oh, the edit window has timed out on my post, and I've noticed that my version doesn't do any type-checking. That is el baddo. So far, it hasn't caused things to crash yet...
arc> (= x 'meh)
meh
arc> (= (car x) 2)
2
arc> x
meh
...but that's just luck and I wouldn't rely on it. [It does destroy the world when you set the car of a table.] Better version is here:
Man, I really wish I could continue editing my original post, 'cause without the type-checking, it's kind of a nuclear bomb in case someone accidentally uses it on a table. Perhaps I should just have left the post unchanged, or just added "Edit: Look in the comments for improvements" at the bottom.
rev isn't idempotent, however, rev:rev (rev composed with itself) is, which is I suspect what fallintothis was thinking. "Involutary" (which term I've never run across prior to this) appears to be a term for just this property: that the square is idempotent.
Involution is more strict than the square being idempotent; it also must be the identity function. I.e. abs^2 is idempotent but abs itself is not involutary, since abs^2(-1) = 1 != -1
3. Why pattern matching is way cooler than car/cdr; why arc isn't a 100-year language; comparative study of macro systems; comparative study of module systems; implementation of a bootstrapping arc compiler; implementation of my pet lisp, chao, which is bootstrapped from arc and compiles to a (hopefully) portable IL... I have lots of ideas.
4. Summer break, since that's when I'm in Silicon Valley.
5. If someone wanted to destroy Arc as a language, this would be the time for them to do it. Everyone interested, gathered in one small space. Be on your guard, comrades! :P
I mostly agree with 3! It might be a good place to finally take the decision about the module system.. It obviously would be awesome if it could be webcasted. (Montreal, Canada here :p)
Yes, they should, because they can be changed within dynamic scope by 'w/stdout etc, and this doesn't work unless they correspond to parameters in mzscheme, which need to be called to get their current value.
Using your dynvar hack, you could avoid this, but that's hardly "not changing the language", now, is it?
You can quote anything, literally anything. Why wouldn't you be able to? The only caveat, if you can call it that, is that you can't necessarily 'write out the resulting code sexpr readably (for example, functions are not, as a rule, writable).
The only reason why you need to quote certain things at all is because the arc compiler is very picky about its input -- it cases on the type of the sexpr it's compiling, and if it doesn't recognize the type it throws an error -- but things inside a quotation escape this examination. If this weren't the case, and it instead just passed them through, then functions could be embedded directly instead of quoted; and everything (I think) other than symbols and lists evaluate to themselves in mzscheme.
