[By now other replies make this somewhat redundant, but I'll proceed anyway. Much this post is rambling about types and language design.] I think dido's question can be answered more simply than that. I.e.: (1) nil is 'nil, always; (cons 'a (cons 'nil nil)) = (cons 'a (cons nil nil)). (2) The funny behavior you observe stems from this: The "coerce" function (and also the "string" function, which uses "coerce" quite directly) coerces the symbol 'nil to the empty string. This decision was made for convenience, as aw illustrates here: http://arclanguage.org/item?id=10802
To answer your question: It's more like a decision to make nil evaluate to 'nil. The train of reasoning goes like this:
1. We need a single value to be considered "false"--by the "if" special form and by any function that's supposed to return either true or false. We call this value nil. Now, we could invent a new type for nil (maybe a "false" type, or maybe a "boolean" type that is either true or false), but in Arc (and Common Lisp before Arc, and probably several other Lisps both historical and contemporary), nil is a symbol.[1]
2. You could stop here. Use 'nil whenever you want to return false. But it's kind of annoying to remember to type the quote. So, instead, we bind the global variable nil to the value 'nil. (The compiler actually handles nil directly--if you managed to rebind nil, it wouldn't make a difference, because nils are transformed away anyway.) Likewise, t is bound to 't, the canonical true value.
[1] Actually, in Common Lisp, nil has type "null", which is a subtype of "symbol", in the same way that a string is a subtype of an array. This might be worth considering...
* (type-of nil) ;Common Lisp
NULL
* (symbolp nil)
T
* (type-of "ach")
(SIMPLE-ARRAY CHARACTER (3))
* (arrayp "ach")
T
* (stringp "ach")
T
Additionally, in CL, the type of t is "boolean", also a subtype of "symbol". And, in fact, "null" is a subtype of "boolean". Hmmph. I feel that's a bit excessive. At any rate, it doesn't make much difference (you could always just ask (is x t)), except perhaps when you're giving type advice to the compiler--but if you were doing that, you should be able to define a "boolean" type as (or t nil), the way you'd define any other derived type. Perhaps nil should have a slightly special type, as it's treated specially by the primitives "if", "car", "cdr". [And hmm, could conses be fundamentally vectors of length 2, just with a different type tag? Probably. This is of course far afield of your question.]
Methinks "is-a" type semantics are fundamental for the implementation. Every object is some number of bits laid out in memory. Hmm, but then (listening to the part of my brain that generates objections anytime I talk as though I'm sure), there are things that could be represented in one of many ways, any of which might be best in a given situation. SICP gives the example of complex numbers as rectangular vs polar, and polynomials could be represented as lists or vectors of coefficients, alists or hash tables of (power coefficient), perhaps in factored form if applicable, and so on. (Even in my nil example, it could be a cons cell or a symbol.) Might it be bad, might it make it particularly difficult or inefficient to do that kind of abstract type behavior if the implementation just uses "is-a" semantics? Ehhh... no. :-) Type dispatching will be the answer, and it'll be just as easy/difficult either way.
[Comment: Any question of making objects callable in functional position is an efficiency concern. If you didn't care about efficiency, then you could just wrap every object inside a closure, and write the system's "print" and "type" functions and so forth to ask the closure how to properly print or type the object. ... And back to conses-as-vectors: I think you might want some arrays to have an entire field of tagging information that would probably need to be stored in the array. At the very least, you'd want the length. And I wouldn't want to make all cons cells 50% bigger. So, eh, conses will be special, and perhaps one could include boxes too... and maybe there's something to "weak" references, which exist but which the garbage collector is free to destroy. Actually, those could be implemented with boxes, though at the cost of adding an indirection to normal references to that object. Mmm.]
2) Were I to have accepted the brilliance of this use case, I'd only have been more interested in why 'pr didn't have the same behavior (which was my main gripe to begin with):
arc> (= speed 2)
2
arc> (prn "You are going " (if (> speed 100) "very ") "fast")
You are going nilfast
"You are going "
3) It was actually something I had already thought of and cast aside for the above reasons. (So it didn't even qualify as something "I'm not thinking of.") If aw was grasping for straws like I was, there probably wasn't much more point in talking about it.
4) It had upvotes too--at least one upvote at the time I first read it. Apparently, what I thought was common sense would be outnumbered.
5) I hadn't programmed in Arc that much yet. Maybe the upvoter(s) saw something there I didn't. At any rate, I'd probably be able to discuss the pros and cons better once I'd used Arc for a while.
6) I did say "I can't think of a single time," and this was a single example. I kinda decided to eat my words on account of that. :-p
Turns out (string:accum ...) is the use case I found that convinced me. The key point was that 'string wasn't consistent for symbols because it was too busy being consistent for lists.
My stance is that they're intuitively separate things. If you take the length of a vector of length 2, you get 2. If you take the length of a linked list node, that's a different story. Still, if a linked list node is implemented as a wrapper around a vector, that's fine.
"Fractal enumeration". I'm taking this literally. Racket's graphics library can probably help you with that. It has some examples, too... In a fresh interaction with Racket, you can type the following:
[Unfortunately, at least for me, it seems you can't put those commands together--it seems that after startup, it displays each "turtle" as an orange triangle, and the "serp" (Sierpinski triangle) procedure creates a bunch of turtles, so you need to wait for the first turtle to get displayed before creating the rest, or else you'll just see a bunch of orange when they all get displayed.]
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
The main insurmountable difficulty with Racket is garbage collections. Eventually (actually pretty frequently) there will be a major garbage collection (as opposed to a minor GC, in the context of a generational GC), which tends to take more than 100 milliseconds even with a bare minimum of objects allocated. That is a game-breaker for this sort of... game.
> But, let's suppose that we decided to make = sequential... like it is right now. Now you need to make a new macro (like pset) to describe parallelness. On the other hand, if = were parallel, it's trivial to use `do` to make it sequential: no need to write a new macro.
Minor objection here: No. I could call it trivial to do the work of describing parallel assignments:
(with (new-a b new-b (+ b a))
(= a new-a b new-b))
And, in fact, I would feel the need to write a new macro to express sequential =. "Gar dammit I hate writing "do" and "=" a bunch of times." To me, both things are trivial, and I just might be more annoyed by the latter.
And then this is a case where my code doesn't actually use multiple arguments to = for accidental reasons, but this is what it would look like:
(def nrev (xs)
(let u nil
(whilet head xs
(= xs cdr.xs
cdr.head u ;I actually use scdr here
u head))
u))
Hmm... come to think of it, I guess it could be done, perhaps better, with parallel assignment. You have to be careful, though. The "cdr.xs" that is set to "u" should be the cdr of the original xs.
(def nrev (xs)
(let u nil
(while xs ;no whilet
(p= xs cdr.xs
cdr.xs u
u xs))
u))
And then there are about 20 cases in which I assign multiple things with = and it wouldn't matter whether it was parallel or not. And there's a case in which I had to be a bit careful about the ordering to make sequential = work.
I almost never think about using parallel assignment, at least not explicitly. (But, hmm, it seems it would be useful for destructive operations on AVL trees, or any data structure. But it must be defined carefully.) I frequently use it in a loop, but it appears as a tail-recursive call; in fact, the example that is the subject of this thread could be done in that style:
(def fib (n)
(xloop (n n a 0 b 1)
(if (is n 0)
a
(next (- n 1) b (+ a b)))))
I do believe that the language should provide both a parallel = and a sequential =. I'm not entirely sure which one should be afforded "official =" status. For the moment, portable code could use "=*" or maybe "=s" for sequential and "p=" or something for parallel assignment (it definitely has to be no more than two characters).
"I do believe that the language should provide both a parallel = and a sequential =. I'm not entirely sure which one should be afforded "official =" status. For the moment, portable code could use "=" or maybe "=s" for sequential and "p=" or something for parallel assignment (it definitely has to be no more than two characters)."
That sounds reasonable. In fact, then = could just be an alias... something like this:
(assign = =p)
And then if you would prefer = to be sequential, you could do this:
(assign = =s)
This would of course clobber other code that expects = to be parallel, but that should be handled by a module/namespace system, so I'm not worried about that.
Side note: maybe we should avoid giving them names that look like emoticons...
This is equivalent to applying the "pset" algorithm once; it's simply expressed in the notation of matrices. And, further:
[1 1]^n x [F_1] = [F_n+1]
[1 0] [F_0] [F_n ]
This is particularly useful, because one can calculate the nth power of a matrix (or of anything) in O(log n) steps with exponentiation by squaring.[0] If we represent a matrix as a list of lists, then the following definitions will work[1][2]...
(def mat-trans (x) ;transpose; this is incredibly terse
(apply map list x))
(def mat-mul (a b)
(let u mat-trans.b
(map (fn (xa)
(map (fn (xb)
(reduce + (map * xa xb)))
u))
a)))
(def mat-id (n) ;n x n identity matrix
(mapn (fn (x)
(mapn (fn (y)
(if (is x y) 1 0))
1 n))
1 n))
(def mat-expt (x n)
(xloop (x x n n total (mat-id (len x)))
(if (is n 0)
total
(even n)
(next (mat-mul x x) (/ n 2) total)
(next x (- n 1) (mat-mul x total)))))
(def fib (n)
(let u (mat-mul (mat-expt '((1 1) (1 0)) n)
'((1) (0)))
u.1.0))
This strategy has the advantage that, once you get it, you can use it for any linear recurrence. For example, if we had
. Also, if one wants, say, these sequences mod m, then it's a fairly simple matter to come up with a "mod"ified version of mat-mul and use that instead--and then the calculation is actually O(log n), because the numbers stay small.
[0] Of course this can be done without the language of matrices. Saying that [1 1; 1 0]^3 = [3 2; 2 1] is the same as saying that the transformation "b -> a+b, a -> b" applied three times is the transformation "b -> 3b+2a, a -> 2b+a". Matrices, and matrix multiplication, are simply a convenient way to represent and compose these transformations.
In fact, as far as I'm concerned, that is the single thing they're good for; and in high school, when I was taught about matrices but not about this stuff, I found it a strange and unmotivated exercise, and so I retained basically none of it, even after it was covered in three consecutive math classes. And I am not known for forgetting or failing to understand things; I've been one of the top students in all of my math classes (except those at an extremely hardcore math camp). I can only imagine how it was for the other students. </rant>
[1] Library functions (with these, the above should work in standard Arc):
(def mapn (f a b)
(if (> a b)
nil
(cons (f a) (mapn f (+ a 1) b))))
(mac xloop (binds . body)
`((rfn next ,(map car pair.binds)
,@body)
,@(map cadr pair.binds)))
[2] It's possible to be slightly more clever than this. E.g. the powers of the [1 1; 1 0] will always look like this:
[F_n+2 F_n+1]
[F_n+1 F_n ]
In theory, you could represent the whole matrix using just two variables (say, F_n+1 and F_n), and the entire computation could be done with four variables.
> Isn't it the other way around? Why are "low bits" not an implementation detail?
The implementation detail is that "you can't tag an object without wrapping it in a compound data structure that old functions will have to be told to reach inside to get the original object".
"Hiding implementation details" isn't something to be done for its own sake. You want to hide implementation details when they're uglier than the semantics you want to convey; e.g. it's impossible to use a MUL instruction to check if the result of a multiplication is a bignum and allocate one and return a tagged pointer to it if necessary, but keeping track of all that is a pain; so instead we have a generic * function that hides all this scrambling around, and we can think of all integers as a single type of object. Exposing that stuff to a user who isn't extremely concerned with performance just sucks. It's bad because the interface sucks, and we'd identify it as "exposing implementation details" because that was the reason it happened.
On the other hand, does anyone want to hide the fact that lists are implemented as conses and that you can take their car and cdr? Not me. That stuff is useful.
> If I define a new type, it makes little sense for it to inherit the qualities of the particular old type I'm using to implement it. That idea does nothing but expose implementation details.
When you first define a new type, no preexisting functions will know how to handle the new type. You have two choices for what should happen in the absence of such instructions. Either they can give errors and fail (unless you use "rep", in which case they do their job as usual), the way they do now, or they can do their job as usual, the way it would be under my proposal. I think the latter choice is clearly--I would say strictly, unless you find the error messages useful--superior.
Now, if you define a new type, the first thing you'll probably do is define some functions that handle the new type, and they will likely need to use old functions that manipulate the objects that your new type is made of. (Perhaps the functions you're defining will be intelligent, wrapped versions of the old ones.) As mentioned, either they have to use "rep", or they don't.
And if you want to define a second new type that's supposed to be a subtype of the first one, then you can still build that on top of the provided "tag" and "type". (I think this answers your last point.) For example:
;Single inheritance. The path of inheritances is an improper list.
;Builtins will have atomic types; you could give something an
;atomic type to pretend it's a builtin.
(def inherit-tag (typ x)
(tag (cons typ (type x)) x))
(def inherit-type (x)
(if (acons (type x))
(car (type x))
(type x)))
(def inherit-rep (x) ;more like "cast to supertype"
(if (acons (type x))
(tag (cdr (type x)) x)
x))
(def is-a (typ x)
(if (atom (type x))
(is typ (type x))
(or (is typ (car (type x)))
(is-a typ (inherit-rep x)))))
If you wanted "has-a" type semantics or something, you could figure out a similar way to define those. (Also, it occurs to me that you could use "tag" to identify your tagged objects, as in (tag 'inheritance-tagged (list (list 'type1 'type2 ...) 'implementation-type x)) or something.) I think you can build things on the type system just as much as before, and meanwhile the initial implementation is cleaner.
[Hmm. Come to think of it, given that the user doesn't have access to the internal "rep", and the built-in functions don't use it, it's meaningless (and useless) for (tag 'a (tag 'b x)) to return nested vectors; I'll make it return the same thing as (tag 'a x). So in the language primitives, everything has a single type--which would likely be just a symbol, but conceivably an Arc standard library might have things that do inheritance with lists of symbols. Anyway, this doesn't change anything I've said above.]
"The implementation detail is that "you can't tag an object without wrapping it in a compound data structure that old functions will have to be told to reach inside to get the original object"."
When I use 'annotate, what I want is to do this: Take a value that's sufficient for the implementation of a new type, and produce a different value such that I can extract the old one using an operation (in this case 'rep) that I can't confuse for part of the type's stable API.
Any "tag" semantics that overwrites the original type is useless to me for that.
I do think "wrap" is a better name for what I want than "tag" or "annotate," and that's the word I reach for when naming a related utility or recreating 'annotate in a new language. I don't mind if you say that tagging is something different. ^_^
---
"You want to hide implementation details when they're uglier than the semantics you want to convey"
From a minimalistic point of view, any accidental feature is ugly complexity, right? But I grant that having easy access to accidental features is useful for a programmer who's writing experimental code.
---
"On the other hand, does anyone want to hide the fact that lists are implemented as conses and that you can take their car and cdr? Not me. That stuff is useful."
I consider Arc lists to be conses by design, not just by implementation. As you say, conses are a positive feature.
On the other hand, the core list utilities would be easier for custom types to support if they relied on a more generic sequence interface, rather than expecting a type of 'cons. This isn't hiding the implementation so much as deciding to rely on it as little as possible, but it's somewhat causally related: If I don't rely on the implementation, I don't care whether or not it's hidden. If the implementation kinda hides itself (the way the body of a 'fn is hidden in official Arc), then I tend to leave it that way, and it can come in handy as a sanity check.
---
"And if you want to define a second new type that's supposed to be a subtype of the first one, then you can still build that on top of the provided "tag" and "type". (I think this answers your last point.)"
No... I said this:
With the way I code, saying (tag a (tag b x)) means I'm making an "a"-typed value that has a "b"-typed value that has "x". I don't consider them all to be the same value[...]
There's no subtype relationship going on here. For comparison's sake, if I say (list (list 4)), I'm making a cons-typed value that has a cons-typed value that has 4. At no point should my conses inherit from 4, and at no point should my "a" inherit from "x". That's just not what I'm trying to do.
---
In any case, just because I like the status quo (or my own spin on it) doesn't mean I shouldn't give your approach a chance too.
So, as long as (tag 'foo (tag 'bar "hello")) makes something nobody can tell is a 'bar, it's consistent for them not to know it's a 'string either. But then what will core utilities which can handle strings and tables (like 'each) do when they get that value? Do they just pick 'string or 'table and assume that type by default? If they pick 'string, won't that make it seem strangely inconsistent when someone comes along and expects (each (k v) (tag 'baz (table)) ...) to work?
