From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 0149ABBAF for ; Sat, 13 Mar 2010 15:00:16 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aj4CAPIom0vRVdrYkGdsb2JhbACOdYF2ghKHbQgVAQEBAQkJDAcTAx+pGoFhhFwuiEsBAQMFhHYE X-IronPort-AV: E=Sophos;i="4.49,632,1262559600"; d="scan'208";a="54751774" Received: from mail-bw0-f216.google.com ([209.85.218.216]) by mail1-smtp-roc.national.inria.fr with ESMTP; 13 Mar 2010 15:00:16 +0100 Received: by bwz8 with SMTP id 8so1778661bwz.3 for ; Sat, 13 Mar 2010 06:00:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:cc:content-type; bh=ARCbIT8vfAhBp3EDxLvWoIt5/Ma5UJwsE/2SkM4NQMk=; b=TeiiFZz2rZqoccdmzBtev1pt7mxGqwTo1GKe8Iw7TfB+HGrH23nvNlEYe4SCmnaEnX fmUYld40VUq1hb+HaTXOrrF8GxfKx4mFgJ3RdaL1RlI0T2f26TvMFLv8kWKFr+v8J266 97Oeqn9/XrBJ1s8lh1cLfG5qkDvyzKZtE3BT0= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=ov3sPs0vG8XEC/m2GBXqtxuX5AUxzq+ZPEMU1HjOFgzE1OEooeKV/yqAR31BqVbBoS 5sgrEnRAMf8S5Ez7ooSOwTvTn68JLSOCXv8X8mXJ7wS3yCTCX1pjPFFGJuE7yYQFgwHY ATKDM/9XYxRGLnyYoKPqR1EkBMNMOzrhXlSew= MIME-Version: 1.0 Received: by 10.204.5.154 with SMTP id 26mr3462232bkv.62.1268488814241; Sat, 13 Mar 2010 06:00:14 -0800 (PST) In-Reply-To: <527cf6bc1003130521p203013bbo1c62ff66479cff6a@mail.gmail.com> References: <320e992a1003130229v1f39f6aek752c32a677c3ac87@mail.gmail.com> <527cf6bc1003130521p203013bbo1c62ff66479cff6a@mail.gmail.com> Date: Sat, 13 Mar 2010 16:00:14 +0200 Message-ID: <320e992a1003130600m5397f86bwe0023c78c3b0991e@mail.gmail.com> Subject: Re: [Caml-list] AGI research using ocaml From: Eray Ozkural To: blue storm Cc: caml-list Content-Type: text/plain; charset=ISO-8859-1 X-Spam: no; 0.00; ocaml:01 eray:01 ozkural:01 ocaml:01 subset:01 subset:01 real-world:01 recursive:01 recursive:01 recursion:01 interpretor:01 langauge:01 bytecode:01 bytecode:01 compiler:01 Hello BlueStorm, I assume you're an AI of some sort ;) On Sat, Mar 13, 2010 at 3:21 PM, blue storm wrote: > It is difficult to understand what you say with no previous knowledge of > your field (wich is probably not a common knowledge among OCaml hackers). > The fact that you paper is named "Stochastic Grammar Based Incremental > Machine Learning Using Scheme" doesn't help. It would be impossible for anybody to construct Algorithmic Probability Theory on his own in little time. In fact, that's why I'm working on incremental machine learning, for there is no way one can simply come up with all the results in a branch of science from zero ground. We stand on the shoulders of the giants, which is the problem I'm working on: general-purpose long-term memory. > If I understand correctly (feel free to correct myself) : Please go ahead, I'll do my best to clarify. > 1) your field of research is "automatic program generation to solve a set of > given tasks" : you generate random programs in a given language, with a > mathematic theory giving you probability distribution for various syntaxic > elements, until you find one that achieve your goal. You have a "learning > mechanism" that can reuse previous solution (such as declared functions) for > helping further tasks Yes, although I don't generate random programs. Programs in the current system are generated in a deterministic order. It's basically a search in the space of leftmost-derivations of Scheme programming language. This is the induction step. You are right, however, that program generation could be random. I have a saying on the relation of all this to better known AI research subjects: Algorithmic Probability Theory is to Genetic Programming what Statistical Learning Theory is to Neural Network Learning. That is, it is a general principle of induction, that's known to have very small generalization error. And there are proposed ways of achieving this, like Adaptive Levin Search. In a nutshell, you could say that it is an advanced kind of GP. > 2) You generate Scheme program fragments Yes. > 3) Your algorithm/generator is written in OCaml, using the ocs Ocaml Scheme > interpreter to test your generated programs That's right. > 4) You would like to generate OCaml program fragments instead of Scheme. > Your idea is that the type system, imposing more constraints on the legal > program, will reduce the search space and accelerate your generator. Absolutely. For simpler function induction problems, I assume this could even be done automatically by inducing type constraints over a set of examples. Part of future research, I think. I am afraid I'll have to read many programming language papers! > In the example you give (square root, nand), you use only a tiny subset of a > general programming language features. Why did you choose to target the full > Scheme, instead of a minimalistic Lisp/Scheme subset ? It seems to me that > targeting a bigger language (wich additional feature your generator probably > doesn't know about anyway) will mainly incur an overhead on program > evaluation. Correct. But that was done to illustrate two (mainly obscure) points. First, that we can tackle a real-world programming language in its whole glory. Second, actually recursive problems are not required to know that the system is in principle of doing such, for recursive problems have been previously solved. Obviously, future problems will feature recursion. For instance, Towers of Hanoi was solved previously. It would be interesting to reproduce that result in Scheme to see if that solution depended on a specific (lucky) initial condition. > It is reasonable if you can access an already existing interpretor/evaluator > implementation that suit your need (reusing one of the available scheme > interpreters makes more sense than reimplementing one for scratch, maybe > even for a tiny subset of the langauge). Yes. > However, I'm not sure you can have something similar for OCaml : the only > used OCaml implementation is the INRIA implementation, wich has bytecode and > native compilers, but are not specially easy to invoke programmatically with > low startup times requirements. Perhaps the bytecode compiler would be quick > enough for your need, you should try. Compilation would probably be overkill. The evaluation shouldn't make any unnecessary syscall's, access files, etc. > I think the easiest way for you would be to implement a small language with > a ML typing system, and a tiny (but not algorithmically inefficient) > interpreter for it. On small program fragments, a small interpreter would > probably be much more interesting that calling an external tool. Besides, > you could design your small language accordingly to your generator > abilities. Yes, something like that is done in ADATE IIRC. > You might also be interesting in minimal ML interpreters/compilers projects. > The two that I know of are : > - MiniML in Andrej Bauer "Programming language Zoo" : > http://andrej.com/plzoo/html/miniml.html > - MinCaml, a tiny ML compiler by Eijiro Sumii : > http://min-caml.sourceforge.net/index-e.html Thank you. Best Regards, -- Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara http://groups.yahoo.com/group/ai-philosophy http://myspace.com/arizanesil http://myspace.com/malfunct