Возникающий в результате коэффициент ветвления в этом пространстве поиска очень велик, но в программе Foil для его уменьшения может также использоваться информация о типе. Например, если проблемная область включает данные не только о числах, но и о людях, то ограничения типов позволят исключить возможность выработки в процедуре New-Literals таких литералов, как Paren t (x, n), где χ — человек, а п — число.

В процедуре Choose-Literal используется эвристика, немного напоминающая эвристику, основанную на приросте информации, для определения того, какой литерал должен быть выбран для добавления. Точные сведения о том, как это осуществляется, не имеет в контексте данной главы слишком большого значения, к тому же было опробовано много различных вариантов таких эвристик. Одно интересное дополнительное средство программы Foil состоит в использовании принципа бритвы Оккама для устранения некоторых гипотез. Если некоторое выражение становится длиннее (согласно определенной метрике), чем общая длина положительных примеров, объясняемых с помощью этого выражения, оно больше не рассматривается в качестве потенциальной гипотезы. Такой метод предоставляет удобный способ предотвращения создания чрезмерно сложных выражений, которые обусловлены наличием шума в данных. Объяснение связи между шумом и длиной выражений приведено на с. 949.

Программа Foil и аналогичные ей программы использовались для изучения широкого ряда определений. Одна из наиболее впечатляющих демонстраций возможностей таких программ [1260] касалась решения длинной последовательности упражнений по функциям обработки списков из учебника по языку Prolog, написанного Братко [174]. В каждом случае программа показала свою способность найти в процессе обучения правильное определение функции на основе небольшого множества примеров, используя в качестве фоновых знаний ранее изученные функции.