𝕋he pure \(\lambda\)-calculus contains only functions as values. It is not exactly easy to write large or interesting programs in the pure \(\lambda\)-calculus. We can however encode objects, such as … Read More →

𝕎e have now seen two operational models for programming languages: small-step and large-step. In this nnote, we consider a different semantic model, called denotational semantics. The idea in … Read More →

𝕋he small-step and large-step semantics are equivalent as captured by the following theorem. Theorem. For all commands $c$ and stores $\sigma$ and $\sigma'$ we have […] The proof is left as an … Read More →

𝕎e will now consider a more realistic programming language, one where we can assign values to variables and execute control constructs such as if and while. The syntax for this imperative language, … Read More →

𝕀n the last lecture we defined a semantics for our language of arithmetic expressions using a small-step evaluation relation $\rightarrow \subseteq \mathbf{Config}\times \mathbf{Config}$ (and its … Read More →

𝕀n this note, we will use the semantics of our simple language of arithmetic expressions, […] to express useful program properties, and we will prove these properties by induction. […] … Read More →

𝕎hat is the meaning of a program? When we write a program, we represent it using sequences of characters. But these strings are just concrete syntax—they do not tell us what the program actually … Read More →

深入浅出算法复杂度一文中，我们提到还存在一种复杂度分析策略，称为摊还分析（Amortized Analysis）。 在摊还分析中，我们主要关心某数据结构的一个操作序列中执行所有操作的平均时间，以此评价单次操作所花费的代价。摊还分析中最常用的三个技术分别是聚合分析、记账分析和势能分析。接下来我们主要讨论这三种摊还分析技术的原理以及例子。 […] 所谓聚合分析，就是尝试求出一个包含$n$ … Read More →

算法是计算机科学中最重要的部分，它们可以通过使用与语言和机器无关的方式进行研究。这意味着我们需要一种技术，使我们能够在不实现算法的情况下比较算法的效率。在算法分析中，两个最重要的工具是 […] 本文将讨论算法的效率分析，以及常用的分析工具和方法。 […] 为了理解本文所写的内容，你需要掌握一些基本的高等数学知识。 […] 一个算法主要有两种效率：时间效率和 … Read More →