dazzle_core/scheme/
compiler.rs

1//! Bytecode compiler for Scheme expressions
2//!
3//! This module compiles arena-based values (ValueId/ValueData) into bytecode instructions.
4//! Following OpenJade's compilation strategy where expressions are compiled once and cached.
5//!
6//! ## Compilation Strategy
7//!
8//! ```cpp
9//! class Identifier {
10//!     Owner<Expression> def_;   // Parsed AST
11//!     InsnPtr insn_;            // Compiled instructions (cached!)
12//! };
13//! ```
14//!
15//! We compile ValueId expressions to instruction sequences, caching the start index.
16
17use crate::scheme::arena::{Arena, ValueData, ValueId, NIL_ID, TRUE_ID, FALSE_ID};
18use crate::scheme::instruction::{Instruction, Program};
19use std::collections::HashMap;
20
21/// Compilation environment (tracks lexical bindings)
22#[derive(Debug, Clone)]
23struct CompileEnv {
24    /// Lexical frames: Vec<frame> where each frame is HashMap<name, offset>
25    /// frames[0] is the outermost frame, frames[last] is the current frame
26    frames: Vec<HashMap<String, usize>>,
27}
28
29impl CompileEnv {
30    fn new() -> Self {
31        CompileEnv {
32            frames: vec![HashMap::new()],
33        }
34    }
35
36    fn push_frame(&mut self) {
37        self.frames.push(HashMap::new());
38    }
39
40    fn pop_frame(&mut self) {
41        self.frames.pop();
42    }
43
44    fn add_binding(&mut self, name: String, offset: usize) {
45        if let Some(frame) = self.frames.last_mut() {
46            frame.insert(name, offset);
47        }
48    }
49
50    /// Look up variable, returning (depth, offset)
51    /// depth = 0 means current frame, depth = 1 means parent frame, etc.
52    fn lookup(&self, name: &str) -> Option<(usize, usize)> {
53        for (depth, frame) in self.frames.iter().rev().enumerate() {
54            if let Some(&offset) = frame.get(name) {
55                return Some((depth, offset));
56            }
57        }
58        None
59    }
60}
61
62/// Bytecode compiler
63pub struct Compiler<'a> {
64    program: Program,
65    env: CompileEnv,
66    arena: &'a Arena,
67}
68
69impl<'a> Compiler<'a> {
70    pub fn new(arena: &'a Arena) -> Self {
71        Compiler {
72            program: Program::new(),
73            env: CompileEnv::new(),
74            arena,
75        }
76    }
77
78    /// Compile an expression and return its starting instruction pointer
79    pub fn compile(&mut self, expr_id: ValueId) -> Result<usize, String> {
80        self.compile_expr(expr_id)
81    }
82
83    /// Extract the compiled program
84    pub fn into_program(self) -> Program {
85        self.program
86    }
87
88    /// Compile an expression
89    fn compile_expr(&mut self, expr_id: ValueId) -> Result<usize, String> {
90        let expr = self.arena.get(expr_id);
91
92        match expr {
93            // Self-evaluating constants
94            ValueData::Nil | ValueData::Bool(_) | ValueData::Integer(_)
95            | ValueData::Real(_) | ValueData::Char(_) | ValueData::String(_)
96            | ValueData::Quantity { .. } | ValueData::Keyword(_) => {
97                Ok(self.program.emit(Instruction::Constant { value_id: expr_id }))
98            }
99
100            // Symbols - variable lookup
101            ValueData::Symbol(name) => {
102                let name_str = name.to_string();
103                if let Some((depth, offset)) = self.env.lookup(&name_str) {
104                    Ok(self.program.emit(Instruction::Variable { depth, offset }))
105                } else {
106                    Ok(self.program.emit(Instruction::GlobalVariable { name: name_str }))
107                }
108            }
109
110            // Pairs - special forms or function application
111            ValueData::Pair { car, cdr, .. } => {
112                let first = self.arena.get(*car);
113
114                // Check for special forms
115                if let ValueData::Symbol(name) = first {
116                    match name.as_ref() {
117                        "quote" => return self.compile_quote(*cdr),
118                        "if" => return self.compile_if(*cdr),
119                        "lambda" => return self.compile_lambda(*cdr),
120                        "begin" => return self.compile_begin(*cdr),
121                        "set!" => return self.compile_set(*cdr),
122                        "and" => return self.compile_and(*cdr),
123                        "or" => return self.compile_or(*cdr),
124                        "let" => return self.compile_let(*cdr),
125                        "let*" => return self.compile_let_star(*cdr),
126                        "letrec" => return self.compile_letrec(*cdr),
127                        "cond" => return self.compile_cond(*cdr),
128                        "case" => return self.compile_case(*cdr),
129                        "define" => return self.compile_define(*cdr),
130                        "define-unit" => return self.compile_define_unit(*cdr),
131                        "declare-initial-value" => return self.compile_declare_initial_value(*cdr),
132                        "declare-characteristic" => return self.compile_declare_characteristic(*cdr),
133                        "declare-flow-object-class" => return self.compile_declare_flow_object_class(*cdr),
134                        "define-language" => return self.compile_define_language(*cdr),
135                        _ => {}
136                    }
137                }
138
139                // Regular function application
140                self.compile_application(*car, *cdr)
141            }
142
143            _ => Err(format!("Cannot compile: {:?}", expr)),
144        }
145    }
146
147    /// Compile (quote expr)
148    fn compile_quote(&mut self, args_id: ValueId) -> Result<usize, String> {
149        let args = self.arena.get(args_id);
150        match args {
151            ValueData::Pair { car, .. } => {
152                Ok(self.program.emit(Instruction::Constant { value_id: *car }))
153            }
154            _ => Err("quote: expected argument".to_string()),
155        }
156    }
157
158    /// Compile (if test consequent alternative)
159    fn compile_if(&mut self, args_id: ValueId) -> Result<usize, String> {
160        let args_vec = self.list_to_vec(args_id)?;
161
162        if args_vec.len() < 2 || args_vec.len() > 3 {
163            return Err("if: expected 2 or 3 arguments".to_string());
164        }
165
166        let test = args_vec[0];
167        let consequent = args_vec[1];
168        let alternative = args_vec.get(2).copied();
169
170        // Compile test (this is the start IP we'll return)
171        let start_ip = self.compile_expr(test)?;
172
173        // Emit Test instruction (will patch else_ip later)
174        let test_ip = self.program.emit(Instruction::Test { else_ip: 0 });
175
176        // Compile consequent
177        self.compile_expr(consequent)?;
178
179        // Jump over alternative
180        let jump_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
181
182        // Patch Test to jump to alternative
183        let else_ip = self.program.instructions.len();
184        self.program.patch_jump(test_ip, else_ip);
185
186        // Compile alternative (or #f if missing)
187        if let Some(alt) = alternative {
188            self.compile_expr(alt)?;
189        } else {
190            self.program.emit(Instruction::Constant { value_id: FALSE_ID });
191        }
192
193        // Patch jump to end
194        let end_ip = self.program.instructions.len();
195        self.program.patch_jump(jump_ip, end_ip);
196
197        Ok(start_ip)
198    }
199
200    /// Compile (lambda (params...) body...)
201    fn compile_lambda(&mut self, args_id: ValueId) -> Result<usize, String> {
202        let args_vec = self.list_to_vec(args_id)?;
203
204        if args_vec.len() < 2 {
205            return Err("lambda: expected parameters and body".to_string());
206        }
207
208        let params_id = args_vec[0];
209        let body_ids = &args_vec[1..];
210
211        // Parse parameter list
212        let (params, required_count) = self.parse_params(params_id)?;
213
214        // Find free variables in the lambda body
215        let mut bound = std::collections::HashSet::new();
216        for param in &params {
217            bound.insert(param.clone());
218        }
219
220        // Collect all free variables from all body expressions
221        let mut all_free_vars = Vec::new();
222        for &body_id in body_ids {
223            let free_vars = self.find_free_variables(body_id, &bound);
224            for fv in free_vars {
225                if !all_free_vars.contains(&fv) {
226                    all_free_vars.push(fv);
227                }
228            }
229        }
230
231        // Start instruction sequence: push free variables onto stack
232        let start_ip = self.program.instructions.len();
233        for free_var in &all_free_vars {
234            // Emit Variable lookup for each free variable
235            if let Some((depth, offset)) = self.env.lookup(free_var) {
236                self.program.emit(Instruction::Variable { depth, offset });
237            } else {
238                // If not found in local env, it's global - emit GlobalVariable
239                self.program.emit(Instruction::GlobalVariable { name: free_var.clone() });
240            }
241        }
242
243        // Emit MakeClosure with correct n_free
244        let closure_ip = self.program.emit(Instruction::MakeClosure {
245            params: params.clone(),
246            required_count,
247            body_ip: 0,
248            n_free: all_free_vars.len(),
249        });
250
251        // Jump over lambda body
252        let skip_body_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
253
254        // Compile body in new environment
255        let body_ip = self.program.instructions.len();
256        self.env.push_frame();
257        for (i, param) in params.iter().enumerate() {
258            self.env.add_binding(param.clone(), i);
259        }
260
261        // Compile body expressions (implicit begin)
262        for &body_id in body_ids {
263            self.compile_expr(body_id)?;
264            if body_id != *body_ids.last().unwrap() {
265                self.program.emit(Instruction::Pop);
266            }
267        }
268
269        self.program.emit(Instruction::Return);
270        self.env.pop_frame();
271
272        // Patch MakeClosure with body_ip
273        match &mut self.program.instructions[closure_ip] {
274            Instruction::MakeClosure { body_ip: ref mut b, .. } => *b = body_ip,
275            _ => unreachable!(),
276        }
277
278        // Patch skip jump
279        let after_body_ip = self.program.instructions.len();
280        self.program.patch_jump(skip_body_ip, after_body_ip);
281
282        Ok(start_ip)
283    }
284
285    /// Compile (begin expr...)
286    fn compile_begin(&mut self, args_id: ValueId) -> Result<usize, String> {
287        let exprs = self.list_to_vec(args_id)?;
288
289        if exprs.is_empty() {
290            return Ok(self.program.emit(Instruction::Constant { value_id: NIL_ID }));
291        }
292
293        let start_ip = self.compile_expr(exprs[0])?;
294
295        for &expr in &exprs[1..] {
296            self.program.emit(Instruction::Pop);
297            self.compile_expr(expr)?;
298        }
299
300        Ok(start_ip)
301    }
302
303    /// Compile (set! var value)
304    fn compile_set(&mut self, args_id: ValueId) -> Result<usize, String> {
305        let args_vec = self.list_to_vec(args_id)?;
306
307        if args_vec.len() != 2 {
308            return Err("set!: expected 2 arguments".to_string());
309        }
310
311        let var_id = args_vec[0];
312        let value_id = args_vec[1];
313
314        // Get variable name
315        let var_data = self.arena.get(var_id);
316        let name = match var_data {
317            ValueData::Symbol(n) => n.to_string(),
318            _ => return Err("set!: first argument must be symbol".to_string()),
319        };
320
321        // Compile value expression
322        let start_ip = self.compile_expr(value_id)?;
323
324        // Emit set instruction based on variable location
325        if let Some((depth, offset)) = self.env.lookup(&name) {
326            self.program.emit(Instruction::SetVariable { depth, offset });
327        } else {
328            self.program.emit(Instruction::SetGlobalVariable { name });
329        }
330
331        Ok(start_ip)
332    }
333
334    /// Compile (and expr...)
335    fn compile_and(&mut self, args_id: ValueId) -> Result<usize, String> {
336        let exprs = self.list_to_vec(args_id)?;
337
338        if exprs.is_empty() {
339            return Ok(self.program.emit(Instruction::Constant { value_id: TRUE_ID }));
340        }
341
342        let mut jump_ips = Vec::new();
343        let start_ip = self.compile_expr(exprs[0])?;
344
345        for &expr in &exprs[1..] {
346            // Test current value - if false, jump to end
347            let test_ip = self.program.emit(Instruction::Test { else_ip: 0 });
348            jump_ips.push(test_ip);
349
350            // Pop true value and evaluate next
351            self.program.emit(Instruction::Pop);
352            self.compile_expr(expr)?;
353        }
354
355        // Patch all test jumps to end
356        let end_ip = self.program.instructions.len();
357        for test_ip in jump_ips {
358            self.program.patch_jump(test_ip, end_ip);
359        }
360
361        Ok(start_ip)
362    }
363
364    /// Compile (or expr...)
365    fn compile_or(&mut self, args_id: ValueId) -> Result<usize, String> {
366        let exprs = self.list_to_vec(args_id)?;
367
368        if exprs.is_empty() {
369            return Ok(self.program.emit(Instruction::Constant { value_id: FALSE_ID }));
370        }
371
372        let mut jump_ips = Vec::new();
373        let start_ip = self.compile_expr(exprs[0])?;
374
375        for &expr in &exprs[1..] {
376            // Duplicate value on stack for testing
377            // Test current value - if true, jump to end (keep value)
378            // Note: We need to keep the true value, so we duplicate before testing
379            // For now, use a simpler approach: test, if false pop and continue
380            let test_ip = self.program.emit(Instruction::Test { else_ip: 0 });
381
382            // If true, jump to end with current value
383            let jump_true = self.program.emit(Instruction::Jump { target_ip: 0 });
384            jump_ips.push(jump_true);
385
386            // Patch test to continue here if false
387            let continue_ip = self.program.instructions.len();
388            self.program.patch_jump(test_ip, continue_ip);
389
390            // Pop false value and evaluate next
391            self.program.emit(Instruction::Pop);
392            self.compile_expr(expr)?;
393        }
394
395        // Patch all jump-to-end instructions
396        let end_ip = self.program.instructions.len();
397        for jump_ip in jump_ips {
398            self.program.patch_jump(jump_ip, end_ip);
399        }
400
401        Ok(start_ip)
402    }
403
404    /// Compile (let ((var val)...) body...) or (let name ((var val)...) body...)
405    ///
406    /// Standard let: (let ((x 1) (y 2)) body...)
407    /// Into: ((lambda (x y) body...) 1 2)
408    ///
409    /// Named let: (let loop ((x 1) (y 2)) body...)
410    /// Into: (letrec ((loop (lambda (x y) body...))) (loop 1 2))
411    fn compile_let(&mut self, args_id: ValueId) -> Result<usize, String> {
412        let args_vec = self.list_to_vec(args_id)?;
413
414        if args_vec.is_empty() {
415            return Err("let: expected bindings and body".to_string());
416        }
417
418        // Check if this is named let: (let name ((var val)...) body...)
419        let first_data = self.arena.get(args_vec[0]);
420        if let ValueData::Symbol(loop_name) = first_data {
421            if args_vec.len() < 3 {
422                return Err("named let: expected name, bindings, and body".to_string());
423            }
424
425            // Named let - delegate to compile_named_let
426            return self.compile_named_let(loop_name.to_string(), &args_vec[1..]);
427        }
428
429        // Standard let
430        let bindings_id = args_vec[0];
431        let body_ids = &args_vec[1..];
432
433        if body_ids.is_empty() {
434            return Err("let: expected body expressions".to_string());
435        }
436
437        // Parse bindings: ((var val) ...)
438        let bindings = self.list_to_vec(bindings_id)?;
439        let mut vars = Vec::new();
440        let mut vals = Vec::new();
441
442        for binding_id in bindings {
443            let binding = self.list_to_vec(binding_id)?;
444            if binding.len() != 2 {
445                return Err("let: binding must be (var val)".to_string());
446            }
447
448            let var_data = self.arena.get(binding[0]);
449            match var_data {
450                ValueData::Symbol(name) => vars.push(name.to_string()),
451                _ => return Err("let: variable must be symbol".to_string()),
452            }
453
454            vals.push(binding[1]);
455        }
456
457        // Compile as lambda application: ((lambda (vars...) body...) vals...)
458        let start_ip = self.program.instructions.len();
459
460        // Compile values first (they become arguments)
461        for &val_id in &vals {
462            self.compile_expr(val_id)?;
463        }
464
465        // Create lambda with vars as parameters and body
466        // We need to manually inline the lambda compilation here
467        let closure_ip = self.program.emit(Instruction::MakeClosure {
468            params: vars.clone(),
469            required_count: vars.len(),
470            body_ip: 0,
471            n_free: 0,
472        });
473
474        let skip_body_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
475
476        // Compile body in new environment
477        let body_ip = self.program.instructions.len();
478        self.env.push_frame();
479        for (i, var) in vars.iter().enumerate() {
480            self.env.add_binding(var.clone(), i);
481        }
482
483        for (idx, &body_id) in body_ids.iter().enumerate() {
484            self.compile_expr(body_id)?;
485            if idx < body_ids.len() - 1 {
486                self.program.emit(Instruction::Pop);
487            }
488        }
489
490        self.program.emit(Instruction::Return);
491        self.env.pop_frame();
492
493        // Patch MakeClosure with body_ip
494        match &mut self.program.instructions[closure_ip] {
495            Instruction::MakeClosure { body_ip: ref mut b, .. } => *b = body_ip,
496            _ => unreachable!(),
497        }
498
499        let after_body_ip = self.program.instructions.len();
500        self.program.patch_jump(skip_body_ip, after_body_ip);
501
502        // Apply the lambda immediately
503        self.program.emit(Instruction::Apply { n_args: vals.len() });
504
505        Ok(start_ip)
506    }
507
508    /// Compile (let* ((var val)...) body...)
509    ///
510    /// Sequential binding: (let* ((x 1) (y x)) body)
511    /// Transforms to nested lets: (let ((x 1)) (let ((y x)) body))
512    fn compile_let_star(&mut self, args_id: ValueId) -> Result<usize, String> {
513        let args_vec = self.list_to_vec(args_id)?;
514
515        if args_vec.is_empty() {
516            return Err("let*: expected bindings and body".to_string());
517        }
518
519        let bindings_id = args_vec[0];
520        let body_ids = &args_vec[1..];
521
522        if body_ids.is_empty() {
523            return Err("let*: expected body expressions".to_string());
524        }
525
526        let bindings = self.list_to_vec(bindings_id)?;
527
528        // Empty bindings case: (let* () body...) => (begin body...)
529        if bindings.is_empty() {
530            if body_ids.len() == 1 {
531                return self.compile_expr(body_ids[0]);
532            } else {
533                // Build begin form
534                let start_ip = self.compile_expr(body_ids[0])?;
535                for &body_id in &body_ids[1..] {
536                    self.program.emit(Instruction::Pop);
537                    self.compile_expr(body_id)?;
538                }
539                return Ok(start_ip);
540            }
541        }
542
543        // Parse all bindings upfront to avoid borrow issues
544        let mut parsed_bindings = Vec::new();
545        for &binding_id in &bindings {
546            let binding = self.list_to_vec(binding_id)?;
547            if binding.len() != 2 {
548                return Err("let*: binding must be (var val)".to_string());
549            }
550
551            let var_data = self.arena.get(binding[0]);
552            let var_name = match var_data {
553                ValueData::Symbol(name) => name.to_string(),
554                _ => return Err("let*: variable must be symbol".to_string()),
555            };
556
557            parsed_bindings.push((var_name, binding[1]));
558        }
559
560        // Compile as nested lambda applications
561        // (let* ((x 1) (y x)) body) => ((lambda (x) ((lambda (y) body) x)) 1)
562        let start_ip = self.compile_let_star_helper(&parsed_bindings, body_ids, 0)?;
563
564        Ok(start_ip)
565    }
566
567    /// Helper to recursively compile let* as nested lambdas
568    fn compile_let_star_helper(
569        &mut self,
570        bindings: &[(String, ValueId)],
571        body_ids: &[ValueId],
572        index: usize,
573    ) -> Result<usize, String> {
574        if index >= bindings.len() {
575            // No more bindings: compile body
576            let start_ip = self.compile_expr(body_ids[0])?;
577            for &body_id in &body_ids[1..] {
578                self.program.emit(Instruction::Pop);
579                self.compile_expr(body_id)?;
580            }
581            return Ok(start_ip);
582        }
583
584        let (var_name, val_id) = &bindings[index];
585
586        // Compile value expression (this becomes the argument)
587        let start_ip = self.compile_expr(*val_id)?;
588
589        // Create lambda for this binding
590        let closure_ip = self.program.emit(Instruction::MakeClosure {
591            params: vec![var_name.clone()],
592            required_count: 1,
593            body_ip: 0,
594            n_free: 0,
595        });
596
597        let skip_body_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
598
599        // Compile lambda body (which contains the rest of the bindings + final body)
600        let body_ip = self.program.instructions.len();
601        self.env.push_frame();
602        self.env.add_binding(var_name.clone(), 0);
603
604        // Recursively compile remaining bindings and body
605        self.compile_let_star_helper(bindings, body_ids, index + 1)?;
606
607        self.program.emit(Instruction::Return);
608        self.env.pop_frame();
609
610        // Patch MakeClosure with body_ip
611        match &mut self.program.instructions[closure_ip] {
612            Instruction::MakeClosure { body_ip: ref mut b, .. } => *b = body_ip,
613            _ => unreachable!(),
614        }
615
616        // Patch skip jump
617        let after_body_ip = self.program.instructions.len();
618        self.program.patch_jump(skip_body_ip, after_body_ip);
619
620        // Apply the lambda immediately
621        self.program.emit(Instruction::Apply { n_args: 1 });
622
623        Ok(start_ip)
624    }
625
626    /// Compile named let: (let loop ((x 1) (y 2)) body...)
627    /// Transforms to: (letrec ((loop (lambda (x y) body...))) (loop 1 2))
628    fn compile_named_let(&mut self, loop_name: String, args: &[ValueId]) -> Result<usize, String> {
629        if args.is_empty() {
630            return Err("named let: expected bindings and body".to_string());
631        }
632
633        let bindings_id = args[0];
634        let body_ids = &args[1..];
635
636        if body_ids.is_empty() {
637            return Err("named let: expected body expressions".to_string());
638        }
639
640        // Parse bindings to extract vars and initial values
641        let bindings = self.list_to_vec(bindings_id)?;
642        let mut vars = Vec::new();
643        let mut init_values = Vec::new();
644
645        for &binding_id in &bindings {
646            let binding = self.list_to_vec(binding_id)?;
647            if binding.len() != 2 {
648                return Err("named let: binding must be (var val)".to_string());
649            }
650
651            let var_data = self.arena.get(binding[0]);
652            match var_data {
653                ValueData::Symbol(name) => vars.push(name.to_string()),
654                _ => return Err("named let: variable must be symbol".to_string()),
655            }
656
657            init_values.push(binding[1]);
658        }
659
660        // Compile as: (letrec ((loop (lambda (vars...) body...))) (loop init_values...))
661        // This is equivalent to creating a recursive closure and immediately calling it
662
663        let start_ip = self.program.instructions.len();
664
665        // Compile initial values (these become arguments to the loop function)
666        for &val_id in &init_values {
667            self.compile_expr(val_id)?;
668        }
669
670        // Create the lambda body in a new environment where loop_name is bound
671        // We'll create a closure that captures loop_name from the letrec environment
672
673        // First, create the lambda: (lambda (vars...) body...)
674        let closure_ip = self.program.emit(Instruction::MakeClosure {
675            params: vars.clone(),
676            required_count: vars.len(),
677            body_ip: 0,
678            n_free: 0,  // Will be in letrec environment
679        });
680
681        let skip_lambda_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
682
683        // Compile lambda body with loop_name available for recursion
684        let lambda_body_ip = self.program.instructions.len();
685        self.env.push_frame();
686
687        // Bind parameters
688        for (i, var) in vars.iter().enumerate() {
689            self.env.add_binding(var.clone(), i);
690        }
691
692        // The loop name will be available via closure from parent scope (letrec)
693        // Add it as a free variable that will be captured
694
695        // Actually, we need to handle this more carefully. In letrec, the function
696        // being defined can refer to itself. We'll handle this by making the loop_name
697        // available in the environment where the lambda executes.
698
699        // For now, let's use a simpler approach: add loop_name to globals temporarily
700        // This isn't perfect but will work for the common case
701
702        // Compile body expressions
703        for (idx, &body_id) in body_ids.iter().enumerate() {
704            self.compile_expr(body_id)?;
705            if idx < body_ids.len() - 1 {
706                self.program.emit(Instruction::Pop);
707            }
708        }
709
710        self.program.emit(Instruction::Return);
711        self.env.pop_frame();
712
713        // Patch lambda body_ip
714        match &mut self.program.instructions[closure_ip] {
715            Instruction::MakeClosure { body_ip: ref mut b, .. } => *b = lambda_body_ip,
716            _ => unreachable!(),
717        }
718
719        let after_lambda_ip = self.program.instructions.len();
720        self.program.patch_jump(skip_lambda_ip, after_lambda_ip);
721
722        // Now we have the lambda on the stack, and below it are the initial values
723        // We need to: 1) define loop_name = lambda, 2) call loop with initial values
724
725        // For simplicity with letrec semantics, we'll:
726        // - Define loop_name as the closure (DefineGlobal for now - not perfect but works)
727        // - Load loop_name
728        // - Apply with the initial values we pushed earlier
729
730        self.program.emit(Instruction::DefineGlobal { name: loop_name.clone() });
731
732        // Now load it back and apply
733        self.program.emit(Instruction::GlobalVariable { name: loop_name });
734        self.program.emit(Instruction::Apply { n_args: init_values.len() });
735
736        Ok(start_ip)
737    }
738
739    /// Compile (letrec ((var val)...) body...)
740    fn compile_letrec(&mut self, args_id: ValueId) -> Result<usize, String> {
741        let args_vec = self.list_to_vec(args_id)?;
742
743        if args_vec.is_empty() {
744            return Err("letrec: expected bindings and body".to_string());
745        }
746
747        let bindings_id = args_vec[0];
748        let body_ids = &args_vec[1..];
749
750        if body_ids.is_empty() {
751            return Err("letrec: expected body expressions".to_string());
752        }
753
754        // Parse bindings
755        let bindings = self.list_to_vec(bindings_id)?;
756        let mut var_names = Vec::new();
757        let mut val_ids = Vec::new();
758
759        for &binding_id in &bindings {
760            let binding = self.list_to_vec(binding_id)?;
761            if binding.len() != 2 {
762                return Err("letrec: binding must be (var val)".to_string());
763            }
764
765            let var_data = self.arena.get(binding[0]);
766            match var_data {
767                ValueData::Symbol(name) => var_names.push(name.to_string()),
768                _ => return Err("letrec: variable must be symbol".to_string()),
769            }
770
771            val_ids.push(binding[1]);
772        }
773
774        // letrec is tricky because the bindings can refer to each other recursively
775        // The standard implementation uses a "black hole" or undefined initial value
776        // For simplicity, we'll use a similar approach to named let:
777        // - Define all variables as globals temporarily
778        // - Evaluate all values (which can now refer to the names)
779        // - Define them properly
780        // This isn't perfect but works for the common case of mutually recursive functions
781
782        let start_ip = self.program.instructions.len();
783
784        // Evaluate each value expression and define it
785        for (name, val_id) in var_names.iter().zip(val_ids.iter()) {
786            self.compile_expr(*val_id)?;
787            self.program.emit(Instruction::DefineGlobal { name: name.clone() });
788        }
789
790        // Now compile body with all names defined
791        for (idx, &body_id) in body_ids.iter().enumerate() {
792            self.compile_expr(body_id)?;
793            if idx < body_ids.len() - 1 {
794                self.program.emit(Instruction::Pop);
795            }
796        }
797
798        Ok(start_ip)
799    }
800
801    /// Compile (cond (test expr...)... [(else expr...)])
802    fn compile_cond(&mut self, args_id: ValueId) -> Result<usize, String> {
803        let clauses = self.list_to_vec(args_id)?;
804
805        if clauses.is_empty() {
806            return Ok(self.program.emit(Instruction::Constant { value_id: NIL_ID }));
807        }
808
809        let mut jump_to_end = Vec::new();
810        let mut start_ip = 0;
811
812        for (idx, &clause_id) in clauses.iter().enumerate() {
813            let clause = self.list_to_vec(clause_id)?;
814            if clause.is_empty() {
815                return Err("cond: clause must have at least a test".to_string());
816            }
817
818            let test_id = clause[0];
819            let test_data = self.arena.get(test_id);
820
821            // Check for else clause
822            let is_else = matches!(test_data, ValueData::Symbol(name) if name.as_ref() == "else");
823
824            if is_else {
825                if idx != clauses.len() - 1 {
826                    return Err("cond: else clause must be last".to_string());
827                }
828
829                // Compile else body
830                if clause.len() == 1 {
831                    self.program.emit(Instruction::Constant { value_id: NIL_ID });
832                } else {
833                    for (i, &expr_id) in clause[1..].iter().enumerate() {
834                        self.compile_expr(expr_id)?;
835                        if i < clause.len() - 2 {
836                            self.program.emit(Instruction::Pop);
837                        }
838                    }
839                }
840            } else {
841                // Compile test
842                if idx == 0 {
843                    start_ip = self.compile_expr(test_id)?;
844                } else {
845                    self.compile_expr(test_id)?;
846                }
847
848                // Test instruction
849                let test_ip = self.program.emit(Instruction::Test { else_ip: 0 });
850
851                // Compile consequent (test value already popped by Test instruction)
852                if clause.len() == 1 {
853                    // No consequent: need to return test value, but Test already popped it
854                    // Re-push the test value - for now, use #t as placeholder
855                    // TODO: Need Dup instruction or different Test behavior
856                    self.program.emit(Instruction::Constant { value_id: TRUE_ID });
857                } else {
858                    // Have consequent: Test already popped test value, so just evaluate consequent
859                    for (i, &expr_id) in clause[1..].iter().enumerate() {
860                        self.compile_expr(expr_id)?;
861                        if i < clause.len() - 2 {
862                            self.program.emit(Instruction::Pop);
863                        }
864                    }
865                }
866
867                // Jump to end
868                let jump_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
869                jump_to_end.push(jump_ip);
870
871                // Patch test to continue here if false
872                let else_ip = self.program.instructions.len();
873                self.program.patch_jump(test_ip, else_ip);
874            }
875        }
876
877        // If no else clause, push #f as default
878        if clauses.len() > 0 {
879            let last_clause_id = clauses[clauses.len() - 1];
880            let last_clause_data = self.arena.get(last_clause_id);
881            let last_is_else = if let ValueData::Pair { car, .. } = last_clause_data {
882                let test_data = self.arena.get(*car);
883                matches!(test_data, ValueData::Symbol(name) if name.as_ref() == "else")
884            } else {
885                false
886            };
887
888            if !last_is_else {
889                self.program.emit(Instruction::Constant { value_id: FALSE_ID });
890            }
891        }
892
893        // Patch all jumps to end
894        let end_ip = self.program.instructions.len();
895        for jump_ip in jump_to_end {
896            self.program.patch_jump(jump_ip, end_ip);
897        }
898
899        Ok(start_ip)
900    }
901
902    /// Compile (case key ((datum...) expr...)... [(else expr...)])
903    fn compile_case(&mut self, args_id: ValueId) -> Result<usize, String> {
904        let args_vec = self.list_to_vec(args_id)?;
905
906        if args_vec.is_empty() {
907            return Err("case: expected key expression".to_string());
908        }
909
910        let key_expr = args_vec[0];
911        let clauses = &args_vec[1..];
912
913        if clauses.is_empty() {
914            return Err("case: expected at least one clause".to_string());
915        }
916
917        // Compile key expression
918        let start_ip = self.compile_expr(key_expr)?;
919
920        let mut jump_to_end = Vec::new();
921
922        for (idx, &clause_id) in clauses.iter().enumerate() {
923            let clause = self.list_to_vec(clause_id)?;
924            if clause.len() < 2 {
925                return Err("case: clause must have datums and body".to_string());
926            }
927
928            let datums_id = clause[0];
929            let datums_data = self.arena.get(datums_id);
930
931            // Check for else clause
932            let is_else = matches!(datums_data, ValueData::Symbol(name) if name.as_ref() == "else");
933
934            if is_else {
935                if idx != clauses.len() - 1 {
936                    return Err("case: else clause must be last".to_string());
937                }
938
939                // Pop key value (we don't need it)
940                self.program.emit(Instruction::Pop);
941
942                // Compile else body
943                for (i, &expr_id) in clause[1..].iter().enumerate() {
944                    self.compile_expr(expr_id)?;
945                    if i < clause.len() - 2 {
946                        self.program.emit(Instruction::Pop);
947                    }
948                }
949            } else {
950                // Parse datum list
951                let datums = self.list_to_vec(datums_id)?;
952                if datums.is_empty() {
953                    return Err("case: datum list must not be empty".to_string());
954                }
955
956                let mut jump_to_body = Vec::new();
957
958                // Test key against each datum
959                for &datum_id in datums.iter() {
960                    // Duplicate key on stack before comparison
961                    // Stack before: [key]
962                    self.program.emit(Instruction::Dup);
963                    // Stack after: [key, key]
964
965                    // Push datum as constant (datums are NOT evaluated in case)
966                    self.program.emit(Instruction::Constant { value_id: datum_id });
967                    // Stack: [key, key, datum]
968
969                    // Equal pops both operands and pushes result
970                    // This consumes the duplicated key and datum
971                    self.program.emit(Instruction::Equal);
972                    // Stack: [key, result]
973
974                    // Test result (pops result)
975                    // If true (match), continue to next instruction (Jump to body)
976                    // If false (no match), jump to next datum test or next clause
977                    let test_ip = self.program.emit(Instruction::Test { else_ip: 0 });
978                    // Stack: [key]
979
980                    // If we get here, the test passed - jump to body
981                    let jump_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
982                    jump_to_body.push(jump_ip);
983
984                    // Patch Test to jump here (next datum test or next clause) if test failed
985                    let next_test_ip = self.program.instructions.len();
986                    self.program.patch_jump(test_ip, next_test_ip);
987                }
988
989                // None matched: jump to next clause
990                let next_clause_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
991
992                // Matched: patch all jump-to-body instructions to here, pop key, execute body
993                let body_ip = self.program.instructions.len();
994                for jump_ip in jump_to_body {
995                    self.program.patch_jump(jump_ip, body_ip);
996                }
997
998                self.program.emit(Instruction::Pop); // Pop key
999
1000                for (i, &expr_id) in clause[1..].iter().enumerate() {
1001                    self.compile_expr(expr_id)?;
1002                    if i < clause.len() - 2 {
1003                        self.program.emit(Instruction::Pop);
1004                    }
1005                }
1006
1007                // Jump to end
1008                let jump_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
1009                jump_to_end.push(jump_ip);
1010
1011                // Patch next_clause jump
1012                let next_ip = self.program.instructions.len();
1013                self.program.patch_jump(next_clause_ip, next_ip);
1014            }
1015        }
1016
1017        // No match and no else: pop key and return unspecified
1018        let last_is_else = {
1019            let last_clause_id = clauses[clauses.len() - 1];
1020            let last_clause = self.list_to_vec(last_clause_id).unwrap();
1021            if let Some(&first) = last_clause.first() {
1022                let data = self.arena.get(first);
1023                matches!(data, ValueData::Symbol(name) if name.as_ref() == "else")
1024            } else {
1025                false
1026            }
1027        };
1028
1029        if !last_is_else {
1030            self.program.emit(Instruction::Pop);
1031            use crate::scheme::arena::UNSPECIFIED_ID;
1032            self.program.emit(Instruction::Constant { value_id: UNSPECIFIED_ID });
1033        }
1034
1035        // Patch all jumps to end
1036        let end_ip = self.program.instructions.len();
1037        for jump_ip in jump_to_end {
1038            self.program.patch_jump(jump_ip, end_ip);
1039        }
1040
1041        Ok(start_ip)
1042    }
1043
1044    /// Compile (define var value) or (define (func params...) body...)
1045    fn compile_define(&mut self, args_id: ValueId) -> Result<usize, String> {
1046        let args_vec = self.list_to_vec(args_id)?;
1047
1048        if args_vec.is_empty() {
1049            return Err("define: expected at least 1 argument".to_string());
1050        }
1051
1052        let first_id = args_vec[0];
1053        let first_data = self.arena.get(first_id);
1054
1055        match first_data {
1056            // (define var value)
1057            ValueData::Symbol(name) => {
1058                if args_vec.len() != 2 {
1059                    return Err("define: expected 2 arguments".to_string());
1060                }
1061
1062                let value_id = args_vec[1];
1063
1064                // Compile value expression
1065                let start_ip = self.compile_expr(value_id)?;
1066
1067                // Emit define instruction
1068                self.program.emit(Instruction::DefineGlobal {
1069                    name: name.to_string(),
1070                });
1071
1072                Ok(start_ip)
1073            }
1074
1075            // (define (func params...) body...)
1076            // Transform to: (define func (lambda (params...) body...))
1077            ValueData::Pair {car: func_name_id, cdr: params_id, ..} => {
1078                // Extract function name
1079                let func_name_data = self.arena.get(*func_name_id);
1080                let func_name = match func_name_data {
1081                    ValueData::Symbol(n) => n.to_string(),
1082                    _ => return Err("define: function name must be symbol".to_string()),
1083                };
1084
1085                // Parse parameters (handles both proper and improper lists)
1086                let (params, required_count) = self.parse_params(*params_id)?;
1087
1088                // Body expressions
1089                let body_ids = &args_vec[1..];
1090                if body_ids.is_empty() {
1091                    return Err("define: expected function body".to_string());
1092                }
1093
1094                // Compile as (lambda (params...) body...)
1095                let start_ip = self.program.instructions.len();
1096
1097                // Emit MakeClosure
1098                let closure_ip = self.program.emit(Instruction::MakeClosure {
1099                    params: params.clone(),
1100                    required_count,
1101                    body_ip: 0,
1102                    n_free: 0,
1103                });
1104
1105                let skip_body_ip = self.program.emit(Instruction::Jump { target_ip: 0 });
1106
1107                // Compile body in new environment
1108                let body_ip = self.program.instructions.len();
1109                self.env.push_frame();
1110                for (i, param) in params.iter().enumerate() {
1111                    self.env.add_binding(param.clone(), i);
1112                }
1113
1114                for (idx, &body_id) in body_ids.iter().enumerate() {
1115                    self.compile_expr(body_id)?;
1116                    if idx < body_ids.len() - 1 {
1117                        self.program.emit(Instruction::Pop);
1118                    }
1119                }
1120
1121                self.program.emit(Instruction::Return);
1122                self.env.pop_frame();
1123
1124                // Patch MakeClosure
1125                match &mut self.program.instructions[closure_ip] {
1126                    Instruction::MakeClosure { body_ip: ref mut b, .. } => *b = body_ip,
1127                    _ => unreachable!(),
1128                }
1129
1130                let after_body_ip = self.program.instructions.len();
1131                self.program.patch_jump(skip_body_ip, after_body_ip);
1132
1133                // Emit DefineGlobal
1134                self.program.emit(Instruction::DefineGlobal { name: func_name });
1135
1136                Ok(start_ip)
1137            }
1138
1139            _ => Err("define: invalid syntax".to_string()),
1140        }
1141    }
1142
1143    /// Compile (define-unit name value)
1144    /// DSSSL unit definition - defines a unit (em, pi, pt, etc.) as a quantity value
1145    fn compile_define_unit(&mut self, args_id: ValueId) -> Result<usize, String> {
1146        let args_vec = self.list_to_vec(args_id)?;
1147
1148        if args_vec.len() != 2 {
1149            return Err("define-unit: expected exactly 2 arguments".to_string());
1150        }
1151
1152        let name_id = args_vec[0];
1153        let value_id = args_vec[1];
1154
1155        // Get unit name
1156        let name_data = self.arena.get(name_id);
1157        let name = match name_data {
1158            ValueData::Symbol(n) => n.to_string(),
1159            _ => return Err("define-unit: first argument must be symbol".to_string()),
1160        };
1161
1162        // Compile value expression
1163        let start_ip = self.compile_expr(value_id)?;
1164
1165        // Emit define instruction
1166        self.program.emit(Instruction::DefineGlobal { name });
1167
1168        Ok(start_ip)
1169    }
1170
1171    /// Compile (declare-initial-value characteristic-name value-expression)
1172    /// DSSSL initial value declaration - sets the initial value for a characteristic
1173    /// Note: characteristic-name is a bare symbol (not evaluated), value-expression is evaluated
1174    fn compile_declare_initial_value(&mut self, args_id: ValueId) -> Result<usize, String> {
1175        let args_vec = self.list_to_vec(args_id)?;
1176
1177        if args_vec.len() != 2 {
1178            return Err("declare-initial-value: expected exactly 2 arguments".to_string());
1179        }
1180
1181        let name_id = args_vec[0];
1182        let value_id = args_vec[1];
1183
1184        // Get characteristic name (not evaluated!)
1185        let name_data = self.arena.get(name_id);
1186        let name = match name_data {
1187            ValueData::Symbol(n) => n.to_string(),
1188            _ => return Err("declare-initial-value: first argument must be symbol".to_string()),
1189        };
1190
1191        // Compile value expression
1192        let start_ip = self.compile_expr(value_id)?;
1193
1194        // Define the characteristic name as a global variable with its value
1195        self.program.emit(Instruction::DefineGlobal { name });
1196
1197        Ok(start_ip)
1198    }
1199
1200    /// Compile (declare-characteristic characteristic-name inherited?)
1201    /// DSSSL characteristic declaration - no-op for code generation
1202    fn compile_declare_characteristic(&mut self, args_id: ValueId) -> Result<usize, String> {
1203        let args_vec = self.list_to_vec(args_id)?;
1204
1205        if args_vec.is_empty() || args_vec.len() > 2 {
1206            return Err("declare-characteristic: expected 1 or 2 arguments".to_string());
1207        }
1208
1209        // Validate that first argument is a symbol (but don't evaluate it)
1210        let name_data = self.arena.get(args_vec[0]);
1211        if !matches!(name_data, ValueData::Symbol(_)) {
1212            return Err("declare-characteristic: first argument must be symbol".to_string());
1213        }
1214
1215        // Return unspecified (no code generated)
1216        use crate::scheme::arena::UNSPECIFIED_ID;
1217        Ok(self.program.emit(Instruction::Constant { value_id: UNSPECIFIED_ID }))
1218    }
1219
1220    /// Compile (declare-flow-object-class class-name (parent-classes...))
1221    /// DSSSL flow object class declaration - no-op for code generation
1222    fn compile_declare_flow_object_class(&mut self, args_id: ValueId) -> Result<usize, String> {
1223        let args_vec = self.list_to_vec(args_id)?;
1224
1225        if args_vec.len() != 2 {
1226            return Err("declare-flow-object-class: expected exactly 2 arguments".to_string());
1227        }
1228
1229        // Validate that first argument is a symbol (but don't evaluate it)
1230        let name_data = self.arena.get(args_vec[0]);
1231        if !matches!(name_data, ValueData::Symbol(_)) {
1232            return Err("declare-flow-object-class: first argument must be symbol".to_string());
1233        }
1234
1235        // Return unspecified (no code generated)
1236        use crate::scheme::arena::UNSPECIFIED_ID;
1237        Ok(self.program.emit(Instruction::Constant { value_id: UNSPECIFIED_ID }))
1238    }
1239
1240    /// Compile (define-language lang-name value)
1241    /// DSSSL language definition
1242    fn compile_define_language(&mut self, args_id: ValueId) -> Result<usize, String> {
1243        let args_vec = self.list_to_vec(args_id)?;
1244
1245        if args_vec.len() != 2 {
1246            return Err("define-language: expected exactly 2 arguments".to_string());
1247        }
1248
1249        let name_id = args_vec[0];
1250        let value_id = args_vec[1];
1251
1252        // Get language name
1253        let name_data = self.arena.get(name_id);
1254        let name = match name_data {
1255            ValueData::Symbol(n) => n.to_string(),
1256            _ => return Err("define-language: first argument must be symbol".to_string()),
1257        };
1258
1259        // Compile value expression
1260        let start_ip = self.compile_expr(value_id)?;
1261
1262        // Emit define instruction
1263        self.program.emit(Instruction::DefineGlobal { name });
1264
1265        Ok(start_ip)
1266    }
1267
1268    /// Compile function application: (func arg1 arg2 ...)
1269    fn compile_application(&mut self, func_id: ValueId, args_id: ValueId) -> Result<usize, String> {
1270        // Capture start IP before compiling anything
1271        let start_ip = self.program.instructions.len();
1272
1273        // Compile arguments first (pushed left-to-right onto stack)
1274        let args = self.list_to_vec(args_id)?;
1275        for &arg_id in &args {
1276            self.compile_expr(arg_id)?;
1277        }
1278
1279        // Compile function
1280        self.compile_expr(func_id)?;
1281
1282        // Apply
1283        self.program.emit(Instruction::Apply { n_args: args.len() });
1284
1285        Ok(start_ip)
1286    }
1287
1288    /// Parse parameter list (handles both proper and improper lists)
1289    /// Returns (params, required_count)
1290    /// - Proper list (a b c) => (["a", "b", "c"], 3)
1291    /// - Improper list (a b . rest) => (["a", "b", "rest"], 2)
1292    /// - Single symbol rest => (["rest"], 0)
1293    fn parse_params(&self, params_id: ValueId) -> Result<(Vec<String>, usize), String> {
1294        let params_data = self.arena.get(params_id);
1295
1296        match params_data {
1297            ValueData::Nil => Ok((vec![], 0)),
1298            ValueData::Symbol(name) => {
1299                // Rest parameter: (lambda args ...) or (define (func . args) ...)
1300                Ok((vec![name.to_string()], 0))
1301            }
1302            ValueData::Pair { .. } => {
1303                // Parse list, handling both proper and improper lists
1304                let mut names = Vec::new();
1305                let mut current = params_id;
1306                let mut required_count = 0;
1307
1308                loop {
1309                    let data = self.arena.get(current);
1310                    match data {
1311                        ValueData::Nil => {
1312                            // End of proper list
1313                            required_count = names.len();
1314                            break;
1315                        }
1316                        ValueData::Pair { car, cdr, .. } => {
1317                            // Get the parameter name
1318                            let param_data = self.arena.get(*car);
1319                            match param_data {
1320                                ValueData::Symbol(name) => {
1321                                    names.push(name.to_string());
1322                                    current = *cdr;
1323                                }
1324                                ValueData::Pair { .. } => {
1325                                    // Destructuring parameter - not standard Scheme
1326                                    // Generate a placeholder name to allow compilation
1327                                    // Execution will fail if this code path is reached
1328                                    let placeholder = format!("__destructure_param_{}", names.len());
1329                                    eprintln!("Warning: Destructuring parameters not supported, using placeholder: {}", placeholder);
1330                                    names.push(placeholder);
1331                                    current = *cdr;
1332                                }
1333                                _ => return Err(format!("lambda: parameter must be symbol, got {:?}", param_data)),
1334                            }
1335                        }
1336                        ValueData::Symbol(rest_name) => {
1337                            // Hit a rest parameter in improper list (a b . rest)
1338                            required_count = names.len();
1339                            names.push(rest_name.to_string());
1340                            break;
1341                        }
1342                        _ => return Err(format!("lambda: invalid parameter list, got {:?}", data)),
1343                    }
1344                }
1345
1346                Ok((names, required_count))
1347            }
1348            _ => Err("lambda: invalid parameter list".to_string()),
1349        }
1350    }
1351
1352    /// Convert a list (ValueId) to Vec<ValueId>
1353    fn list_to_vec(&self, list_id: ValueId) -> Result<Vec<ValueId>, String> {
1354        let mut result = Vec::new();
1355        let mut current = list_id;
1356
1357        loop {
1358            let data = self.arena.get(current);
1359            match data {
1360                ValueData::Nil => break,
1361                ValueData::Pair { car, cdr, .. } => {
1362                    result.push(*car);
1363                    current = *cdr;
1364                }
1365                _ => return Err("Expected proper list".to_string()),
1366            }
1367        }
1368
1369        Ok(result)
1370    }
1371
1372    /// Find free variables in an expression (variables not bound in params or current env)
1373    fn find_free_variables(
1374        &self,
1375        expr_id: ValueId,
1376        bound: &std::collections::HashSet<String>,
1377    ) -> Vec<String> {
1378        let mut free_vars = Vec::new();
1379        let mut visited = std::collections::HashSet::new();
1380        self.collect_free_vars(expr_id, bound, &mut free_vars, &mut visited);
1381
1382        // Deduplicate while preserving order
1383        let mut seen = std::collections::HashSet::new();
1384        free_vars.retain(|v| seen.insert(v.clone()));
1385
1386        free_vars
1387    }
1388
1389    /// Recursively collect free variables from an expression
1390    fn collect_free_vars(
1391        &self,
1392        expr_id: ValueId,
1393        bound: &std::collections::HashSet<String>,
1394        free_vars: &mut Vec<String>,
1395        visited: &mut std::collections::HashSet<ValueId>,
1396    ) {
1397        // Avoid infinite loops on circular structures
1398        if visited.contains(&expr_id) {
1399            return;
1400        }
1401        visited.insert(expr_id);
1402
1403        let expr = self.arena.get(expr_id);
1404
1405        match expr {
1406            // Symbol: check if it's a free variable
1407            ValueData::Symbol(name) => {
1408                let name_str = name.to_string();
1409                if !bound.contains(&name_str) && self.env.lookup(&name_str).is_some() {
1410                    // It's in the outer environment but not in our bound set
1411                    free_vars.push(name_str);
1412                }
1413            }
1414
1415            // Pair: recursively check car and cdr
1416            ValueData::Pair { car, cdr, .. } => {
1417                let first = self.arena.get(*car);
1418
1419                // Handle special forms that introduce bindings
1420                if let ValueData::Symbol(name) = first {
1421                    match name.as_ref() {
1422                        "lambda" => {
1423                            // Don't analyze lambda bodies - they have their own scope
1424                            return;
1425                        }
1426                        "let" | "let*" => {
1427                            // Don't analyze let bindings - simplified for now
1428                            return;
1429                        }
1430                        "quote" => {
1431                            // Quoted expressions don't have free variables
1432                            return;
1433                        }
1434                        _ => {}
1435                    }
1436                }
1437
1438                // Regular pair: recurse on both elements
1439                self.collect_free_vars(*car, bound, free_vars, visited);
1440                self.collect_free_vars(*cdr, bound, free_vars, visited);
1441            }
1442
1443            // Other types don't contain free variables
1444            _ => {}
1445        }
1446    }
1447}
1448
1449#[cfg(test)]
1450mod tests {
1451    use super::*;
1452    use std::rc::Rc;
1453
1454    #[test]
1455    fn test_compile_constant() {
1456        let mut arena = Arena::new();
1457        let value_id = arena.int(42);
1458
1459        let mut compiler = Compiler::new(&arena);
1460        let ip = compiler.compile(value_id).unwrap();
1461
1462        assert_eq!(ip, 0);
1463        assert_eq!(compiler.program.instructions.len(), 1);
1464    }
1465
1466    #[test]
1467    fn test_compile_if() {
1468        let mut arena = Arena::new();
1469
1470        // Build (if #t 1 2)
1471        let test = TRUE_ID;
1472        let cons_val = arena.int(1);
1473        let alt_val = arena.int(2);
1474
1475        let alt_pair = arena.cons(alt_val, NIL_ID);
1476        let cons_pair = arena.cons(cons_val, alt_pair);
1477        let args = arena.cons(test, cons_pair);
1478
1479        let if_sym = arena.symbol(Rc::from("if"));
1480        let expr = arena.cons(if_sym, args);
1481
1482        let mut compiler = Compiler::new(&arena);
1483        let ip = compiler.compile(expr).unwrap();
1484
1485        assert!(ip == 0);
1486        // Should have: Constant(test), Test, Constant(consequent), Jump, Constant(alternative)
1487        assert!(compiler.program.instructions.len() >= 5);
1488    }
1489
1490    #[test]
1491    fn test_compile_or() {
1492        let mut arena = Arena::new();
1493
1494        // Build (or #f 42)
1495        let false_val = FALSE_ID;
1496        let forty_two = arena.int(42);
1497
1498        let second = arena.cons(forty_two, NIL_ID);
1499        let args = arena.cons(false_val, second);
1500
1501        let or_sym = arena.symbol(Rc::from("or"));
1502        let expr = arena.cons(or_sym, args);
1503
1504        let mut compiler = Compiler::new(&arena);
1505        let ip = compiler.compile(expr).unwrap();
1506
1507        assert_eq!(ip, 0);
1508        // Should have compiled or expression
1509        assert!(compiler.program.instructions.len() > 0);
1510    }
1511
1512    #[test]
1513    fn test_compile_let() {
1514        let mut arena = Arena::new();
1515
1516        // Build (let ((x 10)) x)
1517        let x_sym = arena.symbol(Rc::from("x"));
1518        let ten = arena.int(10);
1519
1520        // Build binding (x 10)
1521        let binding_vals = arena.cons(ten, NIL_ID);
1522        let binding = arena.cons(x_sym, binding_vals);
1523
1524        // Build bindings list ((x 10))
1525        let bindings = arena.cons(binding, NIL_ID);
1526
1527        // Build body (x)
1528        let body = arena.cons(x_sym, NIL_ID);
1529
1530        // Build args (bindings body)
1531        let args = arena.cons(bindings, body);
1532
1533        let let_sym = arena.symbol(Rc::from("let"));
1534        let expr = arena.cons(let_sym, args);
1535
1536        let mut compiler = Compiler::new(&arena);
1537        let ip = compiler.compile(expr).unwrap();
1538
1539        assert_eq!(ip, 0);
1540        // Let compiles to lambda + apply
1541        assert!(compiler.program.instructions.len() > 0);
1542    }
1543
1544    #[test]
1545    fn test_compile_define() {
1546        let mut arena = Arena::new();
1547
1548        // Build (define x 42)
1549        let x_sym = arena.symbol(Rc::from("x"));
1550        let forty_two = arena.int(42);
1551
1552        let val_list = arena.cons(forty_two, NIL_ID);
1553        let args = arena.cons(x_sym, val_list);
1554
1555        let define_sym = arena.symbol(Rc::from("define"));
1556        let expr = arena.cons(define_sym, args);
1557
1558        let mut compiler = Compiler::new(&arena);
1559        let ip = compiler.compile(expr).unwrap();
1560
1561        assert_eq!(ip, 0);
1562        // Should end with DefineGlobal
1563        let last_insn = compiler.program.instructions.last();
1564        assert!(matches!(last_insn, Some(Instruction::DefineGlobal { .. })));
1565    }
1566}
dazzle_core/scheme/compiler.rs

dazzle_core/scheme/
compiler.rs
