时间戳

首页 > 解决方案 > Rebol 中用于列表理解的“编译器”

list-comprehension - Rebol 中用于列表理解的“编译器”

问题描述

我想编译这个列表理解：

>> 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]

在：

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

我在 Red 中的丑陋实现是：

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
]

该程序不流动，它充满了变量，if和append（我在parse时遇到了困难；在这种情况下， compose是有限的）。
有没有更“rebo​​lish”的方式（在 rebol2/rebol3/red/ren-c 中）来解决这个问题？

更新：我对“编译器”的实现只是表明我打算做什么。我不是要求更正我的程序（我什至无法报告它），而是要求更好地使用解析并更清晰地构建代码的解决方案。

标签： list-comprehensiondslrebolred

解决方案

列表理解是方言构建的一个很好的练习：它的大小适中，有明确的目的，一般来说，它可以作为有抱负的年轻蚱蜢的代码 kata——没有单一的“正确”方法可以做到这一点，但很多更好或更差的解决方案。

“Rebolish”的方式是保持务实，从用例开始，让问题域指导你——也许你正在解决 Euler 项目并且需要一个集合论库，也许你想要的是类似 LINQ 的数据库查询，也许只是为了学习和重新发明轮子的乐趣，谁知道呢？

在考虑它的同时，您可能会意识到您实际上不需要列表推导，这很好！最精简的代码是永远不会被编写的代码，而最聪明的解决方案是通过用更简单的术语重新定义问题来将问题扼杀在萌芽状态。

假设您只是涉足元编程或学习 Red 而没有任何具体问题，并考虑到我的初步评论和您随后的编辑，这是我的 2 美分：

从语法开始

列表理解，作为一种句法结构，具有明确定义的形式。查阅相应的wiki页面可以立即定义基本语法：

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

弄清楚要发射什么

您已经了解了这一点：对于 set-builder 表示法中的每个生成器，我们需要一个额外的foreach;层。inner 的 bodyforeach应该 有 形式<predicate> [<keep> <expression>].

定义一个接口

而不是/flat我会使用/only，因为这是一个众所周知的成语。由于我们的函数体中有很多set-word!s，我将使用function构造函数：

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

将点连接

循序渐进，从简单开始：

  1. 解析specwithset-builder并提取相关部分以进行进一步处理。
  2. 将提取的部分组合在一起。

步骤1

我们需要相应地修改我们的语法：在需要的地方添加collect/keep并对抗边缘情况。

我们需要提取 3 个部分：表达式、生成器和谓词。我们可以通过添加一个额外的来将生成器组合在一起collect：

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

  1. expression很简单：

    expression: [keep to '|]

  2. 因此，但predicate我们还需要：keepif

    predicate: [ahead 'if keep to end]

  3. 但generator更棘手，有两个原因：

    1. 有一种东西叫做部分匹配。我们不能只写：

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

      当generatororpredicate匹配在里面时，它会因为or匹配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]]

现在将所有这些混合在一起：

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是 a block!（如果它存在于 中spec）或none!（如果不存在）。

第2步

首先，我们组成 inner 的主体块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>是 abody或 innermost 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]]

好吗？如果它可以帮助您稍微了解 Red、Parse 和方言，那么我认为它可能会。不好吗？如果是这样，那么您可以从我的错误中吸取教训并做得更好。

在任何情况下，如果您发现自己在 Parse 方面遇到困难，您可能想浏览一下管道中的参考文档parse，以及可以寻求帮助的 Gitter 房间。

一旦你重构了你的代码并且对它感到满意，请在 Red社区聊天中分享快乐并获得一些反馈。在那之前，保重！

推荐阅读