«Компилятор» для понимания списка в Rebol - PullRequest
Новая
       60

«Компилятор» для понимания списка в Rebol

0 голосов
/ 12 января 2020

Я хочу составить этот список понимания: 

>> lc [reduce [x y] | x in [1 2 3] y in [4 5 6]]
== [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]

в: 

collect [
   foreach x [1 2 3] [
       foreach y [4 5 6] [
           keep/only reduce [x y]]]]

или: 

>> lc [reduce [x y] | x in range [1 5] y in range reduce[1 x] if x + y > 4]
== [[3 2] [3 3] [4 1] [4 2] [4 3] [4 4] [5 1] [5 2] [5 3] [5 4] [5 5]...

в: 

collect [
    foreach x range [1 5] [
        foreach y range reduce [1 x] [
            if x + y > 4 [keep/only reduce [x y]]]]]

или: 

>> lc/flat [reduce [x y] | x in range [1 5] y in range reduce [1 x] if x + y > 4]
== [3 2 3 3 4 1 4 2 4 3 4 4 5 1 5 2 5 3 5 4 5 5]

in: 

collect [
    foreach x range [1 5] [
        foreach y range reduce [1 x] [
           if x + y > 4 [keep reduce [x y]]]]]

Моя уродливая реализация в красном: 

fx: func [code] [func [x] code]
lc: function [list-comp /flat] [ ; list-comp = [code | generators [opt if test]]
    flat: any [flat false]
    var: none
    part-gen: part-if: rest: code: []
    rule-var: [set var word! 'in]
    list: copy []
    generator+if: [copy part-gen to 'if copy part-if to end]
    generator: [copy part-gen to end]
    emit: fx [append/only list x]
    parse list-comp [
        copy code to '| skip [
            generator+if 
        | 
            generator   ]
        ]
    parse part-gen [
        some [
            rule-var (emit var) copy rest to [rule-var | end ] (emit rest)
            ]
        ]
    option: either flat [copy [keep]] [copy [keep/only]]
    code: append option code
    if part-if <> [] [code: append/only part-if code]
    foreach [l v] reverse list [code: compose [foreach (v) (l) (reduce [code])]]
    collect code
]

; from hof.r
range: func [
    {Makes a block containing a range of ord! values.
    Format: .. [1 5]   == [1 2 3 4 5]
            .. [1 3 6] == [1 2 5]
            .. [2 2 6] == [2 2 2 2 2 2]
    }
    xs [block!] {either [start end] or [start next end]}
    /local range x1 x2 delta result [block!]
][
    range: reduce xs
    x1: range/1
    either range/3 [
        x2: range/3
        delta: (range/2 - x1)
    ][
        x2: range/2
        delta: 1
    ]

    ;result: make block! (x2 - x1) / delta
    result: copy []
    either delta <> 0 [
        result: reduce [x1]
        loop x2 - x1 [
            append result delta + last result
        ]
    ][
        loop absolute x2 [
            insert tail result x1
        ]
    ]
    result
]

Программа не flow , он полон переменных, , если и append (у меня были трудности с parse ; compose , в данном случае, ограничено).
Существует ли более "reboli sh" способ (в rebol2 / rebol3 / red / ren- c) для решения этой проблемы?

Обновление: моя реализация 'компилятора' является лишь указанием на то, что я намерен делать. Я не прошу об исправлении моей программы (я даже не мог сообщить об этом), но о решении, которое лучше использует parse и создает код более четко.

1 Ответ

5 голосов
/ 13 января 2020

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

"Reboli sh" - это остаться прагматичным c, начать с вариантов использования и позволить проблемной области руководить вами - возможно, вы решаете Эйлера спроектируйте и вам нужна библиотека теорий множеств c, возможно, вам нужны LINQ-подобные запросы к базе данных, может, это просто ради обучения и удовольствия заново изобретать колесо, кто знает?

Во время размышлений об этом, вы можете понять, что вам на самом деле не нужны списки, и это хорошо! Самый простой код - тот, который никогда не пишется, а самое умное решение - это то, что устраняет проблему в зародыше, переопределяя ее в более простых терминах. конкретная c проблема в уме, и принимая во внимание мой начальный комментарий с вашим последующим редактированием , вот мои 2 ¢:

Начните с грамматики

Понимание списка, как синтаксическая конструкция c, имеет четко определенную форму. Обращаясь к соответствующей странице wiki , можно сразу определить базовую грамматику c: 

set-builder: [expression '| some generator predicate]
expression:  [to '|]
generator:   [word! 'in to [generator | predicate | end]]
predicate:   ['if to end]

Выяснить, что испускать

Вы уже рассмотрели это: для каждого генератора в обозначении построителя множеств нам нужен дополнительный слой foreach; тело внутреннего foreach должно иметь форму <predicate> [<keep> <expression>].

Определить интерфейс

Вместо /flat Я бы использовал /only, так как это хорошо известно идиома. Так как в теле нашей функции много set-word! s, я буду использовать конструктор function: 

list: function [spec [block!] /only][...]

Соедините точки

Выполните шаги ребенка и начните с простого:

  1. Выполните синтаксический анализ spec с set-builder и извлеките соответствующие детали для дальнейшей обработки.
  2. Составьте извлеченные детали вместе.

Шаг 1

Нам нужно соответствующим образом изменить нашу грамматику: добавьте collect / keep, где это необходимо, и счетчик крайних случаев.

Нам нужно извлечь 3 части: выражение, генераторы и сказуемое. Мы можем сгруппировать генераторы, добавив дополнительные collect: 

set-builder: [collect [expression '| collect some generator predicate]]

  1. expression просто: 

    expression: [keep to '|]

  2. Так как predicate, но нам нужно keep if также: 

    predicate: [ahead 'if keep to end]

  3. Но generator сложнее по двум причинам:

    1. Есть такая вещь, как частичное совпадение . Мы не можем просто написать: 

      generator: [keep word! 'in keep to [generator | predicate | end]]

      Когда generator или predicate совпадает внутри to, он будет рекурсивно keep дополнительных данных из-за совпадения word! или to end, что испортит извлеченный блок.

    2. keep ведет себя по-разному в зависимости от количества сохраняемых значений: он сохраняет одно значение как есть, но группирует многие из них вместе. 

      [1 2 3]         -> foreach x [1 2 3] ..., not foreach x 1 2 3 ...
[range [4 5 6]] -> foreach y range [4 5 6] ...

    Итак, нам нужно (a) правило, которое проверяет, что то, на что мы смотрим, действительно является генератором, без извлечения чего-либо (word! 'in должен делать ) и (b) небольшое изменение keep, которое всегда извлечет block! - keep copy dummy-word. И вот: 

    generator: [keep word! 'in keep copy range to [word! 'in | 'if | end]]

Теперь ма sh все это вместе: 

set-builder: [collect [expression '| collect some generator predicate]]
expression:  [keep to '|]
generator:   [keep word! 'in keep copy range to [word! 'in | 'if | end]]
predicate:   [ahead 'if keep to end]

set [expression ranges: clause:] parse spec set-builder

Обратите внимание, что я использую set-word! s внутри блока для подорвать function нашему делу. ranges содержит диапазоны, каждый из которых содержит слово для перебора и сам диапазон. clause - это либо block! (если он присутствовал в spec), либо none! (если его не было).

Шаг 2

Первым делом, мы составляем блок тела из внутреннего foreach: 

body: [<clause> [<keep> <expression>]]

Это приводит к: 

body: compose/deep [(any [clause 'do]) [(pick [keep/only keep] only) (expression)]]

, что охватывает два дополнительных случая: отсутствие предиката (безусловная оценка) и наличие из /only уточнения.

Давайте разберемся, как выглядит каждый последующий слой foreach: 

layer: [foreach <word> <range> <body>]

<word> можно использовать как есть; <range> может быть сращено; <body> является либо body, либо самым внутренним layer. Из-за сращивания диапазона (т.е. отслаивания дополнительного слоя [...] из извлеченных данных) мы не можем использовать compose/only, поэтому нам нужно обернуть <body> в блок и использовать compose/deep: 

layer: [foreach (word) (range) [(body)]]

И последнее: мы извлекали данные сверху донизу, но нам нужно их накапливать наоборот, наслаивая foreach друг на друга, начиная с body. Так что нам нужно reverse блок диапазонов: 

foreach [range word] reverse ranges [...]

Все готово! Теперь просто нажмите collect сверху и проследите body, чтобы перейти на следующую итерацию: 

collect foreach [range word] reverse ranges [body: compose/deep layer]

И все это так: 

list: function [
    "List comprehension"
    spec [block!]
    /only
][
    #1
    set-builder: [collect [expression '| collect some generator predicate]]
    expression:  [keep to '|]
    generator:   [keep word! 'in keep copy range to [word! 'in | 'if | end]]
    predicate:   [ahead 'if keep to end]

    set [expression ranges: clause:] parse spec set-builder

    #2
    body:  compose/deep [(any [clause 'do]) [(pick [keep/only keep] only) (expression)]]
    layer: [foreach (word) (range) [(body)]]

    collect foreach [range word] reverse ranges [body: compose/deep layer]
]

Примеры: 

>> list [as-pair x y | x in [1 2 3] y in [4 5 6]]
== [1x4 1x5 1x6 2x4 2x5 2x6 3x4 3x5 3x6]
>> list/only [reduce [x y] | x in range [1 5] y in range reduce [1 x] if x + y > 4]
== [[3 2] [3 3] [4 1] [4 2] [4 3] [4 4] [5 1] [5 2] [5 3] [5 4] [5 5]]

Это хорошо? Если бы это помогло вам немного попрактиковать красный, парсинг и диалекты, то я думаю, что это может быть. Это плохо? Если так, то вы можете учиться на моих ошибках и делать лучше.

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

Как только вы реорганизовали свой код и довольны им, поделитесь радостью в общедоступном чате Red и получите некоторую обратную связь. А пока, береги себя!

...