Re: [Caml-list] How to do this properly with OCaml?

Re: [Caml-list] How to do this properly with OCaml?

[David Thomas]

Adding to stdlib is silly if no one is going to be
using the addition, particularly when the lack of
availability of the structure will promote better
programming.  I'm not saying that last bit will always
be the case, but in many cases it is.  Again, the list
is:

(1) See if there's a better algorithm.
(2) Write it inefficiently.
(3) If the program is running poorly, profile.  

If the inefficiency added in (2) is the cause, then
(3a) See if there's a better algorithm.
(3b) Talk about fixing the stdlib.

else, 
(4) fix bottleneck, and go back to (3)

Until you've reached (3b), the stdlib isn't deficient.



--- Jon Harrop <jon@ffconsultancy.com> wrote:

> On Wednesday 27 July 2005 16:34, you wrote:
> > I'm still curious what numerical algorithm is so
> > desperately in need of variable length arrays...
> 
> I've no idea. I think he just wants a fuller stdlib.
> :-)
> 
> -- 
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.
> Objective CAML for Scientists
>
http://www.ffconsultancy.com/products/ocaml_for_scientists
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 2267 bytes --]

On Sun, 2005-07-31 at 01:06 +0100, Jon Harrop wrote:

> Yes, I think the only advantage of extensible arrays is a slightly improvement 
> in the constant prefactor in the complexity of some algorithms.

Not quite, simply because 'complexity' is not the only
thing of importance, since it only applies to asymptotic
behaviour, which of no interested to clients of algorithms,
only algorithm providers: clients are interested in 
performance and limits on problems which can realistically
be solved on their hardware, which is bounded in memory,
and limited by processing speed -- please take that
as a definition of 'client', ok?

Here, the 'constant prefactor' can degrade and lead
to quite significant differences: for example

(a) doubling the amount of store your major data structure
needs is only a 'constant' factor, but may make solution
of a problem you are interested in swap from being
barely possible to out of the question.

(b) because of caching effects, the performance over
ranges of problem size may not be 'linear' in the
theoretical complexity: doubling the number of
indirections could spill a fully 'in cache'
intense computation out to the next level of
caching and lead to an order of magnitude performance
loss on just the size of problem you're interested in:

I have been in several 'industrial' situations where
this has actually happened, eg in a telco where
a transaction rate of 60 calls/second for a switch
was achieved but they needed more like 
600 calls/second .. buying 40 servers instead of 4
isn't something you wish to tell your prospective
clients they must do to use your software... :)

Another scenario, recently discussed, where this
happens is in games: close to the hardware solutions
for graphics are often unnecessary but done anyway
because programmers don't understand performance
characteristics of their code, but sometimes
there are places where there is just no other way to 
build a viable product.

In these types of situations, it is better if the
vendor doesn't try to tell the application developer
what they really need: better to let the application
developer make their own mistakes :)



-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 2397 bytes --]

On Sun, 2005-07-31 at 01:24 +0200, Thomas Fischbacher wrote:

> I originally was somewhat worried whether extensible arrays really would 
> be such a dramatic improvement - what if the next person needs displaced 
> arrays, or any other functionality from CL's arrays with their many bells, 
> gongs, and whistles? But thinking a bit more about it, it seems as if
> virtually anything of interest could be accomplished by other means, with 
> the exception of just extensible arrays.

You have gone further than me, since your thoughts support
the proposition that extensible arrays are the *only*
data structure missing from the core libraries,
which cannot be safely encoded by the end user in Ocaml.

Whether or not that proposition is sustainable,
it would just be nice if the programmer had a choice:
it should not really be that the compiler vendor
forces the programmer to make a particular choice
for their application, IMHO.

I have been quite involved in another such scenario,
where the compiler vendor 'forces' the naive C
programmer requiring user space context switching
to write compiler dependent assembly code to do that
job, since the standard library setjmp/longjmp doesn't
quite do enough. For C this is not too onerous, particular
for OS that now provide this support in a library ..
however for C++ it is virtually impossible, since with
exception handling the stack modelling is much more
difficult than plain C.

My argument here is that 'control exchange' is an absolutely
fundamental computing primitive, and the failure of the
C language to provide it utterly condemns C as a general
language -- and has forced generations of developers
to encoding things badly, lead to miseducation, and 
a lot of other serious problems. I would direct the
same wrath at C++ for failing to provide proper
discriminated unions and first class lexically
scoped functions: to build a programming system
that deliberately omits *fundamentals* of programming
is shameful.

Of course this doesn't apply nearly as strongly to
extensible arrays: they're hardly fundamental
in the theoretical sense that control exchange,
categorical sums, and first class functions
with closures are: its merely a commonly data structure,
certainly less useful in Ocaml than some other systems.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[james woodyatt]

On 30 Jul 2005, at 16:33, Thomas Fischbacher wrote:
> On Wed, 27 Jul 2005, David Thomas wrote:
>> I'm still curious what numerical algorithm is so desperately in  
>> need of variable length arrays...
>
> There are quite some geometric algorithms where you want to process a
> subset (of a priori unknown size) of all geometric entities that  
> satisfy a
> certain constraint by decreasing priority. Using a binary heap  
> implemented
> on top of an array often is a reasonable choice there.

Yes, but is there ever a case where it would be a reasonable choice  
to use an extensible array for this instead of simply using a purely  
functional skew-binomial heap, e.g. [Cf_sbheap] from my OCaml NAE  
core foundation library?


-- 
j h woodyatt <jhw@wetware.com>
markets are only free to the people who own them.

Re: [Caml-list] How to do this properly with OCaml?

[Jon Harrop]

On Sunday 31 July 2005 00:24, Thomas Fischbacher wrote:
> I originally was somewhat worried whether extensible arrays really would
> be such a dramatic improvement - what if the next person needs displaced
> arrays, or any other functionality from CL's arrays with their many bells,
> gongs, and whistles? But thinking a bit more about it, it seems as if
> virtually anything of interest could be accomplished by other means, with
> the exception of just extensible arrays.

Yes, I think the only advantage of extensible arrays is a slightly improvement 
in the constant prefactor in the complexity of some algorithms.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] How to do this properly with OCaml?

[Thomas Fischbacher]

On Wed, 27 Jul 2005, David Thomas wrote:

> I'm still curious what numerical algorithm is so
> desperately in need of variable length arrays...

There are quite some geometric algorithms where you want to process a 
subset (of a priori unknown size) of all geometric entities that satisfy a 
certain constraint by decreasing priority. Using a binary heap implemented 
on top of an array often is a reasonable choice there.

I am not an expert on this, but I think that even some algorithms that 
deal with the problem of permuting indices of a sparse matrix to optimize 
cache efficiency of subsequent matrix-vector products may belong to this 
category. Now if the sparse matrix is not known a priori, but assembled at 
run time...

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] How to do this properly with OCaml?

[Thomas Fischbacher]

On Thu, 28 Jul 2005, skaller wrote:

> I'm not arguing "I don't like this approach". I already know
> of several ways to do variable length arrays, you haven't
> shown me anything new: it seems you're simply not accepting
> my assertion: it isn't possible to do it efficiently
> in Ocaml without magic: either Obj.magic or C code with
> an Ocaml interface: both solutions are fragile and
> require secret knowledge of ocaml implementation.

Plus keeping fingers crossed that major compiler changes will not break 
those implementations. (What if, at one point, GC would start making extra 
homogeneity assumptions over arrays - if it does not do so already?)

> Thus, to safely use variable length arrays they
> have to be provided by INRIA. That doesn't imply
> they *should* be provided by INRIA of course.
> I can always use a different data structure,
> ignore safety, or use another programming language.

First of all, it certainly would be nice if OCaml provided more 
flexible arrays. There are specialized applications where it really is a 
pain having to emulate them manually, and especially if it's about 
numerics, extra consing / indirection often have to be reduced to a 
minimum.

I originally was somewhat worried whether extensible arrays really would 
be such a dramatic improvement - what if the next person needs displaced 
arrays, or any other functionality from CL's arrays with their many bells, 
gongs, and whistles? But thinking a bit more about it, it seems as if
virtually anything of interest could be accomplished by other means, with 
the exception of just extensible arrays.


-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] How to do this properly with OCaml?

[Paul Snively]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


On Jul 28, 2005, at 11:26 AM, Jonathan Bryant wrote:

> Is this was possible?  It thought you could only dynamically load
> bytecode from a running bytecode program and not from native code.  I
> know you can't dynamically load native code, though.
>
Regrettably, it would appear that you're correct, so the situation is  
rather more dire than I had understood it to be. Thanks for the  
correction!

> -- 
> *=========================*
> |Jonathan Bryant          |
> |Valdosta State University|
> |Information Technology   |
> |System Operations        |
> |-------------------------|
> |jtbryant@valdosta.edu    |
> |x6358                    |
> *=========================*
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Best regards,
Paul Snively


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Darwin)

iEYEARECAAYFAkLpZe4ACgkQO3fYpochAqKZJgCg3jn0CG4ftvl8GnmSYz28UZ+J
4MAAni0yQ4uWmmP7ej4SCSAQAhnf8dCr
=o7a3
-----END PGP SIGNATURE-----

Re: [Caml-list] How to do this properly with OCaml?

[Jonathan Bryant]

On Wed, 2005-07-27 at 17:03 -0700, Paul Snively wrote:
> ... Heck, the  
> game logic could even be compiled to native code, although mods etc.  
> would have to be bytecode-compiled in order to be dynamically  
> loadable. ...

Is this was possible?  It thought you could only dynamically load
bytecode from a running bytecode program and not from native code.  I
know you can't dynamically load native code, though.

-- 
*=========================*
|Jonathan Bryant          |
|Valdosta State University|
|Information Technology   |
|System Operations        |
|-------------------------|
|jtbryant@valdosta.edu    |
|x6358                    |
*=========================*

Re: [Caml-list] How to do this properly with OCaml?

[David Thomas]

Ah.  I personally have a vendetta against floating
point in general, so I'll stay away from that one
then, as I don't want yet another discussion to
degrade into a flame war.  If anyone's curious about
my thoughts on the matter in detail, they can feel
free to email me directly, though.

--- skaller <skaller@users.sourceforge.net> wrote:

> On Wed, 2005-07-27 at 08:35 -0700, David Thomas
> wrote:
> > I'm still curious what numerical algorithm is so
> > desperately in need of variable length arrays...
> 
> I think I was not clear. Normally Ocaml boxes
> contain either an int or a heap pointer
> to a data object. So a floating point value
> is represented by a pointer.
> 
> Doing numerical programming with an array
> of pointers to floats instead of an
> array of floats has a performance impact,
> so Ocaml now provides arrays of unboxed floats.
> 
> I wasn't referring to the need for variable length
> arrays
> in numerical code, but the need to circumvent boxing
> in numerical code for arrays of numerical values:
> this is considered significant enough to warrant
> specialised compiler optimisations and data
> structures.
> 
> The point being, arrays of boxes are considered
> inefficient,
> and in some cases it is already considered
> significant
> enough for considerable work to be done to fix it.
> 
> So arguing an extra indirection required for the
> array of option solution to variable length arrays
> is insignificant is contrary to the evidence that
> INRIA already accepts it can be inefficient.
> 
> Again, this is not to say variable length arrays
> without this extra overhead should be provided,
> just that the argument that the overhead is not
> significant is suspect.
> 
> -- 
> John Skaller <skaller at users dot sourceforge dot
> net>
> 
> > _______________________________________________
> Caml-list mailing list. Subscription management:
>
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Re: [Caml-list] How to do this properly with OCaml?

[Michael Walter]

Hello,

> Fact is that most PC games I have played the programmers
> didn't have the faintest idea how to get good frame rates,
> in fact they couldn't even get double buffering to
> work properly -- 2/3 games the mouse cursor is incorrectly
> handled (and also on some Gnome/Linux apps too, it is done wrong).

I suspect the problem was vsync being disabled, not single buffering.
You can force that on in the control panel.

> however for larger games, eg RPG or Strategy class PC games,
> you aren't tweaking the hardware anyhow: you'll have an
> underlying abstraction like DirectX or OpenGl to work with
> instead. On that class of platform, Ocaml would be quite
> competitive IMHO.

These are pretty low-level as well (make no mistake, most of OpenGL's
seemingly high-level interface is unused in games since it just
doesn't cut it performance-wise).

Cheers,
Michael

Re: [Caml-list] How to do this properly with OCaml?

[Paul Snively]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


On Jul 27, 2005, at 2:13 PM, Pal-Kristian Engstad wrote:

> 1. It doesn't support console platforms.
>     - The PC market is quite minor compared to consoles.
>
I'd say that depends a great deal upon the type of game that you're  
developing. For example, I don't find it at all surprising that Deus  
Ex, developed for the PC first and ported to consoles, did much  
better in the marketplace than Deus Ex 2, developed for consoles  
first and ported to the PC. Consoles just aren't up to the kind of  
more-than-point-and-shoot interaction that PCs offer and a title like  
Deus Ex relies on.

> 2. It doesn't support low-level constructs.
>     - No SIMD (AltiVec/VMX) vector operations.
>     - No explicit assignment of (bit and byte) offsets
>       within a record.
>     - No explicit alignment specification.
>     - No inline assembly.
>
Again, apart from consoles, which tend not to have the operating  
system/middleware support we enjoy on other platforms and do have  
interfaces to from O'Caml, it's not clear at all why this is  
important. In any case, there is actually an AltiVec library for O'Caml.

> 3. There is no controlled real-time GC.
>     - GC needs to run between frames,
>       and only for a controlled amount of time.
>
It would be interesting to see some experiments around GC and the  
desire to have some kind of QoS guarantees around framerates. I  
personally haven't been impressed with current claims of constancy in  
framerates, and have found that the easiest way to get more bang for  
my framerate buck is to have more VRAM so more stuff gets cached for  
longer.

> 4. There is no real support for unboxed data-types.
>     - This one is actually very important for consoles.
>
I dunno; I find having all-float records or arrays of floats unboxed  
to be sufficient, but again, I suspect that if I were targeting  
platforms with less in the way of middleware/OS support, I might be  
more concerned.

> For game-code (AI, behaviors, etc.), it is better suited,
> though the GC issue is there. But it doesn't support much
> of threading - be it through pthreads or cooperatively -
> which renders it unusable to us.
>
So your point is basically that you wouldn't want to write your  
renderer in O'Caml. Well, that's probably fair. But when you consider  
that usually what you do is write your renderer in C or C++ and embed  
a scripting language for the actual game logic (something I know you  
folks at Naughty Dog know all too well, being famous for having a  
Lisp-derived scripting language whose compiler is written in Common  
Lisp), it stops seeming like much of a stretch to suggest that, with  
a little elbow grease, someone could take OCamlSDL and lablGL and  
write a quite respectable game for PCs and Macintoshes. Heck, the  
game logic could even be compiled to native code, although mods etc.  
would have to be bytecode-compiled in order to be dynamically  
loadable. It'd probably still be worth it, and faster in the end than  
titles developed with an embedded Lua interpreter or even the Unreal  
technology and UnrealScript, which Tim Sweeney concedes is anywhere  
from about 10x-20x out, performance-wise, from his C++.

In any case, your claim about O'Caml's thread support is odd, since  
O'Caml supports both pthreads and cooperative threading. But I don't  
know what your requirements are, so it's hard to say much more than  
that.

> So in the end, ... ocaml is nice as a tool, but it is by far
> not usable for the game console world. So, I guess we'll stick
> with C++ for a while...
>
Yes, if in the console world you're stuck writing your own renderers,  
this much is probably true. Maybe someday the consoles will give us  
OpenGL and OpenAL and the conclusion will likely change.

> Thanks,
>
> PKE.
> -- 
>   _
>   \`.       Pål-Kristian Engstad, Lead Programmer,
>    \ `|     Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
>   __\ |`.   Santa Monica, CA 90404, USA. (310) 633-9112.
>     /  /o   mailto:engstad@naughtydog.com http://www.naughtydog.com
>    /  '~    mailto:mrengstad@yahoo.com    http://www.engstad.com
>   / ,'      Hang-gliding Rulez!
>   ~'
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Best regards,
Paul Snively

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Darwin)

iEYEARECAAYFAkLoIN0ACgkQO3fYpochAqLw3ACeJRkss1ZwUUg6he54OdrxUjf+
M6oAoMEXuPAlobZpLtNlFPSctTjl5NvE
=l0tU
-----END PGP SIGNATURE-----

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 5845 bytes --]

On Wed, 2005-07-27 at 14:13 -0700, Pal-Kristian Engstad wrote:
> On Wednesday 27 July 2005 10:21 am, skaller wrote:
> > Just an aside-- but this is why
> > most games are utter crap. The developers have no idea
> > how to develop high level code, so they focus on weenie
> > details of graphics, and as a result we have stunning
> > high performance motion interfacing to the most banal
> > rubbish I have ever seen. As time goes by things just
> > seem to get worse.
> 
> Hi,
> 
> Skaller, that's one of the most sweeping generalizations I
> have ever seen.

hehe .. 

>  Exactly what kind of games are you talking
> about? 

My experience is with PC based games, not console.
Consoles are obviously limited by storage constraints.

> The gaming industry is big - I believe the latest 
> numbers indicate that we're bigger than the movie industry 
> w.r.t to earnings.

Yup, I think 4'th largest industry in Japan one year.

> I've been looking into O'Caml, and I've written some tools
> in it (caml is great for tools), but here's a couple of points 
> against it:
> 
> 1. It doesn't support console platforms.
> 	- The PC market is quite minor compared to consoles.

That is the fault of marketing idiots. The PC market
is in fact far larger and worth lots of money,
especially the adult market.

However, this is only evident where by luck someone
produced a good game for adults. One of my friends
works with Trainz, for example. It is basically owns
the world market for train enthusiasts, having killed
Microsofts offering.. and I can tell you train people
are all mad, rich, and there are a heck of a lot of
them -- hows that for another sweeping generalisation? :)

Some of these people spend $50-100 per week on this
single game .. that's a LOT of money. And the game
isn't going to die next week, like some fad game
for 14 year olds... it will keep developing
and growing for a long time.

> 2. It doesn't support low-level constructs.
> 	- No SIMD (AltiVec/VMX) vector operations.
> 	- No explicit assignment of (bit and byte) offsets 
> 	  within a record.
> 	- No explicit alignment specification.
> 	- No inline assembly.

It isn't necessary for higher level parts of a PC based game.
For a console, yes, you'd need lots of low level stuff,
but I have no interest in arcade games, which is about
all you can do on a standalone console.

That may change with unwired online networking, where
a lot of the engine runs on a remote server -- this
is happening with phones now so it may not be long
before online consoles (if not just your phone) are
the way to go: in this case most of the game
is running on a large server.

> 3. There is no controlled real-time GC. 
> 	- GC needs to run between frames, 
> 	  and only for a controlled amount of time.

That is open to debate. Ocaml uses an incremental
generational and very fast collector. I have played
plenty of games where the framerate varied, and the
game even froze up a bit sometimes, so it is not clear
that a bit of sloppiness won't be tolerated.

It also isn't clear manual memory management can
do any better. If you limit what you're doing 
for a console to a finite state machine, then
of course you don't really need ANY memory management.

As soon as you go to a more advanced game model,
you're going to need to split the video generator
thread off from the rest of the system anyhow:
the generator can provide a constant frame-rate
by running at a higher priority.

Fact is that most PC games I have played the programmers
didn't have the faintest idea how to get good frame rates,
in fact they couldn't even get double buffering to
work properly -- 2/3 games the mouse cursor is incorrectly
handled (and also on some Gnome/Linux apps too, it is done wrong).


> 4. There is no real support for unboxed data-types.
> 	- This one is actually very important for consoles.

There is some support, but not as much as you'd get from
C, C++ or my language Felix (which is designed for games
and uses C/C++ object model including unboxed types).

> For game-code (AI, behaviors, etc.), it is better suited, 
> though the GC issue is there. But it doesn't support much 
> of threading - be it through pthreads or cooperatively - 
> which renders it unusable to us. 

This isn't really correct. Ocaml certainly DOES support
pthreads, it just doesn't allow for multi-processing.

The bytecode interpreter actually DOES do cooperative
multi-tasking, using the same interface as the pthreads
in fact -- its pretty cool.

And of course you can design your own technique for
cooperation, although programming it can be painful:
the required control inversion is done automatically
by Felix.

> So in the end, ... ocaml is nice as a tool, but it is by far 
> not usable for the game console world.

Yup, if you have a small box with limited store, and you need
to spend a lot of time playing with the hardware, then
Ocaml may not be ideal -- you could look at Felix instead
(it is a C++ code generator, so it can be used WITH your
existing codes).

however for larger games, eg RPG or Strategy class PC games,
you aren't tweaking the hardware anyhow: you'll have an
underlying abstraction like DirectX or OpenGl to work with
instead. On that class of platform, Ocaml would be quite
competitive IMHO.

Again, if you have a need to interface with C/C++ have
a look at Felix -- it provides lots of higher level stuff
like first class functions, pattern matching, high performance
user space threading, and other things, while retaining
C/C++ compatibility (to see how you'll need to look: the
language syntax isn't compatible, but the system is
source compatible .. :)

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[Pal-Kristian Engstad]

On Wednesday 27 July 2005 10:21 am, skaller wrote:
> Just an aside-- but this is why
> most games are utter crap. The developers have no idea
> how to develop high level code, so they focus on weenie
> details of graphics, and as a result we have stunning
> high performance motion interfacing to the most banal
> rubbish I have ever seen. As time goes by things just
> seem to get worse.

Hi,

Skaller, that's one of the most sweeping generalizations I
have ever seen. Exactly what kind of games are you talking
about? The gaming industry is big - I believe the latest 
numbers indicate that we're bigger than the movie industry 
w.r.t to earnings.

I've been looking into O'Caml, and I've written some tools
in it (caml is great for tools), but here's a couple of points 
against it:

1. It doesn't support console platforms.
	- The PC market is quite minor compared to consoles.
2. It doesn't support low-level constructs.
	- No SIMD (AltiVec/VMX) vector operations.
	- No explicit assignment of (bit and byte) offsets 
	  within a record.
	- No explicit alignment specification.
	- No inline assembly.
3. There is no controlled real-time GC. 
	- GC needs to run between frames, 
	  and only for a controlled amount of time.
4. There is no real support for unboxed data-types.
	- This one is actually very important for consoles.

For game-code (AI, behaviors, etc.), it is better suited, 
though the GC issue is there. But it doesn't support much 
of threading - be it through pthreads or cooperatively - 
which renders it unusable to us. 

So in the end, ... ocaml is nice as a tool, but it is by far 
not usable for the game console world. So, I guess we'll stick 
with C++ for a while...

Thanks,

PKE.
-- 
  _       
  \`.       Pål-Kristian Engstad, Lead Programmer,
   \ `|     Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
  __\ |`.   Santa Monica, CA 90404, USA. (310) 633-9112. 
    /  /o   mailto:engstad@naughtydog.com http://www.naughtydog.com
   /  '~    mailto:mrengstad@yahoo.com    http://www.engstad.com
  / ,'      Hang-gliding Rulez!
  ~'

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 1386 bytes --]

On Wed, 2005-07-27 at 08:35 -0700, David Thomas wrote:
> I'm still curious what numerical algorithm is so
> desperately in need of variable length arrays...

I think I was not clear. Normally Ocaml boxes
contain either an int or a heap pointer
to a data object. So a floating point value
is represented by a pointer.

Doing numerical programming with an array
of pointers to floats instead of an
array of floats has a performance impact,
so Ocaml now provides arrays of unboxed floats.

I wasn't referring to the need for variable length arrays
in numerical code, but the need to circumvent boxing
in numerical code for arrays of numerical values:
this is considered significant enough to warrant
specialised compiler optimisations and data structures.

The point being, arrays of boxes are considered inefficient,
and in some cases it is already considered significant
enough for considerable work to be done to fix it.

So arguing an extra indirection required for the
array of option solution to variable length arrays
is insignificant is contrary to the evidence that
INRIA already accepts it can be inefficient.

Again, this is not to say variable length arrays
without this extra overhead should be provided,
just that the argument that the overhead is not
significant is suspect.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 1415 bytes --]

On Wed, 2005-07-27 at 16:29 +0100, Jon Harrop wrote:
> On Wednesday 27 July 2005 16:05, skaller wrote:
> > Given that there is a simple requirement for a simple
> > efficient data structure (analogous to C++ STL Vector)
> > but it needs magic to do properly, the varray is best
> > supplied by INRIA magicians.
> 
> At what cost?

I am not the one to judge that. There is a 'working'
implementation in Extlib, I imagine Xavier could
knock one up in a day .. ah no, given the kinds
of things the Ocaml teams do at the Functional
Programming Contest in a week .. nah, he could
knock one up in one hour. 

There are also costs in maintaining it, and I'm sure 
INRIA teams has other things to do too. It seems to
me to be a small cost. But only INRIA can make
that judgement (and they have .. they're not 
supporting it)

All I can say is that if Xavier keeps condemning
people for sticking dirty syringes in their arms,
he should allow he's partly responsible for
not providing a clean one.. if people are going
to use imperative programming style they're going
to want a suitable set of basic data structures
to use to build others.

You can argue the imperative style isn't the best,
but it is provided and supported in Ocaml, Ocaml
even has Objects, so clearly it is expected
people WILL do imperative programming.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 369 bytes --]

On Tue, 2005-07-26 at 02:22 +0100, Jon Harrop wrote:
> On Monday 25 July 2005 12:35, skaller wrote:
> > The language requirements with respect to initialisation
> > are the difference: Ocaml requires all store to be
> > initialised, C/C++ does not.
> 
> String.create

Except for strings .. :)

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 831 bytes --]

On Tue, 2005-07-26 at 04:34 +0300, Jere Sanisalo wrote:

> It's just that I know that I'm missing some crucial learning points about
> designing software in FP manner. And games *are* close to the HW, usually.

Just an aside-- but this is why
most games are utter crap. The developers have no idea
how to develop high level code, so they focus on weenie
details of graphics, and as a result we have stunning
high performance motion interfacing to the most banal
rubbish I have ever seen. As time goes by things just
seem to get worse.

I sure hope using Ocaml can help to fix this problem,
and allow the real game programmers to focus
on game design -- the way they did in the days
of Zork when all that pretty embellishment just
wasn't possible.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 3354 bytes --]

On Mon, 2005-07-25 at 20:20 -0500, Brian Hurt wrote:

> No- variable length arrays are needed when you're implementing other data 
> structures on top of arrays, like stacks or queues.  At which point I 
> start asking which data structure you really need- a variable length 
> array, or a stack or queue?

I need to represent what is naturally a graph of some kind:
I have a Hashtable mapping function number to code,
where the code is a list of instructions (including labels
and branches to them). The main
kind of optimisation is inlining function calls.

I am not currently using any sophisticated analysis,
although I would like to: in part this is because
the data structure I'm using isn't very good.

There is a tension between a good data structure
in the abstract (for example a graph) and one which
is good in Ocaml -- Ocaml can work with inductive
data structures like lists well because of pattern
matching, but abstract data structures are much
harder to use.

The main problem is that rewriting rules are intrinsically
mutations, which makes caching very hard. I do some of this
and it is a mess if I forget to update a cache.

An entirely functional approach is likely to be absurdly
inefficient: you simply cannot recalculate the properties
of the code after a rewrite rule is applied from
scratch every time.

What my code actually does is optimise special cases
found by pattern matching -- and other algorithms
try to coerce the code into this form. For example:


	fun f (x:int):int = {
		y := f (x - 1);
		return y
	|

This representation of a function does not contain
a direct tail call. However by subtitution of y
we can reduce the code to:

	return f (x - 1);

which is in tail form, and can be recognized by a
pattern match as a tail call. Additional logic determines
the call is a self call, so the function is rewritten as:

	fun f(x:int):int = {
		var a = x;
	loop:>
	 	a' := a - 1;
		a = a';
		goto loop;
	}

and a bit more work eliminates a' (this is entirely
non-trivial when the parameter is a tuple, recall
previous discussion of parallel assignment).

The point is that processing this requires three or four 
distinct processes: the substitution is justified by a limited
kind of linear data flow analysis which is enough to handle
unpacking an expression in to SSA form, the tail-call is
done with a single pattern match, and the tail-recursion
is handled by a check and a transformation that needs
to know the current function name, and also needs to 
modify the code at the start of the function.  In addition
you don't want to do that twice if there are TWO 
self-tail-rec calls.

Whilst there is no particular guarantee of closure
elimination, in common cases the process does seem
to generate efficient code -- testing on Ackermann's
function shows the result is faster than any other
language translator including both Ocamlopt and gcc,
probably because one less word is required on the
machine stack.

In addition, I doubt there is any single best
theory of optimisation with guarantees, at least
in 2005 :)

So given my explanation of the kinds of things
I'm doing I'd be interested to learn what kind
of data structure you think I should be using.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 693 bytes --]

On Tue, 2005-07-26 at 02:05 +0100, Jon Harrop wrote:

> How can that be a problem given that you (basically) cannot guarantee 
> collection anyway?

This is an important point because it is hard to answer
properly. I would say "I basically trust the Ocaml 
system to do a good job if it is allowed to". The problem
with an arbitrary dummy value being kept around just to
fool the Ocaml type system is that it seems to me it may
interfere with the requirement that it "be allowed to"
do a good job.

The problem in a varray implementation using this
technique is that it is hidden from the client 
programmer.


-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 1180 bytes --]

On Mon, 2005-07-25 at 20:10 -0500, Brian Hurt wrote:
> 
> Note that languages encourage or discourage certain styles of programming. 
> For example, C++, and to a lesser extent Java and C#, rather strongly 
> discourages an applicative style of programming- primarily due to the 
> costs of allocation.  You can do it, but it's going to be a fairly serious 
> perfomance hit.  

I agree with your assertion but not the reason you cite for it.
The real reason it is discouraged is the lack of lexical 
scoping.

I cite Felix as a counter example: the current implementation
provides lexical scoping and functional programming in the
ML style is simple and easy. Yet the stack frames are indeed
allocated using malloc in the standard driver.

For some classes of problems, the lack of performance here
just isn't an issue -- especially as the optimiser eliminates
almost all closures. 

[The real problem in Felix is the the collector cannot
be run inside functional code, because there is no way
to predict the structure of the machine stack: procedural
code doesn't use the machine stack]

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[David Thomas]

I'm still curious what numerical algorithm is so
desperately in need of variable length arrays...

--- Jon Harrop <jon@ffconsultancy.com> wrote:

> On Wednesday 27 July 2005 16:05, skaller wrote:
> > Given that there is a simple requirement for a
> simple
> > efficient data structure (analogous to C++ STL
> Vector)
> > but it needs magic to do properly, the varray is
> best
> > supplied by INRIA magicians.
> 
> At what cost?
> 
> -- 
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.
> Objective CAML for Scientists
>
http://www.ffconsultancy.com/products/ocaml_for_scientists
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
>
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 



		
____________________________________________________
Start your day with Yahoo! - make it your home page 
http://www.yahoo.com/r/hs 
 

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 837 bytes --]

On Mon, 2005-07-25 at 18:01 -0700, Stephane Glondu wrote:

> But skaller already argued that he didn't like this approach.

I'm not arguing "I don't like this approach". I already know
of several ways to do variable length arrays, you haven't
shown me anything new: it seems you're simply not accepting
my assertion: it isn't possible to do it efficiently
in Ocaml without magic: either Obj.magic or C code with
an Ocaml interface: both solutions are fragile and
require secret knowledge of ocaml implementation.

Thus, to safely use variable length arrays they
have to be provided by INRIA. That doesn't imply
they *should* be provided by INRIA of course.
I can always use a different data structure,
ignore safety, or use another programming language.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[Jon Harrop]

On Wednesday 27 July 2005 16:05, skaller wrote:
> Given that there is a simple requirement for a simple
> efficient data structure (analogous to C++ STL Vector)
> but it needs magic to do properly, the varray is best
> supplied by INRIA magicians.

At what cost?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 1214 bytes --]

On Mon, 2005-07-25 at 19:47 -0500, Brian Hurt wrote:
> 
> On Mon, 25 Jul 2005, skaller wrote:
> > On Sun, 2005-07-24 at 23:45 -0700, Stephane Glondu wrote:
> >
> > Well, basically the real topic is how to implement variable
> > length arrays. This is easy enough in C and C++: why should
> > it be very hard or even impossible in Ocaml?
> 
> It is, in fact, neither- *IF* you don't mind a little bit of inefficiency.

But I do. There is already an indirection due to boxing,
however that cost isn't always paid (for example reversing
the elements of an array doesn't require examining them)
and it is a fundamental property of Ocaml: 
nevertheless even this inefficiency cannot be tolerated
in numerical programs, and there are officially supported
special optimisations and array types to solve that problem.

> It's insisting that it be done without options that's tricky.

It isn't tricky, it just requires use of Obj.magic.

Given that there is a simple requirement for a simple
efficient data structure (analogous to C++ STL Vector)
but it needs magic to do properly, the varray is best
supplied by INRIA magicians.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[David Thomas]

> As a side note, whenever I or anyone else starts
> bitching about how something is easy to do in C but 
> hard to do in Ocaml, that's a sign that I'm
> approaching the problem wrong. 

Well, Brian, you're clearly approaching the problem
wrong, because other people are bitching about how
stuff is easy in C and hard in Ocaml.

(I'm sorry, that interpretation was too much fun to
not remark on... ^_^)

Anyway, I agree with the sentiment. 

If you're having trouble doing something efficiently
in Ocaml that would be "so easy" in C, the procedure
is simple:

(1) See if you can think of another way.
(2) Implement it inefficiently
(3) If the inefficiency turns out to be significant:
(3a) See if you can think of another way.
(3b) Bitch.

If you haven't done 1-3a, then as far as I'm concerned
you don't have a problem.

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Re: [Caml-list] How to do this properly with OCaml?

[Richard Jones]

On Tue, Jul 26, 2005 at 04:34:44AM +0300, Jere Sanisalo wrote:
> It's just that I know that I'm missing some crucial learning points about
> designing software in FP manner. And games *are* close to the HW, usually.
> Not always, but sometimes. And some gameplay tweaks are near the tweaks HW
> drivers do (perhaps because it's not researched enough, perhaps? this is the
> thing I want to know).

Have a look at http://merjis.com/developers/ocamlode in particular,
the tarball which contains a "game" (I use quotes because the game is
quite rubbish).  The game is implemented with a pure functional style.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Caml-list] How to do this properly with OCaml?

[Alex Baretta]

skaller wrote:
> On Mon, 2005-07-25 at 10:21 -0700, Ken Rose wrote:
> 
>>skaller wrote:
>>
>>>I would appreciate an officially supported variable 
>>>length array a lot: it can't be efficiently implemented 
>>>*without* Obj.magic. 
>>
>>I must be missing something obvious.  What's wrong with map?
> 
> 
> It is not efficient, it is very
> clumsy to use because it is an ocaml functor,
> and it is not imperative.
> 
> I actually use Hashtables a lot, rather than Maps,
> simply because the type variables are instantiated
> automatically.

There is a beautiful parametrically polymorphic map module, largely
based on map.ml, lying around the net somewhere. Let me see if I can
find the reference...

***

Why, obviously it's int the Extlib!

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] How to do this properly with OCaml?

[Jere Sanisalo]

On Mon, Jul 25, 2005 at 08:10:29PM -0500, Brian Hurt wrote:
>>Depends on the task.. What if it was a hardware driver?
>Hardware drivers are specialized tasks.  One thing that drives me crazy is 
>the assumption that a language needs to be able to do everything, and if 
>it can't, it can't do anything.

Well I was hardly saying that now was I? In my line of work (games) you
often need to cross the borders a bit in order to accomplish what you want.
I'm a bit late in these discussions and I just started to feel like I was
throwing gas on the fire. I'm sorry about that, and I will refrain further
from this discussion (after this message).

It's just that I know that I'm missing some crucial learning points about
designing software in FP manner. And games *are* close to the HW, usually.
Not always, but sometimes. And some gameplay tweaks are near the tweaks HW
drivers do (perhaps because it's not researched enough, perhaps? this is the
thing I want to know).

>The point is that instead of bitching about how hard it is to implement 
>the other language's solution in this language, to instead be thinking 
>about the correct solution to implement in this language.

And this is indeed the thing I want to know.. But before, I was just saying,
that in general, a languages "usefulness" is usually measured by the things
it can do. And by that, people rarely consider the language. Actually what
they consider is the API and the libraries. Just one pellet of fuel to the
fire, I guess.. :)

But just to recap, I really really want to stop programming my games in C++.
I have been looking for a way out for years. I have found one possibility
for tools; .NET/C#. Not quite the ideal, but F# helps in some respects and
the API is quite nice for tools. But I find many gaming problems to be
easier to solve in FP manner, but some of their relatives tie to the
hardware and low level way of thinking. If I'm small minded now, that's ok.
I'm not saying I'm right.

I just want to learn ;D.

But that's it for me now.. I'll keep my eye on this thread, though..

And sorry again..

-- 
Jere Sanisalo [xm@xmunkki.org] - http://www.xmunkki.org/

Re: [Caml-list] How to do this properly with OCaml?

[Jon Harrop]

On Monday 25 July 2005 18:21, Ken Rose wrote:
> skaller wrote:
> > I would appreciate an officially supported variable
> > length array a lot: it can't be efficiently implemented
> > *without* Obj.magic.
>
> I must be missing something obvious.  What's wrong with map?

Map is several times slower (e.g. for 10^3 elements). There are timings of 
many important operations on various data structures in the optimisation 
chapter of my OCaml book.

Map is also not quite an extensible array because you'd have to handle the 
lookup values yourself. Does anyone have links to tree-based functional array 
implementations in OCaml?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] How to do this properly with OCaml?

[Jon Harrop]

On Tuesday 26 July 2005 02:20, Brian Hurt wrote:
> On Tue, 26 Jul 2005, Jon Harrop wrote:
> > I came from a C++/STL background and was accustomed to using extensible
> > arrays. Having tweaking my perception of suitable data structures to be
> > more appropriate when coding in OCaml, I now prefer the idea of a faster
> > run-time and no extensible arrays. I've never actually needed them
> > (except inside Hashtbl).
>
> Actually, they aren't needed in hashtbl either...

Ooops, yes. I thought Hashtbl used Obj but you're quite right - I was thinking 
of Queue.

> No- variable length arrays are needed when you're implementing other data
> structures on top of arrays, like stacks or queues.  At which point I
> start asking which data structure you really need- a variable length
> array, or a stack or queue?

I've never used Queue so I guess I'm not even using Obj indirectly...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] How to do this properly with OCaml?

[Jon Harrop]

On Monday 25 July 2005 12:35, skaller wrote:
> The language requirements with respect to initialisation
> are the difference: Ocaml requires all store to be
> initialised, C/C++ does not.

String.create

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] How to do this properly with OCaml?

[Brian Hurt]

On Tue, 26 Jul 2005, Jon Harrop wrote:

> I came from a C++/STL background and was accustomed to using extensible
> arrays. Having tweaking my perception of suitable data structures to be more
> appropriate when coding in OCaml, I now prefer the idea of a faster run-time
> and no extensible arrays. I've never actually needed them (except inside
> Hashtbl).

Actually, they aren't needed in hashtbl either.  If you're resizing the 
array, you need to go through and rehash all the elements anyways, as many 
will need to be moved.  So you might as well copy them into a new array 
while you're at it.  And since you need to deal with hash collisions 
anyways, the easiest way is to make the underlying type really a 'a list 
array, which gives you an obvious empty element- the empty list.

No- variable length arrays are needed when you're implementing other data 
structures on top of arrays, like stacks or queues.  At which point I 
start asking which data structure you really need- a variable length 
array, or a stack or queue?

Brian

Re: [Caml-list] How to do this properly with OCaml?

[Brian Hurt]

On Mon, 25 Jul 2005, Stephane Glondu wrote:

> Brian Hurt wrote:
>> let get arr idx =
>>     if (idx < 0) || (idx > arr.len) then
>>        invalid_arg "get_arr"
>>     else
>>        arr.data.(idx)
>> ;;
>
> Maybe:
>
> let get arr idx =
>    if (idx < 0) || (idx > arr.len) then
>       invalid_arg "get_arr"
>    else
>       match arr.data.(idx) with None -> assert false | Some a -> a
> ;;
>
> would be better...

Duh!  Yeah- thinko there.  That's what I meant.

> Maybe storing the arr.data's length in the record would be better...

Not really.  Array.length is a pretty efficient routine- it gets inline to 
a mov, shift, and mask IIRC.

> But skaller already argued that he didn't like this approach.

Yep.  His argument is "It's impossible to implement cleanly, except for 
the obvious solution, which I hate."  OK, so it's not very efficient for 
integers.  Hey, why stop there?  If it's an array of chars or bools, using 
whole words to store individual members is inefficient!  We should only 
store the bytes or individual bits.  For anything much larger than ints, 
this actually isn't that inefficient.

Brian

Re: [Caml-list] How to do this properly with OCaml?

[Brian Hurt]

On Tue, 26 Jul 2005, Jere Sanisalo wrote:

> On Mon, Jul 25, 2005 at 07:47:16PM -0500, Brian Hurt wrote:
>>> The language requirements with respect to initialisation
>>> are the difference: Ocaml requires all store to be
>>> initialised, C/C++ does not.
>> Yep.  The following C code is really hard to implement in Ocaml:
>>    char * ptr = (char *) 0xA00000ul;
>>    ptr[315] = 'a';
>> I consider this an advantage of Ocaml over C/C++.
>
> Depends on the task.. What if it was a hardware driver?

Hardware drivers are specialized tasks.  One thing that drives me crazy is 
the assumption that a language needs to be able to do everything, and if 
it can't, it can't do anything.

> More so, it's not
> the language, it's the things you can do with it, coupled with the APIs
> possible and already present. I know I'm already favoring .NET as a general
> platform for API tools in the gaming world. The games still need to be fast,
> so C++ for them for now, but C# (and others) solve the tool problem quite
> nicely. And the .NET library is not the least of the reasons; it's easy to
> do so.

Note that languages encourage or discourage certain styles of programming. 
For example, C++, and to a lesser extent Java and C#, rather strongly 
discourages an applicative style of programming- primarily due to the 
costs of allocation.  You can do it, but it's going to be a fairly serious 
perfomance hit.  Ocaml, on the other hand, discourages an imperitive style 
of programming.  There's no performance hit, but there are some type 
issues and library support.

The point is that instead of bitching about how hard it is to implement 
the other language's solution in this language, to instead be thinking 
about the correct solution to implement in this language.

Brian

Re: [Caml-list] How to do this properly with OCaml?

[Jon Harrop]

On Monday 25 July 2005 01:32, skaller wrote:
> On Sun, 2005-07-24 at 16:23 -0700, Stephane Glondu wrote:
> > On Sunday 24 July 2005 14:55, skaller wrote:
> > > If you have to initialise the store, it is expensive,
> >
> > I understand your point now. However, if you want your array to hold
> > allocated values, you will always have to initialise the array.
>
> Not if the collector is modified by INRIA to support variable
> length arrays: this is some kind of tagged block with
> a mutable length count which limits how far along the block
> the collector looks for boxes: the length count is less
> than or equal to the actual number of allocated slots.

As I recall, the last time we discussed this, Damien said that altering the 
run-time to allow variable-length arrays would slow the run-time down for all 
other code and would be likely to introduce bugs.

I came from a C++/STL background and was accustomed to using extensible 
arrays. Having tweaking my perception of suitable data structures to be more 
appropriate when coding in OCaml, I now prefer the idea of a faster run-time 
and no extensible arrays. I've never actually needed them (except inside 
Hashtbl).

> > Moreover,
> > I think the overhead of this initialisation is insignificant compared to
> > the GC overhead.
>
> I am not so sure: to initialise an array causes a store
> in each slot, which forces the whole array to scroll
> through your cache: if the array is big this means
> disk paging/swapping activity.

You could RLE the uninitialised elements to recover memmap capability.

> ...
> However that turned what in C is a trivial set of
> library functions into a complex unreliable mess
> and left me wondering whether the encoding was
> properly transparent.

I'd just go for the simplest approach, at least to start with.

> > I didn't mean to change the dummy value all the time! Just take the first
> > value as the dummy value, and keep it even if the first entry in the
> > array changes. This will work fine for small values.
>
> But if you do that you have a reference to an object
> that the client does not know about. So the client
> will be confused if the object isn't finalised,
> and that in turn could cause many other objects
> to remain alive unexpectedly.

How can that be a problem given that you (basically) cannot guarantee 
collection anyway?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Technical Presentation Software
http://www.ffconsultancy.com/products/presenta

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

Brian Hurt wrote:
> let get arr idx =
>     if (idx < 0) || (idx > arr.len) then
>        invalid_arg "get_arr"
>     else
>        arr.data.(idx)
> ;;

Maybe:

let get arr idx =
    if (idx < 0) || (idx > arr.len) then
       invalid_arg "get_arr"
    else
       match arr.data.(idx) with None -> assert false | Some a -> a
;;

would be better...

> let append arr x = (* add x to the end of arr *)
>     if (arr.len == (Array.length arr.data)) then
>         begin
>             let newarr = Array.make (2*arr.len) None in
>             Array.blit arr.data 0 newarr 0 arr.len;
>             arr.data <- newarr;
>         end;
>     arr.data.(arr.len) <- Some(x);
>     arr.len <- arr.len + 1;
>     ()
> ;;

Maybe storing the arr.data's length in the record would be better...

Of course, all this would be wrapped in a module so that 'a t is an
abstract type.

But skaller already argued that he didn't like this approach.


-- 

Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[Jere Sanisalo]

On Mon, Jul 25, 2005 at 07:47:16PM -0500, Brian Hurt wrote:
>>The language requirements with respect to initialisation
>>are the difference: Ocaml requires all store to be
>>initialised, C/C++ does not.
>Yep.  The following C code is really hard to implement in Ocaml:
>    char * ptr = (char *) 0xA00000ul;
>    ptr[315] = 'a';
>I consider this an advantage of Ocaml over C/C++.

Depends on the task.. What if it was a hardware driver? More so, it's not
the language, it's the things you can do with it, coupled with the APIs
possible and already present. I know I'm already favoring .NET as a general
platform for API tools in the gaming world. The games still need to be fast,
so C++ for them for now, but C# (and others) solve the tool problem quite
nicely. And the .NET library is not the least of the reasons; it's easy to
do so.

-- 
Jere Sanisalo [xm@xmunkki.org] - http://www.xmunkki.org/

Re: [Caml-list] How to do this properly with OCaml?

[Brian Hurt]

On Mon, 25 Jul 2005, skaller wrote:

> On Sun, 2005-07-24 at 23:45 -0700, Stephane Glondu wrote:
>
>> It would surely be interesting. But now, we have moved from "using
>> Obj.magic for better efficiency" to "modifying to collector"...
>
> Well, basically the real topic is how to implement variable
> length arrays. This is easy enough in C and C++: why should
> it be very hard or even impossible in Ocaml?

It is, in fact, neither- *IF* you don't mind a little bit of inefficiency.

For example:

type 'a t = {
     mutable len: int;
     mutable data: 'a option array;
};;

let make init_size =
     let init_size = if init_size <= 0 then 16 else init_size in
     { len = 0; data = Array.make init_size None }
;;

let get arr idx =
     if (idx < 0) || (idx > arr.len) then
        invalid_arg "get_arr"
     else
        arr.data.(idx)
;;

let append arr x = (* add x to the end of arr *)
     if (arr.len == (Array.length arr.data)) then
         begin
             let newarr = Array.make (2*arr.len) None in
             Array.blit arr.data 0 newarr 0 arr.len;
             arr.data <- newarr;
         end;
     arr.data.(arr.len) <- Some(x);
     arr.len <- arr.len + 1;
     ()
;;

It's insisting that it be done without options that's tricky.

As a side note, whenever I or anyone else starts bitching about how 
something is easy to do in C but hard to do in Ocaml, that's a sign that 
I'm approaching the problem wrong.  Most likely, you need some sort of 
deque or other data structure.

> The language requirements with respect to initialisation
> are the difference: Ocaml requires all store to be
> initialised, C/C++ does not.

Yep.  The following C code is really hard to implement in Ocaml:
     char * ptr = (char *) 0xA00000ul;
     ptr[315] = 'a';

I consider this an advantage of Ocaml over C/C++.

Brian

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 799 bytes --]

On Mon, 2005-07-25 at 10:21 -0700, Ken Rose wrote:
> skaller wrote:
> > 
> > I would appreciate an officially supported variable 
> > length array a lot: it can't be efficiently implemented 
> > *without* Obj.magic. 
> 
> I must be missing something obvious.  What's wrong with map?

It is not efficient, it is very
clumsy to use because it is an ocaml functor,
and it is not imperative.

I actually use Hashtables a lot, rather than Maps,
simply because the type variables are instantiated
automatically.

In any case, the point is that each data structure
has different properties and I would like a choice.
Don't say 'roll your own then' because the point
is that I can't: Ocaml won't let me (without magic:)

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[Ken Rose]

skaller wrote:
> 
> I would appreciate an officially supported variable 
> length array a lot: it can't be efficiently implemented 
> *without* Obj.magic. 

I must be missing something obvious.  What's wrong with map?

  - ken

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 1239 bytes --]

On Sun, 2005-07-24 at 23:45 -0700, Stephane Glondu wrote:

> It would surely be interesting. But now, we have moved from "using 
> Obj.magic for better efficiency" to "modifying to collector"...

Well, basically the real topic is how to implement variable
length arrays. This is easy enough in C and C++: why should
it be very hard or even impossible in Ocaml?

> > However that turned what in C is a trivial set of
> > library functions into a complex unreliable mess
> > and left me wondering whether the encoding was
> > properly transparent.
> 
> I agree that strongly-typedness makes things more intricate sometimes, but 
> it will not make me prefer C... :-)

I agree, but C++ has stronger array typing than Ocaml,
so this is the wrong place to make such an argument :)

The language requirements with respect to initialisation
are the difference: Ocaml requires all store to be
initialised, C/C++ does not. 

> BTW, for some purposes can also use another datatype such as a Map or a 
> Set. They do not involve such problems, are quite efficient, and more 
> enjoyable than in C...

Yes sometimes: I just don't like not having a choice.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

On Sunday 24 July 2005 17:32, skaller wrote:
> Not if the collector is modified by INRIA to support variable
> length arrays: this is some kind of tagged block with
> a mutable length count which limits how far along the block
> the collector looks for boxes: the length count is less
> than or equal to the actual number of allocated slots.

It would surely be interesting. But now, we have moved from "using 
Obj.magic for better efficiency" to "modifying to collector"...

> I am not so sure: to initialise an array causes a store
> in each slot, which forces the whole array to scroll
> through your cache: if the array is big this means
> disk paging/swapping activity.
>
> Why do all that when the values will never be read?
> We do not even know in advance how much of the
> array will actually be used. Consider an array
> of length 10,000 elements, where only 100 are used.
> We allocate space for 10,000 because we're conservative
> and want the program to run on many sized data sets.

I was just saying that the GC will go through all your array anyway, even 
if you use only the first 100 elements (as far as I understood).

> BTW: this is a *real* issue an Ocaml user had.

I agree.

> Think of a class type, whose constructor function itself
> takes other class values as arguments .. it can be quite
> complicated to set up such values, and, worse,
> Ocaml being imperative doing so may have side-effects.

You can make a dummy class object with dummy methods without using your 
class definition (class typing is done only with the set of methods). 
However, I agree this is not satisfactory.

> However that turned what in C is a trivial set of
> library functions into a complex unreliable mess
> and left me wondering whether the encoding was
> properly transparent.

I agree that strongly-typedness makes things more intricate sometimes, but 
it will not make me prefer C... :-)

> Not just huge values: values that contain references
> to other values .. such as in a graph .. occupy
> a lot of memory.

That is what I mean by huge values.


BTW, for some purposes can also use another datatype such as a Map or a 
Set. They do not involve such problems, are quite efficient, and more 
enjoyable than in C...


-- 
Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 4464 bytes --]

On Sun, 2005-07-24 at 16:23 -0700, Stephane Glondu wrote:
> On Sunday 24 July 2005 14:55, skaller wrote:
> > If you have to initialise the store, it is expensive,
> 
> I understand your point now. However, if you want your array to hold 
> allocated values, you will always have to initialise the array. 

Not if the collector is modified by INRIA to support variable
length arrays: this is some kind of tagged block with
a mutable length count which limits how far along the block
the collector looks for boxes: the length count is less
than or equal to the actual number of allocated slots.

> Moreover, 
> I think the overhead of this initialisation is insignificant compared to 
> the GC overhead.

I am not so sure: to initialise an array causes a store
in each slot, which forces the whole array to scroll
through your cache: if the array is big this means
disk paging/swapping activity.

Why do all that when the values will never be read?
We do not even know in advance how much of the
array will actually be used. Consider an array
of length 10,000 elements, where only 100 are used.
We allocate space for 10,000 because we're conservative
and want the program to run on many sized data sets.

BTW: this is a *real* issue an Ocaml user had.

Ok, so my argument is flawed as follows: the whole
point of a variable length array is to keep the size
of the array roughly the size of the data it actually
holds: when extending, we're already initialising
the new array with data from the old one, and the
overhead initialising the rest is only going
to double the time taken.. unless you happen
to hit a cache size boundary, when it could
take 10-100 times longer than necessary.

So -- you could indeed be correct, but it isn't
entirely clear that gratuitous writes are not
going to impact performance.


> > and if you have to provide a dummy value it is hard
> > to use.
> 
> Maybe hard is not the appropriate word. I would just say annoying. You can 
> always define easily a dummy value when you define a (non-empty) type.

Think of a class type, whose constructor function itself 
takes other class values as arguments .. it can be quite 
complicated to set up such values, and, worse, 
Ocaml being imperative doing so may have side-effects.

This isn't far fetched at all -- it happened to me :)

That is why I implemented a variable length array,
to get around this obstacle. I used the 'one element
is taken as a dummy value' technique (no Obj.magic!).

However that turned what in C is a trivial set of
library functions into a complex unreliable mess
and left me wondering whether the encoding was
properly transparent.

> I didn't mean to change the dummy value all the time! Just take the first 
> value as the dummy value, and keep it even if the first entry in the array 
> changes. This will work fine for small values. 

But if you do that you have a reference to an object
that the client does not know about. So the client
will be confused if the object isn't finalised,
and that in turn could cause many other objects
to remain alive unexpectedly. Even if there are
no side-effects on finalisation, the extra memory
use could be a problem.

> If you are planning to put 
> huge values in the array,

Not just huge values: values that contain references
to other values .. such as in a graph .. occupy
a lot of memory. Much of that data structure may be
shared, but we normally expect unreferenced parts
of the graph to die, and release memory.

> > That won't happen in Buffer because you can't modify it,
> > but it must be allowed in more general variable length
> > mutable array.
> 
> What do you mean?

The current implementation makes buffers extensible
but immutable. However, for a general variable length
array you would like to not only modify elements,
but insert and delete as well.

Without this additional requirement, using the
'first' element as a dummy value would work fine:
that is, you are correct 'a array option idea
for Buffer would be make efficient elimination
of the 'dummy value' requirement possible (although
not eliminating the need to initialise the array).

But for a true variable length array, and without
gratuitously hanging on to an unused value,
you'd need each store to the first element to
also store in every unused slot.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[Brian Hurt]

On Mon, 25 Jul 2005, skaller wrote:

> On Sun, 2005-07-24 at 12:14 -0700, Stephane Glondu wrote:
>> On Sunday 24 July 2005 11:48, skaller wrote:
>>>> I strongly disagree. Look at source code of buffer.ml: no Obj.magic.
>>>> What do you mean by "efficiently"?
>>>
>>> Buffer only works for characters.
>>
>> You can make it work for any datatype by using an 'a array option instead
>> of a string.
>
> That fails to be 'efficient'. Would you use
>
> char array option
>
> instead of the existing Buffer???

The problem is that there is no one perfect structure.  bool array is 
incredibly inefficient- it's much better to use a bitfield.  Etc.

As for having a dynamic (resizable) array as a standard library, I think 
I disagree with this idea.  A standard applicative tree-based array, 
maybe.  But a dynamic array, like a mutable doubly linked list, encourages 
imperitive programming- when I think imperitive programming should be 
*discouraged*.  There are reasons, and time, when imperitive programming 
is necessary.  But I think they are few and far between- much rarer than 
people suppose.  But imperitive semantics impose implicit coupling- when 
you pass a mutable data structure to a subroutine there is an implicit 
contract between the caller and callee- either to modify in a known way or 
to not modify the value at all.  This increases coupling and leads to 
maintainance problems.

Brian

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

On Sunday 24 July 2005 14:55, skaller wrote:
> If you have to initialise the store, it is expensive,

I understand your point now. However, if you want your array to hold 
allocated values, you will always have to initialise the array. Moreover, 
I think the overhead of this initialisation is insignificant compared to 
the GC overhead.

> and if you have to provide a dummy value it is hard
> to use.

Maybe hard is not the appropriate word. I would just say annoying. You can 
always define easily a dummy value when you define a (non-empty) type. One 
may argue that you may need to compute a path in a type dependency
graph, but it is far-fetched: the path is given by the type definition!

> then you can use the first value of the array as
> the dummy value for the rest of the array, and avoid
> Obj.magic -- however this is very inefficient, since
> the dummy would have to be changed in many places
> whenever the first entry in the array changed

I didn't mean to change the dummy value all the time! Just take the first 
value as the dummy value, and keep it even if the first entry in the array 
changes. This will work fine for small values. If you are planning to put 
huge values in the array, I really think that the overhead of using an 'a 
option array is insignificant compared to the GC overhead.

> (and that isn't just a store -- there is a write-barrier
> to think about .. :)
>
> That won't happen in Buffer because you can't modify it,
> but it must be allowed in more general variable length
> mutable array.

What do you mean?

-- 
Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 1615 bytes --]

On Sun, 2005-07-24 at 14:08 -0700, Stephane Glondu wrote:

> BTW, I was talking about 'a array option, not 'a option array. You can use 
> (mostly of) the implementation of Buffer, hence have the same 
> efficiency... I don't understand your point about "efficiency". If you 
> think that the Buffer implementation is not efficient, I may agree with 
> you, but this is an algorithmic issue, not a typing issue. 

Observe the constructor:

let create n =
 let n = if n < 1 then 1 else n in
 let n = if n > Sys.max_string_length then Sys.max_string_length else n
in
 let s = String.create n in
 {buffer = s; position = 0; length = n; initial_buffer = s}

creates an *uninitialised* string of length n:

"val create : int -> string
String.create n returns a fresh string of length n. The string initially
contains arbitrary characters."

If you have to initialise the store, it is expensive,
and if you have to provide a dummy value it is hard
to use.

If you used a 'a array option, and 

assert (match Some a -> Array.length a > 0 | None -> true)

then you can use the first value of the array as
the dummy value for the rest of the array, and avoid
Obj.magic -- however this is very inefficient, since
the dummy would have to be changed in many places
whenever the first entry in the array changed
(and that isn't just a store -- there is a write-barrier
to think about .. :)

That won't happen in Buffer because you can't modify it,
but it must be allowed in more general variable length
mutable array.


-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

On Sunday 24 July 2005 13:49, skaller wrote:
> > > You can make it work for any datatype by using an 'a array option
> > > instead of a string.
> >
> > That fails to be 'efficient'. Would you use
> >
> > char array option
> >
> > instead of the existing Buffer???
>
> Woops, of course I meant 'char option array' :)

Your question is the same as "Would you use a char array instead of a 
string"? My answer is no. But string can only store chars...

BTW, I was talking about 'a array option, not 'a option array. You can use 
(mostly of) the implementation of Buffer, hence have the same 
efficiency... I don't understand your point about "efficiency". If you 
think that the Buffer implementation is not efficient, I may agree with 
you, but this is an algorithmic issue, not a typing issue. It has nothing 
to do with Obj.magic. Are you thinking about a specific implementation 
that you cannot do in O'Caml because of typing? If yes, tell us so we can 
help you get rid of Obj.magic if possible.


-- 
Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 670 bytes --]

On Mon, 2005-07-25 at 06:29 +1000, skaller wrote:
> On Sun, 2005-07-24 at 12:14 -0700, Stephane Glondu wrote:
> > On Sunday 24 July 2005 11:48, skaller wrote:
> > > > I strongly disagree. Look at source code of buffer.ml: no Obj.magic.
> > > > What do you mean by "efficiently"?
> > >
> > > Buffer only works for characters.
> > 
> > You can make it work for any datatype by using an 'a array option instead 
> > of a string.
> 
> That fails to be 'efficient'. Would you use
> 
> char array option
> 
> instead of the existing Buffer???

Woops, of course I meant 'char option array' :)

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 538 bytes --]

On Sun, 2005-07-24 at 12:14 -0700, Stephane Glondu wrote:
> On Sunday 24 July 2005 11:48, skaller wrote:
> > > I strongly disagree. Look at source code of buffer.ml: no Obj.magic.
> > > What do you mean by "efficiently"?
> >
> > Buffer only works for characters.
> 
> You can make it work for any datatype by using an 'a array option instead 
> of a string.

That fails to be 'efficient'. Would you use

char array option

instead of the existing Buffer???

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

On Sunday 24 July 2005 11:48, skaller wrote:
> > I strongly disagree. Look at source code of buffer.ml: no Obj.magic.
> > What do you mean by "efficiently"?
>
> Buffer only works for characters.

You can make it work for any datatype by using an 'a array option instead 
of a string.

-- 
Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 514 bytes --]

On Sun, 2005-07-24 at 11:13 -0700, Stephane Glondu wrote:
> On Sunday 24 July 2005 10:33, skaller wrote:
> > I would appreciate an officially supported variable
> > length array a lot:
> 
> It would be interesting indeed...
> 
> > it can't be efficiently implemented *without* Obj.magic.
> 
> I strongly disagree. Look at source code of buffer.ml: no Obj.magic. What 
> do you mean by "efficiently"?

Buffer only works for characters.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

On Sunday 24 July 2005 10:33, skaller wrote:
> I would appreciate an officially supported variable
> length array a lot:

It would be interesting indeed...

> it can't be efficiently implemented *without* Obj.magic.

I strongly disagree. Look at source code of buffer.ml: no Obj.magic. What 
do you mean by "efficiently"?


Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[skaller]

[-- Attachment #1: Type: text/plain, Size: 903 bytes --]

On Sat, 2005-07-23 at 14:34 +0200, Xavier Leroy wrote:

> In other terms:
> 
> " I was walking in the city the other day.  I saw a syringe lying on
>   the sidewalk.  I stuck the needle in my forearm.  That was a classy
>   neighborhood, so the use of the syringe seemed justified. "
> 
> Sorry for being sarcastic, but I strongly feel that any suggestion
> to use Obj functions should be avoided on this list. 

> Coming back to the initial question, I would first warn against
> premature optimization: quite possibly the overhead of the "option"
> solution is negligible.  If not, just ask the user to pass an initial
> value of the heap element type to the "create heap" function.

I would appreciate an officially supported variable 
length array a lot: it can't be efficiently implemented 
*without* Obj.magic. 

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] How to do this properly with OCaml?

[Berke Durak]

On Sat, Jul 23, 2005 at 08:50:04PM +0200, Matthieu Sozeau wrote:
> 
> Le 23 juil. 05 à 20:27, Berke Durak a écrit :
> >I mean that there could be a built-in, type-safe Ocaml function  
> >that would
> >yield a valid, yet arbitrary value of any type.
> 
> Find an inhabitant of `type t` (the empty type).

Good point.  That settles it.
-- 
Berke Durak

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

On Saturday 23 July 2005 12:59, Thomas Fischbacher wrote:
> I think that this will not work.
>
> If I duplicate entries to fill up holes, and later on remove a
> legitimate entry whose duplicates fill holes from the heap, I have to
> introduce extra bookkeeping so that the other placeholder copies of that
> entry are replaced as well - otherwise it could not be reclaimed by GC.

Oh, you are right, I didn't think about it... However, my first idea was to 
use always the same value to fill the holes (e.g. the first one given), so 
that you keep only this one allocated. Still, it won't be a good deal if 
your first value uses a lot of memory...


Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[james woodyatt]

On 23 Jul 2005, at 13:15, Brian Hurt wrote:
> On Sat, 23 Jul 2005, Thomas Fischbacher wrote:
>>
>> If I duplicate entries to fill up holes, and later on remove a  
>> legitimate entry whose duplicates fill holes from the heap, I have  
>> to introduce extra bookkeeping so that the other placeholder  
>> copies of that entry are replaced as well - otherwise it could not  
>> be reclaimed by GC.
>
> I'd be very inclined just to use options- especially since, as  
> you've mentioned in other posts, the elements you're putting into  
> the heap are are fairly large and expensive to create.  In this  
> case, the overhead of options is small, relative to the rest of the  
> data.

If they're large and expensive to create, I'd consider using ['a  
Lazy.t array] instead of ['a array].  When you initialize the array,  
do it like this:

     let initArray n = Array.init n (fun _ -> lazy (assert false))



-- 
j h woodyatt <jhw@wetware.com>
markets are only free to the people who own them.

Re: [Caml-list] How to do this properly with OCaml?

[Brian Hurt]

On Sat, 23 Jul 2005, Thomas Fischbacher wrote:

> If I duplicate entries to fill up holes, and later on remove a
> legitimate entry whose duplicates fill holes from the heap, I have to
> introduce extra bookkeeping so that the other placeholder copies of that
> entry are replaced as well - otherwise it could not be reclaimed by GC.

I'd be very inclined just to use options- especially since, as you've 
mentioned in other posts, the elements you're putting into the heap are 
are fairly large and expensive to create.  In this case, the overhead of 
options is small, relative to the rest of the data.

Brian

Re: [Caml-list] How to do this properly with OCaml?

[Thomas Fischbacher]

On Sat, 23 Jul 2005, Stephane Glondu wrote:

> > What if I have operations that add and remove elements on the heap in
> > random order (so that the heap sometimes has to shrink), and I want
> > (1) that every element which was removed from the heap and is otherwise
> > inaccessible can be reclaimed by GC,
> 
> When you want to "remove" an element, you can put another (random) value 
> from the same array at its place so that it can be garbage collected. If 
> the remaining heap is empty (i.e. there is no other value to pick), you 
> replace the Fill a with Empty n.

I think that this will not work.

If I duplicate entries to fill up holes, and later on remove a
legitimate entry whose duplicates fill holes from the heap, I have to 
introduce extra bookkeeping so that the other placeholder copies of that 
entry are replaced as well - otherwise it could not be reclaimed by GC.

> > and (2) that removing a single  
> > element from the heap does not require copying the underlying Array?
> 
> This is a matter of algorithmics, isn't it?

To some extent, it is a matter of the type system getting in the way of 
algorithmics, I fear.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

On Saturday 23 July 2005 12:35, Thomas Fischbacher wrote:
> This seems to be equivalent to the idea of using an array option, which
> I mentioned earlier.

Indeed.

> Problems:
>
> What if I have operations that add and remove elements on the heap in
> random order (so that the heap sometimes has to shrink), and I want
> (1) that every element which was removed from the heap and is otherwise
> inaccessible can be reclaimed by GC,

When you want to "remove" an element, you can put another (random) value 
from the same array at its place so that it can be garbage collected. If 
the remaining heap is empty (i.e. there is no other value to pick), you 
replace the Fill a with Empty n.

> and (2) that removing a single  
> element from the heap does not require copying the underlying Array?

This is a matter of algorithmics, isn't it?


Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[Thomas Fischbacher]

On Sat, 23 Jul 2005, Stephane Glondu wrote:

> On Saturday 23 July 2005 11:27, Berke Durak wrote:
> > That was my point.  You could cleanly initialize your heap with that
> > "any" value.
> 
> I was thinking about sth you could adjust to your purpose:
> 
> module type HEAP = sig
>   type 'a t
>   val create : int -> 'a t
>   val set : 'a t -> int -> 'a -> unit
>   val get : 'a t -> int -> 'a
> end
> 
> module Heap : HEAP = struct
>   type 'a cell = Fill of 'a array | Empty of int
>   type 'a t = 'a cell ref
> 
>   let create n = ref (Empty n)
> 
>   let set h i e = match !h with
>       Empty n -> h := Fill (Array.create n e)
>     | Fill a -> a.(i) <- e
> 
>   let get h n = match !h with
>       Empty _ -> raise Not_found
>     | Fill a -> a.(n)
> end
> 
> No Obj.magic here. Does this suit you?

This seems to be equivalent to the idea of using an array option, which I 
mentioned earlier.

Problems:

What if I have operations that add and remove elements on the heap in 
random order (so that the heap sometimes has to shrink), and I want 
(1) that every element which was removed from the heap and is otherwise 
inaccessible can be reclaimed by GC, and (2) that removing a single 
element from the heap does not require copying the underlying Array?

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] How to do this properly with OCaml?

[Thomas Fischbacher]

On Sat, 23 Jul 2005, Xavier Leroy wrote:

> For instance, the following implementation of "magic" arrays will
> eventually cause the GC to crash:
> 
> type 'a t = int array
> let get (a: 'a t) i = (Obj.magic a.(i) : 'a)
> let set (a: 'a t) i (x: 'a) = a.(i) <- (Obj.magic x : int)
> 
> while the same code with "string" instead of "int" will not.  You
> don't understand why?  Then, don't use Obj.magic.

Could this be for precisely the same reason why I used Obj.magic (1,2) 
where Michael suggested using Obj.magic 0? I suppose Obj.magic () 
also would not work, right?

> Coming back to the initial question, I would first warn against
> premature optimization:

I do not think this is premature optimization in that particular case. The 
code I am talking about is quite mature and performed very well for years 
in its Lisp incarnation - I am just right now transliterating it to 
OCaml, as I need it there.

Another low-level question: it seems to me as if it were a piece of cake 
to build a C-linkable shared object library that in all respects looks 
like any old C .so library, but internally uses code that was compiled 
from OCaml.

However, in order to get there, I had to ar x libcamlrun.a and 
ld a new libcamlbytecode.so shared object from the pieces. It may well be 
that I just missed something in the documentation due to my own 
stupidity/ignorance, but so far it seems to me as if this were 
tremendously useful, but somehow not documented very well.

Anyway, as I clearly do appreciate the option to build C shared objects in 
something better than C, I wonder whether I can rely on being able to do 
that trick with future versions of the OCaml compiler as well.

> quite possibly the overhead of the "option" solution is negligible.

For a lot of applications this is indeed right. However, for the 
particular one I have in mind right now, I am more or less competing
with C code, so I am indeed a bit worried about that extra indirection.

> If not, just ask the user to pass an initial
> value of the heap element type to the "create heap" function.

Well, that's also not that beautiful, but at least, it would work.

But coming back to:

> while the same code with "string" instead of "int" will not.

Can I take this as a guarantee that will also hold for later versions of 
the compiler? Just for my particular private application - not that I 
would advise or teach anyone to use such a technique, or distribute any 
code in compiled or source form that makes use of it.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

On Saturday 23 July 2005 11:27, Berke Durak wrote:
> That was my point.  You could cleanly initialize your heap with that
> "any" value.

I was thinking about sth you could adjust to your purpose:

module type HEAP = sig
  type 'a t
  val create : int -> 'a t
  val set : 'a t -> int -> 'a -> unit
  val get : 'a t -> int -> 'a
end

module Heap : HEAP = struct
  type 'a cell = Fill of 'a array | Empty of int
  type 'a t = 'a cell ref

  let create n = ref (Empty n)

  let set h i e = match !h with
      Empty n -> h := Fill (Array.create n e)
    | Fill a -> a.(i) <- e

  let get h n = match !h with
      Empty _ -> raise Not_found
    | Fill a -> a.(n)
end

No Obj.magic here. Does this suit you?


Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[Thomas Fischbacher]

On Sat, 23 Jul 2005, Michael Alexander Hamburg wrote:

> I was constructing a binary heap of tuples the other day.  After pondering
> these options, I just used Obj.magic 0 as the null value in the array.
> The heap was in a module, so nothing else could see the array, and I could
> prove that the code never accessed the null elements, so the use of
> Obj.magic seemed justified.

Big question is, of course, what does the GC think about this, and will 
the GC's view on such a hack change in future versions of ocaml?

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] How to do this properly with OCaml?

[Matthieu Sozeau]

Le 23 juil. 05 à 20:27, Berke Durak a écrit :

> On Sat, Jul 23, 2005 at 09:36:47AM -0700, Stephane Glondu wrote:
>
>> On Saturday 23 July 2005 06:16, Berke Durak wrote:
>>
>>> However I was wondering how feasible it would be to have a "any :  
>>> 'a"
>>> value, that would return an (unspecified) value of any given type...
>>>
>>
>> That seems to be dirty and would surely beak type safety.
>>
>>
>>> This is clearly feasible for base types.
>>> possible for tuples, records and functions of base types.
>>>
>>
>> What do you mean?
>>
>
> I mean that there could be a built-in, type-safe Ocaml function  
> that would
> yield a valid, yet arbitrary value of any type.

Find an inhabitant of `type t` (the empty type).

-- mattam

Re: [Caml-list] How to do this properly with OCaml?

[Michael Alexander Hamburg]

Ouch.

I bow to your superior experience.

Is there a syntax which makes treatment of options easy?  That is, if
about every other line of my library is an action on objects from this
array, is there a convenient way to use options without cluttering up the
code?

I can't use your second solution, because the objects in the heap may be
difficult and expensive to construct, and may have side effects (for
example, in one instance they are handles to processes; in another they
are handles to Libevent events).

Mike

On Sat, 23 Jul 2005, Xavier Leroy wrote:

> > I was constructing a binary heap of tuples the other day.  After pondering
> > these options, I just used Obj.magic 0 as the null value in the array.
> > The heap was in a module, so nothing else could see the array, and I could
> > prove that the code never accessed the null elements, so the use of
> > Obj.magic seemed justified.
>
> In other terms:
>
> " I was walking in the city the other day.  I saw a syringe lying on
>   the sidewalk.  I stuck the needle in my forearm.  That was a classy
>   neighborhood, so the use of the syringe seemed justified. "
>
> Sorry for being sarcastic, but I strongly feel that any suggestion
> to use Obj functions should be avoided on this list.  The OCaml
> compiler performs some type-dependent optimizations that can result in
> incorrect code (w.r.t. GC invariants) if wrong types are given using
> Obj.magic.
>
> For instance, the following implementation of "magic" arrays will
> eventually cause the GC to crash:
>
> type 'a t = int array
> let get (a: 'a t) i = (Obj.magic a.(i) : 'a)
> let set (a: 'a t) i (x: 'a) = a.(i) <- (Obj.magic x : int)
>
> while the same code with "string" instead of "int" will not.  You
> don't understand why?  Then, don't use Obj.magic.
>
> A few years ago, I spent one full day debugging a mysterious crash
> in code provided by a user, then realized that the problem was exactly
> the use of Obj.magic outlined above.  I then swore to throw away all
> bug reports whose repro case uses Obj.  So, you can break the type
> system with Obj, but you get to keep the pieces afterwards.
>
> Coming back to the initial question, I would first warn against
> premature optimization: quite possibly the overhead of the "option"
> solution is negligible.  If not, just ask the user to pass an initial
> value of the heap element type to the "create heap" function.
>
> - Xavier Leroy
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] How to do this properly with OCaml?

[Berke Durak]

On Sat, Jul 23, 2005 at 09:36:47AM -0700, Stephane Glondu wrote:
> On Saturday 23 July 2005 06:16, Berke Durak wrote:
> > However I was wondering how feasible it would be to have a "any : 'a"
> > value, that would return an (unspecified) value of any given type...
> 
> That seems to be dirty and would surely beak type safety.
> 
> > This is clearly feasible for base types.
> > possible for tuples, records and functions of base types.
> 
> What do you mean?

I mean that there could be a built-in, type-safe Ocaml function that would
yield a valid, yet arbitrary value of any type.

> > Recursive values could prove problematic :
> >
> >   type stuff1 = { mutable a : stuff2 }
> >   and stuff2 = { mutable b : stuff1 }
> 
> What's the problem here? You can always define a dummy value of a given 
> type:
> 
> let rec dummy1 = { a = dummy2 } and dummy2 = { b = dummy1 }

Yes of course, but you may need to compute a path in a type dependency
graph.

> > Would it be worth the fuss ?
> 
> I think that a better design (which doesn't need such hacks) would be 
> worth.

That was my point.  You could cleanly initialize your heap with that "any"
value.
-- 
Berke Durak

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

On Saturday 23 July 2005 06:16, Berke Durak wrote:
> However I was wondering how feasible it would be to have a "any : 'a"
> value, that would return an (unspecified) value of any given type...

That seems to be dirty and would surely beak type safety.

> This is clearly feasible for base types.
> possible for tuples, records and functions of base types.

What do you mean?

> Recursive values could prove problematic :
>
>   type stuff1 = { mutable a : stuff2 }
>   and stuff2 = { mutable b : stuff1 }

What's the problem here? You can always define a dummy value of a given 
type:

let rec dummy1 = { a = dummy2 } and dummy2 = { b = dummy1 }

> Would it be worth the fuss ?

I think that a better design (which doesn't need such hacks) would be 
worth.


Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[Berke Durak]

On Sat, Jul 23, 2005 at 02:34:03PM +0200, Xavier Leroy wrote:
> > I was constructing a binary heap of tuples the other day.  After pondering
> > these options, I just used Obj.magic 0 as the null value in the array.
> > The heap was in a module, so nothing else could see the array, and I could
> > prove that the code never accessed the null elements, so the use of
> > Obj.magic seemed justified.
> 
> In other terms:
> 
> " I was walking in the city the other day.  I saw a syringe lying on
>   the sidewalk.  I stuck the needle in my forearm.  That was a classy
>   neighborhood, so the use of the syringe seemed justified. "

Quite a metaphor.

However I was wondering how feasible it would be to have a "any : 'a"
value, that would return an (unspecified) value of any given type...
This is clearly feasible for base types.  Hence it should also be possible
for tuples, records and functions of base types.  Recursive values could
prove problematic :

  type stuff1 = { mutable a : stuff2 }
  and stuff2 = { mutable b : stuff1 }
  
Would it be worth the fuss ?
-- 
Berke Durak

Re: [Caml-list] How to do this properly with OCaml?

[Xavier Leroy]

> I was constructing a binary heap of tuples the other day.  After pondering
> these options, I just used Obj.magic 0 as the null value in the array.
> The heap was in a module, so nothing else could see the array, and I could
> prove that the code never accessed the null elements, so the use of
> Obj.magic seemed justified.

In other terms:

" I was walking in the city the other day.  I saw a syringe lying on
  the sidewalk.  I stuck the needle in my forearm.  That was a classy
  neighborhood, so the use of the syringe seemed justified. "

Sorry for being sarcastic, but I strongly feel that any suggestion
to use Obj functions should be avoided on this list.  The OCaml
compiler performs some type-dependent optimizations that can result in
incorrect code (w.r.t. GC invariants) if wrong types are given using
Obj.magic.

For instance, the following implementation of "magic" arrays will
eventually cause the GC to crash:

type 'a t = int array
let get (a: 'a t) i = (Obj.magic a.(i) : 'a)
let set (a: 'a t) i (x: 'a) = a.(i) <- (Obj.magic x : int)

while the same code with "string" instead of "int" will not.  You
don't understand why?  Then, don't use Obj.magic.

A few years ago, I spent one full day debugging a mysterious crash
in code provided by a user, then realized that the problem was exactly
the use of Obj.magic outlined above.  I then swore to throw away all
bug reports whose repro case uses Obj.  So, you can break the type
system with Obj, but you get to keep the pieces afterwards.

Coming back to the initial question, I would first warn against
premature optimization: quite possibly the overhead of the "option"
solution is negligible.  If not, just ask the user to pass an initial
value of the heap element type to the "create heap" function.

- Xavier Leroy

Re: [Caml-list] How to do this properly with OCaml?

[Michael Alexander Hamburg]

I was constructing a binary heap of tuples the other day.  After pondering
these options, I just used Obj.magic 0 as the null value in the array.
The heap was in a module, so nothing else could see the array, and I could
prove that the code never accessed the null elements, so the use of
Obj.magic seemed justified.

Mike

On Fri, 22 Jul 2005, Thomas Fischbacher wrote:

>
> I repeatedly stumble across problems where I would like to use a
> programming style which seems quite out of line with how one is supposed
> to use OCaml (to say it otherwise, it looks outright wrong and
> horrendously ugly), but which nevertheless might be just appropriate for
> the situation in question. So, I would like to hear the opinion of the
> OCaml community about this.
>
> Imagine constructing a binary heap of tuples. It is somewhat neat to be
> able to just use an array to store the entries of the heap which is
> pre-allocated to some fixed size and replaced by a larger array whenever
> more space is needed. The only thing known about the heap's entries at
> compile time is that they are bound to be tuples, hence boxed objects,
> but nothing else is known about their size or even type.
>
> As one does not have a prototype of such a tuple at the time the array is
> created, it seems to me as if the best thing one could do in OCaml would
> be:
>
> (1) Make an array of <tuple> option and initially fill it with None.
>
> (2) Make an optional array of tuples which is None until the first entry
> is made.
>
> One drawback of approach (2) is that when we "remove" entries from the
> heap, the underlying array will keep unnecessary references to values
> which by chance might be quite big, and which we might want to be
> reclaimed by GC, so that's not too beautiful for a general-purpose
> application.
>
> The major drawback of (1), however, is that there is a further level of
> indirection for array entries, which means some unnecessary consing, as
> well as more work for the machine to get at a given entry.
>
> If I just define a function
>
> let whatever () = Obj.magic (1,2);
>
> then
>
> let a = Array.make 10 (whatever());;
>
> would give me more or less just what I want. An array of boxed things that
> I then would like to use as in:
>
> # let () = a.(2) <- (1,2,3,4) in a.(2);;
> - : int * int * int * int = (1, 2, 3, 4)
> # let () = a.(3) <- (5,8,2,1) in a.(2);;
> - : int * int * int * int = (1, 2, 3, 4)
> # a.(3);;
> - : int * int * int * int = (5, 8, 2, 1)
>
> Mind you - in this case, I will only assign int*int*int*int tuples to that
> array, or the result of the evaluation of whatever() when I want to kill
> an entry. Plus, I guarantee never to look at any entry that is set to
> whatever().
>
> In some other situation, I might be inclined to use the same code, but
> with string*bool instead of int*int*int*int. But again, I will promise
> never to put anything else but string*bool into the underlying array, and
> never look at entries which are not set properly. (Which, of course,
> includes never printing such an array at the toplevel unless it is fully
> occupied.)
>
> Please don't tell me that "well, OCaml is not Lisp, after all".
> This I already know. But is there no proper way to get around that
> (technically speaking) unnecessary extra level of indirection that is
> forced upon me due to static type checking?
>
> The very same problem appears in a different guise when one tries to write
> a function that flattens 'a array array -> 'a array. The best I could
> come up with here is:
>
> let join_arrays aa =
>   let len_total = Array.fold_left (fun sf a -> sf+Array.length a) 0 aa
>   and nr_arrays = Array.length aa
>   in
>   if len_total=0
>   then
>     if nr_arrays = 0 then [||] else aa.(0)
>       (* ^ Take a close look! *)
>   else
>     (* Here, we face the problem that we have to get some value
>        of the proper type to init the joined array with.
>      *)
>     let first_entry =
>       (let rec seek pos =
> 	let array_here = aa.(pos) in
> 	if Array.length array_here = 0
> 	then seek (pos+1)
> 	else array_here.(0)
> 	    (* This is guaranteed to terminate, as len_total>0! *)
>       in seek 0)
>     in
>     let result = Array.make len_total first_entry in
>     let transfer_to_result arr offset =
>       let nr = Array.length arr in
>       for i = 0 to nr-1 do result.(i+offset) <- arr.(i) done
>     in
>     let rec populate nr_array_now offset =
>       if nr_array_now = nr_arrays
>       then result
>       else
> 	let array_now = aa.(nr_array_now) in
> 	let () = transfer_to_result array_now offset in
> 	populate (1+nr_array_now) (offset+Array.length array_now)
>     in
>     populate 0 0
> ;;
>
> Of course, it is pretty awkward having to scan for the first element in
> the first nonempty array in an array of arrays, especially as that element
> really does not play a that special role.
>
> Could anyone please tell me how to do all this in a more appropriate way?
>
> --
> regards,               tf@cip.physik.uni-muenchen.de              (o_
>  Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
> (lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
> (if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] How to do this properly with OCaml?

[Stephane Glondu]

Hi,

Christophe Dehlinger wrote:
> I have my own array-related problem, so I'll plug it here :)
> A couple of times, I would have liked to build arrays of functions whose
> body uses the array itself, like:
> 
> #let rec foo = Array.init 5 (fun n () -> if n=0 then 0 else foo.(n/2) ())
> This kind of expression is not allowed as right-hand side of `let rec'
> 
> Why is this kind of construct forbidden ?

In general, you cannot define a recursive value as a result of a
computation which uses the being-defined value. Intuitively, I explain
it in that way: here, the second argument references sth which is
created by Array.init itself, so the compiler has to know the result of
the call before compiling the argument function, which is clearly
impossible.

You have to do sth like this:

let foo =
  let bar = Array.make 5 (fun () -> 0) in
  for n = 1 to 4 do
    bar.(n) <- (fun () -> bar.(n/2) ())
  done;
  bar;;

However, you can do this:

let rec foo = [| (fun () -> 0); (fun () -> foo.(0) ()) |];;

(here, the array is created by the compiler itself, so it knows its
location).

I hope this is clear.


Stephane Glondu.

Re: [Caml-list] How to do this properly with OCaml?

[brogoff]

On Fri, 22 Jul 2005, Berke Durak wrote:
> On Fri, Jul 22, 2005 at 04:26:55PM +0200, Thomas Fischbacher wrote:
> > As one does not have a prototype of such a tuple at the time the array is
> > created, it seems to me as if the best thing one could do in OCaml would
> > be:
> >
> > (1) Make an array of <tuple> option and initially fill it with None.
> >
> > (2) Make an optional array of tuples which is None until the first entry
> > is made.
>
> I'd suggest you provide a "zero" value for whatever type you want
> to put in your heap.

That's the solution I have used most often. There's usually some out-of-band
value in a computation that works as a zero.

I agree, it's a bit more of a pain in a statically typed language than in Lisp
or Scheme. Nothing to keep you awake at night though.

-- Brian

Re: [Caml-list] How to do this properly with OCaml?

[Michel Quercia]

Le Vendredi 22 Juillet 2005 16:26, Thomas Fischbacher a écrit :
> I repeatedly stumble across problems ...

> (2) Make an optional array of tuples which is None until the first entry
> is made.
>
> One drawback of approach (2) is that when we "remove" entries from the
> heap, the underlying array will keep unnecessary references to values
> which by chance might be quite big, and which we might want to be
> reclaimed by GC, so that's not too beautiful for a general-purpose
> application.

if you know which element of the heap will removed last, then you can 
overwrite any element to be removed with this one. Otherwise pick some 
element when building the heap and use it for removals.

> The very same problem appears in a different guise when one tries to write
> a function that flattens 'a array array -> 'a array.

Is the following code that ugly ?

let join_arrays aa =

  (* get total length and index of first non-empty array *)
  let l = ref 0 and i = ref 0 in
  for j = Array.length(aa) - 1 downto 0 do
    let lj = Array.length aa.(j) in
    if lj > 0 then begin l := !l + lj; i := j end
  done;

  (* now copy all arrays, ending with the first non empty *)
  if !l = 0 then [||] else begin
    let r = Array.make !l aa.(!i).(0) in
    for j = Array.length(aa) - 1 downto !i do
      let lj = Array.length aa.(j) in
      if lj > 0 then begin
        l := !l - lj;
        Array.blit aa.(j) 0 r !l lj
      end
    done;
    r
  end

-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://michel.quercia.free.fr (maths)
http://pauillac.inria.fr/~quercia (informatique)
mailto:michel.quercia@prepas.org

Re: [Caml-list] How to do this properly with OCaml?

[Berke Durak]

On Fri, Jul 22, 2005 at 04:26:55PM +0200, Thomas Fischbacher wrote:
> I repeatedly stumble across problems where I would like to use a 
> programming style which seems quite out of line with how one is supposed 
> to use OCaml (to say it otherwise, it looks outright wrong and 
> horrendously ugly), but which nevertheless might be just appropriate for 
> the situation in question. So, I would like to hear the opinion of the 
> OCaml community about this.
> 
> Imagine constructing a binary heap of tuples. It is somewhat neat to be 
> able to just use an array to store the entries of the heap which is 
> pre-allocated to some fixed size and replaced by a larger array whenever 
> more space is needed. The only thing known about the heap's entries at 
> compile time is that they are bound to be tuples, hence boxed objects,
> but nothing else is known about their size or even type.
> 
> As one does not have a prototype of such a tuple at the time the array is 
> created, it seems to me as if the best thing one could do in OCaml would 
> be:
> 
> (1) Make an array of <tuple> option and initially fill it with None.
> 
> (2) Make an optional array of tuples which is None until the first entry 
> is made.

I feel some psychorigidity here.  Maybe some
3-[2-[4-(6-fluoro-1,2-benzisoxazol-3-yl)-1-piperidinyl]ethyl]-6,7,8,9-
tetrahydro-2-methyl-4H-pyrido[1,2-a]pyrimidin-4-one can help ?  Just
joking.

I'd suggest you provide a "zero" value for whatever type you want
to put in your heap.  That "zero" value should have a small memory
footprint.  This value does not need to be distinct from possible values
for your heap, since the length information is required and sufficient for
knowing which entries of your array are empty.  You could package the whole
stuff into a modules.  Example :

modul type ELEMENTS =
  sig
    type t
    val zero : t
  end

module Heap(E : ELEMENTS) =
  sig
    type t = {
      a : E.t array;
      mutable n : int; (* count *)
    }

    let create () = { a = Array.make 256 E.zero ; n = 0 }

    etc.
  end
-- 
Berke Durak

Re: [Caml-list] How to do this properly with OCaml?

[Eric Cooper]

On Fri, Jul 22, 2005 at 04:26:55PM +0200, Thomas Fischbacher wrote:
> [...]
> The very same problem appears in a different guise when one tries to write 
> a function that flattens 'a array array -> 'a array. The best I could 
> come up with here is:
> [...] 
> Could anyone please tell me how to do all this in a more appropriate way?

let join_arrays aa = Array.concat (Array.to_list aa)

(although Array.concat in the standard library is basically equivalent
to your code)

-- 
Eric Cooper             e c c @ c m u . e d u