有什么方法可以在 Typed Racket 中声明一个表示所有可调用过程（任何可调用过程）的类型？

Question

我正在使用 Typed Racket 开发 SICP 的 metacircular-evaluator，但在使用符号和过程对象的缺点列表预先准备原始过程时卡住了。在书中，作者准备了如下的原始过程，但是，当我在 Typed Racket 中模仿它并在其上定义访问器时，我根本无法提取过程或符号，因为我需要使用我指定的类型显式实例化 car 或 cdr不能写下来，即列表中所有过程类型的并集。所以我想，如果我可以声明一个代表所有可调用过程的类型（没有关键字参数但有剩余参数），我最终可以注释下面的列表。我认真地用谷歌搜索并自己尝试了很多方法，但我没有想出好主意。任何人都可以想出一种定义这种类型的好方法吗？或者更好的是，任何人都可以想出一个更好的主意来准备所有原始程序吗？

(define primitive-procedures
    (list (cons 'car car)
          (cons 'cdr cdr)
          (cons 'list list)
          ...))

Answer 1

问题在于尝试将一组异构函数类型放入同构列表类型/同构查找结果类型。

在评论中您注意到您不能给出类型 primitive-procedures : (All (a b) (Listof (Pairof Symbol (-> a * b))) 因为声明的类型不同于实际列表中的每个过程。您可能尝试添加 All 因为您试图在其中容纳所有异构类型。但是 Listof 类型，更重要的是 lookup 用于从列表中获取基元的函数，具有基本相同的类型。您必须使类型同构并解决列表中的类型。

如果您的目标语言中的值与元循环解释器的宿主相同，则此同类函数类型的最简单选择是 (-> Any * Any)。

(: primitive-procedures : (Listof (Pairof Symbol (-> Any * Any))))
(: lookup-primitive : (-> (Listof (Pairof Symbol (-> Any * Any))) Symbol (-> Any * Any)))

那么使用lookup-primitive应该没问题，使用apply。然而最复杂的部分是primitive-procedures这个齐次类型的定义。

正在使用

(define primitive-procedures
  (list (cons 'car car)
        (cons 'cdr cdr)
        (cons 'list list)
        ...))

不够，类型不匹配。

car 不能用作 (-> Any * Any)。它可以用作 (-> (Pairof Any Any) Any).
cdr 不能用作 (-> Any * Any)。它可以用作 (-> (Pairof Any Any) Any).
list可以当(-> Any * Any)使用。不错。

所以我们必须以某种方式包装 car 和 cdr，在将参数传递给 car 和cdr.

(lambda [args : Any *]
  (match args
    [(list arg)
     (unless (pair? arg) (error 'car "wrong argument type"))
     (car arg)]
    [_
     (error 'car "wrong number of arguments")]))

现在这个 lambda 表达式可以用作 (-> Any * Any)，但它很笨重。更糟糕的是，当你认为我们必须对每个还不适合的基元执行此操作时：

(define primitive-procedures
  (list (cons 'car (lambda [args : Any *]
                     (match args
                       [(list arg)
                        (unless (pair? arg) (error 'car "wrong argument type"))
                        (car arg)]
                       [_
                        (error 'car "wrong number of arguments")])))
        (cons 'cdr (lambda [args : Any *]
                     (match args
                       [(list arg)
                        (unless (pair? arg) (error 'cdr "wrong argument type"))
                        (cdr arg)]
                       [_
                        (error 'cdr "wrong number of arguments")])))
        (cons 'list list)
        ...))

这段代码很丑，而且重复了很多次。我会定义一个名为 prim 的宏来为我执行此模式：

(require syntax/parse/define)

(define-simple-macro (prim (arg-pred ...) proc)
  #:with (arg-id ...) (generate-temporaries #'(arg-pred ...))
  (lambda [args : Any *]
    (match args
      [(list arg-id ...)
       (unless (arg-pred arg-id) (error 'proc "wrong argument type")) ...
       (proc arg-id ...)]
      [_
       (error 'proc "wrong number of arguments")])))

然后我们可以在primitive-procedures中使用它，比如

(define primitive-procedures
  (list (cons 'car (prim (pair?) car))
        (cons 'cdr (prim (pair?) cdr))
        (cons 'list list)
        ...))

现在终于用齐次类型定义了(Listof (Pairof Symbol (-> Any * Any)))。

有什么方法可以在 Typed Racket 中声明一个表示所有可调用过程（任何可调用过程）的类型？

Is there any way to declare a type representing all the callable procedures(any procedure which is callable) in Typed Racket?

scheme

racket

typed-racket