Turing Complete Type Systems

From 3739ce5d1969df71f272d18a3ff8b5e13cd27f4f Mon Sep 17 00:00:00 2001 From: Akshay Date: Thu, 18 Jun 2020 10:39:57 +0530 Subject: new post: turing complete type systems --- docs/posts/auto-currying_rust_functions/index.html | 512 ++++++++++----------- docs/posts/rapid_refactoring_with_vim/index.html | 50 +- docs/posts/static_sites_with_bash/index.html | 36 +- docs/posts/turing_complete_type_systems/index.html | 73 +++ 4 files changed, 372 insertions(+), 299 deletions(-) create mode 100644 docs/posts/turing_complete_type_systems/index.html (limited to 'docs/posts') diff --git a/docs/posts/auto-currying_rust_functions/index.html b/docs/posts/auto-currying_rust_functions/index.html index db70890..a86667c 100644 --- a/docs/posts/auto-currying_rust_functions/index.html +++ b/docs/posts/auto-currying_rust_functions/index.html @@ -94,17 +94,17 @@ h(x)(y)(z) = g(y)(z) = k(z) = v

We will be using Attribute macros to convert a Rust function into a curried Rust function, which we should be able to call via: function(arg1)(arg2).

Definitions

Being respectable programmers, we define the input to and the output from our proc-macro. Here’s a good non-trivial function to start out with:

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

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

Hmm, what would our output look like? What should our proc-macro generate ideally? Well, if we understood currying correctly, we should accept an argument and return a function that accepts an argument and returns … you get the point. Something like this should do:

fn add_curried1(x: u32) -> ? {
-  return fn add_curried2 (y: u32) -> ? {
-    return fn add_curried3 (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;
+    }
+  }
+}

A couple of things to note:

Return types
We have placed ?s in place of return types. Let’s try to fix that. add_curried3 returns the ‘value’, so u32 is accurate. add_curried2 returns add_curried3. What is the type of add_curried3? It is a function that takes in a u32 and returns a u32. So a fn(u32) -> u32 will do right? No, I’ll explain why in the next point, but for now, we will make use of the Fn trait, our return type is impl Fn(u32) -> u32. This basically tells the compiler that we will be returning something function-like, a.k.a, behaves like a Fn. Cool!

@@ -117,9 +117,9 @@ We have placed ?s in place of return types. Let’s try to fix that A function cannot access it’s environment. Our solution will not work. add_curried3 attempts to access x, which is not allowed! A closure¹ however, can. If we are returning a closure, our return type must be impl Fn, and not fn. The difference between the Fn trait and function pointers is beyond the scope of this post.

Armed with knowledge, we refine our expected output, this time, employing closures:

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

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

Alas, that does not compile either! It errors out with the following message:

error[E0562]: `impl Trait` not allowed outside of function
 and inherent method return types
@@ -130,15 +130,15 @@ and inherent method return types

You are allowed to return an impl Fn only inside a function. We are currently returning it from another return! Or at least, that was the most I could make out of the error message.

We are going to have to cheat a bit to fix this issue; with type aliases and a convenient nightly feature ²:

#![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 applied
-type T1 = impl Fn(u32) -> T0;  // the return value when one arg is to be applied
-type T2 = impl Fn(u32) -> T1;  // the return value when two args are to be applied
-
-fn add(x: u32) -> T2 {
-  return move |y| move |z| x + y + z;
-}

#![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 applied
+type T1 = impl Fn(u32) -> T0;  // the return value when one arg is to be applied
+type T2 = impl Fn(u32) -> T1;  // the return value when two args are to be applied
+
+fn add(x: u32) -> T2 {
+  return move |y| move |z| x + y + z;
+}

Drop that into a cargo project, call add(4)(5)(6), cross your fingers, and run cargo +nightly run. You should see a 15 unless you forgot to print it!

The In-Betweens

Let us write the magical bits that take us from function to curried function.

@@ -172,19 +172,19 @@ proc-macro = true # this is important!

We will be using an external proc-macro2 crate as well as an internal proc-macro crate. Not confusing at all!

The attribute macro

Drop this into src/lib.rs, to get the ball rolling.

// src/lib.rs
-
-use proc_macro::TokenStream;  // 1
-use quote::quote;
-use syn::{parse_macro_input, ItemFn};
-
-#[proc_macro_attribute]   // 2
-pub 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 {}

// src/lib.rs
+
+use proc_macro::TokenStream;  // 1
+use quote::quote;
+use syn::{parse_macro_input, ItemFn};
+
+#[proc_macro_attribute]   // 2
+pub 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

A Tokenstream holds (hopefully valid) Rust code, this is the type of our input and output. Note that we are importing this type from proc_macro and not proc_macro2.

quote! from the quote crate is a macro that allows us to quickly produce TokenStreams. Much like the LISP quote procedure, you can use the quote! macro for symbolic transformations.

@@ -196,16 +196,16 @@ proc-macro = true # this is important!

4. Returning TokenStreams

We haven’t filled in generate_curry yet, but we can see that it returns a proc_macro2::TokenStream and not a proc_macro::TokenStream, so drop a .into() to convert it.

Lets move on, and fill in generate_curry, I would suggest keeping the documentation for syn::ItemFn and syn::Signature open.

// src/lib.rs
-
-fn 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
-}

// src/lib.rs
+
+fn 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
+}

We are simply extracting the bits of the function, we will be reusing the original function’s visibility and name. Take a look at what syn::Signature can tell us about a function:

                       .-- syn::Ident (ident)
                       /
@@ -217,220 +217,220 @@ syn::token::Fn --'            /               \       (output)
 Enough analysis, lets produce our first bit of Rust code.
 Function Body
 Recall that the body of a curried add should look like this:
-return move |y| move |z| x + y + z;
+return move |y| move |z| x + y + z;
 And in general:
-return move |arg2| move |arg3| ... |argN| <function body here>
+return move |arg2| move |arg3| ... |argN| <function body here>
 We already have the function’s body, provided by fn_body, in our generate_curry function. All that’s left to add is the move |arg2| move |arg3| ... stuff, for which we need to extract the argument identifiers (doc: Punctuated, FnArg, PatType):
-// src/lib.rs
-use syn::punctuated::Punctuated;
-use syn::{parse_macro_input, FnArg, Pat, ItemFn, Block};
-
-fn extract_arg_idents(fn_args: Punctuated<FnArg, syn::token::Comma>) -> Vec<Box<Pat>> { 
-  return fn_args.into_iter().map(extract_arg_pat).collect::<Vec<_>>();
-}
+// src/lib.rs
+use syn::punctuated::Punctuated;
+use syn::{parse_macro_input, FnArg, Pat, ItemFn, Block};
+
+fn extract_arg_idents(fn_args: Punctuated<FnArg, syn::token::Comma>) -> Vec<Box<Pat>> { 
+  return fn_args.into_iter().map(extract_arg_pat).collect::<Vec<_>>();
+}
 Alright, so we are iterating over function args (Punctuated is a collection that you can iterate over) and mapping an extract_arg_pat to every item. What’s extract_arg_pat?
-// src/lib.rs
-
-fn extract_arg_pat(a: FnArg) -> Box<Pat> {
-  match a {
-    FnArg::Typed(p) => p.pat,
-    _ => panic!("Not supported on types with `self`!"),
-  }
-}
+// src/lib.rs
+
+fn extract_arg_pat(a: FnArg) -> Box<Pat> {
+  match a {
+    FnArg::Typed(p) => p.pat,
+    _ => panic!("Not supported on types with `self`!"),
+  }
+}
 FnArg is an enum type as you might have guessed. The Typed variant encompasses args that are written as name: type and the other variant, Reciever refers to self types. Ignore those for now, keep it simple.
 Every FnArg::Typed value contains a pat, which is in essence, the name of the argument. The type of the arg is accessible via p.ty (we will be using this later).
 With that done, we should be able to write the codegen for the function body:
-// src/lib.rs
-
-fn generate_body(fn_args: &[Box<Pat>], body: Box<Block>) -> proc_macro2::TokenStream {
-  quote! {
-    return #( move |#fn_args|  )* #body
-  }
-}
+// src/lib.rs
+
+fn generate_body(fn_args: &[Box<Pat>], body: Box<Block>) -> proc_macro2::TokenStream {
+  quote! {
+    return #( move |#fn_args|  )* #body
+  }
+}
 That is some scary looking syntax! Allow me to explain. The quote!{ ... } returns a proc_macro2::TokenStream, if we wrote quote!{ let x = 1 + 2; }, it wouldn’t create a new variable x with value 3, it would literally produce a stream of tokens with that expression.
 The # enables variable interpolation. #body will look for body in the current scope, take its value, and insert it in the returned TokenStream. Kinda like quasi quoting in LISPs, you have written one.
 What about #( move |#fn_args| )*? That is repetition. quote iterates through fn_args, and drops a move behind each one, it then places pipes (|), around it.
 Let us test our first bit of codegen! Modify generate_curry like so:
-// 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();
- }
+// 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();
+ }
 Add a little test to tests/:
-// tests/smoke.rs
-
-#[currying::curry]
-fn add(x: u32, y: u32, z: u32) -> u32 {
-  x + y + z
-}
-
-#[test]
-fn works() {
-  assert!(true);
-}
+// tests/smoke.rs
+
+#[currying::curry]
+fn add(x: u32, y: u32, z: u32) -> u32 {
+  x + y + z
+}
+
+#[test]
+fn works() {
+  assert!(true);
+}
 You should find something like this in the output of cargo test:
 return move | y | move | z | { x + y + z }
 Glorious println! debugging!
 Function signature
 This section gets into the more complicated bits of the macro, generating type aliases and the function signature. By the end of this section, we should have a full working auto-currying macro!
 Recall what our generated type aliases should look like, for our add function:
-type T0 = u32;
-type T1 = impl Fn(u32) -> T0;
-type T2 = impl Fn(u32) -> T1;
+type T0 = u32;
+type T1 = impl Fn(u32) -> T0;
+type T2 = impl Fn(u32) -> T1;
 In general:
-type T0 = <return type>;
-type T1 = impl Fn(<type of arg N>) -> T0;
-type T2 = impl Fn(<type of arg N - 1>) -> T1;
-.
-.
-.
-type T(N-1) = impl Fn(<type of arg 2>) -> T(N-2);
+type T0 = <return type>;
+type T1 = impl Fn(<type of arg N>) -> T0;
+type T2 = impl Fn(<type of arg N - 1>) -> T1;
+.
+.
+.
+type T(N-1) = impl Fn(<type of arg 2>) -> T(N-2);
 To codegen that, we need the types of:
 
 all our inputs (arguments)
 the output (the return type)
 
 To fetch the types of all our inputs, we can simply reuse the bits we wrote to fetch the names of all our inputs! (doc: Type)
-// src/lib.rs
-
-use syn::{parse_macro_input, Block, FnArg, ItemFn, Pat, ReturnType, Type};
-
-fn extract_type(a: FnArg) -> Box<Type> {
-  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<FnArg, syn::token::Comma>) -> Vec<Box<Type>> {
-  return fn_args.into_iter().map(extract_type).collect::<Vec<_>>();
-
-}
+// src/lib.rs
+
+use syn::{parse_macro_input, Block, FnArg, ItemFn, Pat, ReturnType, Type};
+
+fn extract_type(a: FnArg) -> Box<Type> {
+  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<FnArg, syn::token::Comma>) -> Vec<Box<Type>> {
+  return fn_args.into_iter().map(extract_type).collect::<Vec<_>>();
+
+}
 A good reader would have looked at the docs for output member of the syn::Signature struct. It has the type syn::ReturnType. So there is no extraction to do here right? There are actually a couple of things we have to ensure here:
 
 We need to ensure that the function returns! A function that does not return is pointless in this case, and I will tell you why, in the Notes section.
 A ReturnType encloses the arrow of the return as well, we need to get rid of that. Recall:
-type T0 = u32
-// and not
-type T0 = -> u32
+type T0 = u32
+// and not
+type T0 = -> u32
 
 Here is the snippet that handles extraction of the return type (doc: syn::ReturnType):
-// src/lib.rs
-
-fn extract_return_type(a: ReturnType) -> Box<Type> {
-  match a {
-    ReturnType::Type(_, p) => p,
-    _ => panic!("Not supported on functions without return types!"),
-  }
-}
+// src/lib.rs
+
+fn extract_return_type(a: ReturnType) -> Box<Type> {
+  match a {
+    ReturnType::Type(_, p) => p,
+    _ => panic!("Not supported on functions without return types!"),
+  }
+}
 You might notice that we are making extensive use of the panic! macro. Well, that is because it is a good idea to quit on receiving an unsatisfactory TokenStream.
 With all our types ready, we can get on with generating type aliases:
-// src/lib.rs
-
-use quote::{quote, format_ident};
-
-fn generate_type_aliases(
-  fn_arg_types: &[Box<Type>],
-  fn_return_type: Box<Type>,
-  fn_name: &syn::Ident,
-) -> Vec<proc_macro2::TokenStream> {    // 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;
-}
+// src/lib.rs
+
+use quote::{quote, format_ident};
+
+fn generate_type_aliases(
+  fn_arg_types: &[Box<Type>],
+  fn_return_type: Box<Type>,
+  fn_name: &syn::Ident,
+) -> Vec<proc_macro2::TokenStream> {    // 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. The return value

 We are returning a Vec<proc_macro2::TokenStream>, i. e., a list of TokenStreams, where each item is a type alias.
 2. Format identifier?

 I’ve got some explanation to do on this line. Clearly, we are trying to write the first type alias, and initialize our TokenStream vector with T0, because it is different from the others:
-type T0 = something
-// the others are of the form
-type Tr = impl Fn(something) -> something
+type T0 = something
+// the others are of the form
+type Tr = impl Fn(something) -> something
 format_ident! is similar to format!. Instead of returning a formatted string, it returns a syn::Ident. Therefore, type_t0 is actually an identifier for, in the case of our add function, _add_T0. Why is this formatting important? Namespacing.
 Picture this, we have two functions, add and subtract, that we wish to curry with our macro:
-#[curry]
-fn add(...) -> u32 { ... }
-
-#[curry]
-fn sub(...) -> u32 { ... }
+#[curry]
+fn add(...) -> u32 { ... }
+
+#[curry]
+fn sub(...) -> u32 { ... }
 Here is the same but with macros expanded:
-type T0 = u32;
-type T1 = impl Fn(u32) -> T0;
-fn add( ... ) -> T1 { ... }
-
-type T0 = u32;
-type T1 = impl Fn(u32) -> T0;
-fn sub( ... ) -> T1 { ... }
+type T0 = u32;
+type T1 = impl Fn(u32) -> T0;
+fn add( ... ) -> T1 { ... }
+
+type T0 = u32;
+type T1 = impl Fn(u32) -> T0;
+fn sub( ... ) -> T1 { ... }
 We end up with two definitions of T0! Now, if we do the little format_ident! dance we did up there:
-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 { ... }
+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 { ... }
 Voilà! The type aliases don’t tread on each other. Remember to import format_ident from the quote crate.
 3. The TokenStream Vector
 We iterate over our types in reverse order (T0 is the last return, T1 is the second last, so on), assign a number to each iteration with zip, generate type names with format_ident, push a TokenStream with the help of quote and variable interpolation.
 If you are wondering why we used (1..).zip() instead of .enumerate(), it’s because we wanted to start counting from 1 instead of 0 (we are already done with T0!).
 Getting it together
 I promised we’d have a fully working macro by the end of last section. I lied, we have to tie everything together in our generate_curry function:
-// 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 ;
-+      }
-+  };
- }
+// 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 ;
++      }
++  };
+ }
 Most of the additions are self explanatory, I’ll go through the return statement with you. We are returning a quote!{ ... }, so a proc_macro2::TokenStream. We are iterating through the type_aliases variable, which you might recall, is a Vec<TokenStream>. You might notice the sneaky semicolon before the *. This basically tells quote, to insert an item, then a semicolon, and then the next one, another semicolon, and so on. The semicolon is a separator. We need to manually insert another semicolon at the end of it all, quote doesn’t insert a separator at the end of the iteration.
 We retain the visibility and name of our original function. Our curried function takes as args, just the first argument of our original function. The return type of our curried function is actually, the last type alias we create. If you think back to our manually curried add function, we returned T2, which was in fact, the last type alias we created.
 I am sure, at this point, you are itching to test this out, but before that, let me introduce you to some good methods of debugging proc-macro code.
@@ -462,57 +462,57 @@ fn main() {
 Writing proc-macros without cargo-expand is tantamount to driving a vehicle without rear view mirrors! Keep an eye on what is going on behind your back.
 Now, your macro won’t always compile, you might just recieve the bee movie script as an error. cargo-expand will not work in such cases. I would suggest printing out your variables to inspect them. TokenStream implements Display as well as Debug. We don’t always have to be respectable programmers. Just print it.
 Enough of that, lets get testing:
-// 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));
-}
+// 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));
+}
 Run cargo +nightly test. You should see a pleasing message:
 running 1 test
 test tests::works ... ok
 Take a look at the expansion for our curry macro, via 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!
+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!
 A sight for sore eyes.
 Here is a more complex example that generates ten multiples of the first ten natural numbers:
-#[curry]
-fn product(x: u32, y: u32) -> u32 {
-  x * y
-}
-
-fn multiples() -> Vec<Vec<u32>>{
-  let v = (1..=10).map(product);
-  return (1..=10)
-      .map(|x| v.clone().map(|f| f(x)).collect())
-      .collect();
-}
+#[curry]
+fn product(x: u32, y: u32) -> u32 {
+  x * y
+}
+
+fn multiples() -> Vec<Vec<u32>>{
+  let v = (1..=10).map(product);
+  return (1..=10)
+      .map(|x| v.clone().map(|f| f(x)).collect())
+      .collect();
+}
 Notes
 I didn’t quite explain why we use move |arg| in our closure. This is because we want to take ownership of the variable supplied to us. Take a look at this example:
-let v = add(5);
-let g;
-{
-  let x = 5;
-  g = v(x);
-}
-println!("{}", g(2));
+let v = add(5);
+let g;
+{
+  let x = 5;
+  g = v(x);
+}
+println!("{}", g(2));
 Variable x goes out of scope before g can return a concrete value. If we take ownership of x by moveing it into our closure, we can expect this to work reliably. In fact, rustc understands this, and forces you to use move.
 This usage of move is exactly why a curried function without a return is useless. Every variable we pass to our curried function gets moved into its local scope. Playing with these variables cannot cause a change outside this scope. Returning is our only method of interaction with anything beyond this function.
 Conclusion
diff --git a/docs/posts/rapid_refactoring_with_vim/index.html b/docs/posts/rapid_refactoring_with_vim/index.html
index c5bc188..ee05dc0 100644
--- a/docs/posts/rapid_refactoring_with_vim/index.html
+++ b/docs/posts/rapid_refactoring_with_vim/index.html
@@ -40,34 +40,34 @@
           
             Last weekend, I was tasked with refactoring the 96 unit tests on ruma-events to use strictly typed json objects using serde_json::json! instead of raw strings. It was rather painless thanks to vim :)
 Here’s a small sample of what had to be done (note the lines prefixed with the arrow):
-→ use serde_json::{from_str};
-  
-  #[test]
-  fn deserialize() {
-    assert_eq!(
-→       from_str::<Action>(r#"{"set_tweak": "highlight"}"#),
-        Action::SetTweak(Tweak::Highlight { value: true })
-        );
-  }
+→ use serde_json::{from_str};
+  
+  #[test]
+  fn deserialize() {
+    assert_eq!(
+→       from_str::<Action>(r#"{"set_tweak": "highlight"}"#),
+        Action::SetTweak(Tweak::Highlight { value: true })
+        );
+  }
 had to be converted to:
-→ use serde_json::{from_value};
-  
-  #[test]
-  fn deserialize() {
-    assert_eq!(
-→       from_value::<Action>(json!({"set_tweak": "highlight"})),
-        Action::SetTweak(Tweak::Highlight { value: true })
-        );
-  }
+→ use serde_json::{from_value};
+  
+  #[test]
+  fn deserialize() {
+    assert_eq!(
+→       from_value::<Action>(json!({"set_tweak": "highlight"})),
+        Action::SetTweak(Tweak::Highlight { value: true })
+        );
+  }
 The arglist
 For the initial pass, I decided to handle imports, this was a simple find and replace operation, done to all the files containing tests. Luckily, modules (and therefore files) containing tests in Rust are annotated with the #[cfg(test)] attribute. I opened all such files:
-# `grep -l pattern files` lists all the files
-#  matching the pattern
-
-vim $(grep -l 'cfg\(test\)' ./**/*.rs)
-
-# expands to something like:
-vim push_rules.rs room/member.rs key/verification/lib.rs
+# `grep -l pattern files` lists all the files
+#  matching the pattern
+
+vim $(grep -l 'cfg\(test\)' ./**/*.rs)
+
+# expands to something like:
+vim push_rules.rs room/member.rs key/verification/lib.rs
 Starting vim with more than one file at the shell prompt populates the arglist. Hit :args to see the list of files currently ready to edit. The square [brackets] indicate the current file. Navigate through the arglist with :next and :prev. I use tpope’s vim-unimpaired ¹, which adds ]a and [a, mapped to :next and :prev.
 All that’s left to do is the find and replace, for which we will be using vim’s argdo, applying a substitution to every file in the arglist:
 :argdo s/from_str/from_value/g
diff --git a/docs/posts/static_sites_with_bash/index.html b/docs/posts/static_sites_with_bash/index.html
index 67eaf12..b2a90a7 100644
--- a/docs/posts/static_sites_with_bash/index.html
+++ b/docs/posts/static_sites_with_bash/index.html
@@ -43,26 +43,26 @@
 I chose to write in markdown, and convert to html with lowdown.
 Directory structure
 I host my site on GitHub pages, so docs/ has to be the entry point. Markdown formatted posts go into posts/, get converted into html, and end up in docs/index.html, something like this:
-posts=$(ls -t ./posts)     # chronological order!
-for f in $posts; do
-    file="./posts/"$f      # `ls` mangled our file paths
-    echo "generating post $file"
-
-    html=$(lowdown "$file")
-    echo -e "html" >> docs/index.html
-done
+posts=$(ls -t ./posts)     # chronological order!
+for f in $posts; do
+    file="./posts/"$f      # `ls` mangled our file paths
+    echo "generating post $file"
+
+    html=$(lowdown "$file")
+    echo -e "html" >> docs/index.html
+done
 Assets
 Most static site generators recommend dropping image assets into the site source itself. That does have it’s merits, but I prefer hosting images separately:
-# strip file extension
-ext="${1##*.}"
-
-# generate a random file name
-id=$( cat /dev/urandom | tr -dc 'a-zA-Z0-9' | fold -w 2 | head -n 1 )
-id="$id.$ext"
-
-# copy to my file host
-scp -P 443 "$1" emerald:files/"$id" 
-echo "https://u.peppe.rs/$id"
+# strip file extension
+ext="${1##*.}"
+
+# generate a random file name
+id=$( cat /dev/urandom | tr -dc 'a-zA-Z0-9' | fold -w 2 | head -n 1 )
+id="$id.$ext"
+
+# copy to my file host
+scp -P 443 "$1" emerald:files/"$id" 
+echo "https://u.peppe.rs/$id"
 Templating
 generate.sh brings the above bits and pieces together (with some extra cruft to avoid javascript). It uses sed to produce nice titles from the file names (removes underscores, title-case), and date(1) to add the date to each post listing!
 
diff --git a/docs/posts/turing_complete_type_systems/index.html b/docs/posts/turing_complete_type_systems/index.html
new file mode 100644
index 0000000..4a7e2b1
--- /dev/null
+++ b/docs/posts/turing_complete_type_systems/index.html
@@ -0,0 +1,73 @@
+
+
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+    
+    
+    Turing Complete Type Systems · peppe.rs
+    
+      
+        
+          ⟵ Back
+          View Raw
+          
+          
+            18/06 — 2020
+            
+              
+                8.78
+              
+              cm
+               
+              
+                0.8
+              
+              min
+            
+          
+          
+            Turing Complete Type Systems
+          
+          
+            Rust’s type system is Turing complete:
+
+FizzBuzz with Rust Traits
+A Forth implementation with Rust Traits
+
+It is impossible to determine if a program written in a generally Turing complete system will ever stop. That is, it is impossible to write a program f that determines if a program g, where g is written in a Turing complete programming language, will ever halt. The Halting Problem is in fact, an undecidable problem.
+How is any of this relevant?
+Rust performs compile-time type inference. The type checker, in turn, compiles and infers types, I would describe it as a compiler inside a compiler. It is possible that rustc may never finish compiling your Rust program!
+I understand that this post lacks content.
+
+          
+          
+    
+        Hi. 
+        
+            Subscribe
+            Donate
+        
+        I'm Akshay, I go by nerd or nerdypepper on the internet.
+        
+        I am a compsci undergrad, Rust programmer and an enthusiastic Vimmer.
+        I write open-source stuff to pass time. I also design fonts: scientifica, curie.
+        
+        Send me a mail at nerdy@peppe.rs or a message at nerd@irc.rizon.net.
+    
+    
+          ⟵ Back
+          View Raw
+        
+      
+    
+
-- 
cgit v1.2.3

Definitions

Refinement

The In-Betweens

The attribute macro

Function Body

Function signature

Getting it together

Notes

Conclusion

The arglist

Directory structure

Assets

Templating

+ Turing Complete Type Systems +