Slang.JS

It is indeed with great pride that I publish my latest learning project on Compiler Construction.

It was an attempt to port the interpreter (written in C#) to Javascript for the programming language named “SLANG” that was created by my mentor and friend Praseed Pai K.T (a.k.a Pai) as part of his teaching endeavours.

It has been a life changing experience and nothing describes the euphoria I get considering the fact I too have hand-coded an interpreter and am part of an amazing learning community that has created a programming language!

Experience it yourself : SlangJS v1.0

Advertisements

Javascript Currying – An Interpretation

As intrigued and obsessed [confession] I am with this Dynamic language, my foray into Functional programming via JS has definitely wired quite a bit of neuron networks which seem to mutate (should I say grow) as days progress. This interpretation of Currying in JS is one byproduct of such mutation.

I have been using the conventional approach advocated by Crockford in his book “JavaScript: The Good Parts” (see below)

Function.prototype.crockfordCurry = function () {
	"use strict";
	var slice = Array.prototype.slice,
		args = slice.apply(arguments),
		that = this;
	return function () {
		return that.apply(null, args.concat(slice.apply(arguments)));
	};
};

until an year back when I started re-looking at Currying as a first-class Functional programming feature and Haskell’s implementation (where almost always curried functions are used to achieve multiple arguments thus having all functions have exactly one argument) of it caught my attention and led me to think why would one need to curry as below and painstakingly compute (highlighted in code below),

function add(x) {
	"use strict";
	return function (y) {
		return x + y;
	};
}

function multiply(x) {
	"use strict";
	return function (y) {
		return x * y;
	};
}

//Creating the curried functions
var adder = add.crockfordCurry();
var multiplier = multiply.crockfordCurry();
//Finding the sum of 1,2 & 3 with the curried function
console.log(adder(adder(1)(2))(3));
//Finding the product of 1,2 & 3 with the curried function
console.log(multiplier(multiplier(1)(2))(3));

especially when computational values are more than 2 and there is little or no use of the resultant partially applied functions; thus automating this and giving user a direct option to compute the results with just a curried function that can accept any number of arguments a.k.a computational values in one shot (thereby living up to the true definition excerpt from Wikipedia below):


In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument (partial application). It was introduced by Moses Schönfinkel and later developed by Haskell Curry.


Function.prototype.haskellCurry = function () {
	"use strict";
	var slice = Array.prototype.slice,
		that = this;
	return function () {
		var	jsEval,
			jsApply,
			fn,
			args = slice.apply(arguments),
			result = args[0];
		jsEval = function () {
			args = slice.apply(arguments);
			fn = that.call(null, result);
			jsApply.apply(null, args);
		};
		jsApply = function () {
			args = slice.apply(arguments);
			result = fn.call(null, args[0]);
			if (args.length > 1) {
				jsEval.apply(null, args.slice(1));
			}
		};
		jsEval.apply(null, args.slice(1));
		return result;
	};
};

And you end up using the curried functions quite conveniently this way (see highlighted):

//Creating the curried functions
var adder2 = add.haskellCurry(),
	multiplier2 = multiply.haskellCurry();
//Finding the sum of 1, 2 & 3 with the curried function
console.log(adder2(1, 2, 3));
//Finding the product of 1, 2, 3, 4, 5 & 6 with the curried function
console.log(multiplier2(1, 2, 3, 4, 5, 6));

I have employed the Meta-Circular Evaluator principle here, along with Partial Application, Cumulative Recursion (with tail call optimization) and Closures to devise this currying operation in JavaScript.

And most surprising was that I found this approach resonate well with a paper (“Making a Fast Curry: Push/Enter vs Eval/Apply for higher-order languages” by none other than the great Simon Peyton Jones and Simon Marlow) published by Microsoft Research on March 17, 2004. I stumbled upon this actually quite recently which prompted me to let this piece of code thaw that was lying in cold a.k.a code storage for the past one year.

Hey! I now have a way to formally or rather [computer] scientifically explain my code.

Though the authors in their paper, drew a conclusion that the ‘Eval-Apply’ currying approach should be employed in compiled implementations, I was curious to find out how it would fare in an interpreted one. Well here’s my jslitmus benchmarking results that seem to corroborate their recommendation (Charts shows ops/second – higher is better!):

Currying Benchmarks

Anyone who likes to fiddle around and see if they can push the bars on the ‘Eval-Apply’ implementation are free to do that at my Github Repo.

Happy Coding!

The case of the “missing” VAR

A couple of days back a colleague (JS enthusiast) of mine asked me if it really matters to declare variables before use in JavaScript. He went on to say that he didn’t seem to find any side effects in doing so. Though I did tell him it has deep consequences (in terms of these rogue variables inheriting the global scope), I wanted him to appreciate this by experiencing it (and hence asked him to try this out) and in case he is still trying to figure it out, here’s a leading light for him and for many others who might still end up treading this path tomorrow…

If you end up in this situation (using a variable implicitly without declaration) in a global scope, this doesn’t have an impact (though not recommended) and I presume this is the situation this colleague of mine is in and hence didn’t notice any side effects whereas if you have a variable implicitly declared inside a function – that is, if it appears on the left side of an assignment expression but has not been declared with var – it is created as a global variableThis is because, in the process of looking up the variable in the scope chain, if the variable is not found all the way till the global scope, it is created at this point in global scope.

See the code below to understand the fun (I am sure this would have been a nightmare for many others):

function increment(x) {
	factor = x;//Implicit usage without declaration
	return function (y) {
		console.log(factor + y);
	};
}
var increment1 = increment(1),
	increment2 = increment(2),
	increment3 = increment(3);
increment1(1);//What result do you expect here?

You can see that in place of 2, you would be getting the result as 4 (for reasons already explained above). Now this is definitely something you wouldn’t want and you end up cursing the language for its unpredictability in addition to all the “undefined” errors it has to put up with (little knowing that it’s actually you who went rogue by not following some best practices and let some bad parts in the language get the best of its good parts).

The good thing is there is vaccine available that can help prevent you from not contracting this disease and those would be:

  1. JSLint/JSHint your code.
  2. The “use strict” Directive (starting ECMAScript version 5).

Happy Coding!

MarkUS

It’s a great moment for any developer to preview version 1.0 of his tool.

Herewith world I unveil MarkUS, the UI for a tool in its making. Well the ecstasy is in understanding how it is made and not why it is made.

I have employed a powerful visual programming tool named “Blockly” for crafting this self-guiding and smart UI. So true credits to the project owners of “blockly” who utilized their 20% time well in Google 🙂 To me it is the best visual DSL tools I have come across (not that I know many others).

Thanks to their documentation plus yet another smart API from Google (Realtime API), I have employed real-time collaboration for the tool as well.

Well I enjoyed every second spent on building MarkUS and “this” moment I call BLISS!

See MarkUS in Action…

YieldJS

YieldJS

As part of creating a JS library for relational data manipulation, I went on to create this library called YieldJS for creating Iterators, Generators and Continuation methods for Arrays. Continuation Passing Style (CPS) is utilized for chaining continuation methods along-side iterators and generators.

I had unveiled YieldJS partially as part of my presentation (JS: Good Parts In Action) for HTML5 developer conference. I wanted to add Generators to the library and hence waited till now to publish it officially.

I would consider this Beta (pending performance profiling and exception handling). I would love feedback (from any interested developer) on this especially in par with usage of UnderscoreJS and other prevalent libraries in use today,

I plan to add my share of benchmarks with more usage scenario documentation.

Change Calculator

A dig at one of those code puzzlers from dzone. Thanks to Abhi (a buddy) for sharing it with me and instilling the urge for this adventure. I have utilized a subset generation algorithm (highlighted in code) from my mentor and friend (Pai) here.

Change Calculator 

Say you are given an infinite number of coins in the following denominations:

  • 25 cents
  • 10 cents
  • 5 cents
  • 1 cent

Write a method that would take an integer parameter named change. Work out all the permutations that can return that amount given the coins that you have available. For example, calculateChange(5) would return

  1. 1 x 5c
  2. 5 x 1c
var calculateChange = function (denominations, amount) {
	'use strict';
	var changeSets = 0,
		printChangeSet = function (denominationSet) {
			var matchFactors = [],
				findCombinationSet = function (denominationIndex, cumilativeSum) {
					var transientSum = 0,
						i = 1,
						denomination = denominationSet[denominationIndex],
						factorCount = denominationSet.length;
					while (transientSum <= amount) {
						//Pretty Printing
						matchFactors[denominationIndex] = i.toString() + " x " + denomination.toString() + "c";
						transientSum = cumilativeSum + (denomination * i);
						if ((denominationIndex + 1) === factorCount) {
							if (transientSum === amount) {
								changeSets += 1;
								console.log(changeSets + ". " + matchFactors);
							}
						} else {
							findCombinationSet(denominationIndex + 1, transientSum);
						}
						i += 1;
					}
				};
			findCombinationSet(0, 0);
		},
		// This function computes the possible denomination sets
		generateChangeSets = function () {
			var bitcount = denominations.length,
				mask = Math.pow(2, bitcount),
				i = 1,
				j = 0,
				k = 1,
				denominationSet = null,
				denominationSum = 0;
			while (i < mask) {
				j = 0;
				denominationSet = [];
				denominationSum = 0;
				while (j < bitcount) {
					if ((i & (k << j)) > 0) {
						denominationSet.push(denominations[j]);
						denominationSum += denominations[j];
					}
					j += 1;
				}
				if (denominationSum <= amount) {
					printChangeSet(denominationSet);
				}
				i += 1;
			}
		};
	generateChangeSets();
};
/*jslint indent: 4, maxerr: 1, passfail: false, browser: false, devel: true, windows: false, rhino: false, undef: true, node: true, bitwise: true */

To test this, simply execute:

calculateChange([1, 5, 10, 25], 5);

The decomposition technique utilized here (that of finding all the denomination sets first and then searching for the combinations that would yield the amount) doesn’t hold good against this classic NP-Hard problem where despite parallelization, you cannot cheat death owing to stack overflow for the larger sets, lower denominations and higher amounts.

JSpell

I was able to implement a JavaScript based spelling corrector based on an article by Peter Norvig (How to Write a Spelling Corrector) and wanted to share this with any interested reader. I always wanted to do this the moment I was shared this link by my mentor and friend (almost 2-3 years now). I always had it in my wish-list and now it’s an accomplishment (a good note to end the year I guess). It is so special and unique in regards to employing Bayes theorem in devising the actual algorithm for the spelling corrector. The code has been optimized to a great extent yet preserved adequate styling for brevity. Future work as suggested by Norvig (in his original article) hasn’t been accommodated though. I have enjoyed using currying extensively especially for the precedence-based filtering part in the algorithm. The Spelling Corrector is an object with the following 2 interfaces:

  1. train – use this function to provide the text for the training model.
  2. correct – use this function to provide the words (or a list) for corrections.

Please read the article (link provided above) for all the details. Additional information (especially training text information) could be found here . I have also documented the code for readability.

var NorvigSpellChecker = function () {
	var that = {},
		filter = /([a-z]+)/g,
		alphabets = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'],
		NWORDS = {};//Training Model
	
	var train = function(trainingText) {
		var features = trainingText.match(filter);
		for(var f in features) {
			var feature = features[f];
			if (NWORDS.hasOwnProperty(feature)) {
				NWORDS[feature] += 1;
			}
			else {
				NWORDS[feature] = 1;
			}
		}
	};
	
	var edits1 = function (words) {
		var edits1Set = [];
		for(var w = 0; w < words.length; w++) {
			var word = words[w];
			for (var i = 0; i <= word.length; i++) {
				//splits (a & b)
				var a = word.slice(0,i),
					b = word.slice(i),
					c = b.slice(1),
					d = b.slice(2);
				if (b != '') {
					//deletes
					edits1Set.push(a + c);
					//transposes
					if (b.length > 1) {
						edits1Set.push(a + b.charAt(1) + b.charAt(0) + d);
					}
					//replaces & inserts
					for (var j = 0; j < alphabets.length; j++) {
						edits1Set.push(a + alphabets[j] + c);//replaces
						edits1Set.push(a + alphabets[j] + b);//inserts
					}
				}
				else {
					//inserts (remaining set for b == '')
					for (var j = 0; j < alphabets.length; j++) {
						edits1Set.push(a + alphabets[j] + b);
					}
				}
			}
		}
		return edits1Set;
	};
	
	var edits2 = function (words) {
		return edits1(edits1(words));
	};

	Object.prototype.isEmpty = function () {
		var that = this;
		for(var prop in that) {
			if(that.hasOwnProperty(prop))
				return false;
		}
		return true;
	};

	Function.prototype.curry = function () {
		var slice = Array.prototype.slice,
			args = slice.apply(arguments),
			that = this;
		return function () {
			return that.apply(null, args.concat(slice.apply(arguments)));
		};
	};
	
	var known = function () {
		var knownSet = {};
		for (var i = 0; knownSet.isEmpty() && i < arguments.length; i++) {
			var words = arguments[i];
			for (var j = 0; j < words.length; j++) {
				var word = words[j];
				if (!knownSet.hasOwnProperty(word) && NWORDS.hasOwnProperty(word)) {
					knownSet[word] = NWORDS[word];
				}
			}
		}
		return knownSet;
	};
	
	var max = function(candidates) {
		var maxCandidateKey = null,
			maxCandidateVal = 0,
			currentCandidateVal;
		for (var candidate in candidates) {
			currentCandidateVal = candidates[candidate];
			if (candidates.hasOwnProperty(candidate) && currentCandidateVal > maxCandidateVal) {
				maxCandidateKey = candidate;
				maxCandidateVal = currentCandidateVal;
			}
		}
		return maxCandidateKey;
	};

	var correct = function () {
		var corrections = {};
		for (var i = 0; i < arguments.length; i++) {
			var word = arguments[i];
			var candidates = known.curry()([word],edits1([word]),edits2([word]));
			corrections[word] = candidates.isEmpty() ? word : max(candidates);
		}
		return corrections;
	};
	
	that.train = train;
	that.correct = correct.curry();
	
	return that;
};
I have also hosted the source code (free for use) and sample test code. Please provide the training text as a string in the sample test code for trying JSpell. Happy New Year!