DEV Community: Piyush Chauhan

How I Built a .NET + React Islands Site With a Playwright Snapshot Worker

Piyush Chauhan — Sat, 26 Sep 2026 15:35:31 +0000

Razor owns the pages. React owns a few interactions. A separate browser publishes the finished HTML before anyone visits.

The problem: interactive pages without browser rendering per visitor

Imagine opening /hotels/casa-aurelia. You should get the hotel's description, prices, photos, and metadata in the HTML response. Then, if you click a photo, a gallery dialog should open. A client-only SPA that initially sends a nearly empty shell makes discovery of that content depend on executing JavaScript; rendering Chromium on every visitor request would solve a different problem at a high operational cost. I wanted crawlable first-response HTML and hydration, without either compromise.

This project is a hotel-and-editorial site built with ASP.NET Core 10 Razor Pages, React islands, PostgreSQL, and a Node/Playwright worker. The public site has catalog pages, a journal, search, and a stay inquiry flow—not a reservation or payment system. Its editors have a separate protected React admin. The awkward part is that the public gallery and other islands begin as empty markers in Razor: rendering only Razor would ship the page content but not the gallery's initial HTML.

My solution was to move browser execution to publication time. Razor generates the source document; a background Chromium process mounts its islands, validates the result, and saves the completed HTML in PostgreSQL. The public gateway serves that saved document. The visitor's browser hydrates the already populated islands for interaction. This is browser-rendered React at publication time, not React server-side rendering in .NET, and Chromium is not on the visitor request path.

Who owns what?

The architecture becomes easier to reason about when each layer has a narrow job:

Owner	Responsibility	What it does not own
ASP.NET Core Razor Pages	Public routes, catalog and article content, HTML shell, SEO title, description, canonical links, structured data, and no-JS results	React's interactive state
React islands	Search/date controls, gallery, mobile navigation, and inquiry form interaction	Public-page routing or the catalog's canonical HTML
React Router admin	Protected editor UI behind the server's document guard and APIs	Public visitor routes
PostgreSQL	Catalog, snapshot jobs, and published HTML	Browser rendering
Playwright worker	Off-request source-page capture, validation, and conditional publication	Serving a visitor request

The distinction between content and controls matters. Razor writes the hotel heading, text, cards, and inquiry link. It also renders search results and GET-based sort/pagination so those remain useful without JavaScript. React adds the gallery dialog and richer search controls; those controls do need JavaScript. The admin is deliberately different: it is a protected React Router SPA, not an island pretending to be a public page.

This arrangement does not claim that every part of the site works without JavaScript. It makes the public content and search-results path independently useful while treating interactive controls as an enhancement with an explicit dependency.

One request, two paths

A canonical public GET or HEAD—such as /hotels/casa-aurelia, a journal post, or bare /search—passes through the snapshot gateway. It looks up a published HTML document by path. The document already includes Razor content and the gallery markup produced by Chromium. Only after delivery does the visitor's React runtime attach behavior.

flowchart LR
    V[Visitor GET /hotels/casa-aurelia] --> G[ASP.NET snapshot gateway]
    G --> P[(PostgreSQL published HTML)]
    P --> H[HTML with populated islands]
    H --> B[Visitor browser hydrates controls]
    Q[Filtered /search?..., inquiry, admin] --> L[Live private server route]
    L --> R[Dynamic response, not public snapshot]

The second path is not an exception hidden behind a cache key. /search?destination=... is a live Razor result page with private, no-store and noindex,follow; the bare /search page is eligible for a canonical snapshot. Inquiry pages and submissions, admin documents, and APIs are live/private, not publicly cached snapshot variants. This keeps a filter query, a guest's inquiry, or an editor session out of the shared HTML store.

The gateway returns persisted HTML with Cache-Control: public, max-age=60, stale-while-revalidate=300. That policy also sets the limit on how quickly an already cached public page may reflect an edit. It is a deliberate tradeoff, not instant global invalidation. In non-snapshot development mode the same canonical Razor pages can be served live; the diagram describes the snapshot-enabled delivery path.

How an island becomes published HTML

Razor emits an island marker and JSON props. Here is the gallery marker excerpt from the hotel page:

<div data-island="Gallery" data-hydrate="visible"
     data-props="@(PublicPageModel.IslandProps(new
     {
         name = hotel.Name,
         items = stay.Gallery.Select(x => new
         {
             x.Id, x.Src, x.Alt, x.Caption, x.Category, x.RoomId
         })
     }))"></div>

_Layout.cshtml likewise supplies the shared MobileNav marker and the runtime script, and owns the document's metadata. The marker above is empty in the Razor source. data-island selects a dynamically imported component; data-props passes its serialized input; data-hydrate="visible" tells the visitor runtime that it can defer mounting until near the viewport.

The worker visits /_snapshot-source?path=/hotels/casa-aurelia with a private token. That route only delegates to Razor for an allowed canonical path that has a job or an existing snapshot. On the protected source page, the island runtime mounts all markers, even normally deferred ones. When every mount's effect has run, it sets window.__SNAPSHOT_READY__. Playwright waits for that signal and for successful browser execution before serializing the document. It rejects invalid documents rather than saving a partial render: among its checks are the canonical path, exactly one h1, populated islands, the expected runtime script, absence of private-form inputs and the token, and browser errors. It also strips Chromium-added Vite modulepreload hints and inserts separators between adjacent island text nodes so the saved HTML can hydrate correctly.

On a visitor's request, this HTML already contains a gallery grid inside the same marker. The runtime checks whether the marker has child markup. Its essential choice is:

// Excerpt from the public island runtime; Ready wraps the imported component.
if (marker.children.length > 0) hydrateRoot(marker, createElement(Ready))
else createRoot(marker).render(createElement(Ready))

hydrateRoot attaches to captured markup; createRoot fills an empty marker in live Razor development or another uncaptured context. Visitors defer visible islands with IntersectionObserver (with a near-viewport margin), whereas the source-page capture mounts them eagerly. There is no duplicate static gallery fallback sitting beside a second React gallery. Without JavaScript, the published gallery grid and Razor text are still present, but its dialog and other island controls will not work.

This is testable as behavior, not just a design sketch. The repository's tests/e2e/hydration.spec.ts reads the published hotel HTML and finds one .gallery-grid inside the gallery island with no duplicate fallback. It then loads that hotel page, opens a gallery image, advances to the next photo, and closes the dialog. The static representation survives delivery and the same representation gains interaction.

Publishing without serving stale work

The worker needs a precise answer to a race: what if an editor changes the hotel again while Chromium is rendering the first change? Saving that first render afterward would roll the public page backward.

flowchart LR
    A[Admin edits catalog] --> T[One DB transaction: content + affected jobs]
    T --> J[(Versioned snapshot jobs)]
    J --> W[Worker leases due job]
    W --> S[Token-protected Razor source]
    S --> C[Chromium mounts islands; waits; validates]
    C --> X{Job version still current?}
    X -- Yes --> P[Atomic HTML upsert + job removal]
    X -- No --> D[Discard obsolete capture]
    P --> G[Gateway serves published HTML]

Admin publication and affected-route invalidation share a database transaction. Editing a hotel can affect its own route, destination listing/detail, bare search, home page, offer pages, and published articles that embed catalog records. Renames include old paths. A route that is no longer published loses its snapshot and job immediately rather than retaining discoverable old HTML. Valid published routes get a new desired job version.

The worker leases due jobs using PostgreSQL FOR UPDATE SKIP LOCKED, renders the protected Razor source in its own Chromium context, and checks the job's current desired version under a row lock before inserting/updating the HTML and deleting the job in one transaction. If the version changed, it discards the obsolete capture. Errors never publish a partial document: the job is released and retried with exponential backoff. The old complete snapshot stays available while a published route is regenerated.

A first-time canonical path has no old document to serve. If it is queued, the gateway responds 503 with Retry-After: 5 until publication succeeds. Unknown or unpublished detail routes return 404 (the fixed canonical index routes can return 503 while their first capture is pending). Once a route is unpublished or renamed, its persisted HTML is removed immediately; already cached copies may still live for the declared cache window, so publication and caching policy must be understood together.

What must never be snapshotted

The easiest way to leak private data would be to treat the snapshot store as a generic response cache. It is not. Its key is a canonical public path, not arbitrary combinations of query string, cookies, authentication, or POST body. Filtered search remains a live private response. The inquiry flow carries personal input, is CSRF-protected, and must remain private. Admin sessions and protected API responses cannot become public snapshots either.

The source endpoint is also a security boundary. It requires a sufficiently long SNAPSHOT_INTERNAL_TOKEN, compares the supplied header, rejects unrecognized canonical routes, sends private, no-store and noindex, and should be blocked from the public ingress as well. A robots directive alone would not secure it. The worker restricts fetched resources to its configured API origin and validates the captured result before publication; neither check replaces proper network isolation and authentication.

The worker rejects a source document containing password or antiforgery inputs, a token string, unexpected executable scripts, missing canonical metadata, unrendered islands, or browser errors. These checks are a publishing guard, not a blanket proof that arbitrary application data is safe to cache. The safe baseline remains an explicit allowlist of canonical public routes and a separate live/private path for anything user-specific.

The SEO advantage over a client-only SPA

A client-only SPA can be indexed by search engines that render JavaScript, but its initial HTML may contain little more than an app root. Content discovery then depends on fetching and running scripts successfully; rendering can be delayed or missed by crawlers that do not execute them. A React SPA with SSR or prerendering does not have that limitation by definition. The comparison here is with a client-rendered shell, not with all SPAs.

For a published hotel URL, a crawler's first HTML response already contains the hotel heading, description, links, gallery markup, and metadata. It does not have to execute React to discover the principal content. Razor provides the page-specific title and description, a canonical URL, and Hotel JSON-LD; the worker preserves these in the published document. The gateway generates robots.txt and an XML sitemap of catalog-published canonical routes. When a route is unpublished, it is removed from that sitemap and its stored HTML is deleted. Bare /search is canonical; filtered search URLs specify noindex,follow to avoid indexing many query variants. Inquiry and admin documents are marked noindex and are not public snapshots.

This is the outcome I like about prerender-then-hydrate designs: content is present before client JavaScript, while controls become interactive after hydration. It shares that goal with several other rendering strategies, but the publication boundary here is different.

The concrete SEO benefit is a more reliable path for crawlers to discover and assess canonical content, links, and metadata. It is not a guaranteed ranking. A sitemap is a discovery hint, structured data does not guarantee a rich result, and an indexable response does not mean a search engine will index or rank it. A newly queued URL returns 503 until its first capture; finish publication before directing production traffic or crawlers to it. After an origin change, wait for republishing and check the actual canonical URLs in the returned HTML: PUBLIC_ORIGIN is embedded at capture time. Old cached pages can also persist briefly after an edit or removal.

Lighthouse audits the loaded page, so it is not a direct test of what a no-JavaScript crawler sees. Here, the first response already exposes content and metadata, while off-request publication avoids Chromium work on the visitor path; both are useful starting conditions. But a high Lighthouse performance score is not automatic: React chunks, CSS, images, fonts, server/cache behavior, hydration work, and audit settings still affect LCP, CLS, and interactivity. Deferred visible islands and removal of captured modulepreload hints can reduce unnecessary upfront work. Audit the published snapshot, not Vite HMR: the repository documents make lighthouse-https for a local HTTPS run and pnpm lighthouse for its desktop preset. Compare repeated runs under the same conditions and inspect the generated HTML, canonical, robots directives, sitemap, and metric breakdown rather than quoting a single score.

How SSR, SSG, ISR, and PPR compare

These names describe when and where HTML is produced, not whether React can hydrate it. Each can ship crawlable HTML when configured to render the actual public content. The useful question for this site was where to pay the rendering cost and how to update edited catalog pages.

Strategy	When HTML is produced	Advantage	Cost or mismatch for this site
SSR (server-side rendering)	On each request, potentially cached afterward	Fresh request-specific data; a natural fit for personalized search or inquiry pages	Uncached rendering and data access add request-path work; cache keys and private data need care
SSG (static site generation)	At build time	Simple, fast delivery of already complete public HTML	Catalog edits or new pages need a rebuild and redeploy unless another regeneration mechanism is added
ISR (incremental static regeneration)	Initially prerendered or generated on demand, then regenerated after revalidation	Reuses HTML between visits and can refresh without rebuilding the whole site	Refresh policy and stale windows must be managed; in the common request-triggered model, regeneration waits for traffic
PPR (Partial Prerendering)	Static shell prepared ahead of time; dynamic regions render and stream at request time	Static content can arrive early while request-specific regions stay dynamic	More per-request rendering and cache-boundary coordination than these wholly public canonical documents need
This site's snapshot publication	Razor source plus browser-mounted islands captured for queued paths after catalog edits or release changes, then stored in PostgreSQL	Full public HTML and hydrated controls, with no Chromium on visitor requests; versioned jobs can target affected routes	Publication delay, first-capture `503`, and a database/browser worker to operate; private routes still need live rendering

The closest analogy is ISR's last-good HTML while regenerating, not an identical implementation. This worker queues affected paths when editors publish, captures eagerly in the background, and discards a capture if its desired version changed. It does not wait for a visitor or a timer to trigger regeneration. PPR is also not what happens here: the canonical snapshot is a complete shared document, not a static shell with request-time streamed islands. The project's filtered search and inquiry pages use live Razor responses instead. Next.js describes ISR's request-triggered revalidation and its static-shell/streamed-region model; those are comparisons, not dependencies of this .NET implementation.

Tradeoffs and running it

The split removes Chromium from visitor latency, but adds a publication pipeline. An edit can take time to appear; a new page waits for its first successful capture. If the worker, Chromium, or PostgreSQL is unavailable, publication stalls even while an old complete snapshot may continue to be served. No performance score or SEO result follows automatically from this architecture: measure the deployed site and audit the generated document.

Locally I use two different modes from the repository root:

pnpm dev             # Live Razor pages and Vite HMR; no snapshot worker required
pnpm dev:snapshots   # Build Vite manifest; run .NET plus continuous worker

The production-like mode needs PostgreSQL, a valid internal token, and Playwright Chromium; the quick-start guide covers initial setup and seeding. When it first starts, a new canonical route may answer 503 until captured. Failed jobs back off rather than writing half a page, so a persistent 503 is a reason to inspect worker logs and the snapshot job table—not to bypass the gateway.

Deploy the API and worker from the same release: the worker's asset fingerprint includes the Vite manifest, relevant source files, and PUBLIC_ORIGIN. A changed fingerprint requeues stored pages; changing PUBLIC_ORIGIN matters because canonical links are embedded in HTML. Keep old hashed assets available while old snapshots still reference them, and restart a running API after rebuilding its manifest in snapshot mode. Otherwise an intact stored page can point at a chunk the server no longer serves. These are operational costs of publishing HTML with client-side hydration rather than computing every page on demand.

The design rule I kept

Give the public document a single owner and give interactivity a clear boundary. Here, Razor defines the public page and its metadata; a background browser completes its islands once for publication; React hydrates that exact markup for visitors. The protected admin and user-specific flows never cross into the public snapshot store.

That buys immediately useful content without putting Chromium on each request. It also makes the limitations visible: editorial publication delay, a PostgreSQL-and-browser worker to operate, JavaScript required for controls, and strict route/cache/security boundaries. For this site, those are easier to reason about than making the entire public experience depend on a client-rendered shell or hiding a browser render in the request path.

Github: https://github.com/piyushchauhan2011/dotnet-islands

Integration Is the Product: Platform Engineering for Fast Frontend Teams

Piyush Chauhan — Sat, 12 Sep 2026 13:26:14 +0000

How local composition, exact artifacts, and versioned releases turn a dependency queue into continuous feedback.

The useful measure of team autonomy is not “can it publish?” It is “how quickly can the team see its exact change running in a realistic product?”

A frontend package can compile, test, and publish successfully—and still break when the product shell owns routing, authentication, server-side rendering (SSR), hydration, global styles, middleware, or a singleton dependency such as React.

I learned this through a familiar local loop:

build package → pnpm pack → edit the shell's package.json → install → run → discover → repeat

That loop proves the product boundary matters. It is also a warning: integration has become manual, temporary state leaks into committed files, and every cross-team change waits for the central application to catch up.

The answer is not “never integrate” or “put everything in a monorepo.” The answer is to make integration a self-service product capability: composable locally, verified as an artifact, previewable in a pinned product, and promotable as an immutable release.

The model in one picture

Each loop answers a different question. Do not make the slowest one the default.

Loop	Question it answers	Default use	Evidence it produces
1. Domain workbench	Does the domain feature behave correctly?	Daily implementation	Fast, deterministic UI and contract feedback
2. Local product composition	Does my source work in the real shell?	Host-boundary changes	Routing, auth, SSR, hydration, styling feedback
3. PR product preview	Does the artifact I intend to ship work in a clean product?	Before merge	A reviewable URL using exact candidate bytes
4. Versioned release	Is this selected composition healthy under shared and production conditions?	Promotion	Canary and operational evidence

The important design rule:

A failure found in an outer loop should improve the cheapest inner loop that can catch it next time.

Some failures—real traffic, irreversible migrations, external side effects—belong in the outer loop. Pretending every risk can move left makes local feedback less trustworthy, not more.

A concrete example: the Booking module

Assume a Booking frontend module mounted in a product shell. It calls Hotel APIs, participates in auth and routing, emits booking events, and server-renders UI.

Here are the four boundaries where its “green” isolated build can still fail:

┌──────────────────┐    ┌────────────────────────┐
│ Booking package  │───▶│ Product shell          │
│ exports, assets, │    │ routing, auth, SSR,    │
│ peer dependencies│    │ hydration, CSS         │
└────────┬─────────┘    └──────────┬─────────────┘
         │                         │
         ▼                         ▼
┌──────────────────┐    ┌────────────────────────┐
│ Domain contracts │    │ Environment and data   │
│ Hotel API/events │    │ pinned versions, known │
│ errors, timing   │    │ scenarios, replayable  │
└──────────────────┘    └────────────────────────┘

1. Build and artifact boundary

Local linking can succeed while the published tarball omits types, CSS, assets, compiled files, or an export-map entry. It can also hide bad peer-dependency resolution.

A particularly expensive frontend failure is a duplicate singleton: Booking bundles React or framework context while the shell expects to own it. Hooks, contexts, or hydration then fail only in the composed application.

Design consequence: support fast local source overrides and install the packed artifact into a clean shell in CI. Neither replaces the other.

2. Platform and runtime boundary

A mini-shell is valuable, but it is not the product. The real shell may resolve auth asynchronously, evaluate flags on the server, enforce CSP, select locale, apply global CSS, and hydrate browser markup.

A synchronous fake user can hide a lifecycle race. A window access can pass locally and fail during SSR. A global selector can quietly override the product header.

Design consequence: teams need an easy route into the real shell before release—not a handoff to another team.

3. Domain contract boundary

Types alone are not contracts. A Hotel response can make a field optional; an event can be duplicated; a shared package can preserve its type while changing runtime behavior.

Design consequence: contracts need examples for absence, errors, timeout, compatibility, and delivery semantics. Providers own valid fakes; consumers own the assumptions they make.

4. Environment and data boundary

A shared environment called dev is usually a location, not a reproducible state. It may contain yesterday’s Hotel build, today’s Payment candidate, mutable test accounts, and an unannounced shell change.

Design consequence: pin composition and provide named, deterministic data scenarios. A passing result should be attributable; a failure should be replayable.

The paved road: two local modes, one composition contract

The productive workflow is not “fake everything” versus “run the whole company.” It offers two intentionally different local modes.

Mode A: domain workbench

The workbench mounts local Booking with the production rendering mode, design system, route contract, and named auth, flag, and locale scenarios. Hotel and Payment provide provider-owned fakes; inexpensive, behaviorally important infrastructure can run locally.

platform dev

Use it for focused work. It should be fast, deterministic, usable offline where practical, and let an engineer select success, absence, timeout, error, and authorization states in one command.

Mode B: real-shell composition

The real product shell runs with released dependencies while the developer substitutes only local Booking source and gets HMR.

platform dev --composition=integration-stable

Use it when the change touches routing, auth lifecycle, SSR/hydration, global CSS, middleware, or framework ownership. It removes the pnpm pack / edit-manifest / reinstall loop without claiming to prove the tarball.

Both modes resolve the same composition contract. The interface can be a CLI, package-manager feature, dev server, container stack, or managed environment; the durable part is the input and output:

composition: integration-stable@sha256:8f1e...
shell: product-shell@13.2.1
modules:
  booking:
    mode: local-source
    path: ../booking
    watch: true
  hotel:
    mode: integration-stable
    version: 5.8.2
  payment:
    mode: fake
    scenario: authorized
scenarios:
  auth: signed-in-customer
  locale: en-GB
data:
  booking: local-isolated

A good platform dev command does four things before it starts:

Resolves peer, shell-API, rendering-mode, and contract compatibility.
Leaves the application’s normal package.json and lockfile untouched.
Watches only explicit local overrides; released components remain immutable.
Prints the resolved versions, modes, paths, scenario IDs, and manifest digest.

That last point matters. “Works on my machine” is useful only when “it” has an identity another developer or CI job can reproduce.

Useful companion commands are straightforward:

platform preview  # create or show this change's pinned preview
platform trace    # inspect correlated diagnostics
platform doctor   # explain peers, credentials, ports, versions, dependencies
platform reset    # remove generated state; never normal project files

Let contracts unblock implementation—not conversation

Composition accelerates feedback after code exists. Contracts solve the earlier scheduling problem: how can Booking start when Hotel is not finished?

The teams still need to agree on meaning. The goal is to turn that agreement into a versioned candidate someone can consume immediately.

For a cancellable reservation hold, the sequence is:

Agree on the smallest useful contract. Request, response, errors, idempotency, timeout expectations, and representative examples.
Publish a provider-owned candidate. Hotel ships the contract plus valid fixtures, fake adapter, or mock server under an immutable candidate ID.
Implement the consumer against it. Booking exercises success, absence, timeout/error, and compatibility scenarios in the workbench.
Verify the provider against the same agreement. Hotel’s CI verifies the implementation. Consumer-driven contracts can run concrete consumer expectations before merge; Pact is one option.
Compose both candidates. The preview pins Booking and Hotel candidates for product-level review.
Keep a declared compatibility window. Support current and previous versions unless an exception is explicit and time-bounded.

semantic decision
        │
        ▼
provider contract candidate ──────▶ consumer implementation
        │                                      │
        └──── provider verification ◀──────────┘
                         │
                         ▼
               pinned combined preview

This separates a necessary semantic dependency from an avoidable implementation dependency. Contract verification does not prove assembled-product behavior, so the combined preview remains necessary.

Test the bytes you will release

Source composition is for speed. Artifact verification is for release confidence.

Before merge, CI should:

build once → pack once → attach commit and provenance → clean install into pinned shell → test → preview

For a Node package, pnpm pack produces the tarball under test. The clean shell install should verify exports, included files, types, assets, lifecycle behavior, package metadata, SSR/hydration where relevant, and only the critical product journeys affected by the module.

The artifact that passes is the artifact that moves forward. Rebuilding for staging or production invalidates prior evidence.

The shell owns singleton dependencies such as React, framework runtimes, and shared contexts. Modules declare supported ranges through peerDependencies rather than bundling private copies. A compatibility manifest adds constraints package resolution cannot express—such as supported shell APIs, rendering modes, or contract generations—and fails an invalid composition with an explanation before it runs.

Provenance answers a different question: which source revision and CI build produced these tested bytes? It complements, rather than replaces, compatibility testing.

Preview a product, not an isolated copy of the company

A PR preview should be a hybrid composition:

dedicate the changed Booking candidate and shell where needed;
reuse known-stable Hotel, Payment, and other remote services;
pin every reused version;
expose the final composition and artifact IDs in the preview.

This gives QA, design, and product a reviewable URL without creating a full company clone for every pull request. It catches artifact omissions, clean-install failures, selected cross-domain behavior, and visual product issues. It still has bounded data, traffic, scale, and external integrations—so it is strong evidence, not a production guarantee.

GitOps gives promotion a memory

A composition is already declarative, so GitOps is useful connective tissue between verified bytes and running environments. It does not “solve integration”; it records, applies, and reconciles a selected product state.

composition: booking-canary-2026-09-12
shell: product-shell@13.2.1
components:
  booking:
    artifact: registry.example/booking@sha256:4d8c...
    version: 7.5.0
    sourceCommit: 91ac...
    buildProvenance: attestations/booking/4d8c...
  hotel:
    artifact: registry.example/hotel@sha256:70be...
    version: 5.8.2

candidate artifact → composition-manifest PR → verification + preview
    → merge → reconciled environment → canary → manifest revert if unhealthy

This aligns with the OpenGitOps principles: desired state is declarative, versioned and immutable, automatically pulled, and continuously reconciled.

Keep environment semantics distinct:

Environment	Purpose	What may change it?
`integration-latest`	Early compatibility signal from accepted updates	Accepted component updates
`integration-stable`	Dependable baseline for local hybrid development	Deliberate known-compatible promotion
staging / release candidate	Release evidence	Deliberately selected manifest only
production	Real customer and traffic evidence	Canary promotion of a reviewed manifest

Routine deployments must not mutate staging. Otherwise it becomes contested shared workspace exactly when it needs to represent a release candidate.

A manifest revert restores the prior artifact digest. It cannot reverse destructive migrations or external side effects, so every module still needs a forward- and backward-compatible migration strategy.

Make failure attributable in one screen

Pinning versions is necessary but incomplete. Reproducibility also needs data and diagnostics.

A provisioned Booking scenario should have a testRunId, TTL, and cleanup policy. Records across Booking, Hotel, and Payment carry that identifier where permitted. Stable fixtures are immutable or automatically reset; tests needing mutation receive isolated data.

Requests and events should propagate trace and request IDs plus:

module version · product composition ID · contract version · testRunId

OpenTelemetry provides the trace and context-propagation model. Adding composition context makes a trace actionable integration evidence.

A failed Booking request should answer:

Which Booking artifact and product composition handled it?
Which Hotel contract and service version were selected?
Which test scenario supplied the data?
Where did time or failure enter the trace?
Which team owns the failing capability and what changed last?

Ownership then follows the boundary: Booking triages a failure in its artifact; Hotel owns a published-contract violation; the platform team owns a composition engine rejection of a valid declared configuration. A bare failure routed to a team channel recreates the integration queue.

Start small: improve one developer journey

Do not begin by building a universal portal. Begin with the most painful edit-to-integrated-feedback loop and give it a measurable exit condition.

Stage	Deliverable	Exit condition
1. Make composition explicit	Pinned shell/module versions, clean artifact install	Any authorized engineer can reproduce a candidate from clean state without editing `package.json`.
2. Shorten local feedback	Workbench, named scenarios, real-shell local overrides	One command reaches a usable shell while the normal lockfile remains unchanged.
3. Move compatibility before merge	Candidate contracts, packed-artifact CI, hybrid preview	CI installs exact candidates into a clean pinned composition and reviewers can identify every changed/reused component.
4. Close the production loop	GitOps manifests, canary, trace metadata, ownership routing	The PR-tested artifact reaches canary/production unchanged and a safe revert restores the prior compatible version.

Measure the wait, not the tooling:

median edit-to-feedback time, separately for workbench and real shell;
percentage of PRs verified with the exact artifact later promoted;
local composition startup success rate, not just process starts;
preview request-to-ready and recovery time;
failures found before versus after merge, classified by boundary;
dependency-update lead time and blocked days caused by cross-team dependencies;
deployment failure/recovery outcomes and observed developer task success.

DORA’s delivery metrics are useful alongside these leading indicators. Do not turn them into a cross-team leaderboard: trends for one product journey reveal more than a blended organizational number.

Integration is the platform product

A weak platform makes teams publishable, then centralizes the moment of truth. A healthy platform makes the product boundary continuously available to the team changing it.

For Booking, that means one connected path:

local source in real shell
  → exact packed candidate in clean CI
  → pinned PR preview
  → reviewed composition manifest
  → canary with traceable identity
  → manifest revert when healthy evidence disappears

Packages, separate repositories, and independent releases can all support this model. The decisive capability is faster, self-service feedback at progressively realistic levels—not the repository topology or a portal.

Integration is not the gate after development. Integration is the product the platform team provides.

References

Graph Coloring: A Simple Implementation with JavaScript

Piyush Chauhan — Tue, 08 Sep 2026 17:04:14 +0000

Introduction

Graph coloring is a fundamental problem in computer science and graph theory, often used to solve various real-world problems such as scheduling tasks, register allocation in compilers, and solving map coloring puzzles. In this article, we will explore how to implement a simple graph coloring algorithm using JavaScript.

What is Graph Coloring?

Graph coloring involves assigning colors to the vertices of a graph such that no two adjacent vertices share the same color. The goal is to use the minimum number of colors required to achieve this condition.

Example: Map Coloring

A classic example is map coloring, where countries (vertices) are colored so that no two adjacent countries have the same color. This ensures that maps can be visually distinguished and avoids confusion between neighboring regions.

Implementation in JavaScript

We will implement a graph coloring algorithm using JavaScript objects to represent the graph structure and perform depth-first search (DFS) for coloring.

Step-by-Step Guide

Graph Representation:
- We will use an adjacency list representation of the graph.
Color Assignment:
- We will use DFS to assign colors while ensuring no two adjacent vertices share the same color.
Conflict Detection:
- We will detect conflicts and return false if a valid coloring cannot be achieved.

JavaScript Code

Here's the complete implementation:

// Function to perform the graph coloring using DFS
function dfs(graph, vertex, visited, colorMap) {
    // If the vertex is already colored, return true
    if (colorMap[vertex] !== undefined) return true;

    // Initialize with a default color
    colorMap[vertex] = 0;

    for (let neighbor of graph[vertex]) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            if (!dfs(graph, neighbor, visited, colorMap)) {
                return false; // Conflict found
            }
        } else if (colorMap[neighbor] === colorMap[vertex]) {
            return false; // Conflict found
        }
    }

    // Assign the next available color
    colorMap[vertex] = 1;

    return true;
}

// Function to perform graph coloring on the entire graph
function graphColoring(graph) {
    const visited = {};
    const colorMap = {};

    for (let vertex of Object.keys(graph)) {
        if (!visited[vertex]) {
            visited[vertex] = true;
            if (!dfs(graph, vertex, visited, colorMap)) {
                return false; // Conflict found
            }
        }
    }

    console.log("Coloring scheme:", colorMap);
    return true;
}

// Example usage:
const graph = {
    A: ['B', 'C'],
    B: ['A', 'D'],
    C: ['A', 'D', 'E'],
    D: ['B', 'C', 'E'],
    E: ['C', 'D']
};

if (graphColoring(graph)) {
    console.log("Graph is colored successfully!");
} else {
    console.log("Conflict found in graph coloring.");
}

Explanation

dfs Function:
- This function performs a depth-first search to assign colors.
- If the vertex has already been assigned a color, it returns true.
- It initializes the color map for unvisited vertices and recursively assigns the next available color while checking for conflicts.
graphColoring Function:
- Initializes visited and colorMap arrays.
- Iterates over all vertices in the graph and calls dfs for unvisited vertices.
- If a conflict is found during the DFS, it returns false; otherwise, it prints the color map.

Example Graph

Let's consider the example graph:

Vertices: A, B, C, D, E
Edges: A-B, A-C, B-D, C-D, C-E, D-E

The output will be a valid coloring scheme for this graph if one exists.

Conclusion

In this article, we explored how to implement a simple graph coloring algorithm using JavaScript. By representing the graph as an adjacency list and performing depth-first search, we can efficiently assign colors while ensuring no two adjacent vertices share the same color.

Navigating Python Development: A Step-by-Step Guide to Using Poetry

Piyush Chauhan — Tue, 08 Sep 2026 17:03:46 +0000

What is Poetry?

Poetry is an opinionated package management system for Python projects. It helps you:

Set up your project with all the necessary files.
Manage dependencies easily.
Isolate environments to ensure that different projects have separate dependencies.
Resolve dependency conflicts automatically.

Why Use Poetry?

Simplifies Project Setup: Automatically generates pyproject.toml and poetry.lock files, making it easier to share your project with others.
Environment Management: Creates isolated virtual environments for each project, which helps avoid version conflicts.
Dependency Resolution: Automatically handles dependencies and their versions, reducing the risk of issues related to dependency mismatches.

Installing Poetry

You can install Poetry using pip:

pip install poetry

Creating a New Project with Poetry

Open your terminal or command prompt.
Navigate to the directory where you want to create your project.
Run the following command to create a new Python project:

   poetry new my_project

This will create a new directory named my_project with the following structure:

my_project/
├── pyproject.toml
└── src/
    └── my_project/
        ├── __init__.py
        └── main.py

Managing Dependencies

Add a Dependency: You can add dependencies to your project using the add command:

   poetry add requests

List Installed Dependencies: To see all installed dependencies, use:

   poetry show

Update a Dependency: To update an existing dependency, use:

   poetry update requests

Remove a Dependency: To remove a dependency, use:

   poetry remove requests

Managing Environments

Activate the Environment: Run the following command to activate your project's virtual environment:

   poetry shell

Deactivate the Environment: Simply type exit in the activated shell.

Running Scripts

You can run scripts from within a Poetry-managed environment by using the poetry run command:

poetry run python src/my_project/main.py

This runs main.py with the virtual environment's Python interpreter.

Summary

Poetry is a powerful tool for managing Python projects. It simplifies dependency management, ensures isolated environments, and helps resolve version
conflicts. By following these steps, you can effectively use Poetry to manage your Python projects.

The browser only talks to one server — composing Marko, React, and Riot into one hotel page

Piyush Chauhan — Mon, 07 Sep 2026 12:32:03 +0000

You open a hotel page. It looks like one product: a search grid, a featured stay, local highlights, reviews, a sticky trip summary.

Under the hood it is eight HTTP servers and three UI runtimes.

That is the experiment behind HarborStay, a demo booking app I built to answer a stubborn question:

Can independent teams ship independent UI, in independent frameworks, and still give the browser a single, paint-ready HTML page?

The punchline: yes — if the shell never imports a component. It only fetches HTML.

The one rule

The browser never talks to a fragment.

It talks to the composer on port 3100. The composer owns routes, layout, and the booking flow. Everything else is a fragment server that returns a chunk of HTML.

flowchart LR
  Browser["Browser"] --> Composer["Composer :3100"]

  subgraph fragments["Fragment servers"]
    Nav["Navigation Marko :3101"]
    Search["Hotel search Marko :3102"]
    Details["Hotel details Marko :3103"]
    Reviews["Reviews Marko :3104"]
    Recs["Recommendations Marko :3105"]
    Highlights["Local highlights React :3106"]
    Disco["Experiences discovery Riot :3107"]
    Itin["Experiences itinerary Riot :3108"]
  end

  Composer --> Nav
  Composer --> Search
  Composer --> Details
  Composer --> Reviews
  Composer --> Recs
  Composer --> Highlights
  Composer --> Disco
  Composer --> Itin
  Composer --> CDN["CDN :3200"]

This is the opposite of the usual microfrontend story (Module Federation, shared React, a host that import()s widgets). HarborStay is HTML composition. The shell does not know whether a fragment was rendered by Marko, React, or a hand-rolled Riot string. It only knows a URL.

That one constraint buys a lot:

Fragment teams can pick a runtime without asking the shell.
A fragment outage becomes a fallback box, not a blank page.
You can deploy search without redeploying reviews.

It also forces honesty. If two fragments need to share a Redux store, the architecture is already leaking.

What the user actually sees

HarborStay models a small premium catalog: Harbor View Lodge in Lisbon, Copper Hill Suites in Seville, Sunset Terrace House in Barcelona, Moss & Lantern in Copenhagen.

Routes the composer owns:

Route	What you get
`/` and `/hotel/:hotelId`	Streaming stays page
`/experiences/:hotelId`	Neighborhood explorer + day plan
`/booking/confirm/:hotelId`	Confirmation (I got `HS-470455` for Moss & Lantern)

On /hotel/moss-lantern the page is not “a React tree.” It is a layout of slots:

flowchart TB
  subgraph page["One HTML page from the composer"]
    Topbar["Topbar: HarborStay + Stays / Experiences"]
    subgraph main["Main column"]
      Search["Search island: Where to next?"]
      Details["Details island: Featured stay"]
      Highlights["Highlights island: What to do in Copenhagen"]
      Reviews["Reviews island: What travelers say"]
      Recs["Recommendations island: More stays nearby"]
    end
    Sidebar["Sticky trip summary + Book this stay"]
  end

Click Luxury on the search chips and the grid collapses to Harbor View Lodge and Moss & Lantern. The reviews below do not re-fetch. They never heard about the filter. That is not a bug — that is the point.

Island rule: each fragment owns its own interactivity. Search filters are Marko state. Highlight selection is React state. Experience categories are Riot state. The composer does not have a global store.

A tiny protocol instead of a shared SDK

Every fragment speaks harborstay-fragment/v1.

GET /?hotelId=moss-lantern
GET /manifest
GET /assets/<name>.css
GET /assets/<name>.js

And a few provenance headers:

X-Fragment-Name: search
X-Fragment-Hotel-Id: moss-lantern
X-Fragment-Protocol: harborstay-fragment/v1
X-Fragment-Css: http://localhost:3200/assets/search.css
X-Fragment-Js:  http://localhost:3200/assets/search.js

The composer reads the HTML body. Asset URLs are informational. In this demo, CSS and JS are served from a tiny CDN app on :3200 that copies fragment assets on startup.

That split is the real-world shape: SSR lives with the team that owns the UI. Bytes live on a CDN.

Assets belong to the fragment that created them, not to the shell:

apps/hotel-search/src/assets/search.css
apps/hotel-search/src/build-client.js   → cdn/public/assets/search.js

If search wants a new filter chip, reviews does not rebuild.

Three runtimes, one HTML contract

This is the part people assume is impossible.

Runtime	Fragments	Server render	Client
Marko	navigation, search, details, reviews, recommendations	`@marko/compiler` → `template.render().toString()`	Marko DOM runtime mounts into a root
React 19	local highlights	`react-dom/server` `renderToStaticMarkup`	`hydrateRoot`
Riot	experiences discovery + itinerary	hand-written `renderSsrMarkup()`	`riot.component()` after clearing the SSR root

The composer does not care. All three return strings.

flowchart TB
  subgraph marko["Marko :3102"]
    M1["hotel-search.marko"] --> M2["HTML string"]
  end
  subgraph react["React :3106"]
    R1["HighlightsView.jsx"] --> R2["HTML string"]
  end
  subgraph riot["Riot :3107"]
    T1["renderSsrMarkup()"] --> T2["HTML string"]
  end
  M2 --> Composer["Composer stitches slots"]
  R2 --> Composer
  T2 --> Composer
  Composer --> Browser["Browser paints HTML before any island JS"]

Why SSR in a microfrontend at all?

The first paint does not wait for JavaScript.
HTML is the only lingua franca three frameworks share.
If experiences-discovery.js fails, the user still sees the cards.

That last one is Islands architecture in the small: static HTML with pockets of JS, not a SPA that hydrates the entire document.

How data crosses the SSR/client gap

Every interactive fragment embeds props as JSON, not data- attributes:

<script type="application/json" id="hotel-search-fragment-data">
  {"hotels":[...],"hotelId":"moss-lantern"}
</script>
<div id="hotel-search-fragment-root">
  <!-- SSR HTML -->
</div>

The client bundle reads that script and mounts. Before embedding, fragment servers escape < as \u003c so a hotel description cannot break out of the script tag.

data-hotels='[{...}]' looks simpler. It is worse: large JSON in attributes bloats the DOM, needs ugly escaping, and is visible to everything that walks the tree.

Hydration is not one word

Walking the live app made this concrete.

Marko search hydrates into #hotel-search-fragment-root. Luxury / Value / Top rated re-render the grid without a navigation. The client template must match the server template or you get a flash.

React highlights hydrates with hydrateRoot. On Moss & Lantern you get Garden loop, Sauna ritual, Harbor market. Click a card and only that island updates.

Riot cannot hydrate the way React does. There is no reconcile-existing-DOM API in this setup, so the client wipes the SSR HTML and remounts:

mountNode.innerHTML = '';
component(DiscoveryTag)(mountNode, props);

You still get a fast first paint. You also get a tiny risk of visual flash if the Riot template and renderSsrMarkup() drift. Keep class names, element types, and copy identical.

On /experiences/moss-lantern I clicked Food: three cards became one tasting session. I clicked Day 2: breakfast / walk / dinner became scenic run / museum / sunset lounge. Two Riot islands, two state machines, zero shared store.

sequenceDiagram
  participant U as User
  participant D as Discovery Riot
  participant I as Itinerary Riot
  U->>D: Click Food
  D->>D: state.activeCategory = Food
  Note over I: Itinerary does not care
  U->>I: Click Day 2
  I->>I: state.selectedDay = 2
  Note over D: Discovery does not care

Streaming: do not wait for the slowest fragment

The stays page does not await Promise.all then send one blob.

streamPage() is an async function* . It yields the <head> and shell immediately, then races fragment promises and flushes HTML as each one finishes.

yield headPrefix;

const pending = new Map(
  fragmentOrder.map((name) => [name, safeRenderFragment(name, hotelId, delay)])
);

while (pending.size > 0) {
  const next = await Promise.race(
    [...pending.entries()].map(([name, promise]) =>
      promise.then((fragment) => ({ name, fragment }))
    )
  );
  pending.delete(next.name);
  yield next.fragment.html;
}

Fastify wraps that in Readable.from(...). The response header x-ssr-stream: true is a breadcrumb that this is a streamed document.

gantt
  title Streaming vs waiting for everyone
  dateFormat  X
  axisFormat  %s ms
  section Buffered
  Wait for slowest fragment     :a1, 0, 860
  First paint                   :a2, 860, 50
  section Streamed
  Head + shell                  :b1, 0, 40
  Search HTML                   :b2, 160, 40
  Recommendations HTML          :b3, 300, 40
  Details HTML                  :b4, 540, 40
  Reviews HTML                  :b5, 860, 40

The demo even fakes latency so you can see streaming:

const FRAGMENT_STREAM_DELAY_MS = {
  search: 160,
  recommendations: 300,
  details: 540,
  reviews: 860,
};

In production you delete those delays. Keep the race. First Contentful Paint becomes “when the shell arrives,” not “when reviews finally woke up.” Skeletons (.loading-fragment) hold layout so later chunks do not shove the page around.

If a fragment is restarting, safeRenderFragment catches the error and yields:

reviews fragment is warming up.

Independent deploys stop being theoretical.

JavaScript budget is a route problem

A composed page can accidentally ship four frameworks to every visitor. HarborStay avoids that with page splits, not heroics.

pnpm dev:home runs composer + CDN + stays fragments.
pnpm dev:experiences runs composer + CDN + the two Riot apps.
The stays page builder never emits experiences-discovery.js.
The experiences page never emits search.js.

That is the cheapest performance win in the repo. Intersection Observer hydration, click-to-hydrate, and requestIdleCallback are next — the docs already sketch them — but route-level omission beats all of them.

flowchart LR
  StayPage["/hotel/:id"] --> StayJS["search.js + highlights.js"]
  ExpPage["/experiences/:id"] --> ExpJS["discovery.js + itinerary.js"]
  StayPage -.-> NoRiot["Riot bundles not referenced"]
  ExpPage -.-> NoMarko["Search bundle not referenced"]

State: URL, local, or an event — pick one

Shared mutable global state is how microfrontends become a distributed monolith.

HarborStay’s rules:

Ephemeral UI state stays in the island. Filter chips, selected highlight, active day.
Shareable state lives in the URL. /hotel/moss-lantern is the source of truth for “which stay.” Full page reload is intentional in this demo.
Cross-fragment talk is an event, not a store import.

document.dispatchEvent(new CustomEvent('harborstay:hotel-selected', {
  bubbles: true,
  detail: { hotelId: 'moss-lantern' },
}));

Do not do this:

import { store } from '@harborstay/store'; // two bundles = two stores

Two IIFE bundles that “import the same store” get two closures. They will not share state. They will gaslight you.

BroadcastChannel is the right tool only when tabs or iframes must stay in sync. localStorage is for values that must survive a round trip. Neither belongs in the first version.

How this would ship

Each fragment is a Node HTTP server. DNS for users points at the composer. Fragments live on internal hostnames. Static assets go to a real CDN.

flowchart TB
  User["User"] --> LB["Load balancer / CDN"]
  LB --> Composer["Composer"]
  Composer --> F1["mfe-hotel-search"]
  Composer --> F2["mfe-reviews"]
  Composer --> F3["mfe-local-highlights"]
  Composer --> F4["other fragments"]
  Assets["cdn.example.com"] -.-> User

Rolling deploy order:

Publish content-hashed assets.
Roll fragment servers (any order — fallbacks cover restarts).
Roll the composer last.

Turborepo is the monorepo glue: pnpm dev:home fans out with persistent dev tasks, and turbo run build only rebuilds what changed.

This is a demo, not a production platform. The goal is a shape you can reason about: one contract, many runtimes, progressive HTML.

What I would do next

The interesting unfinished work is not “add another framework.” It is:

Soft navigation — history.pushState + swap only the fragments that changed.
True streaming inside fragments — Marko template.stream(), React renderToPipeableStream.
Riot hydrate() when the API is stable, so we stop wiping SSR DOM.
Edge composer — the generator already looks like a Web Streams mental model.
SWR cache of fragment HTML at the composer for anonymous hotel pages.

Run it

pnpm install
pnpm dev:home          # stays flow
pnpm dev:experiences   # experiences flow
pnpm dev:all           # everything

Then open http://localhost:3100.

If you want a mental model to steal, steal this one:

Compose HTML, not components. Hydrate islands, not pages. Keep state with the team that owns the UI. Let the slowest fragment arrive last without blocking the first paint.

The user still sees one hotel page. The architecture is allowed to be many rooms behind one door.

GITHUB: https://github.com/piyushchauhan2011/marko-mfe

Why Your JavaScript Sums Are Wrong (And How to Fix Them)

Piyush Chauhan — Wed, 05 Aug 2026 07:24:22 +0000

You know that Array.prototype.reduce you've used a thousand times to sum numbers? It's lying to you.

1. A One-Liner That Should Work

const nums = Array.from({ length: 1000 }, () => 0.1);
const sum = nums.reduce((a, b) => a + b, 0);

console.log(sum);        // 99.9999999999986
console.log(sum === 100); // false (!)

A thousand tenths should equal one hundred. But in JavaScript — and in virtually every other mainstream language — it doesn't. Not exactly.

If you've ever shrugged off a 0.0000000000001 discrepancy, this article is for you. Because at scale, that "tiny" error isn't tiny at all.

2. The Problem: Why Floats Betray Us

JavaScript uses IEEE 754 double-precision floating-point for all numbers. In plain English: your numbers are stored as binary fractions, and most decimal fractions (like 0.1) have no exact binary representation.

When you add 0.1 + 0.2, the computer isn't adding "one-tenth plus two-tenths." It's adding the closest binary approximations it can store. The result? 0.30000000000000004.

Now multiply that imperfection across a thousand, a million, or a billion additions. The error doesn't stay small — it accumulates.

The Core Issue

When you sum left-to-right with a running total, you eventually reach a point where the running total is huge and the next number is tiny. In floating-point arithmetic, adding a tiny number to a huge number often results in no change at all — the tiny number gets "swallowed."

Imagine pouring water into a bucket with a small hole. Each pour loses a few drops. After 1,000 pours, you're missing a puddle.

3. The Fix: Kahan Summation

In 1965, William Kahan published an algorithm that tracks and recovers the low-order bits lost in each addition. The trick? A compensation variable that remembers what got rounded away.

The Intuition

Instead of just keeping a running total, Kahan summation keeps two values:

sum — the best approximation so far
c (compensation) — the error that was discarded in the last step

Before each new addition, the compensation from the previous step is added back in. After the addition, the new error is computed and stored for the next iteration.

The Algorithm

Input: x
       │
       ▼
    x + c  ◄── compensation from last step
       │
       ▼
   t = sum + (x + c)
       │
       ▼
   c = (t - sum) - (x + c)  ← the "recovered" error
       │
       ▼
   sum = t

JavaScript Implementation

function kahanSum(numbers) {
  let sum = 0;
  let c = 0; // compensation for lost low-order bits

  for (let i = 0; i < numbers.length; i++) {
    const y = numbers[i] - c;  // subtract previous error
    const t = sum + y;         // tentative sum
    c = (t - sum) - y;         // new error: (what we added) - (what we meant to add)
    sum = t;
  }

  return sum;
}

Line-by-Line Breakdown

Line	What It Does
`y = numbers[i] - c`	Add back the error from the previous step
`t = sum + y`	Perform the actual addition
`c = (t - sum) - y`	Calculate what got lost in rounding
`sum = t`	Commit the new sum

The magic is in (t - sum) - y. Because of how floating-point subtraction works, this expression recovers the bits that were rounded away during sum + y.

4. Live Comparison: Naive vs. Kahan

Let's run both algorithms on the same pathological dataset:

// 10 million copies of 0.0001
// True answer: exactly 1000
const nums = Array.from({ length: 10_000_000 }, () => 0.0001);

console.time('naive');
const naive = nums.reduce((a, b) => a + b, 0);
console.timeEnd('naive');

console.time('kahan');
const kahan = kahanSum(nums);
console.timeEnd('kahan');

console.log('Naive: ', naive);  // 999.9998999965879
console.log('Kahan: ', kahan);  // 1000.0000000000001

The naive sum is off by 0.0001. That might not sound like much, but in financial systems processing millions of transactions, "small" errors compound into real money.

Kahan's error? 1.1e-13 — effectively zero for all practical purposes.

5. The Middle Ground: Pairwise Summation

Before we crown Kahan the winner, there's a third contender that often gets overlooked: pairwise summation (also called cascade summation).

The idea is beautifully simple: instead of accumulating left-to-right, recursively split the array in half, sum each half, then add the two results. This ensures you're always adding numbers of roughly the same magnitude.

The Intuition

Imagine balancing a scale. Naive summation keeps piling weights on one side until the running total dwarfs every new addition. Pairwise summation weighs equal-sized groups against each other at every step.

[1, 2, 3, 4, 5, 6, 7, 8]
    /              \
[1,2,3,4]      [5,6,7,8]
  /    \          /    \
[1,2] [3,4]    [5,6] [7,8]
 |     |        |     |
 3     7        11    15
   \   /          \  /
    10             26
         \        /
           36

Recursive Implementation

function pairwiseSum(arr, start = 0, end = arr.length) {
  const len = end - start;
  if (len === 0) return 0;
  if (len === 1) return arr[start];

  const mid = start + Math.floor(len / 2);
  return pairwiseSum(arr, start, mid) + pairwiseSum(arr, mid, end);
}

⚠️ Caution: For very large arrays (> ~10,000 items), the recursive version will blow the call stack. Here's a stack-safe iterative version:

🔧 Stack-safe iterative version

function pairwiseSumIterative(arr) {
  if (arr.length === 0) return 0;

  let queue = arr.slice();

  while (queue.length &gt; 1) {
    const next = [];
    for (let i = 0; i &lt; queue.length; i += 2) {
      next.push(queue[i] + (queue[i + 1] || 0));
    }
    queue = next;
  }

  return queue[0];
}

6. The Heavyweight: decimal.js

Sometimes you need exact decimal arithmetic, not just "less error." That's where decimal.js comes in. It represents numbers as strings internally and performs arbitrary-precision math.

Installation

npm install decimal.js

Usage

const Decimal = require('decimal.js');

function decimalSum(numbers) {
  return numbers
    .reduce((sum, n) => sum.plus(new Decimal(n.toString())), new Decimal(0))
    .toNumber();
}

💡 Pro tip: Always pass numbers through .toString() before constructing a Decimal. new Decimal(0.1) still inherits floating-point imprecision because 0.1 is already corrupted by the time it reaches the constructor.

7. The Showdown: Four-Way Comparison

Let's put them all to the test with a pathological dataset:

// 10 million copies of 0.0001
// True answer: exactly 1000
const nums = Array.from({ length: 10_000_000 }, () => 0.0001);

Method	Result	Error	Relative Speed
Naive `reduce`	`999.9998999965879`	`~1.0e-4`	1.0x (baseline)
Pairwise	`999.9999999999123`	`~8.8e-11`	~1.5x slower
Kahan	`1000.0000000000001`	`~1.1e-13`	~3.5x slower
decimal.js	`1000` (exact)	`0`	~40-80x slower

What the Numbers Tell Us

Naive is fast but wrong at scale. The error is small in absolute terms, but in financial systems, "small" errors compound into real money.
Pairwise dramatically reduces error with minimal overhead. Its error grows logarithmically O(log n) instead of linearly.
Kahan achieves near-constant error O(ε) — the gold standard for floating-point summation.
decimal.js is exact but slow. It's not really a summation algorithm; it's a different number system entirely.

8. The Decision Framework

Here's a quick cheat sheet for choosing the right tool:

Scenario	Recommendation	Why
Small arrays (< 1,000 items)	Naive `reduce`	Error is negligible; don't over-engineer
Large arrays, need speed, "good enough" accuracy	Pairwise	Logarithmic error growth, parallelizable
Financial/scientific computing, must minimize error	Kahan	Constant error bound, no extra dependencies
Accounting, currency, must be exact	decimal.js	Arbitrary precision eliminates rounding entirely
GPU/Web Worker parallel processing	Pairwise	Perfectly parallelizable; Kahan is inherently sequential

The Trade-off Triangle

        Speed
         /\
        /  \
       /    \
      /      \
     /   ⚠️   \
    /__________\
 Accuracy    Simplicity

You can pick two:

Fast + Simple → Naive
Fast + Accurate → Pairwise
Accurate + Simple → Kahan
Exact → decimal.js (sacrifices speed)

9. When NOT to Use Kahan

Kahan summation is great, but it's not always the right call:

Integers only — If your array contains only integers representable in 53 bits, naive summation is exact until you exceed Number.MAX_SAFE_INTEGER.
Already using a decimal library — If you've bought into decimal.js or big.js, you don't need Kahan; you're already exact.
Real-time graphics/animation — A 3-4x slowdown for a pixel-perfect particle position is rarely worth it.
Very small datasets — The error on [0.1, 0.2, 0.3] is 5.55e-17. Your users don't care.

10. One-Liners for Your Toolkit

For the copy-paste engineers:

// Kahan (functional, but slightly slower due to array destructuring)
const kahanSum = (a) => a.reduce(([s, c], x) => {
  const y = x - c;
  const t = s + y;
  return [t, (t - s) - y];
}, [0, 0])[0];

// Pairwise (iterative, stack-safe)
const pairwiseSum = (a) => {
  let q = [...a];
  while (q.length > 1) {
    const n = [];
    for (let i = 0; i < q.length; i += 2) n.push(q[i] + (q[i+1] || 0));
    q = n;
  }
  return q[0] || 0;
};

Conclusion

Floating-point summation is one of those problems that seems trivial until it isn't. The good news: JavaScript gives you options.

Reach for pairwise summation when you need a quick accuracy boost without a performance cliff.
Reach for Kahan summation when precision is paramount and you're working with raw floats.
Reach for decimal.js when you're dealing with money, tax calculations, or anything where "close enough" isn't in your vocabulary.

And sometimes? Just use reduce. Not every array needs a PhD.

What's your go-to strategy for numerical accuracy in JavaScript? Drop your war stories in the comments below. 👇

Backtracking Unveiled: Mastering Depth-First Search and Pruning Techniques

Piyush Chauhan — Sat, 22 Feb 2025 09:04:27 +0000

Backtracking is a systematic way to iterate through all possible configurations of a problem. It is often used to solve problems where a sequence of decisions must be made, and each decision leads to a new set of possibilities. Backtracking uses depth-first search (DFS) to explore the state space, and it employs pruning functions to eliminate invalid or suboptimal paths early in the search process.

Components of Backtracking Problems

Initial State: The starting point of the problem.
Target/Goal State: The desired solution.
Intermediate States: States generated while moving from the initial state to the target state.
Path: The sequence of states from the initial state to the target state.
Operators: Rules or actions that transform one state into another.
Pruning Function: A heuristic to eliminate invalid or suboptimal states early.

Backtracking Algorithm

Start with the initial state.
Use DFS to explore all possible states.
If a state is invalid (based on the pruning function), backtrack and try another path.
If a state is the goal state, return the solution.
Repeat until all possible states are explored or a solution is found.

Example Problems Solved Using Backtracking

1. 3-Digit Lock Problem

Initial State: "111"
Target State: The correct combination (e.g., "352")
Operators: Increment each digit by 1 (from 1 to 9).
Pruning Function: If a digit is correct (e.g., produces a "click"), fix it and move to the next digit.

Implementation:

function findLockCombination(target) {
    function backtrack(combination, index) {
        if (combination === target) {
            console.log("Found combination:", combination);
            return true;
        }
        if (index >= 3) return false;

        for (let i = 1; i <= 9; i++) {
            const newCombination = combination.slice(0, index) + i + combination.slice(index + 1);
            if (newCombination[index] === target[index]) {
                console.log("Click at position", index + 1, "with digit", i);
                if (backtrack(newCombination, index + 1)) return true;
            }
        }
        return false;
    }

    backtrack("111", 0);
}

const targetCombination = "352";
findLockCombination(targetCombination);

2. Monks and Demons Problem

Initial State: 3 monks, 3 demons, and the boat on the left shore.
Target State: All monks and demons on the right shore.
Operators: Move 1 or 2 people in the boat.
Pruning Function: Ensure that monks are never outnumbered by demons on either shore.

Implementation:

function solveMonksAndDemons() {
    const initialState = { left: { monks: 3, demons: 3 }, right: { monks: 0, demons: 0 }, boat: "left" };
    const visited = new Set();

    function isSafe(state) {
        const { left, right } = state;
        return (
            (left.monks === 0 || left.monks >= left.demons) &&
            (right.monks === 0 || right.monks >= right.demons)
        );
    }

    function backtrack(state, path = []) {
        const key = JSON.stringify(state);
        if (visited.has(key)) return false;
        visited.add(key);

        if (state.left.monks === 0 && state.left.demons === 0) {
            console.log("Solution found:", path);
            return true;
        }

        const { left, right, boat } = state;
        const moves = [
            { monks: 1, demons: 0 },
            { monks: 2, demons: 0 },
            { monks: 0, demons: 1 },
            { monks: 0, demons: 2 },
            { monks: 1, demons: 1 },
        ];

        for (const move of moves) {
            if (
                (boat === "left" && left.monks >= move.monks && left.demons >= move.demons) ||
                (boat === "right" && right.monks >= move.monks && right.demons >= move.demons)
            ) {
                const newLeft = {
                    monks: left.monks - (boat === "left" ? move.monks : -move.monks),
                    demons: left.demons - (boat === "left" ? move.demons : -move.demons),
                };
                const newRight = {
                    monks: right.monks - (boat === "right" ? move.monks : -move.monks),
                    demons: right.demons - (boat === "right" ? move.demons : -move.demons),
                };
                const newState = {
                    left: newLeft,
                    right: newRight,
                    boat: boat === "left" ? "right" : "left",
                };

                if (isSafe(newState) && backtrack(newState, [...path, newState])) {
                    return true;
                }
            }
        }
        return false;
    }

    backtrack(initialState);
}

solveMonksAndDemons();

3. Farmer, Goat, Cabbage, and Wolf Problem

Initial State: Farmer, goat, cabbage, and wolf on the left shore.
Target State: All on the right shore.
Operators: Farmer can take one item (goat, cabbage, or wolf) in the boat.
Pruning Function: Ensure the goat is not left alone with the cabbage, and the wolf is not left alone with the goat.

Implementation:

function solveFarmerProblem() {
  const initialState = {
    left: ["farmer", "goat", "cabbage", "wolf"],
    right: [],
    boat: "left",
  };
  const visited = new Set();

  function isSafe(state) {
    const unsafe = (side) =>
      (side.includes("goat") &&
        side.includes("cabbage") &&
        !side.includes("farmer")) ||
      (side.includes("wolf") &&
        side.includes("goat") &&
        !side.includes("farmer"));

    return !(unsafe(state.left) || unsafe(state.right));
  }

  function stateKey(state) {
    return JSON.stringify(state);
  }

  function backtrack(state, path = []) {
    if (state.left.length === 0) {
      console.log("Solution found:", path);
      return true;
    }

    const key = stateKey(state);
    if (visited.has(key)) return false;
    visited.add(key);

    const { left, right, boat } = state;
    const fromShore = boat === "left" ? left : right;

    // Possible moves: Farmer alone or Farmer + one item
    for (const item of [...fromShore, null]) {
      if (item === null || item !== "farmer") {
        let newLeft = [...left];
        let newRight = [...right];

        if (boat === "left") {
          newLeft = newLeft.filter((x) => x !== "farmer" && x !== item);
          newRight = [...newRight, "farmer"];
          if (item) newRight.push(item);
        } else {
          newRight = newRight.filter((x) => x !== "farmer" && x !== item);
          newLeft = [...newLeft, "farmer"];
          if (item) newLeft.push(item);
        }

        const newState = {
          left: newLeft,
          right: newRight,
          boat: boat === "left" ? "right" : "left",
        };

        if (isSafe(newState) && backtrack(newState, [...path, newState])) {
          return true;
        }
      }
    }

    return false;
  }

  backtrack(initialState);
}

solveFarmerProblem();

4. Water Jug Problem

Initial State: Both jugs are empty.
Target State: 2 gallons in the 4-gallon jug.
Operators: Fill, empty, or pour water between jugs.
Pruning Function: Avoid revisiting states.

Implementation:

function solveWaterJug() {
    const initialState = { jug4: 0, jug3: 0 };
    const target = 2;
    const visited = new Set();

    function backtrack(state, path = []) {
        const key = `${state.jug4},${state.jug3}`;
        if (visited.has(key)) return false;
        visited.add(key);

        if (state.jug4 === target) {
            console.log("Solution found:", path);
            return true;
        }

        const { jug4, jug3 } = state;
        const moves = [
            { jug4: 4, jug3 }, // Fill jug4
            { jug4, jug3: 3 }, // Fill jug3
            { jug4: 0, jug3 }, // Empty jug4
            { jug4, jug3: 0 }, // Empty jug3
            { jug4: Math.max(0, jug4 - (3 - jug3)), jug3: Math.min(3, jug3 + jug4) }, // Pour jug4 to jug3
            { jug4: Math.min(4, jug4 + jug3), jug3: Math.max(0, jug3 - (4 - jug4)) }, // Pour jug3 to jug4
        ];

        for (const move of moves) {
            if (backtrack(move, [...path, move])) {
                return true;
            }
        }
        return false;
    }

    backtrack(initialState);
}

solveWaterJug();

Key Points:

Backtracking is a systematic way to explore all possible solutions.
It uses depth-first search and pruning functions to eliminate invalid paths.
It is useful for solving NP-hard problems like puzzles, constraint satisfaction problems, and combinatorial optimization.

A* Search Algorithm and Iterative Deepening A* in JavaScript

Piyush Chauhan — Sat, 08 Feb 2025 05:44:55 +0000

1. Introduction

Search algorithms play a crucial role in solving problems across computer science, robotics, game development, and beyond. Among them, heuristic-based search algorithms stand out for their ability to efficiently find solutions by leveraging additional knowledge about the problem domain. This article delves into two such algorithms: the widely used A* search algorithm and its memory-efficient counterpart, Iterative Deepening A* (IDA*).

By the end of this article, you will:

Understand the core principles of A* and IDA*.
Learn how these algorithms work through code implementations in JavaScript.
Explore their mathematical underpinnings and use cases.

**2. Understanding A* Search Algorithm**

What is A*?

A* is a best-first search algorithm that aims to find the shortest path from a start node to a goal node. It uses an evaluation function:

f (n) = g (n) + h (n)

Where:

$g (n)$ : The cost of the path from the start node to the current node $n$ .
$h (n)$ : A heuristic estimate of the cost to reach the goal node from $n$ .

The algorithm prioritizes nodes with the smallest $f (n)$ value, making it both optimal and complete, provided the heuristic $h (n)$ is admissible (never overestimates the true cost).

Properties of A*

Completeness: Guaranteed to find a solution if one exists.
Optimality: Finds the shortest path with an admissible heuristic.
Admissibility and Consistency: Ensures the heuristic is reliable for optimal solutions.

Wikipedia Pseudocode for A*

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    // This is usually implemented as a min-heap or priority queue rather than a hash-set.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from the start
    // to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the currently known cost of the cheapest path from start to n.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
    // how cheap a path could be from start to finish if it goes through n.
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        // This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := tentative_gScore + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure

**3. Implementing A* in JavaScript**

Below is a JavaScript implementation of A* for a grid-based shortest path problem:

const assert = require("assert");

class PriorityQueue {
  constructor() {
    this.elements = [];
  }

  enqueue(item, priority) {
    this.elements.push({ item, priority });
    this.elements.sort((a, b) => a.priority - b.priority);
  }

  dequeue() {
    return this.elements.shift().item;
  }

  isEmpty() {
    return this.elements.length === 0;
  }
}

function aStar(start, goal, grid, heuristic) {
  const rows = grid.length;
  const cols = grid[0].length;

  const openSet = new PriorityQueue();
  openSet.enqueue(start, 0);

  const cameFrom = {};
  const gScore = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
  gScore[start[0]][start[1]] = 0;

  const fScore = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
  fScore[start[0]][start[1]] = heuristic(start, goal);

  while (!openSet.isEmpty()) {
    const current = openSet.dequeue();
    const [x, y] = current;

    if (current[0] === goal[0] && current[1] === goal[1]) {
      return reconstructPath(cameFrom, current);
    }

    for (const [dx, dy] of [
      [0, 1],
      [1, 0],
      [0, -1],
      [-1, 0],
    ]) {
      const neighbor = [x + dx, y + dy];
      const [nx, ny] = neighbor;

      if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] === 0) {
        const tentative_gScore = gScore[x][y] + 1;

        if (tentative_gScore < gScore[nx][ny]) {
          cameFrom[neighbor] = current;
          gScore[nx][ny] = tentative_gScore;
          fScore[nx][ny] = tentative_gScore + heuristic(neighbor, goal);

          openSet.enqueue(neighbor, fScore[nx][ny]);
        }
      }
    }
  }
  return "No path found";
}

function heuristic([x1, y1], [x2, y2]) {
  return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

function reconstructPath(cameFrom, current) {
  const path = [current];
  while (cameFrom[current]) {
    current = cameFrom[current];
    path.unshift(current);
  }
  return path;
}

// Test A* Algorithm
const grid = [
  [0, 0, 0, 0],
  [1, 1, 1, 0],
  [0, 0, 0, 0],
  [0, 1, 1, 1],
  [0, 0, 0, 0],
];

const start = [0, 0];
const goal = [4, 3];
const path = aStar(start, goal, grid, heuristic);
console.log("Found Path:", path);
assert.notStrictEqual(path, "No path found");
assert.strictEqual(Array.isArray(path), true);

// Test for no path
const blockedGrid = [
  [0, 1, 0],
  [1, 1, 0],
  [0, 1, 0],
];
const noPathResult = aStar([0, 0], [2, 2], blockedGrid, heuristic);
assert.strictEqual(noPathResult, "No path found");

4. Mathematical Proofs and Analysis

Proof of Optimality

A* guarantees the shortest path if the heuristic $h (n)$ is admissible and consistent.

Admissibility: $h (n)$ never overestimates the true cost to the goal. This ensures that A* will not bypass the optimal path.
Consistency: For every pair of nodes $n$ and $n^{'}$ , the heuristic satisfies: $h (n) \leq c (n, n^{'}) + h (n^{'})$ where $c (n, n^{'})$ is the cost of transitioning from $n$ to $n^{'}$ . This property ensures that the $f (n)$ values along a path are non-decreasing.

Time and Space Complexity

Time Complexity: In the worst case, A* explores all nodes with $f (n)$ less than the cost of the optimal solution. This can grow exponentially with the branching factor $b$ and the depth $d$ of the solution: $O (b^{d})$ .
Space Complexity: A* stores all explored nodes in memory, leading to $O (b^{d})$ space usage.

5. Limitations of A*

While A* is highly efficient for many problems, it has significant limitations:

Memory Requirements: Storing all explored nodes can become infeasible for large graphs.
Performance: On graphs with high branching factors or inaccurate heuristics, A* may perform poorly.

**6. Iterative Deepening A* (IDA*)**

Why IDA*?

IDA* addresses A*'s memory limitations by combining the benefits of A*'s heuristic-guided search with the memory efficiency of depth-first search. Instead of maintaining a priority queue, IDA* performs iterative depth-first searches with increasing $f$ -cost thresholds.

How It Works

Initialize the threshold to $h (s t a r t)$ .
Perform a depth-first search, pruning paths with $f (n) >$ threshold.
If no solution is found, increase the threshold to the smallest $f (n)$ value that exceeded the current threshold.
Repeat until the goal is reached.

Wikipedia Pseudocode for IDA*

path              current search path (acts like a stack)
node              current node (last node in current path)
g                 the cost to reach current node
f                 estimated cost of the cheapest path (root..node..goal)
h(node)           estimated cost of the cheapest path (node..goal)
cost(node, succ)  step cost function
is_goal(node)     goal test
successors(node)  node expanding function, expand nodes ordered by g + h(node)
ida_star(root)    return either NOT_FOUND or a pair with the best path and its cost

procedure ida_star(root)
    bound := h(root)
    path := [root]
    loop
        t := search(path, 0, bound)
        if t = FOUND then return (path, bound)
        if t = ∞ then return NOT_FOUND
        bound := t
    end loop
end procedure

function search(path, g, bound)
    node := path.last
    f := g + h(node)
    if f > bound then return f
    if is_goal(node) then return FOUND
    min := ∞
    for succ in successors(node) do
        if succ not in path then
            path.push(succ)
            t := search(path, g + cost(node, succ), bound)
            if t = FOUND then return FOUND
            if t < min then min := t
            path.pop()
        end if
    end for
    return min
end function

**7. Implementing IDA* in JavaScript**

function idaStar(start, goal, grid, heuristic) {
  let threshold = heuristic(start, goal);

  while (true) {
    const cameFrom = {};
    const result = dfs(
      start,
      0,
      threshold,
      goal,
      grid,
      heuristic,
      cameFrom,
      new Set()
    );
    if (result.found) {
      return reconstructPath(cameFrom, goal);
    }
    if (result.threshold === Infinity) {
      return "No path found";
    }
    threshold = result.threshold;
  }
}

function dfs(node, g, threshold, goal, grid, heuristic, cameFrom, visited) {
  const f = g + heuristic(node, goal);
  if (f > threshold) return { threshold: f, found: false };
  if (node[0] === goal[0] && node[1] === goal[1])
    return { found: true, cameFrom };

  visited.add(node.toString());
  let minThreshold = Infinity;
  for (const [dx, dy] of [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ]) {
    const neighbor = [node[0] + dx, node[1] + dy];
    const [nx, ny] = neighbor;

    if (
      nx >= 0 &&
      nx < grid.length &&
      ny >= 0 &&
      ny < grid[0].length &&
      grid[nx][ny] === 0 &&
      !visited.has(neighbor.toString())
    ) {
      cameFrom[neighbor] = node;
      const result = dfs(
        neighbor,
        g + 1,
        threshold,
        goal,
        grid,
        heuristic,
        cameFrom,
        visited
      );
      if (result.found) return result;
      if (result.threshold < minThreshold) minThreshold = result.threshold;
    }
  }
  visited.delete(node.toString());
  return { threshold: minThreshold, found: false };
}

const grid = [
  [0, 0, 0, 0],
  [1, 1, 1, 0],
  [0, 0, 0, 0],
  [0, 1, 1, 1],
  [0, 0, 0, 0],
];

const start = [0, 0];
const goal = [4, 3];

const pathIdaStar = idaStar(start, goal, grid, heuristic);
console.log("IDA* Found Path:", pathIdaStar);
assert.notStrictEqual(pathIdaStar, "No path found");
assert.strictEqual(Array.isArray(pathIdaStar), true);

const blockedGrid = [
  [0, 1, 0],
  [1, 1, 0],
  [0, 1, 0],
];

const noPathResultIdaStar = idaStar([0, 0], [2, 2], blockedGrid, heuristic);
assert.strictEqual(noPathResultIdaStar, "No path found");

**8. Comparing A* and IDA***

Feature	A*	IDA*
Memory Usage	High (stores all nodes)	Low (depth-first search)
Speed	Faster for smaller graphs	Slower due to iterative nature
Implementation Complexity	Moderate	Higher
Suitability for Large Graphs	Limited	More suitable

9. Use Cases

Game Development: Pathfinding for characters and AI in games (e.g., NPC movement).
Robotics: Navigation for autonomous robots in real-world environments.
Network Routing: Finding the shortest paths in network graphs.
Puzzle Solving: Solving puzzles like the 8-puzzle or 15-puzzle efficiently.

10. Common Pitfalls and Best Practices

When implementing and applying A* or IDA*, it’s essential to avoid common mistakes and adopt best practices to ensure optimal performance.

1. Choosing Heuristics Wisely

Admissibility: Ensure that the heuristic never overestimates the cost to reach the goal. This guarantees that A* will find the optimal solution.
Consistency (Monotonicity): Verify that the heuristic satisfies the triangle inequality: $h (n) \leq c (n, n^{'}) + h (n^{'})$ . This ensures that the algorithm’s $f (n)$ values are non-decreasing.
Common heuristics include:
- Manhattan Distance: Suitable for grid-based problems where movement is restricted to horizontal or vertical directions.
- Euclidean Distance: Best for problems allowing diagonal or free movement in a continuous space.
- Domain-Specific Heuristics: Tailor heuristics based on specific problem knowledge to improve performance.

2. Balancing $g (n)$ and $h (n)$

Assign appropriate weights to $g (n)$ (path cost so far) and $h (n)$ (estimated cost to goal).
Overemphasizing $h (n)$ might lead to suboptimal solutions or longer paths.
Relying heavily on $g (n)$ might degrade performance, as the algorithm explores more nodes unnecessarily.

3. Debugging and Visualization Techniques

Visualization: Tools like heatmaps or animations of the search process can help debug and optimize the algorithm.
Logging: Track $f (n)$ , $g (n)$ , and $h (n)$ values for each node to identify anomalies.
Unit Testing: Validate heuristic functions and graph structures with simple test cases to ensure correctness.
Benchmarking: Test the implementation on different datasets to measure performance and identify bottlenecks.

11. Advanced Topics

1. Variants of A*

A* has inspired several variants tailored to specific scenarios or performance needs:

Weighted A*:
- Modifies the evaluation function to $f (n) = g (n) + w \cdot h (n)$ , where $w$ (weight) adjusts the heuristic's influence.
- Used to trade optimality for speed by biasing the search toward the goal.
Memory-Bounded A*:
- Examples include Simplified Memory-Bounded A* (SMA*) and Recursive Best-First Search (RBFS).
- These variants limit memory usage by discarding or revisiting nodes as needed.
Hierarchical A*:
- Splits large graphs into smaller subgraphs, solves each independently, and combines results.
- Ideal for complex environments like city navigation.

2. Integration with Machine Learning

Machine learning can enhance A* by dynamically adjusting heuristics or guiding the search process:

Dynamic Heuristics: Use neural networks or reinforcement learning to predict better heuristic values for each state.
Adaptive Pathfinding: Train models to optimize paths based on historical data or changing environments.
Hybrid Models: Combine A* with ML-driven approaches for problems like real-time strategy games or robotics.

3. Parallelizing A* for Performance Optimization

Parallelization can significantly speed up A* for large graphs:

Parallel Open Set: Divide the open set among multiple threads or processes, each exploring a subset of nodes.
Distributed Search: Use distributed systems to partition the graph and execute search concurrently.
GPU Acceleration: Leverage GPUs for massive parallelism, especially for heuristic computations and large-scale graph traversal.

12. Conclusion

The A* search algorithm and Iterative Deepening A* are powerful tools for solving pathfinding and graph traversal problems. While A* excels in speed and guarantees optimality with sufficient memory, IDA* offers a memory-efficient alternative for large graphs. By understanding their principles, properties, and implementations, you can leverage these algorithms to tackle a wide range of computational problems effectively.

How I Use AI, Sticky Notes, and Pomodoro to Stay Productive as a Software Engineer

Piyush Chauhan — Fri, 24 Jan 2025 15:43:44 +0000

As a software engineer juggling frontend and backend tasks, I’ve found that staying organized and focused is key to delivering quality work without burning out. Over time, I’ve developed a workflow that combines AI assistance, sticky notes, and the Pomodoro Technique to break down tasks, track progress, and maintain my sanity. In this article, I’ll share my process and how you can adapt it to your own workflow.

The Problem: Overwhelming Tasks and Context Switching

When working on a new feature or story, I often start with a vague set of requirements. Breaking these down into actionable steps can be overwhelming, especially when I’m still figuring out the details. Add in the constant context switching between frontend and backend work, and it’s easy to lose track of what’s done and what’s left.

To tackle this, I needed a system that:

Helps me break down tasks into manageable chunks.
Keeps me aware of my progress.
Allows me to adapt as I learn more about the problem.
Ensures I stay focused and hydrated (because, let’s be honest, we all forget to drink water sometimes).

My Workflow: AI, Sticky Notes, and Pomodoro

Here’s how I’ve structured my workflow to address these challenges:

1. Generate an Initial To-Do List with AI

When I start a new subtask, I use AI tools (like Perplexity.ai or Continue.dev with Codellama) to generate an initial to-do list based on the requirements. For example, if I’m working on a user login feature, I might ask:

"Generate a to-do list for implementing a user login feature with email and password authentication. Include frontend and backend tasks."

The AI might suggest:

Set up login API endpoint.
Create frontend login form.
Add input validation for email and password.
Implement error handling for invalid credentials.

This gives me a solid starting point with 2–5 high-level tasks.

2. Create a Feature Branch

Once I have my initial to-do list, I create a feature branch for the subtask. For example:

git checkout -b feature/user-login

This keeps my work isolated and makes it easier to manage changes.

3. Work Incrementally and Extend the To-Do List

I start by tackling the first task on my list. As I work, I often uncover additional subtasks or edge cases. This is where AI comes in again. I’ll share my current progress and ask for suggestions:

"I’m working on implementing the login API. Here’s what I’ve done so far: [details]. What additional tasks should I consider?"

The AI might suggest:

Add rate limiting to prevent brute force attacks.
Log failed login attempts for security monitoring.
Write unit tests for the login functionality.

I add these tasks to my to-do list and continue working incrementally.

4. Track Progress with Sticky Notes

I’m a big fan of sticky notes for tracking progress. Whether physical or digital, they give me a visual representation of what’s done and what’s left.

Physical Sticky Notes: I place them on my desk or monitor, moving completed tasks to a "Done" section.
Digital Tools: If I’m working remotely, I use tools like Trello, Notion, or Todoist to manage my to-do list.

Crossing off tasks gives me a sense of accomplishment and keeps me motivated.

5. Stay Focused with the Pomodoro Technique

To maintain focus, I use the Pomodoro Technique:

Work for 25 minutes, then take a 5-minute break.
After four Pomodoros, take a longer break (15–30 minutes).

I assign specific to-do items to each Pomodoro session. For example:

Pomodoro 1: Set up login API endpoint.
Pomodoro 2: Add input validation for email and password.

During breaks, I make sure to hydrate, stretch, or take a short walk.

6. Create a Pull Request and Request Review

Once all tasks are completed, I create a pull request (PR) for my feature branch. I write a detailed PR description summarizing:

What was implemented.
Any challenges faced.
Testing performed.

I then request a review from my team and iterate based on feedback.

Tools I Use

Here are some tools and methods that have been invaluable in my workflow:

AI Tools

Perplexity.ai: For generating initial to-do lists and brainstorming solutions.
Continue.dev: For seamless integration with my IDE and local development environment.
Local AI Models: I use Qwen2.5-Coder 7B and CodeLlama 7B for code completion, debugging, and extending my to-do lists as I work. Running these models locally ensures privacy and customization.

Task Management

Trello: For visual task tracking with boards, lists, and cards.
Notion: For documenting requirements, progress, and reference materials.
JIRA: For aligning my tasks with team-wide project management and sprint planning.

Pomodoro Timers

Manual iPhone Timer: I use the built-in timer on my iPhone for Pomodoro sessions. It’s simple and effective.
Paper Checklist: I keep a handwritten checklist on paper to track tasks for each Pomodoro session. There’s something satisfying about physically crossing off completed tasks.

Hydration Tracking

Manual iPhone Timer: I set recurring reminders to drink water throughout the day.
Paper Drawing: I draw circles on paper and color them in to track my hydration progress. Each circle represents a glass of water, and filling them in gives me a visual sense of accomplishment.

Why This Works for Me

This workflow works because it:

Breaks down complex tasks into manageable chunks.
Adapts to new information as I learn more about the problem.
Keeps me focused with the Pomodoro Technique.
Provides a visual representation of progress with sticky notes.
Ensures I stay hydrated and energized throughout the day.

Example Workflow in Action

Scenario: Implementing a User Login Feature

Initial To-Do List (AI-Generated):
- Set up login API endpoint.
- Create frontend login form.
- Add input validation for email and password.
- Implement error handling for invalid credentials.
Feature Branch: feature/user-login
Incremental Work:
- Start with "Set up login API endpoint."
- Commit: git commit -m "Add login API endpoint with email/password validation"
- Ask AI: "What else should I consider for the login API?"
- AI suggests: Add rate limiting, log failed attempts, and write unit tests.
- Add these tasks to your to-do list.
Sticky Notes:
- Move "Set up login API endpoint" to "Done."
- Add new tasks: "Add rate limiting," "Log failed attempts," "Write unit tests."
Pomodoro Sessions:
- Session 1: Work on "Add rate limiting."
- Session 2: Work on "Log failed attempts."
PR and Review:
- Create PR with title "feat: implement user login" and description: "Implemented user login feature with email/password authentication. Added rate limiting and logging for security. Unit tests included."
- Request review and iterate based on feedback.

Key Benefits of This Workflow

Clarity: Breaking tasks into smaller chunks makes complex work manageable.
Focus: Pomodoro sessions and sticky notes help maintain focus and track progress.
Adaptability: AI assistance allows you to dynamically adjust your plan as you learn more.
Wellness: Regular breaks and hydration keep you energized and productive.

By formalizing and refining this workflow, you can enhance your productivity, reduce stress, and deliver high-quality work consistently.

Try It Out!

If you’re feeling overwhelmed by your tasks or struggling to stay focused, give this workflow a try. Start small—use AI to generate a to-do list, create a feature branch, and work incrementally. Experiment with sticky notes and the Pomodoro Technique to see what works best for you.

I’d love to hear how you stay productive in your day-to-day work. Share your tips and tools in the comments below!

Happy coding! 🚀

Introduction to WebAssembly (WASM)

Piyush Chauhan — Fri, 10 Jan 2025 16:21:06 +0000

WebAssembly (WASM) is a binary instruction format for a stack-based virtual machine, designed as a portable target for high-performance applications. In this article, we'll explore how to compile a simple C program to WebAssembly, load it into a web browser, and interact with it using JavaScript. We'll also explore some useful tools and commands for working with WASM outside the dev container environment.

Setting Up the Development Environment

Create the necessary folder structure and files for your WebAssembly project.

Create Project Folder:

Begin by creating a new directory for your project. Inside this folder, you'll add the necessary files and configurations.

mkdir wasm-web-example
cd wasm-web-example

Set Up Dev Container:

In the wasm-web-example directory, create the .devcontainer folder to store the dev container configuration files. These files will set up a container with Emscripten installed to compile C code into WebAssembly.

Inside the .devcontainer folder, create the following files:

devcontainer.json: The devcontainer.json file configures VSCode to use the Docker container with the necessary extensions and environment settings.

{
    "name": "Emscripten DevContainer",
    "build": {
        "dockerfile": "Dockerfile"
    },
    "customizations": {
        "vscode": {
            "settings": {
                "terminal.integrated.shell.linux": "/bin/bash",
                "C_Cpp.default.configurationProvider": "ms-vscode.cmake-tools",
                "C_Cpp.default.intelliSenseMode": "gcc-x64"
            },
            "extensions": [
                "ms-vscode.cpptools",
                "ms-vscode.cmake-tools"
            ]
        }
    },
    "postCreateCommand": "emcc --version"
}

Dockerfile: The Dockerfile will set up the Emscripten environment. Here's the content for that file:

# Use the official Emscripten image
FROM emscripten/emsdk:3.1.74

# Set the working directory
WORKDIR /workspace

# Copy the source code into the container
COPY . .

# Install any additional packages if necessary (optional)
# Ensure to clean up cache to minimize image size
RUN apt-get update && \
    apt-get install -y build-essential && \
    apt-get clean && \
    rm -rf /var/lib/apt/lists/*

Create VSCode Settings:

In the root of your project, create a .vscode folder with the following files:

c_cpp_properties.json: This file configures the C++ IntelliSense and include paths for your project.

{
    "configurations": [
        {
        "name": "Linux",
        "includePath": [
            "${workspaceFolder}/**",
            "/emsdk/upstream/emscripten/system/include"
        ],
        "defines": [],
        "compilerPath": "/usr/bin/gcc",
        "cStandard": "c17",
        "cppStandard": "gnu++17",
        "configurationProvider": "ms-vscode.cmake-tools"
        }
    ],
    "version": 4
}

settings.json: This file includes specific VSCode settings for language associations.

{
    "files.associations": {
        "emscripten.h": "c"
    },
    "[javascript]": {
        "editor.defaultFormatter": "vscode.typescript-language-features"
    },
    "[typescript]": {
        "editor.defaultFormatter": "vscode.typescript-language-features"
    },
    "[jsonc]": {
        "editor.defaultFormatter": "vscode.json-language-features"
    },
    "[json]": {
        "editor.defaultFormatter": "vscode.json-language-features"
    },
    "[html]": {
        "editor.defaultFormatter": "vscode.html-language-features"
    }
}

Create C, JavaScript, and HTML Files:

Now, create the following files for your project:

test.c: This C file contains the simple function that will be compiled to WebAssembly.

// test.c
int add(int lhs, int rhs) {
    return lhs + rhs;
}

test.html: This HTML file will load the WebAssembly module using JavaScript.

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>WebAssembly Example</title>
</head>

<body>
  <h1>WebAssembly Example</h1>
  <div id="output"></div>

  <script src="test.js"></script>
</body>

</html>

test.js: This JavaScript file will fetch the WebAssembly module and call the exported function.

// test.js
// Path to the .wasm file
const wasmFile = 'test.wasm';

// Load the WebAssembly module
fetch(wasmFile)
  .then(response => {
    if (!response.ok) {
      throw new Error(`Failed to load ${wasmFile}: ${response.statusText}`);
    }
    return response.arrayBuffer();
  })
  .then(bytes => WebAssembly.instantiate(bytes))
  .then(({ instance }) => {
    // Access exported functions
    const wasmExports = instance.exports;
    console.log({ wasmExports })

    // Example: Call a function exported from the WebAssembly module
    if (wasmExports.add) {
      const result = wasmExports.add(5, 3); // Example function call
      document.getElementById('output').textContent = `Result from WebAssembly: ${result}`;
    } else {
      document.getElementById('output').textContent = 'No "add" function found in the WebAssembly module.';
    }
  })
  .catch(error => {
    console.error('Error loading or running the WebAssembly module:', error);
    document.getElementById('output').textContent = 'Error loading WebAssembly module.';
  });

Now that you've set up all the necessary files and configurations, you can move on to compiling and interacting with WebAssembly.

The project structure looks like following now:

➜  wasm-web-example: tree . -a
.
├── .devcontainer
│   ├── Dockerfile
│   └── devcontainer.json
├── .vscode
│   ├── c_cpp_properties.json
│   └── settings.json
├── test.c
├── test.html
├── test.js

Compiling C Code to WebAssembly Using Emscripten

Basic C Program:

The file test.c contains a simple function add that adds two integers. We will compile this C function into WebAssembly using Emscripten.

// test.c
int add(int lhs, int rhs) {
    return lhs + rhs;
}

Emscripten Command:

Inside the dev container, open the terminal (use cmd+j in VSCode) and run the following Emscripten command to compile the C code to WebAssembly:

emcc test.c -O3 -s STANDALONE_WASM -s EXPORTED_FUNCTIONS='["_add"]' --no-entry -o test.wasm

Breakdown of the Command

emcc: This is the Emscripten C/C++ compiler command. It compiles C/C++ source files into WebAssembly or asm.js.
test.c: This specifies the input C source file that you want to compile.
-O3: This flag enables aggressive optimizations during the compilation process. The -O3 optimization level is typically used for performance-critical applications, as it applies various optimization techniques that can significantly improve runtime performance.
-s STANDALONE_WASM: This option instructs Emscripten to generate a standalone WebAssembly module. A standalone WASM module does not depend on any JavaScript glue code and can be executed independently in environments that support WebAssembly.
-s EXPORTED_FUNCTIONS='["_add"]': This flag specifies which functions from the C code should be exported and made available for calling from JavaScript. In this case, the function named _add will be accessible in the resulting WASM module.
--no-entry: This option tells the compiler that there is no entry point (like a main() function) in the program. This is useful for libraries or modules that are intended to be used by other code rather than executed directly.
-o test.wasm: This specifies the output file name for the compiled WebAssembly module. In this case, it will create a file named test.wasm.

This command will generate test.wasm, the WebAssembly binary, and ensure that the add function is exported for use in JavaScript.

Loading and Interacting with WebAssembly in the Browser

HTML Setup:

The file test.html contains a simple HTML page that loads the WebAssembly binary using JavaScript. The JavaScript code in test.js fetches the .wasm file and instantiates it.

<!-- test.html -->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>WebAssembly Example</title>
</head>

<body>
  <h1>WebAssembly Example</h1>
  <div id="output"></div>

  <script src="test.js"></script>
</body>

</html>

JavaScript Setup:

The JavaScript file test.js loads the test.wasm file and calls the exported add function:

// test.js
// Path to the .wasm file
const wasmFile = 'test.wasm';

// Load the WebAssembly module
fetch(wasmFile)
  .then(response => {
    if (!response.ok) {
      throw new Error(`Failed to load ${wasmFile}: ${response.statusText}`);
    }
    return response.arrayBuffer();
  })
  .then(bytes => WebAssembly.instantiate(bytes))
  .then(({ instance }) => {
    // Access exported functions
    const wasmExports = instance.exports;
    console.log({ wasmExports })

    // Example: Call a function exported from the WebAssembly module
    if (wasmExports.add) {
      const result = wasmExports.add(5, 3); // Example function call
      document.getElementById('output').textContent = `Result from WebAssembly: ${result}`;
    } else {
      document.getElementById('output').textContent = 'No "add" function found in the WebAssembly module.';
    }
  })
  .catch(error => {
    console.error('Error loading or running the WebAssembly module:', error);
    document.getElementById('output').textContent = 'Error loading WebAssembly module.';
  });

This will display the result of the add function in the HTML page when the module is loaded successfully.

Using External Tools on macOS

Outside the dev container, there are several useful commands you can run to work with WebAssembly on your Mac.

Install `wabt`:

wabt (WebAssembly Binary Toolkit) provides utilities for working with WebAssembly, including converting .wasm files to the human-readable WAT (WebAssembly Text) format. Install it via Homebrew:

brew install wabt

Convert WASM to WAT:

Once wabt is installed, you can use the wasm2wat tool to convert your WebAssembly binary (test.wasm) to the WAT format:

wasm2wat test.wasm

This will output a text representation of the WebAssembly module that you can read and inspect.

(module
  (type (;0;) (func))
  (type (;1;) (func (param i32 i32) (result i32)))
  (type (;2;) (func (param i32)))
  (type (;3;) (func (result i32)))
  (func (;0;) (type 0)
    nop)
  (func (;1;) (type 1) (param i32 i32) (result i32)
    local.get 0
    local.get 1
    i32.add)
  (func (;2;) (type 2) (param i32)
    local.get 0
    global.set 0)
  (func (;3;) (type 3) (result i32)
    global.get 0)
  (table (;0;) 2 2 funcref)
  (memory (;0;) 258 258)
  (global (;0;) (mut i32) (i32.const 66560))
  (export "memory" (memory 0))
  (export "add" (func 1))
  (export "_initialize" (func 0))
  (export "__indirect_function_table" (table 0))
  (export "_emscripten_stack_restore" (func 2))
  (export "emscripten_stack_get_current" (func 3))
  (elem (;0;) (i32.const 1) func 0))

Serve the HTML Page:

To view the HTML page that interacts with the WebAssembly module, you can use Python’s simple HTTP server:

python -m http.server

This command will start a local web server on http://localhost:8000, where you can open index.html in your browser to see the WebAssembly module in action.

Conclusion

By following the steps outlined in this article, you can set up a development environment to compile C code to WebAssembly, interact with it using JavaScript, and convert the resulting WebAssembly binary to the WAT format for inspection. The use of external tools like wabt and Python’s HTTP server makes it easier to manage and explore WebAssembly modules on your macOS system.

Functional Programming in Go with IBM fp-go: Error Handling Made Explicit

Piyush Chauhan — Fri, 27 Dec 2024 14:43:19 +0000

Functional programming (FP) principles are gaining popularity in modern software development due to their emphasis on immutability, composability, and explicitness. While Go is traditionally an imperative language, the fp-go library, developed by IBM, introduces FP abstractions such as Option, Either, Fold, and utilities for functional composition. In this article, we will explore how to use fp-go to handle errors explicitly, define function signatures with multiple error types, and build a real-world CRUD API example demonstrating these concepts.

Why Functional Error Handling?

Error handling is crucial for building reliable software. Traditional Go error handling relies on returning error values, which can be unintentionally ignored or mishandled. Functional error handling introduces abstractions like:

Option: Represents optional values, akin to Some and None in other FP languages.
Either: Encapsulates a value that can either be a Right (success) or Left (failure), making error propagation explicit.
Tagged Unions: Allow function signatures to clearly define possible error types.
Composition: Enables chaining operations while handling errors naturally.

Let’s dive into these concepts and see how fp-go facilitates them in Go.

Getting Started with fp-go

First, add fp-go to your Go project:

go get github.com/IBM/fp-go

Import the necessary modules:

import (
    either "github.com/IBM/fp-go/either"
    option "github.com/IBM/fp-go/option"
)

`Option`: Handling Optional Values

Option represents a value that may or may not exist. It is either Some(value) or None.

Example: Parsing an Integer

func parseInt(input string) option.Option[int] {
    value, err := strconv.Atoi(input)
    if err != nil {
        return option.None[int]()
    }
    return option.Some(value)
}

func main() {
    opt := parseInt("42")

    option.Fold(
        func() { fmt.Println("No value") },
        func(value int) { fmt.Printf("Parsed value: %d\n", value) },
    )(opt)
}

Key Takeaways:

Option eliminates nil values.
Fold is used to handle both cases (Some or None).

`Either`: Handling Errors Explicitly

Either represents a computation that can result in two possibilities:

Left: Represents an error.
Right: Represents a successful result.

Example: Safe Division

type MathError struct {
    Code    string
    Message string
}

func safeDivide(a, b int) either.Either[MathError, int] {
    if b == 0 {
        return either.Left(MathError{Code: "DIV_BY_ZERO", Message: "Cannot divide by zero"})
    }
    return either.Right(a / b)
}

func main() {
    result := safeDivide(10, 0)

    either.Fold(
        func(err MathError) { fmt.Printf("Error [%s]: %s\n", err.Code, err.Message) },
        func(value int) { fmt.Printf("Result: %d\n", value) },
    )(result)
}

Key Takeaways:

Either separates success and failure paths.
Fold simplifies handling both cases in one place.

Function Signatures with Multiple Error Types

Real-world applications often need to handle multiple types of errors. By using tagged unions, we can define explicit error types.

Example: Tagged Union for Errors

type AppError struct {
    Tag     string
    Message string
}

const (
    MathErrorTag    = "MathError"
    DatabaseErrorTag = "DatabaseError"
)

func NewMathError(msg string) AppError {
    return AppError{Tag: MathErrorTag, Message: msg}
}

func NewDatabaseError(msg string) AppError {
    return AppError{Tag: DatabaseErrorTag, Message: msg}
}

func process(a, b int) either.Either[AppError, int] {
    if b == 0 {
        return either.Left(NewMathError("Division by zero"))
    }
    return either.Right(a / b)
}

func main() {
    result := process(10, 0)

    either.Fold(
        func(err AppError) { fmt.Printf("Error [%s]: %s\n", err.Tag, err.Message) },
        func(value int) { fmt.Printf("Processed result: %d\n", value) },
    )(result)
}

Benefits:

Tagged unions make errors self-documenting.
Explicit types reduce ambiguity in error handling.

Real-World Example: CRUD API

Let’s implement a simple CRUD API with explicit error handling using Either.

Model and Error Definitions

type User struct {
    ID    int
    Name  string
    Email string
}

type AppError struct {
    Code    string
    Message string
}

const (
    NotFoundError    = "NOT_FOUND"
    ValidationError  = "VALIDATION_ERROR"
    DatabaseError    = "DATABASE_ERROR"
)

func NewAppError(code, message string) AppError {
    return AppError{Code: code, Message: message}
}

Repository Layer

var users = map[int]User{
    1: {ID: 1, Name: "Alice", Email: "alice@example.com"},
}

func getUserByID(id int) either.Either[AppError, User] {
    user, exists := users[id]
    if !exists {
        return either.Left(NewAppError(NotFoundError, "User not found"))
    }
    return either.Right(user)
}

Service Layer

func validateUser(user User) either.Either[AppError, User] {
    if user.Name == "" || user.Email == "" {
        return either.Left(NewAppError(ValidationError, "Name and email are required"))
    }
    return either.Right(user)
}

func createUser(user User) either.Either[AppError, User] {
    validation := validateUser(user)
    return either.Chain(
        func(validUser User) either.Either[AppError, User] {
            user.ID = len(users) + 1
            users[user.ID] = user
            return either.Right(user)
        },
    )(validation)
}

Controller

func handleGetUser(id int) {
    result := getUserByID(id)

    either.Fold(
        func(err AppError) { fmt.Printf("Error [%s]: %s\n", err.Code, err.Message) },
        func(user User) { fmt.Printf("User: %+v\n", user) },
    )(result)
}

func handleCreateUser(user User) {
    result := createUser(user)

    either.Fold(
        func(err AppError) { fmt.Printf("Error [%s]: %s\n", err.Code, err.Message) },
        func(newUser User) { fmt.Printf("Created user: %+v\n", newUser) },
    )(result)
}

func main() {
    handleGetUser(1)
    handleCreateUser(User{Name: "Bob", Email: "bob@example.com"})
    handleGetUser(2)
}

Conclusion

Using fp-go in Go, we can:

Model errors explicitly using Either.
Represent optional values with Option.
Handle multiple error types via tagged unions.
Build maintainable and composable APIs.

These patterns make your Go code more robust, readable, and functional. Whether you’re building a CRUD API or complex business logic, fp-go empowers you to handle errors cleanly and consistently.

Mastering Trampolining: A Deep Dive into Recursive Optimization

Piyush Chauhan — Wed, 25 Dec 2024 17:02:44 +0000

Mastering Trampolining: A Deep Dive into Recursive Optimization

In the world of programming, recursion is a powerful tool that allows functions to call themselves to solve complex problems. However, deep recursion can lead to stack overflow errors, especially in languages that do not optimize recursive calls. Enter trampolining, a technique that transforms recursive calls into an iterative process, allowing for infinite recursion without the risk of exhausting the call stack. In this article, we will explore trampolining in detail, providing implementations in multiple programming languages, including Java, C++, JavaScript, and Go.

Understanding Trampolining

What is Trampolining?

Trampolining is a method used to optimize recursive functions by converting them into iterations. Instead of a function calling itself directly, it returns another function (or "thunk") to be executed later. This allows the program to manage function calls without piling them up on the call stack.

Why Use Trampolining?

Using trampolining has several benefits:

Improved Performance: It enhances the execution speed of your code by converting recursive calls into iterations.
Preventing Stack Overflow: By avoiding deep recursion, it prevents stack overflow errors, especially in functions that call themselves repeatedly.

How Trampolining Works

The basic principle of trampolining involves converting recursive calls into iterations. Instead of a function calling itself directly, it returns another function to be executed. This process continues until a final value is produced.

Example Code

To illustrate how trampolining works, let's look at an example in JavaScript.

Before Trampolining:

function factorial(n) {
    if (n === 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

After Trampolining:

function trampoline(fn) {
    return function(...args) {
        let result = fn(...args);
        while (typeof result === 'function') {
            result = result();
        }
        return result;
    };
}

function factorial(n, acc = 1) {
    if (n === 0) {
        return acc;
    } else {
        return () => factorial(n - 1, n * acc);
    }
}

const trampolinedFactorial = trampoline(factorial);
console.log(trampolinedFactorial(5)); // Output: 120

Technical Explanation

Trampolining leverages continuations and tail-call optimization. Continuations allow the function to pause and resume, while tail-call optimization ensures that the function doesn’t add new frames to the call stack.

Preparing Your Functions

Not all functions need trampolining. Identify functions that involve deep recursion or are likely to cause stack overflow.

Refactoring for Trampolining

Identify the Recursive Function: Find the function that repeatedly calls itself.
Modify the Function: Change it to return another function instead of making a direct recursive call.
Wrap with a Trampoline: Use a trampoline function to execute the modified function iteratively.

Common Pitfalls and How to Avoid Them

Common pitfalls include infinite loops and performance overhead. Ensure your base case is correct to avoid infinite loops, and test and optimize performance as needed.

Advanced Trampolining Techniques

Trampolining can be further enhanced with techniques like memoization and lazy evaluation. These techniques can help improve performance further by caching results or delaying computations until necessary.

Real-World Applications

Many large-scale applications use trampolining to handle recursive tasks efficiently. Examples include:

Parsing Complex Data Structures: For instance, when dealing with nested JSON objects or XML.
Functional Programming Paradigms: Languages like Scala and Haskell often utilize trampolining for efficient recursion.

Implementing Trampolining in Other Languages

Java Implementation

In Java, trampolining can be implemented using interfaces or functional programming constructs available in Java 8 and later.

import java.util.function.Supplier;

public class TrampolineExample {

    public static <T> T trampoline(Supplier<T> supplier) {
        Supplier<T> current = supplier;
        while (current != null) {
            T result = current.get();
            if (result instanceof Supplier) {
                current = (Supplier<T>) result;
            } else {
                return result;
            }
        }
        return null;
    }

    public static Supplier<Integer> factorial(int n, int acc) {
        if (n == 0) {
            return () -> acc;
        } else {
            return () -> factorial(n - 1, n * acc);
        }
    }

    public static void main(String[] args) {
        int number = 5;
        int result = trampoline(() -> factorial(number, 1));
        System.out.println("Factorial of " + number + " is: " + result); // Output: 120
    }
}

C++ Implementation

In C++, trampolining can be achieved using std::function and lambda expressions.

#include <iostream>
#include <functional>

std::function<int()> trampoline(std::function<int()> func) {
    while (func) {
        func = func();
    }
    return nullptr;
}

std::function<int()> factorial(int n, int acc) {
    if (n == 0) {
        return [acc]() { return acc; };
    } else {
        return [n, acc]() { return factorial(n - 1, n * acc); };
    }
}

int main() {
    int number = 5;
    auto result = trampoline(factorial(number, 1));
    std::cout << "Factorial of " << number << " is: " << result() << std::endl; // Output: 120
}

Go Implementation with Generics

Go provides an elegant way to implement trampolining using generics introduced in Go 1.18.

package main

import (
    "fmt"
)

// Define the thunk type for generic functions
type thunk[T any] func() (T, thunk[T])

// Trampoline function that executes the supplied thunk
func trampoline[T any](fn thunk[T]) T {
    for {
        result, next := fn()
        if next == nil {
            return result // Final result
        }
        fn = next // Continue with the next thunk
    }
}

// Fibonacci function using trampolining with generics
func fib(n int, prev int, curr int) thunk[int] {
    if n == 0 {
        return func() (int, thunk[int]) {
            return prev, nil // Return final accumulated value
        }
    }
    if n == 1 {
        return func() (int, thunk[int]) {
            return curr, nil // Return final accumulated value
        }
    }
    return func() (int, thunk[int]) {
        return 0, fib(n-1, curr, curr+prev) // Return next step as a thunk
    }
}

func main() {
    n := 10 // fib(10) == 55
    fibThunk := fib(n, 0, 1) // Initialize with starting values
    result := trampoline(fibThunk)
    fmt.Printf("Fibonacci(%d) = %d\n", n, result) // Output: 55
}

Conclusion

Trampolining is a powerful technique for optimizing recursive functions across various programming languages. It improves performance and prevents stack overflow errors by transforming recursive calls into an iterative process. By mastering this technique and implementing it in your codebase—whether in JavaScript, Java, C++, or Go—you can enhance the robustness and efficiency of your applications.

As you explore more complex algorithms and data structures in your programming journey, consider incorporating trampolining where appropriate. This approach not only helps manage recursion effectively but also encourages cleaner and more maintainable code.

Happy coding!

Citations:
[1] https://rdinnager.github.io/trampoline/
[2] https://www.geeksforgeeks.org/es6-trampoline-function/
[3] https://gcc.gnu.org/onlinedocs/gccint/Trampolines.html