如何使用scheme中的符号和列表来处理数据？

Question

我是scheme新手，正在写一个检查规则成对不相交的函数（暂时不完整），我用符号和列表来表示规则语法。大写符号在文法中是非终结符，小写是终结符。我正在尝试检查规则是否通过成对不相交测试。

我基本上会检查规则中是否只有一个唯一终端。如果是这样，则该规则通过成对不相交测试。在方案中，我想通过用小写字母表示终端符号来实现这一点。该规则的一个示例是：
```
'(A <= (a b c))
```
然后我将检查包含 or 的规则的大小写。喜欢：
```
'(A <= (a (OR (a b) (a c))))   
```
最后，我将递归检查非终端。这种情况的规则是
```
'(A <= (B b c))
```
但是，让我卡住的是如何将这些符号用作数据以便对其进行处理和递归。我考虑过将符号转换为字符串，但如果有这样的列表，例如 '(a b c) 我该怎么做？这是我到目前为止达到的结果：
```
#lang racket
(define grammar
   '(A <= (a A b))
    )

(define (pairwise-disjoint lst)
  (print(symbol->string (car lst)))
  (print( cddr lst))
 )
```

Answer 1

由于 grammar 在列表中有一个列表，我认为您必须在调用 symbol->string 之前通过 list? 进行测试（因为正如您发现的那样，symbol->string 不会在列表上工作），否则你可以这样做：

(map symbol->string (flatten grammar))

> '("A" "<=" "a" "A" "b")

编辑： 对于您正在做的事情，我想 flatten 路线可能没有那么有用。所以，每次解析时都通过 list? 进行测试并进行相应处理。

Answer 2

成对不相交

据我所知，检查集合是否成对不相交的唯一方法是枚举所有可能的对并检查匹配项。请注意，这不符合 racket 语法，但意思应该还是很清楚的。

(define (contains-match? x lst)
  (cond ((null? x) #f)           ; Nothing to do
        ((null? lst) #f)         ; Finished walking full list
        ((eq? x (car lst)) #t)   ; Found a match, no need to go further
        (else
          (contains-match? x (cdr lst))))) ; recursive call to keep walking

(define (pairwise-disjoint? lst)
  (if (null? lst) #f
    (let ((x (car lst))         ; let inner vars just for readability
          (tail (cdr lst)))
      (not
        ;; for each element, check against all later elements in the list
        (or (contains-match? x tail)
            (contains-match? (car tail) (cdr tail)))))))

我不清楚你还想做什么，但这将是通用方法。根据您的数据，您可能需要使用不同的（甚至是定制的）检查是否相等，但这对于普通符号是有效的：

]=> (pairwise-disjoint? '(a b c d e))
;Value: #t

]=> (pairwise-disjoint? '(a b c d e a))
;Value: #f

符号和数据

这部分是基于我认为 OP 对方案基础知识的相当根本的误解，以及对他们的实际目标是什么的一些猜测。 如果接下来的内容对您没有帮助，请澄清问题！

However, What is keeping me stuck is how to use those symbols as data...

在方案中，您可以将符号与您想要的任何内容相关联。事实上，define 关键字实际上只是告诉解释器 "Whenever I say contains-match? (which is a symbol) I'm actually referring to this big set of instructions over there, so remember that." 解释器通过将符号和它所指的东西存储在一个大的 table 中来记住这一点，以便以后可以找到它。

每当解释器遇到一个符号时，它会在它的 table 中查看它是否知道它的实际含义并替换为实际值，在本例中是一个函数。

]=> pairwise-disjoint?
;Value 2: #[compound-procedure 2 pairwise-disjoint?]

我们告诉解释器将符号保持在原位，而不是使用引号运算符 ' 或 (quote ...):

进行替换

]=> 'pairwise-disjoint?
;Value: pairwise-disjoint?

综上所述，出于您的目的使用 define 可能是一个非常糟糕的决定，原因与全局变量通常不好的原因相同。

为了保留对语法很重要的所有特定符号的定义，您可能正在寻找类似 hash table 的东西，其中您知道的每个符号都是一个键，其细节是相关联的值。

而且，如果你想传递符号，你真的需要理解 quote 和 quasiquote。

一旦你在某个地方找到了你的定义，你唯一剩下的工作就是像我上面那样写一些可能更适合你的特定情况的东西。

Answer 3

数据类型

如果您有终端和非终端，为什么不为每个创建数据类型？在 #lang racket 中引入新数据类型的方法是 struct.

;; A Terminal is just has a name. 
(struct Terminal (name))

;; A Non-terminal has a name and a list of terms
;; The list of terms may contain Terminals, Non-Terminals, or both.
(struct Non-terminal (name terms))

处理非终端

现在我们可以使用谓词 Terminal? 在非终端的术语列表中找到终端，当我们将终端定义为 struct.

时自动提供该谓词

(define (find-terminals non-terminal)
  (filter Terminal? (Non-terminal-terms non-terminal)))

成对不相交的终端

一旦我们过滤了术语列表，我们就可以确定属性：

;; List(Terminal) -> Boolean
define (pairwise-disjoint? terminals)
  (define (roundtrip terms)
    (set->list (list->set terms)))
  (= (length (roundtrip terminals) 
     (length terminals))))

往返 list->set->list 不一定针对速度进行优化，当然，分析实际工作实施可能证明重构是合理的，但至少它被黑盒化了。

备注

使用 struct 定义数据类型提供了各种选项，用于在实例化类型时验证数据。如果你查看 Racket 代码库，你会发现 struct 在最近的部分中被频繁使用。

如何使用scheme中的符号和列表来处理数据？

How to use symbols and lists in scheme to process data?

scheme

racket

grammar

bnf

成对不相交

符号和数据

数据类型

处理非终端

成对不相交的终端

备注