Run a program written in a tiny language under two variable scope rules, and print the results side by side.
The program has n lines, one command per line.
From a def f line to an end line is the definition of function f, and the lines in between are the body of f.
Function definitions appear only at the outermost level; no function is defined inside a function.
The lines outside function definitions are the top-level commands, and they run from top to bottom.
A function definition itself is not executed, and a function can be called wherever its definition is in the program.
Variables live in 'frames'. Top-level commands use the global frame.
Each time a function is called, a new empty frame is made, and the body of that function runs in that frame. When the function ends, the frame disappears.
There are five commands.
- var x v: make variable x in the current frame and put the value v in it. If x is already in the current frame, just change its value to v.
- set x v: find x and change its value to v.
- add x v: find x and add v to its value.
- print x: find x and print its value. If it is not found, print ?.
- call f: call function f. When f ends, go on to the next command.
If set or add cannot find x, they do nothing. They do not make a new variable.
'Finding' means looking at frames in a fixed order and choosing the first frame that contains x. That order is the scope rule.
Under lexical scope, look at the current frame, then the global frame.
Under dynamic scope, look at the current frame, the frame of the function that called the current function, the frame of the function that called that one, and so on, and the global frame last.
At the top level, the current frame is the global frame.
Variable names and function names are separate. The same name may be used for a variable and a function.
Run the program once with lexical scope and once with dynamic scope, each from the initial state. Both runs execute print the same number of times.
Each time a print is executed, print on one line the output under lexical scope and the output under dynamic scope, separated by a single space.
Input
The first line gives n, and the next n lines give one command each. 1 ≤ n ≤ 1,000. Names are 1–10 lowercase letters and digits starting with a lowercase letter. Every v, and every value a variable takes while running, is an integer from -10^9 to 10^9. Every def has a matching end, no function name is defined twice, and every function called with call is defined. No function calls itself, directly or through other functions. In both runs, at most 50,000 commands (including call) are executed, at most 30 function calls are open at once, and 1 to 5,000 prints are executed
Output
As many lines as prints executed
Example 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
Example 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
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
All 8 languages use lexical scope. The names a function sees depend on 'where it is written', not 'where it was called from'. Dynamic scope can be seen in old Lisps, Emacs Lisp (by default), local in bash functions, and Perl local. In the first example, show always sees the global x (1) under lexical scope, and sees x of its caller change (2, 3) under dynamic scope. The solution keeps one dictionary per frame and stacks the frames in a list: a list of Python dict, JS/TS Map[], Java List<Map<String, Integer>>, C# List<Dictionary<string, int>>, C++ std::vector<std::unordered_map<…>>, a list of Craykon Dict(). C has no dictionary, so turn names into numbers, stack (number, value) pairs in one array, and remember where each frame starts. call pushes a frame, runs the body recursively, and pops the frame. Lexical lookup checks only the top frame and frame 0; dynamic lookup checks from the top down to frame 0. Comparing with each language's real rules: Python treats a name assigned inside a function as local to the whole function, and you need global/nonlocal to change an outer one. This problem's set instead changes the frame it finds. In Craykon, assigning inside a function to a variable made at the top (outside functions) changes that variable, and a name first made inside a function belongs to that function, so the checker stops you from using it outside. JS var is function-scoped, and let/const are block-scoped. C/C++/Java/C# are block-scoped, and Java/C# forbid redeclaring an outer local's name in an inner block. Trap ① looking up dynamic scope with only the current and global frames, or looking into callers' frames under lexical scope. ② Searching dynamic scope from the global frame first (the nearest frame comes first). ③ Keeping a frame after the function ends so the next call sees old values (like a C static local). ④ Making a new variable in the current frame when set finds nothing (Python-style assignment). ⑤ Letting var change a variable that is already visible (var always uses the current frame).
Pythonmain.py · 53 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
n = Console.ReadLine().ToNumber();funcs = Dict(); // 함수 이름 → 몸체 명령들main = []; // 맨 바깥 명령들body = null;for (i = 0; i < n; i++){ t = Console.ReadLine().Trim().Split(" "); if (t[0] == "def") { body = []; funcs[t[1]] = body; } else if (t[0] == "end") { body = null; } else if (body == null) { main.Add(t); } else { body.Add(t); }}frames = []; // 0번이 전역, 끝이 지금 실행 중인 함수의 칸dynamic = false;printed = [];// 이름을 가진 칸의 번호(없으면 -1)// 정적: 지금 칸 → 전역. 동적: 지금 칸 → 부른 함수의 칸 → … → 전역찾기(name){ top = frames.Count - 1; if (dynamic) { for (d = top; d >= 0; d--) { if (frames[d].Contains(name)) { return d; } } return -1; } if (frames[top].Contains(name)) { return top; } if (frames[0].Contains(name)) { return 0; } return -1;}실행(cmds){ foreach (c in cmds) { switch (c[0]) { case "var": frames[frames.Count - 1][c[1]] = c[2].ToNumber(); break; case "set": case "add": d = 찾기(c[1]); if (d >= 0) { if (c[0] == "set") { frames[d][c[1]] = c[2].ToNumber(); } else { frames[d][c[1]] = frames[d][c[1]] + c[2].ToNumber(); } } break; case "print": d = 찾기(c[1]); if (d >= 0) { printed.Add("" + frames[d][c[1]]); } else { printed.Add("?"); } break; default: frames.Add(Dict()); // 부를 때마다 빈 칸에서 시작한다 실행(funcs[c[1]]); frames.RemoveAt(frames.Count - 1); // 끝나면 그 칸은 사라진다 break; } }}돌리기(동적인가){ dynamic = 동적인가; frames = [Dict()]; printed = []; 실행(main); return printed;}lex = 돌리기(false);dyn = 돌리기(true);for (i = 0; i < lex.Count; i++){ Console.WriteLine(lex[i] + " " + dyn[i]);}