编程语言概念

默认只展示每周独有的知识重点；节奏、考核、Tutorial 和避坑信息按需展开。

1. 1

   编程语言概论与函数式编程入门

   📖核心知识点：编程语言的分类——命令式、函数式、逻辑式、面向对象；编程范式的核心差异——状态变换vs值映射vs逻辑推理；Haskell语言入门——纯函数式、惰性求值、强静态类型；基本语法——函数定义、模式匹配、列表操作（head, tail, map, filter）；类型签名的阅读与书写。⏰本周节奏：如果没有Haskell基础，本周需要大量实践时间，建议完成至少20个小型Haskell函数定义练习。🎯考试关联：Haskell代码的阅读与求值追踪是期末基础题；编程范式的分类与特征是简答题考点。🧪Tutorial/Lab：安装GHC/GHCi环境，完成基本函数定义和列表操作练习；使用模式匹配实现列表处理函数。📌作业关联：所有Assignment都用Haskell完成，本周的语言熟练度直接决定后续作业效率。⚠️易错点：用命令式思维写Haskell（如想用循环变量——Haskell用递归代替循环）；类型错误不知如何调试——善用GHCi的:t命令查看表达式类型。

2. 2

   高阶函数与类型系统基础

   📖核心知识点：高阶函数——函数作为参数和返回值；柯里化（Currying）——多参数函数的本质是返回函数的函数；经典高阶函数——map、filter、foldr/foldl的定义与使用；Haskell类型系统——基本类型、函数类型（a→b）、多态类型（参数多态）；类型类（Type Class）基础——Eq、Ord、Show、Num的概念。⏰本周节奏：高阶函数和柯里化是函数式编程的核心思维跳跃，建议用foldr重新实现map和filter以深入理解fold的威力。🎯考试关联：给定高阶函数表达式求值是期末必考计算题；foldr/foldl的区别与求值过程是高频考点。🧪Tutorial/Lab：用foldr实现多个列表函数（sum, length, reverse, map）；练习部分应用（Partial Application）的使用。📌作业关联：Assignment中大量使用高阶函数，熟练使用map/filter/fold是编写简洁代码的关键。⚠️易错点：foldl在惰性求值下可能栈溢出（应使用foldl'严格版本）；柯里化的类型签名阅读——a→b→c应理解为a→(b→c)。

3. 3

   代数数据类型与模式匹配

   📖核心知识点：代数数据类型（ADT）——用data关键字定义自定义类型；积类型（Product Type，如元组和记录）与和类型（Sum Type，如枚举和标签联合）；递归数据类型——自定义列表、二叉树的定义；模式匹配的深度——嵌套模式、通配符、as模式；类型安全——穷尽模式匹配的编译器检查。⏰本周节奏：ADT是Haskell的核心设计工具，建议定义3-5个不同的递归数据类型并为每个编写相关操作函数。🎯考试关联：给定ADT定义编写操作函数是期末编程题核心形式；递归数据类型上的递归函数定义是高频考点。🧪Tutorial/Lab：定义二叉树ADT并实现插入、查找、遍历操作；用ADT定义简单的算术表达式语言并实现求值器。📌作业关联：Assignment通常要求用ADT定义语言的抽象语法树（AST），本周的ADT设计技能直接服务于作业。⚠️易错点：模式匹配顺序影响语义——Haskell从上到下匹配，通配符放前面会遮蔽后续模式；递归数据类型忘记定义基础情况（base case）。

4. 4

   Lambda演算

   📖核心知识点：无类型Lambda演算——语法（变量、抽象λx.M、应用M N）；自由变量与绑定变量的识别；α-变换（重命名绑定变量）、β-归约（函数应用）、η-归约（函数等价）；归约策略——正序（Normal Order）vs应用序（Applicative Order）；Church-Rosser定理（合流性）——如果终止则结果唯一。⏰本周节奏：Lambda演算是编程语言理论的数学基础，需要纯粹的符号操作练习，建议做10+道β-归约链练习。🎯考试关联：Lambda表达式的β-归约过程是期末必考计算题（15-20分）；Church-Rosser定理的陈述是简答题考点。🧪Tutorial/Lab：手动对Lambda表达式执行β-归约直到正则形式；识别自由变量和绑定变量；比较不同归约策略的结果。📌作业关联：Assignment可能要求实现Lambda演算的求值器，理解β-归约的机械过程是实现基础。⚠️易错点：β-归约时忘记避免变量捕获（需要先α-变换）；混淆自由变量和绑定变量——同名变量在不同作用域可能一个自由一个绑定。

5. 5

   类型系统与类型推断

   📖核心知识点：简单类型Lambda演算（Simply Typed Lambda Calculus）；类型规则——变量规则、抽象规则、应用规则的推导树形式；类型安全性——Progress（不会卡住）和Preservation（类型保持）定理；Hindley-Milner类型系统——参数多态与let-多态；类型推断算法——Algorithm W、合一（Unification）算法。⏰本周节奏：类型推断是全课最抽象的主题之一，建议先掌握类型推导树的手动构造，再理解合一算法的工作原理。🎯考试关联：给定表达式推导其类型（画推导树）是期末大题；合一算法的手动执行是高频考点。🧪Tutorial/Lab：为给定Lambda表达式手动构造类型推导树；手动执行合一算法推断多态函数的类型。📌作业关联：Assignment可能要求实现简单的类型检查器或类型推断器。⚠️易错点：类型推导树中忘记检查上下文（Context/Environment）中的类型假设；合一时发生occurs check失败（如将a与[a]合一导致无限类型）。

6. 6

   语义学：操作语义

   📖核心知识点：编程语言语义的三种方法——操作语义、指称语义、公理语义；大步操作语义（Big-step/Natural Semantics）——直接给出表达式到值的关系；小步操作语义（Small-step/Structural Operational Semantics）——描述单步计算过程；大步vs小步的优缺点——大步简洁但无法描述不终止计算，小步可描述中间状态；语义规则的推导树构造。⏰本周节奏：操作语义是形式化描述语言行为的核心工具，建议对同一语言同时写出大步和小步语义规则并对比。🎯考试关联：用操作语义规则推导表达式的求值过程是期末必考大题；大步vs小步语义的区别是简答题考点。🧪Tutorial/Lab：为简单的算术+布尔表达式语言编写大步和小步操作语义规则；用推导树证明表达式的求值结果。📌作业关联：Assignment可能要求为扩展语言特性编写操作语义规则并实现对应的求值器。⚠️易错点：大步语义规则的前提（premises）遗漏导致推导不完整；小步语义中确定性问题——每个配置最多一步可走的保证。

7. 7

   语义学：指称语义与域理论

   📖核心知识点：指称语义（Denotational Semantics）——将程序映射到数学对象（通常是函数）；语义函数⟦·⟧的定义——组合式（Compositional）结构；域理论（Domain Theory）基础——完全偏序集（CPO）、连续函数、最小不动点；不动点定理（Kleene定理）——递归函数的语义=语义函数的最小不动点；while循环的指称语义——通过不动点理解循环的数学含义。⏰本周节奏：指称语义和域理论数学抽象度极高，建议先理解不动点的直觉（递归=逐层逼近），再看形式化定义。🎯考试关联：用指称语义定义简单语言构造的语义函数是期末设计题；不动点定理的陈述与应用是考点。🧪Tutorial/Lab：为简单命令式语言编写指称语义函数；手动计算递归函数定义的最小不动点逼近过程。📌作业关联：Assignment中可能涉及指称语义的实现或证明两种语义的等价性。⚠️易错点：指称语义的组合性要求——子表达式的语义不依赖于其出现的上下文；最小不动点逼近的起始点必须是底元素（⊥）。

8. 8

   Monad与副作用处理

   📖核心知识点：纯函数式语言中处理副作用的挑战——IO、状态、异常如何在纯函数框架中表达；Monad的定义——类型构造器m + return :: a→m a + (>>=) :: m a→(a→m b)→m b；Monad三定律——左单位元、右单位元、结合律；常用Monad实例——Maybe（可失败计算）、List（非确定性）、State（有状态计算）、IO（输入输出）；do-notation语法糖与Monad组合子。⏰本周节奏：Monad是Haskell最难理解的概念之一，建议从Maybe Monad开始理解「链式计算中自动处理失败「的直觉，再推广到其他Monad。🎯考试关联：Monad定律的验证和do-notation的展开（脱糖为>>=链）是期末考点；不同Monad的语义区别是简答题高频考点。🧪Tutorial/Lab：实现自定义Monad实例并验证Monad定律；用State Monad实现一个简单的解释器。📌作业关联：Assignment的解释器/编译器实现通常需要用Monad管理状态和错误处理。⚠️易错点：Monad不是「盒子「比喻那么简单——它是一种计算模式的抽象；do-notation中的let vs <-搞混（let是纯绑定，<-是Monad绑定）。

9. 9

   高级类型系统特性

   📖核心知识点：参数多态（Parametric Polymorphism）vs特设多态（Ad-hoc Polymorphism/Type Classes）；存在类型（Existential Types）——隐藏实现细节的抽象机制；GADT（Generalized Algebraic Data Types）——在数据构造器中携带类型等式约束；类型系统与逻辑的对应——Curry-Howard同构（命题=类型，证明=程序）；依赖类型（Dependent Types）的直觉介绍。⏰本周节奏：高级类型特性理论深度大，建议重点理解Curry-Howard同构的哲学意义和GADT的类型安全增强作用。🎯考试关联：Curry-Howard同构的基本对应关系（→对应蕴含、×对应合取、+对应析取）是简答题考点；GADT的类型安全示例可能出现在分析题中。🧪Tutorial/Lab：用GADT定义类型安全的表达式语言（确保ill-typed表达式无法构造）；探索Curry-Howard同构的简单示例。📌作业关联：Assignment中的高级特性可能涉及GADT或存在类型的使用。⚠️易错点：混淆参数多态（对所有类型统一行为）与类型类多态（不同类型不同实现）；Curry-Howard中⊥（Bottom类型）对应假命题/不可终止程序。

10. 10

    并发与全课总结

    📖核心知识点：并发编程模型——共享内存（锁、信号量）vs消息传递（Actor模型、CSP）；软件事务内存（STM）——用事务机制替代锁的并发控制；函数式并发的优势——纯函数天然无数据竞争（data race）；编程语言设计的权衡——安全性vs灵活性、表达力vs可分析性；全课知识图谱——函数式基础→Lambda演算→类型系统→语义学→Monad→高级类型的完整PL理论体系。⏰本周节奏：最后一周以整合为主，建议按「语法→语义→类型系统「三个维度回顾每个主题，绘制全课概念关系图。🎯考试关联：期末综合题可能要求为一个小型语言设计语法、语义和类型规则的完整方案；STM的原理是简答题可能考点。🧪Tutorial/Lab：用Haskell STM实现并发数据结构；做全课综合模拟题覆盖Lambda演算、类型推断、操作语义等核心主题。📌作业关联：所有Assignment截止前最终检查——确保类型正确、语义规则完整、代码风格良好。⚠️易错点：复习时只刷Haskell代码题忽略理论推导（操作语义、类型推导树）；混淆课程中多种语义描述方法的适用范围。