William Lovas <wlovas@stwing.upenn.edu> wrote:

> On Fri, Jan 30, 2004 at 11:36:13AM +0100, Thomas Fischbacher wrote:
> > 
> > On Thu, 29 Jan 2004, William Lovas wrote:
> > 
> > >     # type ('a, 'b) specialist = S of (('a, 'b) specialist -> 'a -> 'b);;
[...]
> > 
> > Hm, correct me if I am wrong, but to me this looks as if you had to 
> > unnecessarily cons at every recursive call...
> 
> Well, it depends on what you mean by "unnecessarily" and what you mean by
> "cons".  First, if by "cons" you mean "call a constructor", then yes, i did
> have to cons at every recursive call.  However, if by "cons" you mean
> "allocate memory", i can't say for sure by looking at this code -- it says
> nothing about the optimizations applied to variant types during compilation
> or potential opportunities for structure sharing.  I strongly suspect that
> memory need not be allocated, though, in which case the answer is no, i did
> not have to allocate memory at every recursive cell.
> 

  Just look at this:

rv@helios:~$ cat specialist_typed.ml
type ('a, 'b) specialist = S of (('a, 'b) specialist -> 'a -> 'b)

let fac n =
  let do_rec (S specialist) n =
    if n = 0 then
      1
    else
      n * specialist (S specialist) (n - 1)
  in
  do_rec (S do_rec) n

rv@helios:~$ ocamlc -dlambda specialist_typed.ml
(setglobal Specialist_typed!
  (let
    (fac/61
       (function n/62
         (let
           (do_rec/63
              (function param/68 n/65
                (if (== n/65 0) 1
                  (let (specialist/64 (field 0 param/68))
                    (* n/65
                      (apply specialist/64 (makeblock 0 specialist/64)
                        (- n/65 1)))))))
           (apply do_rec/63 (makeblock 0 do_rec/63) n/62))))
    (makeblock 0 fac/61)))

rv@helios:~$ ocamlc -dlambda specialist_untyped.ml
(setglobal Specialist_untyped!
  (let
    (fac/56
       (function n/57
         (let
           (do_rec/58
              (function specialist/59 n/60
                (if (== n/60 0) 1
                  (* n/60
                    (apply specialist/59 (id specialist/59) (- n/60 1))))))
           (apply do_rec/58 do_rec/58 n/57))))
    (makeblock 0 fac/56)))


The difference between the two versions are in those two calls

    (id specialist/..)               ; obviously a nop
and
    (makeblock 0 specialist/..)      ; ???

Comments about whether (makeblock 0 ..) is a special case which can be
optimized away are welcome.

> 
> cheers,
> William
> 

Regards,
Vasha

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners