DEV Community: Denys Potapov

@call_once python macro for unlimited recursion depth

Denys Potapov — Mon, 03 Nov 2025 18:04:01 +0000

I like competitive programming (like Meta Hacker Cup). Where you solve algorithmic puzzles in limited time. In many problems, a recursive solution feels more natural than an iterative one — but Python’s recursion depth limit (usually around 1000) makes it impractical for larger inputs.

So I built a small macro — @call_once — that lets you write recursive functions with virtually unlimited recursion depth.

Example

Let’s take a simple Fibonacci example:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(200_000) % 1_000)

This will crash immediately — Python’s call stack can’t handle that depth.

But with one decorator:

@call_once
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(200_000) % 1_000)

…it runs fine, limited only by memory.

Internals

To achieve unlimited recursion, we simulate the call stack in user space.

The macro rewrites the function’s AST into a continuation-style version.

For example, our fib becomes something like this:

def fib_aux(n):
    if n <= 1:
        return ('result', n)

    fib_n_1_args = (n - 1,)
    if fib_n_1_args not in fib_CACHE:
        return ('call', fib_n_1_args)

    fib_n_2_args = (n - 2,)
    if fib_n_2_args not in fib_CACHE:
        return ('call', fib_n_2_args)

    return ('result', fib_CACHE[fib_n_1_args] + fib_CACHE[fib_n_2_args])

We do two main things:

Check if recursive results are already cached.
If not, return 'call' — meaning we need to compute that subcall.

Main loop

The wrapper function implements the “virtual stack”:

while stack:
    current_args = stack.pop()
    typ, value = fn(*current_args)
    if typ == 'call':
        stack.append(current_args)
        stack.append(value)
        continue
    if typ == 'result':
        cache[current_args] = value

Each frame is just a tuple of arguments.

If the inner call returns 'call', we push its arguments and continue.

This way, recursion happens in our heap-allocated stack, not Python’s C stack — so it never overflows.

The stack also behaves like an ordered set — the same arguments aren’t pushed twice, hence the name call_once.

Performance

To compare, let’s use an iterative Fibonacci:

def fib_fast(n):
    lst = [0] * (n + 1)
    lst[0] = 0
    lst[1] = 1
    for i in range(2, n + 1):
        lst[i] = lst[i - 1] + lst[i - 2]
    return lst[n]

Results (see fib.call_once.py):

fib_fast time:     1.10 seconds, result: 125
@call_once fib time: 1.29 seconds, result: 125

The overhead is small — within ~20%.

But it deserves deeper benchmarking on more complex recursion patterns.

Real-world use case

I first needed this macro during the Meta Hacker Cup 2025, in the problem A2: Snake Scales (Chapter 2).

Problem: facebook.com/codingcompetitions/hacker-cup/2025/round-1/problems/A2

You’re given a list of platform heights, e.g.:

4 2 5 6 4 2 1

Each number is the height of a platform.

You can climb between platforms using a ladder.

You can reach a platform either:

From the ground (ladder length ≥ platform height), or
From a neighbor (ladder length depending on the height difference).

The goal: find the minimal ladder length that allows visiting all platforms.

Recursive solution

We define a helper function min_left(n) — the minimal ladder length needed to reach platform n from the left or ground:

def min_left(n):
    from_ground = A[n]
    if n == 0:
        return from_ground
    dist = abs(A[n] - A[n - 1])
    from_left = max(min_left(n - 1), dist)
    return min(from_ground, from_left)

Then, compute the minimal ladder length overall:

mn = 0
for i in range(len(A)):
    min_from_both = min(min_left(i), min_right(i))
    mn = max(mn, min_from_both)

With @call_once, this works even for arrays of length 100_000 — still within time limits.

Full code: hackercup/a2.py

Summary

@call_once lets you write naturally recursive algorithms in Python without worrying about the recursion limit.

It works by rewriting your function into a manual stack loop that executes calls iteratively, preserving performance close to iterative code.

It’s ideal for competitive programming, graph traversals, dynamic programming, or any case where recursion feels right but Python says “RecursionError: maximum recursion depth exceeded”.

Porting is-odd npm to OCaml using remelange compiler

Denys Potapov — Tue, 01 Apr 2025 16:14:18 +0000

If you've ever worked with JavaScript, you've probably encountered tiny, hyper-focused utility libraries like is-odd. It's a simple function that checks whether a number is odd. But in OCaml, we don’t typically reach for an external library for something this basic.

So why port it?

This post is about demonstrating how we can port an npm library to OCaml using remelange, an experimental JS/TS to OCaml compiler I’m working on. We'll take an existing JavaScript module, compile it to OCaml, and make it available for the OCaml ecosystem.

Why `is-odd`?

Tiny (~20 LOC): Perfect for a quick proof of concept.
Popular npm utility: A real-world example with more than 300k weekly downloads.

Step 1: Understanding `is-odd`

Here’s the JavaScript source of is-odd:

const isNumber = require('is-number');

module.exports = function isOdd(value) {
    const n = Math.abs(value);
    if (!isNumber(n)) {
        throw new TypeError('expected a number');
    }
    if (!Number.isInteger(n)) {
        throw new Error('expected an integer');
    }
    if (!Number.isSafeInteger(n)) {
        throw new Error('value exceeds maximum safe integer');
    }

    return (n % 2) === 1;
};

It:

Uses is-number to check if the input is valid.
Computes Math.abs(value) % 2 === 1 to determine oddness.
Throws an error if the input isn’t a number.

Step 2: Compiling with remelange

Rather than rewriting everything manually, we’ll let remelange generate the OCaml code for us.

Run the following command:

npx remelange is-odd.js > is_odd.ml

This outputs an OCaml version of is-odd.js. Let’s format it for better readability:

ocamlformat --enable-outside-detected-project is_odd.ml

is_odd.ml:

(* COMPILED WITH remelange *)
let is_odd value =
  let n = Int.abs value in
  n mod 2 = 1

Step 3: Generating an Interface File (`.mli`)

If we want to publish this as an Opam package, we should generate an .mli file to define the module’s public API:

ocamlc -i is_odd.ml > is_odd.mli

This creates is_odd.mli:

val is_odd : int -> bool

This makes the library easier to use and type-safe.

Step 4: Using the Generated OCaml Code

Now that we have our is_odd.ml implementation, we can test it:

let () =
  Printf.printf "%b\n" (is_odd 3);
  Printf.printf "%b\n" (is_odd 4);

To compile and run:

$ ocaml is_odd.ml
true
false

Conclusion

This experiment shows that remelange can automate JavaScript-to-OCaml conversions, even for something as simple as is-odd. It also provides a pathway for porting more useful JavaScript libraries into the OCaml ecosystem.

Would you like to see date-fns or lodash next? Let me know!

I’m posting this on April 1st. But hey, maybe someone actually needs is-odd in OCaml. Who am I to judge?

New binary Hadamard-like transform with avalanche effect

Denys Potapov — Thu, 09 May 2024 10:11:53 +0000

In cryptography, the avalanche effect is a property observed in block ciphers and hash functions. This effect ensures that even a slight change in the input, such as flipping a single bit, results in significant changes in the output. Consider the $SHA256⁡\operatorname{SHA256}$ hash function. Given a random input $A$ and its hash $SHA256⁡(A)\operatorname{SHA256}(A)$ , flipping just one bit in $A$ to create $A^{'}$ results in a new hash $SHA256⁡(A′)\operatorname{SHA256}(A')$ that differs from $SHA256⁡(A)\operatorname{SHA256}(A)$ by approximately 128 bits on average:

A = 0x0000000000000000000000000000000000000000000000000000000000000001
A' = 0x0000000000000000000000000000000000000000000000000000000000000003

SHA256(A) = 0x01d0fabd251fcbbe2b93b4b927b26ad2a1a99077152e45ded1e678afa45dbec5
SHA256(A') = 0x91d3827f052f5a4b44d5fe2bed657c752247365d94f80a33cb09c1436a16b125

# Number of different bits (Hamming distance)
DISTANCE(SHA256(A), SHA256(A')) = 126

Finding the P-Transform

During my recreational math practice I thought of transform $P (A)$ , that:

Transforms binary vector to binary vector of same length.
Involutive: $P (P (A)) = A$ ;
Has an avalanche effect similar to that observed in $SHA256⁡\operatorname{SHA256}$ .

This characteristic was hypothesized to potentially weaken the avalanche effect when applied prior to $SHA256⁡\operatorname{SHA256}$ hashing. Although this particular application did not alter $SHA256⁡\operatorname{SHA256}$ robustness as anticipated, the experiment was fun and resulting transform looks somehow beautiful.

Design Basis: The Hadamard Transform

I drew inspiration from the classical Hadamard transform, a well-known mathematical transformation used primarily in signal processing and data compression. The Hadamard transform operates on vectors of real numbers and transforms the input vector into a vector of outputs based on Hadamard matrices. The general equation for the Hadamard transform of a vector $A$ can be expressed as:

H (A) = A \cdot H

Where $H$ represents the Hadamard matrix.

Hadamard transform: the product of a binary vector and a Hadamard matrix $(1, 0, 1, 0, 0, 1, 1, 0) \times H (8) = (4, 2, 0, - 2, 0, 2, 0, 2)$

Adapting to Binary Inputs and Outputs

However, unlike the Hadamard transform which outputs are real numbers, I expect P-transform to produce binary outputs. To adapt the concept to binary inputs and outputs, we define the transform as a matrix product of the input vector with a specially designed matrix followed by taking the result modulo 2. This ensures that the output remains within the binary domain (0s and 1s). The transformation equation thus becomes:

\operatorname{mod} 2

Here, $P$ matrix is constructed to retain the involutive property and the desired avalanche effect.

Constructing P matrix of size 4×4

To construct the $P$ matrix that underpins the P-Transform, we start with a manageable size of 4×4. Our goal is to ensure that the matrix is involutive and that each operation changes about half of the bits in the input, aligning with the desired avalanche effect.
Key Considerations:

Equal Row and Column Sums: We aim for uniformity in the influence each input bit has on the output, meaning each row and each column should sum to the same value.
Simplicity and Symmetry: By reducing the number of variants through symmetry and fixed sums, we can simplify the construction and analysis.

Given these requirements, we manually iterate over all possible 4x4 matrices of 0s and 1s. To streamline this, we focus on matrices that meet our sum criteria and disregard row permutations. This approach leaves us with two primary candidates:

Reversed Diagonal Matrix

[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 1, 0, 0]
[1, 0, 0, 0]

Inverse of Reversed Diagonal Matrix

[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 1, 1]
[0, 1, 1, 1]

We choose to proceed with the Reversed Diagonal Matrix for its simplicity and direct alignment with our criteria.

Expanding P-matrix

To extend this approach to larger sizes, we will apply an iterative process where we construct larger matrices based on the properties established with this 4×4 matrix. We anticipate that each row in a matrix of size $N$ will aim to have sums equal $N /2 - 1$ , thus approaching our goal of altering approximately half of the bits in any input.

To construct an 8×8 P matrix, we use two instances of the 4×4 reversed diagonal matrix we previously determined. These instances are placed in the top-left and bottom-right corners of the 8×8 matrix.

The remaining top-right and bottom-left quadrants of the 8x8 matrix are crucial for ensuring that the row and column sums across the matrix meet our uniformity requirement. Given the setup of the existing 4×4 blocks, each row and column in these quadrants must sum to 2 to maintain the balance.

The simplest solution that meets this requirement is a symmetric arrangement where each quadrant is filled with a pattern that has two '1's per row and column, structured as follows:

[0, 0, 1, 1]
[0, 0, 1, 1]
[1, 1, 0, 0]
[1, 1, 0, 0]

To make it more visual here is a 4×4 and 8×8 matrices:

4×4 and 8×8 P matrices. White pixel corresponds to 1, black — 0

16×16 and 32×32 P matrices

Iterative process generates beautiful self-similar patterns:

512×512 P-matrix

Code and results

I've implemented a sample Python version of the P-Transform, which you can view and download from this GitHub repository.

First we can preview the transform with same numbers as for $SHA256⁡\operatorname{SHA256}$ at the beginning of article:

A = 0x0000000000000000000000000000000000000000000000000000000000000001
A' = 0x0000000000000000000000000000000000000000000000000000000000000003

P_transform(A) = 0x8f000ff0000ffff00000000ffffffff0000000000000000ffffffffffffffff
P_transform(A') = 0x0300000000000000000000000000000000000000000000000000000000000000

# Number of different bits (Hamming distance)
DISTANCE(P_transform(A), P_transform(A')) = 127

Through avalanche effect is close to that of $SHA256⁡\operatorname{SHA256}$ , the transformed vectors look less random than $SHA256⁡\operatorname{SHA256}$ .

Following the aim of this transform I also calculated the average avalanche effect of $SHA256⁡\operatorname{SHA256}$ , $P-transform⁡\operatorname{P-transform}$ and $P-transform⁡\operatorname{P-transform}$ applied before $SHA256⁡\operatorname{SHA256}$ :

Generate random input vector $A$
Flip one bit in $A$ to get $B$
Calculate average distance between $F n (A)$ and $F n (B)$ .

SHA256 Avalanche 127.9851
P_transform Avalanche 127.0
SHA256 + P_transform Avalanche 128.0161

Future work

Self-Similarity of Matrices: Investigating the self-similarity and properties of the underlying matrices in the P-Transform could yield practical applications.
Cryptographic Applications: Exploring the use of the P-Transform as a basis for deterministic length extension in cryptanalysis presents a promising avenue for further research.

npm hack to remove unused transitive dependencies

Denys Potapov — Sat, 09 Sep 2023 13:13:09 +0000

Unused dependencies can be a pain in javascript project. For example your use foo package in your project. And foo package depends on bar package. Sometimes code from bar is unused in your project, but there is no way to remove it.

I've created an empty dry-uninstall package to «solve» an issue with unused transitive dependencies:

{
  "overrides": {
    "foo": {
      "bar": "npm:dry-uninstall"
    }
  }
}

It uses hack in overrides section of package.json to replace bar dependency of foo with an empty index.js:

module.exports = {};

Reasoning

The main reasons why this could help are:

Bundle size. When tree-shaking does not work for some reasons.
Simplified Build. There was a long time when installing mongodb required kerberos package. That itself required to build native add-on modules, and it can be painful.
Security. Replace the vulnerable packages, to be sure that the code is never used.
License Issues.

Sample: Removing momentjs package from simple-node-logger

You've created a minimal project that uses simple-node-logger, simple multi-level logger for console and files:

// index.js
const SimpleLogger = require('simple-node-logger');
const appender = new SimpleLogger.appenders.ConsoleAppender();

const manager = new SimpleLogger();
manager.addAppender(appender);

const log = manager.createLogger();
log.info('this is a simplelog statement');

Check the size of bundle (~383 KB)

    esbuild index.js --bundle --platform=node --outfile=index.dist.js

      index.dist.js  383.7kb

Removing momentjs

Update timestamp format code to remove the momentjs dependency:

// index.js
appender.formatter = function(entry) {
    const fields = this.formatEntry( entry, appender);

    return fields.join( appender.separator );
};
appender.formatTimestamp = (ts) => {
    return ts.toString();
};

Override momentjs with dry-uninstall in package.json

{
  "dependencies": {
    "simple-node-logger": "^21.8.12"
  },
  "overrides": {
    "moment": "npm:dry-uninstall@0.3.0"
  }
}

Check the size of bundle (~241 KB)

    esbuild index.js --bundle --platform=node --outfile=index.dist.js

      index.dist.js  241.7kb

Saved around 140 kb, not bad.