On the contrary, the question of how a particular implementation represents with arc lists has nothing to do with what arc lists are.
In fact, you could make ac.scm more efficient by doing a (define nil '()), eliminating all the denil stuff, and then changing the print routines, if you cared to.
Is ac-niltree/ac-denil a constant overhead, or does it make some O(1) operations into O(n) operations? Hopefully the nil/denil traverses the whole list only when you're already traversing the whole list. But I haven't been able to convince myself that's always the case. This is on my list of things to investigate, but has anyone already figured this out?
I'm not completely sure, but I think this is a compile-time overhead. So when you type directly into the toplevel, its a O(n) overhead, but when you execute a function defined in arc, executing the function itself should be less additional overhead because it was compiled to a scheme function in the original def.
; translate fn directly into a lambda if it has ordinary
; parameters, otherwise use a rest parameter and parse it.
(define (ac-fn args body env)
; ...
Have to watch out for corner cases - Arc's usage of 'nil as the list terminator is exposed in several places within the language itself. For example `(is (coerce "nil" 'sym) (cdr nil))` is true under the existing implementation, yet would be false if you just (defined nil '()). You'd need to patch `is`, `coerce`, and possibly a bunch of other primitives to preserve the existing behavior.
Which exposes the problem of "the code is the spec". If there was a prose spec, pg could have just said that such stuff was undefined and we wouldn't care that such things break.
If stuff doesn't work right, having the spec say it's supposed to not work right doesn't help at all.
Prose specs came into being to help multiple implementations interoperate (somewhat) when implemented in low level languages. I don't see the need when you have just one pretty concise and declarative implementation.
The question of how a particular implementation represents with arc lists has nothing to do with what arc lists are.
The code is the spec.
The fact remains that in arc when you type '(a b c) you get '(a . (b . (c . nil))) and in scheme you get '(a . (b . (c . ()))).
You could make ac.scm more efficient by doing a (define nil '())
There is a difference between nil being the empty list and nil evaluating to the empty list.
One problem with (define nil '()) is that then 'nil returns the symbol nil rather than the empty list ().
I am not convinced that (define nil '()) would greatly increase efficiency, because most of that overhead is incurred in the initial read, and not at run time. It takes billions of times longer for the user to type a statement into arc than it takes arc to denil the input. And after that, nil or () isn't an issue because arc functions are compiled to scheme functions anyways.
I'm fairly sure that "the code is the spec" applies to arc.arc, not to ac.scm. That is, anything that can interpret arc.arc properly is a conforming Arc implementation; ac.scm is just one of them. And since nil is (), then in Arc, your two lists are the same but with different formatting. Observe:
arc> (is nil '())
t
arc> (is nil ())
t
arc> (iso '(a b c) '(a . (b . (c . nil))))
t
arc> (iso '(a b c) '(a . (b . (c . ()))))
t
arc> (iso '(a . (b . (c . nil))) '(a . (b . (c . ()))))
t
Please note that the behavior of is is defined by ac.scm, not arc.arc. (And iso uses is to test for equality.)
The equality and interchangability of nil and () is just because there is a line in the definition of is that specifically says that false values are equal.
So even if you put #f in the terminating position, your lists will still be iso.
arc> (iso '(a b c) '(a b c . #f))
t
Are you saying that arc lists are #f terminated just because it doesn't break arc to put #f in random lists? Even if arc lists can be terminated by nil, (), and #f, it doesn't mean they necessarily are. Any given list (ignoring nested lists) can only have one termination object. I think it is reasonable to say that that list is terminated by that object. I do not think it is reasonable to say that list is terminated by another object, even if it could be, because the actual object at the end of the list is not that other object. And because the current implementation (the only official implementation) uses nil, I think it reasonable to say that arc lists are terminated by nil. Note the use of the present tense. If that changes at some future time, I my statement will obviously not apply.
In short, given the current implementation, we have (at least) six different ways to write nil: nil, 'nil, (), '(), #f, and '#f. These six things are all considered identical within Arc. The same is true, for instance, of 'a and (quote a), which are the same thing entered differently. You can check that they are the same with is; I won't put all those examples into this post.
I have never said that Arc lists aren't nil terminated--clearly, they are. What I'm saying is that Arc lists are nil terminated for any representation of nil--whether that representation is nil from Common Lisp, '() from Scheme, or #f from a leftover artifact of using the mzscheme reader.
