6 个版本 (3 个破坏性更新)

使用旧的 Rust 2015

0.4.0 2018年10月6日
0.3.0 2018年9月8日
0.2.1 2018年8月26日
0.1.1 2018年8月25日

#507 in 科学

Apache-2.0

270KB
5.5K SLoC

Lamcal REPL

Crates.io Docs.rs Linux Build Status Windows Build Status codevoc.io Apache-2.0

lamcal-repl 是一个用 Rust 编写的 Lambda Calculus REPL 命令行应用程序。它可以用于交互式地玩转 lambda 演算表达式。

这个应用程序受到了 glebec 的这个 演讲 的启发,他在 JavaScript 控制台中玩转 lambda 演算。

lamcal-repl 使用 lamcal 库 crate 的 lambda 演算功能,并添加了 REPL 功能,使其成为一个应用程序。可执行文件名为 lamcali

安装

要安装 lamcal-repl 命令行应用程序,请在您的终端中运行以下命令

> cargo install lamcal-repl

安装成功后,我们可以通过键入可执行文件名来运行 lamcal-repl

> lamcali

或者,我们可以克隆这个 Git 仓库,进入 repl 子目录,然后键入 cargo run,如下所示

> cd lamcal/repl
lamcal/repl> cargo run

用法

当应用程序启动时,我们在命令行中看到以下内容

info: Welcome to lamcal-repl, the Lambda Calculus REPL, version 0.3.0
λ>

请注意,命令行提示符变为 λ>。要评估 lambda 表达式,我们只需在提示符中键入表达式,如下所示

λ> (\x.(\y.x y) a) b

按下回车键后,表达式将被解析,并应用默认的 α-转换和 β-归约。结果将打印到控制台,如下所示

λ> (\x.(\y.x y) a) b
b a

我们可以使用反斜杠字符 \ 或希腊小写字母 λ 来表示 lambda 抽象的 lambda 表达式。解析器理解反斜杠和 lowercase lambda 符号作为抽象的开始。

REPL 支持控制应用程序行为的命令。命令始终以冒号开头。最重要的命令包括

  • :h:help 打印帮助信息
  • :q:quit 退出应用程序

所有实现的命令列表可以在帮助信息中找到(命令 :h)。

let 绑定和环境

当处理更复杂的表达式时,手动输入可能会很繁琐。因此,lamcal 包提供了在预定义项绑定到名称的环境中评估项的可能性。在 REPL 启动时,它将默认环境实例化为全局环境。默认情况下,在评估表达式时使用全局环境。

要向环境中添加新的绑定或替换现有的绑定,我们使用 :let 命令。例如,以下命令将 rev 名称绑定到项 λf.λa.λb.f b a

λ> :let rev = λf.λa.λb.f b a

现在,当我们将在任何表达式中作为自由变量使用 rev 时,它将被等号右侧的整个表达式替换。

λ> rev
λf.λa.λb.f b a

λ> rev f x y
f y x

最后的评估等同于输入

λ> (λf.λa.λb.f b a) f x y
f y x

如果我们想在展开绑定名称之前执行 beta-缩减,我们可以使用 :b 命令

λ> :b (λa.rev a) f x y
rev f x y

要展开绑定名称而不缩减项,我们可以使用 :x 命令

λ> :x (λa.rev a) f x y
(λa.(λf.λa.λb.f b a) a) f x y

检查模式

在检查模式下,我们可以跟踪展开和缩减的每一步。要打开检查模式,我们输入命令 :i

λ> :i
Inspected mode switched on

现在当我们评估一个表达式时,每个步骤的中间结果都会打印到终端

λ> I x
I x
(λa.a) x
x

首先 I 扩展为恒等项 (λa.a),然后将其应用于变量 x,结果为 x。酷吧!不是吗?要关闭检查模式,只需再次输入命令 :i 即可。

命令

以下命令可用

:h or :help       displays this help information

:q or :quit       quits the repl session

:v or :version    prints out the version of lamcali

:i or :inspected  toggle inspected mode on and off. In inspected mode the
                  result of each step during evaluation or reduction is
                  printed to the terminal.

:e <expr> or :eval <expr>
                  evaluates the lambda expression <expr>. This command is
                  equivalent to just typing a lambda expression and
                  pressing [enter].

:b <expr> or :beta <expr>
                  performs a beta-reduction on the lambda expression <expr>
                  using the current set strategy.

:x <expr> or :expand <expr>
                  replaces free variables in the lambda expression <expr>
                  with the expression bound to the variable's name in the
                  current environment.

:p <expr> or :parse <expr>
                  parses the lambda expression <expr> and prints out the
                  abstract syntax tree (AST) of the lambda expression.

:bs or :beta-strategy
                  prints the current set beta-reduction strategy.

:bs <strategy> or :beta_strategy <strategy>
                  set the beta-reduction strategy to <strategy>.
                  <strategy> can be one of:
                  app : applicative-order reducing to normal form
                  cbn : call-by-name reducing to weak head normal form
                  cbv : call-by-value reducing to weak normal form
                  hap : hybrid-applicative-order reducing to normal form
                  hno : hybrid-normal-order reducing to normal form
                  hsp : head-spine reducing to head normal form
                  nor : normal-order reducing to normal form (the default)

:as or :alpha-strategy
                  prints the current set alpha-conversion strategy.

:as <strategy> or :alpha-strategy <strategy>
                  set the alpha-conversion strategy to <strategy>.
                  <strategy> can be one of:
                  enumerate : appending increasing digits (the default)
                  prime     : appending tick symbols

:let <name> = <expr>
                  defines a new binding of <expr> to <name> and adds it to
                  the environment. If a binding with the same name
                  previously existed in the environment it is replaced by
                  the new binding.

:clr-env          clears the environment, all bindings are removed

:ld-env default   loads the default set of predefined bindings into the
                  environment. Existing bindings with the same name as a
                  binding in the default set will be replaced. Existing
                  bindings with no name clash will not be changed.

:ls-env           lists all bindings defined in the environment

:ls-env <pattern> lists all bindings filtered by <pattern>. It lists all
                  bindings with a name that contains the given pattern as a
                  substring (ignoring case).

许可

根据 Apache 许可证第 2 版许可
有关详细信息,请参阅 LICENSEhttp://apache.ac.cn/licenses/LICENSE-2.0

贡献

除非您明确声明,否则根据 Apache-2.0 许可证定义的任何有意提交以包含在您的工作中的贡献,应按上述方式许可,不附加任何其他条款或条件。


依赖关系

~4–12MB
~133K SLoC