CodeSnips

Friday, December 4, 2015

Recursion examples in Python

"To iterate is human to recurse is divine"
- unknown programmer

In mathematics, the function is how we turn one thing into another thing. More essentially than that, we define functions to "map" one thing to another thing.  One of the more surprising features of functions is they can create other functions as an output - including themselves. This is the essential nature of recursion.

For example. If I want a function that returns the sum of (1 + 2 + 3 + ... n) numbers, I can define it as follows:

SumOfNumbers ( n )  
{   
     If n is equal to 1, the output is 1, otherwise the output is n + SumOfNumbers(n-1).
}

This is a recursive definition because the function refers to itself in its definition. The key part of the definition is that there is a single case for a specific input that does not refer to itself - but returns a value - allowing the function to escape from an infinite regress of definition. In the "SumOfNumbers" case, this is the output when given "1" as the input.  

One thing you'll notice as you work through the solution of SumOfNumbers(4) is you have to keep four intermediate answers before you can combine them into the final output:

SumOfNumbers(4) = 4 + SumOfNumbers(3)
SumOfNumbers(3) = 3 + SumOfNumbers(2)
SumOfNumbers(2) = 2 + SumOfNumbers(1)
SumOfNumbers(1) = 1

In a computer, storing each intermediate function result requires memory. So, recursive functions (assuming your computer language of choice supports recursive function definitions) can take longer to solve and may be limited by available memory to solve large inputs ( try SumOfNumbers(1000) on paper...) 

Let's look at another recursive function example - generating Fibonacci numbers.

The following code expresses the implementation of a function which returns the "nth" number in the Fibonacci sequence. Note how it  reads: the nth fibonacci number is the sum of the two previous fibonacci numbers (the first 2 numbers are always "1"):

def fibo(n):
    if n <= 2:
        return 1
    return fibo(n-1) + fibo(n-2)

This function runs just fine in Python up until you enter something like fibo(300) - at which point you will notice that Python is not optimizing this function as it will explode and set your computer on fire.

If the last statement in a recursive function is a call to itself (as it does in the above example) then it is possible to optimize the function by doing a "tail" recursive optimization. Some languages can detect a tail recursive definition and automatically optimize it. Python doesn't do this.

You can optimize it yourself by passing along extra parameters to carry the intermediate results into the next nested call.  This essentially turns the recursion into an iteration. Here's the tail recursive version:

def fibotail(n):
    def fibohelp(i,j,n):
        return fibohelp(j,i+j,n-1) if n>0 else j
    return fibohelp(0,1,n)


I'm taking advantage here of Python's ability to define nested functions. Fibotail calls its fibohelp function recursively - note the extra parameters to carry along the two previous results in the call.

To tell you the absolute truth, every time I write this code, I have to read it twice. I do not find it all intuitive. It is recursive, it is succinct code, and it will work efficiently on very large inputs. So it is optimized, but I would argue it's not worth the time to write it this way - as it loses the primary benefit of writing recursive function definitions: they can make certain algorithms easier to express and understand.

If your language of choice doesn't support automatic tail recursion optimization I'd recommend falling back on iteration to express your algorithm. I'd argue the following code at least captures the essence of the algorithm even if it is less brief and succinct.

def fiboloop(n):
    firstfibo = 1
    secondfibo = 1
    nextfibo = 1
    
    for x in range(1,n-1):
        nextfibo = firstfibo + secondfibo
        firstfibo = secondfibo
        secondfibo = nextfibo

    return nextfibo

As always, these are often matters of taste. however, if you are using a functional language that doesn't support loops and does not automatically optimize tail-recursive function definitions, then you'll possibly need to know how to write a hand-optimized tail-recursive code.

Wednesday, December 2, 2015

JGrasp - quick example 1

JGrasp is a tool similar to Linqpad to execute and explore code snippets. Here's a simple example of some Java code that shows the difference between static and instance class attributes. You should be able to past this code into JGrasp, save as Example1.java, and run/debug it.

public class Example1 {

  public static void main(String[] args) {
    
    System.out.println("Hello, World!!!\n");
        
    Square sq1 = new Square("My Square");
    Square sq2 = new Square("My Other Square"); 
        
    String line1 = 
      String.format("Squares have %d sides.\n", Square.Sides);

    String line2 = String.format("sq1 name is %s.", sq1.Name);
        
    System.out.println(line1+line2);
        
    System.out.println(String.format("sq2 name is \"%s\"",
        sq2.Name));
  }

}

class Square
{
  public static int Sides;
  public String Name;
    
  // Static initializer runs as part of class declaration.
  static {
    Sides = 4;
  }
    
  // Constructor - runs when instance is created by "new"
  public Square(String name)
  {
    Name = name;
  }
        
}


Sunday, September 20, 2015

WPF Simple Canvas Drawing

I'm brushing up on 3D mathematics and I find it useful (indeed necessary)  to write small bits of code to help understand and visualize the material. I even had a bit of fun writing a few programs in BASIC on a C64 that's part of my vintage computer collection.

Still, having modern tools, it's generally more useful to write graphic programs for more modern displays.  I whipped up the following code to display the results of a parametric circle equation. The tool of choice in this case was LinqPad. I like Linqpad because it's nice for writing and running short code snippets.

I think for many programmers WPF (Windows Presentation Framework) seems to be a complex tool, but, surprisingly, it's relatively simple to whip up simple interfaces using only code.  For this I decided to use the Canvas, Line, and Ellipse shape primitives to create a quick graphic display like this:.
void Main()
{
 var g = new Grid();
 var w = new Window { Width = 420, Height = 440, 
                             Title = "Graph", Content = g};
 var c = new Canvas { Background = Brushes.BlanchedAlmond };

 DrawLine(200,10,200,390,c);
 DrawLine(10,200,390,200,c);
 
 for (int i=0; i<50; i++)
 {
     double t = (1.0 / 50.0) * (i);
  int x = (int) (Math.Cos( 2 * Math.PI * t) * 100) + 197;
  int y = (int) (Math.Sin( 2 * Math.PI * t) * 100) + 197;
  DrawPoint(x,y,c);
 }
 
 g.Children.Add(c);
    w.ShowDialog();
 
}

public void DrawPoint(int x, int y, Canvas c)
{
    var e = new Ellipse { Height = 6, Width = 6, 
                          Fill = Brushes.Blue, Stroke = Brushes.Black };
 Canvas.SetLeft(e,x);
 Canvas.SetTop(e,y);
 c.Children.Add(e);
}

public void DrawLine(int x1, int y1, int x2, int y2, Canvas c)
{
    var l = new Line{ X1 = x1, Y1 = y1, X2 = x2, Y2 = y2, 
                      Stroke = Brushes.Black, StrokeThickness = 1 };
 c.Children.Add(l);
}

Saturday, July 19, 2014

AngularJS Number Validator Directive

After some searching yielded a few hints and examples, none of which really worked all that well, I pieced this together. Hopefully others will find it useful.

This AngularJS directive validates numeric entry. It uses a regular expression to test whether the input matches the expected numeric format and set the validity state of the element.

How does this work?
The $parsers array is an array of functions which can test the value on the input element. They pass the value along to other parsers by returning the value.  I change the value by removing any commas so the returned numeric string can be used as a Number.

In the directive, I capture the value of the directive attribute and add a parser function and formatter function to the respective arrays passed in.

The $formatters array is an array of functions which can format the model value for display in the input element. I use the built-in "numberFilter" for this.



View/Run/Edit the example in Plunker


app.directive('isNumber', ['numberFilter',function(numberFilter){
    return{
        require:'ngModel',
        link: function(scope, elem, attrs, ctrl){
            var digits = attrs.isNumber.length===0 ? "2" : attrs.isNumber;
            ctrl.$parsers.unshift(checkForNumber);
            ctrl.$formatters.unshift(formatNumber);

            function checkForNumber(viewValue){

                // Checks for positive or negative decimal or integer number with or without thousand separators
                if (/^-{0,1}\d{1,3}(,\d{3})*\.{0,1}\d*$|^-{0,1}\d*\.{0,1}\d*$/.test(viewValue)) {
                    ctrl.$setValidity('isNumber',true);
                }
                else{
                    ctrl.$setValidity('isNumber', false);
                }
                return viewValue.replace(/,/g,'');
            }

            function formatNumber(viewValue) {
                return numberFilter(viewValue,digits);
            }
        }
    };
}]);

Sunday, July 13, 2014

MEAN Stack CRUD Example

I thought it would be useful to create a full example using the MEAN stack. I wanted to include most of the bells and whistles in this particular example so that it would serve as a useful reference for other more complex applications.

MEAN is an acronym which stands for "Mongo Express Angular Node", and I must say this stack lets you create some very mean (and lean) code. 

The source for the full example is angularExample on GitHub - the README.md tells you how to run it.

Points of interest

  • The 'seeddb' script shows how to run Mongo command and run a Javascript setup script which creates the database and seeds the Account and AccountType collections. It creates a unique index on the Accounts collection.
  • The app.js file in the project root folder has the setup for Express, it passes the configured express handler as a "module.exports = app" - which is used by the (bin/www) script to setup the server listener.
  • Client-side setup of Socket.IO can be found in (/public/views/layout.jade) last two lines. This creates a global "socket" variable for client-side javascript to use for sending/receiving events. 
  • The application uses Socket.IO to broadcast account update notifications to the client browsers using the application.  See the bin/www file on how server-side Socket.IO is plugged in - along with the event send/receive.
  • The AngularJS controller (/public/javascripts/app/accountController.js) has the Socket.IO client code which sends notifications after saving/deleting items, and listens for the broadcast event in order to refresh the account list.
  • The (/routes/index.js) file has all the route handlers for the REST "/api" routes and home page load.




Wednesday, February 12, 2014

LINQPad4 Command Line And Dapper Via Nuget Just For Fun

LINQPad4 recently added a command line runner "lprun.exe" which provides some very useful and fun things to do with LINQPAD scripts (or even code fragments).  I'll finish this post with an example, but first I was surprised to realize that you can, via the F4 command, reference Nuget packages in a linqpad script. For additional fun I thought I'd add references to Dapper and DapperExtensions, a nice "micro" ORM and helper extension methods that lets you do all sorts of useful things with databases.

Let's get started:

1. In LINQPad, hit F4 to bring up the references dialog and choose "Add Nuget..." under the "Additional References" tab.
2. Search (and add) "Dapper", then "DapperExtensions".
3. Under the "Additional Namespace Imports" tab, add "Dapper" and "DapperExtensions".









 You are now ready to do some Dapper things in LINQPad4. The logical question might be "why?" as we are able to do SQL linq stuff in LINQPad4 right out of the box. But, there are some useful things you can do in Dapper and there's no reason you can't mix the two things together. Plus, this is for play as much as for anything else. Let's have some fun.

This script gives a small example of how to obtain the connection string and do a little Dapper.  Note, it's interesting that you can do pretty much anything, such as DDL (commented out line), with Dapper - as opposed to linq for SQL. This simply creates some output.

// Dapper stuff
// import Dapper;
// import DapperExtensions;

var conn = new SqlConnection(Connection.ConnectionString);
var results = conn.Query("SELECT * FROM ROLES").ToList();

foreach (IDictionary r in results) {
    Console.WriteLine("\"{0}\",\"{1}\",{2}",
                      r["Rolename"],r["ApplicationName"],r["COUNT"]);
}

//conn.Execute("ALTER TABLE ROLES ADD COUNT DECIMAL (19,6)");

Now, you are able to run this script, using the new lprun.exe utility provided with LINQPad4, at the command line.











I'd recommend checking out the various options, especially the format options, available with this tool. For those who'd like to combine powershell scripting along with some database work, this could be a powerful, and yes, fun, way to do things.

Have fun!




Wednesday, September 18, 2013

Versioning REST web services in WebApi

Much has been written on the subject of the proper approach to versioning REST web services  If you google long enough, you find there are two basic approaches:

1. Put the version identifier on the URI somehow:
    http://myhost/Account
    http://myhost/v2/Account
    http://myhost/Account/?version=2.0
    http://myhostV2/Account

2. Use the HTTP headers: 'Accept', 'Content-Type', and/or 'X-mycustom' to pass the desired version from the client.
    Accept: application/myhost-v2+js
    Content-Type: application/myhost-v2+js
    X-Version: 2.0


Any scheme which requires a URI change seems like a bad idea to me. The URI is supposed to be, essentially, a coordinate to a specific entity. Adding version to the coordinate will break older clients immediately regardless of whether the entity has changed in a breaking way.

A more robust approach would allow clients and the web service to negotiate the version needed, but leave the URI the same. This is more compatible with the semantics of HTTP.

Specifically in the case where we are using Microsoft's WebApi to provide REST web services, I wanted to see if I could add version handling in the least obtrusive way for programmers, and to that end I wanted something that fit the following design goals:

Design Goals
1. The URI doesn't change.
2. Handling the logic to shape the entity based on version should be done within a single method (or class.)
3. I want to minimize any special handling in the ApiController.
4. I want to decouple my domain entities from my model entities.
5. I want to have zero configuration changes to make in IIS or my web.config.

I think the following solution meets each of the above goals.

Example Code

To avoid creating new content types, which would require me to alter my IIS config [goal 5], I've chosen to use a custom header: "X-Version". This allows me to leave my URI format alone [goal 1]

To minimize any special handling of this header in my ApiControllers [goal 3], I've created a base class from which my controllers will inherit. It sets a "Version" property on the controllers which inherit from this base class:

    public class BaseApiController : ApiController
    {
        public double Version { get; set; }

        protected override void Initialize(HttpControllerContext controllerContext)
        {
             base.Initialize(controllerContext);
             Version = 1.0;
             var versionHeader = 
                 Request.Headers.FirstOrDefault(h => h.Key == "X-Version");
             if (versionHeader.Value != null)
             {
                 double version;
                 if (double.TryParse(versionHeader.Value.ToList()[0],out version))
                 {
                     Version = version;
                 }
             }
        }
    }

    // Example usage
    public class AccountController : BaseApiController
    {
        IAccountRepo _accountRepo;

        public AccountController(IAccountRepo accountRepo)
        {
            _accountRepo = accountRepo;
        }

        public IEnumerable Get()
        {
            foreach (var acct in _accountRepo.getAll())
            {
                yield return acct.AccountMap(Version);
            }
        }

        public Account Get(int id)
        {
            return _accountRepo.getById(id).AccountMap(Version);
        }

        // We handle the other verbs (POST, PUT, etc.) similarly
        // with a mapping from Model to Domain.
   }



I want to send back a Version property on all my model entities so my client can confirm it is getting the right version of the model entities it requested.

    public abstract class ModelBase
    {
        public double Version { get; set; }
    }

    public class Account : ModelBase
    {
        public int Id { get; set; }
        public string AccountCode { get; set; }
        public string Name { get; set; }
        public string AccountName { get; set; }
        public bool IsActive { get; set; }
    }



To decouple my domain entities (in this case Account) [goal 4] from my model entities, I've chosen to implement a "mapper" as an extension method on my domain entity type. This extension method takes a version parameter so it can choose how to return the data. The mapper also updates the Version property. All my mapping logic goes into this method [goal 2] so I only have to make changes here if I create a new version of the model entity.

        

        // Note: this is the mapper from Domain to Model entity.
        // Same idea for the Model to Domain mapper would apply (not shown here)
        //
        public static Model.Account AccountMap(this Domain.Account acct,
                                               double version)
        {
            if (acct == null)
                return null;

            // Version 1 Account Model

            if (version == 1.0)
            {
                return new Account
                {
                    Version = version,
                    Id = acct.Id,
                    AccountCode = acct.AccountCode,
                    Name = acct.Name,
                    IsActive = acct.IsActive,
                    AccountName = null,               // not used in v1
                };
            }

            // Version 2 (Current) Account Model
            return new Account
            {
                Version = version,
                Id = acct.Id,
                AccountCode = "V2" + acct.AccountCode, // content
                Name = null,                           // deprecated
                IsActive = acct.IsActive,
                AccountName = acct.Name,               // new

            };
        }
    }



Version mapping. There are basically four kinds of changes: adding properties, renaming properties, deprecating properties, and changing the content of existing properties.

One drawback of the serialization of the C# model classes is they can't be dynamic (at least without a bunch of ugly work), so to avoid breaking changes, you have to leave old properties in place on the model classes. However, this isn't too bad and you're able to handle the various kinds of changes noted above and not break clients expecting the old versions. New version clients will not be cluttered with old properties either - so most of this mapping mess goes into a single set of mappers in the server code.

Summary

The work in this example creates a couple of small base classes and a version-aware mapping function. The base classes could easily be added to a common library for other applications to use.  The mapping function is an example of one way to transform models based on version - there are undoubtedly better approaches, but the end result is you can manage version changes to models in one place.

I've learned that to handle versioning in a clean way, it's important to design ahead of time and make sure allowances are made for future change in both client and server code. This particular approach meets the goals I set out.

Lastly, non-WebApi REST web service frameworks that are implemented in more dynamic, loosely typed, languages would have a bit easier time transforming the returned data based on version. In my case, I wanted to use as much of C# and WebApi out-of-the-box as possible (I guess this is the implied design "goal 6"), but I think any solution should probably address the first 5 goals above.