Tree structure implemented with nested functions

function obj = mktree(value)
    _children = [];
    _parent   = [];
    _value    = v;

    obj.add_child = @add_child;
    obj.children = @children;
    obj.parent = @parent;
    obj.each = @each;

    function child = add_child(value)
        child = mktree(obj, value);
        _children = [ _children child ];
    end

    function ch = children
        ch = _children;
    end

    function p = parent
        p = _parent;
    end

    function v = value
        v = _value;
    end

    % Depth first iteration
    function each( fn )
        for i = 1:length(_children)
            c = _children(i);
            c.each(fn);
        end
        fn(c);
    end

end

%% Usage

>> t = mktree(10);
>> c1 = t.add_child(20);
>> c2 = t.add_child(30);
>> c11 = c1.add_child(40);

% Do a depth first iteration
>> t.each( @(c) disp(c.value()) );
40
20
30
10

Function Currying

I remember my old university days studying functional programming and that old favorite comp sci term, curried function. No it doesn't refer to a tasty oriental banquet, rather an obsure little programming trick.

We want to create a function that if not given it's full set of input parameters returns a new function that will accept the rest of the parameters. If that new function is not called with the full set if remaining parameters then the process repeats untill all the parameters are bound and the function returns with the value of the original function.

Turns out this is not too hard to do in Matlab using nested functions.

function cfnh = curry(fn)
    cfnh = @cfn;
    N = nargin(fn);
    args = {};
    function r = cfn(varargin)
        if nargin==N
            r = fn(args{:}, varargin{:});
        else
            N = N - nargin;
            args = { args{:} varargin{:} };
            r = @cfn;
        end
    end
end

The above code will turn any normal matlab function into a curried function. Watch the humble plus function be transformed.

> fc = curry(@plus);
> fc(1,2)
ans =
     3

just as we would expect.

> fc = curry(@plus);
> fc2 = fc(1);
fc2 =

    @curry/cfn
> fc2(2)
ans =
   3

Magic :)

Memoize function accelerator

The below function wraps a function handle to produce a memoized version. Essentially it tries to cache previously calculated values instead of recomputing them.

function fnm = memoize( fn )
    key_list = {};
    val_list = {};
    fnm = @exec;
    function varargout = exec(varargin)
        % Generate a unique key
        keys = cellfun(@num2str, varargin, 'UniformOutput',false);
        key = sprintf('%s:',keys{:});
        p = strmatch(key, key_list);
        if isempty(p)
            % Do fn
            [varargout{1:nargout}] = fn(varargin{:});
            % Cache value
            key_list{end+1} = key;
            val_list{end+1} = varargout;
        else
            % Use cached return value.
            varargout = val_list{p};
        end
    end
end

The above implementation is a bit flaky as I don't believe the hash key is necessarily unique for all types of functions. In fact I am sure it isn't.

Usage:

f = memoize(@sin);
x = f(pi/2);

Unit Testing

Have a look at
this tutorial

and write your test files like

% TEST_TEMPLATE
%
% Use this template as a starting point for your new tests. To
% run the test and see the report.
%
% suite = munit_testsuite('test_template');
% r = suite.run();
% r.web();
%
% See also test_munit1, test_munit2
function test = test_template

    % Subclass the testcase object
    test = munit_testcase;

    function setup
        % This function will be called at the
        % start of *every* test_ function
    end

    function teardown
        % This function will be called at the
        % end of *every* test_ function
    end

    % These are examples tests. Create new tests by creating
    % new functions whose name starts with test_
    %
    % The three tests below show the three different styles you
    % can use to create assertions. Refer to the documentation
    % for more details.

    function test_0
        x = 10;
        y = 20;
        % Simple assert using logical expression
        test.assert( x == y );
    end

    function test_1
        x = 10;
        y = 20;
        % Assert using anonymous functions ( recommended )
        test.assert( @() x == y );
    end
end

Matlab hashtable

Structs in Matlab are very usefull for collecting associated data together. However in Matlab you are limited to using valid Matlab variable names for the fields in the struct, even when using dynamic indexing.

For example.

>> h.('bad name') = 10
??? Invalid field name: 'bad name'.

What matlab requires is a hashtable object, sometimes refered to as a dictionary in other programming language. A hashtable can associate any string (key) with a value and retrieve the value later. More generic hashtables allow keys to be arbitrary objects but for the sake of simplicity I stick to strings for this implementation.

First of all download the hashtable object

Now you can try the following

   h = hashtable
   h.x = 10;
   y = h.x;

That was just like a standard matlab struct but it has other tricks.

h   = hashtable
h.x = 10;
y   = h;
h.x = 20;
y.x

  ans =

     20

Thats right, hashtable is a reference object. Assigning the hashtable instance to another variable does not make a copy of the data.

Lets try to use non standard field names.

h = hashtable
h.('a funny key') = 10;
y = h.('a funny key')

y =

    10

How does all this work?

First of all I am using a combination of nested functions and standard Matlab OOPs objects. The M-OOPS give me the ability to overide subsref and subsasgn to get the funky indexing and the nested functions give me the reference object behaviour.

The storage is managed by generated a hash of the string and using that hash to index into a storage cell array. My hash generating function is

function hash = hashcode(str)
    str = uint32(str(:))';
    hash = uint32(5381);
    for c = str
        hash = bitshift(hash, 5) + hash + c;
    end
end

I have a C version of the above function but for portability it is easier to use pure Matlab code. Unfortunately the pure M code is about 10 times slower in generating the code.

Once we have the code we generate a number over the number of storge buckets we have available.

 function i = hash(string)
      i = rem(hashcode(string),buckets) + 1;
 end

Retrieving the value is fairly simple. The modified hash is used to retrieve a structure array from a cell array of buckets. Generally the structure array is empty or contains only a few key-value pairs. A linear search is performed on the structure array to get the correct value.

   function out = get(key)
      i = hash(key);
      if isempty(contents{i})
         out = [];
         return;
      end
      items = contents{i};
      for j = 1:length(items);item = items(j);
         if isequal(item.key, key)
            out = item.value;
            return;
         end
      end
      out = [];
      return;
   end

Putting is more complex. We wish to maintain the efficiency of the table. This means avoiding filling each bucket up too much so that the linear search part takes too much time. If a certain threshold is reached then the number of buckets is increased and the elements redistributed over the hashtable. This is an expensive operation so you try to set up your hashtable with a suitable initial capacity to start with.

Have a look at the code for more details.

How to use nested functions to build an object oriented framework.

This currently only works in Matlab R14 SP3. In previous versions this does not work.

It is sometimes usefull to be able to obtain a function handle of a nested function in the calling scope. What this means is that you use evalin('caller',...) to perform an operation which retrieves function handles from the caller. An example of this is my unit test tool for Matlab MUnit which obtains a list of function handles whose names match the regular expression 'test_[A-Za-z0-9_]*'.

To do this first create a cell array of the function names you wish to grab. How you decide on what these names are are an application matter. In MUnit I scan the calling file and use regular expressions to find all function names that match the patterns.

In munit_testcase.m you will find

 stk = dbstack('-completenames');
 mname = stk(2).file;
 fcn_names = scan(mname, {'setup' ,'teardown', 'test_[A-Za-z0-9_]*'});

where the scan function is defined as

% SCAN
%
% Scans and extracts function names from an m file
% using regular expression patterns.
%
% Arguments
%   file        -   full path to an m file to scan
%   patterns    -   A cell array of regular expressions for function names
%                   to extract
%
function names = scan(fname, patterns)
    if iscell(patterns)
        patterns = sprintf('(%s)|',patterns{:});
    end
    str = evalc(sprintf('mlint(''-calls'',''%s'')', fname));
    names = regexp(str,'\d+\s*([AZa-z][A-Za-z0-9_]*)','tokens');
    names = cellfun(@(x) x{1}, names, 'uniformoutput', false);
    i = cellfun(@(x)~isempty(regexp(x, patterns)), names);
    names = names(i);
end

The above is different to what is in MUnit which uses an older scanning method and caching approach to avoid scanning the file more than once.

When you have your cell array, here stored in the variable fcn_names execute the following code

 fcns = evalin('caller',['@(){' sprintf('@%s ', fcn_names{:}) '}']);
 fcns = fcns();
 for i = 1:length(fcns);fcn = fcns{i};
   test_case.(fcn_names{i}) = fcn;
 end

If fcn_names contains

{'fun1' 'fun2' 'fun3'}

then the following expression will be evaluated in the caller

@(){ @fun1 @fun2 @fun3 }

That is it generates an anonymous function that when evaluated, line 2, generates a cell array of function handles.

Line 3 to line 5 just copies the function handles to named fields on a structure which can be returned.

You may ask why I need the extra layer of the anonymous function. I don't really know. It should be enough just to evaluate the cell array of function handles in the caller but this just does not work. Matlab bug or feature???

The savvy among you may realize that you can use this trick to easily create an object framework in Matlab. For example my theoretical object function may look like.

function self = my_object(x)
   self = create_object;
   function y = m_incr(r)
      x = x + r;
      y = x;
   end
   function y = m_decr(r)
      x = x - r;
      y = x;
   end
end

and create_object looks like

function self = create_object
 stk = dbstack('-completenames');
 mname = stk(2).file;
 fcn_names = scan(mname, {'m_[A-Za-z0-9_]*'});
 fcns = evalin('caller',['@(){' sprintf('@%s ', fcn_names{:}) '}']);
 fcns = fcns();
 for i = 1:length(fcns);fcn = fcns{i};
   self.(fcn_names{i}) = fcn;
 end
end

Now at the command line you should be able to

>> x = my_object(10);
>> x.m_incr(1)
ans =
      11
>> x.m_decr(2)
ans =
      9

Have fun

Simple objects with nested functions

You can create simple reference objects using nested functions and matlab structures.

function obj = counter(c1)

   obj.decr = @decr;
   obj.incr = @incr;

   function c1 = incr
       c1 = c1 + 1;
   end

   function c1 = decr
       c1 = c1 - 1;
   end

   function c1 = get
   end

end

You can then use the returned structure to access the counter
object

% create the counter
c = counter(10);

% increment;
c.incr();
c.incr();

% decrement;
c.decr();

% get the value
c.get()
ans =
     11

Nested Function Counter

Nested function are a powerfull way of creating mini objects that maintain their own state. The most basic example most often given is that of creating a counter.

function h = create_counter(x)
   h = @nest_count;
   count = x

   function count = nest_count
      count = count + incr
   end
end

and can be used like this

>> counter = create_counter(5);
>> counter()
ans =
      6

>> counter();
ans = 7

>> counter2 = create_counter(5);

>> counter2()
ans = 6

>> counter()
ans =
      8

As can be seen each counter function maintains it's own
counter variable.

GUI Tables

Here is a simple way to use java tables in matlab. I've wrapped the standard java table model with a matlab data model. Nested functions are taken advantage of to provide data set and get methods, cell rendering and entry validation.

% XTARGETS_UITABLE
%
% t = xtargets_uitable(table, rows, cols, getfun, setfun, labelfun, editfun)
%
% Arguments
%   table     Any instance or subclass instance of javax.swing.JTable
%   rows      numbers of rows
%   cols      number of cols
%   getfun    function handle for aquiring data to the table.
%             val = getfun(row, col)
%   setfun    function handle for setting data to the table.
%             setfun(row, col, val)
%   labelfun  function handle for generating a label in the table
%             string = labelfun(row, col, val)
%   editfun   function handle for validating string input
%             value = editfun(row, col, string)
%             throw an error if the string is invalid
%             to show a dialog box and reset the old value
%             of the cell
%   table    an instance of javax.swing.JTable or a subclass of
%
% Example
%   See xtargets_uitable_test
%

% Copyright Brad Phelan (C) 2005 under the LGPL license
% http://xtargets.com
function t = xtargets_uitable(table, rows, cols, getfun, setfun, labelfun, editfun)


    import javax.swing.*;
    import javax.swing.table.*;
    import ca.odell.renderpack.*;

    tableModel = javax.swing.table.DefaultTableModel(rows,cols);

    % Initialize the table model
    for r = 1:rows
       for c = 1:cols
           tableModel.setValueAt(labelfun(r,c,getfun(r,c)),r-1,c-1);
       end
    end

    table.setModel(tableModel);


    scroller = JScrollPane(table);
    scroller.setVerticalScrollBarPolicy(ScrollPaneConstants.VERTICAL_SCROLLBAR_AS_NEEDED);
    scroller.setHorizontalScrollBarPolicy(ScrollPaneConstants.HORIZONTAL_SCROLLBAR_AS_NEEDED);


    [hcom, hg] = javacomponent(scroller);
    hg = handle(hg);
    p = schema.prop(hg,'table','mxArray');
    hg.table = handle(table);
    set(hg,'position',[0 0 200 200]);

    %Fix for JTable focus bug : see http://www.mycgiserver.com/~Kleopatra/swing/table/merlineditfun.html
    table.putClientProperty('terminateEditOnFocusLost', java.lang.Boolean.TRUE);
    table.setAutoResizeMode(JTable.AUTO_RESIZE_OFF);


    t = hg;

    % A flag to avoid change handler recursion
    syncchange = false;

    set(tableModel, 'TableChangedCallback', @change_fcn);
    function change_fcn(src, ev)
        if syncchange
            % This change was invoked from this handler
            syncchange = false;
            return
        end
        syncchange = true;

        row = ev.getFirstRow;
        col = ev.getColumn;

        string = tableModel.getValueAt(row,col);

        row = row + 1;
        col = col + 1;
        % Perform validation on the string and convert it to a value
        try
            val = editfun(row, col, string);
            setfun(row,col,val);
            tableModel.setValueAt(labelfun(row,col,val), row-1,col-1);
        catch
            errordlg(lasterr,'Invalid Edit');
            % The value was not valid so reset the cell
            tableModel.setValueAt(labelfun(row,col,getfun(row,col)), row-1,col-1);
        end

    end
end

A test function demonstrates the behaviour of the table with a simple data model and validation.

% xtargets_uitable_test
%
% A simple example of using the table model to modify data in
% a nested function workspace. The data is in double format
% so we use the '%g' sscanf pattern to render and read the
% data from the table cells.

% Copyright Brad Phelan (C) 2005 under the LGPL license
% http://xtargets.com
function xtargets_uitable_test
    close all;

    data = rand(5);

    table = javax.swing.JTable;

    % Create a uitable with a simple matlab data model. Specify
    % that the conversion class will be %g.
    t = xtargets_uitable(table, 5,5, @getfun, @setfun, @labelfun, @editfun);

    function val = getfun( row, col)
       val = data(row,col);
    end

    function setfun( row, col, val)
       data(row,col) = val;
    end

    function val = editfun(row, col, string)
        val = sscanf(string, '%g');
        if isempty(val)
            error([ '''' string ''' is not a valid entry' ]);
        end
    end

    function label = labelfun(row, col, val)
         label = sprintf('%g',val);
    end

    % uicontrol to display the data model on the command line
    uicontrol('string','push me','position',[300 0 100 50], ...
        'callback',@disp_data);

    function disp_data(src,ev)
        disp(data);
    end
end

Create a library of functions hidden from the path

Suppose I have written 40 functions and I don't want 40 m-files but I want to put them in 1 big file. Suppose I want to use the functions from this big file in another function. So something like a library with functions that you want to access from a m-file.

A hack which does exactly what you want but is probably quite
inefficient .... The code allows you to *import* sub/nested
function contained within a single m-file into the current
workspace without having to access them from a structure.

% M_IMPORT_TEST
%
% A m file function library compatible with
% m_import.
%
% Usage
%
%   m_import m_import_test
%   whos % See the new functions in the workspace
%   a = fun1();  % Use fun1
%   b = fun2();  % Use fun2
%   c = fun3();  % Use fun3
function lib = m_import_test

     lib = { @fun1 @fun2 @fun3 };

     function fun1
         disp('1');
     end

     function fun2
         disp('2');
     end

     function fun3
         disp('3');
     end

end

% M_IMPORT
%
% import mfiles from a library into the current workspace.
%
% Arguments
%   fname   -   The name of the file where the library lives
%
% The library function must return a cell array of function
% handles. This function then inserts into the *callers*
% workspace a set of function handles as variables with the
% same name as the original functions.
%
function m_import(fname)
     funs = feval(fname);
     for i = 1:length(funs)
        % Strip of the function prefix
        [pathstr,name,ext,versn] = fileparts(func2str(funs{i}));
        % Place the function in the callers workspace
        assignin('caller', name, funs{i});
     end
end