From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA19917; Sat, 19 Oct 2002 16:56:25 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA20128 for ; Sat, 19 Oct 2002 16:56:24 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g9JEuND01081 for ; Sat, 19 Oct 2002 16:56:23 +0200 (MET DST) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.5/jtpda-5.4) with ESMTP id g9JEuMjR026147 ; Sat, 19 Oct 2002 16:56:22 +0200 (CEST) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id QAA66870 ; Sat, 19 Oct 2002 16:54:49 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id QAA1507464 ; Sat, 19 Oct 2002 16:54:49 +0200 Date: Sat, 19 Oct 2002 16:54:49 +0200 (DST) From: Diego Olivier Fernandez Pons To: "Kontra, Gergely" cc: Caml-list@inria.fr Subject: Re: [Caml-list] types & design advices (musical program) In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Antivirus: scanned by sophie at shiva.jussieu.fr Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, I did all my musical studies in France, so I may not use the same vocabulary than you. If you do not understand what I mean (or think I misunderstood what you were telling me), just feel free to ask more explanations. > Thx in advance. My future plan is automatic transcription from > numeral bass to 4-voice choir (automatic music-theory example > solver). If you mean harmonisation, it is a well known problem and has been studied in constraint programming world (since it is a declarative problem). You should look to the Principles and Practice of Constraint Programming Conference Proceedings (Springer LNCS) (I will give more information monday) I remember a research report from LIP6 (in english) explaining how they did a oriented object constraint solver for music harmonisation in SmallTalk, but LIP6 server being down, I haven't been able to localize it. There is also some papers by Xavier Rodet's and alii at Ircam (they adapted the well known Lisp constraint programming engine Screamer to solve music constraints in Open Music) What you need is a small constraint solver. There is already one in Caml (FaCiLe) which has been used to handle air traffic control by the ENAC. http://www.recherche.enac.fr/opti/facile/ If what you want to do is simple, it should be enougth. But I am afraid FaCiLe code is not very clean. I read it once because I wanted to include a simplex algorithme and I gave up. Roughtly it uses : - Objects to handle constraints - A simple constraint repository - AC6 constraint propagation algorithm - Finite domains are represented by simply linked lists If you face a combinatorial explosion problem, you may need to use smarter tricks (but I really don't think it will be the case unless you are trying to solve very huge music problems). First try to define you own goals, constraint propagation rules and search strategy (see advanced usage in FaCiLe manual). If it still doesn't improve enought, then you will have to write down your own constraint solver with smarter algorithms like : - Diet trees to represent finite domains - DAC or PC constraint propagation (only an idea, but I don't think there is much to gain here, unless your problem has special mathematical properties) - Heuristics and a priority-search queue for your exploration algorithms I have written a prototype general purpose constraint solver (written over Baire and my graph library) inpired by ALICE (Lauri=E8re 78) but it is still at an experimental stage and will need several months of more work, so do not hold your breath. Diego Olivier ------------------- 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