⟨ortho|normal⟩

Categories

Computer Touching
Miscellany
Outside
Type Theory
Unicode

Notes on Guarded Types

Overview

Work Summary
Nakano1 STLC + recursive types + guarded types
Birkdeal, Møgelberg, Schwinghammer, Stovring2 dependent types + recursive types + guarded types
Atkey and McBride3 STLC + recursive types + guarded types + clocks
Birkedal and Møgelberg4 dependent types + guarded types
Møgelberg5 dependent types + guarded types + clocks
GDTT6 dependent types + guarded types + clocks + delayed substitution
CloTT7 dependent types + guarded types + ticks + clocks
GCTT8 cubical type theory + guarded types + delayed substitution
TCTT9 cubical type theory + guarded types + ticks
CCTT10 cubical type theory + guarded types + ticks + clocks
  1. Nakano, Hiroshi. A Modality for Recursion. (LICS 2000). ᴅᴏɪ: 10.1109/lics.2000.855774

  2. Birkedal, Lars; Møgelberg, Rasmus Ejlers; Schwinghammer, Jans; Stovring, Kristian. First Steps in Synthetic Guarded Domain Theory: .Step-Indexing in the Topos of Trees. (LICS 2011). ᴅᴏɪ: 10.1109/LICS.2011.16

  3. Atkey, Robert; McBride, Conor. Productive Coprogramming with Guarded Recursion. (ICFP 2013). ᴅᴏɪ: 10.1145/2500365.2500597

  4. Birkedal, Lars; Møgelberg, Rasmus Ejlers. Intensional Type Theory with Guarded Recursive Types qua Fixed Points on Universes. (LICS 2013). ᴅᴏɪ: 10.1109/LICS.2013.27

  5. Møgelberg, Rasmus Ejlers. A type theory for productive coprogramming via guarded recursion. (LICS 2014). ᴅᴏɪ: 10.1145/2603088.2603132

  6. Bizjak, Aleš; Grathwohl, Hans Bugge; Clouston, Ranald; Møgelberg, Rasmus Ejlers; Birkedal, Lars. Guarded Dependent Type Theory with Coinductive Types. (FoSSaCS 2016). ᴅᴏɪ: 10.1007/978-3-662-49630-5_2

  7. Bahr, Patrick; Grathwohl, Hans Bugge; Møgelberg, Rasmus Ejlers. The Clocks Are Ticking: No More Delays! (LICS 2017). ᴅᴏɪ: 10.1109/LICS.2017.8005097

  8. Birkedal, Lars; Bizjak, Aleš; Clouston, Ranald; Grathwohl, Hans Bugge; Spitters, Bas; Vezzosi, Andrea. Guarded Cubical Type Theory. (Journal of Automated Reasoning, 2019). ᴅᴏɪ: 10.1007/s10817-018-9471-7

  9. Møgelberg, Rasmus Ejlers; Veltri, Niccolò. Bisimulation as Path Type for Guarded Recursive Types. (POPL 2019). ᴅᴏɪ: 10.1145/3290317

  10. Kristensen, Magnus Baunsgaard; Møgelberg, Rasmus Ejlers; Vezzosi, Andrea. Greatest HITs: Higher inductive types in coinductive definitions via induction under clocks. (LICS 2022). ᴅᴏɪ: 10.1145/3531130.3533359

More …

Lossless Image File Formats

This was originally a two-part post on cohost.

Recently I needed to convert a large TIFF scan of a duochrome page into something reasonable, i.e. a web-supported image format that was still lossless since it seemed a shame to ruin such a nice high-definition scan with lossy compression. In terms of lossless formats, all browsers1 support PNG, WEBP, and AVIF, while I really hope JXL support is imminent.

I therefore wanted to see which file format would perform the best in terms of file size by converting my ~183 MiB TIFF to each of them using ImageMagick. For PNG, WEBP, and JXL, there’s an effort setting: lower effort means faster compression but larger size, while higher effort means slower compression but smaller size. I used the highest three settings for these, yielding sizes from ~50 MiB to ~20 MiB. (As a treat, I’ve also converted to JPG, WEBP, AVIF, and JXL at -quality 0, i.e. lossy with the worst settings.)

  1. Except Edge doesn’t support AVIF, but who cares about Edge? 

More …

Little Shops in Philadelphia

I’ve previously posted about my favourite ice cream shops in Philadelphia, but there’s a ton of other great little shops to visit. Here’s a few that I’ve really liked, sorted into two categories: used bookstores and vintage/oddities. I’ve excluded all food places, including coffeeshops, roasteries, bakeries, dessert shops, grocers, markets, food trucks, and so on, because there are just too many of them.

More …

What's in a GIF?

This was originally a multi-part post on cohost.

I wanted to inspect the structure of an animated GIF, so I created a 1 px × 1 px monochrome animation that switches from white to black every 1024 milliseconds in GNU IMP, exported it as an animated GIF with disposal method “combine”, and hexdumped it. Here’s the GIF below, at the center of this 1rem box so you can see it.

More …

Ice Cream Shops in Philadelphia

When I arrived in Philadelphia, I started a Tweet thread of ice cream shops that are or aren’t as good as Rain or Shine back in Vancouver, which was the ice cream place I frequented most often since they have a location on the UBC campus. (I don’t have a thread or a list for ice cream shops in Vancouver, but you really can’t go wrong with Rain or Shine or with Earnest.)

Here I collect a list of the shops that are as good as Rain or Shine, ordered from west to east.

More …