标签: lambda-calculus

在"类型和编程语言"的6.1.2节中,他们讨论了用于对lambda表达式中的自由变量进行编号的命名上下文.使用示例方案,他们已经提供了,都?x.xb和?x.xx都会有自己的德布鲁因表示形式?.00时,他们明显不同的术语.这是如何运作的？

我curry在JavaScript中编写了一个简单的函数,可以在大多数情况下正常工作

const add = curry((a, b, c) => a + b + c);

const add2 = add(2);

const add5 = add2(3);

console.log(add5(5));

<script>
const curried = Symbol("curried");

Object.defineProperty(curry, curried, { value: true });

function curry(functor, ...initArgs) {
    if (arguments.length === 0) return curry;

    if (typeof functor !== "function") {
        const value = JSON.stringify(functor);
        throw new TypeError(`${value} is not a function`);
    }

    if (functor[curried] || initArgs.length >= functor.length)
        return functor(...initArgs);

    const result = (...restArgs) => curry(functor, ...initArgs, ...restArgs);

    return …

我正在阅读实现函数式语言:一个教程,并在实现完全懒惰的lambda提升的浮动传递时遇到了问题.

我想描述浮动如何使这个问题清楚,如果你熟悉它,只需跳到下面的问题.

该概念在本文的第246页介绍,主要在第256-257页实施.

在let(rec)表达的情况下,它说:

我们必须在let(rec)表达本身之前放置右侧的浮动定义,因为右侧可能依赖于它们.

例如:

\a ->
  let f = \b -> b + (let $mfe = a * a in $mfe)
  in f

变量$mfe是一个最大自由表达式(MFE),它通过前一次传递识别,当处理let f表达式时,我们f作为一个组浮出并附加到它[(1, [($mfe, a * a)])],这是从右边获得的let f.这里,第一个组件1表示组的自由级别.

当回溯到\a -> f抽象,我们发现,无论是$mfe和f被它约束,因此我们应该在这里安装它们:

\a ->
  let $mfe = a * a
  in
    let f = \b -> b …

在系统F中,类型exists a. P可以被编码为forall b. (forall a. P -> b) -> b使用存在性的任何系统F术语可以根据关于打字和缩减规则的该编码来表达.

在"类型和编程语言"中,将显示以下练习:

我们可以根据存在类型编码通用类型吗？

我的直觉说这是不可能的,因为在某种程度上,"存在包装"机制并不像"类型抽象"机制那样强大.我如何正式展示这个？

我甚至不确定我需要证明什么才能正式显示这个结果.

我可以理解如何创建和思考SKI和BCKW演算,但我永远无法找到实际用途.也许我看得不够深？也就是说,我想知道(仅仅是一个例子,我并不是暗示这是真的)Java Servlets广泛使用S而Python生成器是BCW的一个例子,我只是无法透过树林看到它？

我试图使用定义在haskell中打印教堂数字:

0 := ?fx.x
1 := ?fx.f x

Haskell代码:

c0 = \f x -> x
c1 = \f x -> f x

当我在haskell控制台中输入它时,我得到一个错误

    test> c1

    <interactive>:1:0:
    No instance for (Show ((t -> t1) -> t -> t1))
      arising from a use of `print' at <interactive>:1:0-1
    Possible fix:
      add an instance declaration for (Show ((t -> t1) -> t -> t1))
    In a stmt of an interactive GHCi command: print it

我无法弄清楚错误说的是什么.

谢谢!

我记得在某处读过Hindley Milner是对system-f的限制.如果是这种情况,有人可以请我提供一些可以输入system-f但不能输入HM的条款.

我在Haskell编程中的冒险并非都是史诗般的.我正在实施Simple Lambda Calculus,我很高兴完成Syntax,Evaluation并且Substitution希望它们是正确的.剩下的是typing红色框内的定义(如下图所示),我正在寻找指导.

标题

如果我错了,请纠正我,

(1)但我收集的是(T-Var),返回给定变量的类型x.Haskell中的构造返回type什么？我知道prelude它是:t x,但我正在寻找一个有效的main = do.

(2)如果我要定义一个函数type_of,我最有可能需要定义期望和返回类型,例如, type_of (Var x) :: type1 -> type2

type1应该是通用的,并且type2必须是存储变量类型信息的任何对象类型.为此,我迷失了如何定义type1和type2.

(3)对于(T-APP)和(T-ABS),我假设我分别应用替换 Abstraction String Lambda 和Application Lambda Lambda.简化形式的类型是返回的类型.那是对的吗？

提前致谢...

你如何使用GADT在OCaml中定义一个简单的lambda演算类DSL？具体来说,我无法弄清楚如何正确定义类型检查器以从无类型的AST转换为类型化的AST,也无法找出上下文和环境的正确类型.

下面是一些使用OCaml中传统方法的简单lambda演算语言的代码

(* Here's a traditional implementation of a lambda calculus like language *)

type typ =
| Boolean
| Integer
| Arrow of typ*typ

type exp =
| Add of exp*exp
| And of exp*exp
| App of exp*exp
| Lam of string*typ*exp
| Var of string
| Int of int
| Bol of bool

let e1=Add(Int 1,Add(Int 2,Int 3))
let e2=Add(Int 1,Add(Int 2,Bol false)) (* Type error *)
let e3=App(Lam("x",Integer,Add(Var "x",Var "x")),Int 4)

let rec typecheck con e …

让这些数据类型分别代表一元和二元自然数:

data UNat = Succ UNat | Zero
data BNat = One BNat | Zero BNat | End

u0 = Zero
u1 = Succ Zero
u2 = Succ (Succ Zero)
u3 = Succ (Succ (Succ Zero))
u4 = Succ (Succ (Succ (Succ Zero)))

b0 = End                   //   0
b1 = One End               //   1
b2 = One (Zero End)        //  10
b3 = One (One End)         //  11
b4 = One (Zero (Zero End)) // 100

(Alternatively, one could use …