Automatic complexity analysis of OCaml programs

Automatic complexity analysis of OCaml programs

[Roberto Bagnara]

I am looking for references and pointers to existing
works concerning the automatic or semiautomatic
complexity analysis of programs written in OCaml or
in a subset of it.  Pointers to the literature
and to available implementations are both very welcome.
Many thanks in advance,

     Roberto

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara@cs.unipr.it

Re: [Caml-list] Automatic complexity analysis of OCaml programs

[Frédéric Gava]

Hi,

See the works of
- Kevin Hammond about inference cost equation.
- Bernd Grobauer about cost recurrence for DML programs,
- Whei-Nagan and Siau-Chaeng Khoo about sized types,
- Daniel Le metayer, ACE an automatic complexity evaluator,
- Brian Reistad and David K. Gifford about satic dependent costs for
estimating program excution time
 - Mads Rosendahl: "automatic complexity analysis"  (cost of extracted nuprl
programs)

Cheers,
Frédéric Gava

----- Original Message -----
From: "Roberto Bagnara" <bagnara@cs.unipr.it>
To: <caml-list@inria.fr>
Sent: Thursday, December 02, 2004 12:57 PM
Subject: [Caml-list] Automatic complexity analysis of OCaml programs


>
> I am looking for references and pointers to existing
> works concerning the automatic or semiautomatic
> complexity analysis of programs written in OCaml or
> in a subset of it.  Pointers to the literature
> and to available implementations are both very welcome.
> Many thanks in advance,
>
>      Roberto
>
> --
> Prof. Roberto Bagnara
> Computer Science Group
> Department of Mathematics, University of Parma, Italy
> http://www.cs.unipr.it/~bagnara/
> mailto:bagnara@cs.unipr.it
>
> _______________________________________________
> 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] Automatic complexity analysis of OCaml programs

[Jacques Carette]

Also the work of the people-next-door to the Ocaml developers, namely the ALGO project.  See their web page at 
http://algo.inria.fr/.

In particular the work of Philippe Flajolet, Bruno Salvy and Marni Mishna (spanning many years) on "automatic 
complexity analysis", *especially* the asymptotic average-case analyses are quite impressive.  They have been doing 
this since 1989, but 'hiding' in the combinatorics and algorithms communities, and somehow their work seems to have 
(unfortunately) escaped the attention of the programming language community.

Jacques

Frédéric Gava <frederic.gava@wanadoo.fr> wrote:
> Hi,
> 
> See the works of
> - Kevin Hammond about inference cost equation.
> - Bernd Grobauer about cost recurrence for DML programs,
> - Whei-Nagan and Siau-Chaeng Khoo about sized types,
> - Daniel Le metayer, ACE an automatic complexity evaluator,
> - Brian Reistad and David K. Gifford about satic dependent costs for
> estimating program excution time
>  - Mads Rosendahl: "automatic complexity analysis"  (cost of extracted nuprl
> programs)
> 
> Cheers,
> Frédéric Gava
> 
> ----- Original Message -----
> From: "Roberto Bagnara" <bagnara@cs.unipr.it>
> To: <caml-list@inria.fr>
> Sent: Thursday, December 02, 2004 12:57 PM
> Subject: [Caml-list] Automatic complexity analysis of OCaml programs
> 
> 
> >
> > I am looking for references and pointers to existing
> > works concerning the automatic or semiautomatic
> > complexity analysis of programs written in OCaml or
> > in a subset of it.  Pointers to the literature
> > and to available implementations are both very welcome.
> > Many thanks in advance,
> >
> >      Roberto
> >
> > --
> > Prof. Roberto Bagnara
> > Computer Science Group
> > Department of Mathematics, University of Parma, Italy
> > http://www.cs.unipr.it/~bagnara/
> > mailto:bagnara@cs.unipr.it
> >
> > _______________________________________________
> > 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
> >
> 
> 
> _______________________________________________
> 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