Tail Call Optimization – Erlang

Surprised to see that Erlang can be run as a script. But here, we are not going to see about escript but to test whether Erlang does the Tail call optimization or not. If it does, how much performance are we gaining on it? I’ve taken the factorial example given in the above escript page.

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname factorial -mnesia debug verbose
main([String]) ->
    try
        N = list_to_integer(String),
        F = fac(N),
        io:format("factorial ~w = ~w\n", [N,F])
    catch
        _:_ ->
            usage()
    end;
main(_) ->
    usage().

usage() ->
    io:format("usage: factorial integer\n"),
    halt(1).

fac(0) -> 1;
fac(N) -> N * fac(N-1).

And, based on that script, amending a few lines, I’ve written a tail-call-optimized version of the script factorial_tco

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname factorial_tco -mnesia debug verbose
main([String]) ->
    try
        N = list_to_integer(String),
        F = fac(N),
        io:format("factorial_tco ~w = ~w\n", [N,F])
    catch
        _:_ ->
            usage()
    end;
main(_) ->
    usage().

usage() ->
    io:format("usage: factorial_tco integer\n"),
    halt(1).

fac1(0, Acc) -> Acc;
fac1(N, Acc) -> fac1(N - 1, N * Acc).

fac(N) -> fac1(N, 1).

Using the following Perl snippet, I tested both the versions.

use Time::HiRes qw(time);
use feature qw(say);

my $t1 = time; `escript ./factorial     100000 > /dev/null`; my $t2 = time;
say "factorial     ran in ", $t2 - $t1, " seconds";

my $t3 = time; `escript ./factorial_tco 100000 > /dev/null`; my $t4 = time;
say "factorial_tco ran in ", $t4 - $t3, " seconds";

The first script takes just above 39 seconds and the second script takes just above 37 seconds. Gaining 2 seconds in calculating a factorial(100000) doesn’t look like a big difference but it looks like tail-call-optimization is being carried out by Erlang.

Cheers!

Perl Sorting

Perl version we are talking about is 5.10

We are going to see about perldoc.perl.org/functions/sort.html

Sorting examples as One-liners

% perl -e ' print ((sort (5, 3, 1, 7, 8, 2, 6, 9, 4)), "\n") '                   # sort 1 to 9
123456789
% perl -e ' print ((sort (5, 10, 3, 1, 7, 8, 2, 6, 9, 4)), "\n") '               # sort 1 to 10, asciibetically
11023456789
% perl -e ' print ((sort {$a <=> $b} (5, 10, 3, 1, 7, 8, 2, 6, 9, 4)), "\n") '   # sort 1 to 10, numerically
12345678910
% perl -e ' print ((sort {$a <=> $b} (5, 10, 3, 1, 7, 8, 2, 6, 9, 4)), "\n") '   # sort 1 to 10, numerically, descending order
10987654321

$a and $b are the variables declared by Perl automatically (something similar to the default variable $_). Declaring those variables by ourself is generally discouraged. You may also want to refer to <=>

sort function looks simple and flexible, but what if we want to sort a complex data structure like an array of arrays?!
Or, how to implement custom sorts like

select *
  from scott.emp
 order by case JOB
          when 'PRESIDENT' then 1
          when 'MANAGER'   then 2
          when 'ANALYST'   then 3
          when 'CLERK'     then 4
          when 'SALESMAN'  then 5
           end,
          ename

I am not going to bore you by explaining the code.
I hope that the code looks simple and simpler with comments.

use strict;
use warnings;
use Data::Dumper;

my $aref = [
        # oracle sample database schema scott emp table data demobld.sql
        # EMPNO, ENAME,   JOB,         MGR,   HIREDATE,      SAL, COMM, DEPTNO
        [7369, 'SMITH',  'CLERK',      7902, '17-DEC-1980',  800, undef, 20],
        [7499, 'ALLEN',  'SALESMAN',   7698, '20-FEB-1981', 1600,   300, 30],
        [7521, 'WARD',   'SALESMAN',   7698, '22-FEB-1981', 1250,   500, 30],
        [7566, 'JONES',  'MANAGER',    7839, '02-APR-1981', 2975, undef, 20],
        [7654, 'MARTIN', 'SALESMAN',   7698, '28-SEP-1981', 1250,  1400, 30],
        [7698, 'BLAKE',  'MANAGER',    7839, '01-MAY-1981', 2850, undef, 30],
        [7782, 'CLARK',  'MANAGER',    7839, '09-JUN-1981', 2450, undef, 10],
        [7788, 'SCOTT',  'ANALYST',    7566, '09-DEC-1982', 3000, undef, 20],
        [7839, 'KING',   'PRESIDENT', undef, '17-NOV-1981', 5000, undef, 10],
        [7844, 'TURNER', 'SALESMAN',   7698, '08-SEP-1981', 1500, undef, 30],
        [7876, 'ADAMS',  'CLERK',      7788, '12-JAN-1983', 1100, undef, 20],
        [7900, 'JAMES',  'CLERK',      7698, '03-DEC-1981',  950, undef, 30],
        [7902, 'FORD',   'ANALYST',    7566, '03-DEC-1981', 3000, undef, 20],
        [7934, 'MILLER', 'CLERK',      7782, '23-JAN-1982', 1300, undef, 10],
];

print Dumper $aref;     # unsorted data

@$aref = sort { $a->[1] cmp $b->[1] } @$aref;
print Dumper $aref;     # sorted by ENAME alphabetically

@$aref = sort { $b->[2] cmp $a->[2] } @$aref;
print Dumper $aref;     # sorted by JOB in descending order

my %job_order = (PRESIDENT => 1, MANAGER => 2, ANALYST => 3, CLERK => 4, SALESMAN => 5);

@$aref = sort { $job_order{$a->[2]} <=> $job_order{$b->[2]} } @$aref;
print Dumper $aref;     # sorted by custom JOB order

@$aref = sort {
                my $n = $job_order{$a->[2]} <=> $job_order{$b->[2]};
                return $n if $n != 0;    # sort by custom JOB order
                $a->[1] cmp $b->[1];     # if the JOBs are same, then order by ENAME
        } @$aref;
print Dumper $aref;    

Given this, you can try ordering the data by the HIREDATE field using Date::Calc or Date::Manip

Happy Programming!