DEV Community: J. Pichardo

Do you even recurse?... And if you do, do you do it safely?

J. Pichardo — Tue, 05 Jun 2018 01:37:27 +0000

Background

Have you ever written a factorial function? If you have then you might have done something like:

function factorial(n) {
  let result = n;

  for (let i = n - 1; i > 1; i++) {
    result = result * i;
  }

  return result;
}

Or even something like:

function factorial(n) {
  return a > 1 
    ? n * factorial(n - 1) 
    : 1;
}

Both are valid approaches but there is something about the second approach that makes it easier to understand what it is doing, we can easily read what factorial does is n * (n - 1)! and that it calls itself until n equals 1 and then we finish, that is what we call a recursive function:

A function that either calls itself or is in a potential cycle of function calls.

The problem

Recursion is great, it helps us write more concise, readable and simple code. However, there is a big drawback regarding recursion, take for instance our factorial function, when we call factorial(5) we get 120, however, if we call the same function with a way bigger value, let's say 12,000 we get a whole different result:

RangeError: Maximum call stack size exceeded

You see, every runtime has a maximum stack size (node has a limit of around 11k), so when we make long recursive cycles our program crashes as there is no more stack space.

The solution

Fortunately, there is an alternative that allows us to safely write recursive functions, Tail Call Optimization.

TCO is a process that many languages have implemented to deal with long recursive chains. It is based on the premise that when a procedure/function calls a subroutine as its final action, then it is possible to replace the current call stack frame with the frame of the new invocation, hence, being as performant as the looped version of that function.

So, how would we modify our factorial function to fulfill this constraint? We could do the following:

function factorial(n, acc = 1) {
  return n > 1 
    ? factorial(n - 1, n * acc) 
    : acc;
}

As you see we added a property, acc, which allows us to pass down any relevant information (our current accumulative product) to the next factorial invocation, thus, rendering all the information of the previous call useless and allowing us to get rid of that stack frame, so, instead of having 11k+ stack frames, we would be replacing the same frame 11k+ times.

Pretty neat right?

Sadly, even though TCO is part of the javascript specification, many engines have decided not to implement it.

An interesting alternative

Despite this, there is still a safe way to use recursion. We can implement our own version of TCO.

According to what we have seen of TCO our aim should be to make a way for recursive functions to behave in a way that instead of having a linear growth of the stack size we keep a constant size, so let's ask ourselves, what control-flow structure do we know that behaves that way? Loops! So what if we had a loop that executed functions repetitively? Well, that is what we call a trampoline.

A trampoline is a special kind of loop that executes thunked-functions, that is, functions that return the next function to call. So, what if we converted each of our recursive calls into a thunk, and pass it to a trampoline? Would our stack maintain a constant size? Let's see:

First, we've got to rewrite our factorial function to be a thunked-function, which would be something like:

function factorial(n, ret = res => res) {
  return n > 1 
    ? () => factorial(n - 1, res => ret(n * res)) 
    : ret(1);
}

Let's analyze what we did there, shall we?

We added an argument to the function signature, ret, which as you see is a function, that fulfills a special role, it allows us to compose our thunks.
We now return a function instead of the value of the factorial computation, by doing that we intend to defer the execution of that function until our trampoline decides to call it.

So let's get into our trampoline implementation.

As we said a trampoline is a loop that executes thunked-functions one at a time, so, taking advantage of the decorator pattern we could write the following:

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);

    while (result && typeof result === 'function') {
      result = result();
    }

    return result;
  };
}

As you realize the implementation is rather simple, we decorate our recursive function with our trampoline in order to do TCO. There are somethings worth noticing here:

The while runs until there are no more functions to call.
Our fn parameter is only used at the beginning since each result represents the next function to call.

So our final result would be something like:

As you can see our call stack never steps pass the 13 frames, which allows us to work with longer recursive chains without worrying about a stack overflow.

A little extra

Even though the trampoline function works nicely I would still add something else to our API, a Symbol! yeah, one of those new things with ES6 that allow us to do metaprogramming, so my final implementation would be:

function factorial(n, ret = res => res) {
  return n > 1
    ? {
        fn: () => factorial(n - 1, res => ret(n * res)),
        [Symbol.for('recurse')]: true
      }
    : ret(1);
}

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);

    while (result && result[Symbol.for('recurse')]) {
      result = result.fn();
    }

    return result;
  };
}

// Or with Decorator syntax


@trampoline
function factorial(n, ret = res => res) {
  // ...
}

That way we can be sure that we stop when we are supposed to, not after.

Finale

Recursion is great, one of the pillars of functional declarative programming, however, it has an interesting drawback, which can cause some unintended issues. Here we saw how to optimize a recursive call using tail calls. It is also important to note that by making the execution path more complex the performance (time-wise) decreases, so use this method with consideration and avoid adding extra layers of complexity where is not needed.

I hope you find this article useful, please let me know what you think about this implementation of TCO.

p.s. While doing research in this topic I stumbled with this awesome article which mentions the possibility of accomplishing a similar effect using python generators, so I'll be researching a way to use ES6 generators to improve the way we are optimizing our recursive calls.

Optional (null-safe) in javascript

J. Pichardo — Wed, 23 May 2018 15:19:27 +0000

Yesterday I ran into this StackOverflow question and it got me thinking about null/undefined handling in javascript.

A short background

What is undefined? undefined is a primitive value that is given to variables that have only been declared, non-existent properties or function arguments

What is null? null is another primitive value that represents the absence of value.

So what happens when we do the following


let obj;

console.log(obj.someProp);

We get the following error

TypeError: Cannot read property 'someProp' of undefined

And the same happens with null

null-checking

So, how can we avoid that? Well, lucky for us in javascript we have short-circuit evaluation, meaning that in order to avoid our previous TypeError we could write the following.


let obj;

console.log(obj && obj.someProp); // Prints undefined

But what if we want to go deeper, something like obj.prop1.prop2.prop3? We would end doing lots of checks, like:


console.log( obj && obj.prop1 && obj.prop1.prop2 && obj.prop1.prop2.prop3 );

Seems obnoxious, doesn't it?

And what if we wanted to print a default value if there was an undefined or null in that chain? Then it would be an even larger expression:


const evaluation = obj && obj.prop1 && obj.prop1.prop2 && obj.prop1.prop2.prop3;

console.log( evaluation != null ? evaluation : "SomeDefaultValue" );

How do other languages do it?

This issue is not exclusive of javascript, it is present in most programming languages, so let's see how to do null-checking in some of them.

Java

In java we have the Optional API:


SomeClass object;

Optional.ofNullable(object)
    .map(obj -> obj.prop1)
    .map(obj -> obj.prop2)
    .map(obj -> obj.prop3)
    .orElse("SomeDefaultValue");

Kotlin

In kotlin (another JVM language) there are the elvis (?:) and safe-call (?.) operators.


val object: SomeClass?

object?.prop1?.prop2?.prop3 ?: "SomeDefaultValue";

C#

Finally, in c# we also have the null-condition (?.) and null-coalescing (??) operators.


SomeClass object;

object?.prop1?.prop2?.prop3 ?? "SomeDefaultValue";

JS Options

So after seeing all this, I was wondering, isn't there a way to avoid writing that much in javascript?, so I started experimenting with regex to write a function that'd allow me to access an object property safely.


function optionalAccess(obj, path, def) {
  const propNames = path.replace(/\]|\)/, "").split(/\.|\[|\(/);

  return propNames.reduce((acc, prop) => acc[prop] || def, obj);
}

const obj = {
  items: [{ hello: "Hello" }]
};

console.log(optionalAccess(obj, "items[0].hello", "def")); // Prints Hello
console.log(optionalAccess(obj, "items[0].he", "def")); // Prints def

And after that, I found about lodash._get, which has the same signature:

_.get(object, path, [defaultValue])

But to be honest I'm not that much a fan of string paths so I started searching a way to avoid them, then I came with a solution using proxies:


// Here is where the magic happens
function optional(obj, evalFunc, def) {

  // Our proxy handler
  const handler = {
    // Intercept all property access
    get: function(target, prop, receiver) {
      const res = Reflect.get(...arguments);

      // If our response is an object then wrap it in a proxy else just return
      return typeof res === "object" ? proxify(res) : res != null ? res : def;
    }
  };

  const proxify = target => {
    return new Proxy(target, handler);
  };

  // Call function with our proxified object
  return evalFunc(proxify(obj, handler));
}

const obj = {
  items: [{ hello: "Hello" }]
};

console.log(optional(obj, target => target.items[0].hello, "def")); // => Hello
console.log(optional(obj, target => target.items[0].hell, { a: 1 })); // => { a: 1 }

The future

Currently, there is a TC39 proposal that will allow us to do the following:


obj?.arrayProp?[0]?.someProp?.someFunc?.();

Looks pretty neat right? However, this proposal is still in stage 1, which means it will probably take a while before we can see this is js. Nonetheless, there is a babel plugin that allows us to use that syntax.

Finale

null has been and will be around for a while and I bet is one of the most hated concepts in programming, however, there are ways to procure null-safety. Here I've posted my two cents, let me know what you think or if you have any other alternatives.

p.s.: Here is a little pretty gist

If it works ... don't touch it?

J. Pichardo — Sat, 19 May 2018 03:30:56 +0000

My thoughts on software engineering.

As you might have guessed this all began with a common phrase, “if it works, don’t touch it”. I was talking to some friends and one started speaking about a project he had worked on last year and how the quality of his code had improved since, so this other friend says “well, if it works, don’t touch it”, then I started thinking about that and the times I’ve thought that or even said it and suddenly I considered what it means to be a software engineer and if by saying “don’t touch it” I was betraying the principles of my profession, so here are my final thoughts.

What does it mean to be a software engineer?

“the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software; that is, the application of engineering to software”

That is the way that ISO/IEC/IEEE Systems and Software Engineering Vocabulary define software engineering and by extrapolating from that definition we can state a software engineer to be one who applies engineering to the process of software building, but what does that really mean? Well, if we want to dig into that concept we need to start by defining what engineering is.

The ENCYCLOPÆDIA BRITANNICA states engineering as “the application of science to the optimum conversion of the resources of nature to the uses of humankind” and if go right to the basics we find out that the word engineering comes from two words “ingenium” and “ingenerare” which mean “cleverness” and *“to create” correspondingly, but where does this leave us? As we defined a software engineer as a person who applies engineering to software, and by taking the previous concept of engineering into consideration we could “refactor” that statement as:

A software engineer is a person who systematically seeks to devise the most optimum way of converting computing resources to the needs of a final user.

Responsibilities of a software engineer

There is a code of ethics (which I recommend you to read) that a joint task force by the IEEE and the ASC summarized in eight points and that I’ll try to summarize even more here (for the purpose of this article I will only include those points that define product, self and profession principles):

Ensure that their products and related modifications meet the highest professional standards
Advance the integrity and reputation of the
Participate in lifelong learning regarding the practice of their profession and shall promote an ethical approach to the practice of the profession.

So, by taking our previous definition and combining it with this professional principles we could complement our statement the following way:

A software engineer is a person who systematically seeks to devise the most optimum way of converting computing resources to the needs of a final user while meeting the highest standards possible and that is constantly contributing and improving his/her knowledge.

So, should I touch it?

Technology evolves, actually faster than anything else, and with every step forward us who are in the business of building it are required to evolve with it. Take for example WEB technologies, they evolved from being a system serving static files to client-server architecture and code on demand and then to websockets, GraphQL, RESTful services, etc. So imagine a software developer, who is asked to build a site with some X functionality, decides to use something with known vulnerabilities like flash or java applets, would you consider him/her to be ethical or even a good software engineer? No, it is not an optimal solution, nor it meets the highest professional standards, so why do it in the first place? (It might surprise you but I have known people like this).

Now let’s see the case of an existing system. I work with an eCommerce platform that has around 4.5million active users, we use Angular for the front-end however due to its configurable nature some pages take a long time to load, and since the site has lots of components active at the same time some operations take long time due to change detection, this could be solved using observable bindings and ChangeDetectionStrategy.OnPush , however it works as it is, it solves the current needs of our customer. Therefore, should I make the change? Let’s see:

The current solution works, there is no doubt about it, however does it fulfill the requirements of what a software engineer should do? The answer is no, it isn’t not optimal and it does not meet the highest standards possible. Should I change it? Will the extra work be worth it? Yeah, I should and will definitely be worth it, because not only I will be satisfying my role as a software engineer but it will prevent future issues, at this point you might be thinking about all the bugs that might appear after this change, but, didn’t we say software engineering was systematical? We did, therefore changes to an existent, even a new, code structure should always go through a pipe of quality analysis, code reviews, functionality reviews, etc. Sure, that never filters all bugs but I’d rather deal with issues that appear due to an improvement than with issues that exists as a consequence of technical debt.

So, what are your thoughts about this?

References:

(1): https://www.computer.org/web/education/code-of-ethics