Back to COMP1521 返回 COMP1521

Week 4 — Procedures, Memory Layout & Recursion 第 4 周 — 过程调用、内存布局与递归

Stack frames, calling conventions, table lookup, sieve pipelines, and Ackermann recursion 栈帧、调用约定、查表模式、埃拉托色尼筛与 Ackermann 递归

🎯 Learning Objectives学习目标

🧩 Exam Alignment与考试练习的对应关系

Coverage Targets 覆盖目标

Document ≥3 procedure templates (leaf, single-call, recursive) and annotate stack diagrams for each. Map every template to at least one lab or exam ID. 记录 ≥3 种过程模板(叶子函数、单层调用、递归调用),为每种绘制栈示意,并与至少一个实验/试题编号对应。

📚 Core Concepts核心概念

Stack Frame Blueprint 栈帧蓝图

Follow the prologue: `addi $sp, $sp, -frameSize`, `sw $ra, offset($sp)`, optional `sw $fp,` then set `$fp = $sp + frameSize`. On exit restore `$fp`, `$ra`, and add back `frameSize`. 序言流程:`addi $sp, $sp, -frameSize`,`sw $ra, offset($sp)`,必要时保存 `$fp`,之后令 `$fp = $sp + frameSize`。结束时恢复 `$fp`、`$ra`,再把 `frameSize` 加回 `$sp`。

Calling Convention 调用约定

Arguments move through `$a0–$a3`; extra parameters spill to stack. Return values use `$v0/$v1`. Callee saves `$s0–$s7` if modified. This template underpins Lab04 `lookup.s` helper functions. 参数通过 `$a0–$a3` 传递,额外参数压栈。返回值放在 `$v0/$v1`。若修改 `$s0–$s7`,被调用者负责保存。该模板支撑 Lab04 `lookup.s` 的辅助函数实现。

Data Directives & Alignment 数据伪指令与对齐

Use `.word` for 32-bit tables, `.space` to reserve scratch buffers, `.align 2` before double-precision blocks, and `.asciiz` for null-terminated messages. Tutorial04 Q11 lists canonical combinations. `.word` 用于 32 位表,`.space` 可预留工作缓冲区,双精度段前使用 `.align 2`,`.asciiz` 保证字符串以空字符结束。教程 04 第 11 题给出了典型组合。

Loop Pipelines & Sieve 循环流水线与筛法

Outer loop increments the base prime; inner loop marks multiples via base+offset writes. Maintain `prime*prime <= limit` guard to minimise passes. Aligns with Lab04 `sieve.s` instructions. 外循环递增当前素数,内循环以基址+偏移方式标记倍数。使用 `prime*prime <= limit` 作为守卫,可减少遍历次数。对应 Lab04 `sieve.s` 的实现要求。

Recursion Guards 递归守卫

Establish base case check immediately after prologue. Push arguments in reverse order, call recursive branch, pop in mirrored order. Document depth counter when translating exam problems like 22T3 Q9. 在序言后立即检查基例。按逆序压入参数,调用递归分支,返回时按镜像顺序弹出。在翻译 22T3 Q9 等题目时记录深度计数器。

🧪 Worked Examples例题与讲解

Example 1 — `lookup.s` Table Access 例 1 — `lookup.s` 查表访问

Goal: map uppercase letters to Morse codes. Steps: load base address into `$s0`, subtract `'A'` to form index, multiply by element size (`sll $t0, $t0, 2`), then `lw` pointer to string. Respect `.word morse_table` layout. 目标:将大写字母映射到莫尔斯电码。流程:先把表基址存入 `$s0`,用输入字符减 `'A'` 得到索引,`sll $t0, $t0, 2` 计算偏移,再 `lw` 获得字符串指针,并遵循 `.word morse_table` 布局。

# offset = (ch - 'A') * 4 addi $t0, $a0, -65 sll $t0, $t0, 2 addu $t1, $s0, $t0 lw $a0, 0($t1) li $v0, 4 syscall # 偏移 = (ch - 'A') * 4 addi $t0, $a0, -65 sll $t0, $t0, 2 addu $t1, $s0, $t0 lw $a0, 0($t1) li $v0, 4 syscall
Exam tie-in: 22T2 Q4 expects identical offset math; failing to subtract `'A'` misaligns entries. 考试关联:22T2 Q4 要求相同偏移公式,若未减 `'A'` 将导致索引错位。

Example 2 — `sieve.s` Nested Loop 例 2 — `sieve.s` 嵌套循环

Outline: outer loop increments candidate prime `p`. Inner loop marks multiples starting at `p*p`. Break when `p*p > limit`. Use `$s1` for base pointer and `$t` temporaries for offsets. 概述:外循环递增候选素数 `p`,内循环从 `p*p` 开始标记倍数。当 `p*p > limit` 时退出。基址放在 `$s1`,偏移用 `$t` 临时寄存器。

Exam 20T3 Q8 matched this structure; annotate invariants (“numbers below p already classified”) to earn full reasoning marks. 20T3 Q8 与此结构一致;写明不变式(“p 之前的数已分类”)可获得完整推理分。

Example 3 — `ackermann.s` Recursion Trace 例 3 — `ackermann.s` 递归追踪

Push arguments `m`, `n`, save `$ra`, call recursive branch. When returning, pop in reverse order, compute final expression, and store result in `$v0`. Guard `m==0` and `n==0` early to limit depth. 先压入参数 `m`、`n`,保存 `$ra`,调用递归分支。返回时按反序弹栈,计算最终表达式并放到 `$v0`。在开头守卫 `m==0` 与 `n==0` 以控制深度。

Cross reference 22T3 Q9: identical stack pattern; missing a pop or swap costs ≥3 marks. 对照 22T3 Q9,栈操作模式完全一致;少弹或顺序错误至少扣 3 分。

⚠️ Common Pitfalls易错点提醒

🛠️ Practice Task实践任务

Build `stats_report.s`: a procedure `collect(int* data, int len, struct summary*)` that computes min/max/mean and stores messages in both English and Chinese buffers. Use `.word` for structure fields and align strings with `.asciiz`. Call the procedure from `main`, preserving caller registers. 实现 `stats_report.s`:编写过程 `collect(int* data, int len, struct summary*)`,计算最小值/最大值/平均值,并分别写入中英文缓冲区。结构体字段使用 `.word`,字符串由 `.asciiz` 对齐。`main` 调用时需保护调用者寄存器。

OptionalOptional: extend with a sieve-based prime counter for the dataset; spend ≤10% time once core functionality passes autotest. 可选Optional:扩展加入基于筛法的素数计数,前提是核心功能通过 autotest,且额外时间不超过 10%。

🧪 Tutorial & Lab Mapping教程与实验映射

Tutorial 04 Highlights Tutorial 04 重点

  • Q1–Q4 practise `.data` directives and struct layout; map directly to Lab04 `cms.s` field packing. 第 1–4 题练习 `.data` 伪指令与结构体布局,直接对应 Lab04 `cms.s` 字段封装。
  • Q5–Q8 trace loads/stores with partial-word access, prepping for pointer arithmetic in `lookup.s`. 第 5–8 题跟踪部分字节的读写,为 `lookup.s` 指针运算做准备。
  • Revision Questions Q11–Q12 dive into directive combinations and signed loads (flagged in exam commentaries). 复习题 Q11–Q12 深入伪指令组合与符号加载,正是考试点评的高频点。

Lab 04 Programming Tasks Lab 04 编程任务

  • `lookup.s`: Table-driven mapping with pointer arithmetic. `lookup.s`:指针寻址的查表映射。
  • `sieve.s`: Prime marking with nested loops and guard conditions. `sieve.s`:带守卫条件的嵌套循环筛法。
  • `mathematics.s` Optional: Floating-point arithmetic drill; revise only after core tasks. `mathematics.s` Optional浮点算术练习,核心任务完成后再复习。
  • `cms.s`: Struct packing and offset management. `cms.s`:结构体压缩与偏移管理。
  • `ackermann.s`: Recursion with deep stack usage, mirrors exam recursion marking. `ackermann.s`:深度栈递归,与考试递归题评分相符。
  • `polymipsism.s` (challenge): Multi-dispatch procedure with pointer tables — stretch goal for advanced quiz tier. `polymipsism.s`(挑战):含指针表的多分派过程,供高级测验题练习。

📝 Study Log — Week 4学习记录 — 第 4 周

Premium Quiz — Stack Frames & Recursion Premium 测验 — 栈帧与递归

28 basic (prologue/epilogue, directives), 8 intermediate (lookup loops, sieve), 4 advanced (multi-procedure recursion). Unlock with membership. 基础 28 题(序言尾声、伪指令),中级 8 题(查表循环、筛法),高级 4 题(多过程递归)。会员解锁后方可使用。

Go to Week 4 Quiz 进入第 4 周测验

🔭 Next Week Preview下周预告

Week 5 pivots to systems I/O, endian transforms, and BCD arithmetic. Skim Lab05 instructions (`sixteen_in/out`, `bcd_arithmetic`) to prime for data-representation heavy quizzes. 第 5 周将转向系统 I/O、端序转换与 BCD 算术。提前浏览 Lab05 (`sixteen_in/out`, `bcd_arithmetic`) 的说明,为数据表示类测验做准备。

📎 Resources & Checklist资源与清单