PS4 · Memory Scramble

记忆扰乱：并发与网络

Board ADT、HTTP 协议交互、并发等待、map/watch 回调——6.102 的收官之战，将前三课的 ADT 技能与并发编程融合。

基本信息

PS4并发异步HTTP安全

官方讲义：web.mit.edu/6.102/ps4 ↗

作业要求

  1. 设计/测试可变 Board ADT 和 parseFromFile()
  2. 连接字符串命令 API：look() 和 flip()
  3. 改造 Board 支持并发玩家。首次翻牌可能需要无忙等等待
  4. 实现异步 map 操作，保持可观察的成对一致性
  5. 实现 watch/变更通知
官方讲义给出了 board-file 文法、board-state 协议和详细的多玩家规则。在设计 Board API 之前直接阅读这些规则；公开 TypeDoc 有意只暴露 parseFromFile，因为大多数 Board 操作由学生设计。

规格说明

Board 文件格式

第一行 ROWSxCOLUMNS，随后恰好 ROWS*COLUMNS 行卡片标记（行优先）。Board.parseFromFile(filename) 返回 Promise。

Board-state 线协议

响应以 ROWSxCOLUMNS 开始，然后每行一个空格：

  • none — 无卡片
  • down — 背面朝上
  • up CARD — 正面朝上但不受请求玩家控制
  • my CARD — 正面朝上且受请求玩家控制

翻牌规则（摘要）

第一张牌：

  • 空格：失败
  • 背面朝上：翻为正面，该玩家获得控制权
  • 正面朝上且无人控制：该玩家获得控制权
  • 正面朝上且他人控制：异步等待直到可获得或失败。其他玩家继续正常操作

第二张牌：

  • 空格：失败并释放第一张牌
  • 任何已控制的正面牌（含自己的第一张）：立即失败，释放第一张
  • 否则揭示候选牌。匹配则保留两张控制权；不匹配则释放控制权，牌保持正面朝上直到玩家下一步操作

下一张第一张牌之前：

  • 匹配：移除两张牌
  • 不匹配：每张前次非匹配牌仅在仍存在、正面朝上且无人控制时翻回背面

命令 API

look(board, playerId): Promise<string>
flip(board, playerId, row, column): Promise<string>
map(board, playerId, f): Promise<string>
watch(board, playerId): Promise<string>
  • look 返回该玩家视角的当前 board 状态
  • flip 执行一次翻牌尝试，失败时 reject。坐标为零基 (row,column)
  • map 异步替换每个卡片字符串。两个匹配的牌在 map 开始时，玩家不得观察到只改了一个的中间态（成对一致性）
  • watch 等待有意义的 board 变更，返回新状态。必须基于 Promise 而非轮询/忙等

并发设计笔记

定义 Board 抽象状态、玩家状态、原子操作、等待条件、唤醒条件和 RI，然后实现并发。

完成清单

  • board-file parser
  • 同步 Board + 游戏逻辑
  • look / flip
  • 异步 Board
  • 无忙等等待
  • 并发玩家测试
  • map
  • watch

源码骨架

board.ts — Board ADT 与文件解析

import { readFile } from 'node:fs/promises';

export class Board {
  // TODO: 指定可变、并发安全的抽象并选择表示
  private constructor() {}

  public static async parseFromFile(filename:string):Promise<Board> {
    // 读取文件使 I/O 管道可用，但验证/解析内容仍是你的任务
    const contents=await readFile(filename,'utf8'); void contents;
    throw new Error('TODO: validate board-file grammar and construct Board');
  }
}

commands.ts — 命令 API

import type { Board } from './board.js';

export async function look(board:Board, playerId:string):Promise<string> { void board; void playerId; throw new Error('TODO: look'); }
export async function flip(board:Board, playerId:string, row:number, column:number):Promise<string> { void board; void playerId; void row; void column; throw new Error('TODO: flip'); }
export async function map(board:Board, playerId:string, f:(card:string)=>Promise<string>):Promise<string> { void board; void playerId; void f; throw new Error('TODO: map'); }
export async function watch(board:Board, playerId:string):Promise<string> { void board; void playerId; throw new Error('TODO: watch'); }

server.ts — 调试服务器

import http from 'node:http';
import type { Board } from './board.js';
import { flip, look, map, watch } from './commands.js';

/** Small independently-written debug server using a simple JSON-ish query protocol. */
export function startServer(board:Board, port:number):http.Server {
  const server=http.createServer(async (req,res)=>{
    try {
      const url=new URL(req.url ?? '/', `http://${req.headers.host ?? 'localhost'}`);
      const player=url.searchParams.get('player') ?? 'player'; let body:string;
      if(url.pathname==='/look') body=await look(board,player);
      else if(url.pathname==='/flip') body=await flip(board,player,Number(url.searchParams.get('row')),Number(url.searchParams.get('col')));
      else if(url.pathname==='/watch') body=await watch(board,player);
      else if(url.pathname==='/map') body=await map(board,player, async card => card);
      else { res.statusCode=404; body='not found'; }
      res.setHeader('content-type','text/plain; charset=utf-8'); res.end(body);
    } catch(e) { res.statusCode=400; res.end(e instanceof Error ? e.message : String(e)); }
  });
  server.listen(port); return server;
}