http://freeshells.ch/~revence/simple.txt

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Woah... That's quite a lot of raving. ._.

His message seems fairly complex. Maybe it's incorrect?

Post a reply to this message

"Darren New" <dne### [at] sanrrcom> wrote

> http://freeshells.ch/~revence/simple.txt

The simple fact is any argument for Haskell and against other languages will
be valid when - scratch that - *if*  people start writing killer
applications, a killer OSs, APIs and killer games in Haskell.

Ah, I stand corrected, here's a killer game:

http://www.geocities.jp/takascience/haskell/monadius_en.html   <g>

from

http://www.haskell.org/haskellwiki/Applications (2nd on list)

I cannot imagine what Haskell will bring us in another 20 years. "A
scientist's toy box" is aptly where Haskell belongs.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> http://freeshells.ch/~revence/simple.txt

  He says that if you need to use arrays, the language is wrong.
That would make haskell wrong, because it supports arrays. (The question
would be: *Why* does it support arrays if, according to him, arrays are
completely unnecessary?)

  He also refers to this:

http://freeshells.ch/~revence/no-c.txt

  He is quite wrong at many places:

  He says that if everything you care about is speed, then you should use
assembly. This is completely wrong. 99.999% of programmers cannot beat a
good C compiler in speed by writing assembly directly. It's way too
complicated (especially with today's processor architectures with all their
multiple pipelines and whatnot).
  Even if you knew how to beat the C compiler by writing assembly directly,
you would be writing for *one* processor architecture only. Your code will
most probably become slower then the C version quite soon, probably in one
or two new processor versions.
  By writing in C you are making fast code for *all* possible processor
architectures which have a decent C compiler. This is simply *impossible*
to do by writing assembly (one reason being that you simply cannot predict
the future and know how processors will develop).
  So the answer is no: You cannot beat a C compiler by writing assembly.
Even if you beat it *now*, you will lose in the near future.

  "If it's speed you want, use macros, not functions." This guy must have
smoked something really bad.

  He also says that optimizing memory usage is complete nonsense. Clearly
he has never made programs which require handling humongous amounts of
data very fast. If he ever has to, and he is running out of memory, he
will have to start hand-optimizing with his beloved haskell using its
ugly byte arrays.

-- 
                                                          - Warp

Post a reply to this message

> His message seems fairly complex. Maybe it's incorrect?

It's simpler to ignore rants, but not always the correct solution.

Computers were created to automate complex and repetitive
tasks.  Therefore it follows that the more complex and
repetitive a task is to accomplish the more suitable it is to
being implemented on a computer.

In everyday life we typically reduce a task into smaller steps.

So if Darren is walking to China to deliver a letter, he'll
put one foot in front of the other, camp in various parks,
eat at countless burger stands, and probably buy
several pairs of shoes on the way. He would do all the work.

He might reduce the problem, and replace walking on
foot with driving his car, this shortens the time and means
less stops. He now lets the car do most of the work.

He might then replace the long drive with an airplane flight,
again, less time. Now the airlines do most of the work.

He might mail a letter instead. Now the postal service
uses some delivery trucks and a plane to deliver the letter,
they do most of the work.

He might use E-mail instead. Now the work is done by
computers and a few technicians.

Now let's say that Darren's friend in China is a really
attractive woman... a peviously unstated factor in his
deciding to take a trip to China. Now it can be seen
the best solution is not always the simple one, if you
allow for outside factors.

In terms of programming, an outside factor might be things
like available memory, disk space, or computation speed.
When memory comes into play you might need destructive
updates to arrays, etc.  The simplest solution isn't always
the best.

For example...
fac n = product [1..n]

This is simple code, but not always the quickest...

Here's a memoized version, it uses more memory
in order to gain speed...
fac :: Integer -> Integer
fac n = facList!!(fromInteger n)

facList = [fac' m | m <- [0..]]

fac' n | n == 0    = 1
       | otherwise = n * fac (n-1)

You can check the performance by mapping
a factorial over a list and taking the sum.  On
my machine the first one takes about 104 sec
to factorial numbers in a list [1..4000], the second
one does that in about 0.5 sec. Essentially the first
runs in O(n^2) time, and the second in O(n), but
has higher memory usage, it's a trade-off based on
outside factors, which one to use in which situation.

Post a reply to this message

"somebody" <som### [at] somewherecom> wrote:
> Ah, I stand corrected, here's a killer game:
>
> http://www.geocities.jp/takascience/haskell/monadius_en.html   <g>

You're not applying this guy's law of simplicity. Maybe his verse on features
will convince you of the value of Monadius:

"[Pet Peeve: Why do you add features to your software that, even though they
will
benefit 80% of your users, will kill the simplicity feature, from which 100% of
your users benefit? Features don't come for free - they feed on user comfort and
simplicity in use of the program and in code for as long as they exist. They are
insatiable parasites. Fight features, defend simplicity.]"

Clearly, Monadius is the best game in the world.

Tom

Post a reply to this message

Tim Attwood wrote:
> So if Darren is walking to China to deliver a letter,

> He might reduce the problem, and replace walking on
> foot with driving his car,

Being in the USA, I'd say both of these could be classified as "wrong" 
regardless of complexity. ;-)  [glub!]

> Now let's say that Darren's friend in China is a really
> attractive woman... 

Or, maybe my wife's relatives?  Don't get me slapped...

> When memory comes into play you might need destructive
> updates to arrays, etc.  

Which is only a problem if your compiler isn't smart enough, or 
disallows providing the appropriate hints. :-)

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> http://freeshells.ch/~revence/simple.txt

Sounds like an adolescent in love for Scheme and wanting the world to be all
about closures, tail-recursion and no explicit typing.  Until getting a bit
older and realizing it's not the world that should change to suit our needs,
but instead we should adapt to survive.

why is he comparing high level languages to high level assembly anyway?
Besides, the always-close-after-open thing in languages like C is a non-issue
when you use code templates and the likes...

Post a reply to this message

nemesis <nam### [at] gmailcom> wrote:
> Besides, the always-close-after-open thing in languages like C is a non-issue
> when you use code templates and the likes...

  In a way his approach to opening and reading the contents of a file seems
too simplistic:

  I agree: If what you are going to do is to read the entire contents of
the file into a string which you can then manipulate, the language offering
you a simple, easy and completely safe way to do this is a good thing.
  Given that languages like haskell use lazy evaluation, even if you are
only going to read part of the file and not the entire file, the haskell
compiler might probably be able to optimize it so that only that part of
the file is indeed read.

  However, I'm wondering what happens with huge files (which won't fit
in memory) and which you read thoroughly. It could be, for example, a
video file (which could be, for example, 3 gigabytes big, while your
computer has only eg. 1 gigabyte of RAM).
  The usual way of doing this is to read a bunch of data from the file
(for example some megabytes), process it, discard it, read a new bunch
of data from the file, etc.

  What I'm wondering is what a language like haskell will do in this case,
even though it has lazy evaluation. In fact, lazy evaluation is of no
help here because you are, after all, reading the entire file. If you
use the completely abstract way you could end up having the haskell
program trying to read the entire file into memory, thus running out of it.

  You have to somehow be able to tell it that you are only going to need
small bunches at a time, and after they have been processed, they can be
discarded. I wonder if there's a really abstract way of saying this in
haskell, or whether you need to go to ugly low-level specifics.

-- 
                                                          - Warp

Post a reply to this message

>> When memory comes into play you might need destructive
>> updates to arrays, etc.
>
> Which is only a problem if your compiler isn't smart enough, or disallows 
> providing the appropriate hints. :-)

The point is that there is no way for a compiler to decide.
Sometimes one is better, and sometimes another. It's up
to the programmer to pick what is correct. If a programmer
picks incorrect, it usually ends up being more complex
instead of simpler.

Post a reply to this message

>  The usual way of doing this is to read a bunch of data from the file
> (for example some megabytes), process it, discard it, read a new bunch
> of data from the file, etc.
>
>  What I'm wondering is what a language like haskell will do in this case,
> even though it has lazy evaluation. In fact, lazy evaluation is of no
> help here because you are, after all, reading the entire file. If you
> use the completely abstract way you could end up having the haskell
> program trying to read the entire file into memory, thus running out of 
> it.
>
>  You have to somehow be able to tell it that you are only going to need
> small bunches at a time, and after they have been processed, they can be
> discarded. I wonder if there's a really abstract way of saying this in
> haskell, or whether you need to go to ugly low-level specifics.

Because of lazy evaluation in Haskell, something like...

readFile "filename" >>= process

is read as a stream in chunks (of system dependent size) into
available heap memory, the entire file isn't read all into memory before
process is called, they are both actively executing at the same time.
After blocks of data are used by process, they're disposed of, the
file then closes itself after it's all read. A large file will hit GC.

In fact, if you are opening a large number of small files this lazy
evaluation of files gets to be a problem, too many file handles are
left open at once. There are ways to force it to read all the contents,
and thus close them quickly, if needed.

There are also more typical IO actions, like openFile which returns a
handle, hClose, and hSetBuffering if you want to over-ride the
default buffering, hFlush to flush the buffer, and other stuff for random
access.
http://haskell.cs.yale.edu/haskell-report/IO.html

Post a reply to this message

Tim Attwood <tim### [at] comcastnet> wrote:
> readFile "filename" >>= process

  Btw, how do you actually read the contents of the file in haskell with
a command like that? What is the unit type? Can you read, for example,
one byte at a time? What if you would want to parse an ascii-formatted
input file, for example? How is it done exactly?

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Tim Attwood <tim### [at] comcastnet> wrote:
> > readFile "filename" >>= process
>
>   Btw, how do you actually read the contents of the file in haskell with
> a command like that? What is the unit type? Can you read, for example,
> one byte at a time? What if you would want to parse an ascii-formatted
> input file, for example? How is it done exactly?

http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v%3AreadFile

readFile returns a String.  But don't despair:  it won't fill the whole memory
with a giant string for large files!  Lazyness means values are only evaluated
once needed.  If you just take the whole contents, yes, you'll be sorry.
Otherwise, you can use a function like "take 5 string" and it'll only take the
first five characters (a string is merely a list of characters in Haskell).
You may process it with folds or other higher-order functions.

To ilustrate lazyness in a simple REPL example:
ones = 1:ones
take 5 ones
take 5 (map (*2) ones)

ones is of course an infinite, recursively-defined list.  If you just evaluate
it at the prompt, the REPL will begin filling your screen with ones or worse
(like filling your memory).  The same for simply doing map (*2) ones which will
try to double every 1 in ones.

But lazyness means we can restrict the evaluated value to just a few members
from this infinite data structure, which is what we do by taking one a few.

So, with lazyness, size really doesn't matter.

Of course, there are other useful IO functions out there that offer more control
over opening/closing file handles etc.

Post a reply to this message

That didn't really answer the question of whether it is able to drop
the parts which are no longer used.

-- 
                                                          - Warp

Post a reply to this message

Tim Attwood wrote:
>>> When memory comes into play you might need destructive
>>> updates to arrays, etc.
>> Which is only a problem if your compiler isn't smart enough, or disallows 
>> providing the appropriate hints. :-)
> 
> The point is that there is no way for a compiler to decide.

...which is why you have the hints... ;-)

Post a reply to this message

somebody wrote:

> The simple fact is any argument for Haskell and against other languages will
> be valid when - scratch that - *if*  people start writing killer
> applications, a killer OSs, APIs and killer games in Haskell.
> 
> Ah, I stand corrected, here's a killer game:
> 
> http://www.geocities.jp/takascience/haskell/monadius_en.html   <g>
> 
> from
> 
> http://www.haskell.org/haskellwiki/Applications (2nd on list)
> 
> I cannot imagine what Haskell will bring us in another 20 years. "A
> scientist's toy box" is aptly where Haskell belongs.

Hmm... You're not going to talk about Haskell Quake then?

http://www.haskell.org/haskellwiki/Frag

Hardly "killer" (unless you'll pardon the pun), but at least a little 
more exciting...



One could legitimately level the claim that only real large-scale 
programs written in functional languages so far have been... compilers 
for more functional languages.

Still, I gather that Xilinix's current toolchain for FPGAs is based on 
Haskell technology. A few other blue-chip peeps are using it. Again, not 
really "killer" - for that, you must look to Erlang. *sigh*

Post a reply to this message

Warp wrote:

>   However, I'm wondering what happens with huge files (which won't fit
> in memory) and which you read thoroughly. It could be, for example, a
> video file (which could be, for example, 3 gigabytes big, while your
> computer has only eg. 1 gigabyte of RAM).
>   The usual way of doing this is to read a bunch of data from the file
> (for example some megabytes), process it, discard it, read a new bunch
> of data from the file, etc.
> 
>   What I'm wondering is what a language like haskell will do in this case,
> even though it has lazy evaluation. In fact, lazy evaluation is of no
> help here because you are, after all, reading the entire file. If you
> use the completely abstract way you could end up having the haskell
> program trying to read the entire file into memory, thus running out of it.

Not so.

>   You have to somehow be able to tell it that you are only going to need
> small bunches at a time, and after they have been processed, they can be
> discarded. I wonder if there's a really abstract way of saying this in
> haskell, or whether you need to go to ugly low-level specifics.

There is. It's called a garbage collector. ;-)

Simply let lazy evaluation read the file as required, and the GC can 
delete the data you've already processed transparently behind you.

In this way, linearly processing a file in constant RAM usage is pretty 
trivial in Haskell.

Now, *random* access... *that* presents a bit more of a problem. (For 
the love of God, don't accidentally hang on to pointers you don't need 
any more! You could end up loading the entire file into RAM - and, 
obviously, that would be "bad".)

Post a reply to this message

Warp wrote:
>   That didn't really answer the question of whether it is able to drop
> the parts which are no longer used.

Garbage collection.

In Haskell, a "string" is a linked-list of characters. Let go of the 
pointer to the start of the list and all elements up to the first one 
you've still got a pointer to will be collected and freed.

Post a reply to this message

Warp wrote:

>> readFile "filename" >>= process
> 
>   Btw, how do you actually read the contents of the file in haskell with
> a command like that? What is the unit type? Can you read, for example,
> one byte at a time? What if you would want to parse an ascii-formatted
> input file, for example? How is it done exactly?

First of all, reading binary data in Haskell is currently "messy". 
Haskell tends to assume that files contain plain ASCII. (If you want to 
be technical, it usually reads 8 bits at a time, and interprets these 
literally as a Unicode code-point.)

That aside, the readFile function gives you (conceptually) a giant 
string representing the entire contents of the file. In typical Haskell 
fasion, this doesn't get actually created until you "look at it".

If you wanted to parse a text file, you'd likely read the whole file 
into a string (conceptually) and then pass that over to your parser. The 
parser just knows how to parse strings; it doesn't have to care that 
*this* string is being transparently read from a file first.

Similarly, if you had a function that takes a string and returns the 
decrypted form of that string, you could apply that to the thing 
returned from readFile and then pass the answer to your parser. The 
result is that the decryption function only decrypts data as the parser 
tries to demand it (due to lazy evaluation). All that stuff that Java 
does with layering stream filters is just function calls in Haskell.



Now, the flip side to all this is that lazy file reading can bite you. 
For example, one guy wrote some program that would crash with an OS 
error complaining about too many open file handles. Letting go of a 
pointer to a file handle causes the file to be closed WHEN THE GC RUNS, 
however exhausting the OS handles limit does not trigger the GC...

There is a certain faction of the Haskell community that considers 
readFile and its ilk to be "evil" and who say you should do things the 
manual way. For example, check this out:

   main = do
     data <- readFile "foo.txt"
     deleteFile "foo.txt"
     writeFile "bar.txt" data

This doesn't work at all. If you run this, the behaviour is technically 
undefined, but generally you will get some kind of OS error. Put simply, 
the first line doesn't *really* read any data - but then you try to 
delete the file (which hasn't actually been read yet, only opened), and 
then write the data to another file (which causes it to actually be 
read). Usually deleting the file is where it will bomb out - the OS will 
usually complain that you can't delete an open file...

Somebody did suggest a file that lazily reads directory structures, and 
allows you to lazily modify them. The general reply was "OMG, NO!!"



As you might expect, Haskell provides primitives for doing file I/O the 
"normal" way. In other words,

   openFile
   hCloseFile
   hReadLine
   hPutStrLn
   hFlush
   etc.

For interactive stuff at a minimum, it's usually critical to control 
exactly *when* I/O happens. And the only way to do this is... to specify 
exactly when I/O happens. No way round it.

Post a reply to this message

Orchid XP v7 wrote:
> Tim Attwood wrote:
>>>> When memory comes into play you might need destructive
>>>> updates to arrays, etc.
>>> Which is only a problem if your compiler isn't smart enough, or 
>>> disallows providing the appropriate hints. :-)
>>
>> The point is that there is no way for a compiler to decide.
> 
> ....which is why you have the hints... ;-)

Or iterative optimizations, like big SQL servers do.  The program runs 
profiled a few times, and tells the linker/compiler which versions run 
faster etc.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

>>> The point is that there is no way for a compiler to decide.
>>
>> ....which is why you have the hints... ;-)
> 
> Or iterative optimizations, like big SQL servers do.

Mmm... big SQL servers do this because which method is faster *strongly* 
depends on the exact data being queried. It's just not possible to make 
reasonable decisions at design-time, it must be at run-time.

I'm not sure all programs face quite such colossal challenges as an SQL 
system... ;-)

Post a reply to this message

>  That didn't really answer the question of whether it is able to drop
> the parts which are no longer used.

The answer is yes, mostly.

Data is automatically destroyed as it goes out of scope. So if you
have a process that works one line at a time, then one line at a time
will be disposed, if you have a process that works on single chars
then one char at a time is disposed.

In general, Haskel takes some input to a function,
produces some new data output in fresh memory,
and then disposes of the input,
and frees that memory if no other function references it,
eventually GC reclaims the memory. (or you can
manually trigger a GC if you want).

File IO is imperative, so it can be treated in manners
typical of other languages. You don't need to bind >>=
files to processes, it's perfectly OK to read one line
at a time and do something with it until the EOF is reached.

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> Garbage collection.

> In Haskell, a "string" is a linked-list of characters.

  I shudder thinking how much memory that must require...

-- 
                                                          - Warp

Post a reply to this message

Tim Attwood <tim### [at] comcastnet> wrote:
> Data is automatically destroyed as it goes out of scope.

  But in this case the data is one big string?

  Someone else said that string are actually linked lists of characters
where each character is garbage-collected. This must require humongous
amounts of memory, especially considering that one character would only
require 1 byte...

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> Letting go of a 
> pointer to a file handle causes the file to be closed WHEN THE GC RUNS, 
> however exhausting the OS handles limit does not trigger the GC...

  This is exactly one of my points in my "I hate Java" page. Garbage
collection is good when the resource is memory, but memory is not the
only resource you can allocate. In some cases (as this one) you have
to free the resource *immediately* when it's not needed anymore, else
malfunction can happen.

  Of course in good modular programming it's the same module which
reserved the resource which should take care of freeing it when it's
not needed anymore. Having to manually call some cleanup function from
the outside breaks modularity.

  What I wonder is why everyone talks like there wouldn't be any negative
sides to GC.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> Simply let lazy evaluation read the file as required, and the GC can 
> delete the data you've already processed transparently behind you.

  That's not possible if the file is indeed read into one single string.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   What I wonder is why everyone talks like there wouldn't be any negative
> sides to GC.

Here's the thing: If you could find all the root pointers in a C++ 
program and know which things pointed to what, you could add GC to C++ 
pretty easily without losing any functionality. GC is a strict superset 
of what C++ gives you, avoiding much of the copying and most or all of 
the errors that C++ leaves you open to.

And it's not like C++ keeps you from leaving resources hanging around. I 
have a C++ program right now that you sure better make sure the client 
can talk to the server, because if it can't, the client leaves the 
broken socket open, only to run out of sockets and crash out some time 
later.

I "fix" this by exec'ing the program in a separate process from a 
program in a GCed language, watching for the debug output to stop, and 
respawning the program when it dies. :-)

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> Simply let lazy evaluation read the file as required, and the GC can 
>> delete the data you've already processed transparently behind you.
> 
>   That's not possible if the file is indeed read into one single string.

My guess is that internally it works the same way you'd do it from C: 
you read a buffer, walk thru the buffer, and then discard the buffer. 
There's no reason it can't work that way, just because it *looks* like a 
list of characters at the program level, any more than getchar() really 
reads one character at a time.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Here's the thing: If you could find all the root pointers in a C++ 
> program and know which things pointed to what, you could add GC to C++ 
> pretty easily without losing any functionality. GC is a strict superset 
> of what C++ gives you, avoiding much of the copying and most or all of 
> the errors that C++ leaves you open to.

  Let's wait for the new C++ standard and see what compilers come up
with... :)

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> My guess is that internally it works the same way you'd do it from C: 
> you read a buffer, walk thru the buffer, and then discard the buffer. 
> There's no reason it can't work that way, just because it *looks* like a 
> list of characters at the program level, any more than getchar() really 
> reads one character at a time.

  If a string is really internally a list of smaller strings, wouldn't GC
become more difficult because you can actually have "references" pointing
to the middle of such strings and not their base?

  I must admit, though, that I don't know how GC is implemented.

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> That didn't really answer the question of whether it is able to drop
> the parts which are no longer used.

no, I don't think readFile per se is a great means of working with large files.
It binds the whole contents as a string to a "variable" and even if you process
it by reading only a few chunks, the already read content is supposedly being
accumulated in the binding "variable".  I don't think if you go back and read
chunks from the beginning of the string the function actually goes back and
performs IO to read that position again.

laziness is great for highly abstract algebraic datatypes, but not that great
for IO.  For that, you have buffered IO just like in other languages (except
for being monadic).

Post a reply to this message

Warp wrote:
>   If a string is really internally a list of smaller strings, wouldn't GC
> become more difficult because you can actually have "references" pointing
> to the middle of such strings and not their base?

You'd have to implement that kind of reference as a base+offset sort of 
thing. Or buffer it and copy it into a list as needed, like building up 
something from multiple reads of C stdio.

>   I must admit, though, that I don't know how GC is implemented.

No, you're right. The kind of GC that can handle arbitrary pointers is 
called "conservative GC" if I recall correctly.  It works pretty poorly.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

>  But in this case the data is one big string?
>
>  Someone else said that string are actually linked lists of characters
> where each character is garbage-collected. This must require humongous
> amounts of memory, especially considering that one character would only
> require 1 byte...

Yeah, it does take a lot, and it uses unicode for characters too,
I think I heard it takes about 12 bytes per character that way.
It's perty bad on big files.

You can use the ByteString module though, it uses a single byte
value for a character, and passes pointers and stuff around behind
the scenes to avoid duplicating stuff that doesn't need to be.
A ByteString is sort of a list of pointers to C style strings, but
with all the pointers hidden.

Post a reply to this message

Tim Attwood <tim### [at] comcastnet> wrote:
> Yeah, it does take a lot, and it uses unicode for characters too,
> I think I heard it takes about 12 bytes per character that way.
> It's perty bad on big files.

  But hey, that's the fad in modern programming: Memory usage and speed
are irrelevant. Processors are getting faster and memory amounts are
doubling every couple of years, so who cares if something like a string
takes 12 times as much memory as it could?

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> Warp wrote:
> >   That didn't really answer the question of whether it is able to drop
> > the parts which are no longer used.

> Garbage collection.

> In Haskell, a "string" is a linked-list of characters. Let go of the 
> pointer to the start of the list and all elements up to the first one 
> you've still got a pointer to will be collected and freed.

  Btw, what does it do if you jump to the beginning of the string after
it has been garbage-collected? (After all, from the programmer's point
of view it's one single string, so you should be able to read it from
whatever point you like, shouldn't you?)

-- 
                                                          - Warp

Post a reply to this message

Tim Attwood nous apporta ses lumieres en ce 2007/11/01 03:34:
>>  But in this case the data is one big string?
>>
>>  Someone else said that string are actually linked lists of characters
>> where each character is garbage-collected. This must require humongous
>> amounts of memory, especially considering that one character would only
>> require 1 byte...
> 
> Yeah, it does take a lot, and it uses unicode for characters too,
> I think I heard it takes about 12 bytes per character that way.
> It's perty bad on big files.
It's about 12 BITS per characters, on average, not BYTES! That's useing UTF8 
encoding. About 16 BITS per characters if using UTF16 encoding.
UTF8 is only 7 BITS per characters if you stick to only standard ASCII 
characters set, but it gets bigger if you also use extended ASCII or characters 
from foreign alphabets.
> 
> You can use the ByteString module though, it uses a single byte
> value for a character, and passes pointers and stuff around behind
> the scenes to avoid duplicating stuff that doesn't need to be.
> A ByteString is sort of a list of pointers to C style strings, but
> with all the pointers hidden. 
> 
> 


-- 
Alain
-------------------------------------------------
You know you have been raytracing for too long when the animation you
render will be finished after yourself.
Urs Holzer

Post a reply to this message

Warp wrote:
>   Btw, what does it do if you jump to the beginning of the string after
> it has been garbage-collected? 

It won't get GCed if it's possible to jump to the beginning.

> (After all, from the programmer's point
> of view it's one single string, 

If it's that, and not a "linked list of characters" (from the 
programmer's point of view), then it won't get GCed until you're done 
with it.

Probably not a good way to process big files, tho, just as it's not a 
good idea in C. :-)

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Warp wrote:
>   But hey, that's the fad in modern programming: Memory usage and speed
> are irrelevant. Processors are getting faster and memory amounts are
> doubling every couple of years, so who cares if something like a string
> takes 12 times as much memory as it could?

Depends on the size of the string, really. If my 100-byte string holding 
an email address turns into 1200 bytes, I'm not really going to worry 
about it much. :-)  Agreed, really big strings where you're actually 
starting to cause significant paging can be a problem, but you're really 
just hitting the wall earlier in Haskell than in other impelmentation.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Alain <ele### [at] netscapenet> wrote:
> It's about 12 BITS per characters, on average, not BYTES! That's useing UTF8 
> encoding. About 16 BITS per characters if using UTF16 encoding.
> UTF8 is only 7 BITS per characters if you stick to only standard ASCII 
> characters set, but it gets bigger if you also use extended ASCII or characters 
> from foreign alphabets.

  Except that if each single character is indeed garbage-collected, that
requires quite a lot of memory per character (compared to the size of the
character).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
> 
>> In Haskell, a "string" is a linked-list of characters.
> 
>   I shudder thinking how much memory that must require...

It's fine for "small" strings. For "large" strings, it's really 
sub-optimal in space and time.

This is why the "ByteString" library was developed. It can present a 
string-style interface, yet every character consumes only 1 byte of 
storage (plus a little overhead for the array itself).

In the most efficient variant, the string is actually a linked list of 
array chunks. That means you can do fast concatinate (just link some 
chunks together), fast substring extraction (just point to the ends, no 
data is copied), and GC can free individual chunks of data. And yet, it 
all handles "as if" it were a naive linked list of individual characters...

So you see, Haskell *can* be made efficient. It's just not completely 
done yet.

Post a reply to this message

Darren New wrote:
> Warp wrote:
>>   Btw, what does it do if you jump to the beginning of the string after
>> it has been garbage-collected? 
> 
> It won't get GCed if it's possible to jump to the beginning.

What Darren said. ;-)

Notice that a string is a *single-linked* list. (I.e., there are "next" 
pointers but no "prev" pointers.)

Post a reply to this message

Warp wrote:

>   Someone else said that string are actually linked lists of characters
> where each character is garbage-collected. This must require humongous
> amounts of memory, especially considering that one character would only
> require 1 byte...

No - it's Unicode. 24 bits per character. ;-)

But yes, the standard Haskell string type is geared to flexibility, not 
performance. See my ByteString comments...

Post a reply to this message

Warp wrote:
> Alain <ele### [at] netscapenet> wrote:
>> It's about 12 BITS per characters, on average, not BYTES! That's useing UTF8 
>> encoding. About 16 BITS per characters if using UTF16 encoding.
>> UTF8 is only 7 BITS per characters if you stick to only standard ASCII 
>> characters set, but it gets bigger if you also use extended ASCII or characters 
>> from foreign alphabets.
> 
>   Except that if each single character is indeed garbage-collected, that
> requires quite a lot of memory per character (compared to the size of the
> character).

I can't actually find documentation to hand to clarify whether it's 12 
bits or 12 bytes per character. (My strong suspecion is that it *is* 12 
*bytes* - since, after all, a single Unicode code point is 24 bits already.)

The situation is actually worse than it looks. All this lazy evaluation 
magic is implemented by storing program state around the place, so an 
"unevaluated" string probably takes up more space still...

Post a reply to this message

Warp wrote:

>   But hey, that's the fad in modern programming: Memory usage and speed
> are irrelevant. Processors are getting faster and memory amounts are
> doubling every couple of years, so who cares if something like a string
> takes 12 times as much memory as it could?

Well, no. There are people working in the Haskell community to fix this 
and related problems. (Can't comment on other programming languages...)

The nice thing about Haskell is that is *allows* you to come up with a 
better implementation and slip it in there later.

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> Simply let lazy evaluation read the file as required, and the GC can 
>> delete the data you've already processed transparently behind you.
> 
>   That's not possible if the file is indeed read into one single string.

Nope, linked list. Each link in the chain can be read seperately when 
accessed.

(As a matter of fact, I very much doubt it reads a single character at 
once. It probably reads much more than that, for efficiency's sake...)

Post a reply to this message

Le 01.11.2007 20:00, Orchid XP v7 nous fit lire :
> No - it's Unicode. 24 bits per character. ;-)

Unicode is just a bunch of tables of glyphs (lot of tables, lot of
glyphs).
It is past 24 bits since a few...  (even past 32 bits!!!)
The real thing is how you encode all these.
UTF-8 is one way (the popular one these days),
UTF-16 another...  and raw storage the worst idea ever!

UTF-8 is about 8 bits for ascii range, usually go up to 24 bits (3 x
8) for classical japanese, 16 for most french variants...

> 
> But yes, the standard Haskell string type is geared to flexibility, not
> performance. See my ByteString comments...

Fixed size unicode... if only they stop adding more tables!

-- 
The superior man understands what is right;
the inferior man understands what will sell.
-- Confucius

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> This is why the "ByteString" library was developed.

  It just shows that the original article which spawned this thread is
naive. *In theory* you can have all kinds of fancy high-level uber-abstract
constructs which abstract away all the dirty internal details. *In practice*,
however, you still need those dirty details if you want any efficiency.
The fancy theories may be good in a big bunch of programs, but like so many
abstractions before, it's not the final silver bullet of programming.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> Notice that a string is a *single-linked* list. (I.e., there are "next" 
> pointers but no "prev" pointers.)

  You can't random-access a string in haskell? You can just go through it
once and that's it? That would be quite limiting...

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> The nice thing about Haskell is that is *allows* you to come up with a 
> better implementation and slip it in there later.

  Is that really so? Can you refactor an existing solution (eg. in a library)
so that it will be more efficient (eg. memorywise) without breaking any
existing programs?

-- 
                                                          - Warp

Post a reply to this message

"Darren New" <dne### [at] sanrrcom> wrote
> Warp wrote:

> Depends on the size of the string, really. If my 100-byte string holding
> an email address turns into 1200 bytes, I'm not really going to worry
> about it much. :-)

Ah yes. Next thing you know, somebody else (or you, in a couple of weeks) is
re-using that piece of code to manage an address book, later, a mailing
list. It's never a bad idea for your code to be scalable. OOP in general,
and bottom up thinking has been a minor disaster in this respect, since many
a programmer fail to think about optimized data structures for the overall
picture any more, and things get quickly out of hand memory and
performancewise.

Post a reply to this message