Tuesday, May 06, 2008

Reluctant Sorting Algorithms Demonstration (Java Applets)

This is a follow-up of another recent article, Reluctant Sorting Algorithms. Hereby I present visualization of neglection and desertion sorting algorithms, written as Java applets. Unfortunately the demonstration doesn't look as nice as Erlang source code. I'd even say, the demonstration shows that these algorithms suck! So better admire the beauty of their source code in Erlang.

Demo

Click on an applet to start (you may need to click twice in IE).


Neglection sort


Desertion sort

Source code

This program is free software; you can redistribute it and/or modify it under the MIT/X11 License.

If you're going to make these applets run in the local environment, you'll also need SortAlgorithm and SortItem classes, both grabbed from Sorting Algorithms Demo by James Gosling, Jason Harrison, Jim Boritz et al.

Sunday, May 04, 2008

Erlang Template Engine (Prototype)

Some may argue, that it is pointless to write one's own template engine. But what if there's no suitable one? Common template engines are too heavy, provide enormous functionality, most of which is unnecessary rubbish, if you use templates right. What do I mean by right use of templates? To answer this question, I would like you to answer another one: what templates are intended for? Templates are intended for representation, hence must not include any logic. Logic is for developers, templates are for designers. Only template engines following this concept but still fully-functional I'm aware of are PHPLib's Template and Google CTemplate. Update: Plus Template::Simple for Perl.

Several years ago I wrote a template engine in Perl, which used PHPLib syntax, but had object-oriented approach for templates, so that every template or block inside a template was an object. If I get round to that, I'll clean up the code and post it in this blog later, and perhaps switch to Google CTemplate syntax, which I discovered recently.

If we deal with an object-oriented language, the natural way of representing a template is wrapping it into an object, using object's properties for template's variables and regarding nested templates as nested objects.

Erlang is a functional programming language. What is the natural way to express anything in a functional programming language? Right, wrap it into a function! In this article I present my experiment of creating a template engine using functional paradigm.

My Erlang template engine uses Google CTemplate syntax. Template variables are expressed through function arguments, and nested templates are expressed through descent calls to other functions.

% et - Erlang template engine
% Copyright (c) 2008 Ivan Fomichev
%
% Permission is hereby granted, free of charge, to any person obtaining a copy
% of this software and associated documentation files (the "Software"), to deal
% in the Software without restriction, including without limitation the rights
% to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
% copies of the Software, and to permit persons to whom the Software is
% furnished to do so, subject to the following conditions:
%
% The above copyright notice and this permission notice shall be included in
% all copies or substantial portions of the Software.
%
% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
% FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
% OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
% THE SOFTWARE.

-module(et).
-export([from_file/3, do/4, arg/2, set_arg/3, none/2, dict/2, switch/5, foreach/4]).

from_file(Logic, Filename, Args) ->
    case file:read_file(Filename) of
        {ok, Binary} -> Logic(binary_to_list(Binary), Args);
        Error -> throw(Error)
    end.

do(Logic, Template, Section, Args) ->
    validate_name(Section),
    
    StartRx = "{{#" ++ Section ++ "}}[ \t]*(\r?\n|\n)?",
    EndRx   = "{{/" ++ Section ++ "}}[ \t]*(\r?\n|\n)?",
    
    case regexp:match(Template, StartRx) of
        {match, StartPos, StartLength} ->
            Rest = string:substr(Template, StartPos + StartLength),
            case regexp:match(Rest, EndRx) of
                {match, EndPos, EndLength} ->
                    Template2 = lists:sublist(Rest, EndPos - 1),
                    Template3 = lists:sublist(Template, StartPos - 1) ++
                        Logic(Template2, Args) ++
                        string:substr(Rest, EndPos + EndLength),
                    dict(Template3, Args);
                        
                nomatch -> throw({template, "No such section " ++ Section})
            end;
        nomatch -> throw({template, "No such section " ++ Section})
    end.

validate_name(Name) ->
    Allowed = lists:seq($0, $9) ++ lists:seq($A, $Z) ++ "_" ++ lists:seq($a, $z),
    AllowedLen = string:span(Name, Allowed),
    if
        AllowedLen == length(Name) -> ok;
        true -> throw({template, "Invalid identifier " ++ Name})
    end.

arg(Key, Args) ->
    case lists:keysearch(Key, 1, Args) of
        {value, {_, Value}} -> Value;
        _ -> undefined
    end.

set_arg(Key, Value, Args) ->
    lists:keystore(Key, 1, Args, {Key, Value}).
    
arg_sort(A, B) ->
    KeyA = element(1, A),
    KeyB = element(1, B),
    KeyA =< KeyB.

none(_, _) -> "".

dict("", _) -> "";

dict(Template, []) -> Template;

dict(Template, [{Name, Value} | T]) ->
    validate_name(Name),
    Rx = "{{" ++ Name ++ "}}",
    Replacement = if
        is_list(Value) -> Value;
        is_float(Value) -> hd(io_lib:format("~g", [Value])); % TODO: choose precision
        is_integer(Value) -> integer_to_list(Value);
        true -> ""
    end,
    case regexp:gsub(Template, Rx, Replacement) of
        {ok, Result, _} -> dict(Result, T)
    end.

switch(_, Template, Section, Args, false) -> do(fun none/2, Template, Section, Args);

switch(Logic, Template, Section, Args, true) -> do(Logic, Template, Section, Args).

foreach_fun(_, "", _, _, _) -> "";

foreach_fun(_, _, [], _, Acc) -> lists:flatten(lists:reverse(Acc));

foreach_fun(Logic, Template, [Args | T], I, Acc) ->
    Args2 = lists:umerge(fun arg_sort/2,
        lists:usort(fun arg_sort/2, [
                {"__i", I},
                {"__first", I =:= 1},
                {"__last", T =:= []},
                {"__odd", I rem 2 =:= 1},
                {"__even", I rem 2 =:= 0}
            ]),
        lists:usort(fun arg_sort/2, Args)),
    Result = Logic(Template, Args2),
    foreach_fun(Logic, Template, T, I + 1, [Result | Acc]).
    
foreach(Logic, Template, Section, Args) ->
    do(fun(Template2, Args2) ->
            Data = arg(Section, Args2),
            foreach_fun(Logic, Template2, Data, 1, [])
        end,
        Template, Section, Args).

Simple example

Let's use Google CTemplate's example for demonstration:

Hello {{name}}
You have just won ${{value}}!
{{#in_ca}}
Well, ${{taxed_value}}, after taxes.
{{/in_ca}}

To animate this template, we write a view module:

-module(example).
-export([view/1]).

view(Args) ->
    et:from_file(fun example/2, "example.tpl", Args).

example(Template, Args) ->
    Bool = et:arg("in_ca", Args),
    et:switch(fun in_ca/2, Template, "in_ca", Args, Bool).

in_ca(Template, Args) ->
    TaxedValue = et:arg("value", Args) * 0.83,
    Args2 = et:set_arg("taxed_value", TaxedValue, Args),
    et:dict(Template, Args2).

Invoked with arguments, links:view returns rendered template:

1> c(et).
{ok,et}
2> c(example).
{ok,example}
3> io:format(example:view([{"name", "John Smith"}, {"value", 25.60}, {"in_ca", true}]), []).
Hello John Smith
You have just won $25.6000!
Well, $21.2480, after taxes.
ok

Complex example

Here's something more complex:

<h1>{{header}}</h1>
{{#list}}
<ul>
{{#item}}
{{#current}}
    <li><strong>{{name}}</strong></li>
{{/current}}
{{#link}}
    <li><a href="{{url}}">{{name}}</a></li>
{{/link}}
{{/item}}
</ul>
{{/list}}
{{#empty}}
<p>The list is empty.</p>
{{/empty}}

And the corresponding code:

-module(links).
-export([view/1]).

view(Args) ->
    et:from_file(fun links/2, "links.tpl", Args).

links(Template, Args) ->
    Empty = et:arg("item", Args) =:= [],
    Result = et:switch(fun list/2, Template, "list", Args, not Empty),
    et:switch(fun et:dict/2, Result, "empty", Args, Empty).

list(Template, Args) ->
    et:foreach(fun item/2, Template, "item", Args).

item(Template, Args) ->
    Current = et:arg("current", Args),
    Result = et:switch(fun et:dict/2, Template, "current", Args, Current),
    et:switch(fun et:dict/2, Result, "link", Args, not Current).

This is how it works:

4> c(links).
{ok,links}
5> io:format(links:view([
5>     {"header", "Colors"},
5>     {"item", [
5>         [
5>             {"name", "red"},
5>             {"current", true},
5>             {"url", "#Red"}
5>         ],
5>         [
5>             {"name", "green"},
5>             {"current", false},
5>             {"url", "#Green"}
5>         ]
5>     ]}
5> ]), []).
<h1>Colors</h1>
<ul>
    <li><strong>red</strong></li>
    <li><a href="#Green">green</a></li>
</ul>
ok
6> io:format(links:view([{"header", "Colors"}, {"item", []}]), []).
<h1>Colors</h1>
<p>The list is empty.</p>
ok

Ideas

  • Better diagnostics
  • Filters (HTML, URL, JavaScript etc.) and formats (date, float, etc.)
  • Performance?

If you've found this module useful, please let me know. It will encourage me to develop this into more than a prototype :-)

Copyright

All source code in this article is free software; you can redistribute it and/or modify it under the MIT/X11 License:

Copyright (c) 2008 Ivan Fomichev

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.