lisp自动生成中垂线_【翻译】自动柯里化Rust函数-白红宇

lisp自动生成中垂线_【翻译】自动柯里化Rust函数

阅读量：4579 次

发布时间：2019-06-08

本文共 15516 字，大约阅读时间需要 51 分钟。

原文标题: Auto-currying Rust Functions

原文链接: https:// peppe.rs/posts/auto-cur rying_rust_functions/

公众号: Rust碎碎念

本文包含Rust中过程宏(procedural macros)的介绍示例和通过过程宏柯里化Rust函数的指导。整个库的源码可以在这里[1]找到。在http://crate.io上也可以找到。

在开始之前，阅读下面的链接会有助于理解:

过程宏(Procedural Macros)[2]

柯里化(Currying)[3]

或者你也可以假装已经阅读了上面的文章，因为我这里已经包含了基本介绍。

内容

柯里化(Currying)

过程宏

定义

改进

插曲

5.1 依赖

5.2 属性宏

5.3 函数体

5.4 函数签名

调试和测试

注意事项

总结

柯里化(Currying)

柯里化是指把形如f(a, b, c)的函数转换为 f(a)(b)(c)的过程。一个被柯里化的函数只有在它接收到所有的参数之后才会返回一个具体的值！如果它没有接受到足够数量的参数，比如3个参数中的1个，它仍然返回一个柯里化的函数，该函数会在收到剩余2个参数之后返回。

curry(f(a, b, c)) = h(a)(b)(c)h(x) = g   <- curried function that takes upto 2 args (g)g(y) = k   <- curried function that takes upto 1 arg (k)k(z) = v   <- a value (v)Keen readers will conclude the following,h(x)(y)(z) = g(y)(z) = k(z) = v

从数学上来讲，如果f是一个接收参数为x和y的函数, 使x ∈ X, y ∈ Y :

f: (X × Y) -> Z

其中 × 表示集合X和集合Y进行笛卡尔乘积，柯里化的f(这里标记为h)表示为:

h: X -> (Y -> Z)

过程宏(Procedural Macros)

它以代码作为输入，以修改后的代码作为输出。 Rust有三种过程宏:

函数风格的宏

继承宏: #[derive(...)], 常被用于为结构体/枚举自动地实现trait

属性宏: #[test], 通常附着在函数上

我们将会使用属性宏来对Rust函数进行柯里化，即变成通过function(arg1)(arg2)这种方式来调用的函数。

定义(Definitions)

作为受人尊敬的程序员，我们定义了输入以及过程宏的输出。我们从一个比较特别的函数开始:

fn add(x: u32, y: u32, z: u32) -> u32 {  return x + y + z;}

我们的输出会是什么样子？理想情况下我们的过程宏应该生成什么？如果我们正确理解了柯里化，我们应该接收一个参数并且返回一个接收一个参数的函数，然后这个函数返回一个...你应该懂了，就像下面这样:

fn add_curried1(x: u32) -> ? {  return fn add_curried2 (y: u32) -> ? {    return fn add_curried3 (z: u32) -> u32 {      return x + y + z;    }  }}

有几件事需要注意:

返回类型(Return types)

我们用?替代了返回类型。让我们尝试修正它。 add_curried3返回了一个值，所以这里返回u32是准确的。 add_curried2返回了add_curried3, 所以add_curried3的类型是什么？它是一个函数，以u32作为参数并返回一个u32，所以fn(u32)->u32正确么？不，接下来我将会解释原因，但是现在，我们将会利用Fntrait，让我们的返回类型impl Fn(u32)->u32。这基本上是在告诉编译器我们将会返回类似函数的东西，行为就像Fn, 酷！

如果你已经跟上来了，你应该就能猜到add_curried1的返回类型是

impl Fn(u32) -> (impl Fn(u32) -> u32)

我们可以丢掉外面的括号，应该->是右关联的:

impl Fn(u32) -> impl Fn(u32) -> u32

访问上下文环境(Accessing environment)

函数是不能访问周围上下文环境的。我们的方案无法生效。add_curried3尝试访问x，这是不被允许的! 但是闭包[4]可以。如果我们返回一个闭包，我们返回类型就必须impl Fn而不是fn。 Fntrait和函数指针的区别已经超出本文范围，不再讨论。

改进(Refinement)

掌握了上述知识，我们改进期望的输出去，这一次，我们使用闭包:

fn add(x: u32) -> impl Fn(u32) -> impl Fn(u32) -> u32 {  return move |y| move |z| x + y + z;}

但是这样无法编译通过，编译器报出下面的错误信息:

error[E0562]: `impl Trait` not allowed outside of functionand inherent method return types  --> src/main.rs:17:37   |   | fn add(x: u32) -> impl Fn(u32) -> impl Fn(u32) -> u32   |

只能在函数内部返回一个impl Fn。我们现在是从另一个返回里返回。至少，这是我从错误信息里获得的最多的理解。

我们不得不通过欺骗编译器来修正这个问题；通过使用类型别名(type aliase)和nightly版本中的一个特性[5]。

#![feature(type_alias_impl_trait)]  // allows us to use `impl Fn` in type aliases!type T0 = u32;                 // the return value when zero args are to be appliedtype T1 = impl Fn(u32) -> T0;  // the return value when one arg is to be appliedtype T2 = impl Fn(u32) -> T1;  // the return value when two args are to be appliedfn add(x: u32) -> T2 {  return move |y| move |z| x + y + z;}

把上面的代码丢到cargo工程里，然后调用add(4)(5)(6), 祈求成功，然后运行cargo +nightly run。你应该看到一个15，除非你忘记打印它。

插曲(The In-Betweens)

让我们写一些能够把函数进行柯里化的神奇的片段。使用cargo new --lib currying初始化你的工作空间。过程宏crates是只把自身进行导出的库。在crate根目录下添加一个tests目录。你的目录看起来应该像下面这样:

.├── Cargo.toml├── src│   └── lib.rs└── tests    └── smoke.rs

依赖(Dependencies)

我们总共将会使用3个外部的crate：

proc_macro2[6]

syn[7]

quote[8]

这里是Cargo.toml的示例:

# Cargo.toml[dependencies]proc-macro2 = "1.0.9"quote = "1.0"[dependencies.syn]version = "1.0"features = ["full"][lib]proc-macro = true  # this is important!

我们将会使用一个外部的proc-macro2 create, 和一个内部的proc-macrocrate。对此无需困惑。

属性宏(The attribute macro)

把下面这些丢进src/lib.rs, 准备开始。

// src/lib.rsuse proc_macro::TokenStream;  // 1use quote::quote;use syn::{parse_macro_input, ItemFn};#[proc_macro_attribute]   // 2pub fn curry(_attr: TokenStream, item: TokenStream) -> TokenStream {  let parsed = parse_macro_input!(item as ItemFn);  // 3  generate_curry(parsed).into()  // 4}fn generate_curry(parsed: ItemFn) -> proc_macro2::TokenStream {}

1. 导入(Imports)

一个Tokenstream包含(希望是有效的)Rust代码，这是我们输入和输出的类型。注意，我们是从proc_macro而不是proc_macro2导出这个类型。quotecrate里的quote!是一个能够让我们快速生成TokenStream的宏。和LISP的quote过程很想，你可以使用quote!宏来进行符号转换。syncrate中的ItemFn含有被解析的一个Rust函数里的TokenStream。 parse_macro_input!是syn提供的一个很有用的宏。

2. 单独导出(The lone export)

使用#[proc_macro_attribute]来标注我们的crate中的pub部分。这告诉rustccurry是一个过程宏，并且我们能够在其他的crate中通过#[crate_name::curry]来使用它。注意curry函数的签名。_attr是代表属性自身的TokenStream,item表示我们要把宏改造成的事物，在这个例子中是个函数(比如add)。返回值是被修改后的TokenStream, 这将会包含我们对add进行柯里化的版本。

3. 辅助宏(The helper macro)

一个TokenStream难以完成工作，这也是为什么我们要有一个能够为Rust符号提供表达类型的syncrate。一个RArrow结构体表示一个函数后面的返回箭头符号，诸如此类。其中一个类型就是ItemFn，它表示一整个Rust函数。parse_macro_input!自动把宏的输入放入ItemFn。

4. 返回TokenStreams(Returning TokenStreams)

我们还没有完善generate_curry，但是我们能看到它返回一个proc_macro2::TokenStream而不是proc_macro::TokenStream, 所以我们使用一个.into()来进行转换。

让我们继续完善generate_curry, 我会建议你打开syn::ItemFn[9]和syn::Signature[10]的文档。

// src/lib.rsfn generate_curry(parsed: ItemFn) -> proc_macro2::TokenStream {  let fn_body = parsed.block;      // function body  let sig = parsed.sig;            // function signature  let vis = parsed.vis;            // visibility, pub or not  let fn_name = sig.ident;         // function name/identifier  let fn_args = sig.inputs;        // comma separated args  let fn_return_type = sig.output; // return type}

我们简单地导出这个函数的片段，我们将会重用原始函数的可见性和名字。来看看syn::Signature可以告诉我们一个函数的什么有关信息:

.-- syn::Ident (ident)                      /                 fn add(x: u32, y: u32) -> u32  (fn_token)      /     ~~~~~~~,~~~~~~  ~~~~~~syn::token::Fn --'            /                      (output)                             '                 `- syn::ReturnType             Punctuated
     
       (inputs)

分析得差不多了，让我们写下第一段Rust代码。

函数体(Function Body)

回想一下，柯里化的add函数应该是像下面这样:

return move |y| move |z| x + y + z;

更通用一点:

return move |arg2| move |arg3| ... |argN|

在generate_curry函数里，我们已经有了由fn_body提供的函数体。接下来要做的就是把move |arg2| move |arg3| ...这些东西添加进去，要完成这个目标，我们需要导出参数的标识(文档:Punctuated[11]，FnArg[12]，PatType[13])：

// src/lib.rsuse syn::punctuated::Punctuated;use syn::{parse_macro_input, FnArg, Pat, ItemFn, Block};fn extract_arg_idents(fn_args: Punctuated
     
      ) -> Vec
      
       
        > {   return fn_args.into_iter().map(extract_arg_pat).collect::
        
         <_>>();}

好吧，所以我们正在遍历函数的参数(Punctuated是一个你可以进行遍历的集合)并且把extract_arg_pat映射到每一项。extract_arg_pat是什么？

// src/lib.rsfn extract_arg_pat(a: FnArg) -> Box
     
       {  match a {    FnArg::Typed(p) => p.pat,    _ => panic!("Not supported on types with `self`!"),  }}

或许你已经猜到，FnArg是一个枚举类型。Typed变量包含一些形式为name:type的参数和其他的变量，Receiver指向self类型。现在先忽略这些，保持简单。

每个FnArg::Typed值包含一个pat，从本质上讲，pat是参数的名字。参数的类型可以通过p.ty来获取(我们会在后面用到)。

了解上述内容后，我们应该能够写出函数体的代码生成：

// src/lib.rsfn generate_body(fn_args: &[Box
     
      ], body: Box
      
       ) -> proc_macro2::TokenStream {  quote! {    return #( move |#fn_args|  )* #body  }}

这些语法令人感到恐怖。容我来解释一下。quote!{ ... }返回一个proc_macro2::TokenStream，如果我们写quote!{ let x = 1 + 2; }，这不会创建一个值为3的变量x,它只会产生关于这个表达式的一个符号流。#能够插入变量。#body将会在当前域中查找body，获取它的值，然后在返回的TokenStream中将其插入。有点像LISP中的准引用。

那么#( move |#fn_args| )*是什么呢？这是重复。 quote遍历fn_args，然后在每一个参数前面加上一个move,然后在参数两边放上竖线|。

让我们先测试一段代码生成！把generate_curry修改成下面这样:

// src/lib.rs fn generate_curry(parsed: ItemFn) -> TokenStream {   let fn_body = parsed.block;   let sig = parsed.sig;   let vis = parsed.vis;   let fn_name = sig.ident;   let fn_args = sig.inputs;   let fn_return_type = sig.output;+  let arg_idents = extract_arg_idents(fn_args.clone());+  let first_ident = &arg_idents.first().unwrap();+  // remember, our curried body starts with the second argument!+  let curried_body = generate_body(&arg_idents[1..], fn_body.clone());+  println!("{}", curried_body);   return TokenStream::new(); }

在tests/目录下加上测试:

// tests/smoke.rs#[currying::curry]fn add(x: u32, y: u32, z: u32) -> u32 {  x + y + z}#[test]fn works() {  assert!(true);}

你应该能在cargo test的输出里找到一些类似下面这样的内容:

return move | y | move | z | { x + y + z }

极好的println!调试!

函数签名(Function signature)

这一部分将要深入宏更复杂的部分-生成类型别名和函数签名。到了这部分结尾，我们就能拥有一个可以完整工作的自动柯里化的宏！

回顾一下，对于我们的add函数，生成的类型别名应该看起来是什么样子：

type T0 = u32;type T1 = impl Fn(u32) -> T0;type T2 = impl Fn(u32) -> T1;

更通用一点儿:

type T0 = 
     
      ;type T1 = impl Fn(
      
       ) -> T0;type T2 = impl Fn(
       
        ) -> T1;...type T(N-1) = impl Fn(
        
         ) -> T(N-2);

要生成上面的内容，我们需要下面这些类型:

所有的输入(参数)

输出(返回类型)

要获取所有输入的类型，我们可以简单地复用之前写过的获取变量名的代码片段(doc: Type[14])

// src/lib.rsuse syn::{parse_macro_input, Block, FnArg, ItemFn, Pat, ReturnType, Type};fn extract_type(a: FnArg) -> Box
     
       {  match a {    FnArg::Typed(p) => p.ty,  // notice `ty` instead of `pat`      _ => panic!("Not supported on types with `self`!"),  }}fn extract_arg_types(fn_args: Punctuated
      
       ) -> Vec
       
        
         > {  return fn_args.into_iter().map(extract_type).collect::
         
          <_>>();}

一个好的读者应该已经看过syn::Signature结构体的输出成员的相关文档。它的类型是syn::ReturnType，所以这里是没有提取操作对么？事实上，这里真的有些事是需要我们确认的：

我们需要确认函数返回值!在这种情况下，一个没有返回的函数是无意义的，我会在最后的注意部分解释原因。

一个ReturnType会关闭返回的箭头，我们需要避免这种情况。回顾:

type T0 = u32// and nottype T0 = -> u32

下面是处理导出返回类型的代码段(doc:syn::ReturnType[15]):

// src/lib.rsfn extract_return_type(a: ReturnType) -> Box
     
       {  match a {    ReturnType::Type(_, p) => p,    _ => panic!("Not supported on functions without return types!"),  }}

你或许已经注意到，我们正在广泛使用panic!宏。很好，这是因为当收到一个不满足条件的TokenStream时执行退出是一个很好的主意。

类型已经准备好了，现在我们可以继续生产类型别名：

// src/lib.rsuse quote::{quote, format_ident};fn generate_type_aliases(  fn_arg_types: &[Box
     
      ],  fn_return_type: Box
      
       ,  fn_name: &syn::Ident,) -> Vec
       
         {    // 1  let type_t0 = format_ident!("_{}_T0", fn_name);    // 2  let mut type_aliases = vec![quote! { type #type_t0 = #fn_return_type  }];  // 3  for (i, t) in (1..).zip(fn_arg_types.into_iter().rev()) {    let p = format_ident!("_{}_{}", fn_name, format!("T{}", i - 1));    let n = format_ident!("_{}_{}", fn_name, format!("T{}", i));    type_aliases.push(quote! {        type #n = impl Fn(#t) -> #p    });  }  return type_aliases;}

1. 返回值

我们正在返回一个Vec<proc_macro2::TokenStream>, 也就是，一个TokenStream列表，其中每一项都一个类型别名。

2. 格式化标识符

我对此有一些解释。显然，我们正在尝试写第一个类型别名，然后用T0初始化我们的TokenStream vector，因为它和其他的不一样。

type T0 = something// the others are of the formtype Tr = impl Fn(something) -> something

format_ident!和format!相似。它返回一个syn::Ident而不是一个格式化后的字符串。因此， type_t0实际上是一个标识符，在我们的例子中，add函数的标识符就是_add_T0。为什么这个格式化很重要？命名空间。

看下面的代码，我们有两个函数，add和subtract，我们希望通过宏对这两个函数进行柯里化。

#[curry]fn add(...) -> u32 { ... }#[curry]fn sub(...) -> u32 { ... }

下面的功能是一样的，但是对宏进行了展开:

type T0 = u32;type T1 = impl Fn(u32) -> T0;fn add( ... ) -> T1 { ... }type T0 = u32;type T1 = impl Fn(u32) -> T0;fn sub( ... ) -> T1 { ... }

我们最终拥有对T0的两个定义。现在，我们进行少量的format_ident!

type _add_T0 = u32;type _add_T1 = impl Fn(u32) -> _add_T0;fn add( ... ) -> _add_T1 { ... }type _sub_T0 = u32;type _sub_T1 = impl Fn(u32) -> _sub_T0;fn sub( ... ) -> _sub_T1 { ... }

类型别名不再互相冲突了。记得要从quotecrate里导出format_ident。

3. The TokenStream Vector

我们以相反的顺序遍历我们的类型(T0是最后的返回， T1是倒数第二个，以此类推)，使用zip对每一次迭代赋一个数字，使用format_ident生成类型别名，使用quote和变量插入把TokenStream送入(vector)。

如果你想知道为什么我们使用(1..).zip()而不是.enumerate()，这是因为我们想要从1开始而不是从0开始(我们已经用过T0了)。

汇总(Getting it together)

我承诺过到最后一部分，我们将会拥有一个能够完成工作的宏。我撒慌了，我们不得不把所有的东西汇总到generate_curry函数里。

// src/lib.rs fn generate_curry(parsed: ItemFn) -> proc_macro2::TokenStream {   let fn_body = parsed.block;   let sig = parsed.sig;   let vis = parsed.vis;   let fn_name = sig.ident;   let fn_args = sig.inputs;   let fn_return_type = sig.output;   let arg_idents = extract_arg_idents(fn_args.clone());   let first_ident = &arg_idents.first().unwrap();   let curried_body = generate_body(&arg_idents[1..], fn_body.clone());+  let arg_types = extract_arg_types(fn_args.clone());+  let first_type = &arg_types.first().unwrap();+  let type_aliases = generate_type_aliases(+      &arg_types[1..],+      extract_return_type(fn_return_type),+      &fn_name,+  );+  let return_type = format_ident!("_{}_{}", &fn_name, format!("T{}", type_aliases.len() - 1));+  return quote! {+      #(#type_aliases);* ;+      #vis fn #fn_name (#first_ident: #first_type) -> #return_type {+          #curried_body ;+      }+  }; }

大部分增加的代码都很容易理解，我会和你一起看看返回语句。我们返回一个quote!{ ... },也就是一个proc_macro2::TokenStream。我们正在遍历type_aliases变量，你应该可以想到，这是一个vec<TokenStream>。你可能注意到在*前面不起眼的分号。这是在告诉quote，要插入一项，然后是一个分后，然后插入下一项，然后是下一个分号，以此类推。这个分号是一个分隔符。我们需要手动插入另一个分号在全部结束的时候，quote不会再迭代结束后插入一个分隔符。

我们保持原来函数的可见性和名字。我们的柯里化后的函数接收参数，就像原来的函数接收的第一个参数一样。柯里化函数的返回类型是我们创建的最后的类型别名。如果你回想一下我们手工进行柯里化的add函数，我们返回了T2，事实上T2就是我们创建的最后的类型别名。

我保证，到这里，你一定渴望测试一下输出结果，但是在那之前，让我为你介绍一些调试过程宏代码的好方法。

调试和测试(Debugging and Testing)

通过下面的命令安装cargo-expand:

cargo install cargo-expand

cargo-expand是一个简洁的工具，它能够把你的宏在原地展开，让你看到生成的代码！例如:

# create a bin package hello$ cargo new hello# view the expansion of the println! macro$ cargo expand#![feature(prelude_import)]#[prelude_import]use std::prelude::v1::*;#[macro_use]extern crate std;fn main() {  {    ::std::io::_print(::core::fmt::Arguments::new_v1(        &["Hello, world!n"],        &match () {            () => [],        },      ));  };}

不使用cargo-expand来写过程宏就像驾驶没有后视镜的货车。它给你一双眼睛看到背后发生的事情。

现在，你的宏将不会总是编译，你只要收到蜜蜂电影剧本当做错误(译者注:这句话没看懂)。cargo-expand将不会在这样的情况下工作。我建议打印出你的变量以便于检查。TokenStream实现了Display和Debug。我们不必总是令人尊重的程序员。只要把它打印出来。

现在让我们开始测试：

// tests/smoke.rs#![feature(type_alias_impl_trait)]#[crate_name::curry]fn add(x: u32, y: u32, z: u32) -> u32 {   x + y + z}#[test]fn works() {  assert_eq!(15, add(4)(5)(6));}

运行cargo +nightly test。你应该能够看到一条令人愉快的消息:

running 1 testtest tests::works ... ok

通过cargo +nightly expand --tests smoke看一看我们的柯里化宏的展开：

type _add_T0 = u32;type _add_T1 = impl Fn(u32) -> _add_T0;type _add_T2 = impl Fn(u32) -> _add_T1;fn add(x: u32) -> _add_T2 {  return (move |y| {    move |z| {      return x + y + z;    }  });}// a bunch of other stuff generated by #[test] and assert_eq!

这是个更复杂的例子，它生产前十个自然数的十倍数:

#[curry]fn product(x: u32, y: u32) -> u32 {  x * y}fn multiples() -> Vec
     
      
       >{  let v = (1..=10).map(product);  return (1..=10)      .map(|x| v.clone().map(|f| f(x)).collect())      .collect();}

注意(Notes)

我没有解释为什么我们在闭包里使用move |arg|。这是因为我们想要获取提供给我们的变量的所有权。看看下面的例子:

let v = add(5);let g;{  let x = 5;  g = v(x);}println!("{}", g(2));

变量x在g能够返回一个具体值之前就离开了作用域。如果我们通过把它move到我们的闭包中来获取x的所有权，这就能达到我们预期的工作。事实上，rustc理解这个，并且强制你使用move。move的使用就解释了为什么一个没有返回的柯里化函数是无意义的。我们传递给柯里化函数每个变量都被移动进了它的本地作用域。使用这个变量不会引起作用域之外的变化。返回是我们唯一的和函数体外部进行交互的方式。