Thanks! I don't really have any concrete questions, but any advice on learning Lisp would be welcome. Maybe I should learn Scheme and read SICP before learning Clojure? Maybe I should forget Lisp altogether until I have more experience with programming in general? I get the feeling Arc is not the best place to start learning Lisp.
I did have a short look at the tutorial, but I had a bit of a hard time diffing it mentally, as I am still fairly new to Lisp. But I will definitely point him in that direction if he is interested in having more than a cursory glance.
My one-sentence summary of arc: minimalist common-lisp-flavored lisp-1 atop scheme. It takes quasiquoting and some other more dynamic design choices from common lisp and overlays them atop the more modern Racket runtime with as little code as possible. Other than that it's lots of tiny ergonomic conveniences. Maybe you should read/show him the tutorial next: http://ycombinator.com/arc/tut.txt. And arc.arc is a pretty fun read: https://github.com/arclanguage/anarki/blob/3fc14d16e9/arc.ar.... What really got me into arc was writing programs in one split window with the friggin compiler for my language in the other.
But yes, it might make sense to avoid pulling in spliceable-list. As long as you can see what it's being used for, there are other ways to get the behavior it provides, though the easy alternatives will be slower.
But as you're finding out, it's work. You can't just pull in dependencies willy-nilly. Fundamentally, arc3.1 and anarki are both about sharing code as ideas, not code as functionality. We've repeatedly mentioned how neither makes promises of compatibility. You can't treat them as interchangeable lego blocks and expect them to just snap into place. No matter how similar they look, they're not close to each other. They're really more like separate universes that you're 'wormholing' matter and energy through. Start with the assumption that that will cause some annihilation unless you're willing to be careful and detail-oriented. How much time should it take? Maybe "dawn to midnight" is reasonable. There's no way to tell until you try to do it. You're in terra incognita with every single little task like this.
Anarki tries to make such wormholing easier by providing tests. Tests are a better "unit of transplanting" than functions or something else. Try to first understand what's involved in making a test pass, then copy the test over, then make it pass. Think of the file upload code in anarki as merely an exposition to help guide you when creating your own version.
But this is harder when transplanting to arc3.1 because it has no tests. Honestly I have no idea why you stick with it. Imagine I'm a villain in a superhero movie or a bollywood movie: "where is your savior now? How long will you be faithful to him?" :) Stay with one repo and you'll be out on a limb less. Pick a repo with tests, and you won't be locked in to it when you do need to go out on a limb and transplant code from somebody else.
I feel bad that you struggled for so long by yourself. If you'd ask for help sooner, and if you provide more information, I think your path could be much eased. For starters, it sounds like you've added to arc3.1 over the years. It makes it harder for me to be sure that any code I suggest won't harm you. I recently made a suggestion to tvvocold over email that caused problems because it turned out he'd made changes I wasn't aware of. I'd prefer not to have more of that on my conscience. Can you share the current state of your codebase?
The final thing that helps us help you: forget about compatibility. Programming gets harder the more constraints you add, so try to focus on concrete issues rather than imaginary abstractions. How do you know your existing changes to arc 3.1 are "compatible"? If someone not called pg magically included file upload atop arc3.1, how would you be sure it was "compatible"? In my opinion the reason that "sending anything to a server requires this whole complicated way of multipart encoding/decoding stuff" is the expectation that things just work when you transplant them from one setting to another. I'll make a moral judgement as kindly and respectfully as I can: To the extent that you care about compatibility, you're part of the problem. Uploads are complicated because somebody else decided they didn't want to know about the details and just wanted uploads to work. Add thousands of such people with slightly different scenarios and vague fears of breaking each other, and you end up with all this complexity.
I stopped at spliceable-list (in scan-past) which needed lib/spliceable-list.arc. I didn't want to go down the rabbit hole of loading it after I saw a redefinition of append.
The dependencies might not be incompatible but I didn't try.
So, today I learned that cons cells, despite having O(n) behavior, are really fast. They outperform mutable JS arrays at random inserts!
It's only once you get up to ~100 elements that AVL trees start to outperform cons cells. A good optimization would be to use cons cells for small lists, and then automatically switch to AVL trees once the list grows to be a certain size.
How disappointing. Mori[1] (which uses ClojureScript's data structures) was either the same as Immutable-js, or significantly worse. In the end, AVL trees win by a large margin for small to medium dictionaries, while Immutable-js performs better for large (> 100 keys) dictionaries.
Get/insert/remove 1 key:
Immutable AVL Tree x 37,909,434 ops/sec ±0.37% (101 runs sampled)
Immutable-js Map x 19,492,874 ops/sec ±0.15% (101 runs sampled)
Mori Hash Map x 2,306,565 ops/sec ±0.74% (96 runs sampled)
Mori Sorted Map x 13,424,409 ops/sec ±0.51% (97 runs sampled)
Immutable AVL Tree x 6,257,569 ops/sec ±0.43% (99 runs sampled)
Immutable-js Map x 2,111,085 ops/sec ±1.07% (91 runs sampled)
Mori Hash Map x 1,553,193 ops/sec ±0.77% (93 runs sampled)
Mori Sorted Map x 3,785,671 ops/sec ±0.43% (96 runs sampled)
Immutable AVL Tree x 3,426,260 ops/sec ±1.38% (97 runs sampled)
Immutable-js Map x 1,415,893 ops/sec ±0.41% (96 runs sampled)
Mori Hash Map x 699,113 ops/sec ±0.40% (98 runs sampled)
Mori Sorted Map x 1,550,116 ops/sec ±1.54% (100 runs sampled)
Get/insert/remove 10 keys:
Immutable AVL Tree x 21,954,005 ops/sec ±0.81% (98 runs sampled)
Immutable-js Map x 17,236,706 ops/sec ±1.02% (99 runs sampled)
Mori Hash Map x 2,474,120 ops/sec ±0.77% (95 runs sampled)
Mori Sorted Map x 911,264 ops/sec ±0.41% (100 runs sampled)
Immutable AVL Tree x 399,700 ops/sec ±0.15% (97 runs sampled)
Immutable-js Map x 218,274 ops/sec ±0.63% (98 runs sampled)
Mori Hash Map x 150,978 ops/sec ±0.74% (96 runs sampled)
Mori Sorted Map x 73,598 ops/sec ±0.68% (98 runs sampled)
Immutable AVL Tree x 135,120 ops/sec ±0.76% (99 runs sampled)
Immutable-js Map x 100,893 ops/sec ±0.20% (97 runs sampled)
Mori Hash Map x 74,750 ops/sec ±10.95% (96 runs sampled)
Mori Sorted Map x 42,696 ops/sec ±0.45% (99 runs sampled)
Get/insert/remove 100 keys:
Immutable AVL Tree x 6,467,149 ops/sec ±0.38% (93 runs sampled)
Immutable-js Map x 14,233,214 ops/sec ±1.05% (96 runs sampled)
Mori Hash Map x 2,513,928 ops/sec ±1.24% (98 runs sampled)
Mori Sorted Map x 384,132 ops/sec ±0.53% (98 runs sampled)
Immutable AVL Tree x 19,760 ops/sec ±0.52% (100 runs sampled)
Immutable-js Map x 12,798 ops/sec ±0.26% (100 runs sampled)
Mori Hash Map x 10,619 ops/sec ±2.59% (93 runs sampled)
Mori Sorted Map x 3,078 ops/sec ±1.49% (98 runs sampled)
Immutable AVL Tree x 6,420 ops/sec ±0.51% (101 runs sampled)
Immutable-js Map x 6,204 ops/sec ±0.20% (99 runs sampled)
Mori Hash Map x 5,394 ops/sec ±0.81% (93 runs sampled)
Mori Sorted Map x 1,757 ops/sec ±0.51% (100 runs sampled)
"Immutable-js Map Transient" means an Immutable-js Map that uses "withMutations" for extra speed.
I also want to test out ClojureScript's data structures, but I haven't gotten around to it yet.
----
As I said earlier, AVL trees are fast. They tend to be 0-3x slower than JavaScript objects.
Stop and think about that for a moment: JavaScript objects are mutable, they're written in C++, they're heavily optimized with various tricks, and they're probably implemented as hash tables.
Meanwhile, AVL trees are immutable, do not use any kind of optimization tricks (the algorithms are very simple and straightforward), and they are implemented in vanilla JavaScript, in less than 400 lines of code.
JavaScript engines are fast. So fast that immutable AVL trees are completely viable. I would not hesitate to replace all my programs with them. This is quite amazing.
In addition, notice that according to those benchmark numbers, you can create 20 empty AVL trees, then insert 100 keys into each AVL tree (for a total of 2,000 insert operations)... once per millisecond. In this case, worrying about the performance cost of immutability is a huge premature optimization.
(I'm not directing this at anybody in particular, in fact I am the kind of person that does premature optimization, so these numbers help with my own personal fears about performance.)
----
I'll test the performance of unsorted arrays soon and post the results here.
It includes algorithms for getting/inserting/removing an element at a particular index (in the case of arrays), and code for getting/inserting/removing an element in sorted order (for dictionaries and sets).
If anybody wants, I can translate the code from JavaScript to Arc.
---
* [1]: Adding in sorted arrays shouldn't be hard, but I haven't had any need for them yet.
It seems the problem with Anarki is that Arc's lists are terminated with the symbol 'nil rather than Racket's null. So you have to convert from Arc lists to Racket lists (and back again). Here is the relevant code:
Thank you for your kind words. I'm glad you've found my post useful. And that's a good catch about node/r.
It looks like the two versions of node/r differ just in the case when (depth x!lf) = (depth x!rt) [and likewise for y], which it appears I had assumed would not be true; perhaps that was valid for insertions but not deletions. (I must admit deletions came as a bit of an afterthought, as evidenced by the typos in "aremove".) I'm pleased that the resolution is so simple.
Anyway, thanks to you, we now have AVL trees that are actually tested and proven to work.
In fact, the normal binary search tree deletion can sometimes cause an unbalanced tree when concatting two arrays, but waterhouse's "amerge" function works correctly!
I think A should be doable. Just call process-comment after submit-item? You'd be double-counting some stats, like for the oversubmitting check. But we can worry about that later.
Went to the page, selected Download Zip, downloaded the file, extracted it and ran 'make && ./' and got:
cc -o arc *.c
read.c: In function 'load_file':
read.c:308:47: warning: initialization makes pointer from integer without a cast [enabled by default]
C:\Users\Steve\AppData\Local\Temp\cctkjQZb.o:read.c:(.text+0xeb4): undefined reference to `_realpath'
collect2.exe: error: ld returned 1 exit status
make: *** [all] Error 1
Strange... It can't find realpath. Seems to be a MinGW issue according to google. I've developed the whole on Android w/ C4droid, and I'm not too experienced with MinGW, but I'll see about finding a fix!
sh-3.1$ pwd
/c/Users/Steve/arc-master
sh-3.1$ make
cc -o arc *.c
builtins.c: In function 'builtin_load':
builtins.c:369:13: warning: assignment makes pointer from integer without a cast [enabled by default]
read.c: In function 'load_file':
read.c:268:47: warning: initialization makes pointer from integer without a cast [enabled by default]
C:\Users\Steve\AppData\Local\Temp\ccTbSwOD.o:builtins.c:(.text+0x1276): undefined reference to `_realpath'
C:\Users\Steve\AppData\Local\Temp\ccr5oXek.o:read.c:(.text+0xd45): undefined reference to `_realpath'\
collect2.exe: error: ld returned 1 exit status
make: *** [all] Error 1
sh-3.1$
I saw this yesterday and got pretty excited. A while back, I stumbled across the same source of inspiration: http://www.lwh.jp/lisp/index.html
Being mainly a CL hacker who came from Python, Arc has looked interesting to me for a while, but I couldn't justify running a small language on a HUGE backend like Racket... So I started implementing the environment described at the link above, which you did as well. Incorporating my initial work with quite a bit of yours, I spent 24 hours hacking together something similar. I haven't done nearly enough to it yet, but I added some new types and support routines. The code layout is slightly reminisce of Quake code. Take a look if you're interested: https://github.com/camden-smallwood/arc
