AFAIK

Valar Morghulis

Indeed, there are a bunch of formats available. Just list a few popular choices here:

  • JSON. Everyone who reads this post right now should have know it :)
  • INI. Do you know there is an operating system, called Windows?
  • YAML. Examples are Kubernetes, Jekyll, and CircleCI.
  • TOML. Examples are PEP 621, which introduces pyproject.toml to Python, and Cargo, which uses Cargo.toml to configure every Rust crate.
  • XML. Examples are Apache Hadoop and Apache Ant.

(Thanks to ChatGPT for providing some of the examples.)

I'd like to put the related formats into four categories, roughly based on the expressivity:

  • Lightweight configuration formats. Examples are JSON, INI, TOML, XML. There are basically human-readable serialization of dictionaries/lists.
  • Medium weight configuration formats. Examples are YAML, OmegaConf. These are more complex (in the sense that templating is possible to some extent) but not fully-fledged.
  • Heavyweight configuration formats. Examples are Nickel, Dhall, Jsonnet, Pkl and RCL. They introduce variables and function, becoming serious Domain-Specific Languages. Some of them are even Turing-complete.
  • General programming languages. Examples are Python (JupyterHub), Lua (WezTerm , neovim), VimL (Vim), Emacs Lisp (Emacs), and even Haskell (xmonad). What I find out is that these projects usually need to define functions/callbacks. I won't discuss them in this post.

Here is a comment from HackerNews, which has a similar classification:

  • Level 1 is just values in a file. The Linux kernel uses that.
  • Level 2 is a list of values, e.g. ini files.
  • Level 3 allows nesting. JSON, XML, and YAML are here.
  • Level 4 allows computation but limited. Dhall and Starlark are here.
  • Level 5 is a Turing-complete language. Python, Javascript, etc.
Read more »

这部剧也不新了。之前早就听说过它的人气,前几天终于抽了个时间把这部剧看了,感觉对得起我对它的期望。这里随手记录一下看过的感受,里面涉及对漫长的季节,Odd Taxi,Manchester by the Sea,The Invisible Guest 和 白夜行 的剧情讨论,没看过的还请绕道。

Read more »

不知怎么的这几天突然想起了沉淀文学,于是自己也玩个梗随便写点东西,顺便把这半个小时水出来的东西当做新年第一篇了 →_→

另外这里的“沉淀”不太会翻译了,ChatGPT 给我翻译成了 accumulation,我个人也感觉挺好的,不知道有没有更好的。

新年快乐 :)

Read more »

从王子屯出发,绕第二城旋转将近一周半后利用重力弹弓前往高树 —— 这就是旅行者号的故事。

在芝加哥待了一阵,因为某些原因最后还是跑路了。这次索性玩把大的。临别芝加哥之际,我发了个票圈文案记录一下,就是上面那句话。这个文案写的特别隐晦,甚至这位聪明的小脑瓜都没看懂:

聪明的小脑瓜

但是我个人还是很满意的,所以专门写了一个官方解读。当时写文案的时候就想着能不能模仿三体里云天明的童话故事的画风,写一个小故事来描述我这一段经历。后来一来不是很想说前东家里发生的事(无可奉告),二来确实这经历也乏善可陈,就只写了一两句话了。之后等我经历更加丰富了,或许也能写出一个云天明的童话故事类似的故事。

Read more »

\(\newcommand{\lpf}{\textnormal{lpf}} \newcommand{\eps}{\varepsilon}\) 之前做 PE 的时候看到一个很有用的数论技巧:令 \(\lpf(x)\) 表示 \(x\) 的最大质因数,我们考虑把 \([n]\) 分成按照 \(\frac{x}{\lpf(x)}\) 来分类,即 \(S_k = \{x: x / \lpf(x) = k\}\),然后每一个 \(S_t\) 单独处理。举个例子,假设我们要求一个积性函数 \(f\) 的前缀和 \(F(x) := \sum\limits_{n=1}^x f(n)\),那么对于一个 \(S_k\),它里面的数的函数和为: \[ \sum_{n \leq x: n / \lpf(n) = k} f(n) = f(k \lpf(k)) + \sum_{\lpf(k) < p \leq x / k} f(kp) = f(k \lpf(k)) + f(k) \sum_{\lpf(k) < p \leq x / k} f(p). \] 后者只要知道形如 \(\tilde F(x) := \sum\limits_{p \leq x} f(p)\) 这样的和就可以了,而这个是有经典解法的。这个算法的更详细的介绍请参考 The prefix-sum of multiplicative function: the black algorithm关于一种积性函数前缀和的通用筛法的时间复杂度证明 - 知乎

显然,这个算法的整体复杂度取决于 \(\tilde F\) 的计算复杂度和有多少个不同的 \(k\)。由于每个问题的 \(f\) 性质不同,\(\tilde F\) 的复杂度会有不同,但是后者相对独立。这里我们就开始研究有多少个不同的 \(k\),即 \(Q_x := \#\{n / \lpf(n): n \leq x\} = \#\{k: k \lpf(k) \leq x\}\) 的大小。

Read more »

注:这篇文章前半部分是八月底写的,后半部分想着别烂尾了所以十一月初才写的,看内容详尽程度明显可以看出来……(活动是七月底举办的,拖延程度可见一斑)

一年一度的 SIGYAO30 又要开办啦!今年的 SIGYAO30 定在西雅图,一来大家都还没去过西雅图,二来刚好有几个人在这里工作。

Read more »

前几天和同事聊天,聊到前几天的北京数学高考题。最后一个题还挺有意思的,我和同事 yy 了好久都不会:

给定两个序列 \(\{a_i\}, \{b_i\} \in [n]^n\),证明存在四个正整数 \(l_a \leq r_a, l_b \leq r_b\) 使得 \[\sum_{i=l_a}^{r_a} a_i = \sum_{i = l_b}^{r_b} b_i.\]

在想这个题的时候,我想到了曾经做 POI 的时候见过的一个题:

给定一个大小为 \(n\) 的序列 \(a\),其中 \(a_i \in \{1, 2\}\)

现在有 \(m\) 个询问,每次给定一个 \(k\),要你找出一个和为 \(k\) 的子段,或者输出不存在。

数据范围为 \(n \leq 10^7, k \leq 10^5\)

Read more »

前几天在逛 论坛 的时候看到这么一句话:

Overloading in combination with Hindley-Milner is NP-complete.

后面的 Hinley-Milner 我不太懂,只知道是 Haskell 用的东西。但是前面这个 overloading 我还是知道是啥的。于是我就一时兴起,找到了这么一篇 文章,就证明在某种情况下,overloading 是 NP-complete 的。看起来这是 Programming Language (PL)领域的一个基础题:

In the 1986 version of the Dragon book, Exercise 6.25 is to show that overloading is NPcomplete: **6.25 The resolution of overloading becomes more difficult if identifier declarations are optional. More precisely, suppose that declarations can be used to overload identifiers representing function symbols, but that all occurrences of an undeclared identifier have the same type. Show that the problem of determining if an expression in this language has a valid type is NP-complete.

然而,作为一个完全没接触过 PL 的小白,我连里面的 notation 都看不懂,后来在 Understanding typing judgments 这篇文章的帮助下终于理解了之前的那篇文章在干些啥。这里就把它翻译成白话顺便魔改了一下证明,不需要 PL 预备知识也能看懂。

Read more »

这是一个经典老题了,如何用 fair coins 来构造一个 biased coin,以及如何用 fair coins 来构造一个 discrete uniform distribution。基于这两个问题,我又 yy 了另外几个小 follow-up,试图去分析其时间复杂度。

Read more »
0%