Создание замыкания в компиляторе, похожем на схему - PullRequest
Новая
       12

Создание замыкания в компиляторе, похожем на схему

0 голосов
/ 10 мая 2019

Я реализую похожий на схему lisp, который в какой-то момент будет скомпилирован в некоторую форму байт-кода, которую можно увидеть здесь .К сожалению, я закодировал себя в какую-то дыру и не уверен, как из нее выбраться.По сути, с учетом лямбды, которая выглядит следующим образом (внешний b преднамеренно не используется): 

(lambda (a b) (lambda (c) (+ a c)))

Мой код выдает это дерево синтаксиса: 

[
  type: :lambda,
  args: [[type: :word, val: 'a'], [type: :word, val: 'b']],
  body: [
    [
      type: :lambda,
      args: [[type: :word, val: 'c']],
      body: [
        [
          type: :expr,
          val: [
            [type: :word, val: '+'],
            [type: :word, val: 'a'],
            [type: :word, val: 'c']
          ]
        ]
      ]
    ]
  ]
]

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

[
  type: :lambda,
  args: [[type: :word, val: 'a'], [type: :word, val: 'b']],
  closure: [],
  body: [
    [
      type: :lambda,
      args: [[type: :word, val: 'c']],
      closure: [[type: :word, val: 'a']],
      body: [
        [
          type: :expr,
          val: [
            [type: :word, val: '+'],
            [type: :word, val: 'a'],
            [type: :word, val: 'c']
          ]
        ]
      ]
    ]
  ]
]

Достаточно легко определить, должен ли данный параметр быть частью замыкания, посмотрев, отображается ли оно в env,однако, поскольку я просто вызываю Enum.map поверх body , я не уверен, как вернуть эту информацию обратно в мой лямбда-объект.Мне не нужен конкретный код для того, чтобы это исправить, но общие указания / подсказки / толчки в правильном направлении были бы хороши (я знаю, что это немного расплывчато, но я не совсем уверен, как сделать более конкретный тестдело за этим).

1 Ответ

2 голосов
/ 10 мая 2019

Вы можете пройтись по своему AST, составив список связанных идентификаторов на каждом узле.

Например, узел lambda связывает свои аргументы (не стесняйтесь переписывать эти имена, если они уже есть в вашем связанном списке), а также let и let*. Вы также создаете список свободных идентификаторов, на которые ссылаются, для каждого узла AST, проходя назад по этому дереву.

lambda, let и let* удаляют идентификаторы из этих списков свободных переменных.

В остальном все просто: на каждом узле lambda вы вычисляете пересечение между ссылочными и связанными списками, и результатом будет среда, которую должно закрывать это замыкание. Если он пуст, это простая функция без среды.

В вашем примере это будет:

[b:() f:()](lambda (a b) [b:(a b) f:(a)] (lambda (c) [b: (a b c) f: (a c)] (+ a c)))

Как вы можете видеть, внутренняя лямбда имеет a общего между списками b: и f:, поэтому вы должны выполнить здесь инструкцию выделения замыкания, создавая среду из одного элемента, a.

Вы можете объединить этот проход с переименованием переменной (например, преобразование имен лямбда-аргументов в номера аргументов).

...