Re: AGI research using ocaml

[Stefan Monnier <monnier@iro.umontreal.ca>]

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

Depending on how you want to use types, it can help, but not
necessarily:

If you manage to use types to restrict your search, then that's great,
since your programs will be properly typed by construction (and the host
language may even know that, e.g. using GADTs or something equivalent)
and you may indeed be able to interpret them faster.

But if you don't, then you end up with programs which may or may not be
properly typed, in which case types will allow you to reject programs
before running them, but at the cost of having to type-check every
program.  So if the run time of each program is short compared to the
program's size, it may end up more costly to type-check the code than to
just run it.


        Stefan