DEV Community: BlueBlazin

Dependency Injection

BlueBlazin — Sat, 10 Dec 2022 13:43:46 +0000

The Story Begins

It's one of those familiar terms in software engineering that you've never really bothered to learn. I mean, the name itself is rather uninviting. This seems to be a common theme in programming. There are many important but usually straightforward concepts gated behind extremely complicated sounding names such as closures, encapsulation, polymorphism, and ... dependency injection.

Imagine you have a box. This box takes certain inputs and produces certain outputs. Now in order to be useful this box presumably does some stuff inside. The question is, does this box also create something out of nothing? That is, does it only use the inputs provided or it also creates things inside that it (hopefully) uses to produce the final output?

What good software engineering suggests is that unless absolutely necessary, the box should not be producing any thing of its own but rather should get it from outside as its input.

This thing of course is something the box depends on. And I am telling you that any dependency should be injected into the box in the form of an input to the box. That's dependency injection.

But why?

By now it should be obvious that the "box" is a function. Or it's a class or any other unit in your program that's taking inputs and producing outputs. Let's go through an example.

Pretend you're building an app and one of the boxes making up this app creates a string "hello, world". It then goes on to use this string and does other stuff to finally produce some output.

Our app is getting popular and soon we have users from all over the world. But now we want to offer the app in multiple languages. Now each box where we created a string like our "hello, world" needs to be modified to first pass that string through a translate() function. But that's messing up our unit tests based on the system language and now we have to update all of those as well.

The principle of dependency injection is asking us:

If a box is creating something inside it, does it absolutely have to be created within the box?

In our case, the thing that our box is creating internally is the "hello, world" string and no, it most certainly does not have to be created inside the box.

Here we should realize that the string is a dependency of the box and should be lifted outside. So we simply pass the string as an input. Now our unit tests for this box still work deterministically and we can pass translated strings as inputs if necessary.

Conclusion

Next time you're writing code and working on a function, just question yourself -- is it necessary for everything originating from inside the function to be created there? If not, inject it from the outside instead.

Understanding `this` in Javascript

BlueBlazin — Mon, 02 Aug 2021 12:46:48 +0000

How did `this` all begin?

The one thing that seems to unify beginner javascript programmers more than anything else is their shared confusion about the concept of this.

Perhaps that's because this or self in other languages behaves differently than in javascript.

Look, the language was created in ten days. Some less than ideal decisions were probably made. It is what it is.

`This` exists

I mean it. You can access this anywhere in a javascript program. At the outermost level? Sure!

console.log(this);

Inside a function? Also, yes.

function foo() {
  console.log(this);
}

What about constructors? Of course!

function Bar(x, y) {
  this.x = x;
  this.y = y;
}

But see, here lies the confusion. It certainly feels sensible to talk about this as a property on functions, constructors, and methods. But that's wrong.

This exists on its own! It's a property on function scopes!

What's `this` scope thing?

You can think of function scopes (or Function Environment Records to be proper) as containers for variables. Each scope will contain a bunch of names of variables (and associated values).

From within any function scope you can:

access variables defined in that scope
access variables defined in any ancestor function scope

At the outermost level is the global scope on which live such famous builtins as: Math, and console, and Number among others.

Notice how they are labeled foo() scope or bar() scope in the diagram and not foo scope, bar scope, etc.

That's because a scope is associated with function calls, not functions themselves. A new function scope is created for each function call. That's why you could do:

function foo(x) {
  let bar = x;
}

foo(7);
foo(42);

and bar will be created two different times with two different values assigned to it.

Now look at the image again. You'll see this exists on each function scope. You don't need to declare it, it's added to the scope automatically.

`This` once more

Here's a recap of what I just said:

Calls create function scopes. Those scopes create this. Ergo, by transitivity, this is associated with function calls.

Not functions. Not constructors. Calls!

The rules of `this` language

In javascript, there are just two types of calls. The value of this depends on the type of call you make.

1. Function calls

Just plain old vanilla function calls.

function foo() {
  console.log(this);
}

foo(); // Window

This gets set to the global Window object for these.

2. Method calls

Method calls are nothing special, just calls which have the form <object>.<attribute>(). For example:

const foo = { 
  bar: function () {
    console.log(this);
  }
};
foo.bar();

For method calls, this gets set to the object from which the method was called. Again, functions don't matter* for this, just the calls.

function foo() {
  console.log(this);
}

let x = { bar: foo };

foo(); // Window
x.bar(); // x
let baz = x.bar;
baz(); // Window

Even baz will print Window. It's not a method call, it doesn't follow the method call format!

That's pretty much all there is to it.........

........or is it?!

I apologize for `this`

Remember how I told you this is all about function calls, not the functions themselves? Well, I lied.

Ok look, let me remind you once again: They made javascript in 10 days!

The this rules we've discussed above, they are a bit limiting. So there's three* ways you can override these rules.

* don't you dare even mention apply

1. `call`

The special call method on functions allows you to pass your own custom value of this to a function call (or the call's scope I should say).

function foo() {
  console.log(this);
}

foo.call({ a: 42 }); // { a: 42 }

2. `bind`

bind is another builtin method on functions. Much like call it too allows you to pass a custom value for this to the function call. Except unlike call, bind doesn't immediately call the function. It instead returns a special 'bound' functions.

function foo() {
  console.log(this);
}

let bar = foo.bind({ a: 42 });
foo(); // Window
bar(); // { a: 42 }

3. Arrow functions

Arrow functions are the third way to override the call rules for this described previously. Arrow functions capture the this from the function scope in which they are created.

function foo() {
  const bar = () => {
    console.log(this);
  };

  return bar;
}

let bar = foo.call({ a: 42 });
bar(); // { a: 42 }

So they're essentially the same as defining a normal function but then also binding it.

// achieves the same effect
function foo() {
  const bar = (function () {
    console.log(this);
  }).bind(this);

  return bar;
}

let bar = foo.call({ a: 42 });
bar(); // { a: 42 }

In summary

Yes, no pun in the heading this time (oops). The key takeaways are this:

In JS this is associated with the current function scope, and since function scopes are associated with functions calls -- this is associated with calls. Those are the rules but they can be overridden.

That is the reason why people are often confused when passing functions referencing this to callbacks. It's also why you were told to use arrow functions if you need to pass them to callbacks.

I too was confused about this for a long time. Instead of taking the more sensible approach of reading an article such as this one, I instead decided to implement my own javascript.

I wrote a subset of javascript. In that subset of javascript. If you want to go down that rabbit hole, then check out the repo:
https://github.com/BlueBlazin/thislang

If you want more posts on other javascript or computing related topics let me know on twitter:
https://twitter.com/suicuneblue

Introduction to Recursion; or Wishful Thinking

BlueBlazin — Sat, 23 Nov 2019 10:29:22 +0000

Introduction

This post introduces recursion using three examples -- reversing a linked list, the towers of Hanoi problem, and deletion in a binary search tree. This article assumes no prerequisites other than familiarity with a programming language (I'll use python but you can easily follow along even if you aren't familiar with it).

Wishful Thinking

Recursion is a top-down approach to solving problems wherein a function calls itself.

The essence of a recursive function is to call itself on instances of sub-problems. These function calls in turn can call the same function again, and so on until some base condition is reached where the solution can be directly computed, and the recursive calls halted.

These chains of recursive calls makes it hard to wrap your head around the concept recursion. Understanding it from a bottom up perspective can get overwhelming very quickly.

So it's easier to look at it from a top down point of view. That's where applying the idea of "wishful thinking" becomes powerful. So much so, that I feel recursion isn't just best understood using wishful thinking, but rather it is wishful thinking!

But that's a lot of words, let's dive straight into it now, with our first problem being that of reversing a singly linked list.

Reversing a Linked List

A linked list is a data structure containing nodes linked by arrows. In a typical singly linked list, each node contains some data, and an arrow to the next node. A doubly linked list node, as you might guess, contains arrows to both the next, and previous nodes.

Defining a linked list in python is very easy. We just define a class:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

Okay, that's straightforward. To make a new linked list you just create multiple nodes and then chain them appropriately:

head = Node(12)
head.next = Node(99)
head.next.next = Node(37)

It doesn't have to be this cumbersome, we can actually write a function that takes a python list and converts it to a linked list:

def make_list(l):
    head = Node(l[0])
    current = head
    for i in range(1, len(l)):
        current.next = Node(l[i])
        current = current.next
    return head

The last thing is to be able to print out the list:

def print_list(node):
    l = []
    while node:
        l.append(node.value)
        node = node.next
    print(l)

I'm being this explicit only because this is the first example. For the others, I won't write out the code for all helper functions. Also note that I'm not writing any tests, checks, or assertions. While important, they are extraneous to the topic being discussed. Anyways, with that out of the way let's move on to the real task at hand: given a head node, we want to reverse the list.

This means that our reverse_list function should take the first node, and return the last node, with all links between nodes reversed.

def reverse_list(first):
    return last

This is it! Our first encounter with wishful thinking. We wish for two things,

to get the last node of the list
to reverse all the links.

We use wishful thinking to assume that the list is reversed from the second node onward, and that we are returned the last node.

def reverse_list(first):
    last = reverse_list(first.next)
    return last

Great! Just like that, we now have our old first node, a reversed list from the second node to the last node, and a pointer to the last node. The only thing we need to do now is to have second.next point to first, and first.next equal None (a.k.a point to nothing).

def reverse_list(first):
    last = reverse_list(first.next)
    first.next.next = first  # second was first.next in the unreversed list
    first.next = None
    return last

At this point we're almost done. The only thing that remains is to deal with the so called 'base case' of when first doesn't have a next. In that case we just return first. In other words, if the list was just a single node, then its reverse is the same as itself.

def reverse_list(first):
    if first.next is None:
        return first
    last = reverse_list(first.next)
    first.next.next = first
    first.next = None
    return last

We can test this, for example:

l = make_list([1, 2, 3, 4, 5])
print_list(l)
rl = reverse_list(l)
print_list(rl)

The output will be:

[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]

If you're used to a bottom-up way of thinking about things, this could be a little hard to accept. But with practice you can develop an ability to use wishful thinking, and recursion will reduce to simply a matter of thinking boldly.

Towers of Hanoi

Our next problem is one of the most famous examples used when teaching recursion. You have three poles, A, B, and C, and disks of various sizes placed on the poles.

We want to move the stack of disks from pole A, to pole C. You may use any of the three poles during the task, but in the end all disks from pole A need to be on pole C. During the intermediate steps, you can only remove the topmost disk from a stack, and at any point disks on the stacks must be in descending order of size from bottom to top. The problem asks us to print all moves we must perform in order to move the stack from A to C.

Let's label the disks from 1 to n, 1 being the top most disk on the stack. With wishful thinking, the solution to this seemingly complicated problem is as simple as just describing the problem in English.

def hanoi(n, source, dest, spare):

The function hanoi has four parameters -- n is the number of disks, source is the starting pole, dest is the destination pole, and spare is the extra spare pole. If you think about it for a minute or two, a general strategy appears. Move the first n-1 disks from pole A to pole B obeying the rules. Move disk n from pole A to pole C. Move the n-1 disks from B to C, and we're done. No rules were violated and we moved all disks from A to C. Believe it or not, the solution in code is exactly that!

def hanoi(n, source, dest, spare):
    hanoi(n-1, source, spare, dest)
    print(f"Move disk {n} from pole {source} to pole {dest}")
    hanoi(n-1, spare, dest, source)

That's it! The first line states that we use our procedure to move the top n-1 disks to spare as destination, using dest as the spare pole. Then we move the largest disk from source to destination. Finally we move the n-1 disks from the spare pole to the destination pole. The only thing remaining is a base case. That's when n is zero, we don't do anything.

def hanoi(n, source, dest, spare):
    if n < 1:
      return
    hanoi(n-1, source, spare, dest)
    print(f"Move disk {n} from pole {source} to pole {dest}")
    hanoi(n-1, spare, dest, source)

If we call this function with arguments n=3, source="A", dest="C", and spare="B", we get this output:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Deletion In Binary Search Trees

A tree is by definition a recursive data structure. It's a linked data structure like linked lists, except instead of having a single next 'link', a tree node can have multiple 'children'. Trees have a root node, which may have links to several child nodes. These can themselves be thought of as root nodes to their own children, and are thus called 'sub-trees'. Thus, trees are recursive and many tree algorithms can be implemented elegantly using recursion.

A binary tree is a special type of tree where each node has at most two children -- left, and right. A binary search tree is a special type of binary tree where every node in the left subtree of a node has value less than its value, and every node in the right subtree has a greater value.

Binary Search Trees (BSTs) can be used to implement binary search, an efficient search algorithm that takes O(log n) time to check if an element is in the tree and return it.

The algorithm for binary search is very simple:

def search(root, value):
    if root is None:
        return None
    if value == root.value:
        return value
    return search(root.left) if value < root.value else search(root.right)

If the value is equal to the root node's value, return it. If it isn't, return the result of calling search on the left subtree if the value is less than the roots value, else the result of search on the right subtree.

The other base case is when the root node is None, in which case the value wasn't found and we return None.

Back to deletion, the algorithm can be a little tricky. We must maintain the BST property after the deleting the element (if it exists). There are three different cases depending on the number of children the node to be deleted has.

Algorithm for Deletion

In case you skipped the wall of text above, here's the deletion algorithm. The three cases that can arise when deleting an element are as follows:

The element has no children
The element has one child
The element has two children

The first case is almost trivial, we just set the node to None. If the node has one child, we set the node to point to that child instead. Doing that, along with some clever recursive code spares us from storing parent pointers or having unnecessary ugly code.

The Final case is the trickiest, where a node has both its children. In that case we'll first find the node with the largest value less than our node's value. That simply means we find the rightmost node from the left subtree. Once we have it, we'll save its value, set it to None, and change our node's value to this saved value.

Why does that work? Well, the node we found was from the left subtree so every element in the right subtree still has a greater value than it. Also, it had the biggest value from the left subtree, so all the other remaining elements in the left subtree will have a value less than it. So, the BST property is retained.

Finally, the code:

def delete(root, key):
    if   key < root.value:
        root.left = delete(root.left, key)
    elif key > root.value:
        root.right = delete(root.right, key)
    else: # key == root.value

What's happening here? Given a key (the element), we first have to find the node with that value. This is just binary search. Since we want to deal with the possibility that no node with the given key's value exists, let's handle it first.

def delete(root, key):
    if root is None:
        return None
  if key < root.value:
      root.left = delete(root.left, key)
  elif key > root.value:
      root.right = delete(root.right, key)
  else:
    # TODO: implement case where node with value equal to key is found
  return root

While this bit looks easy, there's actually something subtle and interesting going on here. We aren't just calling delete(root.left, key) for example, we're setting root.left equal to it! I mentioned above that we'll use some clever recursive code to avoid having parent pointers and ugly helper code. That clever recursive bit isn't just helping keep the code elegant, it's actually directly applying our old friend:

Wishful Thinking!

What is it that we wish to do if we knew that the key we want to delete is in the left subtree of our root node? Why, we want to point root.left to the subtree where the node with value equal to this key is deleted and everything has been taken care of of course!

And that's exactly what we're doing. We're simply setting root.left, or root.right to this subtree which has had the correct node deleted, and its BST property restored. That's some extreme wishful thinking but it will all work out in the end.

Now, let's move on to the main task of actually deleting the node once it's found using our three cases. We're gonna handle case 1, and one half of case 2 together, in a single line of code!

def delete(root, key):
    if root is None:
        return None
    if   key < root.value:
        root.left = delete(root.left, key)
    elif key > root.value:
        root.right = delete(root.right, key)
    else:
        if root.left if None:
            return root.right
    return root

Since our implementation of case three depends on finding the rightmost child from the left subtree, the left subtree can't be None. So if it is, we simply return root.right. If root had no children, this would just return None which would propagate up through the recursive call and set the appropriate child of our root's parent to None. No need for parent pointers or checks for which child of the parent the deleted node belonged to. This also handles the case when the node to be deleted has a single right child.

Now let's focus on case 3, since case 2 with a single left child is handled automagically by just considering case 3.

def delete(root, key):
    if root is None: return None
    if   key < root.value: root.left = delete(root.left, key)
    elif key > root.value: root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        tmp = root
        root = get_max(root.left)
        root.left = del_max(tmp.left)
        root.right = tmp.right
    return root

First, create a temporary variable that points to the same node as root. This is needed because root will itself soon point to the rightmost child of the left subtree. We set root to the highest valued node (rightmost child) in the left subtree using the get_max function.

Once root is pointing to it, we'll set its parent to point to None instead. In other words, we'll delete this rightmost node using del_max. The node itself isn't deleted per se, it's just not pointed to by its parent anymore. The root node is still pointing to it, so it's safe.

Finally, we point our new root's right child to the old root's right child, which was stored safely in tmp. Finally we return root. This will propagate up through the chain of recursive calls, correctly setting left and right subtrees of parents to new subtrees with the correct node deleted and the BST property intact. Here's the full code:

def delete(root, key):
    if root is None:
        return None
    if   key < root.value:
        root.left = delete(root.left, key)
    elif key > root.value:
        root.right = delete(root.right, key)
    else:
        if root.left if None:
            return root.right
        tmp = root
        root = get_max(root.left)
        root.left = del_max(tmp.left)
        root.right = tmp.right
    return root

def get_max(root):
    if root.right is None:
        return root
    return get_max(root.right)

def del_max(root):
    if root.right is None:
        return root.left
    root.right = del_max(root.right)
    return root

By now, you have enough experience with wishful thinking to analyze the two functions get_max, and del_max yourself. The del_max function in particular is a microcosm of the larger delete algorithm. Go ahead and apply wishful thinking to understand how it works.

Conclusion

Hopefully seeing these three examples of recursion in action will help you understand how you can use it to solve some challenging problems.

There are many problem solving strategies which employ recursion.

In the 'divide and conquer' method you recursively solve multiple simpler sub-problems and build up the solution from them.

In dynamic programming, you keep a table of intermediate solutions so you don't repeat work.

Finally, with mutual recursion, you can keep your code succinct and elegant.

I want you to take away this if you choose to employ wishful thinking - think bold, think top down, and forget about the base case until the end.

DEV Community: BlueBlazin

Dependency Injection

The Story Begins

But why?

Conclusion

Understanding `this` in Javascript

How did this all begin?

This exists

What's this scope thing?

This once more

The rules of this language

1. Function calls

2. Method calls

I apologize for this

* don't you dare even mention apply

1. call

2. bind

3. Arrow functions

In summary

Introduction to Recursion; or Wishful Thinking

Introduction

Wishful Thinking

Reversing a Linked List

Towers of Hanoi

Deletion In Binary Search Trees

Algorithm for Deletion

Conclusion

How did `this` all begin?

`This` exists

What's `this` scope thing?

`This` once more

The rules of `this` language

I apologize for `this`

1. `call`

2. `bind`