Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
AGI research using ocaml
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Eray Ozkural <examachine@g...>
Subject: Re: [Caml-list] AGI research using ocaml
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


> 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).


> 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" :
> - MinCaml, a tiny ML compiler by Eijiro Sumii :

Thank you.

Best Regards,

Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara