How to do this properly with OCaml?

How to do this properly with OCaml?

[Thomas Fischbacher]

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)

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

Re: [SPAM_PROBABLE] - [Caml-list] How to do this properly with OCaml? - Bayesian Filter detected spam

[Christophe Dehlinger]

Thomas Fischbacher wrote:

> 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?
>
Hi Thomas,

What you're trying to build looks a lot like Extlib's dynamic 
(resizable) arrays.
I gave their implementation a cursory look: it seems to rely heavily on 
the Obj module.
So I guess there probably is no clean and efficient way to do this.

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?
>
Here's imho a more elegant way to flatten arrays :

let flatten arar =
  let cur_length = ref (-1) in
  let ai = ref (-1) in
  let i = ref (-1) in
  let total_length = Array.fold_left (fun accu ar -> accu + 
(Array.length ar)) 0 arar in
  let initfun _ =
    incr i ;
    while !i >= !cur_length do
      incr ai ;
      cur_length := Array.length arar.(!ai) ;
      i := 0
    done ;
    arar.(!ai).(!i) in
  Array.init total_length initfun;;
val flatten : 'a array array -> 'a array = <fun>
# flatten [| [|1;2;3|]; [|4|]; [| |]; [|5; 6|] |] ;;
- : int array = [|1; 2; 3; 4; 5; 6|]

However, this is very different from the first problem, as
- you know at the time of creation of the array both its length and its 
contents
- its length will not change after its creation


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 ?

Cheers,
Christophe



__________________________

Ce message (et toutes ses pièces jointes éventuelles) est confidentiel et établi à l'intention exclusive de ses destinataires. Toute utilisation de ce message non conforme à sa destination, toute diffusion ou toute publication, totale ou partielle, est interdite, sauf autorisation expresse. L'IFP décline toute responsabilité au titre de ce message.

This message and any attachments (the message) are confidential and intended solely for the addressees. Any unauthorised use or dissemination is prohibited. IFP should not be liable for this message.

Visitez notre site Web / Visit our web site : http://www.ifp.fr
__________________________

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?

[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?

[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?

[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?

[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?

[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?

[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 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?

[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?

[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 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, 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?

[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:

> > 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?

[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?

[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?

[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?

[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: How to do this properly with OCaml?

[Bardur Arantsson]

Michael Alexander Hamburg wrote:
> 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?

Well, not sure if it's exactly what you're looking for, but ExtLib has 
an Option module which contains various convenience functions for 
working with option values. See

      http://ocaml-lib.sourceforge.net/doc/Option.html

Cheers,

-- 
Bardur Arantsson
<bardur@imada.sdu.dk>
<bardur@scientician.net>

In anticipation, John licked his own lips.
                         A. Lloyd, http://adamcadre.ac/lyttle.html

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

[Michael Alexander Hamburg]

Yes.  But if I wanted to link in Extlib, I would just use the dynamic arrays
that it offers.

I'd rather minimize the number of dependencies, and so far I haven't needed
anything from Extlib other than dynamic arrays and a few convenience functions
that are easily recreated.

I think I'll just use options, the heap code isn't that long.

Mike Hamburg

Quoting Bardur Arantsson <spam@scientician.net>:

> Michael Alexander Hamburg wrote:
> > 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?
>
> Well, not sure if it's exactly what you're looking for, but ExtLib has
> an Option module which contains various convenience functions for
> working with option values. See
>
>       http://ocaml-lib.sourceforge.net/doc/Option.html
>
> Cheers,
>
> --
> Bardur Arantsson
> <bardur@imada.sdu.dk>
> <bardur@scientician.net>
>
> In anticipation, John licked his own lips.
>                          A. Lloyd, http://adamcadre.ac/lyttle.html
>
> _______________________________________________
> 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?

[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] "Just say no!" campaign against Obj [was: How to do this properly with OCaml?]

[Alex Baretta]

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. "

Once upon a time I felt a desperate need for polymorphic recursion. At
that time the INRIA gang was selling a new ligth drug whose effects are
similar to polymorphic recursion. They called it "polymorphic records".
Polymorphic records do not give addiction--unlike polymorphic variants,
which are much more dangerous from this point of view--but when they are
used to attain that euphoric state of mind given by polymorphic
recursion, they must be injected in one's code with Obj.magic. Yes, i
picked up the syringe and used it. Yes, I got ill with type-unsafety,
but eventually careful medication made me recover. At the end, I must
say experiencing polymorphic recursion was well worth the pain that came
from using Obj.magic.

Notwithstanding my experience, I agree with Xavier that is the social
duty of us all to discourage the young generations to take Obj as a
means to escape the conventional type system imposed upon them by
society. We must convey the idea that the type system the elders have
perpetuated since the time of the professor Church is for their own
good! So, when confronted with Obj, guys, "Just say no!"

Yet, I believe we must make some allowance for the need for polymorphic
recursion. If the laws of the compiler allowed type annotations to
substitute type-inference alone--not type-checking--for the sake of
having type-safe polymorphic recursion, then, maybe, less young people
would be deceived into taking the road of Obj, which inevitably leads to
a segfault.

;)

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] "Just say no!" campaign against Obj

[james woodyatt]

On 24 Jul 2005, at 00:27, Alex Baretta wrote:
>
> At the end, I must say experiencing polymorphic recursion was well  
> worth the pain that came from using Obj.magic.

Well, you know what Timothy Leary said about teaching the young about  
drugs... the correct message to send is "Just Say Know."  I strongly  
believe this, so it was I was happy to see Xavier come out with: "For  
instance, the following implementation of 'magic' arrays will  
eventually cause the GC to crash: <elided>.  You don't understand  
why?  Then, don't use Obj.magic."

I have been known to use Obj.magic.  I understand that recursive  
modules are a new way to avoid some of the old uses for which I have  
put that construction.  Some day, I will reform my old code and make  
it safe for public review.  Still, I'm glad that Obj.magic is there  
and has the effect it does.  But I don't blame Xavier for wanting to  
ban its use in problem reports for the compiler team.


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

Re: [Caml-list] "Just say no!" campaign against Obj

[Stephane Glondu]

On Sunday 24 July 2005 00:27, Alex Baretta wrote:
> Once upon a time I felt a desperate need for polymorphic recursion. At
> that time the INRIA gang was selling a new ligth drug whose effects are
> similar to polymorphic recursion. They called it "polymorphic records".
> Polymorphic records do not give addiction--unlike polymorphic variants,
> which are much more dangerous from this point of view--but when they are
> used to attain that euphoric state of mind given by polymorphic
> recursion, they must be injected in one's code with Obj.magic. Yes, i
> picked up the syringe and used it. Yes, I got ill with type-unsafety,
> but eventually careful medication made me recover. At the end, I must
> say experiencing polymorphic recursion was well worth the pain that came
> from using Obj.magic.

Forgive my ignorance... I never heard of "polymorphic recursion" before. Is 
it exactly polymorphic records (in which case I don't understand where the 
name "polymorphic recursion" is from), or something else?

Thank you,


Stephane Glondu.

Re: [Caml-list] "Just say no!" campaign against Obj

[Alex Baretta]

Stephane Glondu wrote:
> On Sunday 24 July 2005 00:27, Alex Baretta wrote:
> 
> 
> Forgive my ignorance... I never heard of "polymorphic recursion" before. Is 
> it exactly polymorphic records (in which case I don't understand where the 
> name "polymorphic recursion" is from), or something else?

A function definition is monomorphic-recursive when all recusive calls
induce unifiable type constraints. With a few exceptions from the world
of polymorphic variants, this means that all recursive calls take
parameters of the same type.

Polymorphic recursion arises when a recursive function is defined on a
non-uniformly recursive data structure, such that the decomposition of
the datastructure at each recursive step produces one or more
sub-structures whose type is different from (non-unifiable with) with
that of the formal parameter.

Maybe the more theoretical gurus on the list will be able to clarify
this issue with some self-contained examples.

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] "Just say no!" campaign against Obj [was: How to do this properly with OCaml?]

[brogoff]

On Sun, 24 Jul 2005, Alex Baretta wrote:
> Once upon a time I felt a desperate need for polymorphic recursion. At
> that time the INRIA gang was selling a new ligth drug whose effects are
> similar to polymorphic recursion. They called it "polymorphic records".
> Polymorphic records do not give addiction--unlike polymorphic variants,
> which are much more dangerous from this point of view--but when they are
> used to attain that euphoric state of mind given by polymorphic
> recursion, they must be injected in one's code with Obj.magic. Yes, i
> picked up the syringe and used it. Yes, I got ill with type-unsafety,
> but eventually careful medication made me recover. At the end, I must
> say experiencing polymorphic recursion was well worth the pain that came
> from using Obj.magic.

I was able to use the higher order polymorphism of record fields to implement
polymorphic recursion, WITHOUT using Obj.magic. I posted that approach on the
list a long time ago, it was really the same trick as using polymorphic methods
to do the same. You can use that trick to implement the signatures in Okasaki's
book that use P.R. fairly easily. Why did you need Obj.magic?

Recursive modules provide a nicer approach, IMO, and explicit types even nicer.

> Notwithstanding my experience, I agree with Xavier that is the social
> duty of us all to discourage the young generations to take Obj as a
> means to escape the conventional type system imposed upon them by
> society.

My issues with the type system are rarely (if ever) made better by using
Obj.magic. GCaml and Alice (with it's packages) tackle the main issue,
which is type safe marshalling.

I agree that a more expressive type system would be nice, and I used Obj
too to get a set_cdr thing going (like in ExtLib) but if you need efficiency
that badly then I think it makes more sense to use C and extend OCaml that
way.

-- Brian

Re: [Caml-list] "Just say no!" campaign against Obj [was: How to do this properly with OCaml?]

[Alex Baretta]

brogoff wrote:
>
> I was able to use the higher order polymorphism of record fields to implement
> polymorphic recursion, WITHOUT using Obj.magic. I posted that approach on the
> list a long time ago, it was really the same trick as using polymorphic methods
> to do the same. You can use that trick to implement the signatures in Okasaki's
> book that use P.R. fairly easily. Why did you need Obj.magic?

I guess the reason is that I could not think of anything better. My
implementation of transaction calculus requiring polymorphic recursion
is of october 2003. I kind of remember a post from you on this issue,
but it must have appeared later.

> Recursive modules provide a nicer approach, IMO, and explicit types even nicer.

I'm not sure recursive modules had been released at that time. 3.06 it
was, IIRC; whereas, recursive modules appeared in 3.07, right?

> My issues with the type system are rarely (if ever) made better by using
> Obj.magic. GCaml and Alice (with it's packages) tackle the main issue,
> which is type safe marshalling.

We have two instances of Obj.magic and and about as many instances of
Marshal.from_xxx. Not once have we escaped the segfault awaiting behind
the bend...

> I agree that a more expressive type system would be nice, and I used Obj
> too to get a set_cdr thing going (like in ExtLib) but if you need efficiency
> that badly then I think it makes more sense to use C and extend OCaml that
> way.

Actually, it is never for efficiency. The type-unsafeties are either due
to marshalling--there's little we can do about it at present--to
polymorphic recursion--I'll look at your proposal based on recursive
modules--or the classic set_cdr thing in a heapsort implementation on lists.

Alex

> _______________________________________________
> 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
> 


-- 
*********************************************************************
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] "Just say no!" campaign against Obj [was: How to do this properly with OCaml?]

[brogoff]

On Mon, 25 Jul 2005, Alex Baretta wrote:
> Actually, it is never for efficiency. The type-unsafeties are either due
> to marshalling--there's little we can do about it at present

Yes, I've had the same issue. There are tricks you can do to make it a bit safer
but it really needs runtime checks.

> polymorphic recursion--I'll look at your proposal based on recursive
> modules

It's actually in Xavier's paper on the experimental recursive module extension
in the proposal linked off of his web site. Not my idea at all.

It happens to be prettier (by my aesthetics checker :) except for the need to
have a "val empty : unit -> t"  in the signature rather than a "val empty : t"
but maybe that's going to be fixed one day.

I'm rather hopeful about the module system extensions, apart from the extra way
yo get polymorphic recursion. Without recursive modules functorized libraries
are a lot less useful.

--or the classic set_cdr thing in a heapsort implementation on lists.

That's just going back to the old discussion on tail recursive map (and the
like) , and using set_cdr to safely implement tail recursion modulo cons.

-- Brian

Re: [Caml-list] "Just say no!" campaign against Obj [was: How to do this properly with OCaml?]

[Alex Baretta]

brogoff wrote:
> On Sun, 24 Jul 2005, Alex Baretta wrote: 
> 
> I was able to use the higher order polymorphism of record fields to implement
> polymorphic recursion, WITHOUT using Obj.magic. I posted that approach on the
> list a long time ago, it was really the same trick as using polymorphic methods
> to do the same. You can use that trick to implement the signatures in Okasaki's
> book that use P.R. fairly easily. Why did you need Obj.magic?

I had missed your post[1]. I just read it. The function dictionary
paradigm is probably what I'm missing to make the type-checker happy.
Thanks Brian!

Alex


[1]
http://caml.inria.fr/pub/ml-archives/caml-list/2002/08/9e1089a04ce714a0541373be008c3130.en.html


-- 
*********************************************************************
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?

[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?

[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: 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 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: 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?

[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?

[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: 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 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: 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?

[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: 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?

[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?

[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 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?

[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?

[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?

[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] Games

[Jon Harrop]

On Wednesday 27 July 2005 18:21, 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.

I would have put that much more elegantly but, basically, I agree.

> 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.

Never heard of Zork. Apparently you could get it on 8" discs. Have you seen 
Darwinia?

I have actually been thinking about writing an "OCaml for Games Programming" 
book. I think there is a lot of scope for interesting and unusual material in 
such a book and I think there are lots of possible examples which would 
demonstrate the power of OCaml for general purpose programming whilst also 
making wicked cool games. The downside is mainly the lack of state-of-the-art 
OpenGL bindings.

I think there is ample market for a games programming OCaml book but it would 
be difficult to sell it at a low enough price (again, I think it would really 
benefit from being full color). So I'm now thinking that it might be better 
suited to educational software rather than a book. Not least because 
on-screen 3D graphics would really help to explain things. When we finish it, 
Presenta should be ideal for this...

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

Re: [Caml-list] Games

[Jere Sanisalo]

On Wed, Jul 27, 2005 at 08:44:42PM +0100, Jon Harrop 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.
>I would have put that much more elegantly but, basically, I agree.

Humh, missed where this started, but.. :)

As a games developer I somewhat disagree. Sure there are people who do not
know how, but in my view (and experience) most of professional games
developers are pretty good at doing high level code. For the problems
described here I can see much easier explanations. Mostly having something
to do with extremely tight deadlines, producers/publishers not knowing what
they want and changing their mind all the time and the tight coupling to a
limited hardware.

On one game developer forum there was a poll on how people managed their
high level code. Many developers had actually written their own
preprocessors to C++ in order to get introspection and the like. Only one (I
know of) have written their own language; GOAL / Naughty Dog. And what I
gather, even GOAL is split into two parts. The macro language is a full
scheme and the game side is more like an imperative language in the lisp
syntax.

Most (if not all) game programmers I have talked to have actively pursued
more better ways to create their games and handle those increasingly
complicated event queues that happen there. It's not easy, I can tell you. I
tried to formulate a basic game in ocaml once and failed badly. It's mostly
because I'm not yet so experienced in FP style and need to learn to think
things differently.

(btw, one major reason for not using more FP-like languages in gamedev is
because the platforms are nowadays mostly not-PC and the compilers / trained
staff is hard to find)

>I have actually been thinking about writing an "OCaml for Games Programming" 
>book. I think there is a lot of scope for interesting and unusual material in 
>such a book and I think there are lots of possible examples which would 
>demonstrate the power of OCaml for general purpose programming whilst also 
>making wicked cool games. The downside is mainly the lack of state-of-the-art 
>OpenGL bindings.

I would love such a book! It would basically have to touch on every single
aspect of FP programming I do not yet know how to do. And it would probably
teach me to think more in FP way, since game programming is much closer to
my daily programming than algorithmic issues (those I can cleanly write in
FP. And I have even written a compiler; those are easy to think in FP
terms).

And I don't think you'd need state-of-the-art OpenGL bindings to write a
good book on the subject. The problem is in the high level, mostly. The low
level bindings are relatively straightforward to do.

A shameless plug; a game I've written for this years Assembly demo party:
http://fpb.xmunkki.org/
The reason I bring this is up is that is uses OpenGL. And all it need is
textured triangles with two different blending modes (normal alpha and
additive). And I've played many fun games with only flat shading :).

The general issue here (I think) is that most programmers are unfamiliar
with the FP style of thinking (about problems). That's why most of them
never even try, except by accident.

>I think there is ample market for a games programming OCaml book but it would 
>be difficult to sell it at a low enough price (again, I think it would really 
>benefit from being full color).

I'd be willing to pay about 80e for such a book.. But then again, it's a
book I've been looking for a long time.

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

Re: [Caml-list] Games

[Jon Harrop]

On Wednesday 27 July 2005 21:35, Jere Sanisalo wrote:
> Humh, missed where this started, but.. :)

Skaller flew off on a tangent because he was beaten by a low-level, 
bit-twiddling games programmer as a child. ;-)

> As a games developer I somewhat disagree. Sure there are people who do not
> know how, but in my view (and experience) most of professional games
> developers are pretty good at doing high level code.

I can see the definition of "high-level" causing a problem here. It is my 
belief (but I may well be wrong) that games programmers have a very different 
notion of "high-level" than, say, most of the other people on this list.

> For the problems 
> described here I can see much easier explanations. Mostly having something
> to do with extremely tight deadlines, producers/publishers not knowing what
> they want and changing their mind all the time and the tight coupling to a
> limited hardware.

Tight deadlines and closeness to hardware make sense. But if the specification 
keeps changing then I would say that a higher-level language would be more 
suitable. I know what you mean though...

> On one game developer forum there was a poll on how people managed their
> high level code. Many developers had actually written their own
> preprocessors to C++ in order to get introspection and the like. Only one
> (I know of) have written their own language; GOAL / Naughty Dog.

I suspect that a high proportion of the people on this list have written their 
own language, probably several languages. I think I've written three 
languages now (two interpreted, one JIT) and I'm just a physicist dabbling in 
OCaml. ;-)

> And what I 
> gather, even GOAL is split into two parts. The macro language is a full
> scheme and the game side is more like an imperative language in the lisp
> syntax.

Again, I suspect (but may well be wrong) that a significant number of people 
here would not regard Lisp as very high level compared to ML.

> Most (if not all) game programmers I have talked to have actively pursued
> more better ways to create their games and handle those increasingly
> complicated event queues that happen there. It's not easy, I can tell you.
> I tried to formulate a basic game in ocaml once and failed badly. It's
> mostly because I'm not yet so experienced in FP style and need to learn to
> think things differently.

Ironically, game programmers probably already do lots of functional 
programming without even realising it.

> (btw, one major reason for not using more FP-like languages in gamedev is
> because the platforms are nowadays mostly not-PC and the compilers /
> trained staff is hard to find)

My guess is that there are far more PC game programmers than console 
programmers. Specifically, outside industry.

> >I have actually been thinking about writing an "OCaml for Games
> > Programming" book. I think there is a lot of scope for interesting and
> > unusual material in such a book and I think there are lots of possible
> > examples which would demonstrate the power of OCaml for general purpose
> > programming whilst also making wicked cool games. The downside is mainly
> > the lack of state-of-the-art OpenGL bindings.
>
> I would love such a book!

I'm not sure your 80e would justify another 4 months of my time but it's 
certainly interesting to hear. :-)

Would you be interested in educational software along these lines and, if so, 
for what platforms?

> It would basically have to touch on every single 
> aspect of FP programming I do not yet know how to do. And it would probably
> teach me to think more in FP way, since game programming is much closer to
> my daily programming than algorithmic issues (those I can cleanly write in
> FP.

Given that games programming has quite a few parallels with scientific 
programming, I think you will find my OCaml book instructive:

  http://www.ffconsultancy.com/products/ocaml_for_scientists

> And I have even written a compiler; those are easy to think in FP 
> terms).

There are many resources on interpreter and compiler writing, of course. 
However, I don't like most of them. I do like Appel's, Xavier's, Cardelli's, 
Peyton-Jones' and several others (I'm reading Torben Mogensen's) but I have 
yet to see a killer treatise on this, particularly because the current 
documents either assume too much knowledge for a passing outsider or because 
they are too vague about implementation details (e.g. Cardelli's papers on 
static typing and even Appel's ML book) for people who don't really know what 
they are doing. So compiler and interpreter writing is my other idea for a 
book... :-)

> And I don't think you'd need state-of-the-art OpenGL bindings to write a
> good book on the subject. The problem is in the high level, mostly. The low
> level bindings are relatively straightforward to do.

I agree with you up to the last sentence. I've tried to write low-level OCaml 
bindings to OpenGL and it is very difficult if you are a pedant like me and 
want to do it properly.

> A shameless plug; a game I've written for this years Assembly demo party:
> http://fpb.xmunkki.org/
> The reason I bring this is up is that is uses OpenGL. And all it need is
> textured triangles with two different blending modes (normal alpha and
> additive). And I've played many fun games with only flat shading :).

Absolutely. I think there is a considerable market here.

> The general issue here (I think) is that most programmers are unfamiliar
> with the FP style of thinking (about problems). That's why most of them
> never even try, except by accident.

I think there is also a mental barrier to the weird and wonderful world of FP 
for many game programmers (and similarly for scientists). However, most C++ 
programmers know that gratuitous use of const is good practice without 
noticing that it is purely functional programming and most C++ programmers 
would write vector/matrix computations in a purely functional style.

> >I think there is ample market for a games programming OCaml book but it
> > would be difficult to sell it at a low enough price (again, I think it
> > would really benefit from being full color).
>
> I'd be willing to pay about 80e for such a book.. But then again, it's a
> book I've been looking for a long time.

What you need is a consultant. :-)

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

Re: [Caml-list] Games

[Jere Sanisalo]

>Skaller flew off on a tangent because he was beaten by a low-level, 
>bit-twiddling games programmer as a child. ;-)

Hey, that's how I became a games programmer in the first place! :D

>I can see the definition of "high-level" causing a problem here. It is my 
>belief (but I may well be wrong) that games programmers have a very different 
>notion of "high-level" than, say, most of the other people on this list.

True.. That's the problem with all terms, I guess. It's hard for me to
relate how other people (especially scientific people) view it.. But just to
say what I think about, it's all about the structure. How to build a
framework where there can be several states, each of which is controlled by
a different set of rules (think about menu screens and then think about a
game area). The menus and the game are usually pretty related in terms of
functionality, but the game (if a modern game; following from skallers
outburst) has so many interactions it's hard to follow them. So the "high
level" becomes how to really make a structure where you can easily manage
your resources and define the wanted interactions between your game objects
(but handle the unwanted also).

It's hard to do that for even a simple game. Almost a highlevel problem, but
in my game I gave the URL to, I'd need to somehow detect and handle the
collision to objects. What really is a collision is the question. If an
object slightly hits the other for 5 physics updates, is that a collisision.
And ifit is, how to handle it. And so on.

>> For the problems 
>> described here I can see much easier explanations. Mostly having something
>> to do with extremely tight deadlines, producers/publishers not knowing what
>> they want and changing their mind all the time and the tight coupling to a
>> limited hardware.
>Tight deadlines and closeness to hardware make sense. But if the specification 
>keeps changing then I would say that a higher-level language would be more 
>suitable. I know what you mean though...

Yeah, well as I see it, the more the pros find the tools to get closer to
the FP style, the easier they have it. Not sure if it's FP or not, but one
intresting idea for handling the game object behaviour was that each object
was really just a "bag of data". And then there were many different
handlers. An object might be subscribed to one or more of these. One handler
might be "physics", one "rendering" and so on. So the data was separated
from the implementation. This helped the people to isolate the
implementation of different modules from each other. The handlers would only
see the data they know the layout to, you see. So the object could contain
whatever, and still be easily manipulated and extended.

I'm still not sure how to do such a thing in FP languages (strictly typed, I
mean). The plus in that was that they could easily add interactions to
objects, without even thinking about other parts. And the object itself
would not bloat with who-knows-what variables might come upon the
development iterations. In ocaml I guess you'd need to make records of them
all and make them all know about each other.. (that C++ solution was partly
affected by the compile times)

>> On one game developer forum there was a poll on how people managed their
>> high level code. Many developers had actually written their own
>> preprocessors to C++ in order to get introspection and the like. Only one
>> (I know of) have written their own language; GOAL / Naughty Dog.
>I suspect that a high proportion of the people on this list have written their 
>own language, probably several languages. I think I've written three 
>languages now (two interpreted, one JIT) and I'm just a physicist dabbling in 
>OCaml. ;-)

Well how many of them have made a console game (or 3) with it? It's just
that Naughty Dog managed to iron out the "hey this would not work with a
console" things out.

[GOAL]
>Again, I suspect (but may well be wrong) that a significant number of people 
>here would not regard Lisp as very high level compared to ML.

Yeah, well how many people would write assembly with lisp? Because if I
figure correctly, that's what they can do. And did. They wrote to the
co-processors directly. And I think they didn't really have a GC in it. They
just ended up to reuse the parts that are good and then end up doing it in
imperative manner.

I find this somewhat intresting. Why like this. I'm sure they had all the
capacity and language to do it all. But maybe the tight performance and
memory limits really hit the tone. I know when I'm doing console/mobile
stuff, my memory and perfomance limits are REALLY tight. Sometimes all I
have memory free is like 200kb out of 32mb total. And it HAS to work, many
hours on end.

>> (btw, one major reason for not using more FP-like languages in gamedev is
>> because the platforms are nowadays mostly not-PC and the compilers /
>> trained staff is hard to find)
>My guess is that there are far more PC game programmers than console 
>programmers. Specifically, outside industry.

True, that.. But how many of them are doing it professionally? The console
markets are increasing daily. The PC markets are growing thin and it's
looking like soon there will only be a few big ones and a lot of sw/net
companies.

But no matter what, FP is not something a new programmer starts to look at
first. It's something along the lines of C, C++, Java or C#. Or some
scripting language.

>> I would love such a book!
>I'm not sure your 80e would justify another 4 months of my time but it's 
>certainly interesting to hear. :-)

If there's one, there's bound to be another.

>Would you be interested in educational software along these lines and, if so, 
>for what platforms?

Well my point is to learn as much about FP as possible. So the software
would help. Lately I've been looking at the Clean language (haskell variant,
as I see it). They have IO and some games made in it, and it intrests me.
But none of them are large and address the issues you encounter when the
game takes more than 6 month to program by a team of 3 or more.

And the platform is all the same to me. Of course, if it's a console
platform, I can use the software to persuade others :). But if it's PC, I
can use it to learn the paradigms and maybe some day think of a way to
really figure out how an FP language should be made to support serious
industrial games development.

>Given that games programming has quite a few parallels with scientific 
>programming, I think you will find my OCaml book instructive:
>  http://www.ffconsultancy.com/products/ocaml_for_scientists

I will look at it later.. Thanks for the link!

>> And I have even written a compiler; those are easy to think in FP 
>> terms).
>There are many resources on interpreter and compiler writing, of course. 

Well I've never read any (about FP, at least). But the thing is, compilers
are fairly simple when looking at the high level. Each module has some input
and some output. And it's completely linear. The problem, for me, comes when
there are many interactions happening and it's not always completely sure
what should happen and between what. (and these things tend to change
rapindly during the development)

>So compiler and interpreter writing is my other idea for a book... :-)

And it's a lot fun too! :)

>> The low level bindings are relatively straightforward to do.
>I agree with you up to the last sentence. I've tried to write low-level OCaml 
>bindings to OpenGL and it is very difficult if you are a pedant like me and 
>want to do it properly.

Yeah, well 1-for-1 probably wouldn't work.. But if I was doing a game with
ocaml, I'd probably write my own wrappers for the platform I was using. I'm
still not convinced that ocaml is the best tool for the close-to-driver/hw
level, so it's easier and better to invent your own API (if you're doing a
big game).

As for doing educational software, an API that exposes "enough" is not hard,
and it imposes the important points. Like "how would FP help me in writing
games".

>I think there is also a mental barrier to the weird and wonderful world of FP 
>for many game programmers (and similarly for scientists). However, most C++ 
>programmers know that gratuitous use of const is good practice without 
>noticing that it is purely functional programming and most C++ programmers 
>would write vector/matrix computations in a purely functional style.

Actually I've never thought about const being "like FP". I do see it now,
though. Damn you ;D. I've been an FP programmer longer than I thought =).
Btw, some even do custom preprocessing for vector/matrix computation in
order to minimize the runtime multiplications (for example concatenating
matrix multiplications).

>> I'd be willing to pay about 80e for such a book.. But then again, it's a
>> book I've been looking for a long time.
>What you need is a consultant. :-)

I've yet to see a consultant worth his/her money :). (most I've seen just
talk what the spit brings up, take their reward and drive away, leaving the
team as lost as ever)

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

Re: [Caml-list] Games

[Jon Harrop]

On Thursday 28 July 2005 02:12, Jere Sanisalo wrote:
> True.. That's the problem with all terms, I guess. It's hard for me to
> relate how other people (especially scientific people) view it.. But just
> to say what I think about, it's all about the structure. How to build a
> framework where there can be several states, each of which is controlled by
> a different set of rules (think about menu screens and then think about a
> game area). The menus and the game are usually pretty related in terms of
> functionality, but the game (if a modern game; following from skallers
> outburst) has so many interactions it's hard to follow them.

This is exactly the kind of thing that imperative OCaml programming is well 
suited to. Our software uses OpenGL to provide interactive GUIs and this 
level of the software is largely imperative. Almost everything "beyond" this 
is purely functional, which has many benefits in applications programming and 
probably in games too but I think it is a good idea to use imperative 
programming when dealing with state machines which the user pokes into 
different states.

> It's hard to do that for even a simple game. Almost a highlevel problem,
> but in my game I gave the URL to, I'd need to somehow detect and handle the
> collision to objects. What really is a collision is the question. If an
> object slightly hits the other for 5 physics updates, is that a
> collisision. And ifit is, how to handle it. And so on.

These kinds of numerical algorithms obviously have a lot of parallels with 
scientific computing and I have found that higher-order functions tend to be 
the dish of the day here. Lots of numerical algorithms can be implemented 
much more elegantly with judicious use of HOFs. Once again though, there is 
little published work on this.

> Yeah, well as I see it, the more the pros find the tools to get closer to
> the FP style, the easier they have it. Not sure if it's FP or not, but one
> intresting idea for handling the game object behaviour was that each object
> was really just a "bag of data". And then there were many different
> handlers. An object might be subscribed to one or more of these. One
> handler might be "physics", one "rendering" and so on. So the data was
> separated from the implementation. This helped the people to isolate the
> implementation of different modules from each other. The handlers would
> only see the data they know the layout to, you see. So the object could
> contain whatever, and still be easily manipulated and extended.

Yes. It sounds as though a redesign from an OCaml point of view would be 
useful. You may well find that a lot can be done with the "bags of data" by 
simply including functions (closures) in the data.

> I'm still not sure how to do such a thing in FP languages (strictly typed,
> I mean). The plus in that was that they could easily add interactions to
> objects, without even thinking about other parts. And the object itself
> would not bloat with who-knows-what variables might come upon the
> development iterations. In ocaml I guess you'd need to make records of them
> all and make them all know about each other.. (that C++ solution was partly
> affected by the compile times)

If the mutual recursion from having them "all know about each other" causes a 
problem then you can use objects to circumvent the mutual recursion, i.e. at 
any given point in the code the OCaml object's type is on a need-to-know 
basis, so it doesn't know about all the others until it is "pulled together" 
at the end.

> > I suspect that a high proportion of the people on this list have written
> > their own language, probably several languages. I think I've written
> > three languages now (two interpreted, one JIT) and I'm just a physicist
> > dabbling in OCaml. ;-)
>
> Well how many of them have made a console game (or 3) with it? It's just
> that Naughty Dog managed to iron out the "hey this would not work with a
> console" things out.

Yes, I doubt anyone here has used their language on a console but there is a 
lot of interesting non-console stuff to discuss.

We're in the early stages of writing an interpreter for a domain-specific 
language for 2D and 3D vector graphics designed to simplify the task of 
diagram generation for technical presentations (as part of Presenta).

> > Again, I suspect (but may well be wrong) that a significant number of
> > people here would not regard Lisp as very high level compared to ML.
>
> Yeah, well how many people would write assembly with lisp?

And I suspect that a lot of people would cite that as an example of doing too 
much low-level stuff. :-)

> Because if I 
> figure correctly, that's what they can do. And did. They wrote to the
> co-processors directly. And I think they didn't really have a GC in it.

That isn't really surprising given how difficult it is to write a decent GC. 
It may even be as difficult as writing "mathematical software". ;-)

> I find this somewhat intresting. Why like this. I'm sure they had all the
> capacity and language to do it all. But maybe the tight performance and
> memory limits really hit the tone. I know when I'm doing console/mobile
> stuff, my memory and perfomance limits are REALLY tight. Sometimes all I
> have memory free is like 200kb out of 32mb total. And it HAS to work, many
> hours on end.

Yes, this is the kind of games programming that OCaml is least well-suited to.

> >My guess is that there are far more PC game programmers than console
> >programmers. Specifically, outside industry.
>
> True, that.. But how many of them are doing it professionally?

Very few, but does that matter? They can still buy products and develop code 
that you guys can use.

> The console 
> markets are increasing daily. The PC markets are growing thin and it's
> looking like soon there will only be a few big ones and a lot of sw/net
> companies.

For games overall, I can't see PC games going anywhere.

> But no matter what, FP is not something a new programmer starts to look at
> first.

Some people start programming when they reach university. Many universities 
teach FP in their first year, AFAIK. That's where I discovered ML.

> >I'm not sure your 80e would justify another 4 months of my time but it's
> >certainly interesting to hear. :-)
>
> If there's one, there's bound to be another.

True. I have quite a few games programming books on my shelves here. I think 
lots of people enjoy reading such books even if they never end up writing 
games professionally.

> >Would you be interested in educational software along these lines and, if
> > so, for what platforms?
>
> Well my point is to learn as much about FP as possible. So the software
> would help. Lately I've been looking at the Clean language (haskell
> variant, as I see it). They have IO and some games made in it, and it
> intrests me. But none of them are large and address the issues you
> encounter when the game takes more than 6 month to program by a team of 3
> or more.

I think you're going to find it very difficult to get information on how FP 
can help with projects that big because there is such a small overlap between 
games and FP at the moment. You may find a little about small games written 
in functional languages. That probably ends with Spaceman Spiff though.

> And the platform is all the same to me. Of course, if it's a console
> platform, I can use the software to persuade others :).

I meant what platforms would you like the educational software to run under, 
rather than what platforms should it describe. :-)

> But if it's PC, I 
> can use it to learn the paradigms and maybe some day think of a way to
> really figure out how an FP language should be made to support serious
> industrial games development.

I suppose it would be feasible to have a low-volume high-cost tutorial along 
those lines for console games. It would be quite a gamble for the author 
though.

> >So compiler and interpreter writing is my other idea for a book... :-)
>
> And it's a lot fun too! :)

Yes indeed! And I forgot to mention Eijiro Sumii's great work on minCaml:

  http://min-caml.sourceforge.net

> >> The low level bindings are relatively straightforward to do.
> >
> > I agree with you up to the last sentence. I've tried to write low-level
> > OCaml bindings to OpenGL and it is very difficult if you are a pedant
> > like me and want to do it properly.
>
> Yeah, well 1-for-1 probably wouldn't work.. But if I was doing a game with
> ocaml, I'd probably write my own wrappers for the platform I was using. I'm
> still not convinced that ocaml is the best tool for the close-to-driver/hw
> level, so it's easier and better to invent your own API (if you're doing a
> big game).

Yes, you'd be better off writing a thick wrapper in C/C++ and binding OCaml 
code to that.

> As for doing educational software, an API that exposes "enough" is not
> hard, and it imposes the important points. Like "how would FP help me in
> writing games".

Right.

> >I think there is also a mental barrier to the weird and wonderful world of
> > FP for many game programmers (and similarly for scientists). However,
> > most C++ programmers know that gratuitous use of const is good practice
> > without noticing that it is purely functional programming and most C++
> > programmers would write vector/matrix computations in a purely functional
> > style.
>
> Actually I've never thought about const being "like FP". I do see it now,
> though. Damn you ;D.

That's just the first example. My other favourite example is how often do you 
use "+" vs "+="? Because the former is purely functional and the latter is 
imperative.

See, I've made a functional programmer out of you already. Now, how do you 
write a numerical derivative function (and no peeking at my free first 
chapter)?

> I've been an FP programmer longer than I thought =). 
> Btw, some even do custom preprocessing for vector/matrix computation in
> order to minimize the runtime multiplications (for example concatenating
> matrix multiplications).

That is no stranger to a scientist, of course. :-)

> >What you need is a consultant. :-)
>
> I've yet to see a consultant worth his/her money :). (most I've seen just
> talk what the spit brings up, take their reward and drive away, leaving the
> team as lost as ever)

If I got a dime for every time I've heard that... :-(

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

Re: [Caml-list] Games

[skaller]

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

On Thu, 2005-07-28 at 03:44 +0100, Jon Harrop wrote:

> If the mutual recursion from having them "all know about each other" causes a 
> problem then you can use objects to circumvent the mutual recursion,

That isn't really the problem. Consider two fighters, with various
kinds of attacks and defences: what happens when A uses punch type P,
and B defends with action D .. taking into account other properties
like speed and strength.. now consider all the possible combinations:
it isn't possible to actually list them all.

You also cannot simulate the real physics -- there isn't
time for a proper simulation.

This problem is often handled by sending messages and
interpreting them.. and having a default. If the default
seems wrong, it is fixed.

Play testing is essential here. The problem is basically
that the interactions are covariant.

Crudely, you need an approximation physics that works
for the game: and this is what most games get wrong.
They don't actually design a physics, they do hoc
hacks left right and centre, and then the whole
system becomes almost impossible to manage.

This is why simplistic games work, and more sophisticated
ones tend to be full of stupid bugs .. for example
casting a 'life leech' spell on an undead monster
or stone gargoyle .. the programmers forgot to
make a special case, and they didn't design
a workable physics either.

> Yes, I doubt anyone here has used their language on a console but there is a 
> lot of interesting non-console stuff to discuss.

Felix has been used on an X-Box .. not really a console like 
a PS2 but anyhow .. :)

>  I know when I'm doing console/mobile
> > stuff, my memory and perfomance limits are REALLY tight. Sometimes all I
> > have memory free is like 200kb out of 32mb total. And it HAS to work, many
> > hours on end.
> 
> Yes, this is the kind of games programming that OCaml is least well-suited to.

Why do you think that it is any worse than C++?

-- 
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] Games

[Jon Harrop]

On Thursday 28 July 2005 05:49, skaller wrote:
> On Thu, 2005-07-28 at 03:44 +0100, Jon Harrop wrote:
> > If the mutual recursion from having them "all know about each other"
> > causes a problem then you can use objects to circumvent the mutual
> > recursion,
>
> That isn't really the problem. Consider two fighters, with various
> kinds of attacks and defences: what happens when A uses punch type P,
> and B defends with action D .. taking into account other properties
> like speed and strength.. now consider all the possible combinations:
> it isn't possible to actually list them all.
>
> You also cannot simulate the real physics -- there isn't
> time for a proper simulation.

The terms "real physics" and "proper simulation" don't mean anything. However, 
a modern PC can do a huge amount of physics modelling in real time (IMHO).

> This problem is often handled by sending messages and
> interpreting them.. and having a default. If the default
> seems wrong, it is fixed.

I'm still not clear on how this is difficult in OCaml. From your description, 
it seems very straightforward...

> Crudely, you need an approximation physics that works
> for the game: and this is what most games get wrong.
> They don't actually design a physics, they do hoc
> hacks left right and centre, and then the whole
> system becomes almost impossible to manage.

I disagree. I've written a few games. One was very popular (twoplay, for the 
Acorn). I deliberately used "fake physics" on all of them because real 
physics almost always leads to bad game play. You get more freedom with fake 
physics (anything goes) which does make it easier to break the code but I'm 
not convinced that this is a real problem. I think there are much bigger 
problems with some of the algorithms, e.g. getting stuck.

> This is why simplistic games work, and more sophisticated
> ones tend to be full of stupid bugs .. for example
> casting a 'life leech' spell on an undead monster
> or stone gargoyle .. the programmers forgot to
> make a special case, and they didn't design
> a workable physics either.

One of the few games that I have really enjoyed in recent years is Grand Theft 
Auto, Vice City (on PS2). That was quite sophisticed with LOD algorithms and 
so forth. It also had many bugs. After you'd been playing for a while it 
slowed down to a crawl (probably due to manual memory allocation ;-). It 
would also hang quite often (probably due to too much low-level coding).

From my point of view, there is nothing technologically difficult in that game 
at all. I can see no reason for those bugs except poor programming.

I think there is no question that OCaml could have been used to write most of 
the code for the PC version without adversely affecting performance whilst 
greatly improving reliability. I see no reason to think that the console 
versions would not be similarly feasible, although it would require more 
work. Many games now use quite sophisticated LOD algorithms and OCaml is 
vastly better suited to this than C++.

> > Yes, I doubt anyone here has used their language on a console but there
> > is a lot of interesting non-console stuff to discuss.
>
> Felix has been used on an X-Box .. not really a console like
> a PS2 but anyhow .. :)

Impressive. :-)

> > > stuff, my memory and perfomance limits are REALLY tight. Sometimes all
> > > I have memory free is like 200kb out of 32mb total. And it HAS to work,
> > > many hours on end.
> >
> > Yes, this is the kind of games programming that OCaml is least
> > well-suited to.
>
> Why do you think that it is any worse than C++?

C++ has much more predictable memory requirements and it is much easier to 
squeeze memory usage in C++ than in OCaml. So if I were programming for 
something with really tight memory requirements (like embedded) then I'd 
probably avoid OCaml. However, modern consoles have a lot more memory and, I 
think, with a little effort OCaml should be workable. If I were a console 
games programmer then I'd definitely want to play with a suitable working 
OCaml setup before using it in a production game, of course.

I guess it would take 6 months of hard work by a single OCaml-familiar 
programmer to get a working system up and running (provided ocamlopt already 
has a backend for the CPU). Given the potential savings, I'd be surprised if 
some games house wouldn't fund such work. Failing that, it would make a funky 
academic project. :-)

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

Re: [Caml-list] Games

[David Thomas]

I'm probably missing something obvious, but... why?

--- Jon Harrop <jon@ffconsultancy.com> wrote:
> Many games now use quite sophisticated LOD
algorithms
> and OCaml is vastly better suited to this than C++.


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

Re: [Caml-list] Games

[Jon Harrop]

On Thursday 28 July 2005 22:32, David Thomas wrote:
> --- Jon Harrop <jon@ffconsultancy.com> wrote:
> > Many games now use quite sophisticated LOD algorithms
> > and OCaml is vastly better suited to this than C++.
>
> I'm probably missing something obvious, but... why?

Essentially, OCaml is much better suited to the manipulation of complicated 
data structures like trees and graphs than C++. In particular, it is much 
easier to write such code correctly in OCaml than in C++.

As games have evolved, their emphasis has moved from blitting to simulating 
the interactions of complicated hierarchical systems in real time. For 
example, the transition from (array-based) sprites to (tree- or graph-based) 
LOD polygonal models in the presence of collision detection.

Similarly, as scientific computing has evolved, emphasis has moved from 
vector/matrix calculations to the hierarchical simulation of physical systems 
(not in real time!). For example, use of the (tree-based) Fast Multipole 
Method (FMM) instead of (array-based) Ewald summation when computing 
long-range interactions between particles.

This is easily explained with a little computer science: We're now close 
enough to the asymptote that asymptotic algorithmic complexity has become 
more important than the constant prefactor. We know that trees, graphs and 
many other non-trivial data structures facilitate common operations (e.g. 
search, insert, replace) with considerably better asymptotic complexities 
(e.g. O(log n) instead of O(n)). So we're ditching arrays in favour of trees 
and graphs and, consequently, we should be ditching C++ in favour of OCaml.

This is exactly the topic of my book "Objective CAML for Scientists". Hence, I 
think I'm a suitable candidate for writing "Objective CAML for Games". :-)

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

Re: [Caml-list] Games

[Michael Walter]

On 7/28/05, Jon Harrop <jon@ffconsultancy.com> wrote:
> On Thursday 28 July 2005 22:32, David Thomas wrote:
> > --- Jon Harrop <jon@ffconsultancy.com> wrote:
> > > Many games now use quite sophisticated LOD algorithms
> > > and OCaml is vastly better suited to this than C++.
> >
> > I'm probably missing something obvious, but... why?
> 
> Essentially, OCaml is much better suited to the manipulation of complicated
> data structures like trees and graphs than C++. In particular, it is much
> easier to write such code correctly in OCaml than in C++.

I don't see the C++ implementation part being a major source of
complexity these days in rendering. I suppose your example would be
more applicable to other areas of game programming.

Cheers,
Michael

Re: [Caml-list] Games

[David Thomas]

So just simplicity of coding the algorithms?  Makes
sense enough, I was just wondering if there was
something deeper.  Thanks :)

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

> On Thursday 28 July 2005 22:32, David Thomas wrote:
> > --- Jon Harrop <jon@ffconsultancy.com> wrote:
> > > Many games now use quite sophisticated LOD
> algorithms
> > > and OCaml is vastly better suited to this than
> C++.
> >
> > I'm probably missing something obvious, but...
> why?
> 
> Essentially, OCaml is much better suited to the
> manipulation of complicated 
> data structures like trees and graphs than C++. In
> particular, it is much 
> easier to write such code correctly in OCaml than in
> C++.
> 
> As games have evolved, their emphasis has moved from
> blitting to simulating 
> the interactions of complicated hierarchical systems
> in real time. For 
> example, the transition from (array-based) sprites
> to (tree- or graph-based) 
> LOD polygonal models in the presence of collision
> detection.
> 
> Similarly, as scientific computing has evolved,
> emphasis has moved from 
> vector/matrix calculations to the hierarchical
> simulation of physical systems 
> (not in real time!). For example, use of the
> (tree-based) Fast Multipole 
> Method (FMM) instead of (array-based) Ewald
> summation when computing 
> long-range interactions between particles.
> 
> This is easily explained with a little computer
> science: We're now close 
> enough to the asymptote that asymptotic algorithmic
> complexity has become 
> more important than the constant prefactor. We know
> that trees, graphs and 
> many other non-trivial data structures facilitate
> common operations (e.g. 
> search, insert, replace) with considerably better
> asymptotic complexities 
> (e.g. O(log n) instead of O(n)). So we're ditching
> arrays in favour of trees 
> and graphs and, consequently, we should be ditching
> C++ in favour of OCaml.
> 
> This is exactly the topic of my book "Objective CAML
> for Scientists". Hence, I 
> think I'm a suitable candidate for writing
> "Objective CAML for Games". :-)
> 
> -- 
> 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] Games

[skaller]

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

On Thu, 2005-07-28 at 19:32 -0700, David Thomas wrote:
> So just simplicity of coding the algorithms?  Makes
> sense enough, I was just wondering if there was
> something deeper.  Thanks :)

gee, I'm confused .. what else could there possibly
be *other* than simplicity of encoding algorithms???

-- 
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] Games

[David Thomas]

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

> On Thu, 2005-07-28 at 19:32 -0700, David Thomas
> wrote:
> > So just simplicity of coding the algorithms? 
> Makes
> > sense enough, I was just wondering if there was
> > something deeper.  Thanks :)
> 
> gee, I'm confused .. what else could there possibly
> be *other* than simplicity of encoding algorithms???
> 
> -- 
> 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
> 



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

Re: [Caml-list] Games

[Gerd Stolpmann]

Am Donnerstag, den 28.07.2005, 04:12 +0300 schrieb Jere Sanisalo:
> >> For the problems 
> >> described here I can see much easier explanations. Mostly having something
> >> to do with extremely tight deadlines, producers/publishers not knowing what
> >> they want and changing their mind all the time and the tight coupling to a
> >> limited hardware.
> >Tight deadlines and closeness to hardware make sense. But if the specification 
> >keeps changing then I would say that a higher-level language would be more 
> >suitable. I know what you mean though...
> 
> Yeah, well as I see it, the more the pros find the tools to get closer to
> the FP style, the easier they have it. Not sure if it's FP or not, but one
> intresting idea for handling the game object behaviour was that each object
> was really just a "bag of data". And then there were many different
> handlers. An object might be subscribed to one or more of these. One handler
> might be "physics", one "rendering" and so on. So the data was separated
> from the implementation. This helped the people to isolate the
> implementation of different modules from each other. The handlers would only
> see the data they know the layout to, you see. So the object could contain
> whatever, and still be easily manipulated and extended.
> 
> I'm still not sure how to do such a thing in FP languages (strictly typed, I
> mean). The plus in that was that they could easily add interactions to
> objects, without even thinking about other parts. And the object itself
> would not bloat with who-knows-what variables might come upon the
> development iterations. In ocaml I guess you'd need to make records of them
> all and make them all know about each other.. (that C++ solution was partly
> affected by the compile times)

Some times ago I wrote a little demo that could be seen as the beginning
of a 3D game: https://gps.dynxs.de/svn/app-3dflight/trunk/

There isn't very much design in it, and because of its simplicity, it
focuses on the rendering part. The key idea is that the various virtual
objects are represented by O'Caml objects that describe themselves. The
only relationship between objects is that they may collide.

I think the interesting part of this demo is the collision algorithm,
because two objects must somehow interact with each other. Actually, no
object needs to know any other object, but it can compute whether it
collides with a single 3D point (i.e. an abstraction of a second
object). This way, the algorithm can be separated in a "local part",
done by the objects themselves, and a "global part", which is the
overall loop. I don't know whether this idea can be applied to other
types of interactions as well, but from a general point of view it seems
to be the right direction to reduce the properties that objects expose
to other objects.

The demo also shows that the speed of the O'Caml code is almost
irrelevant; there is no difference whether you compile it to bytecode or
to native code. The speed of the graphics engine is very relevant.

> Well my point is to learn as much about FP as possible. So the software
> would help. Lately I've been looking at the Clean language (haskell variant,
> as I see it). They have IO and some games made in it, and it intrests me.
> But none of them are large and address the issues you encounter when the
> game takes more than 6 month to program by a team of 3 or more.
> 
> And the platform is all the same to me. Of course, if it's a console
> platform, I can use the software to persuade others :). But if it's PC, I
> can use it to learn the paradigms and maybe some day think of a way to
> really figure out how an FP language should be made to support serious
> industrial games development.

It isn't that hard to port the O'Caml core to a new architecture
(provided the CPU is supported). The problematic part are the libraries,
and you need at least a good 3D graphics library. But if a company
invested in that, e.g. one man year, the resulting platform would be
quite attractive.

> Well I've never read any (about FP, at least). But the thing is, compilers
> are fairly simple when looking at the high level. Each module has some input
> and some output. And it's completely linear. The problem, for me, comes when
> there are many interactions happening and it's not always completely sure
> what should happen and between what. (and these things tend to change
> rapindly during the development)

Exactly this requirement makes O'Caml attractive: you can change the
program frequently, and almost all update problems are detected by the
compiler.

> Yeah, well 1-for-1 probably wouldn't work.. But if I was doing a game with
> ocaml, I'd probably write my own wrappers for the platform I was using. I'm
> still not convinced that ocaml is the best tool for the close-to-driver/hw
> level, so it's easier and better to invent your own API (if you're doing a
> big game).

For the hardware level it is definitely not a good choice. You need a
graphics API, be a standard one like openGL or a custom API.

Doing the bindings to O'Caml isn't very much work if you don't pass
complex structures.

> Actually I've never thought about const being "like FP". I do see it now,
> though. Damn you ;D. I've been an FP programmer longer than I thought =).
> Btw, some even do custom preprocessing for vector/matrix computation in
> order to minimize the runtime multiplications (for example concatenating
> matrix multiplications).

Looks like this type of optimisation can be done in camlp4.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Telefon: 06151/153855                  Telefax: 06151/997714
------------------------------------------------------------

Re: [Caml-list] Games

[David Thomas]

I would probably recommend a B&W book, and some
examples and pictures online.  That way the pictures
and examples cost you nothing to distribute, people
can have a nice handy dead-tree copy, and other people
can see the examples and go, "I want to learn how to
do that..." and thus increase interest in the book.

--- Jon Harrop <jon@ffconsultancy.com> wrote:
> I think there is ample market for a games
programming
> OCaml book but it would be difficult to sell it at a

> low enough price (again, I think it would really 
> benefit from being full color). So I'm now thinking
> that it might be better suited to educational
software 
> rather than a book. Not least because on-screen 3D 
> graphics would really help to explain things. When
we 
> finish it, Presenta should be ideal for this...



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

Re: [Caml-list] Games

[Jon Harrop]

On Thursday 28 July 2005 18:19, David Thomas wrote:
> I would probably recommend a B&W book, and some
> examples and pictures online.  That way the pictures
> and examples cost you nothing to distribute, people
> can have a nice handy dead-tree copy, and other people
> can see the examples and go, "I want to learn how to
> do that..." and thus increase interest in the book.

If I were to do this then it would be significantly cheaper to have entirely 
software rather than a book, simply because the distribution costs are so 
much lower for software.

I also think there is great scope for educational software which includes 
real-time 2D and 3D graphics but I'll put my money where my mouth is before 
advocating that further. :-)

What other OCaml-related educational software would people be interested in? 
DSL design?

-- 
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?

[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: 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?

[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] Games

[Jon Harrop]

On Wednesday 27 July 2005 22:13, Pal-Kristian Engstad wrote:
> 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.

Firstly, the PC game market is minor compared to consoles in terms of 
industrial profits. However, the console market is minor compared to the PC 
market in terms of the number of programmers.

Secondly, what would it take for OCaml to support console platforms?

> 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.

From my point of view, making a statement that that about ML really makes me 
think that you're pointing in the wrong direction. ML is all about _not_ 
exposing such low-level constructs.

I think you should try forgetting about all of the subpoints you've made here 
for a mini project (if you're interested in persuing this) just to see how 
important they really are.

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

OCaml's current GC is good enough for games, IMHO.

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

Can you explain why this is particularly 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.

I know very little of threads but I believe your assertion is incorrect. I'm 
sure someone more knowledgeable than I will clarify...

> 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...

Your statement about OCaml's current suitability for games console programming 
is subjective. I think it would be more productive to try to objectively 
state what work needs to be done in order to make OCaml suitable for games 
console programming. My guess is that you "only" need low-level bindings from 
OCaml to whatever library is exposed. Writing these bindings will probably be 
a lot of work though.

Then it is a case of "suck it and see". As I say, I think you'll find that the 
GC is irrelevant. However, you may be correct about alignment issues etc., in 
which case you will need to move code from OCaml to C. That still leaves 
plenty of interesting high-level code that can be productively written in 
OCaml.

However, I (and I don't think Skaller) was talking about games consoles. I was 
thinking (and gave the example of Darwinia) of the much larger number of 
games that are written for fun, often by people in their spare time, for 
desktop computers. I think there is a market here for educational material to 
teach these people how to program games more easily by using OCaml instead of 
C++. I'd bet that Darwinia, for example, would have been much easier to write 
in OCaml. I agree that OCaml is currently much better suited to this than to 
consoles but consoles aren't everything...

-- 
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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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: 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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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?

[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: 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?

[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?

[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)