I think the axiomatic approach is intended to stop this. Lisp suffered because the spec was complex and ambiguous. To port Arc, just port the axioms, run the "spec" et voilà, you have a conforming implementation.
It should be noted that pg intends to implement more of Arc in Arc, when he gets the time.
In fact I have an implementation in SBCL half way (it basically can load arc.arc, but I haven't bothered with network/thread functions yet). To solve the call/cc problem I got to the point of doing a CPS transform, and since Arc has only 4 special forms (very few axioms, as you say) this was 'easy'...
In all the Arc code I've written so far, I've used map a lot. That's probably quite common for anyone programming in a language based on lists. I therefore propose that Arc have a special syntax that turns a normal function into one that maps over a list.
(def $ (x . lists)
(if lists
(apply map x lists)
(fn (lists) (apply map x lists))))
More or less does what you want, without special syntax.
($$car... would have to be written ($($ car)... though.
To me this looks like a specific case of wanting currying/partial application built in for functions of semi-fixed arity, rather than a need for new syntax.
You can even be cleaner: $car is $.car (though this doesn't work for $.$.car). But I don't think this is really a specific case of partial application (though I see where you're coming from). While partial application would be ((map car) '((1 2) (3 4) (5 6))) and this would be ($car '((1 2) (3 4) (5 6))), the biggest win (for me) is not the partial application aspect, but the conciseness of having just one character, as opposed to (currently) ([map car _] '((1 2) (3 4) (5 6))) or ([apply map car __] '((1 2) (3 4) (5 6))), or even the partial application version. And even so, this strikes me as more similar to a request for explicit partial application, which is already implementable, than implicit partial application.
Yes, it was the conciseness I was after. The syntax was inspired by K, where you can do this by putting a ' before a function name.
Of course, K often looks like line noise, but then K takes this technique to its logical conclusion and uses special syntax for everything. There's no need to go that far.
I dislike this idea, mostly because the syntax is pretty trivial anyway using the bracket currying suggested elsewhere. [map car] isn't much shorter than $car, and it's much more flexible and leaves $ (or whatever symbol might end up being used) open for some other meaning. It's also more explicit, although I'm not sure that's worth much.
That's not necessarily true; as I pointed out further down (http://arclanguage.org/item?id=4704), you can get the effect you want. On the other hand, you do take a speed hit. I'm inclined towards supporting both, but swapping the args is very easy to write and may not belong in the core.
pg said he is planning on opening up intrasymbol syntax and, presumably, presymbol syntax as well. Once that's there this is a trivial addition to play with.
But when? That may be the single biggest change I want, actually--much of the rest is implementable within Arc, but this is not. Certainly, when that happens this is trivial, but it hasn't yet, and there's no inkling of when.
I really like this idea, but I don't know that $ is the best choice. On the other hand, I can't think of something better... ^car? &car? At any rate, fantastic idea.
I think it's a neat idea (it really does bug me when I write really short macros that just delegate) but I agree with almkglor that mixing functions and macros isn't good. I'd prefer that defq just always returned a macro.
Don't want to be too critical though. It's a great idea and could definitely make a few programs shorter.
And to expand on that, the answer is generally yes. MzScheme is a great version of scheme for its completeness, not its speed. However, several schemes are directly competitive SBCL and CMUCL. Arc could be ported to one of these without too much effort.
As for speed, Stalin Scheme is amazing for example. Not very complete and well documented for example. However, CL is full of "efficiency hacks". Scheme is full of purity, not always easy to implement efficiently. Optimizing CL is easier than Scheme, IMHO.
Why do you think CL is easier to optimize that Scheme? This isn't a hostile question; I'm just curious. Intuitively, I feel like "purer" languages should be easier to optimize.
First, CL has in the standard many possibilities for making declarations reagrding optimization : for the functions you want, you can compile code, declare types (e. g. this var only holds fixnums), declare you want to optimize the speed and ignore type safety, etc. This way, you end up writing code the way you would write it in C. There is no such thing in the Scheme standard. Individual implementations could, of course, but as far as I know no one does.
Abother example is call/cc. This is a very interesting beast, only existing in Scheme. But it is hard to implement efficiently.
The last example I can think of is 'nil. Using nil as false and the empty list is very interesting in this regard : you can implement nil as the NULL pointer, which is also 0, the false boolean. Less manipulations to do on the bare metal. Distinguishing between #f and '(), on the contrary, implies making more tests at the lower levels.
re: call/cc - I think a bit of the lambda the ultimate series of papers eventually boils down to the realization that a machine language jump-to-subroutine is equivalent to a call/cc, and the target of the call/cc just has to access the return address on the stack as a function address.
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.
Ah, I get it. I suppose typing is one of the big issues affecting speed. If the language standard insists on dynamic typing, there might be no way to get certain kinds of optimizations.
And yeah, call/cc is probably always going to be a bear. But man is it cool. :)
I suppose this goes against what a few of us (including me) were saying above -- that the language and the speed are really separate issues. Or maybe it's more coherent to say that language standards (as opposed to "languages" generally understood) can have a profound effect on speed. If they don't give implementors a lot of choice, they can box people into certain corners.
It's interesting that Scheme actually mandates optimization in at least one case (tail recursion). I don't know how many language standards make those kinds of demands, but I suspect there aren't many.
Tail recursion is interesting as it is not especially an optimization for speed but as a way to make programmers rely primarily on functional programming : if you don't have it, functional programming is rapidly a dead-end as you can make the stack explode really fast. As a bonus, it is faster :)
And a third alternative is to use dotted pairs for the associations, but my point was that by treating a plain list as alternating keys and values, it plays nice with rest arguments in functions.
Generally, a list may be interpreted in different ways in different situations, and a common complaint about lisp is that you can't tell if a cons cell is supposed to be the starting point of a tree, an assoc list, a sequence, or something else. I think the way to tackle this in Arc should be to make better use of annotations.
A rest argument will always be a plain list without a tag. That's the reason for the suggested interpretation of kvp!b.
Exactly. It's basically a roundabout way of adding keywords into the language. A better idea would be to just add them, and then list-functional notation could be used for something more generally useful.
Combining what gaah (Jesin) said with other things you've pointed out, the final solution would work something like this:
1. Write mock versions of all the Arc primitives that are dangerous.
2. Write a function that calls macex on an expression and then scans it for all instances of (set <symbol> ...).
3. Write a macro that takes an expression or a file, and wraps the whole thing in a with form that locally defines/shadows all the mock functions and the symbols detected with the above function.
4. Create a mock version of eval that wraps its argument in the above macro. This should obviously be shadowed in the macro too.
There are still some parts that are stumping me. It seems like I need to either (a) mock annotate to use a different mechanism, or (b) prevent the code from annotating pre-existing variables. The same goes for accessing sig.
Also, I'm not sure how to handle scar/scdr/sref. It don't think places are first-class, so I can't have a table of untouchable places, unless I start working in mzscheme. (Which I would rather avoid.)
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?
Here's an implementation of the n queens algorithm in the wikipedia article:
(def rot ((x . y)) (join y `(,x)))
(def nqueens (n)
(withs (m (mod n 12) r (range 1 n) od (keep odd r) cod (cddr od) s '(1 3) cods (join cod s) ev (keep even r))
(join (if (pos m '(3 9)) (rot ev) ev)
(case m
8 (apply join (map rev (pair od)))
2 (join (rev s) (rot cod))
3 cods
9 cods
od))))
Arc makes it very nice to implement, although it still bugs me that you can't use join to add a single item to the end of a list (which I've wanted to do a few times already). My preferred semantics:
The challenge is to produce all 92 solutions as the Ruby code does in the OP. I linked to wikipedia for the description of the problem, not the algorithm.
I also showed the ellided output for clarification.
class Array
def rot
push( shift )
end
end
nqueens = proc{|n|
odds, evens = (1..n).partition{|x| x % 2 > 0 }
case n % 12
when 2
odds = [3,1] + odds[3..-1] + [5]
when 3, 9
odds.rot.rot
evens.rot
when 8
d = -2
odds.map!{|x| d *= -1; x + d}
end
p evens + odds
}
nqueens[8]
class Array
def rot
push( shift )
end
end
proc{|n| p ((1..n).partition{|x|x%2>0}.inject{|o,e|
e + case n % 12
when 2
[3,1]+o[3..-1]+[5]
when 3,9
o.rot.rot;e.rot;o
when 8
d=-2;o.map{|x| x + d*=-1} end})}[ 8 ]
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.)
I should add that dsb and thus defun support optional and keyword args at the same time only because it is possible; I cannot imagine it ever being sensible. :)
Very nice work on supporting both opt and key args.
Although if you had something like this:
(defun fn (a &o (b 'b) (c 'c) &k (d 'd))
with a usage like this:
(fn 1 'd 'e)
... how would you know whether:
1) 'd is the value of the first opt arg and 'e is the value of the second (the key arg unsupplied)
or
2) 'd is the key for the key arg, and 'e is its supplied value (the 2 opt args unsupplied)
?
Maybe I'm missing something here, but it seems to me that unless you have special syntax for keywords, you will get into trouble.
And if you have to introduce special syntax for keys anyway, it is just as well to make every single argument keyable on its symbol (even vanilla ones), and just worry about combining &o and &rest (which should then be doable).
"with a usage like this: (fn 1 'd 'e) how would you know..."
The interpretation is that d and e are the two optional args, so any caller wanting to supply a keyword arg has to supply the optionals. Recall that I said it was possible, not sensible. :) But in tool design I think we should let users hang themselves rather than guess (perhaps wrongly) that no one would ever come up with a good use for such a thing.
A second, lesser motivation is that CL works that way.
c.l.lisp just offered a much better observation: the optional args above are standard for the various "read" functions, and the start and end keywords are standard for string functions. Read-from-string then is inheriting consistently from both families.
> Having all parameters be keyword arguments as well might be interesting, but it wouldn't avoid optional/keyword confusion.
Why not?
Let's say you have a function with 3 standard args followed by 2 opt args. So you have 5 args, all keyable on the symbol you give them in the def.
Let's further say that in a call to this function, I key the middle standard arg (#2 in the def) plus the first opt arg (#4 in the def) and also, I omit the second opt arg (#5 in the def). So, I'm supplying two standard args apart from the two args I'm keying. Then the function call parser would know, after identifying the 2 keyed args and matching them to positions #2 and #4 in the def, that the first non-key arg supplied corresponds to position #1 in the def, the second non-key arg supplied corresponds to position #3 in the def, and that an arg for position #5 in the def is missing, leading to the usage of the default value for this opt arg.
This would even work when you want to raise an error for a non-supplied, non-opt arg.
Wouldn't this work quite intuitively (keying an arg when calling a function "lifts it out" of the normal "vanillas then optionals" argument sequence, shortening that sequence, put keeping a well-defined order for it)? (You would need special syntax for keys in this proposal. My suggestion is a colon appended to the arg symbol, rather than prepended, like in CL.)
Can someone give a counterexample if they think this somehow wouldn't work?
&rest args are left as an exercise for the reader :-)
It could be, if you had an old function that was using optional arguments, and then eventually had to add even more arguments, which you finally decide to make keyworded; without breaking existing code, you can support both optional and keyword args.
What I would like to see is optional, keyword, and rest arguments. Imagine something like this:
The syntax to add rest args, if it followed the CL example, would be:
(dsb (r1 &o o1 &r rest &k k1) data ....)
If data was (1 2 'k1 3) then most params would be bound as expected and then rest would be bound to (k1 3).
But now the data (1 2 'k1 3 4) causes an error "Key list is not even", ie, once you say &k you undertake certain obligations as the caller. Even if you even up the list:
(1 2 'k1 2 3 5)
...you get an error "3 is an invalid keyword", because 3 appears in a keyword position. This can be avoided by announcing your intention to have undeclared keywords:
(a b &rest rest &key k1 &allow-other-keys)
That of course is CL, and it kinda makes my day that if I were crazy enough to extend dsb in Arc I would end up with:
Ok, and then going forward only the new code has the burden of supplying optionals... hmmm, refactoring at 7am with the demo to the CEO scheduled for 9am?...
