and has 14 comments

Intro

  If you are like me, you want to first establish a nice skeleton app that has everything just right before you start writing your actual code. However, as weird as it may sound, I couldn't find a way to use command line parameters with dependency injection, in the same simple way that one would use a configuration file with IOptions<T> for example. This post shows you how to use CommandLineParser, a nice library that handles everything regarding command line parsing, but in a dependency injection friendly way.

  In order to use command line arguments, we need to obtain them. For any .NET Core application or .NET Framework console application you get it from the parameters of the static Main method from Program. Alternately, you can use Environment.CommandLine, which is actually a string, not an array of strings, or Environment.GetCommandLineArgs(). But all of these are kind of nudging you towards some ugly code that either has a dependency on the static Environment, either has code early in the application to handle command line arguments, or stores the arguments somehow. What we want is complete separation of modules in our application.

Defining the command line parameters

  In order to use CommandLineParser, you write a class that contains the properties you expect from the command line, decorated with attributes that inform the parser what is the expected syntax for all. In this post I will use this:

// the way we want to use the app is
// FileUtil <command> [-loglevel loglevel] [-quiet] -output <outputFile> file1 file2 .. file10
public class FileUtilOptions
{
    // use Value for parameters with no name
    [Value(0, Required = true, HelpText = "You have to enter a command")]
    public string Command { get; set; }

    // use Option for named parameters
    [Option('l',"loglevel",Required = false, HelpText ="Log level can be None, Normal, Verbose")]
    public string LogLevel { get; set; }

    // use bool for named parameters with no value
    [Option('q', "quiet", Default = false, Required = false, HelpText = "Quiet mode produces no console output")]
    public bool Quiet { get; set; }

    // Required for required values
    [Option('o', "output", Required = true, HelpText = "Output file is required")]
    public string OutputFile { get; set; }

    // use Min/Max for enumerables
    [Value(1, Min = 1, Max = 10, HelpText = "At least one file name and at most 10")]
    public IEnumerable<string> Files { get; set; }
}

  At this point the blog post will split into two parts. One is very short and easy to use, thanks to commenter Murali Karunakaran. The other one is what I wrote in 2020 when I didn't know better. This second part is just a reminder of how much people can write when they don't have to :)

The short and easy solution

All you have to do is add your command line parameters class as options, then define what will happen when you request one instance of it:

// in ConfigureServices or wherever you define dependencies for injection
services
  .AddOptions<FileUtilOptions>()
  .Configure(opt => 
    Parser.Default.ParseArguments(() => opt, Environment.GetCommandLineArgs())
  );

// when needing the parameters
public SomeConstructor(IOptions<FileUtilOptions> options)
{
    _options = options.Value;
}

When an instance of FileUtilOptions is requested, the lambda will be executed, setting the options based on ParseArguments. If any issue, the parser will display the help to the console

This process, however, does not throw any exceptions. The instance of FileUtilOptions requested will be provided empty or partially/incorrectly filled. In order to handle the errors, some more complex code is needed, and here is a silly example:

using (var writer = new StringWriter())
{
	var parser = new Parser(configuration =>
	{
		configuration.AutoHelp = true;
		configuration.AutoVersion = false;
		configuration.CaseSensitive = false;
		configuration.IgnoreUnknownArguments = true;
		configuration.HelpWriter = writer;
	});
	var result = parser.ParseArguments<T>(_args);
	result.WithNotParsed(errors => HandleErrors(errors, writer));
	result.WithParsed(value => _value = value);
}

// a possible way to handle errors
private static void HandleErrors(IEnumerable<Error> errors, TextWriter writer)
{
	if (errors.Any(e => e.Tag != ErrorType.HelpRequestedError && e.Tag != ErrorType.VersionRequestedError))
	{
		string message = writer.ToString();
		throw new CommandLineParseException(message, errors, typeof(T));
	}
}

Now, the original post follows:

Writing a lot more than necessary

  How can we get the arguments by injection? By creating a new type that encapsulates the simple string array.

// encapsulates the arguments
public class CommandLineArguments
{
    public CommandLineArguments(string[] args)
    {
        this.Args = args;
    }

    public string[] Args { get; }
}

// adds the type to dependency injection
services.AddSingleton<CommandLineArguments>(new CommandLineArguments(args));
// the generic type declaration is superfluous, but the code is easy to read

  With this, we can access the command line arguments anywhere by injecting a CommandLineArguments object and accessing the Args property. But this still implies writing command line parsing code wherever we need that data. We could add some parsing logic in the CommandLineArguments class so that instead of the command line arguments array it would provide us with a strong typed value of the type we want. But then we would put business logic in a command line encapsulation class. Why would it know what type of options we need and why would we need only one type of options? 

  What we would like is something like

public SomeClass(IOptions<MyCommandLineOptions> clOptions) {...}

  Now, we could use this system by writing more complicated that adds a ConfigurationSource and then declaring that certain types are command line options. But I don't want that either for several reasons:

  • writing configuration providers is complex code and at some moment in time one has to ask how much are they willing to write in order to get some damn arguments from the command line
  • declaring the types at the beginning does provide some measure of centralized validation, but on the other hand it's declaring types that we need in business logic somewhere in service configuration, which personally I do not like

  What I propose is adding a new type of IOptions, one that is specific to command line arguments:

// declare the interface for generic command line options
public interface ICommandLineOptions<T> : IOptions<T>
    where T : class, new() { }

// add it to service configuration
services.AddSingleton(typeof(ICommandLineOptions<>), typeof(CommandLineOptions<>));

// put the parsing logic inside the implementation of the interface
public class CommandLineOptions<T> : ICommandLineOptions<T>
    where T : class, new()
{
    private T _value;
    private string[] _args;

    // get the arguments via injection
    public CommandLineOptions(CommandLineArguments arguments)
    {
        _args = arguments.Args;
    }

    public T Value
    {
        get
        {
            if (_value==null)
            {
                // set the value by parsing command line arguments
            }
            return _value;
        }
    }

}

  Now, in order to make it work, we will use CommandLineParser which functions in a very simple way:

  • declare a Parser
  • create a POCO class that has properties decorated with attributes that define what kind of command line parameter they are
  • parse the command line arguments string array into the type of class declared above
  • get the value or handle errors

  Also, to follow the now familiar Microsoft pattern, we will write an extension method to register both arguments and the mechanism for ICommandLineOptions. The end result is:

// extension class to add the system to services
public static class CommandLineExtensions
{
    public static IServiceCollection AddCommandLineOptions(this IServiceCollection services, string[] args)
    {
        return services
            .AddSingleton<CommandLineArguments>(new CommandLineArguments(args))
            .AddSingleton(typeof(ICommandLineOptions<>), typeof(CommandLineOptions<>));
    }
}

public class CommandLineArguments // defined above

public interface ICommandLineOptions<T> // defined above

// full class implementation for command line options
public class CommandLineOptions<T> : ICommandLineOptions<T>
    where T : class, new()
{
    private T _value;
    private string[] _args;

    public CommandLineOptions(CommandLineArguments arguments)
    {
        _args = arguments.Args;
    }

    public T Value
    {
        get
        {
            if (_value==null)
            {
                using (var writer = new StringWriter())
                {
                    var parser = new Parser(configuration =>
                    {
                        configuration.AutoHelp = true;
                        configuration.AutoVersion = false;
                        configuration.CaseSensitive = false;
                        configuration.IgnoreUnknownArguments = true;
                        configuration.HelpWriter = writer;
                    });
                    var result = parser.ParseArguments<T>(_args);
                    result.WithNotParsed(errors => HandleErrors(errors, writer));
                    result.WithParsed(value => _value = value);
                }
            }
            return _value;
        }
    }

    private static void HandleErrors(IEnumerable<Error> errors, TextWriter writer)
    {
        if (errors.Any(e => e.Tag != ErrorType.HelpRequestedError && e.Tag != ErrorType.VersionRequestedError))
        {
            string message = writer.ToString();
            throw new CommandLineParseException(message, errors, typeof(T));
        }
    }
}

// usage when configuring dependency injection
services.AddCommandLineOptions(args);

Enjoy!

Final notes

Now there are some quirks in the implementation above. One of them is that the parser class generates the usage help by writing it to a TextWriter (default being Console.Error), but since we want this to be encapsulated, we declare our own StringWriter and then store the generated help if any errors. In the case above, I am storing the help text as the exception message, but it's the principle that matters.

Also, with this system one can ask for multiple types of command line options classes, depending on the module, without the need to declare said types at the configuration of dependency injection. The downside is that if you want validation of the command line options at the very beginning, you have to write extra code. In the way implemented above, the application will fail when first asking for a command line option that cannot be mapped on the command line arguments.

Note that the short style of a parameter needs to be used with a dash, the long one with two dashes:

  • -o outputFile.txt - correct (value outputFile.txt)
  • --output outputFile.txt - correct (value outputFile.txt)
  • -output outputFile.txt - incorrect (value output and outputFile.txt is considered an unnamed argument)

Intro

  As I was working on LInQer I was hooked on the multiple optimizations that I was finding. Do you want to compute the average of an iterable? You would need the total count and the sum of the items, which you can get in a single function that you can reuse to get the sum or the count. But what if the iterable is an integer range between 1 and 10? Then you can compute the sum and you already know the count. Inspired by that work and by other concepts like interval types or Maybe/Nullable types, I've decided to write this post, which I do not know if it will lead to any usable code.

What is an iterable/enumerable?

  In Javascript they call it an Iterable, in .NET you have IEnumerable. They mean the same thing: sources of values. With new concepts like async/await you can use Observables as Enumerables as well, although they are theoretically diametrically opposing patterns. In both languages they are implemented as having a method that returns an iterator/enumerator, an object that can move to the next value, give you the next value and maybe reset itself. You can define any stream of values like that, having one or more values or, indeed, none. From now own I will discuss in terms of .NET nomenclature, but I see no reason why it wouldn't apply to any other language that implements this feature.

  For example an array is defined as an IEnumerable<T> in .NET. Its enumerator will return false if trying to move to the next value and the array is empty, or true if there is at least a value and the current value will return the first value in the array. Move next again and it will return true or false depending on whether there is a next value. But there is no need for the values to exist to have an Enumerable. One could write an object that would return all the positive integer numbers. It's length would be infinite and the values would only be generated when requested. There is no differentiation between an Enumerable and a generator in .NET, but there is in Javascript. For this reason whenever I will use the term generator, I will mean an object that generates values rather than produce them from a source of existing ones.

The NULL controversy

  A very popular InfoQ post describes the introduction of the NULL concept in programming languages a the billion dollar mistake. I am not so sure about that, but I can concede they make good points. The alternative to using a special value to describe the absence of a value is use an "option" object that either has Some value or it has None. You would check the existence of a value by calling a method to tell you if it has a value and you would get the value from the current value property. Doesn't it sound familiar? It's a more specific case of an Enumerator! Another popular solution to remove NULLs from code is to never return values from your methods, but arrays. An empty array would represent no value. An array is an Enumerable!

And that last idea opens up an interesting possibility: instead of one or none, you can have multiple values. What then? What would a multiplication mean? What about a decision block?

The LInQer experience

  If you know me, you are probably fed up with me plugging LInQer as the greatest thing since fire was invented. But that's because it is! And while implementing .NET LInQ as a Javascript library I've played with some very interesting concepts.

  For example, while implementing the Last operator on enumerables, I had two different implementations depending on whether one could know the length in advance and one could use indexed access to the values. An array of one billion values has no problem giving you the last item in it because of two things: you know where the array ends and you can access any item at any position without having to go through other values. You just take the value at index one billion minus one. If you would have a generator, though, the only way to get the last value would be to enumerate again and again and again and only when moving to the next value would fail you would have the last value as the last one. And of course, this would be bad if there are no bounds to the generator.

  But there is more. What about very common statistical values like the sum? This, of course, applies to numbers. The Enumerable need not produce numbers, so in other contexts it means nothing. Then there are concepts like statistical distribution. One can make some assumptions if they know the distribution of values. A constant yet infinite generator of numbers will always have the same average value. It would return the same value, regardless of index.

  I spent a lot of time doing sorting that only needs a part of the enumerable, or partial sorting. I've implemented a Quicksort algorithm that works faster than the default sort when there are enough values and that can ignore the parts of the array that I don't need. Also, there are specific algorithm to return the last or first N items. All of this depends on functions that determine the order of items. Randomness is also interesting, as it needs to take into consideration the change of probabilities as the list of items increases with each request. Sampling was fun, too!

  Then there were operators like Distinct or Group which needed to use functions to determine sameness.

  With all this work, I've never intended to make this more than what LInQ is in .NET: a way to dynamically filter and map and enumerate sequences of items without having to go through them all or to create intermediate but unnecessary arrays. What I am talking about now is taking things further and deeper.

Continuous intervals

  What if the Enumerable abstraction is not enough? For example one could define the interval of real numbers between 0 and 1. You can never enumerate the next value, but there are definite boundaries, a clear distribution of values, a very obvious average. What about series and limits? If a generator generates values that depend on previous values, like a geometric progression or a Fibonacci series, you can sometimes compute the minimum or maximum value of the items in it, or of their sums.  

Tools

  So we have more concepts in our bag now:

  • move next (function)
  • current value
  • item length (could be infinite or just unknown)
  • indexed access (or not)
  • boundaries (min, max, limits)
  • distribution (probabilities)
  • order
  • discreteness

  How could we use these?

Concrete cases

  There is one famous probabilities problem: what are the chances you will get a particular value by throwing a number of dice. And it is interesting because there is a marked difference between using one die or more. Using at least two dice and plotting the values you get after multiple throws you get what is called a Normal distribution, a Gauss curve, and that's because there are more combinations of values that sum up to 6 than there are for 2.

  How can we declare a value that belongs to an interval? One solution is to add all kinds of metadata or validations. But what if we just declare an iterable with one value that has a random value between 1 and 6? And what if we add it with another one? What would that mean?

  Here is a demo example. It's silly and it looks too much like the Calculator demos you see for unit testing and I really hate those, but I do want to just demo this. What else can we do with this idea? I will continue to think about it.

class Program
    {
        static void Main(string[] args)
        {
            var die1 = new RandomGenerator(1, 6);
            var die2 = new RandomGenerator(1, 6);
            // just get the value
            var value1 = die1.First() + die2.First();
            // compose the two dice using Linq, then get value
            var value2 = die1.Zip(die2).Select(z => z.First + z.Second).First();
            // compose the two dice using operator overload, then get value
            var value3 = (die1 + die2).First();
            var min = (die1 + die2).Min();
        }

        /// <summary>
        /// Implemented Min alone for demo purposes
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public interface IGenerator<T> : IEnumerable<T>
        {
            int Min();
        }

        /// <summary>
        /// Generates integer values from minValue to maxValue inclusively
        /// </summary>
        public class RandomGenerator : IGenerator<int>
        {
            private readonly Random _rnd;
            private readonly int _minValue;
            private readonly int _maxValue;

            public RandomGenerator(int minValue, int maxValue)
            {
                _rnd = new Random();
                this._minValue = minValue;
                this._maxValue = maxValue;
            }

            public static IGenerator<int> operator +(RandomGenerator gen1, IGenerator<int> gen2)
            {
                return new AdditionGenerator(gen1, gen2);
            }

            public IEnumerator<int> GetEnumerator()
            {
                while (true)
                {
                    yield return _rnd.Next(_minValue, _maxValue + 1);
                }
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return ((IEnumerable<int>)this).GetEnumerator();
            }

            public int Min()
            {
                return _minValue;
            }
        }
        
        /// <summary>
        /// Combines two generators through addition
        /// </summary>
        internal class AdditionGenerator : IGenerator<int>
        {
            private IGenerator<int> _gen1;
            private IGenerator<int> _gen2;

            public AdditionGenerator(Program.RandomGenerator gen1, Program.IGenerator<int> gen2)
            {
                this._gen1 = gen1;
                this._gen2 = gen2;
            }

            public IEnumerator<int> GetEnumerator()
            {
                var en1 = _gen1.GetEnumerator();
                var en2 = _gen2.GetEnumerator();
                while (true)
                {
                    var hasValue = en1.MoveNext();
                    if (hasValue != en2.MoveNext())
                    {
                        throw new InvalidOperationException("One generator stopped providing values before the other");
                    }
                    if (!hasValue)
                    {
                        yield break;
                    }
                    yield return en1.Current + en2.Current;
                }

            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return ((IEnumerable<int>)this).GetEnumerator();
            }

            public int Min()
            {
                return _gen1.Min() + _gen2.Min();
            }
        }
    }

Conclusion (so far)

I am going to think about this some more. It has a lot of potential as type abstraction, but to be honest, I deal very little in numerical values and math and statistics, so I don't see what I personally could do with this. I suspect, though, that other people might find it very useful or at least interesting. And yes, I am aware of mathematical concepts like interval arithmetic and I am sure there are a ton of existing libraries that already do something like that and much more, but I am looking at this more from the standpoint of computer science and quasi-primitive types than from a mathematical or numerical perspective. If you have any suggestions or ideas or requests, let me know!

  You can consider this an interview question, although to be fair if someone did ask me this for an interview I would say they are assholes. What is the difference between the pre-increment operator and the post-increment operator in C#?

  They look the same in C and C# and Javascript and Java and all the languages that share the curly bracket syntax with C, but in fact they are slightly different. Slight enough to make someone an asshole for asking the question as if it were relevant, but important enough for you to read about it. One of the most common interpretations of the syntax is that x++ is incrementing the value after the operation, while ++x is incrementing it before the operation. That is wrong.

  In fact, for C++ the return values are different between pre and post operators. I am not a C++ dev, so I give you this reference link: "Pre operators increment or decrement the value of the object and return a reference to the result. Post operators create a copy of the object, increment or decrement the value of the object and return the copy from before the increment or decrement." So one returns an object, the other returns a reference to an object. It is also possible that the assignment be done after the value was produced in C or C++. In C# the assignment must be done before any value is returned.

  In C#, to paraphrase Eric Lippert, "Both pre and post operators determine the value of the variable, what value will be assigned back to storage and assign the new value to storage. The postfix operator produces the original value, and the prefix operator produces the assigned value." So it's (kindda) like this piece of code:

int Increment(ref int x, bool post) {
  var originalX = x;
  var newX = x+1;
  x = newX;
  return post ? originalX : newX;
}

  So why the hell does it matter? I mean, it's a rather meaningless difference between the programming languages and the before/after mnemonic is making the code pretty clear, doesn't it? OK. Let's try some code and let me see how fast you come up with the answer. Remember, this is supposed to be simple, so if you are thinking too much about it, it doesn't matter you get the correct answer. Ready?

  1. Any difference between x++ and ++x if the resulting value is not used?
  2. var a=1; var b=++a; What's the value of b?
  3. var a=1; var b=a++; var c=++a; What's the value of c?
  4. var i = 0; for (i=0; i<5; ++i) Console.Write(i+" "); Console.WriteLine(i); What is printed at the console?
  5. var i = 0; for (i=0; i<5; i++) Console.Write(i+" "); Console.WriteLine(i); What is printed at the console?
  6. var a=1; a=a++; What's the value of a?

And all of this was about the increment operator as normally used for integer values. There is a big part about operator overloading in there, but I believe less relevant in the context of differences between pre and post increment/decrement operators.

There is one important part to discuss, though, and that is best code practices. When to use post and when to use pre. And they are really easy: separate statements from expressions! Statements execute code with side effects, they should return nothing. Expressions return values without side effects. If you never use the value of an increment or decrement and instead use it as a statement with side-effects, there is no difference between ++a and a++. In fact one doesn't need the preincrement/predecrement operators at all! In this context, the answers for the questions above is 1. No 2,3,6: You are using it wrong! 4,5: the same thing, since without getting the value we have scenario 1.

Just for reference, though, here are the answers:

  1. No
  2. 2
  3. 3 (b is 1)
  4. 0 1 2 3 4 5
  5. 0 1 2 3 4 5
  6. 1

Hope that makes you think.

 Intro

  When I was a kid, computers didn't have multithreading, multitasking or even multiple processes. You executed a program and it was the only program that was running. Therefore the way to do, let's say, user key input was to check again and again if there is a key in a buffer. To give you a clearer view on how bonkers that was, if you try something similar in Javascript the page dies. Why? Because the processing power to look for a value in an array is minuscule and you will basically have a loop that executes hundreds of thousand or even millions of times a second. The CPU will try to accommodate that and run at full power. You will have a do nothing loop that will take the entire capacity of the CPU for the current process. The browser would have problems handling legitimate page events, like you trying to close it! Ridiculous!

Bad solution

Here is what this would look like:

class QBasic {

    constructor() {
        this._keyBuffer=[];
        // add a global handler on key press and place events in a buffer
        window.addEventListener('keypress', function (e) {
            this._keyBuffer.push(e);
        }.bind(this));
    }

    INKEY() {
        // remove the first key in the buffer and return it
        const ev = this._keyBuffer.shift();
        // return either the key or an empty string
        if (ev) {
            return ev.key;
        } else {
            return '';
        }
    }
}

// this code will kill your CPU and freeze your page
const qb = new QBasic();
while (qb.INKEY()=='') {
 // do absolutely nothing
}

How then, should we port the original QBasic code into Javascript?

WHILE INKEY$ = ""

    ' DO ABSOLUTELY NOTHING

WEND

Best solution (not accepted)

Of course, the best solution is to redesign the code and rewrite everything. After all, this is thirty year old code. But let's imagine that, in the best practices of porting something, you want to find the first principles of translating QBasic into Javascript, then automate it. Or that, even if you do it manually, you want to preserve the code as much as possible before you start refactoring it. I do want to write a post about the steps of refactoring legacy code (and as you can see, sometimes I actually mean legacy, as in "bestowed upon by our forefathers"), but I wanted to write something tangible first. Enough theory!

Interpretative solution (not accepted, yet)

Another solution is to reinterpret the function into a waiting function, one that does nothing until a key is pressed. That would be easier to solve, but again, I want to translate the code as faithfully as possible, so this is a no-no. However, I will discuss how to implement this at the end of this post.

Working solution (slightly less bad solution)

Final solution: do the same thing, but add a delay, so that the loop doesn't use the entire pool of CPU instructions. Something akin to Thread.Sleep in C#, maybe. But, oops! in Javascript there is no function that would freeze execution for a period of time.

The only thing related to delays in Javascript is setTimeout, a function that indeed waits for the specified interval of time, but then executes the function that was passed as a parameter. It does not pause execution. Whatever you write after setTimeout will execute immediately. Enter async/await, new in Javascript ES8 (or EcmaScript 2017), and we can use the delay function as we did when exploring QBasic PLAY:

function delay(duration) {
    return new Promise(resolve => setTimeout(resolve, duration));
}

Now we can wait inside the code with await delay(milliseconds);. However, this means turning the functions that use it into async functions. As far as I am concerned, the pollution of the entire function tree with async keywords is really annoying, but it's the future, folks!

Isn't this amazing? In order to port to Javascript code that was written in 1990, you need features that were added to the language only in 2017! If you wanted to do this in Javascript ES5 you couldn't do it! The concept of software development has changed so much that it would have been impossible to port even the simplest piece of code from something like QBasic to Javascript.

Anyway, now the code looks like this:

function delay(duration) {
    return new Promise(resolve => setTimeout(resolve, duration));
}

class QBasic {

    constructor() {
        this._keyBuffer=[];
        // add a handler on every key press and place events in a buffer
        window.addEventListener('keypress', function (e) {
            this._keyBuffer.push(e);
        }.bind(this));
    }

    async INKEY() {
        // remove the first key in the buffer and return it
        const ev = this._keyBuffer.shift();
        // return either the key or an empty string
        if (ev) {
            return ev.key;
        } else {
            await delay(100);
            return '';
        }
    }
}

const qb = new QBasic();
while (qb.INKEY()=='') {
 // do absolutely nothing
}

Now, this will work by delaying for 100 milliseconds when there is nothing in the buffer. It's clearly not ideal. If one wanted to fix a problem with a loop running too fast, then the delay function should have at least been added to the loop, not the INKEY function. Using it like this you will get some inexplicable delays in code that would want to use fast key inputs. It's, however, the only way we can implement an INKEY function that will behave as close to the original as possible, which is hiring a 90 year old guy to go to a letter box and check if there is any character in the mail and then come back and bring it to you. True story, it's the original implementation of the function!

Interpretative solution (implementation)

It would have been much simpler to implement the function in a blocking manner. In other words, when called, INKEY would wait for a key to be pressed, then exit and return that key when the user presses it. We again would have to use Promises:

class QBasic {

    constructor() {
        this._keyHandler = null;
        // instead of using a buffer for keys, keep a reference
        // to a resolve function and execute it if it exists
        window.addEventListener('keypress', function (e) {
            if (this._keyHandler) {
                const handler = this._keyHandler;
                this._keyHandler = null;
                handler(e.key);
            }
        }.bind(this));
    }

    INKEY() {
        const self = this;
        return new Promise(resolve => self._keyHandler = resolve);
    }
}


const qb = new QBasic();
while ((await qb.INKEY())=='') { // or just await qb.INKEY(); instead of the loop
 // do absolutely nothing
}

Amazing again, isn't it? The loops (pun not intended) through which one has to go in order to force a procedural mindset on an event based programming language.

Disclaimer

Just to make sure, I do not recommend this style of software development; this is only related to porting old school code and is more or less designed to show you how software development has changed in time, from a period before most of you were even born.

Intro

  This is part of a series that I plan to build on as time goes on: technical interview questions, dissected and laid bare for both interviewers and interviewees. You can also check out the previous one: Interview question: all items in table A but not in B.

  This question is a little bit more complex and abstract at the same time. The post is written more for interviewers this time, because as candidates go, you need to read the links in it if you didn't know the concepts in it. This also is not a question with a single correct answer. It comes after asking about Dependency Injection as a whole and the candidate answering correctly.

  I expect senior developers to be able to go through this successfully, it is not a test for junior developers, although depending on their previous experience juniors might be able to go through it and seniors be force to reason through it.

The test

Bonus introduction question: why use DI at all? Expected answers would be separation of concerns and testability. 

  The question has two steps.

Step 1: given the following code in a legacy application, improve it to use Dependency Injection:

public SomeClass {
  public List<Item> GetItems(int days, string filter) {
    var service = new ItemService();
    return service.GetItems()
      .Where(i => i.Time >= DateTime.Now.AddDays(-days));
  }
}

Bonus questions:

  • has the candidate worked with LINQ before?
  • what does the code do?

Now, this question is about programming knowledge as it is for attention. There are three irregularities that can attract that attention:

  • the most obvious: the service is being instantiated by calling the constructor
    • the interviewer expects at the very least for the candidate to notice it and suggest moving the instantiation of the service in the constructor of the SomeClass class and inject it instead of using new
    • there is the possibility of passing the service as a parameter, as well, but suggest that the signature of the method should remain the same to get around it. Anyway, one can discuss the idea of moving all dependencies to the constructor and/or the calling methods and get insight in the way the candidate is thinking.
  • the unexplained string filter in the signature of the method
    • the interviewer can either tell the candidate that it will become relevant later, because it will, or that this is a method that implements an interface, to which a more snarky candidate might reply that SomeClass implements nothing (bonus for attention)
  • the use of DateTime.Now
    • it is a static property that gives a different output every time so it should be taken into account for Dependency Injection or at least for unit testing

By now you have filtered out the majority of failing candidates and you are left with someone who used or at least understands DI, can read and understand code, has used or at least understood basic LINQ and you have also gauged their level of attention to detail.

If the candidate only talked about the service and they decided to create an interface for ItemService and then add it as a parameter for the constructor of SomeClass, ask them to write a unit test for the method, explain to them that testability is one of the goals of DI if you didn't cover this already

  • bonus: see if they do unit testing or at least understand the concept
  • if they do attempt to write the unit test, ask them what would happen if you would run the test in different days

The expected result of this part is that the candidate understands the need of abstracting DateTime.Now. It is interesting to note how they intend to abstract it, since they do not have access to the code and it is a static method/property to abstract.

Whether the candidate figured it out by themselves or it was explained to them, the expected answer is that DateTime.Now is abstracted by creating an IDateTimeService interface that is implemented as a wrapper over DateTime.

At this point the code should look like this:

public SomeClass {
  private IItemService _itemService;
  private IDateTimeService _dateTimeService;

  public SomeClass(IItemService itemService, IDateTimeService dateTimeService) {
    _itemService = itemService;
    _dateTimeService = dateTimeService;
  }

  public List<Item> GetItems(int days, string filter) {
    return _itemService.GetItems()
      .Where(i => i.Time >= _dateTimeService.Now.AddDays(-days));
  }
}

Also, the candidate should be asked to write a unit test, just to see they know how, for bonus points. Note if the candidate understands isolation for unit testing or does something that would work but be silly like generate the test data based on current date or duplicate the code logic in the test instead of working with static data.

Step 2: tell the candidate that the legacy code they need to fix looks a bit different:

public SomeClass {
  public List<Item> GetItems(int days, string filter) {
    var service = new ItemService(filter);
    return service.GetItems()
      .Where(i => i.Time >= DateTime.Now.AddDays(-days));
  }
}

The ItemService now receives the filter as the parameter. Ask them what to do in this case.

The expected answer is a factory injected instead of the service, which will then be used to instantiate an IItemService with a parameter. Bonus discussion about software patterns can be inserted here.

There are other valid answers here, like using the DI container itself as a factory for the service, which might provoke interesting discussions in itself, like weighing constructor injection versus service provider in dependency injection and whether hybrid solutions might be better.

Bonus question: what if you cannot control the code of ItemService in step 1 and it does not implement an interface or a base class?

  • warning, this might give a hint for the second part of the interview, so use it at the end 
  • correct answer 1: use the class as the type of the parameter and let the dependency container decide how to instantiate it
  • correct answer 2: use a wrapper over the class that implements the interface and proxies to the instance methods.

Conclusion

For me this test told me a lot more about the candidate than just their dependency injection knowledge. We got to talking, I became aware of how their minds worked and I was both pleasantly surprised when they came with alternate solutions that kind of worked and a bit irked that they went that far and didn't see the superior option. Most of the time this made me think about the differences between what I would answer and what they did and this resulted in interesting discussions that enriched not only their experience, but also mine.

Dependency injection, separation of concerns and unit testing are important concepts for any modern developer. I hope this helps devs evolve and interviewers find the best candidates... at least until all of them get to read my blog.

Summary

Once you finished with the foundation, it doesn't matter who you call to architect your house or fix problems you might have. Businesses and software are exactly like that. Think hard about your foundation, it will save you a lot of effort later on. I've been working in a lot of different places and was surprised to see they didn't know there are other ways of doing things. I distill the foundational principles one needs for a good software solution and maybe not just software:

  • Separation of concerns - processes, components and people should be able to function in isolation. If you can test they work when everything else is shut down, you're good. People should only do what they are good at. Components should do only one thing.
  • Cleanliness - keep your code readable rather than efficient, your process flow intuitive, roles and responsibilities clear. Favor convention over documentation, document anything else.
  • Knowledge sharing - Allow knowledge to be free and alive in your organization by promoting knowledge sharing, collaborative documentation, searchability.

Intro

  I am not the greatest of all developers or architects, but I am good. I know how things should be and what they should do in order to reach a goal. When people ask me about software, my greatest gaps are around specific software tools or some algorithm, not the general craft. That is because of several reasons: I enjoy my work, I've been really enthusiastic in my youth and sponged everything I could in order to become better and I've worked in many different types of organizations so I know multiple ways in which people have tried to do this. As I grow older, the last one may be my most valuable skill, but I am yet to find the employer to realize this.

  You see, what I've learned from my career so far is that most businesses live in a bubble. Used to not only learn software development as I am working on some task, but also network with other people in the craft from all across the business, I kind of expected every other developer to be like that. Or at least the senior devs, the dev leads and architects, maybe some managers. But no, most of the time, people are stuck in their little position and never stray from it. They may invoke life work balance, or they are just burned out, or they just don't care enough, but more often, they haven't even realized what they are missing. And that's the bubble. A bubble is not a prison, is just a small area in which people stay voluntarily and never get out of.

  This is why gaming development is so different from business app development. That is why development in an administrative business with a small software department is so different from development in a software company. It is why development in small shops is so different than in large software companies. Sometimes people, really smart people, have worked for a long time in only one of these ecosystems and they only know that one. They can hardly conceive of different ways to do things.

  So this is why I am writing this post, to talk about the foundations of things, that part that separates one from the other, forever, no matter what you do afterwards. And this applies to business, people organization, but especially well to large software projects. You see, if you start your solution badly, it will be bad until you rewrite it. Just like a building with a weak foundation. It doesn't matter you bring the best workers and architects afterwards, they will only build a wonderful house that will fall down when the foundation fails. You want to make a good thing, first plan it through and build the greatest foundation you can think of and afford. It's much easier to change the roof than the foundation.

  And you wouldn't believe how many times I've been put in the situation of having to fix the unfixable. "Hey, you're smart, right? We started this thing a million years ago, we thought we would save some money, so we got a bunch of junior developers to do it, and it worked! But then it didn't anymore. Fix it!" And I have to explain it to them: you can't scale duct tape. You can go only so much with a thing held together by paper clips, chewing gum and the occasional hero employee with white hair and hunched back and in his twenties.

  Now of course, to an entitled senior engineer like me any software evokes the instinct to rewrite it in their own image. "Also, get some juniors to carve my face into that hill over there!". Sometimes it's just a matter of adapting to the environment, work with what you have. But sometimes you just have to admit things are beyond salvation. Going forward is just a recipe for disaster later on. It's the law of diminishing returns when the original returns were small to begin with. And you wouldn't believe how many people agree with that sentiment, then declare there is nothing that can be done. "They won't give us the budget!" is often muttered. Sometimes it's "We only need this for a few years. After that we start from scratch" and in a few years some "business person" makes a completely uninformed cost and gain analysis and decides building up from existing code is cheaper than starting over. But don't worry, they will suuuurely start from scratch next time.

  Sometimes the task of rewriting something is completely daunting. It's not just the size of it, or the feeling that you've achieved nothing if you have to start over to do the same thing. It's the dread that if you make the same thing and it takes less effort and less money and it works better then you must be inferior. And it's true! You sucked! Own it and do better next time. It's not the same thing, it's version 2.0. You now have something that you couldn't have dreamed of when building version 1.0: an overview. You know what you need, not what you think you will need. Your existing project is basically the D&D campaign you've played so many times that it has become a vast landscape, rich with characters and story. You've mapped it all down.

  This post is an overview. Use it! To be honest, reaching this point is inevitable, there will always be a moment when a version 2.0 makes more sense than continuing with what you have. But you can change how terrible your software is when you get to it. And for this you need the right foundation. And I can teach you to do that. It's not even hard.

Separation of Concerns

  Most important thing: separation of concerns. Components should not be aware of each other. Compare a Lego construction to a brick and mortar one. One you can disassemble and reassemble, adding to it whatever you need, the other you need to tear down and rebuild from zero. Your foundation needs to allow and even enable this. Define clear boundaries that completely separate the flow into independent parts. For example a job description is an interface. It tells the business that if the person occupying a job leaves, another can come and take their place. The place is clearly defined as a boundary that separates a human being from their role in the organization.

  Software components, too, need to be abstracted as interfaces in order to be able to swap them around. And I don't mean the exact concept of interface from some programming languages. I mean that as loosely as one can. A web service is an interface, since it abstracts business logic from user interface. A view model is an interface, as it abstracts the user interface logic from its appearance. A website is an interface, as it performs a different task than another that is completely separated. If you can rewrite an authorization component in isolation and then just replace the one you have and the application continues to work as before, that means you have done well.

  Separation of concerns should also apply to your work process and the people in it. A software developer should not have to do much outside developing software. A manager should just manage. People should only be in meetings that bring value and should only be in those that actually concern them. If the process becomes too cumbersome, split it up into smaller pieces, hire people to handle each of them. Free the time of your employees to do the job they are best suited for. 

  One important value you gain from isolating components is testing. In fact, you can use testing as a force towards separation of concerns. If you can test a part of your application in isolation (so all other parts do not need to be working for it), then you have successfully separated concerns. Consider a fictional flow: you get on the bus, you get to the market, you find a vegetable stand, you buy a kilo of tomatoes, you get back to the bus, you come home. Now, if you can successfully test your ability to get on a bus, any bus, to get anywhere the bus is going, in order to test that you can buy tomatoes from the market you just test you can find the stand and buy the tomatoes. Then, if you can test that you can buy anything at any type of stand, you only need to test your ability to find a stand in a market.

  It seems obvious, right? It feels that way to me. Even now, writing this post, I am thinking I sound like an idiot trying to seem smart, but I've seen droves of developers who don't even consider this. Businesses who are not even aware of this as a possibility. "We have testing teams to make sure the application is working end to end, we don't need unit testing" or "We have end to end automated testing. For each new feature we write new tests". When you hear this, fight it. Their tests, even if written correctly and maintained perfectly, will take as long as one needs to get on a bus and go to the market. And then the other test will take as long as one need to get on a train and get to the airport. And so on. End to end testing should exist and if you can automate it, great, but it should be sparse, it should function like an occasional audit, not something that supports your confidence in the solution working correctly.

  So go for testable, not for tests. Tests often get a bad wrap because someone like me comes and teaches a company to write tests, then they leave and the people in the company either skip testing occasionally or they change bits of the application and don't bother to update the tests. This leads to my next point: clean code.

Cleanliness

  Cleanliness applies to everything, again. The flow of your solution (note that I am being as general as possible) needs to be as clear as possible, at every level. In software this usually translates in readable code and builds up from that. Someone looking at the code should be able to instantly and easily understand what it does. Some junior developers want to write their code as efficient as possible. They just read somewhere that this method is faster than the other method and want to put that in code. But it boils down to a cost analysis: if they shave one second off a process you run ten times a day, they save one hour per year; if another developer has to spend more than one hour to understand what the code does, the gain means nothing.

  Code should be readable before being fast. Comments in code should document decisions, not explain what is going on. Comments should display information from another level than the code's. Component names, object names, method names, variable names should be self explanatory. Configuration structures, property names, property values, they should be intuitive and discoverable.

  And there is another aspect to cleanliness. Most development environments have some automated checks for your code. You can add more and even make your own. This results in lists of errors, warnings and notifications. On a flow level, this might translate to people complaining about various things, some in key positions, some not. Unit tests, once you have them, might be passing or failing. It is important to clean that shit up! Do not ignore warnings or even notifications. You think a warning is wrong, find a way to make it go away, not by ignoring it, but by replacing the complaining component, marking it specifically in the code as not a valid warning and document why, run all the tests and make sure they are green or remove the tests that you think are not important (this should not happen usually). The reason is simple: in a sea of ignored warnings you will not see the one that matters.

  To be perfectly clear: by clean code I don't mean code that follows design patterns, I don't mean documentation comments on every property and method, I don't mean color coded sections (although that's nice). What I mean is code clean enough to read without cringing or having to look in ten other places to figure out what it does. If your hotdog falls on that code you should be comfortable enough to pick it up and continue eating it.

  Cleanliness should and must be applied to your work process. If the daily meeting is dirty (many people talking about unrelated things) then everybody is wasting time. If the process of finishing a task is not clear, you will have headless chickens instead of professionals trying to complete it. If you have to ask around where to log your hours or who is responsible for a specific job that you need done in order to continue, you need to clean that process. Remove all superfluous things, optimize remaining ones. Remember separation of concerns.

  Cleanliness extends to your project folder structure, your solution structure, your organizational structure. It all has to be intuitive. If you declare a principle, it should inform every query and decision, with no exception. "All software development people are at the fifth floor! Ugh... all except Joe". What if you need Joe? What if you don't know that you need Joe, but you still need him? Favor convention over configuration/documentation, document everything else. And that leads me to the final point: knowledge sharing.

Knowledge Sharing

  To me, knowledge sharing was always natural. In small companies there was always "that guy" who would know everything and couldn't work at all because people came to ask him things. In medium companies there was always some sort of documentation of decisions and project details. In large companies there were platforms like Confluence where people would share structured information, like the complete description of tasks: what they are about, how decisions were made, who is responsible for what, how they were split into specific technical tasks, what problems arose, what the solutions were, etc. And there were always your peers that you could connect to and casually talk about your day.

  Imagine my surprise to find myself working in places where you don't know what anyone else is doing, where you don't know what something is and what it is supposed to do, there are no guidelines outside random and out of date Powerpoint files, where I am alone with no team, brought in for problems that need strong decisions in order to fix but no one is willing to make them, and already I have no idea who should even attempt to. I solve a common problem, I want to share the solution, there is no place to do that. People are not even in the same building as me. Emails are come and go and no one has time to read them.

  Knowledge should live freely in your company. You should be able to search for anything and find it, be able to understand it, contribute to it, add more stuff. It should be more natural for the people in your company to write a blog post than go for coffee and complain. It should be easier to find and consume information from people that left the company than to get it from colleagues at the desk next to you. And maybe this cannot be generalized to all departments, but it is fucking important: people in the office should never need to open Microsoft Office (or any similar product suite). I can't stress that enough.

  You should not need printed documents, so no need for Word. Excel files are great for simple data tasks, but they are not specific. If you need something done repeatedly and you use Excel sheet, it is probably better to build a tool for it. Don't reinvent the wheel now, but use the best tool for the job. And there are better and more modern tools than Powerpoint files, but I will allow the use of them because, in the context of knowledge sharing, everyone should feel free and confident enough to make presentation for the team. My tenet still stands, though: the Powerpoint file would be used in a presentation. Hardly anyone else should need to open it. I mean, there would be a video of the presentation available, right?

Vision

  Imagine a park. It is sunny, birds are singing, there are people walking on hardened dirt walkways, cyclers biking on their asphalted bike lanes, benches everywhere, with a small notepad attached to them that people can just pick up and read or write their own notes. Places in the park are clearly indicated with helpful arrows: children playground, hotdog stand, toilet, football field, bar, ice ring. Everything is clean, everybody is doing what they do best, all is good. You feel hungry, you see the arrow pointing towards the hotdog stand, you walk there calmly and ask for one. The boy there give you a bun and a wurst. He is new, but he has a colleague that knows exactly how much mustard and ketchup to put on the hotdog. He even asks you if you want curry on it. 

  Imagine a park. It is sunny, birds are singing. Some walkways start of as asphalt, then continue as dirt. Some stop suddenly or end in a ditch. There is a place that serves hotdogs next to a toilet. You have to ask around to find out where to find it. You get lost several times, as some people don't know either, but they still come with an opinion, or they are just misinformed. You get tired, but you can't sit on a bench, they are all taken and there are so few of them. You have to look both ways several times before you walk to the stand, because of cyclers. You stand in a line, then order a hotdog. The boy there gives you a bun with a wurst in it. You ask for mustard, but the boy is new and it takes him a while to find it after looking for some paper that tells him where it is. You have to dodge a football that was coming at your head. Someone flushes the toilet.

Intro

  This post will take you on an adventure through time and sound. It will touch the following software development concepts:

  • await/async in Javascript
  • named groups in regular expressions in Javascript
  • the AudioContext API in Javascript
  • musical note theory
  • Gorillas!

  In times immemorial, computers were running something called the DOS operating system and almost the entire interface was text based. There was a way to draw things on the screen, by setting the values of pixels directly in the video memory. The sound was something generated on a "PC speaker" which was a little more than a small speaker connected to a power port and which you had to make work by handling "interrupts". And yet, since this is when I had my childhood, I remember so many weird little games and programs from that time with a lot of nostalgic glee.

  One of these games was Gorillas, where two angry gorillas would attempt to murder each other by throwing explosive bananas. The player would have to enter the angle and speed and also take into account a wind speed that was displayed as an arrow on the bottom of the screen. That's all. The sounds were ridiculous, the graphics really abstract and yet it was fun. So, as I was remembering the game, I thought: what would it take to make that game available in a modern setting? I mean, the programming languages, the way people thought about development, the hardware platform, everything has changed.

  In this post I will detail the PLAY command from the ancient programming language QBASIC. This command was being used to generate sound by instructing the computer to play musical notes on the PC speaker. Here is an example of usage:

PLAY "MBT160O1L8CDEDCDL4ECC"

  This would play the short song at the beginning of the Gorillas game. The string tells the computer to play the sound in the background, at a tempo of 160 in the first octave, with notes of an eighth of a measure: CDEDCD then end with quarter measure notes: ECC. I want to replicate this with Javascript, one because it's simpler to prototype and second because I can make the result work in this very post.

Sound and Music

  But first, let's see how musical notes are being generated in Javascript, using the audio API. First you have to create an AudioContext instance, with which you create an Oscillator. On the oscillator you set the frequency and then... after a while you stop the sound. The reason why the API seems so simplistic is because it works by creating an audio graph of nodes that connect to each other and build on each other. There are multiple ways in which to generate sound, including filling a buffer with data and playing that, but I am not going to go that way.

  Therefore, in order to PLAY in Javascript I need to translate concepts like tempo, octaves, notes and measures into values like duration and frequency. That's why we need a little bit of musical theory.

  In music, sounds are split into domains called octaves, each holding seven notes that, depending on your country, are either Do, Re, Mi, Fa, So, La, Si or A, B,C, D, E, F and G or something else. Then you have half notes, so called sharp or flat notes: A# is half a note above A and A♭ is a half note below A. A# is the same as B♭. For reasons that I don't want to even know, the octaves start with C. Also the notes themselves are not equally spaced. The octaves are not of the same size, in terms of frequency. Octave 0 starts at 16.35Hz and ends at 30.87, octave 1 ranges between 32.70 and 61.74. In fact, each octave spreads on twice as much frequency space as the one before. Each note has twice the frequency of the same note on the lower octave.

  In a more numerical way, octaves are split into 12: C, C#, D, E♭, E, F, F#, G, G#, A, B♭, B. Note (heh heh) that there are no half notes between B and C and E and F. The frequency of one of these notes is 21/12 times the one before. Therefore one can compute the frequency of a note as:

Frequency = Key note * 2n/12, where the key note is a note that you use as a base and n is the note-distance between the key note and the note you want to play.

  The default key note is A4, or note A from octave 4, at 440Hz. That means B♭ has a frequency of 440*1.059463 = 466.2.

  Having computed the frequency, we now need the duration. The input parameters for this are: tempo, note length, mode and the occasional "dot":

  • tempo is the number of quarter measures in a minute
    • this means if the tempo is 120, a measure is 60000 milliseconds divided by 120, then divided by 4, so 125 milliseconds
  • note length - the length of a note relative to a measure
    • these are usually fractions of a measure: 1, 1/2, 1/4, 1/8, 1/16, etc
  • mode - this determines a general speed of playing the melody
    • as defined by the PLAY command, you have:
      • normal: a measure is 7/8 of a default measure
      • legato: a measure is a measure
      • staccato: a measure is 3/4 of a default measure
  • dotted note - this means a specific note will be played for 3/2 of the defined duration for that note

  This gives us the formula:

Duration = note length * mode * 60000 / 4 / tempo * dotDuration

Code

  With this knowledge, we can start writing code that will interpret musical values and play a sound. Now, the code will be self explanatory, hopefully. The only thing I want to discuss outside of the audio related topic is the use of async/await in Javascript, which I will do below the code. So here it is:

class QBasicSound {

    constructor() {
        this.octave = 4;
        this.noteLength = 4;
        this.tempo = 120;
        this.mode = 7 / 8;
        this.foreground = true;
        this.type = 'square';
    }

    setType(type) {
        this.type = type;
    }

    async playSound(frequency, duration) {
        if (!this._audioContext) {
            this._audioContext = new AudioContext();
        }
        // a 0 frequency means a pause
        if (frequency == 0) {
            await delay(duration);
        } else {
            const o = this._audioContext.createOscillator();
            const g = this._audioContext.createGain();
            o.connect(g);
            g.connect(this._audioContext.destination);
            o.frequency.value = frequency;
            o.type = this.type;
            o.start();
            await delay(duration);
            // slowly decrease the volume of the note instead of just stopping so that it doesn't click in an annoying way
            g.gain.exponentialRampToValueAtTime(0.00001, this._audioContext.currentTime + 0.1);
        }
    }

    getNoteValue(octave, note) {
        const octaveNotes = 'C D EF G A B';
        const index = octaveNotes.indexOf(note.toUpperCase());
        if (index < 0) {
            throw new Error(note + ' is not a valid note');
        }
        return octave * 12 + index;
    }

    async playNote(octave, note, duration) {
        const A4 = 440;
        const noteValue = this.getNoteValue(octave, note);
        const freq = A4 * Math.pow(2, (noteValue - 48) / 12);
        await this.playSound(freq, duration);
    }

    async play(commandString) {
        const reg = /(?<octave>O\d+)|(?<octaveUp>>)|(?<octaveDown><)|(?<note>[A-G][#+-]?\d*\.?)|(?<noteN>N\d+\.?)|(?<length>L\d+)|(?<legato>ML)|(?<normal>MN)|(?<staccato>MS)|(?<pause>P\d+\.?)|(?<tempo>T\d+)|(?<foreground>MF)|(?<background>MB)/gi;
        let match = reg.exec(commandString);
        let promise = Promise.resolve();
        while (match) {
            let noteValue = null;
            let longerNote = false;
            let temporaryLength = 0;
            if (match.groups.octave) {
                this.octave = parseInt(match[0].substr(1));
            }
            if (match.groups.octaveUp) {
                this.octave++;
            }
            if (match.groups.octaveDown) {
                this.octave--;
            }
            if (match.groups.note) {
                const noteMatch = /(?<note>[A-G])(?<suffix>[#+-]?)(?<shorthand>\d*)(?<longerNote>\.?)/i.exec(match[0]);
                if (noteMatch.groups.longerNote) {
                    longerNote = true;
                }
                if (noteMatch.groups.shorthand) {
                    temporaryLength = parseInt(noteMatch.groups.shorthand);
                }
                noteValue = this.getNoteValue(this.octave, noteMatch.groups.note);
                switch (noteMatch.groups.suffix) {
                    case '#':
                    case '+':
                        noteValue++;
                        break;
                    case '-':
                        noteValue--;
                        break;
                }
            }
            if (match.groups.noteN) {
                const noteNMatch = /N(?<noteValue>\d+)(?<longerNote>\.?)/i.exec(match[0]);
                if (noteNMatch.groups.longerNote) {
                    longerNote = true;
                }
                noteValue = parseInt(noteNMatch.groups.noteValue);
            }
            if (match.groups.length) {
                this.noteLength = parseInt(match[0].substr(1));
            }
            if (match.groups.legato) {
                this.mode = 1;
            }
            if (match.groups.normal) {
                this.mode = 7 / 8;
            }
            if (match.groups.staccato) {
                this.mode = 3 / 4;
            }
            if (match.groups.pause) {
                const pauseMatch = /P(?<length>\d+)(?<longerNote>\.?)/i.exec(match[0]);
                if (pauseMatch.groups.longerNote) {
                    longerNote = true;
                }
                noteValue = 0;
                temporaryLength = parseInt(pauseMatch.groups.length);
            }
            if (match.groups.tempo) {
                this.tempo = parseInt(match[0].substr(1));
            }
            if (match.groups.foreground) {
                this.foreground = true;
            }
            if (match.groups.background) {
                this.foreground = false;
            }

            if (noteValue !== null) {
                const noteDuration = this.mode * (60000 * 4 / this.tempo) * (longerNote ? 1 : 3 / 2);
                const duration = temporaryLength
                    ? noteDuration / temporaryLength
                    : noteDuration / this.noteLength;
                const A4 = 440;
                const freq = noteValue == 0
                    ? 0
                    : A4 * Math.pow(2, (noteValue - 48) / 12);
                const playPromise = () => this.playSound(freq, duration);
                promise = promise.then(playPromise)
            }
            match = reg.exec(commandString);
        }
        if (this.foreground) {
            await promise;
        } else {
            promise;
        }
    }
}

function delay(duration) {
    return new Promise(resolve => setTimeout(resolve, duration));
}

One uses the code like this:

var player = new QBasicSound();
await player.play('T160O1L8CDEDCDL4ECC');

Note that you cannot start playing the sound directly, you need to wait for a user interaction first. An annoying rule to suppress annoying websites which would start playing the sound on load. And here is the result (press multiple times on Play for different melodies):

Javascript in modern times

There are two concepts that were used in this code that I want to discuss: named regular expression groups and async/await. Coincidentally, both are C# concepts that have crept up in the modern Javascript specifications when .NET developers from Microsoft started contributing to the language.

Named groups are something that appeared in ES2018 and it is something I've been using with joy in .NET and hated when I didn't have it in some other language. Look at the difference between the original design and the current one:

// original design
var match = /(a)bc/.exec('abcd');
if (match && match[1]) { /*do something with match[1]*/ }

// new feature
const match = /(?<theA>a)bc/.exec('abcd');
if (match && match.groups.theA) { /*do something with match.groups.theA*/ }

There are multiple advantages to this:

  • readability for people revisiting the code
  • robustness in the face of changes to the regular expression
    • the index might change if new groups are added to it
  • the code aligns with the C# code (I like that :) )

My advice is to always use named groups when using regular expressions.

Another concept is await/async. In .NET it is used to hide complex asynchronous interactions in the code and with the help of the compiler helps with all the tasks that are running at the same time. Unfortunately, in C#, that means polluting code with async keywords on all levels as async methods can only be used inside other async methods. No such qualms in Javascript.

While in .NET the await/async system runs over Task<T> methods, in Javascript it runs over Promises. Both are abstractions over work that is being done asynchronously.

A most basic example is this:

// original design
getSomethingAsync(url,function(data) {
  getSomethingElseAsync(data.url,function(data2) {
    // do something with data2
  }, errorHandler2);
},errorHandler1);

// Promises
getSomethingAsync(url)
  .then(function(data) {
    getSomethingElseAsync(data.url);
  })
  .then(function(data2) {
    // so something with data2
  })
  .catch(errorHandler);

// async/await
try {
  var data = await getSomethingAsync(url);
  var data2 = await getSomethingElseAsync(data.url);
  // do something with data2
} catch(ex) {
  errorHandler(ex);
}

You see that the await/async way looks like synchronous code, you can even catch errors. await can be used on any function that returns a Promise instance and the result of it is a non-blocking wait until the Promise resolves and returns the value that was passed to the resolve function.

If you go back to the QBasicSound class, at the end, depending on if the sound is in the foreground or background, the function is either awaiting a promise or ... just letting it run. You might also notice that I've added a delay function at the end of the code which is using setTimeout to resolve a Promise. Here is what is actually going on:

// using await
console.log(1);
await delay(1000).then(()=>console.log(2));
console.log(3);
// this logs 1,2,3


// NOT using await
console.log(1);
delay(1000).then(()=>console.log(2));
console.log(3);
// this logs 1,3,2

In the first case, the Promise that was constructed by a one second delay and then logging 2 is awaited, meaning the code waits for the result. After it is executed, 3 gets logged. In the second case, the logging of 2 is executed after one second delay, but the code does not wait for the result, therefore 3 is logged immediately and 2 comes after.

What sorcery is this?! Isn't Javascript supposed to be single threaded? How does it work? Well, consider that in the delay function, the resolve function will only be called after a timeout of one second. When executed, it starts the timeout, then reaches the end of the function. It has not been resolved yet, so it passes control back to the engine, which uses it to execute other things. When the timeout is fired, the engine takes back control, executes the resolve function, then passes control back. All of this is invisible to the user, who gets the illusion of multithreaded behavior.

Already some standard out of the box APIs are async, like fetch. In order to get an object from a REST API that is called via HTTP the code would look like this:

// fetch API
let response = await fetch('/article/promise-chaining/user.json');
let user = await response.json();

Conclusion

I spent an entire day learning about sounds and writing code that would emulate QBASIC code from a billion years ago. Who knows, maybe my next project will be to port the entire Gorillas game in Javascript. Now one can lovingly recreate the sounds of one's childhood.

Other references:

Gorillas.BAS

QBasic/Appendix

Generate Sounds Programmatically With Javascript

Musical Notes

Gorrilas game online

  On the SQLite reference page for the WITH clause there is a little example of solving a Sudoku puzzle. Using SQL. I wanted to see it in action and therefore I've translated it into T-SQL.

  You might think that there is a great algorithm at play, something that will blow your mind. I mean, people have blogged about Sudoku solvers to hone their programming skills for ages and they have worked quite a lot, writing lines and lines of how clever they were. And this is SQL, it works, but how do you do something complex in it? But no, it's very simple, very straightforward and also performant. Kind of a let down, I know, but it pretty much takes all possible solutions and only selects for the valid ones using CTEs (Common Table Expressions).

  Here is the translation, followed by some explanation of the code:

DECLARE @Board VARCHAR(81) = '86....3...2...1..7....74...27.9..1...8.....7...1..7.95...56....4..1...5...3....81';
WITH x(s,ind) AS
(
  SELECT sud,CHARINDEX('.',sud) as ind FROM (VALUES(@Board)) as input(sud)
  UNION ALL
  SELECT
	CONVERT(VARCHAR(81),CONCAT(SUBSTRING(s,1,ind-1),z,SUBSTRING(s,ind+1,81))) as s,
	CHARINDEX('.',CONCAT(SUBSTRING(s,1,ind-1),z,SUBSTRING(s,ind+1,81))) as ind
  FROM x
  INNER JOIN (VALUES('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9')) as digits(z)
  ON NOT EXISTS (
            SELECT 1
              FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) as positions(lp)
             WHERE z = SUBSTRING(s, ((ind-1)/9)*9 + lp, 1)
                OR z = SUBSTRING(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
                OR z = SUBSTRING(s, (((ind-1)/3) % 3) * 3
                        + ((ind-1)/27) * 27 + lp
                        + ((lp-1) / 3) * 6, 1)
	)
	WHERE ind>0
)
SELECT s FROM x WHERE ind = 0

  The only changes from the original code I've done is to extract the unsolved puzzle into its own variable and to change the puzzle values. Also, added a more clear INNER JOIN syntax to replace the obnoxious, but still valid, comma (aka CROSS JOIN) notation. Here is the breakdown of the algorithm, as it were:

  • start with an initial state of the unsolved puzzle as a VARCHAR(81) string and the first index of a dot in that string, representing an empty slot - this is the anchor part
  • for the recursive member, join the current state with all the possible digit values (1 through 9) and return the strings with the first empty slot replaced by all valid possibilities and the position of the next empty slot
  • stop when there are no more empty slots
  • select the solutions (no empty slots)

  It's that simple. And before you imagine it will generate a huge table in memory or that it will take a huge time, worry not. It takes less than a second (a lot less) to find the solution. Obviously, resource use increases exponentially when the puzzle doesn't have just one solution. If you empty the first slot (. instead of 8) the number of rows is 10 and it takes a second to compute them all. Empty the next slot, too (6) and you get 228 solutions in 26 seconds and so on.

 The magical parts are the recursive Common Table Expression itself and the little piece of code that checks for validity, but the validity check is quite obvious as it is the exact translation of the Sudoku rules: no same digits on lines, rows or square sections.

  A recursive CTE has three parts:

  • an initial query that represents the starting state, often called the anchor member
  • a recursive query that references the CTE itself, called the recursive member, which is UNIONed with the anchor
  • a termination condition, to tell SQL when to end the recursion

  For us, we started with one unsolved solution, we recursed on all possible valid solutions for replacing the first empty slot and we stopped when there were no more empty slots.

  CTEs are often confusing because the notation seems to indicate something else to a procedural programmer. You imagine doing this without CTEs, maybe in an object oriented programming language, and you think of this huge buffer that just keeps increasing and you have to remember where you left off so you don't process the same partial solution multiple times and you have to clean the data structure so it doesn't get too large, etc. SQL, though, is at heart a declarative programming language, very close to functional programming. It will take care not only of the recursion, but also filter the rows by the final condition of no empty slots while (and sometimes before) it makes the computations.

  Once you consider the set of possible solutions for a problem as a working set, SQL can do wonders to find the solution, provided you can encode it in a way the SQL engine will understand. This is just another example of the right tool for the right job. Hope you learned something.

  This is something that appeared in C# 5, so a long time ago, with .NET 4.5, but I only found out about it recently. Remember when you wanted to know the name of a property when doing INotifyPropertyChanged? Or when you wanted to log the name of the method that was calling? Or you wanted to know which line in which source file is responsible for calling a certain piece of code? All of this can be done with the Caller Information feature.

  And it is easy enough to use, just decorate a method parameter with an explicit default value with any of these three attributes:

The parameter value, if not set when calling the method, will be filled in with the member name or file name or line number. It's something that the compiler does, so no overhead from reflection. Even better, it works on the caller of the method, not the interior of the method. Imagine you had to write a piece of code to do the same. How would you reference the name of the method calling the method you are in?

Example from Microsoft's site:

public void DoProcessing()
{
    TraceMessage("Something happened.");
}

public void TraceMessage(string message,
        [System.Runtime.CompilerServices.CallerMemberName] string memberName = "",
        [System.Runtime.CompilerServices.CallerFilePath] string sourceFilePath = "",
        [System.Runtime.CompilerServices.CallerLineNumber] int sourceLineNumber = 0)
{
    System.Diagnostics.Trace.WriteLine("message: " + message);
    System.Diagnostics.Trace.WriteLine("member name: " + memberName);
    System.Diagnostics.Trace.WriteLine("source file path: " + sourceFilePath);
    System.Diagnostics.Trace.WriteLine("source line number: " + sourceLineNumber);
}

// Sample Output:
//  message: Something happened.
//  member name: DoProcessing
//  source file path: c:\Visual Studio Projects\CallerInfoCS\CallerInfoCS\Form1.cs
//  source line number: 31

  So you want to use a queue, a structure that has items added at one side and removed on another, in Javascript code. Items are added to the tail of the queue, while they are removed at the head. We, Romanians, are experts because in the Communist times resources were scarce and people often formed long queues to get to them, sometimes only on the basis of rumour. They would see a line of people and ask "Don't they have meat here?" and the answer would come "No, they don't have milk here. It's next building they don't have meat at". Anyway...

  There is an option that can be used directly out of the box: the humble array. It has methods like .push (add an item), .pop (remove the latest added item - when you use it as a stack) and .shift (remove the oldest added item - when you use it as a queue). For small cases, that is all you need.

  However, I needed it in a high performance algorithm and if you think about it, removing the first element of an array usually means shifting (hence the name of the function) all elements one slot and decreasing the length of the array. Consider a million items array. This is not an option.

  One of the data structure concepts we are taught at school is the linked list. Remember that? Each item has a reference to the next (and maybe the previous) item in the list. You explore it by going from one item to the next, without indexing, and you can remove any part of the list or add to any part of the list just by changing the value of these references. This also means that for each value you want stored you have the value, the reference(s) and the overhead of handling a more complex data object. Again, consider a million numbers array. It's not the right fit for this problem.

  Only one option remains: still using an array, but moving the start and the end of the array in an abstract manner only, so that all queue/dequeue operations take no effort. This means keeping a reference to the tail and the head of the queue in relation to the length of the queue and of the underlying array.

  But first let's establish a baseline. Let's write a test and implement a queue using the default array pop/shift implementation:

// the test
const size = 100000;
const q=new Queue();
time(()=> { for (let i=0; i<size; i++) q.enqueue(i); },'Enqueue '+size+' items');
time(()=> { for (let i=0; i<size; i++) q.dequeue(i); },'Dequeue '+size+' items');
time(()=> { for (let i=0; i<size/10; i++) {
	for (let j=0; j<10; j++) q.enqueue(i);
	for (let j=0; j<9; j++) q.dequeue(i);
} },'Dequeue and enqueue '+size+' items');

// the Queue implementation
class Queue {
  constructor() {
    this._arr = [];
  }

  enqueue(item) {
    this._arr.push(item);
  }

  dequeue() {
    return this._arr.shift();
  }
}

// the results
Enqueue 100000 items, 10ms
Dequeue 100000 items, 1170ms
Dequeue and enqueue 100000 items, 19ms

  The Enqueue operation is just adding to an array, enqueuing and dequeuing by leaving an item at ever series of dequeues is slightly slower, as the amount of array shifting is negligible. Dequeuing, though, is pretty heavy. Note that increasing just a little bit the amount of items leads to an exponential increase in time:

Enqueue 200000 items, 12ms
Dequeue 200000 items, 4549ms
Dequeue and enqueue 200000 items, 197ms

  Now let's improve the implementation of the queue. We will keep enqueue using Array.push, but use a _head index to determine which items to dequeue. This means faster speed, but the queue will never shorten. It's the equivalent of Romanians getting their product, but remaining in the queue.

// the Queue implementation
class Queue {
  constructor() {
    this._arr = [];
    this._head = 0;
  }

  enqueue(item) {
    this._arr.push(item);
  }

  dequeue() {
    if (this._head>=this._arr.length) return;
    const result = this._arr[this._head];
    this._head++;
    return result;
  }
}

// the results
Enqueue 200000 items, 11ms
Dequeue 200000 items, 4ms
Dequeue and enqueue 200000 items, 11ms

  The performance has reached the expected level. Dequeuing is now even faster than enqueuing because it doesn't need to expand the array as items are added. However, for all scenarios the queue is only growing, even when dequeuing all the items. What I can do is reuse the slots of the dequeued items for the items to be added. Now it gets interesting!

  My point is that right now we can improve the functionality of our queue by replacing dequeued but still stored items with newly enqueued items. That is the equivalent of Romanians leaving the queue only after they get the meat and a new Romanian comes to take their place. If there are more people coming than getting served, then people that got their meat will all leave and we can just add people to the tail of the queue.

  So let's recap the algorithm:

  • we will use an array as a buffer
  • the queue items start at the head and end at the tail, but wrap around the array buffer
  • whenever we add an item, it will be added in the empty space inside the array and the tail will increment
  • if there is no empty space (queue length is the same as the array length) then the array will be rearranged so that it has space for new itms
  • when we dequeue, the item at the head will be returned and the head incremented
  • whenever the head or tail reach the end of the array, they will wrap around

Some more improvements:

  • if we enqueue a lot of items then dequeue them, the array will not decrease until we dequeue them all. An improvement is to rearrange the array whenever the queue length drops below half of that of the array. It will add computation, but reduce space.
  • when we make space for new items (when the array size is the same as the one of the logical queue) we should add more space than just 1, so I will add the concept of a growth factor and the smallest size increase.

Here is the code:

/**
 * A performant queue implementation in Javascript
 *
 * @class Queue
 */
class Queue {

    /**
     *Creates an instance of Queue.
     * @memberof Queue
     */
    constructor() {
        this._array = [];
        this._head = 0;
        this._tail = 0;
        this._size = 0;
        this._growthFactor = 0.1;
        this._smallestSizeIncrease = 64;
    }

    /**
     * Adding an iterator so we can use the queue in a for...of loop or a destructuring statement [...queue]
     */
    *[Symbol.iterator]() {
        for (let i = 0; i < this._size; i++) {
            yield this.getAt(i);
        }
    }

    /**
     * Returns the length of the queue
     *
     * @readonly
     * @memberof Queue
     */
    get length() {
        return this._size;
    }

    /**
     * Get item based on item in the queue
     *
     * @param {*} index
     * @returns
     * @memberof Queue
     */
    getAt(index) {
        if (index >= this._size) return;
        return this._array[(this._head + index) % this._array.length];
    }

    /**
     * Gets the item that would be dequeued, without actually dequeuing it
     *
     * @returns
     * @memberof Queue
     */
    peek() {
        return this.getAt(0);
    }

    /**
     * Clears the items and shrinks the underlying array
     */
    clear() {
        this._array.length = 0;
        this._head = 0;
        this._tail = 0;
        this._size = 0;
    }

    /**
     * Adds an item to the queue
     *
     * @param {*} obj
     * @memberof Queue
     */
    enqueue(obj) {
        // special case when the size of the queue is the same as the underlying array
        if (this._size === this._array.length) {
            // this is the size increase for the underlying array
            const sizeIncrease = Math.max(this._smallestSizeIncrease, ~~(this._size * this._growthFactor));
            // if the tail is behind the head, it means we need to move the data from the head to 
            // the end of the array after we increase the array size
            if (this._tail <= this._head) {
                const toMove = this._array.length - this._head;
                this._array.length += sizeIncrease;
                for (let i = 0; i < toMove; i++) {
                    this._array[this._array.length - 1 - i] = this._array[this._array.length - 1 - i - sizeIncrease];
                }
                this._head = (this._head + sizeIncrease) % this._array.length;
            }
            else
            // the array size can just increase (head is 0 and tail is the end of the array)
            {
                this._array.length += sizeIncrease;
            }
        }
        this._array[this._tail] = obj;
        this._tail = (this._tail + 1) % this._array.length;
        this._size++;
    }

    /**
     * Removed the oldest items from the queue and returns it
     *
     * @returns
     * @memberof Queue
     */
    dequeue() {
        if (this._size === 0) {
            return undefined;
        }
        const removed = this._array[this._head];
        this._head = (this._head + 1) % this._array.length;
        this._size--;
        // special case when the size of the queue is too small compared to the size of the array
        if (this._size > 1000 && this._size < this._array.length / 2 - this._smallestSizeIncrease) {
            if (this._head<this._tail) {
                this._array = this._array.slice(this._head,this._tail);
            } else {
                this._array=this._array.slice(this._head, this._array.length).concat(this._array.slice(0,this._tail));
            }
            this._head = 0;
            this._tail = 0;
        }   
        return removed;
    }
}

  Final notes:

  • there is no specification on how an array should be implemented in Javascript, therefore I've used the growth factor concept, just like in C#. However, according to James Lawson, the array implementation is pretty smart in modern Javascript engines, we might not even need it.
  • the optimization in dequeue might help with space, but it could be ignored if what you want is speed and don't care about the space usage
  • final benchmarking results are:
    Enqueue 200000 items, 15ms, final array size 213106
    Dequeue 200000 items, 19ms, final array size 1536
    Dequeue and enqueue 200000 items, 13ms, final array size 20071

  While working on my pet project Linqer (LINQ for Javascript and Typescript) I've spent quite a lot of time improving the performance of the Quicksort algorithm I am using for .orderBy. Therefore I am publishing it here, even if you could extract it just the same from the Linqer sources, with limited discussion on what is going on.

  Why

  First, why use it at all? Doesn't Javascript have the .sort method in the Array class? What's wrong with that?

  The answer is that the implementation for sort is different from browser to browser, or better said, from Javascript engine to Javascript engine. In Chrome, for example, the algorithm used is insertion sort, which is simple, in place, stable and reasonably fast. It is optimized for the most common usage: small arrays that need to be sorted for UI purposes and such. However, when using large arrays, the algorithm doesn't perform as well as one might expect.

  For Linqer I had an additional reason, because I would use ordering followed by skip and take methods that limited the scope of the need for sorting. Imagine a million items array that I wanted ordered and then needed the first ten items. Sorting the entire thing for just ten items would have been overkill. The default .sort function doesn't have parameters for such scenarios.

  And there is another reason: the default function used to compare array items is alphanumeric. [1, 2, 10] would get ordered as [1, 10, 2].

  Second, why Quicksort? There are a bunch of sorting algorithms out there. Mergesort, Heapsort, Radixsort, Timsort, Selectionsort. What's so special about Quicksort.

  I have to admit that I went for it by googling fast sorting algorithm. It does have "quick" in the name, doesn't it? I also found it elegant and easy to comprehend. And for my particular scenario, I liked that it used a divide et impera strategy which allowed me to ignore parts of the array if I didn't need the items there. In other words, it's very well suited both as a general sorting algorithm and a partial sorting algorithm.

  What

  I would like to tell you that it's simple to explain what Quicksort does, but it requires some amount of attention and time. In general terms, it chooses an arbitrary item (called a pivot) then orders the remaining items relative to the pivot, in two so called partitions: the smaller items to the left, the larger to the right. Then it repeats the process for each of the two sides. How the pivot is chosen and how the partitions are handled is what differentiates Quicksort algorithms and determines their performance.

  It is an in place algorithm, meaning it doesn't copy the array in some other type of structure and instead it moves items around inside it. It is not a stable algorithm, meaning the order of "equal" items is not preserved. The average computational complexity is O(n log n), with the worst cases O(n^2). The space complexity is harder to determine. Most people say it is O(1) because it uses no additional data structures, but that is not really correct. Being a recursive algorithm, the call stack gets used quite a lot, an invisible storage that should be computed in the data complexity.

  Unfortunately, the worst case scenarios are also very common: already sorted arrays and arrays filled with the same value. There are various optimizations to be used in order to handle this sort of thing. Also, Quicksort is efficient with large quantities of data, but less so with small numbers of items.

  How

  Finally, we get to the code. The _quicksort function receives:

  • an array
  • left and right index values determining the inclusive area that will be sorted (usually 0 and array.length-1)
  • a comparer function (item1,item2)=> 1, 0 or -1 and that defaults to _defaultComparer which tries to sort items based on the > and < operators
  • min and max index values determining the window of the array that we need to have sorted

The left and right indexes determine which section (before the sort) of the array will be sorted, the min and max indexes determine which items I am interested in (after the sort). This allows me to skip ordering partitions that are outside my area of interest.

As I said, the pivot choice is important. Some strategies are very popular:

  • the last item in the array as the pivot
    • this is the strategy used in the original incarnation of Quicksort
    • leads to very poor performance when the array is already sorted
  • the median item
    • this suggests parsing the array in order to get the value, implying extra computation
    • it only makes sense when the values in the array are numbers
  • the average between the first, the last and the middle item
    • it only makes sense when the values in the array are numbers
  • the item that is in the middle of the array
    • this is the one that I am using
  • a random item in the array
    • this makes the algorithm escape scenarios where the performance would be bad
    • the outcome of the sorting is unpredictable in terms of time used and stability of items
  • multiple pivots
    • an interesting concept, but one that complicated the algorithm too much for comfort

Then there is the matter of the partitioning. I've used an optimization that involves two indexes, one at the start the other at the end of a partition, coming toward each other and swapping items that are on the wrong side of the pivot. In some implementations, if the pivot is the last item, the partitioning is from one side only. In others, multiple indexes are used to handle multiple pivots.

In most implementations, the algorithm recurses on _quicksort, but I refactored it to only recurse on the partitioning. Then, because I didn't want to get stack overflows when bad data was used, I've eliminated the recursion and instead used a stack of my own where the partitions to be sorted are stored and wait their turn. This is where the data complexity comes around. In my case I was using a little more data than I actually needed, because I was adding partitions to the stack and also incrementing the index of the current partition, meaning the stack array grew with handled partitions. Even if there is no computation performance benefit, I've optimized this as well by adding a queueIndex which is used to recycle the slots in the partition array that are behind the partitionIndex. New partitions are being added behind the partitionIndex and queueIndex is incremented. When the loop reaches the last partition in the stack, a new loop is started with the partitions from 0 to queueIndex. Thus, for a ten million item array the partition stack rarely goes above 40000 in length.

A further optimization is to use insertion sort on partitions that have become too small (under 64 items). It irks me to have had to do this, I would have liked to use a "pure" algorithm, but this improved the performance and minimized the size of the partition stack.

The Code

That's about it. Here is the code:

    function _insertionsort(arr, leftIndex, rightIndex, comparer) {
        for (let j = leftIndex; j <= rightIndex; j++) {
            const key = arr[j];
            let i = j - 1;
            while (i >= leftIndex && comparer(arr[i], key) > 0) {
                arr[i + 1] = arr[i];
                i--;
            }
            arr[i + 1] = key;
        }
    }
    function _swapArrayItems(array, leftIndex, rightIndex) {
        const temp = array[leftIndex];
        array[leftIndex] = array[rightIndex];
        array[rightIndex] = temp;
    }
    function _partition(items, left, right, comparer) {
        const pivot = items[(right + left) >> 1];
        while (left <= right) {
            while (comparer(items[left], pivot) < 0) {
                left++;
            }
            while (comparer(items[right], pivot) > 0) {
                right--;
            }
            if (left < right) {
                _swapArrayItems(items, left, right);
                left++;
                right--;
            }
            else {
                if (left === right)
                    return left + 1;
            }
        }
        return left;
    }
    const _insertionSortThreshold = 64;
    function _quicksort(items, 
                        left, right, comparer = _defaultComparer,
                        minIndex = 0, maxIndex = Number.MAX_SAFE_INTEGER) {
        if (!items.length)
            return items;
        const partitions = [];
        partitions.push({ left, right });
        while (partitions.length) {
            ({ left, right } = partitions.pop());
            if (right - left < _insertionSortThreshold) {
                _insertionsort(items, left, right, comparer);
                continue;
            }
            const index = _partition(items, left, right, comparer);
            if (left < index - 1 && index - 1 >= minIndex) {
                partitions.push({ left, right: index - 1 });
            }
            if (index < right && index < maxIndex) {
                partitions.push({ left: index, right });
            }
        }

        return items;
    }
    _defaultComparer = (item1, item2) => {
        if (item1 > item2)
            return 1;
        if (item1 < item2)
            return -1;
        return 0;
    };

So I was trying to optimize a sorting algorithm, only the metrics did not make any sense. On the test page I had amazing performance, on the other it was slow as hell. What could possibly be the problem?

The difference between the two tests was that one was sorting inline (normal array reading and writing) and the other was using a more complex function and iterated a data source. So I went to test the performance of iterating itself.

The code tests the speed of adding all the items of a large array in three cases:

  • a classic for...in loop that increments an index and reads the array at that index
  • a for...of loop that iterates the items of the array directly
  • a for...of loop that iterates over a generator function that yields the values of the array
time(()=>{ let sum=0; for (let i=0; i<arr.length; i++) sum+=arr[i]; },'for in');
time(()=>{ let sum=0; for (const v of arr) sum+=v; },'iterator for of');
time(()=>{ let sum=0; for (const v of (function*(){ for (let i=0; i<arr.length; i++) yield arr[i]; })()) sum+=v; },'generator for of');

time is a function I used to compute the speed of the execution. The array is 100 million integers. And here are the results:

for in: 155.12999997008592
for of: 1105.7250000303611
for of: 2309.88499999512

I haven't yet processed what it means, but I really thought using an iterator was going to be at least as fast as a for loop that uses index accessing to read values. Instead there is a whooping 7 to 14 times decrease in speed.

So from now on I will avoid for...of in high performance scenarios.

Just a thing I learned today: using the bitwise not operator (~) on a number in Javascript ignores its fractional part (it converts it to integer first), therefore using it twice gives you the integer part of original number. Thanks to fetishlace for clarifications.

Notes:

  • this is equivalent to (int)number in languages that support the int type
  • this is equivalent to Math.trunc for numbers in the integer range
  • this is equivalent to Math.floor only for positive numbers in the integer range

Examples:
~~1.3 = 1
~~-6.5432 = -6
~~(2 ** 32 + 0.5) = 0
~~10000000000 = 1410065408

P.S. If you don't know what ** is, it's called the Exponentiation operator and it came around in Javascript ES2016 (ES7) and it is the equivalent of Math.pow. 2 ** 3 = Math.pow(2,3) = 8

and has 2 comments

  Sometimes a good regular expression can save a lot of time and lead to a robust, yet flexible system that works very efficiently in terms of performance. It may feel like having superpowers. I don't remember when exactly I've decided they were useful, but it happened during my PHP period, when the Linux command line system and its multitude of tools made using regular expressions a pretty obvious decision. Fast forward (waaaay forward) and now I am a .NET developer, spoiled by the likes of Visual Studio and the next-next approach to solving everything, yet I still use regular expressions, well... regularly, sometimes even when I shouldn't. The syntax is concise, flexible and easy to use most of the time.

  And yet I see many senior developers avoiding regular expressions like they were the plague. Why is that? In this post I will argue that the syntax makes a regular pattern be everything developers hate: unreadable and hard to maintain. Having many of the characters common in both XML and JSON have special meaning doesn't help either. And even when bent on learning them, having multiple flavors depending on the operating system, language and even the particular tool you use makes it difficult. However, using small incremental steps to get the job done and occasionally look for references to less used features is usually super easy, barely an inconvenience. As for using them in your code, new language features and a few tricks can solve most problems one has with regular expressions.

 The Syntax Issue

The most common scenario for the use of regular expressions is wanting to search, search and replace or validate strings and you almost always start with a bunch of strings that you want to match. For example, you want to match both dates in the format 2020-01-21 and 21/01/2020. Immediately there are problems:

  • do you need to escape the slashes?
  • if you match the digits, are you going for two digit month and day segments or do you also accept something like 21/1/2020?
  • is there the possibility of having strings in your input that look like 321/01/20201, in which case you will still match 21/01/2020, but it's clearly not a date?
  • do you need to validate stuff like months being between 1-12 and days between 1-31? Or worse, validate stuff like 30 February?

But all of these questions, as valid as they are, can be boiled down to one: given my input, is my regular expression matching what I want it to match? And with that mindset, all you have to do is get a representative input and test your regular expression in a tester tool. There are many out there, free, online, all you have to do is open a web site and you are done. My favourite is RegexStorm, because it tests .NET style regex, but a simple Google search will find many and varied tools for reading and writing and testing regular expressions.

The syntax does present several problems that you will hit every time:

  • you cannot reuse parts of the pattern
    • in the example above, even if you have clearly three items that you look for - year, month, day - you will need to copy/paste the pattern for each variation you are looking for
  • checking the same part of the input string multiple times is not what regular expressions were created for and even those that support various methods to do that do it in a hackish way
    • example: find a any date in several formats, but not the ones that are in March or in 2017
    • look behind and look ahead expressions are usually used for scenarios like this, but they are not easy to use and reduce a lot of the efficiency of the algorithm
  • classic regular expression syntax doesn't support named groups, meaning you often need to find and maintain the correct index for the match
    • what index does one of the capturing groups have?
    • if you change something, how do other indexes change?
    • how do you count groups inside groups? Do they even count if they match nothing?
  • the "flags" indicating how the regular engine should interpret the pattern are different in every implementation
    • /x/g will look for all x characters in the string in Javascript
    • C# doesn't even need a global flag and the flags themselves, like CaseInsensitive, are .NET enums in code, not part of the regular pattern string
  • from the same class of issues as the two above (inconsistent implementation), many a tool uses a regular expression syntax that is particular to it
    • a glaring example is Visual Studio, which does not use a fully compatible .NET syntax

  The Escape Issue

The starting point for writing any regular expression has to be a regex escaped sample string that you want to match. Escaping means telling the regular expression engine that characters from your sample string that have meaning to it are just simple characters. Example 12.23.34.56, which is an IP address, if used exactly like that as a regular pattern, will match 12a23b34c56, because the dot is a catch all special character for regular expressions. The pattern working as expected would be 12\.23\.34\.56. Escaping brings several severe problems:

  • it makes the pattern less humanly readable
    • think of a phrase in which all white space has been replaced with \s+ to make it more robust (it\s+makes\s+the\s+pattern\s+less\s+humanly\s+readable)
  • you only escape with a backslash in every flavor of regular expressions, but the characters that are considered special are different depending on the specific implementation
  • many characters found in very widely used data formats like XML and JSON are special characters in regular expressions and the escaping character for regex is a special character in JSON and also string in many popular programming languages, forcing you to "double escape", which magnifies the problem
    • this is often an annoyance when you try to store regular patterns in config files

  Readability and Maintainability

Perhaps the biggest issue with regular expressions is that they are hard to maintain. Have you ever tried to understand what a complex regular expression does? The author of the code started with some input data and clear objectives of what they wanted to match, went to regular expression testers, found what worked, then dumped a big string in the code or configuration file. Now you have neither the input data or the things that they wanted matched. You have to decompile the regular pattern in your head and try to divine what it was trying to do. Even when you manage to do that, how often do developers redo the testing step so they verify the changes in a regular expressions do what was intended?

Combine this with the escape issue and the duplication of subpatterns issue and you get every developer's nightmare: a piece of code they can't understand and they are afraid to touch, one that is clearly breaking every tenet of their religion, like Don't Repeat Yourself or Keep It Simple Silly, but they can't change. It's like an itch they can't scratch. The usual solution for code like that is to unit test it, but regular expression unit tests are really really ugly:

  • they contain a lot of text variables, on many lines
  • they seem to test the functionality of the regular expression engine, not that of the regular expression pattern itself
  • usually regular expressions are used internally, they are not exposed outside a class, making it difficult to test by themselves

  Risk

Last, but not least, regular expressions can work poorly in some specific situations and people don't want to learn the very abstract computer science concepts behind regular expression engines in order to determine how to solve them.

  • typical example is lazy modifiers (.*? instead of .*) which tell the engine to not be greedy (get the least, not the most)
    • ex: for input "ineffective" the regular expression .*n will work a lot worse than .*?n, because it will first match the entire word, then see it doesn't end with n, then backtrack until it gets to "in" which it finally matches. The other syntax just stops immediately as it finds the n.
  • another typical example is people trying to find the HTML tag that has a an attribute and they do something like \<.*href=\"something\".*\/\> and what it matches is the entire HTML document up to a href attribute and the end of the last atomic tag in the document.
  • the golden hammer strikes again
    • people start with a simple regular expression in the proof of concept, they put it in a config file, then for the real life application they continuously tweak the configured pattern instead of trying to redesign the code, until they get to some horrible monstrosity
    • a regex in an online library that uses look aheads and look behinds solves the immediate problem you have, so you copy paste it in the code and forget about it. Then the production app has serious performance problems. 

  Solutions

  There are two major contexts in which to look for solutions. One is the search/replace situation in a tool, like a text editor. In this case you cannot play with code. The most you can hope for is that you will find a tester online that supports the exact syntax for regular expressions of the tool you are in. A social solution would be to throw shade on lazy developers that think only certain bits of regular expressions should be supported and implemented and then only in one particular flavor that they liked when they were children.

  The second provides more flexibility: you are writing the code and you want to use the power of regular expressions without sacrificing readability, testability and maintainability. Here are some possible solutions:

  • start with simple stuff and learn as you go
    • the overwhelming majority of the time you need only the very basic features of regular expressions, the rest you can look up when you need them
    • if the regular expression becomes too complex it is an indication that maybe it's not the best approach
  • store subpatterns in constants than you can then reuse using templated strings
    • ex: var yearPattern = @"(?<year>\d{4})"; var datePattern = $@"\b(?:{yearPattern}-(?<month>\d{2})-(?<day>\d{2})|(?<month>\d{2})\/(?<day>\d{2})\/{yearPattern})\b";
    • the example above only stores the year in another variable, but you can store the two different formats, the day, the month, etc
    • in the end your code might look more like the Backus-Naur (BNF) syntax, in which every separate component is described separately
  • use verbatim strings to make the patterns more readable by avoiding double escaping
    • in C# use @"\d+" not "\\d+"
    • in Javascript they are called template literals and use backticks instead of quotes, but they have the same mechanism for escaping characters as normal strings, so they are not a solution
  • use simple regular expressions or, if not, abstract their use
    • a good solution is using a fluent interface (check this discussion out) that allows the expressivity of human language for something that ends up being a regular expression
    • no, I am not advocating creating your own regular expression syntax... I just think someone probably already did it and you just have to find the right one for you :)
  • look for people who have solved the same problem with regular expression and you don't have to rewrite the wheel
  • always test your regular expressions on valid data and pay attention to the time it took to get the matches
  • double check any use of the string methods like IndexOf, StartsWith, Contains, even Substring. Could you use regular expressions?
    • note that you cannot really chain these methods. Replacing a regular expression like ^http[s]?:// with methods always involves several blocks of code and the introduction of cumbersome constants:
      if (text.StartsWith("http")) {
        // 4 works now, but when you change the string above, it stops working
        // you save "http" to a constant and then use .Length, you write yet another line of code
        text=text.Substring(4);
      } else {
        return false;
      }
      if (text.StartsWith("s")) {
        text=text.Substring(1);
      }
      return text.StartsWith("://");
      
      // this can be easily refactored to
      return text
               .IfStartsWith("http")
               .IfStartsWithOrIgnore("s")
               .IfStartsWith("://");
      // but you have to write your own helper methods
      // and you can't save the result in a config file​

  Conclusion

Regular expressions look daunting. Anyone not familiar with the subject will get scared by trying to read a regular expression. Yet most regular expression patterns in use are very simple. No one actually knows by heart the entire feature set of regular expressions: they don't need to. Language features and online tools can help tremendously to make regex readable, maintainable and even testable. Regular expressions shine for partial input validation and efficient string search and replace operations and can be easily stored in configuration files or data stores. When regular expressions become too complex and hard to write, it might be a sign you need to redesign your feature. Often you do not need to rewrite a regular expression, as many libraries with patterns to solve most common problems already exist.

  I was looking into the concept of partial sorting, something that would help in a scenario where you want the k smaller or bigger items from an array of n items and k is significantly smaller than n. Since I am tinkering with LInQer, my implementation for LINQ methods in Javascript, I wanted to tackle the OrderBy(...).Take(k) situation. Anyway, doing that I found out some interesting things.

  First, the default Javascript array .sort function has different implementations depending on browser and by that I mean different sort algorithms. Chrome uses insertion sort and Firefox uses merge sort. None of them is Quicksort, the one that would function best when the number of items is large, but that has worst case complexity O(n^2) when the array is already sorted (or filled with the same value).

I've implemented a custom function to do Quicksort and after about 30000 items it becomes faster than the default one.  For a million items the default sort was almost three times slower than the Quicksort implementation. To be fair, I only tested this on Chrome. I have suspicions that the merge sort implementation might be better.

  I was reporting in a previous version of this post that QuickSort, implemented in Javascript, was faster than the default .sort function, but it seems this was only an artifact of the unit tests I was using. Afterwards, I've found an optimized version of quicksort and it performed three times faster on ten million integers. I therefore conclude that the default sort implementation leaves a lot to be desired.

  Second, the .sort function is by default alphanumeric. Try it: [1,2,10].sort() will return [1,10,2]. In order to do it numerically you need to hack away at it with [1,2,10].sort((i1,i2)=>i1-i2). In order to sort the array based on the type of item, you need to do something like: [1,2,10].sort((i1,i2)=>i1>i2?1:(i1<i2?-1:0)).

  Javascript has two useful functions defined on the prototype of Object: toString and valueOf. They can also be overwritten, resulting in interesting hacks. For some reason, the default .sort function is calling toString on the objects in the array before sorting and not valueOf. Using the custom comparers functions above we force using valueOf. I can't test this on primitive types though (number, string, boolean) because for them valueOf cannot be overridden.

  And coming back to the partial sorting, you can't do that with the default implementation, but you can with Quicksort. Simply do not sort any partition that is above and below the indexes you need to get the items from. The increases in time are amazing!

  There is a difference between the browser implemented sort algorithms and QuickSort: they are stable. QuickSort does not guarantee the order of items with equal sort keys. Here is an example: [1,3,2,4,5,0].sort(i=>i%2) results in [2,4,0,1,3,5] (first even numbers, then odd, but in the same order as the original array). The QuickSort order depends on the choice of the pivot in the partition function, but assuming a clean down the middle index, the result is [4,2,0,5,1,3]. Note that in both cases the requirement has been met and the even numbers come first.