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.

If I understand correctly (feel free to correct myself) :

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

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

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.


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

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