小さな言語で書いたプログラムを二つの変数スコープ規則でそれぞれ実行し、結果を並べて出力する。 プログラムは n 行で、各行に命令が一つある。 def f の行から end の行までが関数 f の定義で、その間の行が f の本体だ。 関数の定義はいちばん外側にだけあり、関数の中で関数を定義しない。 関数の定義の外の行がいちばん外側の命令で、上から順に実行する。 関数の定義そのものは実行せず、関数は定義がプログラムのどこにあっても呼べる。 変数は「枠」に入っている。 いちばん外側の命令はグローバルの枠を使う。 関数を呼ぶたびに空の枠を新しく作り、その関数の本体をその枠で実行する。 関数が終わるとその枠は消える。 命令は五種類だ。 - var x v：今の枠に変数 x を作り、値 v を入れる。 今の枠に x がすでにあれば、その値だけを v に変える。 - set x v：x を探し、その値を v に変える。 - add x v：x を探し、その値に v を足す。 - print x：x を探し、その値を出力する。 見つからなければ ? を出力する。 - call f：関数 f を呼ぶ。 f が終わったら次の命令へ進む。 set と add は x が見つからなければ何もしない。 新しい変数は作らない。 「探す」とは、決まった順に枠を見て、x が入っている最初の枠を選ぶことだ。 その順序がスコープ規則だ。 静的スコープでは、今の枠を見て、次にグローバルの枠を見る。 動的スコープでは、今の枠、今の関数を呼んだ関数の枠、その関数を呼んだ関数の枠、… の順に見て、最後にグローバルの枠を見る。 いちばん外側では、今の枠がそのままグローバルの枠だ。 変数の名前と関数の名前は別々に扱う。 同じ名前を変数と関数の両方に使ってよい。 プログラムを静的スコープで一回、動的スコープで一回、最初の状態から別々に実行する。 二回の実行で print が実行される回数は同じだ。 print が実行されるたびに一行に、静的スコープで実行したときの出力と動的スコープで実行したときの出力を空白一つで区切って出力せよ。
入力
一行目に n、続く n 行に命令が一つずつ与えられる。 1 ≤ n ≤ 1,000。 名前は英小文字で始まる英小文字・数字 1～10 文字だ。 すべての v と、実行中に変数が持つすべての値は -10^9 以上 10^9 以下の整数だ。 def にはすべて対になる end があり、同じ名前の関数を二度定義せず、call で呼ぶ関数はすべて定義されている。 関数は直接にも他の関数を通しても自分自身を呼ばない。 どちらの実行でも、実行される命令（call を含む）は 50,000 個以下、同時に開いている関数呼び出しは 30 個以下、実行される print は 1 個以上 5,000 個以下だ
出力
print が実行された回数だけの行
例 1 · stdin
13
var x 1
def show
print x
end
def change
var x 2
call show
set x 3
call show
end
call change
print x
call show
stdout
1 2
1 3
1 1
1 1
例 2 · stdin
21
def inc
add n 1
print n
end
def run
var n 10
call inc
call inc
end
var n 0
call run
print n
def peek
print m
end
def outer
var m 5
call peek
end
call outer
call peek
stdout
1 11
2 12
2 0
? 5
? ?
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
8 つの言語はすべて静的スコープです。 関数の中で見える名前は「どこから呼んだか」ではなく「どこに書いてあるか」で決まります。 動的スコープは古い Lisp、Emacs Lisp（既定）、bash 関数の local、Perl の local で見られます。 一つ目の例の show は、静的スコープではいつもグローバルの x（1）を見て、動的スコープでは自分を呼んだ change の x（2、3）を見ます。 解き方は、枠ごとに辞書を一つ置き、枠をリスト（スタック）に積むことです：Python dict のリスト、JS・TS Map[]、Java List<Map<String, Integer>>、C# List<Dictionary<string, int>>、C++ std::vector<std::unordered_map<…>>、Craykon 辞書() のリスト。 C には辞書がないので、名前を番号に変えてから（番号, 値）の組を一列に積み、枠ごとに開始位置を覚えます。 call は枠を一つ積み、本体を再帰で実行してから枠を取り除きます。 静的な探し方はいちばん上の枠と 0 番の枠だけを、動的な探し方は上から 0 番まで順に見ます。 各言語の実際の規則と比べると：Python は関数の中で値を入れる名前をその関数全体のローカル変数とみなし、外のものを変えるには global・nonlocal を使います。 この問題の set は逆に、見つけた枠を変えます。 Craykon では、いちばん上（関数の外）で作った変数に関数の中で入れるとその変数が変わり、関数の中で初めて作った名前はその関数のものなので、外で使うとチェッカーが止めます。 JS の var は関数スコープ、let・const はブロックスコープです。 C・C++・Java・C# はブロックスコープで、Java・C# は内側のブロックで外側のローカル変数と同じ名前を宣言し直すことを禁じます。 落とし穴 ① 動的スコープを今の枠とグローバルだけで探す、静的スコープなのに呼び出し元の枠まで探す。 ② 動的スコープをグローバルから探す（いちばん近い枠が先です）。 ③ 関数が終わっても枠を残し、次の呼び出しが前の値を見る（C の static ローカル変数のような動作）。 ④ set が見つからないとき今の枠に新しく作る（Python 式の代入）。 ⑤ var がすでに見えている変数を変える（var は常に今の枠です）。
Pythonmain.py · 53 行
import syslines = sys.stdin.read().split("\n")n = int(lines[0])funcs = {} # 함수 이름 → 몸체 명령들main = [] # 맨 바깥 명령들body = Nonefor line in lines[1:1 + n]: t = line.split() if t[0] == "def": body = funcs[t[1]] = [] elif t[0] == "end": body = None else: (main if body is None else body).append(t)def run(dynamic): frames = [{}] # frames[0]은 맨 바깥(전역), 끝이 지금 실행 중인 함수의 칸 printed = [] def find(name): """이름을 가진 칸(사전)을 찾는다. 없으면 None.""" # 정적: 지금 칸 → 전역. 동적: 지금 칸 → 부른 함수의 칸 → … → 전역 order = reversed(frames) if dynamic else (frames[-1], frames[0]) for frame in order: if name in frame: return frame return None def execute(cmds): for cmd in cmds: op = cmd[0] if op == "var": frames[-1][cmd[1]] = int(cmd[2]) elif op in ("set", "add"): frame = find(cmd[1]) if frame is not None: frame[cmd[1]] = int(cmd[2]) if op == "set" else frame[cmd[1]] + int(cmd[2]) elif op == "print": frame = find(cmd[1]) printed.append("?" if frame is None else str(frame[cmd[1]])) else: # call frames.append({}) # 부를 때마다 빈 칸에서 시작한다 execute(funcs[cmd[1]]) frames.pop() # 끝나면 그 칸은 사라진다 execute(main) return printedfor a, b in zip(run(False), run(True)): print(a, b)
JavaScriptmain.js · 43 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const funcs = new Map(); // 함수 이름 → 몸체 명령들const main = []; // 맨 바깥 명령들let body = null;for (const line of lines.slice(1, 1 + n)) { const t = line.trim().split(" "); if (t[0] === "def") funcs.set(t[1], (body = [])); else if (t[0] === "end") body = null; else (body ?? main).push(t);}function run(dynamic) { const frames = [new Map()]; // frames[0]은 전역, 끝이 지금 실행 중인 함수의 칸 const printed = []; // 정적: 지금 칸 → 전역. 동적: 지금 칸 → 부른 함수의 칸 → … → 전역 const find = (name) => { const order = dynamic ? [...frames].reverse() : [frames[frames.length - 1], frames[0]]; return order.find((f) => f.has(name)); }; const execute = (cmds) => { for (const [op, name, arg] of cmds) { if (op === "var") { frames[frames.length - 1].set(name, Number(arg)); } else if (op === "set" || op === "add") { const f = find(name); if (f) f.set(name, op === "set" ? Number(arg) : f.get(name) + Number(arg)); } else if (op === "print") { const f = find(name); printed.push(f ? String(f.get(name)) : "?"); } else { frames.push(new Map()); // 부를 때마다 빈 칸에서 시작한다 execute(funcs.get(name)); frames.pop(); // 끝나면 그 칸은 사라진다 } } }; execute(main); return printed;}const lex = run(false), dyn = run(true);console.log(lex.map((v, i) => `${v} ${dyn[i]}`).join("\n"));
TypeScriptmain.ts · 48 行
import { readFileSync } from "node:fs";type Frame = Map<string, number>;const lines: string[] = readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const funcs = new Map<string, string[][]>(); // 함수 이름 → 몸체 명령들const main: string[][] = []; // 맨 바깥 명령들let body: string[][] | null = null;for (const line of lines.slice(1, 1 + n)) { const t = line.trim().split(" "); if (t[0] === "def") { body = []; funcs.set(t[1], body); } else if (t[0] === "end") body = null; else (body ?? main).push(t);}function run(dynamic: boolean): string[] { const frames: Frame[] = [new Map()]; // frames[0]은 전역, 끝이 지금 실행 중인 함수의 칸 const printed: string[] = []; // 정적: 지금 칸 → 전역. 동적: 지금 칸 → 부른 함수의 칸 → … → 전역 const find = (name: string): Frame | undefined => { const order = dynamic ? [...frames].reverse() : [frames[frames.length - 1], frames[0]]; return order.find((f) => f.has(name)); }; const execute = (cmds: string[][]): void => { for (const [op, name, arg] of cmds) { if (op === "var") { frames[frames.length - 1].set(name, Number(arg)); } else if (op === "set" || op === "add") { const f = find(name); if (f) f.set(name, op === "set" ? Number(arg) : (f.get(name) ?? 0) + Number(arg)); } else if (op === "print") { const f = find(name); printed.push(f ? String(f.get(name)) : "?"); } else { frames.push(new Map()); // 부를 때마다 빈 칸에서 시작한다 execute(funcs.get(name) ?? []); frames.pop(); // 끝나면 그 칸은 사라진다 } } }; execute(main); return printed;}const lex = run(false), dyn = run(true);console.log(lex.map((v, i) => `${v} ${dyn[i]}`).join("\n"));
JavaMain.java · 78 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class Main { static Map<String, List<String[]>> funcs = new HashMap<>(); // 함수 이름 → 몸체 명령들 static List<Map<String, Integer>> frames; // 0번이 전역, 끝이 지금 함수의 칸 static boolean dynamic; static List<String> printed; // 정적: 지금 칸 → 전역. 동적: 지금 칸 → 부른 함수의 칸 → … → 전역 static Map<String, Integer> find(String name) { int top = frames.size() - 1; if (dynamic) { for (int i = top; i >= 0; i--) if (frames.get(i).containsKey(name)) return frames.get(i); return null; } if (frames.get(top).containsKey(name)) return frames.get(top); if (frames.get(0).containsKey(name)) return frames.get(0); return null; } static void execute(List<String[]> cmds) { for (String[] c : cmds) { switch (c[0]) { case "var" -> frames.get(frames.size() - 1).put(c[1], Integer.parseInt(c[2])); case "set", "add" -> { Map<String, Integer> f = find(c[1]); if (f != null) f.put(c[1], c[0].equals("set") ? Integer.parseInt(c[2]) : f.get(c[1]) + Integer.parseInt(c[2])); } case "print" -> { Map<String, Integer> f = find(c[1]); printed.add(f == null ? "?" : String.valueOf(f.get(c[1]))); } default -> { frames.add(new HashMap<>()); // 부를 때마다 빈 칸에서 시작한다 execute(funcs.get(c[1])); frames.remove(frames.size() - 1); // 끝나면 그 칸은 사라진다 } } } } static List<String> run(List<String[]> main, boolean dyn) { dynamic = dyn; frames = new ArrayList<>(); frames.add(new HashMap<>()); printed = new ArrayList<>(); execute(main); return printed; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); List<String[]> main = new ArrayList<>(), body = null; for (int i = 0; i < n; i++) { String[] t = in.readLine().trim().split(" "); if (t[0].equals("def")) { body = new ArrayList<>(); funcs.put(t[1], body); } else if (t[0].equals("end")) { body = null; } else { (body == null ? main : body).add(t); } } List<String> lex = run(main, false), dyn = run(main, true); StringBuilder out = new StringBuilder(); for (int i = 0; i < lex.size(); i++) out.append(lex.get(i)).append(' ').append(dyn.get(i)).append('\n'); System.out.print(out); }}
C#Main.cs · 81 行
using System;using System.Collections.Generic;using System.Text;class Program{ static Dictionary<string, List<string[]>> funcs = new(); // 함수 이름 → 몸체 명령들 static List<Dictionary<string, int>> frames = new(); // 0번이 전역, 끝이 지금 함수의 칸 static bool dynamic; static List<string> printed = new(); // 정적: 지금 칸 → 전역. 동적: 지금 칸 → 부른 함수의 칸 → … → 전역 static Dictionary<string, int> Find(string name) { int top = frames.Count - 1; if (dynamic) { for (int i = top; i >= 0; i--) if (frames[i].ContainsKey(name)) return frames[i]; return null; } if (frames[top].ContainsKey(name)) return frames[top]; if (frames[0].ContainsKey(name)) return frames[0]; return null; } static void Execute(List<string[]> cmds) { foreach (string[] c in cmds) { switch (c[0]) { case "var": frames[^1][c[1]] = int.Parse(c[2]); break; case "set": case "add": var f = Find(c[1]); if (f != null) f[c[1]] = c[0] == "set" ? int.Parse(c[2]) : f[c[1]] + int.Parse(c[2]); break; case "print": var g = Find(c[1]); printed.Add(g == null ? "?" : g[c[1]].ToString()); break; default: frames.Add(new Dictionary<string, int>()); // 부를 때마다 빈 칸에서 시작한다 Execute(funcs[c[1]]); frames.RemoveAt(frames.Count - 1); // 끝나면 그 칸은 사라진다 break; } } } static List<string> Run(List<string[]> main, bool dyn) { dynamic = dyn; frames = new List<Dictionary<string, int>> { new() }; printed = new List<string>(); Execute(main); return printed; } static void Main() { int n = int.Parse(Console.ReadLine().Trim()); var main = new List<string[]>(); List<string[]> body = null; for (int i = 0; i < n; i++) { string[] t = Console.ReadLine().Trim().Split(' '); if (t[0] == "def") funcs[t[1]] = body = new List<string[]>(); else if (t[0] == "end") body = null; else (body ?? main).Add(t); } var lex = Run(main, false); var dyn = Run(main, true); var sb = new StringBuilder(); for (int i = 0; i < lex.Count; i++) sb.Append(lex[i]).Append(' ').Append(dyn[i]).Append('\n'); Console.Write(sb); }}
C++main.cpp · 76 行
#include <iostream>#include <sstream>#include <string>#include <unordered_map>#include <vector>using Frame = std::unordered_map<std::string, int>;struct Cmd { std::string op, name; int arg;};std::unordered_map<std::string, std::vector<Cmd>> funcs; // 함수 이름 → 몸체 명령들std::vector<Frame> frames; // 0번이 전역, 끝이 지금 함수의 칸bool dynamic;std::vector<std::string> printed;// 정적: 지금 칸 → 전역. 동적: 지금 칸 → 부른 함수의 칸 → … → 전역Frame *find(const std::string &name) { if (dynamic) { for (auto it = frames.rbegin(); it != frames.rend(); ++it) if (it->count(name)) return &*it; return nullptr; } if (frames.back().count(name)) return &frames.back(); if (frames.front().count(name)) return &frames.front(); return nullptr;}void execute(const std::vector<Cmd> &cmds) { for (const Cmd &c : cmds) { if (c.op == "var") { frames.back()[c.name] = c.arg; } else if (c.op == "set" || c.op == "add") { if (Frame *f = find(c.name)) (*f)[c.name] = c.op == "set" ? c.arg : (*f)[c.name] + c.arg; } else if (c.op == "print") { Frame *f = find(c.name); printed.push_back(f ? std::to_string(f->at(c.name)) : "?"); } else { // 부를 때마다 빈 칸에서 시작한다. push_back이 vector를 옮길 수 있어 칸을 가리키는 포인터는 오래 들지 않는다 frames.emplace_back(); execute(funcs[c.name]); frames.pop_back(); // 끝나면 그 칸은 사라진다 } }}std::vector<std::string> run(const std::vector<Cmd> &main, bool dyn) { dynamic = dyn; frames.assign(1, Frame{}); printed.clear(); execute(main); return printed;}int main() { int n; std::string line; std::getline(std::cin, line); n = std::stoi(line); std::vector<Cmd> main; std::vector<Cmd> *body = nullptr; for (int i = 0; i < n; i++) { std::getline(std::cin, line); std::istringstream ss(line); Cmd c{"", "", 0}; ss >> c.op >> c.name >> c.arg; if (c.op == "def") body = &funcs[c.name]; else if (c.op == "end") body = nullptr; else (body ? *body : main).push_back(c); } auto lex = run(main, false), dyn = run(main, true); std::string out; for (size_t i = 0; i < lex.size(); i++) out += lex[i] + " " + dyn[i] + "\n"; std::cout << out;}
Cmain.c · 121 行
#include <stdio.h>#include <string.h>enum { VAR, SET, ADD, PRINT, CALL };typedef struct { int op, id, arg; } Cmd; /* id: 변수 번호, call이면 함수 번호 */static char vname[1000][11], fname[1000][11];static int nv, nf;static Cmd cmds[1000];static int ncmd;static int fstart[1000], fend[1000]; /* 함수 몸체는 cmds[fstart, fend) */static int mainlist[1000], nmain; /* 맨 바깥 명령의 번호들 *//* 칸 하나는 (변수 번호, 값) 묶음들. 모든 칸을 한 줄로 쌓고, 칸마다 시작 자리를 둔다 */static int ent_id[1000], ent_val[1000], nent;static int frame_at[64], depth; /* frame_at[d]: d번 칸의 시작. 0번이 전역 */static int dynamic;static char printed[2][50000][12];static int nprinted;static int intern(char names[][11], int *count, const char *s) { for (int i = 0; i < *count; i++) if (strcmp(names[i], s) == 0) return i; strcpy(names[*count], s); return (*count)++;}/* d번 칸에서 변수 id의 자리(없으면 -1) */static int in_frame(int d, int id) { int end = d == depth ? nent : frame_at[d + 1]; for (int e = frame_at[d]; e < end; e++) if (ent_id[e] == id) return e; return -1;}/* 정적: 지금 칸 → 전역. 동적: 지금 칸 → 부른 함수의 칸 → … → 전역 */static int find(int id) { int e; if (dynamic) { for (int d = depth; d >= 0; d--) if ((e = in_frame(d, id)) >= 0) return e; return -1; } if ((e = in_frame(depth, id)) >= 0) return e; return depth > 0 ? in_frame(0, id) : -1;}static void exec_one(const Cmd *c);static void call(int f) { depth++; frame_at[depth] = nent; /* 부를 때마다 빈 칸에서 시작한다 */ for (int i = fstart[f]; i < fend[f]; i++) exec_one(&cmds[i]); nent = frame_at[depth]; /* 끝나면 그 칸은 사라진다 */ depth--;}static void exec_one(const Cmd *c) { int e; switch (c->op) { case VAR: if ((e = in_frame(depth, c->id)) < 0) { e = nent++; ent_id[e] = c->id; } ent_val[e] = c->arg; break; case SET: case ADD: if ((e = find(c->id)) >= 0) ent_val[e] = c->op == SET ? c->arg : ent_val[e] + c->arg; break; case PRINT: e = find(c->id); if (e < 0) strcpy(printed[dynamic][nprinted++], "?"); else snprintf(printed[dynamic][nprinted++], 12, "%d", ent_val[e]); break; case CALL: call(c->id); break; }}int main(void) { int n, cur = -1; scanf("%d", &n); for (int i = 0; i < n; i++) { char op[8], name[11]; scanf("%7s", op); if (strcmp(op, "end") == 0) { fend[cur] = ncmd; cur = -1; continue; } scanf("%10s", name); if (strcmp(op, "def") == 0) { cur = intern(fname, &nf, name); fstart[cur] = ncmd; continue; } Cmd c = {0, 0, 0}; if (strcmp(op, "call") == 0) { c.op = CALL; c.id = intern(fname, &nf, name); /* 뒤에서 정의되는 함수도 번호를 먼저 받는다 */ } else { c.op = strcmp(op, "var") == 0 ? VAR : strcmp(op, "set") == 0 ? SET : strcmp(op, "add") == 0 ? ADD : PRINT; c.id = intern(vname, &nv, name); if (c.op != PRINT) scanf("%d", &c.arg); } if (cur < 0) mainlist[nmain++] = ncmd; cmds[ncmd++] = c; } int count = 0; for (dynamic = 0; dynamic <= 1; dynamic++) { nent = depth = nprinted = 0; frame_at[0] = 0; for (int i = 0; i < nmain; i++) exec_one(&cmds[mainlist[i]]); count = nprinted; } for (int i = 0; i < count; i++) printf("%s %s\n", printed[0][i], printed[1][i]); return 0;}
Craykonmain.cray · 116 行
n = コンソール.行読み().数に();funcs = 辞書(); // 함수 이름 → 몸체 명령들main = []; // 맨 바깥 명령들body = なし;繰り返す (i = 0; i < n; i++){ t = コンソール.行読み().空白除去().分ける(" "); もし (t[0] == "def") { body = []; funcs[t[1]] = body; } でなければ もし (t[0] == "end") { body = なし; } でなければ もし (body == なし) { main.追加(t); } でなければ { body.追加(t); }}frames = []; // 0번이 전역, 끝이 지금 실행 중인 함수의 칸dynamic = 偽;printed = [];// 이름을 가진 칸의 번호(없으면 -1)// 정적: 지금 칸 → 전역. 동적: 지금 칸 → 부른 함수의 칸 → … → 전역찾기(name){ top = frames.個数 - 1; もし (dynamic) { 繰り返す (d = top; d >= 0; d--) { もし (frames[d].含む(name)) { 返す d; } } 返す -1; } もし (frames[top].含む(name)) { 返す top; } もし (frames[0].含む(name)) { 返す 0; } 返す -1;}실행(cmds){ それぞれ (c の中 cmds) { 選択 (c[0]) { 場合 "var": frames[frames.個数 - 1][c[1]] = c[2].数に(); 抜ける; 場合 "set": 場合 "add": d = 찾기(c[1]); もし (d >= 0) { もし (c[0] == "set") { frames[d][c[1]] = c[2].数に(); } でなければ { frames[d][c[1]] = frames[d][c[1]] + c[2].数に(); } } 抜ける; 場合 "print": d = 찾기(c[1]); もし (d >= 0) { printed.追加("" + frames[d][c[1]]); } でなければ { printed.追加("?"); } 抜ける; それ以外: frames.追加(辞書()); // 부를 때마다 빈 칸에서 시작한다 실행(funcs[c[1]]); frames.位置で取り除く(frames.個数 - 1); // 끝나면 그 칸은 사라진다 抜ける; } }}돌리기(동적인가){ dynamic = 동적인가; frames = [辞書()]; printed = []; 실행(main); 返す printed;}lex = 돌리기(偽);dyn = 돌리기(真);繰り返す (i = 0; i < lex.個数; i++){ コンソール.書く(lex[i] + " " + dyn[i]);}