* Automatic complexity analysis of OCaml programs @ 2004-12-02 11:57 Roberto Bagnara 2004-12-02 15:00 ` [Caml-list] " Frédéric Gava 0 siblings, 1 reply; 3+ messages in thread From: Roberto Bagnara @ 2004-12-02 11:57 UTC (permalink / raw) To: caml-list 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 ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [Caml-list] Automatic complexity analysis of OCaml programs 2004-12-02 11:57 Automatic complexity analysis of OCaml programs Roberto Bagnara @ 2004-12-02 15:00 ` Frédéric Gava 2004-12-02 15:21 ` Jacques Carette 0 siblings, 1 reply; 3+ messages in thread From: Frédéric Gava @ 2004-12-02 15:00 UTC (permalink / raw) To: Roberto Bagnara, caml-list 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 > ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [Caml-list] Automatic complexity analysis of OCaml programs 2004-12-02 15:00 ` [Caml-list] " Frédéric Gava @ 2004-12-02 15:21 ` Jacques Carette 0 siblings, 0 replies; 3+ messages in thread From: Jacques Carette @ 2004-12-02 15:21 UTC (permalink / raw) To: Frédéric Gava, Roberto Bagnara, caml-list 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 ^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2004-12-02 15:21 UTC | newest] Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2004-12-02 11:57 Automatic complexity analysis of OCaml programs Roberto Bagnara 2004-12-02 15:00 ` [Caml-list] " Frédéric Gava 2004-12-02 15:21 ` Jacques Carette
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).