I thought it would've been kind of implicit in the perennial "hey, let's make strings lists" idea. Which isn't new, by the way.
Haskell
Prelude> :type "abc"
"abc" :: [Char]
Erlang
1> A="abc".
"abc"
2> is_list(A).
true
Prolog
?- is_list("abc").
true.
What else do all these strings-are-lists languages have in common? They're notoriously slow for string processing. Linked lists use up more memory and simple accesses are O(n) rather than O(1). It's to the point that the Haskell guys wrote the ByteString library to override the standard Prelude functions and added a GHC extension to parse "abc" as a ByteString instead of [Char].
; compromises in this implementation:
...
; separate string type
; (= (cdr (cdr str)) "foo") couldn't work because no way to get str tail
; not sure this is a mistake; strings may be subtly different from
; lists of chars
; idea: get rid of strings and just use symbols
; could a string be (#\a #\b . "") ?
PicoLisp uses the strings-are-symbols approach (http://software-lab.de/doc/faq.html#strings). And that illustrates that it's all a matter of focus. PicoLisp is dynamic, perhaps to a fault. By design, it has no arrays, strings, lambda keyword, or even a compiler. But if you have any investment in efficiency, proper strings seem smarter, if only as a library for when you need the performance (as in Haskell). Never mind arguable conceptual differences.
Arc awkwardly straddles this divide. It has (a) hash tables instead of alists, but (b) lists instead of arrays, (c) a "compiler" that's mostly to keep code from being prohibitively slow, and (d) proper strings, but everyone says they want lists.
It seems to me that the people who want strings == lists are mostly looking for a Grand Unified Theory of Sequences. The idea is that if you don't want the standard lib to be a mess of
you'll just make everything lists, and to hell with the distinction. Everything's the same, so it's simpler!
You could tackle the problem from the other end. Other languages invest in abstractions to write code that sanely deals with different data types. What sort of abstractions do we get out of this? Often some form of object orientation, be it message-passing or generic functions or what-have-you. It starts looking pretty enticing: man, we could make everything an object, and to hell with the distinction. Everything's the same, so it's simpler!
Do you think it's a bad thing to have a specialized library for optimized string processing? In the big majority of cases, I personally don't care at all about the performance of my string processing. Would the needs arrive, I'd be perfectly willing to use another library specialized for that (Which I would accept that all the high level function won't work for optimization reasons).
Also, as you say, a couple of (case) would be needed in the standard library. But again, I hardly see why it is a bad thing? (Maybe multi-methods would be a better approach but that's another debate). My point is that I don't really care what the standard lib code looks like.. the important part is the end language result.. no?
Finally, I get your point about the "Grand Unified Theory of Sequences". However, this list of chars suggestion is more about making the code behaviour simpler.. not that much about trying to be "minimalist to be minimalist".
For instance, what (map bleh "test") should do? What should it return? If I know that "test" is simply a list of character, I know for sure what would happen (bleh would be applied on a character and map would returns a list of whatever the function returns). Now, what does it currently do? Maybe the same thing, maybe not. (See that post: http://arclanguage.org/item?id=12311) If my function returns a string instead of a character, it crashes.. since when does map expect something special? I.e. (map ... (range 1 10)) doesn't expect me to return a list of integer.
Do you think it's a bad thing to have a specialized library for optimized string processing?
Not in principle. Especially if it was totally transparent. This isn't the case in Haskell, because you wind up importing ByteString functions qualified with a prefix like B, so your code is littered with B.map this and B.length that.
But then, if it's totally transparent (i.e., same behavior & syntax between the inefficient one and the efficient one), what was the point of the separation to begin with? Just use the efficient one.
Also, as you say, a couple of (case) would be needed in the standard library.
Actually, no. I was saying that treating strings as lists would make code shorter. E.g., map has to check for strings manually right now.
(def map (f . seqs)
(if (some [isa _ 'string] seqs)
(withs (n (apply min (map len seqs))
new (newstring n))
((afn (i)
(if (is i n)
new
(do (sref new (apply f (map [_ i] seqs)) i)
(self (+ i 1)))))
0))
(no (cdr seqs))
(map1 f (car seqs))
((afn (seqs)
(if (some no seqs)
nil
(cons (apply f (map1 car seqs))
(self (map1 cdr seqs)))))
seqs)))
But if strings were built out of cons, we'd be able to prune out that first branch.
(def map (f . seqs)
(if (no (cdr seqs))
(map1 f (car seqs))
((afn (seqs)
(if (some no seqs)
nil
(cons (apply f (map1 car seqs))
(self (map1 cdr seqs)))))
seqs)))
(On that note, would there be a difference between "" and nil?)
Finally, I get your point about the "Grand Unified Theory of Sequences". However, this list of chars suggestion is more about making the code behaviour simpler.. not that much about trying to be "minimalist to be minimalist".
My point was that fusing lists and strings is a popular idea since Arc doesn't really have good facilities for polymorphism. You currently need to do the (case ...) junk (or macroexpand into it or whatever), since there are sequences with their subtle interface differences. Strings-are-lists would get rid of this (until we needed another sequence type...). Object-oriented languages "do polymorphism" better (e.g., with multimethods), but breed a fervor for all-things-OO similar to the just-make-everything-a-list sentiment, even though both are extremes.
I don't really care what the standard lib code looks like.. the important part is the end language result.. no?
Right now Arc sits in the middle, without a unified sequence interface -- be it making everything a list or having some other abstraction -- so we all suffer for it, both in the standard library and in user code. Here's a fun one:
The difference being count uses each, which is polymorphic (i.e., is written essentially with a big (case ...)), but counts hard-codes recursion on cdrs.
Not to get too hung up on this example -- I can appreciate the simplicity of the strings-are-lists model where map is concerned -- but...
You could argue that map's current behavior is sane. There's a subtle difference between expected behaviors, depending on how you want to interpret map. Currently, map says the output sequence should be of the same type as the input. As such, you might expect an error from
(map [+ "abc" _] "def")
if it was to be understood roughly as
(map-as 'string [+ "abc" _] "def")
since strings aren't really lists -- they don't have arbitrary elements. (Using the map-as from my post wouldn't actually throw an error here. coerce special-cases strings and flattens them. Yet another subtlety in expectations: should map's "same type" behavior abide by coerce's rules?)
This tangentially relates back to the contagion point in http://paulgraham.com/arcll1.html -- how to shift between strings and lists depending on what sorts of elements are added.
(Note: I don't by any means want to be aggressive. I'm still a beginner in the lisp world.. so everything I say here as a big: "Me being a real newbie thinks: " in front :) )
"But then, if it's totally transparent (i.e., same behavior & syntax between the inefficient one and the efficient one), what was the point of the separation to begin with? Just use the efficient one."
Maybe I wasn't clear.. but I never said it needed to be transparent. If I need my strings to be highly optimized, I'd much prefer use a specialized string library and use, say:
(which would take care of rebinding core high level functions)
-----
Also, I'm not sure I agree with you on the "(until we needed another sequence type...)." Why another sequence type? Any sequences could be coerce to simple list which work with the core functions. Use map-hash, or map-file, or map-whatever if you need specialized version for other sequences. (Or as I said in the last example)
-----
Finally, again (sorry), I don't really agree on: "map says the output sequence should be of the same type as the input."
Neither do I. Just trying to be terse (not that I am anyways; I have a problem with conciseness). :)
I never said it needed to be transparent
No, but I was. In my limited experience, using ByteStrings in Haskell is still too much work, as opposed to having the standard Prelude functions work "out of the box". Instead of being able to say
map (\x -> 'x') "abc"
you wind up needing to
import qualified Data.Bytestring as B
B.map (\x -> 'x') (B.pack "abc")
When you need to start changing every string-related function, the reader, the writer, blah blah blah, it gets to be a hassle. Perhaps it's less of a pain in dynamically-typed languages like Arc. I don't know.
Why another sequence type? Any sequences could be coerce to simple list which work with the core functions.
Not everything is a linked list. And forcefully coercing every data structure into a linked list wrecks the time & space complexities that give many data structures their purpose. You'd force ranges (virtual sequences, a la Python) to eat up memory, though you certainly want to (say) map over them. You force arrays to have O(n) random access times. You couldn't have immutable sequences because linked lists are mutable. Etc.
Use map-hash, or map-file, or map-whatever if you need specialized version for other sequences. (Or as I said in the last example)
Frankly, ad-hoc polymorphism is ugly. Take Scheme, for instance, whose (R5RS) standard comparison operators include:
"When you need to start changing every string-related function, the reader, the writer, blah blah blah, it gets to be a hassle. Perhaps it's less of a pain in dynamically-typed languages like Arc. I don't know."
I also don't know :) Maybe advanced arc users could share their opinion on that?
"Not everything is a linked list. And forcefully coercing every data structure into a linked list wrecks the time & space complexities that give many data structures their purpose."
Yes, this is true.
In fact, it's a decision that needs to be taken.. should the core high level function work against different data structure? (As it does with clojure?)
As for now, map does work with string (but has a weird behavior in my opinion) and doesn't work with hash. Is this what we want?
Also, what do you think about multimethods? Do you think it's something useful to be added in Arc?
---------
About the map input versus output, I get what you mean. However, (map [string "test" _] "123") should work :-/ Maybe the problem lies in the concatenation operator while constructing the new string. i.e.
(map [coerce _ 'int] "123") could give "116101115116"
(I know it's not a good example... however, look at this one) :
should the core high level function work against different data structure?
The answer seems to be a resounding yes. Polymorphism was one of Arc's main principles when it was 3 weeks old (http://paulgraham.com/arcll1.html), and one that's been more-or-less preserved to this day -- just clunkily.
doesn't work with hash
I don't care for maptable in Arc. Seems like something that should be done by map. I address the point about hash-tables-as-sequences more in http://arclanguage.org/item?id=12341.
Also, what do you think about multimethods? Do you think it's something useful to be added in Arc?
From what I've seen, generic functions (single dispatch or multimethods) seem a "Lisp-y" way of solving the type-dispatch problem, and you don't really need to go full-blown OO about it. But I don't know much about other options.
However, (map [string "test" _] "123") should work :-/
Oh, I agree. I was just saying, the case could be made. :P
I think my map-as (from your original thread: http://arclanguage.org/item?id=12341) reflects map's intended behavior best, since coerce is really our standard for how types should interact. Not that it should be implemented that way, necessarily. But since coerce will flatten strings, it seems fair to say that
The map-as approach would still preserve the input type == output type behavior, but do it by coerce's rules, which happen to play nicely with strings here.
I've been thinking about the semantics of maptable. Right now it seems misnamed; it iterates over the table before returning it unmodified. But what should the right semantics be? Should it return a table with modified values for the same set of keys? Or should it return a list? Or should each iteration return a (k v) pair so you can get a new table with entirely new keys (I think map-as does this)? All of these could be useful; I think we need a more elaborate language than just map/fold to describe them.
