一个同态 lambda 演算解释器

主要观点:作者在研究recursion-schemes,思考能否将其用于 lambda 演算,最终得出相关实现。
关键信息:

  • 定义了LambdaF函子和Lambda固定点类型,用于表示 lambda 演算的项。
  • 决定将项求值为suspended computation,定义了Value数据类型来表示求值结果。
  • 编写了evalAlgebra代数,用于处理LambdaF的各种情况,实现了 lambda 演算的求值。
  • 定义了EnvM新类型,满足特定的MonadReader约束,用于求值Lambda
  • 给出了SKI组合子的定义,并验证了其正确性。
    重要细节:
  • 使用 de-Bruijn 索引简化表示。
  • evalAlgebra中对抽象体的处理,将其求值为m (Value m)并放入闭包。
  • EnvM的定义和实例,用于满足求值的约束条件。
  • 示例中对ks组合子的求值验证。
阅读 13
0 条评论