I don't get it. There's the whole stack copying for call/cc, so call/cc is much more expensive.
(I read the "Lambda the ultimate GOTO" paper you referenced earlier; it's about goto vs structured programming, not call/cc. As an aside, it's very interesting to reflect on just how controversial structured programming was.)
Implementing call/cc efficiently has been well-reasearched in the Scheme community. For a very well-written account of a non-stack-copying implementation see
Then continue at ReadScheme at "Compiler Technology/Implementation Techniques and Optimization"
to see further developments (Look especially for Clinger's papers).
In a function call, the state (the current computation being done) is saved anyway, and therefore "copied" if that is your preferred term. So ideally, call/cc should have the same overhead as an ordinary function call; the only difference is that in call/cc the continuation state is the value given to the function, while in a function call it's just one of the values given to the function.
Note however that much of the theoretical analyses of call/cc make a basic assumption of a "spaghetti stack", which would mean that partially unwound stacks would be saved implicitly as long as any continuation exists which refers to that stack, and all stacks themselves are subject to garbage collection. Most machines don't actually have a spaghetti stack and can't make a spaghetti stack anyway ^^. That said a spaghetti stack could be implemented as a simple list, with push == cons and pop = cdr.
Alternatively store the local variables on a garbage-collected heap, and include a reference to the local variables with the continuation/return address (you'll probably need to save the pointer-to-local-variables anyway, since the target function is likely to use that pointer for its own locals). Again, no additional overhead over plain function calls, except perhaps to restructure the return address and the pointer-to-local-variables.
Don't know about MIT Scheme, but if I were to implement call/cc on stock hardware and compiling down to machine language that's what I'd do ^^
I'm still totally not understanding your claim that call/cc should have the same overhead as an ordinary function call.
I read the Clinger "Implementation Strategies for Continuations" paper and they found call/cc about 10 times slower than function calls on the tak/ctak tests. I tried those tests on PLT Scheme and the overhead I saw is even worse: .7 seconds with function calls vs 51.8 seconds with continuations on (tak 24 16 8).
Clinger says about the stack strategy: "When a continuation is captured, however, a copy of the entire stack is made and stored in the heap. ... Variations on the stack strategy are used by most implementations of Scheme and Smalltalk-80."
Components of function call: (1) put arguments somewhere (2) put return address somewhere (3) jump to function.
Components of call/cc: (1) put return address as argument somewhere (2) put return address somewhere (3) jump to function.
That said, continuations generally assume that "put X somewhere" means somewhere != stack. Yes, even return addresses are not intended to be on the stack when using continuations. The main problem is when compiling down to C, which always assumes that somewhere == stack. If you're compiling down to machine language where you have access to everything, then you can just ignore the stack, but not in C, which inherently expects the stack.
I took a look at arc.arc, and I didn't see any macros there that would be helped by destructuring quotation. I did notice that the macros: w/stdin, w/stdout, thread, atomic solely exist to wrap body code in a lambda (fn) expression. Maybe that sort of wrapping would be useful to add to defq?
Yes, most of the axiomatic stuff in arc.arc probably would not benefit from this I think. I can see a couple, such as "deftem", that could probably make use of this.
Is nil! an Anarki thing? (wipe m) is the Arc expression to set m to nil. (And (assert m) sets m to t. Assert tops my list of confusingly named functions.)
It seems like the most plausible way to keep scar/scdr/sref from mutating variables outside the no-side-effects scope is to keep a table of the variables they are allowed to operate on, which is basically anything the user created with cons or table inside the no-side-effects scope. This should invalidate code like
(= a (table))
(no-side-effects (= b a) (= (b "key") "value"))
Is there any more natural way to track this than keeping a table keyed by symbol?
I guess you could also do this with a macro that replaces all the symbols by gensyms, so inside no-side-effects, foo is really a unique variable. But that seems like a pain to implement.
As an aside, watch out for denial-of-service attacks in untrusted code: e.g. code that goes into an infinite loop or infinite memory allocation. Depending on what you're doing, that can be a big problem, or not.
"Use Java" is not the answer I was hoping for. ;-)
This seems like such a simple request - I can express it in a few sentences - that it should be at least not extremely difficult to implement in the ideal programming language. So I hope it can be done in Arc, and if not, hopefully this is a use case that can be taken into account while figuring out how to handle arc modules/namespaces/whatever.
Anyways. I thought about replacing symbols by gensyms, but at what point would I do that? If I just check all symbols in the code I will miss things like
(eval `(= ,(sym "foo") 2))
For denial of service, I was thinking about something like (reval n code) would run the code but only allow up to n function calls. Seems like this would require writing eval in Arc then modifying. Is this similar to what you were suggesting by a replacing-symbols-by-gensyms macro?
"This seems like such a simple request - I can express it in a few sentences"
Awesome. I want to time travel. That's just one sentence. :)
"it should be at least not extremely difficult to implement in the ideal programming language"
Cue the asbestos! No one said Arc was intended to be some abstract ideal satisfying all few-sentence specifications, and as per the Java crack, who says that the ideal language is idiot-proof or attack-proof? To the contrary, the Design Imperatives I have seen trust the programmer to be good and are not hoping to be able to run virus attacks imperviously.
As for your question, it is a hard problem and one reason I think we do not have a Lisp plug-in for browsers.
I don't mean to start a flame war - I am certainly not a big Java or JavaScript fan ;-)
I don't want to make the language idiot-proof. I acknowledge this is a hard, rather "meta" thing and I was hoping Arc would be powerful enough to do this.
So, regardless of whether "the ideal language would have it", you agree this would be very useful; it would let us have an Arc plug-in for browsers for example. Or make a site
where you could make your own Arc site by entering code and the main servers would run it restrictedly. Arc is trying to be native to the web, and allowing restricted execution is a very webby thing to do.
"I was hoping Arc would be powerful enough to do this."
OK, asbestos did not work, try the foam!
What you might be missing is that power makes attacks easier, not harder. As I suggested, part of that power is reflection so you have a fighting chance, my concern is that once you have blocked all the exits there will be no way to get in. Whatever that means.
"you agree this would be very useful"
I do? Wow. Actually, I do not know much about security,tho I might have to learn soon. My guess is that probably the best way to go is not to cripple the plugin, rather to allow only registered, vetted, digitally signed code to run. ie, the plugin looks for a digital certificate before launching.
Tilton's Law: Solve the right problem. What is the problem? Losers posting evil code. Solution? Don't run just anyone's code.
"I think we do not have a Lisp plug-in for browsers"
Well, we have JavaScript, and it is not really safer by design than Lisp (they are quite close, too). But JavaScript has a security manager, quite restrictive sometimes. And look at rebol : that's also a close relative to Lisp and it's got a cool security manager.
Well, they mainly prevent you from reading/writing the host filesystem or from connecting to undesired remote servers.
Lacker, this might not be as "secure" as Java's model, and not exactly what you were asking as it does not prevent you from overwriting another's code, but it is obviously enough to run untrusted code on one's machine. And to implement it, you only need to overwrite the dedicated axioms in ac.scm.
Then there was that other ILC where the speaker argued we Lispers should rejoice because Javascript was a Lisp and was in all the browsers. Make sure there are no children in the room and I'll tell you what happened next.
You had me worried, but I'm pretty sure there's absolutely no problem with using strings as the keys for tables.
The MzScheme documentation says: make-hash-table ... 'equal -- creates a hash table that compares keys using equal? instead of eq? (needed, for example, when using strings as keys).
Checking ac.scm, sure enough:
(xdef 'table (lambda () (make-hash-table 'equal))
Likewise, the "is" operation in Arc uses MzScheme's string=? . (That's a statement, not a question :-) So string comparison works, although in O(n) time.
Net net: strings are okay for comparison and table keys in Arc.
I wasn't saying that they weren't usable, just that they were, in fact, slower; that's what you observed. Symbol comparison is O(1) time, whereas string comparison is O(n) time. That's all.
In my experience, the meta-issue is that there are multiple substantial barriers to Lisp adoption, and an uncertain payoff, leading to the question, "Is this really the best use of my time?"
The first substantial barrier is Emacs. Before learning Lisp, first you must learn Emacs. I've tried several times, but keep deciding it's not worth the effort. Imagine for an instant that in order to use Ruby, you need to use some strange Japanese editor, but it's really not bad once you get used to the cryptic commands and rebind your keyboard so it is usable. Do you think this might hamper the adoption of Ruby?
Next, the IDE. I'm willing to put up with Slime's 1980's styling, but I keep ending up in mysterious inferior modes that don't seem to be documented. After reading through Slime documentation, it seems I need to understand Emacs's Lisp modes first.
Then, the REPL. Sure, it's nice to be able to interact. But sometimes I need to write a self-contained script that can take part in the whole Unix environment: things like being part of a pipeline, running as a cron job, running through CGI, running as a command. Python makes this trivial; Lisp makes this difficult or impossible.
Then there's the payoff. Will Lisp actually help me solve any of my problems? That's still extremely unclear. Perl or Python are great for random problems I have, such as "Fetch a web page, pull stuff out with regular expressions, and convert it from iso-8859-1 to UTF-8" or "Analyze a pcap dump file". This is where Lisp runs into the infamous library issues. The problems Lisp solves seem to not be the problems I want to solve.
The issue of a dialect/implementation is somewhat vexing: try reading SICP and Practical Common Lisp at the same time, and discovering that everything is different. Also, the expectation that whatever implementation you pick will be the wrong one for the libraries you want is a bit scary. But overall, I'd say this isn't a fundamental barrier.
The above is meant as an honest answer to your question; I'm not interested in starting a flame war.
"But sometimes I need to write a self-contained script that can take part in the whole Unix environment: things like being part of a pipeline, running as a cron job, running through CGI, running as a command. Python makes this trivial; Lisp makes this difficult or impossible."
This is hugely under-estimated as a reason for lack of Lisp adoption. I would put this way ahead of lack of IDEs.
"The first substantial barrier is Emacs. Before learning Lisp, first you must learn Emacs. I've tried several times, but keep deciding it's not worth the effort."
First of all, I don't think it's accurate to say that you must learn Emacs before learning Lisp. Other editors such as vi or IDEs such as ACL & LispWorks are used successfully.
On the other hand, after using IDEs for over a decade, I switched to vim for a couple of years and more recently switched to Emacs. Get the "Learning GNU Emacs" book and it will be trivial to pick up Emacs.
I'd like improvements in basic usability. This includes filling in missing functionality (e.g. trig, socket connections, regular expressions) and/or an escape to Scheme to do these. Also non-brokenness on Linux, Windows, etc. Also ability to simply make a non-REPL Arc script. Picking up the Anarki stable fixes would probably cover most of this.
On the trivial side: w/bars must die.
One question: why is currying so popular? I don't see the point, so I guess I'm in blub-land with respect to currying.
The post by raymyers (http://www.arclanguage.org/item?id=3997) gives some very cool examples of the power of bracket-style currying. In addition to cutting down the number of tokens in the common [foo bar _] case of bracket-notation, it allows much nicer wrapping of variadic functions - or just functions for which you want to leave more than one argument open. Compare [* 2] to (fn args (apply * 2 args)), for instance.
