Full Width [alt+shift+f] FOCUS MODE Shortcuts [alt+shift+k]
Sign Up [alt+shift+s] Log In [alt+shift+l]
32
Bad code <img src="/images/edit.gif" onclick="openEditDialog(123)"> <img src="/images/delete.gif" onclick="openDeleteDialog(123)"> Issues and how to fix them The purpose of the img element is to display images, not to execute JavaScript. A click event on a img triggers only on click. A click event on a button triggers on click and if the user presses the Enter or Space key. There’s no text alternative for the image. Screen readers may announce the filename instead. Good code Solution #1: Use buttons and add alt attribute to images <button onclick="openEditDialog(123)"> <img src="/images/edit.gif" alt="Edit product XY"> </button> <button onclick="openDeleteDialog(123)"> <img src="/images/delete.gif" alt="Delete product XY"> </button> Solution #2: Use buttons, add text content and hide images Unfortunately, there’s no native way of hiding content only visually. The .sr-only class makes sure that content is visually hidden but still accessible to screen reader users. .sr-only { ...
over a year ago

Comments

Improve your reading experience

Logged in users get linked directly to articles resulting in a better reading experience. Please login for free, it takes less than 1 minute.

More from HTMHell

datalists are more powerful than you think

by Alexis Degryse I think we all know the <datalist> element (and if you don’t, it’s ok). It holds a list of <option> elements, offering suggested choices for its associated input field. It’s not an alternative for the <select> element. A field associated to a <datalist> can still allow any value that is not listed in the <option> elements. Here is a basic example: Pretty cool, isn't it? But what happens if we combine <datalist> with less common field types, like color and date: <label for="favorite-color">What is your favorite color?</label> <input type="color" list="colors-list" id="favorite-color"> <datalist id="colors-list"> <option>#FF0000</option> <option>#FFA500</option> <option>#FFFF00</option> <option>#008000</option> <option>#0000FF</option> <option>#800080</option> <option>#FFC0CB</option> <option>#FFFFFF</option> <option>#000000</option> </datalist> Colors listed in <datalist> are pre-selectable but the color picker is still usable by users if they need to choose a more specific one. <label for="event-choice" class="form-label col-form-label-lg">Choose a historical date</label> <input type="date" list="events" id="event-choice"> <datalist id="events"> <option label="Fall of the Berlin wall">1989-11-09</option> <option label="Maastricht Treaty">1992-02-07</option> <option label="Brexit Referendum">2016-06-23</option> </datalist> Same here: some dates are pre-selectable and the datepicker is still available. Depending on the context, having pre-defined values can possibly speed up the form filling by users. Please, note that <datalist> should be seen as a progressive enhancement because of some points: For Firefox (tested on 133), the <datalist> element is compatible only with textual field types (think about text, url, tel, email, number). There is no support for color, date and time. For Safari (tested on 15.6), it has support for color, but not for date and time. With some screen reader/browser combinations there are issues. For example, suggestions are not announced in Safari and it's not possible to navigate to the datalist with the down arrow key (until you type something matched with suggestions). Refer to a11ysupport.io for more. Find out more datalist experiment by Eiji Kitamura Documentation on MDN

8 months ago 88 votes
Boost website speed with prefetching and the Speculation Rules API

by Schepp Everybody loves fast websites, and everyone despises slow ones even more. Site speed significantly contributes to the overall user experience (UX), determining whether it feels positive or negative. To ensure the fastest possible page load times, it’s crucial to design with performance in mind. However, performance optimization is an art form in itself. While implementing straightforward techniques like file compression or proper cache headers is relatively easy, achieving deeper optimizations can quickly become complex. But what if, instead of solely trying to accelerate the loading process, we triggered it earlier—without the user noticing? One way to achieve this is by prefetching pages the user might navigate to next using <link rel="prefetch"> tags. These tags are typically embedded in your HTML, but they can also be generated dynamically via JavaScript, based on a heuristic of your choice. Alternatively, you can send them as an HTML Link header if you lack access to the HTML code but can modify the server configuration. Browsers will take note of the prefetch directives and fetch the referenced pages as needed. ⚠︎ Caveat: To benefit from this prefetching technique, you must allow the browser to cache pages temporarily using the Cache-Control HTTP header. For example, Cache-Control: max-age=300 would tell the browser to cache a page for five minutes. Without such a header, the browser will discard the pre-fetched resource and fetch it again upon navigation, rendering the prefetch ineffective. In addition to <link rel="prefetch">, Chromium-based browsers support <link rel="prerender">. This tag is essentially a supercharged version of <link rel="prefetch">. Known as "NoState Prefetch," it not only prefetches an HTML page but also scans it for subresources—stylesheets, JavaScript files, images, and fonts referenced via a <link rel="preload" as="font" crossorigin> — loading them as well. The Speculation Rules API A relatively new addition to Chromium browsers is the Speculation Rules API, which offers enhanced prefetching and enables actual prerendering of webpages. It introduces a JSON-based syntax for precisely defining the conditions under which preprocessing should occur. Here’s a simple example of how to use it: <script type="speculationrules"> { "prerender": [{ "urls": ["next.html", "next2.html"] }] } </script> Alternatively, you can place the JSON file on your server and reference it using an HTTP header: Speculation-Rules: "/speculationrules.json". The above list-rule specifies that the browser should prerender the URLs next.html and next2.html so they are ready for instant navigation. The keyword prerender means more than fetching the HTML and subresources—it instructs the browser to fully render the pages in hidden tabs, ready to replace the current page instantly when needed. This makes navigation to these pages feel seamless. Prerendered pages also typically score excellent Core Web Vital metrics. Layout shifts and image loading occur during the hidden prerendering phase, and JavaScript execution happens upfront, ensuring a smooth experience when the user first sees the page. Instead of listing specific URLs, the API also allows for pattern matching using where and href_matches keys: <script type="speculationrules"> { "prerender": [{ "where": { "href_matches": "/*" } }] } </script> For more precise targeting, CSS selectors can be used with the selector_matches key: <script type="speculationrules"> { "prerender": [{ "where": { "selector_matches": ".navigation__link" } }] } </script> These rules, called document-rules, act on link elements as soon as the user triggers a pointerdown or touchstart event, giving the referenced pages a few milliseconds' head start before the actual navigation. If you want the preprocessing to begin even earlier, you can adjust the eagerness setting: <script type="speculationrules"> { "prerender": [{ "where": { "href_matches": "/*" }, "eagerness": "moderate" }] } </script> Eagerness values: immediate: Executes immediately. eager: Currently behaves like immediate but may be refined to sit between immediate and moderate. moderate: Executes after a 200ms hover or on pointerdown for mobile devices. conservative (default): Speculates based on pointer or touch interaction. For even greater flexibility, you can combine prerender and prefetch rules with different eagerness settings: <script type="speculationrules"> { "prerender": [{ "where": { "href_matches": "/*" }, "eagerness": "conservative" }], "prefetch": [{ "where": { "href_matches": "/*" }, "eagerness": "moderate" }] } </script> Limitations and Challenges While the Speculation Rules API is powerful, it comes with some limitations: Browser support: Only Chromium-based browsers support it. Other browsers lack this capability, so treat it as a progressive enhancement. Bandwidth concerns: Over-aggressive settings could waste user bandwidth. Chromium imposes limits to mitigate this: a maximum of 10 prerendered and 50 prefetched pages with immediate or eager eagerness. Server strain: Poorly optimized servers (e.g., no caching, heavy database dependencies) may experience significant load increases due to excessive speculative requests. Compatibility: Prefetching won’t work if a Service Worker is active, though prerendering remains unaffected. Cross-origin prerendering requires explicit opt-in by the target page. Despite these caveats, the Speculation Rules API offers a powerful toolset to significantly enhance perceived performance and improve UX. So go ahead and try them out! I would like to express a big thank you to the Webperf community for always being ready to help with great tips and expertise. For this article, I would like to thank Barry Pollard, Andy Davies, and Noam Rosenthal in particular for providing very valuable background information. ❤️

8 months ago 94 votes
Misleading Icons: Icon-Only-Buttons and Their Impact on Screen Readers

by Alexander Muzenhardt Introduction Imagine you’re tasked with building a cool new feature for a product. You dive into the work with full energy, and just before the deadline, you manage to finish it. Everyone loves your work, and the feature is set to go live the next day. <button> <i class="icon">📆</i> </button> The Problem You find some good resources explaining that there are people with disabilities who need to be considered in these cases. This is known as accessibility. For example, some individuals have motor impairments and cannot use a mouse. In this particular case, the user is visually impaired and relies on assistive technology like a screen reader, which reads aloud the content of the website or software. The button you implemented doesn’t have any descriptive text, so only the icon is read aloud. In your case, the screen reader says, “Tear-Off Calendar button”. While it describes the appearance of the icon, it doesn’t convey the purpose of the button. This information is meaningless to the user. A button should always describe what action it will trigger when activated. That’s why we need additional descriptive text. The Challenge Okay, you understand the problem now and agree that it should be fixed. However, you don’t want to add visible text to the button. For design and aesthetic reasons, sighted users should only see the icon. Is there a way to keep the button “icon-only” while still providing a meaningful, descriptive text for users who rely on assistive technologies like screen readers? The Solution First, you need to give the button a descriptive name so that a screen reader can announce it. <button> <span>Open Calendar</span> <i class="icon">📆</i> </button> The problem now is that the button’s name becomes visible, which goes against your design guidelines. To prevent this, additional CSS is required. .sr-only { position: absolute; width: 1px; height: 1px; padding: 0; margin: -1px; overflow: hidden; clip: rect(0, 0, 0, 0); white-space: nowrap; border-width: 0; } <button> <span class="sr-only">Open Calendar</span> <i class="icon">📆</i> </button> The CSS ensures that the text inside the span-element is hidden from sighted users but remains readable for screen readers. This approach is so common that well-known CSS libraries like TailwindCSS, Bootstrap, and Material-UI include such a class by default. Although the text of the buttons is not visible anymore, the entire content of the button will be read aloud, including the icon — something you want to avoid. In HTML you are allowed to use specific attributes for accessibility, and in this case, the attribute aria-hidden is what you need. ARIA stands for “Accessible Rich Internet Applications” and is an initiative to make websites and software more accessible to people with disabilities. The attribute aria-hidden hides elements from screen readers so that their content isn’t read. All you need to do is add the attribute aria-hidden with the value “true” to the icon element, which in this case is the “i”-element. <button> <span class="sr-only">Open Calendar</span> <i class="icon" aria-hidden="true">📆</i> </button> Alternative An alternative is the attribute aria-label, which you can assign a descriptive, accessible text to a button without it being visible to sighted users. The purpose of aria-label is to provide a description for interactive elements that lack a visible label or descriptive text. All you need to do is add the attribute aria-label to the button. The attribute aria-hidden and the span-Element can be deleted. <button aria-label="Open Calendar"> <i class="icon">📆</i> </button> With this adjustment, the screen reader will now announce “Open calendar,” completely ignoring the icon. This clearly communicates to the user what the button will do when clicked. Which Option Should You Use? At first glance, the aria-label approach might seem like the smarter choice. It requires less code, reducing the likelihood of errors, and looks cleaner overall, potentially improving code readability. However, the first option is actually the better choice. There are several reasons for this that may not be immediately obvious: Some browsers do not translate aria-label It is difficult to copy aria-label content or otherwise manipulated it as text aria-label content will not show up if styles fail to load These are just a few of the many reasons why you should be cautious when using the aria-label attribute. These points, along with others, are discussed in detail in the excellent article "aria-label is a Code Smell" by Eric Bailey. The First Rule of ARIA Use The “First Rule of ARIA Use” states: If you can use a native HTML element or attribute with the semantics and behavior you require already built in, instead of re-purposing an element and adding an ARIA role, state or property to make it accessible, then do so. Even though the first approach also uses an ARIA attribute, it is more acceptable because aria-hidden only hides an element from screen readers. In contrast, aria-label overrides the standard HTML behavior for handling descriptive names. For this reason, following this principle, aria-hidden is preferable to aria-label in this case. Browser compatibility Both aria-label and aria-hidden are supported by all modern browsers and can be used without concern. Conclusion Ensuring accessibility in web design is more than just a nice-to-have—it’s a necessity. By implementing simple solutions like combining CSS with aria-hidden, you can create a user experience that is both aesthetically pleasing and accessible for everyone, including those who rely on screen readers. While there may be different approaches to solving accessibility challenges, the key is to be mindful of all users' needs. A few small adjustments can make a world of difference, ensuring that your features are truly usable by everyone. Cheers Resources / Links Unicode Character “Tear-Off Calendar” comport Unicode Website mdn web docs aria-label mdn web docs aria-hidden WAI-ARIA Standard Guidlines Tailwind CSS Screen Readers (sr-only) aria-label is a Code Smell First Rule of ARIA Use

8 months ago 74 votes
The underrated &lt;dl&gt; element

by David Luhr The Description List (<dl>) element is useful for many common visual design patterns, but is unfortunately underutilized. It was originally intended to group terms with their definitions, but it's also a great fit for other content that has a key/value structure, such as product attributes or cards that have several supporting details. Developers often mark up these patterns with overused heading or table semantics, or neglect semantics entirely. With the Description List (<dl>) element and its dedicated Description Term (<dt>) and Description Definition (<dd>) elements, we can improve the semantics and accessibility of these design patterns. The <dl> has a unique content model: A parent <dl> containing one or more groups of <dt> and <dd> elements Each term/definition group can have multiple <dt> (Description Term) elements per <dd> (Description Definition) element, or multiple definitions per term The <dl> can optionally accept a single layer of <div> to wrap the <dt> and <dd> elements, which can be useful for styling Examples An initial example would be a simple list of terms and definitions: <dl> <dt>Compression damping</dt> <dd>Controls the rate a spring compresses when it experiences a force</dd> <dt>Rebound damping</dt> <dd>Controls the rate a spring returns to it's extended length after compressing</dd> </dl> A common design pattern is "stat callouts", which feature mini cards of small label text above large numeric values. The <dl> is a great fit for this content: <dl> <div> <dt>Founded</dt> <dd>1988</dd> </div> <div> <dt>Frames built</dt> <dd>8,678</dd> </div> <div> <dt>Race podiums</dt> <dd>212</dd> </div> </dl> And, a final example of a product listing, which has a list of technical specs: <h2>Downhill MTB</h2> <dl> <div> <dt>Front travel:</dt> <dd>160mm</dd> </div> <div> <dt>Wheel size:</dt> <dd>27.5"</dd> </div> <div> <dt>Weight:</dt> <dd>15.2 kg</dd> </div> </dl> Accessibility With this markup in place, common screen readers will convey important semantic and navigational information. In my testing, NVDA on Windows and VoiceOver on MacOS conveyed a list role, the count of list items, your position in the list, and the boundaries of the list. TalkBack on Android only conveyed the term and definition roles of the <dt> and <dd> elements, respectively. If the design doesn't include visible labels, you can at least include them as visually hidden text for assistive technology users. But, I always advocate to visually display them if possible. Wrapping up The <dl> is a versatile element that unfortunately doesn't get much use. In over a decade of coding, I've almost never encountered it in existing codebases. It also doesn't appear anywhere in the top HTML elements lists in the Web Almanac 2024 or an Advanced Web Ranking study of over 11.3 million pages. The next time you're building out a design, look for opportunities where the underrated Description List is a good fit. To go deeper, be sure to check out this article by Ben Myers on the <dl> element.

8 months ago 75 votes
Preloading fonts for web performance with link rel=”preload”

by Alistair Shepherd Web performance is incredibly important. If you were here for the advent calendar last year you may have already read many of my thoughts on the subject. If not, read Getting started with Web Performance when you’re done here! This year I’m back for more web performance, this time focusing on my favourite HTML snippet for improving the loading performance of web fonts using preloads. This short HTML snippet added to the head of your page, can make a substantial improvement to both perceived and measured performance. <link rel="preload" href="/nova-sans.woff2" as="font" type="font/woff2" crossorigin="anonymous" > Above we have a link element that instructs the browser to preload the /nova-sans.woff2 font. By preloading your critical above-the-fold font we can make a huge impact by reducing potential flashes of unstyled or invisible text and layout shifts caused by font loading, like here in the following video: Recording of a page load illustrating how a font loading late can result in a jarring layout shift How web fonts are loaded To explain how preloading fonts can make such an impact, let’s go through the process of how web fonts are loaded. Font files are downloaded later than you may think, due to a combination of network requests and conservative browser behaviour. In a standard web page, there will be the main HTML document which will include a CSS file using a link element in the head. If you’re using self-hosted custom fonts you’ll have a @font-face rule within your CSS that specifies the font name, the src, and possibly some other font-related properties. In other CSS rules you specify a font-family so elements use your custom font. Once our browser encounters our page it: Starts streaming the HTML document, parsing it as it goes Encounters the link element pointing to our CSS file Starts downloading that CSS file, blocking the render of the page until it’s complete Parses and applies the contents of that file Finds the @font-face rule with our font URL Okay let’s pause here for a moment — It may make sense for step 6 to be “Starts downloading our font file”, however that’s not the case. You see, if a browser downloaded every font within a CSS file when it first encountered them, we could end up loading much more than is needed. We could be specifying fonts for multiple different weights, italics, other character sets/languages, or even multiple different fonts. If we don’t need all these fonts immediately it would be wasteful to download them all, and doing so may slow down higher priority CSS or JS. Instead, the browser is more conservative and simply takes note of the font declaration until it’s explicitly needed. The browser next: Takes a note of our @font-face declarations and their URLs for later Finishes processing CSS and starts rendering the page Discovers a piece of text on the page that needs our font Finally starts downloading our font now it knows it’s needed! So as we can see there’s actually a lot that happens between our HTML file arriving in the browser and our font file being downloaded. This is ideal for lower priority fonts, but for the main or headline font this process can make our custom font appear surprisingly late in the page load. This is what causes the behaviour we saw in the video above, where the page starts rendering but it takes some time before our custom font appears. A waterfall graph showing how our custom ‘lobster.woff2’ font doesn’t start being downloaded until 2 seconds into the page load and isn’t available until after 3 seconds This is an intentional decision by browser makers and spec writers to ensure that pages with lots of fonts aren’t badly impacted by having to load many font files ahead of time. But that doesn’t mean it can’t be optimised! Preloading our font with a link <link rel="preload" href="/nova-sans.woff2" as="font" type="font/woff2" crossorigin="anonymous" > The purpose of my favourite HTML snippet is to inform the browser that this font file will be needed with high priority, before it even has knowledge of it. We’re building our page and know more about how our fonts are used — so we can provide hints to be less conservative! If we start downloading the font as soon as possible then it can be ready ahead of when the browser ‘realises’ it’s needed. Looking back at our list above, by adding a preload we move the start of the font download from step 9 to step 2! Starts streaming the HTML document, parsing it as it goes Encounters our preload and starts downloading our font file in the background Encounters the link element pointing to our CSS file Continues as above Taking a closer look at the snippet, we’re using a link element and rel="preload" to ask the browser to preload a file with the intention of using it early in the page load. Like a CSS file, we provide the URL with the href attribute. We use as="font" and type="font/woff2" to indicate this is a font file in woff2. For modern browsers woff2 is the only format you need as it’s universally supported. Finally there’s crossorigin="anonymous". This comes from the wonderfully transparent and clear world of Cross Origin Resource Sharing. I jest of course, CORS is anything but transparent and clear! For fonts you almost always want crossorigin="anonymous" on your link element, even when the request isn’t cross-origin. Omitting this attribute would mean our preload wouldn’t be used and the file would be requested again. But why? Browser requests can be sent either with or without credentials (cookies, etc), and requests to the same URL with and without credentials are fundamentally different. For a preload to be used by the browser, it needs to match the type of request that the browser would have made normally. By default fonts are always requested without credentials, so we need to add crossorigin="anonymous" to ensure our preload matches a normal font request. By omitting this attribute our preload would not be used and the browser would request the font again. If you’re ever unsure of how your preloads are working, check your browsers’ devtools. In Chrome the Network pane will show a duplicate request, and the Console will log a warning telling you a preload wasn’t used. Screenshot showing the Chrome devtools Console pane, with warnings for an incorrect font preload Result and conclusion By preloading our critical fonts we ensure our browser has the most important fonts available earlier in the page loading process. We can see this by comparing our recording and waterfall charts from earlier: Side-by-side recording of the same page loading in different ways. ‘no-preload’ shows a large layout shift caused by the font switching and finishes loading at 4.4s. ‘preload’ doesn’t have a shift and finishes loading at 3.1s. Side-by-side comparison of two waterfall charts of the same site with font file `lobster.woff2`. For the ‘no-preload’ document the font loads after all other assets and finishes at 3s. The ‘preload’ document shows the font loading much earlier, in parallel with other files and finishing at 2s. As I mentioned in Getting started with Web Performance, it’s best to use preloads sparingly so limit this to your most important font or two. Remember that it’s a balance. By preloading too many resources you run the risk of other high-priority resources such as CSS being slowed down and arriving late. I would recommend preloading just the heading font to start with. With some testing you can see if preloading your main body font is worth it also! With care, font preloads can be a simple and impactful optimisation opportunity and this is why it’s my favourite HTML snippet! This is a great step to improving font loading, and there are plenty of other web font optimisations to try also!

8 months ago 77 votes

More in programming

Understanding Bazel remote caching

A deep dive into the Action Cache, the CAS, and the security issues that arise from using Bazel with a remote cache but without remote execution

4 hours ago 2 votes
Apologies and forgiveness

The first in a series of posts about doing things the right way

3 hours ago 2 votes
Trying to Make Sense of Casing Conventions on the Web

(I present to you my stream of consciousness on the topic of casing as it applies to the web platform.) I’m reading about the new command and commandfor attributes — which I’m super excited about, declarative behavior invocation in HTML? YES PLEASE!! — and one thing that strikes me is the casing in these APIs. For example, the command attribute has a variety of values in HTML which correspond to APIs in JavaScript. The show-popover attribute value maps to .showPopover() in JavaScript. hide-popover maps to .hidePopover(), etc. So what we have is: lowercase in attribute names e.g. commandfor="..." kebab-case in attribute values e.g. show-popover camelCase for JS counterparts e.g. showPopover() After thinking about this a little more, I remember that HTML attributes names are case insensitive, so the browser will normalize them to lowercase during parsing. Given that, I suppose you could write commandFor="..." but it’s effectively the same. Ok, lowercase attribute names in HTML makes sense. The related popover attributes follow the same convention: popovertarget popovertargetaction And there are many other attribute names in HTML that are lowercase, e.g.: maxlength novalidate contenteditable autocomplete formenctype So that all makes sense. But wait, there are some attribute names with hyphens in them, like aria-label="..." and data-value="...". So why isn’t it command-for="..."? Well, upon further reflection, I suppose those attributes were named that way for extensibility’s sake: they are essentially wildcard attributes that represent a family of attributes that are all under the same namespace: aria-* and data-*. But wait, isn’t that an argument for doing popover-target and popover-target-action? Or command and command-for? But wait (I keep saying that) there are kebab-case attribute names in HTML — like http-equiv on the <meta> tag, or accept-charset on the form tag — but those seem more like legacy exceptions. It seems like the only answer here is: there is no rule. Naming is driven by convention and decisions are made on a case-by-case basis. But if I had to summarize, it would probably be that the default casing for new APIs tends to follow the rules I outlined at the start (and what’s reflected in the new command APIs): lowercase for HTML attributes names kebab-case for HTML attribute values camelCase for JS counterparts Let’s not even get into SVG attribute names We need one of those “bless this mess” signs that we can hang over the World Wide Web. Email · Mastodon · Bluesky

yesterday 5 votes
The Angels and Demons of Nondeterminism

Greetings everyone! You might have noticed that it's September and I don't have the next version of Logic for Programmers ready. As penance, here's ten free copies of the book. So a few months ago I wrote a newsletter about how we use nondeterminism in formal methods. The overarching idea: Nondeterminism is when multiple paths are possible from a starting state. A system preserves a property if it holds on all possible paths. If even one path violates the property, then we have a bug. An intuitive model of this is that for this is that when faced with a nondeterministic choice, the system always makes the worst possible choice. This is sometimes called demonic nondeterminism and is favored in formal methods because we are paranoid to a fault. The opposite would be angelic nondeterminism, where the system always makes the best possible choice. A property then holds if any possible path satisfies that property.1 This is not as common in FM, but it still has its uses! "Players can access the secret level" or "We can always shut down the computer" are reachability properties, that something is possible even if not actually done. In broader computer science research, I'd say that angelic nondeterminism is more popular, due to its widespread use in complexity analysis and programming languages. Complexity Analysis P is the set of all "decision problems" (basically, boolean functions) can be solved in polynomial time: there's an algorithm that's worst-case in O(n), O(n²), O(n³), etc.2 NP is the set of all problems that can be solved in polynomial time by an algorithm with angelic nondeterminism.3 For example, the question "does list l contain x" can be solved in O(1) time by a nondeterministic algorithm: fun is_member(l: List[T], x: T): bool { if l == [] {return false}; guess i in 0..<(len(l)-1); return l[i] == x; } Say call is_member([a, b, c, d], c). The best possible choice would be to guess i = 2, which would correctly return true. Now call is_member([a, b], d). No matter what we guess, the algorithm correctly returns false. and just return false. Ergo, O(1). NP stands for "Nondeterministic Polynomial". (And I just now realized something pretty cool: you can say that P is the set of all problems solvable in polynomial time under demonic nondeterminism, which is a nice parallel between the two classes.) Computer scientists have proven that angelic nondeterminism doesn't give us any more "power": there are no problems solvable with AN that aren't also solvable deterministically. The big question is whether AN is more efficient: it is widely believed, but not proven, that there are problems in NP but not in P. Most famously, "Is there any variable assignment that makes this boolean formula true?" A polynomial AN algorithm is again easy: fun SAT(f(x1, x2, …: bool): bool): bool { N = num_params(f) for i in 1..=num_params(f) { guess x_i in {true, false} } return f(x_1, x_2, …) } The best deterministic algorithms we have to solve the same problem are worst-case exponential with the number of boolean parameters. This a real frustrating problem because real computers don't have angelic nondeterminism, so problems like SAT remain hard. We can solve most "well-behaved" instances of the problem in reasonable time, but the worst-case instances get intractable real fast. Means of Abstraction We can directly turn an AN algorithm into a (possibly much slower) deterministic algorithm, such as by backtracking. This makes AN a pretty good abstraction over what an algorithm is doing. Does the regex (a+b)\1+ match "abaabaabaab"? Yes, if the regex engine nondeterministically guesses that it needs to start at the third letter and make the group aab. How does my PL's regex implementation find that match? I dunno, backtracking or NFA construction or something, I don't need to know the deterministic specifics in order to use the nondeterministic abstraction. Neel Krishnaswami has a great definition of 'declarative language': "any language with a semantics has some nontrivial existential quantifiers in it". I'm not sure if this is identical to saying "a language with an angelic nondeterministic abstraction", but they must be pretty close, and all of his examples match: SQL's selects and joins Parsing DSLs Logic programming's unification Constraint solving On top of that I'd add CSS selectors and planner's actions; all nondeterministic abstractions over a deterministic implementation. He also says that the things programmers hate most in declarative languages are features that "that expose the operational model": constraint solver search strategies, Prolog cuts, regex backreferences, etc. Which again matches my experiences with angelic nondeterminism: I dread features that force me to understand the deterministic implementation. But they're necessary, since P probably != NP and so we need to worry about operational optimizations. Eldritch Nondeterminism If you need to know the ratio of good/bad paths, the number of good paths, or probability, or anything more than "there is a good path" or "there is a bad path", you are beyond the reach of heaven or hell. Angelic and demonic nondeterminism are duals: angelic returns "yes" if some choice: correct and demonic returns "no" if !all choice: correct, which is the same as some choice: !correct. ↩ Pet peeve about Big-O notation: O(n²) is the set of all algorithms that, for sufficiently large problem sizes, grow no faster that quadratically. "Bubblesort has O(n²) complexity" should be written Bubblesort in O(n²), not Bubblesort = O(n²). ↩ To be precise, solvable in polynomial time by a Nondeterministic Turing Machine, a very particular model of computation. We can broadly talk about P and NP without framing everything in terms of Turing machines, but some details of complexity classes (like the existence "weak NP-hardness") kinda need Turing machines to make sense. ↩

yesterday 5 votes
Announcing the 2025 TokyoDev Developers Survey

The 2025 edition of the TokyoDev Developer Survey is now live! If you’re a software developer living in Japan, please take a few minutes to participate. All questions are optional, and it should take less than 10 minutes to complete. The survey will remain open until September 30th. Last year, we received over 800 responses. Highlights included: Median compensation remained stable. The pay gap between international and Japanese companies narrowed to 47%. Fewer respondents had the option to work fully remotely. For 2025, we’ve added several new questions, including a dedicated section on one of the most talked-about topics in development today: AI. The survey is completely anonymous, and only aggregated results will be shared—never personally identifiable information. The more responses we get, the deeper and more meaningful our insights will be. Please help by taking the survey and sharing it with your peers!

yesterday 8 votes