Path: utzoo!mnetor!uunet!husc6!ut-sally!utah-cs!defun.utah.edu!shebs
From: shebs%defun.utah.edu.uucp@utah-cs.UUCP (Stanley T. Shebs)
Newsgroups: comp.lang.prolog
Subject: Re: Strings
Message-ID: <5349@utah-cs.UUCP>
Date: 15 Mar 88 16:20:23 GMT
References: <512@ecrcvax.UUCP> <768@cresswell.quintus.UUCP> <5348@utah-cs.UUCP> <776@cresswell.quintus.UUCP>
Sender: news@utah-cs.UUCP
Reply-To: shebs%defun.utah.edu.UUCP@utah-cs.UUCP (Stanley T. Shebs)
Organization: PASS Research Group
Lines: 49

In article <776@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:

>If you need random access into some collection, a vector-like structure
>is going to be a really good idea.  The point is that most uses of STRINGS
>just aren't like that.

In other words, if I use strings in the ways for which lists are a good
representation, fine, and if I don't, then my program is going to have
really shabby performance.

>	Arithmetic in Basic Algebraic Domains
>	Collins, Mignotte, & Winkler
>which describes a number of algorithms Knuth didn't.
>This chapter claims quite strongly that list representation is better
>for bignums.  The fact that one seldom if ever accesses the "elements"
>of a bignum in other than strict sequential order suggests that this
>may be a good idea.

Actually, I'm in the process of constructing a system that will (among
other things) try using lists to represent bignums.  Experimentation will
involve using both representations within a language, to see how they compare.

>I used "boxing" loosely.  I did not, as Shebs excusably thinks, mean
>"allocating storage for", but "suitably locating in a register and
>supplying with an appropriate tag".  This is cheap, but it isn't free.

Tagging it shouldn't be necessary, either, but I grant that the character
has to live in a register, at least temporarily - most machines are pretty
insistent on having their intermediate data in registers. :-)

>> I think the real underlying motivation for strings is that languages like C
>> can do string processing with essentially zero space and time overhead,
>
>C can do this precisely because it ****HASN'T**** got a string data type!

But surely you're not suggesting that Prologs provide "buffers"?  Perhaps
I'm the only person left in the world who cares about abstraction, but
I thought that the whole rationale for high-level languages was to have
datatypes that are *not* exact equivalents of machine structures, and it's
the business of the language implementation to choose structures for those
datatypes that are both compact and efficient.  If lists are *always* the
most efficient approach for processing sequences, fine.  If they are not,
then the implementation should use something else.

Ah well, these days the drumbeat is for low-level languages like C to do
everything.  Who needs Prolog when you can hack the bits directly, eh?

							stan shebs
							shebs@cs.utah.edu