Компиляция вложенной взаимно рекурсивной функции - PullRequest
Новая
       26

Компиляция вложенной взаимно рекурсивной функции

3 голосов
/ 07 января 2010

Я создаю игрушечный динамический язык (болеющий за javascript), и хотя моя реализация находится на вершине DLR, я решил, что решение этой проблемы будет довольно независимым от языка / платформы.

У меня нет проблем с компиляцией рекурсивных функций или взаимно рекурсивных функций, которые существуют рядом друг с другом. Но компиляция вложенных взаимно-рекурсивных функций оказалась намного сложнее.

Пример функции, которую я использую для проверки, следующий: 

void f(int x) {
 void g(int y) {
  if((x + y) < 100) {
   f(x + y);
  } else {
   print(x + y);
  }
 }
 g(x);
}

Я подумал, что решение этой проблемы должно быть довольно общим (возможно, я ошибаюсь) и не относящимся к DLR, я предполагаю, что мне как-то нужно вывести внутреннее определение g определите его до f и сохраните контекст закрытия.

Ответы [ 3 ]

3 голосов
/ 07 января 2010

Замыкания обычно представляются в виде комбинации указателей на функции и списка аргументов. Первый шаг - действительно, чтобы поднять все вложенные функции в глобальную область с любыми связанными переменными из их среды в качестве параметров. Это будет эквивалентно: 

void _f(int x) 
{ 
  closure g = closure(_g,x);       
  call(g,x);  
}

void _g(int x, int y) 
{
  ...;
}

Когда у вас есть примитивы 'closure' и 'call', все работает. В статическом языке closure() будет содержать только соответствующие переменные. В динамическом языке closure() должен поддерживать весь стек контекста доступным в случае, если функция нуждается в этом.

1 голос
/ 07 января 2010

Я знаю, что вы создаете динамический язык, но я думаю, что те же принципы применимы и к нединамическому языку - у вас все еще есть таблица символов, и вам все еще нужно обрабатывать источник за несколько проходов.

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

Если вы выполняете оптимизацию (рекурсию хвостовой части?), То вам нужно выполнить два прохода, прежде чем проанализировать ее для этого типа оптимизации. Это нормально для всех компиляторов, которые я видел, так как этот этап происходит после семантического / лексического анализа.

Полагаю, диаграмма в этой статье хорошо показывает то, о чем я говорю (однако у нее есть дополнительный бит двух разных языков ввода.)

0 голосов
/ 07 января 2010

То, что вы пытаетесь достичь, это y-комбинатор

http://blogs.msdn.com/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx

Что такое y-комбинатор?

...