Перевод императива в функциональный код

Question

Мне нужно написать программу, которая переведет императивный код в чисто функциональный стиль. Я не беспокоюсь о вводе / выводе - у меня есть некоторые решения для этого - но мне нужно иметь дело с объектами кучи, а также с локальными переменными.

Я полагаю, что это можно сделать, передавая объект TheWorld при каждом вызове и возврате функции, а затем оптимизируя оттуда, пытаясь удалить этот параметр из функций, где он не используется и т. Д. Но существует ли известный лучший способ делать это?

Answer 1

Как указывает SK-logic, вы можете представить свою императивную программу в форме SSA.

Однако вместо применения преобразования CPS вы можете напрямую преобразовать обязательное представление SSA в эквивалентную чисто функциональную программу в «административной нормальной форме» - ограниченном функциональном языке, основанном на алгоритме, опубликованном Задарновским и др. 1003 *

Два языка задаются как:

См .: « Функциональная перспектива алгоритмов оптимизации SSA », в которой приведены алгоритмы автоматического перевода программ в форме SSA в ANF.

Answer 2

Существует несколько способов сделать такой перевод эффективно. Во-первых, стоит выполнить преобразование SSA с последующим преобразованием CPS : таким образом вы получите набор тривиальных взаимно рекурсивных функций из императивного кода с переменными и ветвями. Вызовы функций (и даже виртуальные вызовы) также можно легко редактировать CPS, передавая параметр продолжения вместо того, чтобы полагаться на неявную семантику стека.

Массивы можно обрабатывать так же, как и переменные, перед преобразованием SSA весь доступ к массиву должен быть заменен на вызовы функций get и update, которые должны иметь неявную семантику копирования (но остерегаться псевдонимов этот случай). То же самое для конструкций.

И только для тех случаев, когда невозможно поддерживать семантику копирования, вам нужен этот TheWorld объект, который должен хранить все выделенные объекты и должен копироваться полностью каждый раз, когда вы модифицируете один из них.