Fancy Fun w/ Functional Decorators
Tags: javascript, python, programming, beginners
Published: 2023-06-30 17:32:39


**The following discussion assumes familiarity with writing functions in a high-level programming language.**

- [TLDR; Skip to the goodies.](#The decorator pattern can be implemented as follows)
- [Skip to cache implementation](#PretendProblem)
- [Skip to execution](#Execution)
- [Results](#Results&&Conclusion)

The decorator pattern provides a concise and elegant way to add functionality to pre-existing code.  The programmer may write the decorating function once and thereafter decorate any number of functions, anywhere.   Sound like too much freedom? As is the nature of programming, there are virtually limitless create-o-logical, electroreasonable ways to write things.  It's my hope to ground the discussion with practical, actionable examples which might justly and concisely demonstrate the potential of the decorator pattern.  

___


Given the name, it would be natural to imagine there's something ~fancy~ about decorators.  They are not, in fact, frivolous adornments (Though the programmer may find them pretty!).  
The truth is they are simply a way of writing _functions_ guided by a specific _design pattern_.

Thankfully, Python and JavaScript both support higher-order functions, meaning all valid functions qualify as "first-class citizens" which can be passed as function arguments *and* returned from *other* functions.  
Cool.  _Why does it matter?_  

The careful reader may reason that "citizens" isn't an entirely semantic way to think about pseudolinguistic abstractions dependent on electricity ... What is meant can be thought of more simply: first-class citizens are treated like values.  They have clearance to go anywhere other values can go.  
And for our decorators to work, we need to be able to pass functions as values into the decorating function.  

___  

Decorators are not exclusive to any specific language, to be clear.  One can write a decorator function in JavaScript or Python or another functional language much the same.  As two of the most commonly used modern languages, and two I am at least familiar with, I've chosen JS and Python to demonstrate decorators through code in the examples to come. 
___  

Now that we've sufficiently murked the water with our stirring, let's see if we can clear things up.

___
  
### The decorator pattern can be implemented as follows

The decorator takes a function or functions as it's argument:  

```python
# PYTHON
def decorator(func):
    pass
```  
  
```js
// JAVASCRIPT
function decorator(func) {
    return;
}
```  

> It's important to note that a decorator should return a function (or in some cases, a class).  Our goal is always to extend, transform, or modify another function's ability, and so we must _return_ a function so that we can use it later as a new and improved "decorated" version.

So we'll setup another function inside the decorator's body and return it:
  
```python
def decorator(func):
    # *args allows for a variable number of arguments
    def modifier(*args):
        return func(*args)
    return modifier
```  

```js
function decorator(func) {
    // rest operator allows for a variable number of arguments
    function modifier(...args) {
        return func(...args);
    }
    return modifier;
}
```  
  
> There's a lot going on here, and some of it involves _closure_, which is too rich a topic to indulge intermittently.  One may content oneself with the idea that closures allow our functions to keep track of internal values.  They are packaged up for future use and modification!
  
Our function is now available to the innermost scope so that it can be augmented, modified, or enhanced by the decorator.  Nonetheless, our decorator remains useless.  We need a problem to solve.
  
___

### Pretend Problem

- We need to optimize some functions that perform computationally intensive work.  
- Each function is pure, meaning that, given the same inputs, the function will always produce the same output.
- It is likely that the function will frequently be called with inputs identical to previous calls.

Given these understandings, _memoization_ will be our chosen strategy.  And the decorator pattern turns out to be an elegant choice for implementing it!

In order to properly demonstrate memoization, we need a function that emulates an "expensive operation":

```python
"""
Adds x to itself x times
"""
def cpu_spinner(x):
    values = [x for _ in range(x)]
    return sum(values)
```
```js
/**
Adds x to itself x times
*/
function cpuSpinner(x) {
    return Array.from({ length: x }, (_) => x)
        .reduce((sum, val) => (sum += val), 0);
}
```
> _Note_: One may note that, compared to the javascript implementation, the python code appears overwhelmingly simple.  This may be related to the fact that, being a data science-centric language, Python is in some ways more optimized for math.  

Sooo, we have a couple of ~highly sophisticated~ and super expensive operations.  Now we need to modify our decorator implementations for memoization, allowing the functions to "remember" previous inputs and their respective results.  In both implementations, our cache is a simple hash table that stores the input function's arguments as a key, and the result of the function call as the value for that key:

```python
def memoize(func):
    # Initialize structure to hold previous results
    cache = {}

    def wrapper(*args):
        
        """
        If we've passed these args before, 
        return early with the stored result
        """
        if args in cache:
            return cache[args]
        """
        Otherwise, execute function and store in cache as
        [args]: result
        """
        result = func(*args)
        cache[args] = result
        return result

    return wrapper
```

The JavaScript version's logic is essentially identical, but because we can't store complex objects as keys, we need to stringify the key (or use a JS [Map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map) that can:

```js
function memoize (func) {
  const cache = {}

  function wrapper (...args) {
    const key = args.toString()
    // return early with result if it's stored
    if (key in cache) return cache[key]
    // otherwise store in cache
    const result = func(...args)
    cache[key] = result
    return result
  }
  return wrapper
}
```

Note that these solutions follow the same decorator template we set up previously, albeit with some simple logic in between.  The key here is that the decorator allows the inner function to keep track of a stateful value.  The inner function captures a reference to it's outer, lexical scope, which in this case includes our mutable cache.  This capturing behavior is what is known as __closure__, and it makes possible class-less statefulness and other functional strategies.  

___

_NICE_  

Typically, functions don't need to concern themselves with the context of previous calls.  But in the event that the programmer _requires_ persistence across subsequent calls, as in the case of our memoization strategy, a thorough understanding of closures may prove something of a weapon. 
___  

It's finally time to ~decorate~ our wildly expensive functions.  [since 2004](https://docs.python.org/3/whatsnew/2.4.html), Python has included support for a dedicated decorator syntax.  While JavaScript has not, the underlying principle and application is much the same.  For python, it's a simple matter of annotating the expensive function with `@name_of_decorator_func`:

```python
@memoize
def cpu_spinner(x):
    """
    Adds x to itself x times
    """
    return sum([x for _ in range(x)])
```

For JS, we can accomplish the same thing by simply passing the function we wish to memoize as an argument to the decorator, returning a decorated version of the function to be called later:
```js
const memoizedCpuSpinner = memoize(cpuSpinner);
```

Now, let's make this ~groovy~ experiment even more fun by including yet another decorator function that follows the very same decorator pattern. Don't worry, this one's even simpler than our memo implementation. But instead of memoizing, this final decorator will time the execution of our memoized functions, so we can explicitly see just how effective memoization can be.

For python, we'll have to import the `time` module:
```python
import time

def timer(func):
    """
    Immediately before and after the function call,
    we capture the time and print the difference as `elapsed`
    """
    def wrapper(*args):
        start_time = time.process_time()
        result = func(*args)
        elapsed = time.process_time() - start_time
        print(f"Elapsed: {elapsed:.3f} ")
        return result

    return wrapper
```  
  
>> Before any pitchforks crest my horizon, I should make very clear that the results of my tests are highly subjective and dependent on a wide range of extraneous factors.  But I believe the results, regardless of their inherent imprecision, should _sufficiently_ illustrate the potential power of memoization.  

JavaScript's `console` object should serve just fine for this simple example:

```js
function timer (func) {
  function wrapper (...args) {
    console.time('JavaScript')
    const result = func(...args)
    console.timeEnd('JavaScript')
    return result
  }
  return wrapper
}
```
____

### Execution

Let's tie everything together with a final record of our work, along with several function calls to our decorated functions, fully timer-wrapped and memoized.  We'll also include some print statements necessary for digesting our results.

```python
# *PYTHON
def memoize(func):
    cache = {}
    # Let's add a second stateful value that will track execution count
    count = 0

    def wrapper(*args):
        nonlocal count
        count += 1
        print(f"Execution count: {count}")
        if args in cache:
            print(f"Cached result for {args}: {cache[args]}")
            return cache[args]
        result = func(*args)
        print(f"Uncached result for {args}: {result}")        
        cache[args] = result
        return result

    return wrapper


def timer(func):
    def wrapper(*args):
        start_time = time.process_time()
        result = func(*args)
        elapsed = time.process_time() - start_time

        print(f"Elapsed: {elapsed:.3f} ")
        return result

    return wrapper


# Syntax sugar for passing the annotated function as an argument
@timer
@memoize
def cpu_spinner(x):
    return sum([x for _ in range(x)])


expensive_input = 100_000_000

cpu_spinner(expensive_input)
cpu_spinner(expensive_input)
cpu_spinner(expensive_input)

```

```js
/* JAVASCRIPT */

// This time, for fun, we'll implement a function expression
const cpuSpinner = (x) => 
  Array.from({ length: x}, _ => x).reduce((sum, val) => (sum += val), 0)


function memoize (func) {
  const cache = {}
  let count = 0

  function wrapper (...args) {
    count += 1
    console.log(`Execution count: ${count}`)
    const key = args.toString()
    // return early with result if it's stored
    if (key in cache) {
      const result = cache[key]
      console.log(`Cached results for argument ${key}: ${result}`)
      return result
    }

    const result = func(...args)
    console.log(`Uncached result: ${result}`)
    cache[key] = result
    return result
  }

  return wrapper
}


function timer (func) {
  function wrapper (...args) {
    console.time('Elapsed')
    const result = func(...args)
    console.timeEnd('Elapsed')
    console.log('\n')
    return result
  }
  return wrapper
}

const timedMemo = timer(memoize(cpuSpinner))

const expensiveInput = 100_000_000
timedMemo(expensiveInput)
timedMemo(expensiveInput)
timedMemo(expensiveInput)

```

### Results && Conclusion

The point with our chosen experiment is not the speed of the language itself, nor how the performance of each language compares against the other (neither is designed for speed in general).  The key takeaway concerning memoization is the proof that each subsequent call to the function using the same argument produces its result almost instantaneously. 
The reasons why the Python code outperforms the JS and the reason why the JS still takes a fraction of a second to retrieve a memo-ized value are questions explored in the PostNotes.

#### Python
```python
Call #1
Uncached result: 1e+16
Execution timer: 4,469ms

Call #2
Cached result for argument 1e+8: 1e+16
Execution timer: 000ms

Call #3
Cached result: 1e+16
Execution timer: 000ms
```


#### JS
```js
Call #1
Uncached result: 1e+16
Execution timer: 9,347ms

Call #2
Cached result for argument 1e+8: 1e+16
Execution timer: 306ms

Call #3
Cached result: 1e+16
Execution timer: 442ms
```

All of the redundancies here are meant to drive home the point that memoization is only effective when a function receives input identical to a previous call and that function is entirely free from side effects.  Otherwise, we can't count on the result being the same as the previous call based solely on the input.

We can see that the first function call takes a notable amount of time to finish executing: 4,469ms and 9,347ms for Python and JS respectively.  We can see given the timing of subsequent calls with the same input argument that the result is produced nearly instantaneously by comparison.

It is my hope that, by this point, it is clear why these results can be expected.  If a function is truly pure, we can count on our identical arguments to produce identical results.  So we use closure to keep a record of previous args and their paired output using a hash table which we've called `cache`. Every time the function is called, our memoization decorator checks the hash table to see if the result is already recorded.  If so, the entire operation amounts to a quick lookup in the hash table to retrieve the expected value.

### Bye For Now
For quick reference, a few concepts we explored throughout this experiment:
- [Decorators](https://en.wikipedia.org/wiki/Decorator_pattern)
- [Memoization](https://www.geeksforgeeks.org/what-is-memoization-a-complete-tutorial/)
- [Closure](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Closures)

Thanks so much for reading!  
Stay tuned in to the following section for some random tidbits that didn't make the cut.

As always,
Keep growing!

___
___
___

### PostNotes

> #### _Fun Fact_:
>> I accidentally produced a fatal heap overflow error in Node.js  when I attempted to increase the input by 5x.  I suspect this is related to poor handling of memory by filling an array without a dedicated `range` operator like the one we used in the Python implementation.  If you know of a more efficient way to populate a JavaScript array for experiments of this kind, please let me know!  

And for fun, here's a screen snip of the abbreviated error:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3gvcvauijskqkj8e36w6.png)
___

> #### _Cool Function, dude_
>> Here's a JavaScript version of the memoize decorator that aims to be as concise as possible by leaning all the way into the functional style.  Though not necessarily practical or easy to read, it was groovy and fun to devise:
 
> 1. Anonymize the second function and return it implicitly.
> 2. Pass the cache silently as a default argument, eliminating the need to declare it inside the function body that we no longer have, but still exposing it to the inner function's lexical scope as is necessary for closure.
> 3. Celebrate victory.

```js
const functionalMemoize =
  (func, cache = {}) =>
  (...args) => {
    const key = args.toString()
    if (key in cache) return cache[key]
    const result = func(...args)
    cache[key] = result
    return result
  }
```
___

> #### _Sneaky Snake_
>> The Python implementation of the "expensive function" which I chose somewhat at random came out short, sweet, incredibly readable and relatively fast.  The near-zero execution time seen in the memoized Python results makes sense considering the simplicity of a hash table lookup.  So why the costly calls in the JavaScript version?
Short answer, I don't actually know. 🙃
But when I removed all console logs from the implementation, the results came much nearer to zero.  This suggests that writing to stdio is more expensive in JS than in Python, but this mystery may go the way of the tootsie pop.

For now ...


___
___
___