fork download
copy 
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4.  
  5. sub lam {
  6.     { type => 'lam', parameter => shift, body => shift };
  7. }
  8.  
  9. sub app {
  10.     { type => 'app', callee => shift, argument => shift };
  11. }
  12.  
  13. sub var {
  14.     { type => 'var', name => shift };
  15. }
  16.  
  17. my $next_alpha_renaming_name = 'a';
  18. sub alpha_rename {
  19.     my $term = shift;
  20.     my $env = shift // {};
  21.     my %methods = (
  22.         lam => sub {
  23.             my $inner_env = {%$env};
  24.             my $new_name = $next_alpha_renaming_name++;
  25.             $inner_env->{$term->{parameter}} = $new_name;
  26.             lam($new_name, alpha_rename($term->{body}, $inner_env));
  27.         },
  28.         app => sub {
  29.             app(
  30.                 alpha_rename($term->{callee}, $env),
  31.                 alpha_rename($term->{argument}, $env),
  32.             );
  33.         },
  34.         var => sub { var($env->{$term->{name}} // $term->{name}); },
  35.     );
  36.     $methods{$term->{type}}->();
  37. }
  38.  
  39. sub fmt {
  40.     my $term = shift;
  41.     my %methods = (
  42.         lam => sub { '(\\' . $term->{parameter} . '.' . fmt($term->{body}) . ')' },
  43.         app => sub { fmt($term->{callee}) . ' ' . fmt($term->{argument}) },
  44.         var => sub { $term->{name} },
  45.     );
  46.     $methods{$term->{type}}->();
  47. }
  48.  
  49. my $term = lam('x', app(var('x'), lam('x', var('x'))));
  50. CORE::say fmt($term);
  51. CORE::say fmt(alpha_rename($term));
  52.  
Success #stdin #stdout 0s 6176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(\x.x (\x.x))
(\a.a (\b.b))
https://ideone.com/uyLLkj
language:
Perl (perl 5.28.1)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!