Ocaml Исключение нехватки памяти; подробный режим говорит о переполнении стека при структурном сравнении

Необходимо исправить очень большую программу ocaml из чужого источника. Одна из проблем заключается в том, что программа вылетает на, казалось бы, невинной строке:

Hashtbl.mem loc_to_no loc

с исключением «Недостаточно памяти». Дело в том, что памяти там наверняка достаточно и эта строка нормально выполняется для других входов и даже раньше при обработке проблемного.

Запустив его с OCAMLRUNPARAM="v=63", я вижу строку, которая печатается прямо перед крахом:

Переполнение стека при структурном сравнении

Используемые структуры определены ниже. loc относится к типу location.

type ('a, 'b, 'c) automaton = {
  aut_id : int ;               
  mutable start_location : (('a, 'b, 'c) location) option ;
  mutable end_location   : (('a, 'b, 'c) location) option ;
  mutable aut_attributes : 'a ;                            
}
and ('a, 'b, 'c) location = {                              
  loc_id : int ;
  mutable succs : ('c * ('a, 'b, 'c) location) list ;
  mutable preds : ('c * ('a, 'b, 'c) location) list ;
  automaton : ('a, 'b, 'c) automaton ;
  mutable loc_attributes : 'b ;
}

Что нужно сделать, чтобы код выполнялся?


crash out-of-memory ocaml
person P Shved    schedule 08.09.2009    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Что ж, поиск в хеш-таблице использует «=» (структурное равенство), чтобы определить, совпадает ли ключ с тем, что вы ищете. Структурное равенство требует тщательной проверки всех подструктур и прочего. У вас сложная рекурсивная структура данных. Возможно, в какой-то момент в структуре есть цикл, из-за которого она будет зацикливаться бесконечно. В любом случае подумайте о том, как вы хотите, чтобы хэш-таблица сообщала, совпадает ли ключ с вашим, и тогда вам нужно использовать такое равенство вместо структурного равенства по умолчанию; используйте функтор Hashtbl.Make для определения модуля хеш-таблицы, который имеет пользовательское равенство и/или хеш-функцию.

person newacct    schedule 08.09.2009
comment
Да, это работает. По умолчанию Hashtbl использует = для сравнения ключей, что является рекурсивным. Я сделал функтор, который использует == для этой цели, этот оператор не сравнивает рекурсивно. - person P Shved; 09.09.2009
comment
да, вы можете использовать == (физическое равенство); но в этом случае убедитесь, что объект, который вы передаете, является тем же объектом, который изначально использовался в качестве ключа (а не просто другим объектом с той же структурой) - person newacct; 10.09.2009