Trouble with JavaScript array

JavaScript arrays are “ancient” objects. They were one of the first data types added to the language, unlike Map, Proxy, WeakMap etc.

An object has two types of properties – public slots and internal slots. E.g. Map() has internal property called [[MapData]] where it keeps all it’s data. Array has no internal slots.

However, array does “process” some properties… like index. If the index is >=0, it considers them to be part of the “array”. However, if we use non positive integer values, array adds the property but does not consider them in certain scenarios, e.g. ‘array.length’ or ‘for of’.

Look at some array quirks

// Normal usage
console.log("const normalArray = [11, 23, 35];");
const normalArray = [11, 23, 35];
console.log(normalArray);
/* [ 11, 23, 35 ] */
// Adding by index
console.log("normalArray[3] = 48;");
normalArray[3] = 48;
console.log(normalArray);
/* [ 11, 23, 35, 48 ] */
// Non positive index get added as keys
console.log("normalArray[-1]=5");
normalArray[1] = 5
console.log(normalArray);
/* [ 11, 23, 35, 48, '-1': 5 ] */
// Even string
normalArray['foo'] = 'bar';
console.log("normalArray['foo'] = 'bar';")
console.log(normalArray);
/* [ 11, 23, 35, 48, '-1': 5, foo: 'bar' ] */
// for of gives only positive index
console.log("for (let index of normalArray)");
for (let element of normalArray)
console.log(element);
/*
11
23
35
48
*/
// for in gives ALL key/value pairs
console.log("for (let index in normalArray)");
for (let index in normalArray)
console.log(`${index}: ${normalArray[index]}`);
/*
0: 11
1: 23
2: 35
3: 48
-1: 5
foo: bar
*/
// It counts only positive index
console.log("normalArray.length");
console.log(normalArray.length);
/* 4 */
Problem with arrays

Fine.. I will be careful while using arrays. Great! But what if you are writing a module/lib and you have to pass you array to the caller? What if she/he adds non-positive index?

Thankfully, we have a new type of object in JavaScript – Proxy. It does what its name says – Proxy for other objects. A Proxy can “intercept” access to another object

Let’s build a “Pure” Array

First, let’s understand Proxy

// Simple object
let person = {
id: 0,
name: "default",
}
// There is no validation if object is used directly
person.id = "Eich"; // We would like it to be positive integer
person.name = 3.14; // Name should ideally be non blank string
console.log(person);
// Let's setup Proxy handler with validations
const handler = {
set(object, property, value, receiver) {
// id should be positive integer
if (property == "id") {
if (typeof value != 'number' || value < 0)
throw "id should be a positive number";
}
// name should be a non blank string
if (property == "name") {
if (typeof value != 'string' || value.trim() == "")
throw "name should be a non blank string";
}
// Passed all validations, so assign to real object
return Reflect.set(object, property, value, receiver);
}
}
// Use a Proxy to person object
const PersonProxy = new Proxy(person, handler);
// These should give errors
PersonProxy.id = "Brendan";
PersonProxy.name = 1;
console.log(PersonProxy);
view raw SimpleProxy.js hosted with ❤ by GitHub
Simple Proxy

As we can see, Proxy can “trap” any access to the object and change the behaviour. In the case above, we are able to validate that id should be integer and name should be a string. We can build a similar Proxy for array and make sure that the index is only positive integers.

Pure Array

// Array proxy
const PureArray = (args) =>
new Proxy([args], // Create internal array
// Handler with traps
{
// Intercept assignment to array using index
set(target, property, value, receiver) {
// Allow built in properties like length
if (Reflect.has(target, property))
return Reflect.get(target, property, receiver);
// Check if property is positive integer
const index = Number.parseInt(property);
if (Number.isNaN(index) || index < 0)
throw new Error("Index must be >= 0");
// Otherwise call the internal array
return Reflect.set(target, property, value, receiver);
},
// Intercept access to the array via index
get(target, property, receiver) {
// Check if its one of the built in properties
if (Reflect.has(target, property))
return Reflect.get(target, property, receiver);
// Check if property is positive integer
const index = Number.parseInt(property);
if (Number.isNaN(index) || index < 0)
throw new Error("Index must be >= 0");
// Otherwise call the internal array
return Reflect.get(target, property, receiver);
}
}
);
// let's create our "Pure" array
const myArray = PureArray(1, 2, 3);
console.log(myArray);
// Normal operations work
myArray[3] = 4;
console.log(myArray);
console.log(myArray.slice(2, 3));
console.log(myArray.length);
// These don't work anymore
myArray[1] = 5;
console.log(myArray[3]);
view raw PureArray.js hosted with ❤ by GitHub
Pure Array

There we have it! We have used a Proxy object to intercept access to an array and allow ONLY non-positive index. For others, it will appear to be an Array and they would see no difference. All array methods will continue to work but we will ensure that only positive indexes are allows.

Build Memoize in JavaScript – Part IV

In the previous posts we have build Memoize using higher order functions, Proxy object and controlled the runaway cache by implementing MRU inside our Proxy objects. However, it would make more sense to have a Most Frequently Used (MFU) cache, which unlike MRU does not go by recency effect but with frequency of usage.

The basic problem remains with Map() as a cache that it does not have insertion order. So we could use Array List, forgoing our O(1) lookup. For sake of challenge and academic satisfaction, let’s write an MFU caches using a hybrid of Map (O(1) look up ) and custom class (for storing frequency).

But first a dirty trick to enable/disable debug output within out code

// Simple debug tricks
const nop = () => { };
let debug = nop; // Disable debug output
debug = console.log; // Enable debug output
view raw Debug.js hosted with ❤ by GitHub

Now Let’s write an MFUMap which extends a Map, where we will incorporate a List with key and frequency and Recency. We create a user defined class to hold them.

// Class to store frequency and recency of the key
class Frequency {
// Private fields
#frequency; // Number of times the key has been accessed
#recency; // Last timestamp of access
constructor(frequency = 1, recency = new Date()) {
this.#frequency = frequency;
this.#recency = recency.getTime() + recency.getMilliseconds();
}
// Update frequency and recency
update = () => {
this.#frequency++;
let now = new Date();
this.#recency = now.getTime() + now.getMilliseconds();
}
get frequency() { return this.#frequency; }
get recency() { return this.#recency; }
toString = () => {
return `{ frequency: ${this.#frequency}, recency: ${this.#recency} }`;
}
}
view raw Frequency.js hosted with ❤ by GitHub

Frequency class holds the frequency (number of times the key has been accessed) and recency (the last time the key was accessed). Recency is tie breaker in case we want to drop entries which has same frequency.

Now to the next… MFUMap which will extend a Map. Rather that composing a Map, we will extend it, so that we don’t have to write wrapper/forwarder functions for a Map. By extending it, we will simply override the ones we want to modify and leave the rest to go to base class Map.

Here is our skeletal MFUMap class

// We extend the map instead of composing it
// So that non-overridden functions are passed to the base
class MFUMap extends Map {
// Private properties
#frequencyMap = new Map();
#maxSize = 10;
constructor(size = 10) {
super();
this.#maxSize = size;
debug(`Initialized map with size=${size}`);
}
// Check if our map size is going beyond maxSize
#resizeMap = () => {
// Drop entries from the map
}
#updateFrequency = key => {
// Update frequency of the key here
}
// Override the get and set function of Map
set(key, value) {
let result = super.set(key, value);
// Update the frequency of the key
this.#updateFrequency(key);
return result;
}
get(key) {
let exists = super.get(key);
// Don't update non existing gets
if (exists)
this.#updateFrequency(key);
return exists;
}
}
view raw SkeletonMFU.js hosted with ❤ by GitHub

We are overriding get and set functions of Map, where we will update the frequency/recency of key usage. This will help us deciding which keys to drop when we go over maxSize.

Now let’s start filling in our MFUMap with details.
First, the UpdateFrequency code, which will be called any time the key is accessed (set/get), so that we can bump up its frequency and also set the last accessed time (tie breaker for same frequency keys).

// if key was accessed, increment its frequency
#updateFrequency = key => {
let frequencyObject = this.#frequencyMap.get(key);
// if existing key, update the frequency
if (frequencyObject)
frequencyObject.update();
else
this.#frequencyMap.set(key, frequencyObject = new Frequency());
debug(`Updated { ${key} => ${frequencyObject} }`);
// Maybe we went over the maxSize, truncate the Map
this.#resizeMap();
}

With that done, we now need to trim our MFUMap whenever it goes over maxSize. Whenever we update frequency, we call private #resize method to check if we need to trim it.

#resizeMap determines the candidate key for removal. It does that by finding out the lowest frequency key and if there are more than 1 with same frequency, it uses recency (timestamp) to elect the candidate (kind of MFU + MRU).

// Check and trim our cache size
#resizeMap = () => {
if (this.size <= this.#maxSize)
return false;
debug(`Resizing map: ${this.size} > ${this.#maxSize}`);
// Elements required to determine candidates
let minKey;
let minFrequency = Number.MAX_VALUE;
let minTime;
// Find the lowest frequency key
for (let [key, value] of this.#frequencyMap) {
let entryFrequency = value.frequency;
let entryTime = value.recency;
// Find the lowest frequency key
if (entryFrequency < minFrequency) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
} else {
// If there are multiple keys with same frequency
// Choose the least recency key
if (entryFrequency == minFrequency) {
if (entryTime < minTime) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
}
}
}
}
debug(`Deleting { ${minKey} => { frequency: ${minFrequency}, recency: ${minTime} }`);
this.delete(minKey);
this.#frequencyMap.delete(minkey);
return true;
}
view raw ResizeMap.js hosted with ❤ by GitHub

Now that we are set, all we need to do is override the Map’s get/set to call our #updateFrequency and let it #resizeMap if necessary

set(key, value) {
let result = super.set(key, value);
// Update the frequency of the key
this.#updateFrequency(key);
return result;
}
get(key) {
let exists = super.get(key);
// Don't update non existing gets
if (exists)
this.#updateFrequency(key);
return exists;
}
}
view raw getset.js hosted with ❤ by GitHub

There! We are set. We have implemented a Most Frequency Used (MFU) cache with Most Recently Used (MRU) for tie-breaker and we can limit the cache size of for Memoize.

Here is the complete list of MFUMap along with Frequency class

/**
* Some debug helpers
*/
const nop = () => { };
let debug = nop; // Disable debug output
debug = console.log; // Enable debug output
// Class to store frequency and recency of the key
class Frequency {
// Private fields
#frequency; // Number of times the key has been accessed
#recency; // Last timestamp of access
constructor(frequency = 1, recency = new Date()) {
this.#frequency = frequency;
this.#recency = recency.getTime() + recency.getMilliseconds();
}
// Update frequency and recency
update = () => {
this.#frequency++;
let now = new Date();
this.#recency = now.getTime() + now.getMilliseconds();
}
get frequency() { return this.#frequency; }
get recency() { return this.#recency; }
toString = () => {
return `{ frequency: ${this.#frequency}, recency: ${this.#recency} }`;
}
}
/**
* MFU class
*/
// We extend the map instead of composing it
// So that non-overridden functions are passed to the base
class MFUMap extends Map {
#frequencyMap = new Map();
#maxSize = 10;
constructor(size = 10) {
super();
this.#maxSize = size;
debug(`Initialized map with size=${size}`);
}
// Check and trim our cache size
#resizeMap = () => {
if (this.size <= this.#maxSize)
return false;
debug(`Resizing map: ${this.size} > ${this.#maxSize}`);
// Elements required to determine candidates
let minKey;
let minFrequency = Number.MAX_VALUE;
let minTime;
// Find the lowest frequency key
for (let [key, value] of this.#frequencyMap) {
let entryFrequency = value.frequency;
let entryTime = value.recency;
// Find the lowest frequency key
if (entryFrequency < minFrequency) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
} else {
// If there are multiple keys with same frequency
// Choose the least recency key
if (entryFrequency == minFrequency) {
if (entryTime < minTime) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
}
}
}
}
debug(`Deleting { ${minKey} => { frequency: ${minFrequency}, recency: ${minTime} }`);
this.delete(minKey);
return true;
}
// if key was accessed, increment its frequency
#updateFrequency = key => {
let frequencyObject = this.#frequencyMap.get(key);
// if existing key, update the frequency
if (frequencyObject)
frequencyObject.update();
else
this.#frequencyMap.set(key, frequencyObject = new Frequency());
debug(`Updated { ${key} => ${frequencyObject} }`);
// Maybe we went over the maxSize, truncate the Map
this.#resizeMap();
}
set(key, value) {
let result = super.set(key, value);
// Update the frequency of the key
this.#updateFrequency(key);
return result;
}
get(key) {
let exists = super.get(key);
// Don't update non existing gets
if (exists)
this.#updateFrequency(key);
return exists;
}
}
view raw MFUMap.js hosted with ❤ by GitHub

Here is the isPrime function we want to Memoize with MFUMap

// Check if given number is prime
const isPrime = number => {
if (number < 2) return false;
// Divide number by all numbers from 2 to sqrt(number)
// If divisible, then its not a prime
let div;
for (div = 2; div <= Math.sqrt(number); div++)
if (number % div == 0)
return false;
return true;
}
view raw isPrime.js hosted with ❤ by GitHub

Let Memoize with MFUMap

// Memoize is a Proxy to the actual function
const memoize = (fn, mfu = 10) => new Proxy(fn,
// Handler with traps
{
cache: new MFUMap(mfu),
max: mfu, // Our cache limit
// Our "magic" property
get(object, property, receiver) {
if (property == "cache")
return this.cache;
return Reflect.get(object, property, receiver);
},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
let result = this.cache.get(args.toString());
if (result)
return result;
result = Reflect.apply(target, thisArg, args);
this.cache.set(args.toString(), result);
return result;
}
}
);
view raw MemoizeMFU.js hosted with ❤ by GitHub

We are all set to roll… let’s test it

We will Memoize isPrime with MFU size of 3 and then repeated called the smartPrime to change the frequency. Further when we call isPrime, instead of MRU, it will select keys which are most frequently used.

let number = 10;
let smartPrime = memoize(isPrime, mfu = 3);
smartPrime(1);
smartPrime(2);
smartPrime(2); // MFU
smartPrime(1); // MFU
smartPrime(3); // MRU
smartPrime(4);
console.log(smartPrime.cache);
/* Output
Initialized map with size=3
Updated { 1 => { frequency: 1, recency: 1596064558140 } }
Updated { 2 => { frequency: 1, recency: 1596064558148 } }
Updated { 3 => { frequency: 1, recency: 1596064558148 } }
Updated { 2 => { frequency: 2, recency: 1596064558150 } }
Updated { 1 => { frequency: 2, recency: 1596064558150 } }
Updated { 4 => { frequency: 1, recency: 1596064558150 } }
Resizing map: 4 > 3
Deleting { 3 => { frequency: 1, recency: 1596064558148 }
MFUMap(3) [Map] { '1' => false, '2' => true, '4' => false }
*/
view raw MFUOutput.js hosted with ❤ by GitHub

Who got dropped first? 3!
Why? Because 1 and 2 were more frequently used, even though 3 was most recently used. Makes sense?

Here is the entire code which implements

  1. debug “macros”
  2. Frequency class
  3. MFUMap
  4. isPrime function
  5. memoize Proxy
  6. Test code
/**
* Some debug helpers
*/
const nop = () => { };
let debug = nop; // Disable debug output
debug = console.log; // Enable debug output
// Class to store frequency and recency of the key
class Frequency {
// Private fields
#frequency; // Number of times the key has been accessed
#recency; // Last timestamp of access
constructor(frequency = 1, recency = new Date()) {
this.#frequency = frequency;
this.#recency = recency.getTime() + recency.getMilliseconds();
}
// Update frequency and recency
update = () => {
this.#frequency++;
let now = new Date();
this.#recency = now.getTime() + now.getMilliseconds();
}
get frequency() { return this.#frequency; }
get recency() { return this.#recency; }
toString = () => {
return `{ frequency: ${this.#frequency}, recency: ${this.#recency} }`;
}
}
/**
* MFU class
*/
// We extend the map instead of composing it
// So that non-overridden functions are passed to the base
class MFUMap extends Map {
#frequencyMap = new Map();
#maxSize = 10;
constructor(size = 10) {
super();
this.#maxSize = size;
debug(`Initialized map with size=${size}`);
}
// Check and trim our cache size
#resizeMap = () => {
if (this.size <= this.#maxSize)
return false;
debug(`Resizing map: ${this.size} > ${this.#maxSize}`);
// Elements required to determine candidates
let minKey;
let minFrequency = Number.MAX_VALUE;
let minTime;
// Find the lowest frequency key
for (let [key, value] of this.#frequencyMap) {
let entryFrequency = value.frequency;
let entryTime = value.recency;
// Find the lowest frequency key
if (entryFrequency < minFrequency) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
} else {
// If there are multiple keys with same frequency
// Choose the least recency key
if (entryFrequency == minFrequency) {
if (entryTime < minTime) {
minFrequency = entryFrequency;
minKey = key;
minTime = entryTime;
}
}
}
}
debug(`Deleting { ${minKey} => { frequency: ${minFrequency}, recency: ${minTime} }`);
this.delete(minKey);
return true;
}
// if key was accessed, increment its frequency
#updateFrequency = key => {
let frequencyObject = this.#frequencyMap.get(key);
// if existing key, update the frequency
if (frequencyObject)
frequencyObject.update();
else
this.#frequencyMap.set(key, frequencyObject = new Frequency());
debug(`Updated { ${key} => ${frequencyObject} }`);
// Maybe we went over the maxSize, truncate the Map
this.#resizeMap();
}
set(key, value) {
let result = super.set(key, value);
// Update the frequency of the key
this.#updateFrequency(key);
return result;
}
get(key) {
let exists = super.get(key);
// Don't update non existing gets
if (exists)
this.#updateFrequency(key);
return exists;
}
}
// Check if given number is prime
const isPrime = number => {
if (number < 2) return false;
// Divide number by all numbers from 2 to sqrt(number)
// If divisible, then its not a prime
let div;
for (div = 2; div <= Math.sqrt(number); div++)
if (number % div == 0)
return false;
return true;
}
// Memoize is a Proxy to the actual function
const memoize = (fn, mfu = 10) => new Proxy(fn,
// Handler with traps
{
cache: new MFUMap(mfu),
max: mfu, // Our cache limit
// Our "magic" property
get(object, property, receiver) {
if (property == "cache")
return this.cache;
return Reflect.get(object, property, receiver);
},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
let result = this.cache.get(args.toString());
if (result)
return result;
result = Reflect.apply(target, thisArg, args);
this.cache.set(args.toString(), result);
return result;
}
}
);
let number = 10;
let smartPrime = memoize(isPrime, mfu = 3);
smartPrime(1);
smartPrime(2);
smartPrime(2);
smartPrime(1);
smartPrime(3);
smartPrime(4);
console.log(smartPrime.cache);
view raw MFUMemoize.js hosted with ❤ by GitHub

Feels good?

Memoize Series

  1. Build Memoize in JavaScript – Part I (Higher order function)
  2. Build Memoize in JavaScript – Part II (Proxy Object)
  3. Build Memoize in JavaScript – Part III (MRU cache)
  4. Build Memoize in JavaScript – Part IV (MFU cache)

Build Memoize in JavaScript – Part III

In the previous two posts we have built memoize feature using two different flavours – Higher order function and Proxy. However, there is one concern in both implementations – runaway caching.

// Check if given number is prime
const isPrime = number => {
if (number < 2) return false;
// Divide number by all numbers from 2 to sqrt(number)
// If divisible, then its not a prime
let div;
for (div = 2; div <= Math.sqrt(number); div++)
if (number % div == 0)
return false;
return true;
}
// Memoize is a Proxy to the actual function
const memoize = fn => new Proxy(fn,
// Handler with traps
{
// We store previous results here
cache: {},
get(object, property, receiver) {
if (property == "length")
return Object.keys(this.cache).length;
},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
if (!(args in this.cache))
this.cache[args] = Reflect.apply(target, thisArg, args);
return this.cache[args];
}
}
);
// This is a known prime
let smartPrime = memoize(isPrime);
let max = 1000000;
let primeCount = 0;
for (let number = 2; number <= max; number++)
if (smartPrime(number)) {
primeCount++;
}
console.log(`Number of primes between 0 and ${max}: ${primeCount}`);
console.log(`Cache memory: ${smartPrime.length}`);
/* Ouput
Number of primes between 0 and 1000000: 78498
Cache memory: 999999
*/
view raw RunAwayCache.js hosted with ❤ by GitHub

OOPS! Every single value we test for prime becomes permanently cached.

Can we limit the number of entries in the cache? Well, we could stop inserting values after a certain number of entries but that would not be very useful as we would catch the least recently used (LRU) results. What we would probably want to do it use most recently used (MRU) results.

Earlier we used object for cache – cache: {} which happens to be a Map internally, making it easier for us to lookup keys in O(1) time. However, we cannot know the order in which keys were inserted into the map (cache object, in our case), hence, we will need to use another data structure which will help us with that – Linked List. Yep, JavaScript Arrays are like Linked List (push, pop, shift, unshift).

The next implementation of Memoize uses a List for MRU in form of
[ {args:2, result:true}, {args:3, result:true}, {args:4, result:false} ]
and so on. We will lose our O(1) time for lookup but at least we will get most recently used cache.

// Check if given number is prime
const isPrime = number => {
if (number < 2) return false;
// Divide number by all numbers from 2 to sqrt(number)
// If divisible, then its not a prime
let div;
for (div = 2; div <= Math.sqrt(number); div++)
if (number % div == 0)
return false;
return true;
}
// Memoize is a Proxy to the actual function
const memoize = (fn, mru=10) => new Proxy(fn,
// Handler with traps
{
// Instead of object, let's use a list which contains
// [ {args:2, result:true}, {args:3, result:true}, {args:4, result:false} ]
cache: [],
max: mru, // Our cache limit
// Our "magic" property
get(object, property, receiver) {
if (property == "cache")
return this.cache;
return Reflect.get(object, property, receiver);
},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
// Scan the list to see if we have args cached
let exists = this.cache.find(element => {
element.args == args.toString();
});
// If exists, return the result
if (exists) {
result = exists.result;
} else {
// New result, store it at the end
result = Reflect.apply(target, thisArg, args);
this.cache.push({ args: args.toString(), result: result });
}
// Have we exceeded the limit? Drop the first element
if (this.cache.length > this.max)
this.cache.shift();
return result;
}
}
);
// Create the proxy and go thru max numbers to test for isPrime
let smartPrime = memoize(isPrime);
let max = 1000000;
let primeCount = 0;
for (let number = 2; number <= max; number++)
if (smartPrime(number)) {
primeCount++;
}
console.log(`Number of primes between 0 and ${max}: ${primeCount}`);
// Let's test 2 again
console.log("2 is prime", smartPrime(2));
console.log(`Cache size: ${smartPrime.cache.length}`);
console.log('Cache:', smartPrime.cache);
/* Output
Number of primes between 0 and 1000000: 78498
2 is prime true
Cache size: 10
Cache: [
{ args: '999992', result: false },
{ args: '999993', result: false },
{ args: '999994', result: false },
{ args: '999995', result: false },
{ args: '999996', result: false },
{ args: '999997', result: false },
{ args: '999998', result: false },
{ args: '999999', result: false },
{ args: '1000000', result: false },
{ args: '2', result: true }
]
*/
view raw MRUAsList.js hosted with ❤ by GitHub

This is cool! we not only have a Memoize Proxy, which can wrap any function to cache its results but we can also control the cache size so that we have most recently used list and conserve on memory size.

Sometimes, it makes sense to have MFU (Most Frequently Used) rather than MRU (Most Recently Used) cache. Just because we used 2 towards the end, it is kept in the list, whereas we may have tested 11 for prime 10 times, but because it was towards the beginning of the usage, it gets shifted out.

How about building an MFU Cache for our Memoize? Perhaps, next post?

Memoize Series

  1. Build Memoize in JavaScript – Part I (Higher order function)
  2. Build Memoize in JavaScript – Part II (Proxy Object)
  3. Build Memoize in JavaScript – Part III (MRU cache)
  4. Build Memoize in JavaScript – Part IV (MFU cache)

Build Memoize in JavaScript – Part II

In the previous post we built a memoize function, which caches the result of any pure function, thereby speeding up the execution when the result is already cachced.

Let’s try and improve our Memoize function.
There is an excellent object called Proxy, which wraps and JavaScript object and allows us to transparently intercept all its access.

First.. the Proxy object
Proxy is a wrapper to other objects and can intercept/trap access to object. This enables proxy to do things like validations, result manipulation and even inserting new “function”, which don’t exist in the object.

// Simple object
let person = {
id: 0,
name: "default",
}
// There is no validation if object is used directly
person.id = "Eich"; // We would like it to be positive integer
person.name = 3.14; // Name should ideally be non blank string
console.log(person);
// Let's setup Proxy handler with validations
const handler = {
set(object, property, value, receiver) {
// id should be positive integer
if (property == "id") {
if (typeof value != 'number' || value < 0)
throw "id should be a positive number";
}
// name should be a non blank string
if (property == "name") {
if (typeof value != 'string' || value.trim() == "")
throw "name should be a non blank string";
}
// Passed all validations, so assign to real object
return Reflect.set(object, property, value, receiver);
}
}
// Use a Proxy to person object
const PersonProxy = new Proxy(person, handler);
// These should give errors
PersonProxy.id = "Brendan";
PersonProxy.name = 1;
console.log(PersonProxy);
view raw SimpleProxy.js hosted with ❤ by GitHub


There! We are intercepting access to the object using a Proxy. While in this case we are trapping property setter, we can intercept other things as well. For example, call to the target function.

If we can intercept function call (e.g. isPrime), we can intercept the return value and cache it in the proxy, so next time if we find the same args, we don’t even have to call the target function and the proxy itself can return the cached value.

So, let’s rewrite our Memoize function as a Proxy

// Check if given number is prime
const isPrime = number => {
if (number < 2) return false;
// Divide number by all numbers from 2 to sqrt(number)
// If divisible, then its not a prime
let div;
for (div = 2; div <= Math.sqrt(number); div++)
if (number % div == 0) {
console.log(`Looped ${div} times`);
return false;
}
console.log(`Looped ${div} times`);
return true;
}
// Memoize is a Proxy to the actual function
const memoize = fn => new Proxy(fn,
// Handler with traps
{
// We store previous results here
cache: {},
// Intercept call to the wrapped function
apply(target, thisArg, args) {
// Do we have result in Proxy itself?
if (!(args in this.cache))
this.cache[args] = Reflect.apply(target, thisArg, args);
return this.cache[args];
}
}
);
// This is a known prime
let number = 1299827;
const smartPrime = memoize(isPrime);
console.log(`${number} is prime: ${smartPrime(number)}`);
console.log(`${number} is prime: ${smartPrime(number)}`);
view raw MemoizeProxy.js hosted with ❤ by GitHub

There we have it! We are caching the result in the Proxy object itself and returning without calling the target function. Apart from function call, we can also intercept other access like property getter/setter or deletion. However, we don’t need that in this case.

However, both our Memoize implementation have one problem… Infinite caching for infinite time. What if the user checks one millions primes? What will happen to our cache? Yep, it would contain one million entries, which may or may not be used again.

We need to build smart cache along with our Memoize feature. Maybe next post?

Memoize Series

  1. Build Memoize in JavaScript – Part I (Higher order function)
  2. Build Memoize in JavaScript – Part II (Proxy Object)
  3. Build Memoize in JavaScript – Part III (MRU cache)
  4. Build Memoize in JavaScript – Part IV (MFU cache)

Build Memoize in JavaScript – Part I

Memoize or Memorize? Memoize!

From Wikipedia “In computing memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.”

So basically, memoization is caching results of function calls. Obviously, this should be done ONLY for those functions which return the same result for same input.

It’s actually pretty easy to implement this. Let’s take a look at how we can implement this in a compute intensive function like calculating primes.

So let’s first write a simple prime program

// Check if given number is prime
const isPrime = number => {
// Divide number by all numbers from 2 to sqrt(number)
// If divisible, then its not a prime
let div;
for (div = 2; div < Math.sqrt(number); div++)
if (number % div == 0) {
console.log(`Looped ${div} times`);
return false;
}
console.log(`Looped ${div} times`);
return true;
}
// This is a known prime
console.log(isPrime(1299827));
console.log(isPrime(1299827));
/* Output
Looped 1141 times
1299827 is prime: true
Looped 1141 times
1299827 is prime: true
*/
view raw SimplePrime.js hosted with ❤ by GitHub
Simple Prime

As we can see, when the function is called twice for the same input, it goes thru the same numbers of execution cycles to compute whether it’s prime or not. What we can do is store the result for that number in some map and then return it without computing it again.

Here is modified isPrime with result caching.

// We store previous results here
const cache = {};
// Check if given number is prime
const isPrime = number => {
// Check cache if we have previous result
if (number in cache) {
console.log(`Found ${number} in cache: ${cache[number]}`);
return cache[number];
}
if (number < 2) return false;
// Divide number by all numbers from 2 to sqrt(number)
// If divisible, then its not a prime
let div;
for (div = 2; div < Math.sqrt(number); div++)
if (number % div == 0) {
console.log(`Looped ${div} times`);
cache[number] = false;
return false;
}
console.log(`Looped ${div} times`);
cache[number] = true;
return true;
}
// This is a known prime
let number = 1299827;
console.log(`${number} is prime: ${isPrime(number)}`);
console.log(`${number} is prime: ${isPrime(number)}`);
/* Output
Looped 1141 times
1299827 is prime: true
Found 1299827 in cache: true
1299827 is prime: true
*/

As we can see, the second time we call isPrime with the same input, it returns the value from cache, saving time of executing the for loop. This is Memoization.

However, we would have to write our own code for Memoization every time. Can’t we build a standalone Memoization and “plug it” on different functions?

Of course we can!

// Check if given number is prime
const isPrime = number => {
if (number < 2) return false;
// Divide number by all numbers from 2 to sqrt(number)
// If divisible, then its not a prime
let div;
for (div = 2; div < Math.sqrt(number); div++)
if (number % div == 0) {
console.log(`Looped ${div} times`);
return false;
}
console.log(`Looped ${div} times`);
return true;
}
const memoize = fn => {
// We store previous results here
const cache = {};
// Return a function to be called
return memoized = (args) => {
// If result not in cache, first cache it
if (!(args in cache))
cache[args] = fn(args);
// Now return it
return cache[args];
}
}
// This is a known prime
let number = 1299827;
const smartPrime = memoize(isPrime);
console.log(`${number} is prime: ${smartPrime(number)}`);
console.log(`${number} is prime: ${smartPrime(number)}`);
/* Output
Looped 1141 times
1299827 is prime: true
1299827 is prime: true
*/

Yay! We have created a “plug in” called memoize, which we can use to wrap any pure function (one which has no side effects and returns the same result for same inputs).

Wait a minute… if we call smartPrime with thousands of different values, won’t it eat up memory in the cache? Unfortunately, yes!

In the next blog post, we will see how to build Memoize using JavaScript Proxy object and how to keep the cache size in control by keeping only the MRU (Most Recently Used) and MFU (Most Frequently Used) entries.

Memoize Series

  1. Build Memoize in JavaScript – Part I (Higher order function)
  2. Build Memoize in JavaScript – Part II (Proxy Object)
  3. Build Memoize in JavaScript – Part III (MRU cache)
  4. Build Memoize in JavaScript – Part IV (MFU cache)

global pollution in JavaScript

JavaScript is far forgiving… Without realising, we land up adding things in the global scope and later run into massive problems.

Let’s first take a look at JavaScript process map to understand how JavaScript organises functions, variables and properties in memory. Entire magic happens in the HEAP.

Process Map of JavaScript

So, there are different types of “scopes“, like global, local, closure etc. Anything with var and let doesn’t go into the global scope but some variables (without var/let) and functions will go into global scope

// Global scope
g_a = 1;
// local to enclosing anonymous function (node.js)
var a = 1;
// Global scope
function hello(name) {
console.log("Hello", name);
}
// Local scope
var greet = function(name) {
console.log("Greetings", name);
}
Global vs Local

As JavaScript programmers, we may not think about such things while writing them but later we may run into trouble.

It gets worse

Functions have dual nature in JavaScript

  1. Act as functions (duh!)
  2. Act as constructors (huh?)

And how do we know which is which? Well, there is no definitive way of determining that.
However, there is a convention that if the function name is camelCase, it is to be used like a function

// add is camelCase
// Use it like a function
function add(a, b) {
return a + b;
}
// Use it like a function
let result = add(1, 2);
console.log("result", result);
// Do NOT use it with new
// Sigh! It doesn't give an error
let unexpected = new add(1, 2);
// NOW, it gives weird result
console.log("unexpected", unexpected);
Output
result 3
unexpected add {}
view raw camelCase.js hosted with ❤ by GitHub
Using function like a constructor

Functions can also be used to create objects as they act as constructors

/*
If a function name starts with uppercase
It is "intended" to be used as a constructor
Imagine a "class" around it, it will make sense
*/
// class Person {
function Person(id, name) {
this.id = id;
this.name = name;
}
// }
// Now let's create the object
let eich = new Person(1, "Brendan");
console.log(eich.id, eich.name);
// OOPS.. we called is like a function
// But there is no error
let brendan = Person(2, "Wrongdon");
// Why error? where did id and name go?
console.log(brendan.id, brendan.name);
Output
console.log(brendan.id, brendan.name);
^
TypeError: Cannot read property 'id' of undefined
Functions as constructors

Sheesh! All this is soooo confusing. Not really! Let’s take a look at Digital Concept Visuals to understand what is happening inside the Process Map

Mystery of the missing properties

When we do
let eich = new Person(1, "Brendan");
we create an “object” from the function.

However, when we just call it as a function
let result = Person(2, "Wrongdon");
there is not object created, we are just running the function with this point to where? global dictionary

OOPS! We just polluted the global dictionary with id and name.

function Person(id, name) {
this.id = id;
this.name = name;
}
let eich = Person(1, "Brendan");
console.log(global.id, global.name);
Pollution of global scope

So how do we avoid id?

  1. use new when function name is upper – Person, Emp, Product
  2. call like regular function when its camelCase – add, getProduct, calcDiscount

All that is fine, but what if someone else calls our functions incorrectly?

Well, there are a number of ways we can can handle it.

  1. new.target
  2. globalThis
  3. Pollyfill globalThis
Let's start with new.target
// Constructor function
// Not to be used as normal function
function Person(id, name) {
// Was this called using new?
if (!new.target)
throw "Error: use 'new Person()'";
this.id = id;
this.name = name;
}
// Expect error here
let result = Person(1, "Brendan");
Output
throw "Error: use 'new Person()'";
^
Error: use 'new Person()'
view raw new.target.js hosted with ❤ by GitHub
Let’s try new.target

Yay! We got it!
Well… almost

Sometimes we use functions like “injectors”… ‘Point and shoot’.
If I am writing a function, I can use another function to inject properties and methods into my own object by simply calling them using .call and .apply

// Constructor function
// Not to be used as normal function
function Person(id, name) {
// Was this called using new?
if (!new.target)
throw "Error: use 'new Person()'";
this.id = id;
this.name = name;
}
// We ARE creating an object of Visitor
function Visitor(id, name, visiting) {
// Using Person as "injector"
// Sadly! It doesn't work
Person.call(this, id, name);
this.visiting = visiting;
}
let ryan = new Visitor(2, "Dahl", "Eich");
Output
throw "Error: use 'new Person()'";
^
Error: use 'new Person()'
call and apply

Sadly, Person.call does not get called with new, hence Person function rejects it.
What if we want ONLY normal calls like Person(1, “Eich”) to be rejected and not these

  • new Person(1, “Eich”);
  • Person.call(this, 2, “Dahl”);
  • Person.apply(this, [2, “Dahl”]
globalThis to the rescue

Basically we just want to reject it if called as normal function. So what is unique about it when it’s called as global function? THIS!!!

If called as normal function this is global. So let’s just test for THAT

// Constructor function
// Not to be used as normal function
function Person(id, name) {
// Was this set to global?
if (this == global)
throw "Error: use 'new Person()'";
this.id = id;
this.name = name;
}
// Expect error here
// let result = Person(1, "Brendan");
function Visitor(id, name, visiting) {
Person.call(this, id, name);
this.visiting = visiting;
}
let ryan = new Visitor(2, "Dahl", "Eich");
view raw global.js hosted with ❤ by GitHub

Yay! We’ have done it! Umm.. not really
When running in node.js, it has a global dictionary, but when running in browsers, there is no global but it’s called window

Oh ok! Let’s update it then

// Constructor function
// Not to be used as normal function
function Person(id, name) {
// Was this called using new?
if (this == global || this == window)
throw "Error: use 'new Person()'";
this.id = id;
this.name = name;
}
// Expect error here
// let result = Person(1, "Brendan");
function Visitor(id, name, visiting) {
Person.call(this, id, name);
this.visiting = visiting;
}
global or window

Oops.. wherever we execute it, we will get an error… either for global or for window.

Introducing globalThis

globalThis is a property recently added to JavaScript, which gives us reference to the global/window/self

// Constructor function
// Not to be used as normal function
function Person(id, name) {
// Was this called using new?
if (this == globalThis)
throw "Error: use 'new Person()'";
this.id = id;
this.name = name;
}
// Expect error here
// let result = Person(1, "Brendan");
function Visitor(id, name, visiting) {
Person.call(this, id, name);
this.visiting = visiting;
}
let ryan = new Visitor(2, "Dahl", "Eich");
view raw globalThis.js hosted with ❤ by GitHub
globalThis

Finally!!! We have a way of rejecting ONLY pure function call but allow new, call and apply.
But will it work with earlier version of JavaScript? NOPE!
So, what do we do? Polyfill!

I am not going to go into details of how to polyfill globalThis but I can point you to another article which shows how ugly it’s going to be

https://mathiasbynens.be/notes/globalthis

Auto-Vivification in JavaScript (upgraded)

While I am an architect and even after 35 years, I love core coding, a lot of times I go into this “academic” developers mode where I tinker with stuff, get envious of another language and try to replicate it in a different language.

Like the other day someone (Manas Dash) showed me how to create quick enums in Python

RED, GREEN, BLUE = range(3)

I got so jealous that I started tinkering with JavaScript and landed up creating 3 different versions of range – for loop – yield, recursive function yield and finally Array expansion yield (You can find thos posts on this blog).

Recently, the same person asked me “Do you know auto-vivification?” and took me back a few years when I was tinkering with perl, so it launched me again into “academician” mode and I wrote auto-vivification in JavaScript and Python (see earlier posts).

All this was just academic interest but then someone said “Hey! You AutoViv doesn’t work in my chart application”. I sat up and said “Hain?”… I didn’t expect anyone to take it seriously. It was just a proof of concept, but then here was someone who was taking it more seriously than I was.

// Use Proxy object and handler to create a new property on the fly
let Auto = () =>
// Proxy() object of JavaScript
new Proxy({}, {
// Handler checks if prop exits
// otherwise, creates it
get: (obj, prop) =>
prop in obj
? obj[prop]
: obj[prop] = Auto()
}
)
// Create only TOP level
let univ = Auto();
// Now assign to deeper level
univ.college.stream.year = "A+";
// Bingo! It works
console.log(univ);
view raw Auto.js hosted with ❤ by GitHub
AutoVivification

Now someone was using this code and told me that many 3rd party libraries were failing because of these Proxy objects, and also wanted to use Array vivification

Something like this

var univ = Auto();
univ.college.stream.year = 2020;
// This is not Auto, its array
univ.college.course = []
univ.college.course[0] = 'Computers'
univ.college.classes = []
univ.college.classes[0] = {name:'Commerce',strength:30}
// Not Auto, so doesn't work
univ.college.classes[2].name = 'Electronics'
Auto doesn’t work on Array

This made me go back to my tinkering in Non-theoretical Engineer mode (Sorry, Sheldon!)
I had to add 2 things to my original code

  1. Convert Proxy graph back to Plain Old JavaScript object graph
  2. Add support for array vivification
Here is what is looks like now
// Needed to check isProxy
const util = require('util');
// Quick and Dirty Type Finder
const type = (obj) =>
obj.__proto__.constructor.name;
// Switch-offable debug
debug = console.log;
// Helpers
const isArray = (obj)
=> type(obj) == "Array";
const isObject = (obj)
=> type(obj) == "Object";
const isFunction = (obj)
=> type(obj) == "Function";
const isProxy = (obj)
=> util.types.isProxy(obj);
const isComplex = (obj) =>
isArray(obj) ||
isObject(obj) ||
isFunction(obj) ||
isProxy(obj)
const isSimple = (obj)
=> !isComplex(obj)
// Convert back to POJSO
// Deep clone Auto object
function deepClone(inputObject) {
// Do we have a leaf element?
if (isSimple(inputObject))
return inputObject;
// We have either array or nested object
let outputObject =
type(inputObject) == "Array"
? []
: {};
// If it's an array
// Even empty slots of Array(n)
if (isArray(inputObject)) {
for (let element = 0;
element < inputObject.length;
element++) {
let value = inputObject[element];
// Either recursively clone array/object
// Or simply copy native types
outputObject[element] =
isArray(inputObject) || isObject(inputObject)
? deepClone(value)
: value;
}
}
// If it's an object
else {
for (let element in inputObject) {
let value = inputObject[element];
outputObject[element] =
isArray(inputObject) || isObject(inputObject)
? deepClone(value)
: value;
}
}
// We are ready with POJSO
return outputObject;
}
// Support added for Array vivification
// If elements is non 0, it creates an array of objects
// otherwise creates a single object
function Auto(elements) {
// Convert to plain old javascript object
function toObject() {
return deepClone(this);
}
if (elements != undefined && elements > 0) {
// If called as Auto(n)
// Create array on n AutoVivs
return new Proxy(new Array(elements),
{
get: (obj, prop) => {
if (prop == 'toObject')
return toObject;
if (prop >= obj.length)
return undefined;
if (obj[prop] === undefined)
obj[prop] = Auto();
return obj[prop];
}
}
)
} else {
// If called as Auto()
// Create a single AutoViv object
return new Proxy({},
{
// Handler checks if prop does not exists, creates it
get: (obj, prop) => {
if (prop == 'toObject')
return toObject;
return (prop in obj
? obj[prop]
: obj[prop] = Auto());
}
}
)
}
}
let univ = Auto();
univ.college.stream.year = "A+";
univ.college.stream.subjects = Auto(3);
univ.college.stream.subjects[0].name = "JavaScript";
univ.college.stream.subjects[0].marks = 33;
console.log(univ);
console.log(univ.toObject());
console.log(univ.college.stream.subjects);
console.log(univ.college.stream.subjects.toObject());
/* Output
{ college: { stream: { year: 'A+', subjects: [Array] } } }
{ college: { stream: { year: 'A+', subjects: [Array] } } }
[ { name: 'JavaScript', marks: 33 }, {}, {} ]
[ { name: 'JavaScript', marks: 33 }, {}, {} ]
*/
view raw Auto.js hosted with ❤ by GitHub
Auto with Clone

The guy who is using is seriously said “Cool, it works!” and later said “Oh it works for nested and array too”.

This is still of academic interest to me. I haven’t built this as commercial piece of code or encouraging people to start using Auto-vivification. While it can be convenient, it can introduce more problems in the code with typos

Imagine landing up doing
univ.collage.steam.year = "A+"
and then wonder why it’s not working, because there will be NO errors with auto-vivification. Whatever you do WILL be accepted.

Still, if you want to give this a spin and use it in your side project, let me know how it goes.

Auto Vivification Series

  1. Auto vivification in JavaScript
  2. Auto vivification in Python
  3. Auto vivification in JavaScript (Upgraded)

Auto-Vivification in Python

We saw in the earlier post what is auto-vivification and how we can implement it in JavaScript.
Can we do it in Python as well? Yes, Sure.

Python does not have built in auto-vivification

Let's see if it supports it
univ = {}
univ.college.stream.year = 1
''' Output
univ.college.stream.year = 1
AttributeError: 'dict' object has no attribute 'college'
'''
view raw NoAutoViv.py hosted with ❤ by GitHub
No AutoViv in Python

Nope!
So what can we do?
Well, Python is a dynamic language, which allows us not only to add properties (attributes) at runtime but we can also ‘intercept’ calls to attributes which do not exist.

class Univ:
def __init__(self):
# define an attribute
self.name = "ABC"
univ = Univ()
print(univ.name) # This works
print(univ.college) # This gives error
view raw NoAttrib.py hosted with ❤ by GitHub
No Attribute Error

So, can we intercept univ.college access and do something different? Sure

class Univ:
def __init__(self):
self.name = "ABC"
# This gets called when attribute is missing
def __getattr__(self, attribute):
try:
return self[attribute]
except:
return "We are very sorry, we cannot server you that yet"
univ = Univ()
print(univ.name) # Actual attribute
print(univ.college) # Custom response
''' Output
ABC
We are very sorry, we cannot server you that yet
'''
Intercept Attribute

Great, we can intercept calls for missing attributes, but can we create the attribute on the fly? Sure

Magic of dunders ( double underscores)
Here we override __getattr__/__setattr__ for univ.college.stream.year = “A+”
and we override __getitem__ for univ[‘college’][‘stream’][‘year’] = “A+”

auto inherits a dictionary

This way we can store the attributes in “dict” we are inheriting which simplifies our code to bare minimum. We can also show “bravado” and build this WITHOUT inheriting from dict and manage everything ourselves. Perhaps, another blog post?

Over to final code
# auto inherits a dictionary
class auto(dict):
# if caller did univ.college
def __getattr__(self, name):
try:
# check if its there
return dict.__setitem__(self, name)
except:
# if not, create it on the fly
dict.__setitem__(self, name, auto())
return dict.__getitem__(self, name)
# if caller did univ.college = value
def __setattr__(self, name, value):
# set it in internal dict
dict.__setitem__(self, name, value)
# if caller did univ['college]
def __getitem__(self, value):
try:
# if found return it
return dict.__getitem__(self, value)
except:
# if not, create it on the fly
dict.__setitem__(self, value, auto())
return dict.__getitem__(self, value)
univ = auto()
univ.college.stream.year = "A+"
print(univ)
univ2 = auto()
univ2['college']['stream']['year'] = "A+"
print(univ2)
view raw AutoViv.py hosted with ❤ by GitHub
Auto Vivification in Python
And here is the output
univ1 {'college': {'stream': {'year': 'A+'}}}
univ2 {'college': {'stream': {'year': 'A+'}}}

Auto Vivification Series

  1. Auto vivification in JavaScript
  2. Auto vivification in Python
  3. Auto vivification in JavaScript (Upgraded)

Auto-Vivifaction in JavaScript

What? You mean auto-verification? NO!

Vivification is when we directly assign a deeply nested attribute/property while the ones above don’t exist, and yet the entire hierarch is automatically created.

Take example of *nix mkdir command. It creates a new directories in a given directory

# Create a single directory in current directory
$ mkdir temp
$ tree
.
└── temp

But, we can also create sub-sub-sub directory

# Try to create a nested directory
# When outer ones don't exist
$ mkdir faltu/bakwaas/bekaar

mkdir: faltu/bakwaas: No such file or directory

See, no vivification! We are unable to create bekaar directory because faltu and bakwaas don’t exist.
We will be forced to create parent directories before the child and grandchild.

# Sigh! One at at ime
$ mkdir faltu
$ mkdir faltu/bakwaas
$ mkdir faltu/bakwaas/bekaar
$  tree
.
└── faltu
    └── bakwaas
        └── bekaar

Don’t we wish we could directly create bekaar without creating faltu and bakwaas first?
Welcome to Auto-vivification. Automatic creation of outer structure when directly creating a nested structure.

# Vivification in mkdir (watch the p)
$ mkdir -p good/bad/ugly
$ tree
.
└── good
    └── bad
        └── ugly

So now we understand auto-vivification, can we do this in programming languages as well?
Well, *some* of them, like perl

perl lnaguage has support auto-vivification. We can directly assign to $year and it would automatically create the chain of $college and $stream

my $univ;
my $college="SITS";
my $stream="BECS";
my $year=4;

$univ{$college}{$stream}{$year}="A+";
print($univ{$college}{$stream}{$year});

Let's do it in JavaScript
// No auto-vivification in JavaScript

// Create top level object
let univ = {};

// Now assign to a deeper level
univ.college.stream.year = "A+"; // ERROR

--------------------------------------------
Output
--------------------------------------------
univ.college.stream.year = "A+"; // ERROR
             ^

TypeError: Cannot read property 'stream' of undefined

Yep, that’s right. While we have an object called univ, currently we do not have a property called ‘college’ and ‘stream’ while trying to assign value to ‘year’

Let’s understand the problem first. When we try to assign to a nested property in JavaScript, it tries to “get” the parent property, which does not exist and we get an error.

How about if we intercept that and create the parent property on-the-fly? Hmm…

let univ = {
  // If property exists return it
  // Otherwise, create it and return it
  get: (prop) => { 
    this[prop] 
      ? this[prop] 
      : this[prop] = {} }
}

univ.college = "SITS"; // WORKS!!!
console.log(univ);

univ.college.stream.year = "BECS"; // ERROR
console.log(univ); 

Well, our joy was short-lived. While it can create any property on the fly inside univ
univ.college = "ABCD";
univ.establised = 1884;
univ.name = "Amazing";

but we cannot do it at the next level, so this doesn’t work
univ.college.stream = "CS";

JavaScript Proxy object to the rescue!
A Proxy object plugs-in another object and can be handler for certain functions/properties.
E.g. We can have a Proxy object which handles get for the handled object.

// Use Proxy object and handler to create a new property on the fly
let AutoViv = () =>

  // Proxy() object of JavaScript
  new Proxy({}, // ANY blank object
    {
      // if property exists, return it
      // Otherwise, create it
      get: (obj, prop) => 
        prop in obj 
          ? obj[prop] 
          : obj[prop] = AutoViv()
    }
  )
Time to put this to test!
// Use Proxy object and handler to create a new property on the fly
let AutoViv = () =>

  // Proxy() object of JavaScript
  new Proxy({},
    {
      // Handler checks if prop does not exists, creates it
      get: (obj, prop) => 
        prop in obj 
          ? obj[prop] 
          : obj[prop] = AutoViv()
    }
  )

// Create only TOP level
let univ = AutoViv();

// Now assign to deeper level
univ.college.stream.year = "A+";
console.log("univ", univ);

let univ2 = AutoViv();
univ2['college']['stream']['year'] = "A+";

// Bingo! It works
console.log("univ2", univ2);

Output
univ { college: { stream: { year: 'A+' } } }
univ2 { college: { stream: { year: 'A+' } } }

Congratulations! We have an Auto-Vivification object in JavaScript now, which allows us to create a nested property without first defining its parent property!

Can we do it in other languages too? Maybe next post.. AutoVivification in Python

Auto vivification Series

  1. Auto vivification in JavaScript
  2. Auto vivification in Python
  3. Auto vivification in JavaScript (Upgraded)

Tail Recursion! What???

You may have heard of recursion, right? It’s when a function calls itself and possibly passes a new set of parameters. This causes stack frame to be created in the stack for every call. If you do not have a stopping condition, well, it leads you to one of favourite site, yep, you guessed it – StackOverflow

Here is a beaten-to-death example of recursion in JavaScript
function factorial(value) {
  // Check out stackframes
  console.trace();

  if (value < 1)
    return 1;

  // Calls itself, create stackframe
  return value * factorial(value - 1);
}

// Should output 120
console.log(factorial(5));

// Give a large value and goto StackOvrflow
console.log(factorial(100000));

So what it tail recursion? Well, its NOT recursion! Eh?
Some languages can convert a recursive function into a normal function with recursive calls becoming a loop internally. Why do that? Because recursion needs a lot of stack memory and is slower because it has to create a stack frame, call the function and pass parameters.

Umm.. let's take a look at recursion

Here is a process map showing multiple stack frames created for recursion, each containing the same parameter but containing different values in different stack frames.

This is what a recursive functions looks like in the Process Map

Now, not all languages support tailrec, so I am going to use Kotlin for examples. The reason being, Kotlin has a keyword called tailrec which has to be applied to the function signature and if your function is not tail-call, it throws a warning, so we can check if we are writing tailrec recursion properly or not.

Can we do it in JavaScript? Ohh, you missed the bus! Chrome V8 has introduced tailrec in JavaScript but then removed it again.

So let's go
// Functions are 'fun' in Kotlin
fun factorial(value: Int): Int {
    if (value <= 1)
        return 1;

    return value * factorial(value - 1);
}

fun main() {
  println( factorial(5) )
}
Now lets add tailrec to it
// Notice tailrec
fun factorial(value: Int): Int {
    if (value <= 1)
        return 1;

    return value * factorial(value - 1);
}

fun main() {
  println( factorial(5) )
}
Annnnd we get a warning!
Kotlin clearly tells us that this is NOT a tailrace function

So when is a recursive function can be TCO (Tail Call Optimised)?
The rule is very simple, the last line should be a recursive call and not an expression.
e.g.
return value * factorial(value-1)
cannot be a tail rec as the statement in not ONLY function call, like this
return factorial(value-1)

But THAT won’t work, the of result factorial will never get multiplied with value on the way back and final result will alway be 1, right? RIGHT!

So, we will change our strategy and multiply value on our way IN, instead of our way out.

// We pass 2 params
// value -> 5, 4, 3, 2, 1
// level -> 5, 20, 50, 120, 120
fun tailfactorial(value: Int, level: Int = 1): Int {
    if (value <= 1)
        return level;

    // LAST statement is ONLY recursive call
    return tailfactorial(value - 1, level * value)
}

fun main() {
  println( factorial(5) )
}

Well, this seems to print the correct result, but is it automatically a tailrec? Well, some language compiler may automatically convert it (like JavaScript did for a while), but Kotlin expects us to explicitly state that it wants us to do that

Finally!
// We finally got our tailrec working
tailrec fun tailfactorial(value: Int, level: Int = 1): Int {
    if (value <= 1)
        return level;

    return tailfactorial(value - 1, level * value)
}

fun main() {
  println( factorial(5) )
}

But how can we be sure if its really converting into a loop internally?
Well, Kotlin lets you decompile Kotlin code into underlying Java source, so let’s have a look

Non tailrec factorial decompiled!
Pretty much a recursive function
Now tailrec tailfactorial decompiled!
Voila! recursive function converted into a loop!

We can further test it by running the code in debugger and step thru the recursive calls and see that no stack frames are being created for tail recursion.

So, tail recursion is a heavy term for ‘convert recursion internally into a loop’, provided we get it right – The last statement can ONLY be recursive call and NOT an expression