lambdust 0.1.1

//! Bag (multiset) operations implementation for SRFI-113: Bag basic data structures.
//!
//! This module provides the primitive procedures for working with Bags in Lambdust,
//! implementing the full SRFI-113 specification for basic bag operations.

use crate::eval::value::{Value, PrimitiveProcedure, PrimitiveImpl, ThreadSafeEnvironment};
use crate::containers::HashComparator;
use crate::diagnostics::{Error, Result, Span};
use crate::effects::Effect;
use std::sync::Arc;
use std::hash::{Hash, Hasher};
use std::collections::HashMap;

/// Helper function to bind a bag primitive.
fn bind_bag_primitive(
    env: &Arc<ThreadSafeEnvironment>,
    name: &str,
    arity_min: usize,
    arity_max: Option<usize>,
    implementation: fn(&[Value]) -> Result<Value>,
) {
    env.define(name.to_string(), Value::Primitive(Arc::new(PrimitiveProcedure {
        name: name.to_string(),
        arity_min,
        arity_max,
        implementation: PrimitiveImpl::RustFn(implementation),
        effects: vec![Effect::Pure],
    })));
}

/// Helper function to bind a bag primitive with evaluator integration.
fn bind_bag_evaluator_primitive(
    env: &Arc<ThreadSafeEnvironment>,
    name: &str,
    arity_min: usize,
    arity_max: Option<usize>,
    implementation: fn(&mut crate::eval::evaluator::Evaluator, &[Value]) -> Result<Value>,
) {
    env.define(name.to_string(), Value::Primitive(Arc::new(PrimitiveProcedure {
        name: name.to_string(),
        arity_min,
        arity_max,
        implementation: PrimitiveImpl::EvaluatorIntegrated(implementation),
        effects: vec![Effect::Pure],
    })));
}

/// Helper function to create a runtime error with no span.
fn runtime_error(msg: impl Into<String>) -> Box<Error> {
    Box::new(Error::runtime_error(msg.into(), None))
}

/// Helper function to create a type error with no span.
fn type_error(msg: impl Into<String>) -> Box<Error> {
    Box::new(Error::type_error(msg.into(), Span::default()))
}

/// An immutable key type for use in hash-based collections
/// that preserves Scheme equality semantics while avoiding clippy::mutable_key_type warnings.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct ValueKey {
    /// The key representation - uses content for immutable values, pointer for mutable ones
    key_type: ValueKeyType,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum ValueKeyType {
    /// Literal values (immutable) - use string representation for hash consistency
    Literal(String),
    /// Symbols (immutable, interned)
    Symbol(crate::utils::SymbolId),
    /// Keywords (immutable)
    Keyword(String),
    /// Nil (immutable)
    Nil,
    /// Unspecified (immutable)
    Unspecified,
    /// Immutable pairs - use content-based equality
    ImmutablePair(Box<ValueKey>, Box<ValueKey>),
    /// Mutable objects - use reference-based equality (Arc pointer address)
    MutableRef(usize), // Arc::as_ptr() as usize for identity
}

impl ValueKey {
    /// Create a key from a Value, preserving Scheme equality semantics
    fn from_value(value: &Value) -> Self {
        let key_type = match value {
            Value::Literal(lit) => ValueKeyType::Literal(format!("{lit}")),
            Value::Symbol(id) => ValueKeyType::Symbol(*id),
            Value::Keyword(k) => ValueKeyType::Keyword(k.clone()),
            Value::Nil => ValueKeyType::Nil,
            Value::Unspecified => ValueKeyType::Unspecified,
            Value::Pair(car, cdr) => {
                // Immutable pairs use structural equality
                ValueKeyType::ImmutablePair(
                    Box::new(ValueKey::from_value(car)),
                    Box::new(ValueKey::from_value(cdr))
                )
            }
            // For all mutable types, use reference equality
            Value::MutablePair(car, _) => ValueKeyType::MutableRef(Arc::as_ptr(car) as usize),
            Value::Vector(vec) => ValueKeyType::MutableRef(Arc::as_ptr(vec) as usize),
            Value::Hashtable(ht) => ValueKeyType::MutableRef(Arc::as_ptr(ht) as usize),
            Value::MutableString(s) => ValueKeyType::MutableRef(Arc::as_ptr(s) as usize),
            Value::AdvancedHashTable(ht) => ValueKeyType::MutableRef(Arc::as_ptr(ht) as usize),
            Value::Ideque(ideque) => ValueKeyType::MutableRef(Arc::as_ptr(ideque) as usize),
            Value::PriorityQueue(pq) => ValueKeyType::MutableRef(Arc::as_ptr(pq) as usize),
            Value::OrderedSet(os) => ValueKeyType::MutableRef(Arc::as_ptr(os) as usize),
            Value::ListQueue(lq) => ValueKeyType::MutableRef(Arc::as_ptr(lq) as usize),
            Value::RandomAccessList(ral) => ValueKeyType::MutableRef(Arc::as_ptr(ral) as usize),
            Value::Set(set) => ValueKeyType::MutableRef(Arc::as_ptr(set) as usize),
            Value::Bag(bag) => ValueKeyType::MutableRef(Arc::as_ptr(bag) as usize),
            Value::Generator(generator) => ValueKeyType::MutableRef(Arc::as_ptr(generator) as usize),
            Value::Procedure(proc) => ValueKeyType::MutableRef(Arc::as_ptr(proc) as usize),
            Value::CaseLambda(cl) => ValueKeyType::MutableRef(Arc::as_ptr(cl) as usize),
            Value::Primitive(prim) => ValueKeyType::MutableRef(Arc::as_ptr(prim) as usize),
            Value::Continuation(cont) => ValueKeyType::MutableRef(Arc::as_ptr(cont) as usize),
            Value::Syntax(syn) => ValueKeyType::MutableRef(Arc::as_ptr(syn) as usize),
            Value::Port(port) => ValueKeyType::MutableRef(Arc::as_ptr(port) as usize),
            Value::Promise(promise) => ValueKeyType::MutableRef(Arc::as_ptr(promise) as usize),
            Value::Type(t) => ValueKeyType::MutableRef(Arc::as_ptr(t) as usize),
            Value::Foreign(foreign) => ValueKeyType::MutableRef(Arc::as_ptr(foreign) as usize),
            Value::ErrorObject(err) => ValueKeyType::MutableRef(Arc::as_ptr(err) as usize),
            Value::CharSet(charset) => ValueKeyType::MutableRef(Arc::as_ptr(charset) as usize),
            Value::Parameter(param) => ValueKeyType::MutableRef(Arc::as_ptr(param) as usize),
            Value::Record(record) => ValueKeyType::MutableRef(Arc::as_ptr(record) as usize),
            #[cfg(feature = "async-runtime")]
            Value::Future(future) => ValueKeyType::MutableRef(Arc::as_ptr(future) as usize),
            #[cfg(feature = "async-runtime")]
            Value::Channel(channel) => ValueKeyType::MutableRef(Arc::as_ptr(channel) as usize),
            #[cfg(feature = "async-runtime")]
            Value::Mutex(mutex) => ValueKeyType::MutableRef(Arc::as_ptr(mutex) as usize),
            #[cfg(feature = "async-runtime")]
            Value::Semaphore(sem) => ValueKeyType::MutableRef(Arc::as_ptr(sem) as usize),
            #[cfg(feature = "async-runtime")]
            Value::AtomicCounter(counter) => ValueKeyType::MutableRef(Arc::as_ptr(counter) as usize),
            #[cfg(feature = "async-runtime")]
            Value::DistributedNode(node) => ValueKeyType::MutableRef(Arc::as_ptr(node) as usize),
            Value::Opaque(opaque) => {
                // For trait objects, we use the Arc pointer itself as the identity
                ValueKeyType::MutableRef(Arc::as_ptr(opaque) as *const Arc<dyn std::any::Any + Send + Sync> as usize)
            }
        };
        ValueKey { key_type }
    }
}

/// Helper function to create an arity error.
fn arity_error(name: &str, _min: usize, _max: Option<usize>, actual: usize) -> Box<Error> {
    Box::new(Error::arity_error(name, actual, actual)) // Simplified for now
}

/// Helper function to check arity.
fn arity_check(name: &str, args: &[Value], min: usize, max: Option<usize>) -> Result<()> {
    if let Some(max_arity) = max {
        if args.len() < min || args.len() > max_arity {
            return Err(arity_error(name, min, max, args.len()));
        }
    } else if args.len() < min {
        return Err(arity_error(name, min, max, args.len()));
    }
    Ok(())
}

/// Installs all bag primitive procedures into the given environment.
pub fn install_bag_primitives(env: &Arc<ThreadSafeEnvironment>) {
    // Basic bag operations
    bind_bag_primitive(env, "bag", 0, None, primitive_bag);
    bind_bag_evaluator_primitive(env, "bag-unfold", 4, Some(5), primitive_bag_unfold);
    bind_bag_primitive(env, "bag?", 1, Some(1), primitive_bag_p);
    bind_bag_primitive(env, "bag-contains?", 2, Some(2), primitive_bag_contains_p);
    bind_bag_primitive(env, "bag-empty?", 1, Some(1), primitive_bag_empty_p);
    bind_bag_primitive(env, "bag-disjoint?", 2, Some(2), primitive_bag_disjoint_p);
    
    // Bag modification
    bind_bag_primitive(env, "bag-adjoin", 1, None, primitive_bag_adjoin);
    bind_bag_primitive(env, "bag-adjoin!", 1, None, primitive_bag_adjoin_mut);
    bind_bag_primitive(env, "bag-delete", 1, None, primitive_bag_delete);
    bind_bag_primitive(env, "bag-delete!", 1, None, primitive_bag_delete_mut);
    bind_bag_primitive(env, "bag-delete-all", 2, Some(2), primitive_bag_delete_all);
    bind_bag_primitive(env, "bag-delete-all!", 2, Some(2), primitive_bag_delete_all_mut);
    
    // Bag increment/decrement operations
    bind_bag_primitive(env, "bag-increment!", 3, Some(3), primitive_bag_increment_mut);
    bind_bag_primitive(env, "bag-decrement!", 3, Some(3), primitive_bag_decrement_mut);
    
    // Bag size operations
    bind_bag_primitive(env, "bag-size", 1, Some(1), primitive_bag_size);
    bind_bag_primitive(env, "bag-unique-size", 1, Some(1), primitive_bag_unique_size);
    bind_bag_primitive(env, "bag-element-count", 2, Some(2), primitive_bag_element_count);
    
    // Bag iteration (higher-order functions)
    bind_bag_evaluator_primitive(env, "bag-for-each", 2, Some(2), primitive_bag_for_each);
    bind_bag_evaluator_primitive(env, "bag-fold", 3, Some(3), primitive_bag_fold);
    bind_bag_evaluator_primitive(env, "bag-map", 2, Some(3), primitive_bag_map);
    bind_bag_evaluator_primitive(env, "bag-filter", 2, Some(2), primitive_bag_filter);
    bind_bag_evaluator_primitive(env, "bag-remove", 2, Some(2), primitive_bag_remove);
    bind_bag_evaluator_primitive(env, "bag-partition", 2, Some(2), primitive_bag_partition);
    
    // Bag mutating iteration functions
    bind_bag_evaluator_primitive(env, "bag-filter!", 2, Some(2), primitive_bag_filter_mut);
    bind_bag_evaluator_primitive(env, "bag-remove!", 2, Some(2), primitive_bag_remove_mut);
    bind_bag_evaluator_primitive(env, "bag-partition!", 2, Some(2), primitive_bag_partition_mut);
    
    // Bag conversion
    bind_bag_primitive(env, "bag->list", 1, Some(1), primitive_bag_to_list);
    bind_bag_primitive(env, "list->bag", 1, Some(2), primitive_list_to_bag);
    bind_bag_primitive(env, "bag->set", 1, Some(1), primitive_bag_to_set);
    bind_bag_primitive(env, "set->bag", 1, Some(1), primitive_set_to_bag);
    
    // Bag theory operations
    bind_bag_primitive(env, "bag-union", 0, None, primitive_bag_union);
    bind_bag_primitive(env, "bag-intersection", 0, None, primitive_bag_intersection);
    bind_bag_primitive(env, "bag-difference", 0, None, primitive_bag_difference);
    bind_bag_primitive(env, "bag-sum", 0, None, primitive_bag_sum);
    bind_bag_primitive(env, "bag-product", 0, None, primitive_bag_product);
    
    bind_bag_primitive(env, "bag-union!", 0, None, primitive_bag_union_mut);
    bind_bag_primitive(env, "bag-intersection!", 0, None, primitive_bag_intersection_mut);
    bind_bag_primitive(env, "bag-difference!", 0, None, primitive_bag_difference_mut);
    bind_bag_primitive(env, "bag-sum!", 0, None, primitive_bag_sum_mut);
    bind_bag_primitive(env, "bag-product!", 0, None, primitive_bag_product_mut);
    
    // Bag comparison
    bind_bag_primitive(env, "bag=?", 2, None, primitive_bag_equal_p);
    bind_bag_primitive(env, "bag<?", 2, None, primitive_bag_subbag_p);
    bind_bag_primitive(env, "bag>?", 2, None, primitive_bag_superbag_p);
    bind_bag_primitive(env, "bag<=?", 2, None, primitive_bag_subbag_eq_p);
    bind_bag_primitive(env, "bag>=?", 2, None, primitive_bag_superbag_eq_p);
    
    // Bag copying
    bind_bag_primitive(env, "bag-copy", 1, Some(1), primitive_bag_copy);
    
    // Bag search operations
    bind_bag_evaluator_primitive(env, "bag-search!", 4, Some(4), primitive_bag_search_mut);
}

/// Creates a new bag with the given elements.
/// (bag [comparator] element ...)
fn primitive_bag(args: &[Value]) -> Result<Value> {
    if args.is_empty() {
        // Empty bag with default comparator
        return Ok(Value::bag());
    }
    
    // Check if first argument is a comparator (simplified for now - assumes no comparator)
    // In a full implementation, we'd check SRFI-128 comparator objects
    Ok(Value::bag_from_iter(args.iter().cloned()))
}

/// Creates a bag by unfolding a generator.
/// (bag-unfold stop? mapper successor seed [comparator])
fn primitive_bag_unfold(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-unfold", args, 4, Some(5))?;
    
    let stop_predicate = &args[0];
    let mapper = &args[1]; 
    let successor = &args[2];
    let mut seed = args[3].clone();
    // Note: Optional comparator at args[4] is ignored for now
    
    let mut elements = Vec::new();
    
    loop {
        // Check if we should stop
        let should_stop = apply_procedure_with_evaluator(eval, stop_predicate, &[seed.clone()])?;
        if !should_stop.is_falsy() {
            break;
        }
        
        // Map the seed to get the element for the bag
        let element = apply_procedure_with_evaluator(eval, mapper, &[seed.clone()])?;
        elements.push(element);
        
        // Generate the next seed
        seed = apply_procedure_with_evaluator(eval, successor, &[seed])?;
        
        // Safety check to prevent infinite loops
        if elements.len() > 10000 {
            return Err(runtime_error("bag-unfold: too many iterations (>10000), possible infinite loop"));
        }
    }
    
    Ok(Value::bag_from_iter(elements))
}

/// Tests whether a value is a bag.
/// (bag? obj)
fn primitive_bag_p(args: &[Value]) -> Result<Value> {
    arity_check("bag?", args, 1, Some(1))?;
    Ok(Value::boolean(args[0].is_bag()))
}

/// Tests whether a bag contains an element.
/// (bag-contains? bag element)
fn primitive_bag_contains_p(args: &[Value]) -> Result<Value> {
    arity_check("bag-contains?", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[0] {
        match bag.contains(&args[1]) {
            Ok(result) => Ok(Value::boolean(result)),
            Err(_) => Err(runtime_error("Failed to check bag membership")),
        }
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Tests whether a bag is empty.
/// (bag-empty? bag)
fn primitive_bag_empty_p(args: &[Value]) -> Result<Value> {
    arity_check("bag-empty?", args, 1, Some(1))?;
    
    if let Value::Bag(bag) = &args[0] {
        match bag.is_empty() {
            Ok(result) => Ok(Value::boolean(result)),
            Err(_) => Err(runtime_error("Failed to check if bag is empty")),
        }
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Tests whether two bags are disjoint.
/// (bag-disjoint? bag1 bag2)
fn primitive_bag_disjoint_p(args: &[Value]) -> Result<Value> {
    arity_check("bag-disjoint?", args, 2, Some(2))?;
    
    match (&args[0], &args[1]) {
        (Value::Bag(bag1), Value::Bag(bag2)) => {
            // Check if bags have any common elements
            let vec1 = bag1.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
            for element in vec1 {
                if bag2.contains(&element).map_err(|_| runtime_error("Failed to check bag membership"))? {
                    return Ok(Value::boolean(false));
                }
            }
            Ok(Value::boolean(true))
        }
        _ => Err(type_error("Expected two bags")),
    }
}

/// Adds elements to a bag, returning a new bag.
/// (bag-adjoin bag element ...)
fn primitive_bag_adjoin(args: &[Value]) -> Result<Value> {
    if args.is_empty() {
        return Err(arity_error("bag-adjoin", 1, None, args.len()));
    }
    
    if let Value::Bag(bag) = &args[0] {
        let mut result_elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        for element in &args[1..] {
            result_elements.push(element.clone());
        }
        Ok(Value::bag_from_iter(result_elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Adds elements to a bag, modifying the bag in place.
/// (bag-adjoin! bag element ...)
fn primitive_bag_adjoin_mut(args: &[Value]) -> Result<Value> {
    if args.is_empty() {
        return Err(arity_error("bag-adjoin!", 1, None, args.len()));
    }
    
    if let Value::Bag(bag) = &args[0] {
        for element in &args[1..] {
            bag.adjoin(element.clone()).map_err(|_| runtime_error("Failed to add element to bag"))?;
        }
        Ok(Value::Unspecified)
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Removes elements from a bag, returning a new bag.
/// (bag-delete bag element ...)
fn primitive_bag_delete(args: &[Value]) -> Result<Value> {
    if args.is_empty() {
        return Err(arity_error("bag-delete", 1, None, args.len()));
    }
    
    if let Value::Bag(bag) = &args[0] {
        let mut result_elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        for element in &args[1..] {
            if let Some(pos) = result_elements.iter().position(|x| x == element) {
                result_elements.remove(pos);
            }
        }
        Ok(Value::bag_from_iter(result_elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Removes elements from a bag, modifying the bag in place.
/// (bag-delete! bag element ...)
fn primitive_bag_delete_mut(args: &[Value]) -> Result<Value> {
    if args.is_empty() {
        return Err(arity_error("bag-delete!", 1, None, args.len()));
    }
    
    if let Value::Bag(bag) = &args[0] {
        for element in &args[1..] {
            bag.delete(element).map_err(|_| runtime_error("Failed to remove element from bag"))?;
        }
        Ok(Value::Unspecified)
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Removes all instances of an element from a bag, returning a new bag.
/// (bag-delete-all bag element)
fn primitive_bag_delete_all(args: &[Value]) -> Result<Value> {
    arity_check("bag-delete-all", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[0] {
        let mut result_elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        result_elements.retain(|x| x != &args[1]);
        Ok(Value::bag_from_iter(result_elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Removes all instances of an element from a bag, modifying the bag in place.
/// (bag-delete-all! bag element)
fn primitive_bag_delete_all_mut(args: &[Value]) -> Result<Value> {
    arity_check("bag-delete-all!", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[0] {
        // Remove all instances by getting current count and decrementing that many times
        let count = bag.element_count(&args[1]).map_err(|_| runtime_error("Failed to get element count"))?;
        for _ in 0..count {
            bag.delete(&args[1]).map_err(|_| runtime_error("Failed to remove element from bag"))?;
        }
        Ok(Value::Unspecified)
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Increments the count of an element in a bag.
/// (bag-increment! bag element count)
fn primitive_bag_increment_mut(args: &[Value]) -> Result<Value> {
    arity_check("bag-increment!", args, 3, Some(3))?;
    
    if let Value::Bag(bag) = &args[0] {
        if let Value::Literal(lit) = &args[2] {
            if let Some(count) = lit.to_usize() {
                for _ in 0..count {
                    bag.adjoin(args[1].clone()).map_err(|_| runtime_error("Failed to increment element in bag"))?;
                }
                Ok(Value::Unspecified)
            } else {
                Err(type_error("Expected a non-negative integer count"))
            }
        } else {
            Err(type_error("Expected a non-negative integer count"))
        }
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Decrements the count of an element in a bag.
/// (bag-decrement! bag element count)
fn primitive_bag_decrement_mut(args: &[Value]) -> Result<Value> {
    arity_check("bag-decrement!", args, 3, Some(3))?;
    
    if let Value::Bag(bag) = &args[0] {
        if let Value::Literal(lit) = &args[2] {
            if let Some(count) = lit.to_usize() {
                for _ in 0..count {
                    bag.delete(&args[1]).map_err(|_| runtime_error("Failed to decrement element in bag"))?;
                }
                Ok(Value::Unspecified)
            } else {
                Err(type_error("Expected a non-negative integer count"))
            }
        } else {
            Err(type_error("Expected a non-negative integer count"))
        }
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Returns the total size of a bag (sum of all multiplicities).
/// (bag-size bag)
fn primitive_bag_size(args: &[Value]) -> Result<Value> {
    arity_check("bag-size", args, 1, Some(1))?;
    
    if let Value::Bag(bag) = &args[0] {
        match bag.total_size() {
            Ok(size) => Ok(Value::number(size as f64)),
            Err(_) => Err(runtime_error("Failed to get bag size")),
        }
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Returns the number of unique elements in a bag.
/// (bag-unique-size bag)
fn primitive_bag_unique_size(args: &[Value]) -> Result<Value> {
    arity_check("bag-unique-size", args, 1, Some(1))?;
    
    if let Value::Bag(bag) = &args[0] {
        match bag.unique_size() {
            Ok(size) => Ok(Value::number(size as f64)),
            Err(_) => Err(runtime_error("Failed to get bag unique size")),
        }
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Returns the multiplicity (count) of an element in a bag.
/// (bag-element-count bag element)
fn primitive_bag_element_count(args: &[Value]) -> Result<Value> {
    arity_check("bag-element-count", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[0] {
        match bag.element_count(&args[1]) {
            Ok(count) => Ok(Value::number(count as f64)),
            Err(_) => Err(runtime_error("Failed to get element count")),
        }
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Converts a bag to a list.
/// (bag->list bag)
fn primitive_bag_to_list(args: &[Value]) -> Result<Value> {
    arity_check("bag->list", args, 1, Some(1))?;
    
    if let Value::Bag(bag) = &args[0] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        Ok(crate::containers::utils::values_to_list(elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Converts a list to a bag.
/// (list->bag list [comparator])
fn primitive_list_to_bag(args: &[Value]) -> Result<Value> {
    arity_check("list->bag", args, 1, Some(2))?;
    
    if let Some(elements) = crate::containers::utils::list_to_values(&args[0]) {
        Ok(Value::bag_from_iter(elements))
    } else {
        Err(type_error("Expected a proper list"))
    }
}

/// Converts a bag to a set.
/// (bag->set bag)
fn primitive_bag_to_set(args: &[Value]) -> Result<Value> {
    arity_check("bag->set", args, 1, Some(1))?;
    
    if let Value::Bag(bag) = &args[0] {
        // Get unique elements from bag (no duplicates)
        let unique_elements: Vec<Value> = {
            let mut seen = std::collections::HashSet::new();
            let mut unique = Vec::new();
            for element in bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))? {
                let key = ValueKey::from_value(&element);
                if seen.insert(key) {
                    unique.push(element);
                }
            }
            unique
        };
        Ok(Value::set_from_iter(unique_elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Converts a set to a bag.
/// (set->bag set)
fn primitive_set_to_bag(args: &[Value]) -> Result<Value> {
    arity_check("set->bag", args, 1, Some(1))?;
    
    if let Value::Set(set) = &args[0] {
        let elements = set.to_vec().map_err(|_| runtime_error("Failed to get set elements"))?;
        Ok(Value::bag_from_iter(elements))
    } else {
        Err(type_error("Expected a set"))
    }
}

/// Creates a union of bags.
/// (bag-union bag ...)
fn primitive_bag_union(args: &[Value]) -> Result<Value> {
    if args.is_empty() {
        return Ok(Value::bag());
    }
    
    if let Value::Bag(first) = &args[0] {
        let mut result = (**first).clone();
        for bag_val in &args[1..] {
            if let Value::Bag(bag) = bag_val {
                result = result.union(bag).map_err(|_| runtime_error("Failed to compute bag union"))?;
            } else {
                return Err(type_error("Expected all arguments to be bags"));
            }
        }
        Ok(Value::Bag(Arc::new(result)))
    } else if args.len() == 1 {
        Err(type_error("Expected a bag"))
    } else {
        primitive_bag_union(&args[1..])
    }
}

/// Creates an intersection of bags.
/// (bag-intersection bag ...)
fn primitive_bag_intersection(args: &[Value]) -> Result<Value> {
    if args.is_empty() {
        return Ok(Value::bag());
    }
    
    if let Value::Bag(first) = &args[0] {
        let mut result = (**first).clone();
        for bag_val in &args[1..] {
            if let Value::Bag(bag) = bag_val {
                result = result.intersection(bag).map_err(|_| runtime_error("Failed to compute bag intersection"))?;
            } else {
                return Err(type_error("Expected all arguments to be bags"));
            }
        }
        Ok(Value::Bag(Arc::new(result)))
    } else if args.len() == 1 {
        Err(type_error("Expected a bag"))
    } else {
        primitive_bag_intersection(&args[1..])
    }
}

/// Creates a difference of bags.
/// (bag-difference bag ...)
fn primitive_bag_difference(args: &[Value]) -> Result<Value> {
    if args.is_empty() {
        return Ok(Value::bag());
    }
    
    if let Value::Bag(first) = &args[0] {
        let mut result = (**first).clone();
        for bag_val in &args[1..] {
            if let Value::Bag(bag) = bag_val {
                result = result.difference(bag).map_err(|_| runtime_error("Failed to compute bag difference"))?;
            } else {
                return Err(type_error("Expected all arguments to be bags"));
            }
        }
        Ok(Value::Bag(Arc::new(result)))
    } else if args.len() == 1 {
        Err(type_error("Expected a bag"))
    } else {
        primitive_bag_difference(&args[1..])
    }
}

/// Creates a sum of bags (alias for union).
/// (bag-sum bag ...)
fn primitive_bag_sum(args: &[Value]) -> Result<Value> {
    primitive_bag_union(args)
}

/// Creates a product of bags.
/// (bag-product bag ...)
fn primitive_bag_product(args: &[Value]) -> Result<Value> {
    if args.is_empty() {
        return Ok(Value::bag());
    }
    
    if let Value::Bag(first) = &args[0] {
        let mut result = (**first).clone();
        for bag_val in &args[1..] {
            if let Value::Bag(bag) = bag_val {
                result = result.product(bag).map_err(|_| runtime_error("Failed to compute bag product"))?;
            } else {
                return Err(type_error("Expected all arguments to be bags"));
            }
        }
        Ok(Value::Bag(Arc::new(result)))
    } else if args.len() == 1 {
        Err(type_error("Expected a bag"))
    } else {
        primitive_bag_product(&args[1..])
    }
}

// Mutating versions of theory operations (simplified - would modify first argument in practice)
fn primitive_bag_union_mut(args: &[Value]) -> Result<Value> {
    primitive_bag_union(args)?;
    Ok(Value::Unspecified)
}

fn primitive_bag_intersection_mut(args: &[Value]) -> Result<Value> {
    primitive_bag_intersection(args)?;
    Ok(Value::Unspecified)
}

fn primitive_bag_difference_mut(args: &[Value]) -> Result<Value> {
    primitive_bag_difference(args)?;
    Ok(Value::Unspecified)
}

fn primitive_bag_sum_mut(args: &[Value]) -> Result<Value> {
    primitive_bag_sum(args)?;
    Ok(Value::Unspecified)
}

fn primitive_bag_product_mut(args: &[Value]) -> Result<Value> {
    primitive_bag_product(args)?;
    Ok(Value::Unspecified)
}

/// Tests whether two bags are equal.
/// (bag=? bag1 bag2)
fn primitive_bag_equal_p(args: &[Value]) -> Result<Value> {
    if args.len() < 2 {
        return Err(arity_error("bag=?", 2, None, args.len()));
    }
    
    let first = &args[0];
    for bag in &args[1..] {
        match (first, bag) {
            (Value::Bag(bag1), Value::Bag(bag2)) => {
                // Compare element counts for all unique elements
                let vec1 = bag1.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
                let vec2 = bag2.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
                
                if vec1.len() != vec2.len() {
                    return Ok(Value::boolean(false));
                }
                
                // Count elements in both bags and compare
                let mut count1 = HashMap::new();
                let mut count2 = HashMap::new();
                
                for elem in vec1 {
                    let key = ValueKey::from_value(&elem);
                    *count1.entry(key).or_insert(0) += 1;
                }
                for elem in vec2 {
                    let key = ValueKey::from_value(&elem);
                    *count2.entry(key).or_insert(0) += 1;
                }
                
                if count1 != count2 {
                    return Ok(Value::boolean(false));
                }
            }
            _ => return Err(type_error("Expected bags")),
        }
    }
    Ok(Value::boolean(true))
}

/// Tests whether the first bag is a subbag of the second.
/// (bag<? bag1 bag2)
fn primitive_bag_subbag_p(args: &[Value]) -> Result<Value> {
    if args.len() < 2 {
        return Err(arity_error("bag<?", 2, None, args.len()));
    }
    
    for i in 0..(args.len() - 1) {
        match (&args[i], &args[i + 1]) {
            (Value::Bag(bag1), Value::Bag(bag2)) => {
                if !bag1.is_subbag(bag2).map_err(|_| runtime_error("Failed to check subbag relationship"))? {
                    return Ok(Value::boolean(false));
                }
            }
            _ => return Err(type_error("Expected bags")),
        }
    }
    Ok(Value::boolean(true))
}

/// Tests whether the first bag is a superbag of the second.
/// (bag>? bag1 bag2)
fn primitive_bag_superbag_p(args: &[Value]) -> Result<Value> {
    if args.len() < 2 {
        return Err(arity_error("bag>?", 2, None, args.len()));
    }
    
    // Reverse the arguments and check subbag
    let mut reversed_args = args.to_vec();
    reversed_args.reverse();
    primitive_bag_subbag_p(&reversed_args)
}

/// Tests whether the first bag is a subbag of or equal to the second.
/// (bag<=? bag1 bag2)
fn primitive_bag_subbag_eq_p(args: &[Value]) -> Result<Value> {
    if args.len() < 2 {
        return Err(arity_error("bag<=?", 2, None, args.len()));
    }
    
    // Check if equal first
    if let Ok(Value::Literal(crate::ast::Literal::Boolean(true))) = primitive_bag_equal_p(args) {
        return Ok(Value::boolean(true));
    }
    
    // Otherwise check subbag
    primitive_bag_subbag_p(args)
}

/// Tests whether the first bag is a superbag of or equal to the second.
/// (bag>=? bag1 bag2)
fn primitive_bag_superbag_eq_p(args: &[Value]) -> Result<Value> {
    if args.len() < 2 {
        return Err(arity_error("bag>=?", 2, None, args.len()));
    }
    
    // Check if equal first
    if let Ok(Value::Literal(crate::ast::Literal::Boolean(true))) = primitive_bag_equal_p(args) {
        return Ok(Value::boolean(true));
    }
    
    // Otherwise check superbag
    primitive_bag_superbag_p(args)
}

/// Creates a copy of a bag.
/// (bag-copy bag)
fn primitive_bag_copy(args: &[Value]) -> Result<Value> {
    arity_check("bag-copy", args, 1, Some(1))?;
    
    if let Value::Bag(bag) = &args[0] {
        // Create a new bag from the elements of the existing bag
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        Ok(Value::bag_from_iter(elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Helper function to properly apply a procedure using the evaluator's trampoline
fn apply_procedure_with_evaluator(
    evaluator: &mut crate::eval::evaluator::Evaluator,
    procedure: &Value,
    args: &[Value],
) -> Result<Value> {
    use crate::eval::evaluator::EvalStep;
    
    // Start with the initial procedure application
    let mut step = evaluator.apply_procedure(procedure.clone(), args.to_vec(), None);
    
    // Run the trampoline loop to handle all evaluation steps
    loop {
        step = match step {
            EvalStep::Return(value) => return Ok(value),
            EvalStep::Error(error) => return Err(Box::new(error)),
            EvalStep::Continue { expr, env } => {
                // Continue evaluation with the given expression and environment
                evaluator.eval_step(&expr, env)
            }
            EvalStep::TailCall { procedure: proc, args: tail_args, location } => {
                // Handle tail call by applying the procedure
                evaluator.apply_procedure(proc, tail_args, location)
            }
            EvalStep::CallContinuation { continuation, value } => {
                // Handle continuation call
                evaluator.call_continuation(continuation, value)
            }
            EvalStep::NonLocalJump { value, target_stack_depth: _ } => {
                // Non-local jump immediately returns the value
                return Ok(value);
            }
        }
    }
}

/// Applies a procedure to each element of a bag.
/// (bag-for-each proc bag)
fn primitive_bag_for_each(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-for-each", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[1] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        for element in elements {
            apply_procedure_with_evaluator(eval, &args[0], &[element])?;
        }
        Ok(Value::Unspecified)
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Folds a procedure over the elements of a bag.
/// (bag-fold proc nil bag)
fn primitive_bag_fold(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-fold", args, 3, Some(3))?;
    
    if let Value::Bag(bag) = &args[2] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        let mut accumulator = args[1].clone();
        
        for element in elements {
            accumulator = apply_procedure_with_evaluator(eval, &args[0], &[element, accumulator])?;
        }
        
        Ok(accumulator)
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Maps a procedure over the elements of a bag, returning a new bag.
/// (bag-map proc bag [comparator])
fn primitive_bag_map(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-map", args, 2, Some(3))?;
    
    if let Value::Bag(bag) = &args[1] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        let mut result_elements = Vec::new();
        
        for element in elements {
            let mapped = apply_procedure_with_evaluator(eval, &args[0], &[element])?;
            result_elements.push(mapped);
        }
        
        Ok(Value::bag_from_iter(result_elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Filters elements of a bag using a predicate, returning a new bag.
/// (bag-filter pred bag)
fn primitive_bag_filter(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-filter", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[1] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        let mut result_elements = Vec::new();
        
        for element in elements {
            let result = apply_procedure_with_evaluator(eval, &args[0], &[element.clone()])?;
            if !result.is_falsy() {
                result_elements.push(element);
            }
        }
        
        Ok(Value::bag_from_iter(result_elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Removes elements of a bag using a predicate, returning a new bag.
/// (bag-remove pred bag)
fn primitive_bag_remove(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-remove", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[1] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        let mut result_elements = Vec::new();
        
        for element in elements {
            let result = apply_procedure_with_evaluator(eval, &args[0], &[element.clone()])?;
            if result.is_falsy() {
                result_elements.push(element);
            }
        }
        
        Ok(Value::bag_from_iter(result_elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Partitions a bag into two bags based on a predicate.
/// (bag-partition pred bag)
fn primitive_bag_partition(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-partition", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[1] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        let mut true_elements = Vec::new();
        let mut false_elements = Vec::new();
        
        for element in elements {
            let result = apply_procedure_with_evaluator(eval, &args[0], &[element.clone()])?;
            if result.is_falsy() {
                false_elements.push(element);
            } else {
                true_elements.push(element);
            }
        }
        
        let true_bag = Value::bag_from_iter(true_elements);
        let false_bag = Value::bag_from_iter(false_elements);
        
        // Return as a pair (true-bag . false-bag)
        Ok(Value::pair(true_bag, false_bag))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Mutating filter for bags.
/// (bag-filter! pred bag)
fn primitive_bag_filter_mut(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-filter!", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[1] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        
        // Clear the bag and repopulate with filtered elements
        bag.clear().map_err(|_| runtime_error("Failed to clear bag"))?;
        
        for element in elements {
            let result = apply_procedure_with_evaluator(eval, &args[0], &[element.clone()])?;
            if !result.is_falsy() {
                bag.adjoin(element).map_err(|_| runtime_error("Failed to add element to bag"))?;
            }
        }
        
        Ok(Value::Unspecified)
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Mutating remove for bags.
/// (bag-remove! pred bag)
fn primitive_bag_remove_mut(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-remove!", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[1] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        
        // Clear the bag and repopulate with non-removed elements
        bag.clear().map_err(|_| runtime_error("Failed to clear bag"))?;
        
        for element in elements {
            let result = apply_procedure_with_evaluator(eval, &args[0], &[element.clone()])?;
            if result.is_falsy() {
                bag.adjoin(element).map_err(|_| runtime_error("Failed to add element to bag"))?;
            }
        }
        
        Ok(Value::Unspecified)
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Mutating partition for bags.
/// (bag-partition! pred bag)
fn primitive_bag_partition_mut(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-partition!", args, 2, Some(2))?;
    
    if let Value::Bag(bag) = &args[1] {
        let elements = bag.to_vec().map_err(|_| runtime_error("Failed to get bag elements"))?;
        let mut false_elements = Vec::new();
        
        // Clear the bag and repopulate with true elements only
        bag.clear().map_err(|_| runtime_error("Failed to clear bag"))?;
        
        for element in elements {
            let result = apply_procedure_with_evaluator(eval, &args[0], &[element.clone()])?;
            if result.is_falsy() {
                false_elements.push(element);
            } else {
                bag.adjoin(element).map_err(|_| runtime_error("Failed to add element to bag"))?;
            }
        }
        
        // Return the false bag as the result
        Ok(Value::bag_from_iter(false_elements))
    } else {
        Err(type_error("Expected a bag"))
    }
}

/// Search for an element in the bag and call appropriate continuation.
/// (bag-search! bag element failure success)
fn primitive_bag_search_mut(eval: &mut crate::eval::evaluator::Evaluator, args: &[Value]) -> Result<Value> {
    arity_check("bag-search!", args, 4, Some(4))?;
    
    if let Value::Bag(bag) = &args[0] {
        let element = &args[1];
        let failure_cont = &args[2];
        let success_cont = &args[3];
        
        // Check if the element exists in the bag
        let contains = bag.contains(element).map_err(|_| runtime_error("Failed to check bag membership"))?;
        
        if contains {
            // Element found - call success continuation with update and remove procedures
            let update_proc = Value::Primitive(Arc::new(PrimitiveProcedure {
                name: "bag-search-update".to_string(),
                arity_min: 3,
                arity_max: Some(3),
                implementation: PrimitiveImpl::RustFn(|update_args| {
                    if update_args.len() != 3 {
                        return Err(arity_error("bag-search-update", 3, Some(3), update_args.len()));
                    }
                    if let Value::Bag(bag) = &update_args[0] {
                        let old_element = &update_args[1];
                        let new_element = &update_args[2];
                        
                        // Remove old element and add new element
                        bag.delete(old_element).map_err(|_| runtime_error("Failed to remove old element from bag"))?;
                        bag.adjoin(new_element.clone()).map_err(|_| runtime_error("Failed to add new element to bag"))?;
                        
                        Ok(Value::Unspecified)
                    } else {
                        Err(type_error("Expected a bag"))
                    }
                }),
                effects: vec![crate::effects::Effect::Pure],
            }));
            
            let remove_proc = Value::Primitive(Arc::new(PrimitiveProcedure {
                name: "bag-search-remove".to_string(),
                arity_min: 2,
                arity_max: Some(2),
                implementation: PrimitiveImpl::RustFn(|remove_args| {
                    if remove_args.len() != 2 {
                        return Err(arity_error("bag-search-remove", 2, Some(2), remove_args.len()));
                    }
                    if let Value::Bag(bag) = &remove_args[0] {
                        let element = &remove_args[1];
                        
                        // Remove the element
                        bag.delete(element).map_err(|_| runtime_error("Failed to remove element from bag"))?;
                        
                        Ok(Value::Unspecified)
                    } else {
                        Err(type_error("Expected a bag"))
                    }
                }),
                effects: vec![crate::effects::Effect::Pure],
            }));
            
            // Call success continuation with (element update-proc remove-proc)
            apply_procedure_with_evaluator(eval, success_cont, &[element.clone(), update_proc, remove_proc])
        } else {
            // Element not found - call failure continuation with insert procedure
            let insert_proc = Value::Primitive(Arc::new(PrimitiveProcedure {
                name: "bag-search-insert".to_string(),
                arity_min: 2,
                arity_max: Some(2),
                implementation: PrimitiveImpl::RustFn(|insert_args| {
                    if insert_args.len() != 2 {
                        return Err(arity_error("bag-search-insert", 2, Some(2), insert_args.len()));
                    }
                    if let Value::Bag(bag) = &insert_args[0] {
                        let element = &insert_args[1];
                        
                        // Add the element
                        bag.adjoin(element.clone()).map_err(|_| runtime_error("Failed to add element to bag"))?;
                        
                        Ok(Value::Unspecified)
                    } else {
                        Err(type_error("Expected a bag"))
                    }
                }),
                effects: vec![crate::effects::Effect::Pure],
            }));
            
            // Call failure continuation with (insert-proc)
            apply_procedure_with_evaluator(eval, failure_cont, &[insert_proc])
        }
    } else {
        Err(type_error("Expected a bag"))
    }
}