From cf385d4bf9cfcb4b8ee27cdac05cd4b00124b7bf Mon Sep 17 00:00:00 2001 From: bnewbold Date: Thu, 21 Apr 2016 03:27:45 -0400 Subject: mvoe implementations into subdirs --- julia/minimal.jl | 128 +++++++++++++++ julia/sexpr.jl | 119 ++++++++++++++ minimal.jl | 128 --------------- minimal.py | 158 ------------------ minimal.rs | 474 ------------------------------------------------------ python/minimal.py | 158 ++++++++++++++++++ python/sexpr.py | 40 +++++ rust/minimal.rs | 474 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ sexpr.jl | 119 -------------- sexpr.py | 40 ----- 10 files changed, 919 insertions(+), 919 deletions(-) create mode 100644 julia/minimal.jl create mode 100644 julia/sexpr.jl delete mode 100644 minimal.jl delete mode 100644 minimal.py delete mode 100644 minimal.rs create mode 100644 python/minimal.py create mode 100644 python/sexpr.py create mode 100644 rust/minimal.rs delete mode 100644 sexpr.jl delete mode 100644 sexpr.py diff --git a/julia/minimal.jl b/julia/minimal.jl new file mode 100644 index 0000000..303b87a --- /dev/null +++ b/julia/minimal.jl @@ -0,0 +1,128 @@ + +# A partial Scheme implementation in Julia + +# null -> nothing +# pair -> Pair type +# boolean (true/false) -> true/false +# number -> Number +# identifier/symbol -> symbol + +is_atom(x) = x == () || !(x == nothing || + typeof(x) <: Tuple || + typeof(x) <: Array || + typeof(x) <: Dict) +is_null(x) = x == () +is_zero(x) = x == 0 +is_eq(a, b) = a == b +is_number(x) = typeof(x) <: Number +is_boolean(x) = x == true || x == false +is_builtin(x) = x in (:lambda, :quote, :cond, :else, :cons, :car, :cdr, + :isnull, :iseq, :isatom, :iszero, :isnumber, + :+, :-, :*, :/, +, -, *, /) + +identity_action(x, ctx) = x +lookup_action(x, ctx) = ctx[x] +quote_action(x, ctx) = length(x) == 2 ? x[2] : throw(ErrorException()) + +function cond_action(x, ctx) + for line in x[2:end] + if line[1] == :else + return meaning(line[2], ctx) + elseif meaning(line[1], ctx) + return meaning(line[2], ctx) + else + # "unspecified" + return nothing + end + end +end + +function lambda_action(x, ctx) + return (:procedure, x[2], x[3:end], copy(ctx)) +end + +function apply_action(x, ctx) + if is_builtin(x[1]) + action = x[1] + args = [meaning(y, ctx) for y in x[2:end]] + if action == :cons + return tuple(args[1], args[2]) + elseif action == :car + return args[1][1] + elseif action == :cdr + return args[1][2] + elseif action == :isnull + return is_null(args[1]) + elseif action == :iseq + return is_eq(args[1], args[2]) + elseif action == :isatom + return is_atom(args[1]) + elseif action == :iszero + return is_zero(args[1]) + elseif action == :isnumber + return is_number(args[1]) + elseif action == :+ || action == + + return args[1] + args[2] + elseif action == :- || action == - + return args[1] - args[2] + elseif action == :* || action == * + return args[1] * args[2] + elseif action == :/ || action == / + return args[1] / args[2] + else + throw(ErrorException("Unexpected builtin: $(x[0])")) + end + elseif typeof(x[1]) <: Tuple + proc = meaning(x[1], ctx) + if proc[1] != :procedure + throw(ErrorException("Not applicable: $(str(proc))")) + end + variables = proc[2] + body = proc[3] + closure = copy(proc[4]) + args = [meaning(y, ctx) for y in x[2:end]] + for i in 1:length(variables) + closure[variables[i]] = args[i] + end + ret = nothing + for expr in body + ret = meaning(expr, closure) + end + return ret + else + throw(ErrorException("Unexpected... thing...: $(x[1])")) + end +end + +function meaning(x, ctx) + action = nothing + if is_atom(x) + if is_number(x) || is_boolean(x) || is_builtin(x) + return identity_action(x, ctx) + elseif typeof(x) <: Symbol + return lookup_action(x, ctx) + end + elseif typeof(x) <: Tuple + if x[1] == :quote + return quote_action(x, ctx) + elseif x[1] == :cond + return cond_action(x, ctx) + elseif x[1] == :lambda + return lambda_action(x, ctx) + elseif typeof(x[1]) <: Tuple + return apply_action(x, ctx) + else # some other identifier, either builtin or not + return apply_action(x, ctx) + end + end + throw(ErrorException("Unexpected expression: $x")) +end + +function value(ast) + return meaning(ast, Dict()) +end + +function test_minimal_scheme() + @assert 6 == value( ((:lambda, (:x, ), (+, 1, :x)), 5) ) + value( (:car, (:quote, (1, 2, 3, 4))) ) +end diff --git a/julia/sexpr.jl b/julia/sexpr.jl new file mode 100644 index 0000000..1a0ba3c --- /dev/null +++ b/julia/sexpr.jl @@ -0,0 +1,119 @@ + +""" +Takes a string 's' and will convert it to an Int64 or Float64 (if possible), or +return the string if not. +""" +function trynum(s::AbstractString) + # Test for: only number chars, and optionally a single decimal (period), + # but not just a single decimal on it's own ("." is not a number). + # Also allow a '-' in the first position. + # Could have just try/caught around Julia's float(), used below. + decimal_count = 0 + dash_count = 0 + for (i, c) in enumerate(s) + if c == '.' + decimal_count += 1 + elseif c == '-' && i == 1 && length(s) > 1 + dash_count += 1 + elseif !(c in "1234567890") + return s + end + end + if decimal_count > 1 || decimal_count + dash_count >= length(s) + return s + end + # Haven't written our own string-to-number function; use Julia's + if decimal_count > 0 + return float(s) + else + # Julia 0.4.3 complains with "use parse(Int,s) instead" of int(s) + return parse(Int, s) + end +end + +""" +Take a string 's' and splits it into elements (based on 'ws' white space +characters) and tuples (based on 'sep' separators). +""" +function tokenize(s::AbstractString; sep="()", ws=" \t\n") + L = AbstractString[] + food = 0 # num of yummy non-whitespace characters we have just eaten + for (i, c) in enumerate(s) + if c in sep || c in ws + if food > 0 + push!(L, s[i-food:i-1]) + end + if c in sep + push!(L, string(c)) + end + food = 0 + elseif i == length(s) + push!(L, s[i-food:end]) + # will break next iteration + else + food += 1 + end + end + # Convert Array of strings to an (immutable) Tuple + return tuple(L...) +end + +""" +Helper for `parse()`. + +Returns two values: the parsed expression, and the number of tokens consumed. + +Note that this function always returns a Tuple, even if only a single token is +passed: calling code must unwrap. Also, this will only parse out the first +complete expression, silently discarding trailing elements. + +Should probably use value exceptions instead of @assert on failure +""" +function _parse_tokens(tokens, depth=0) + L = [] + i = 1 + while i <= length(tokens) + el = tokens[i] + if el == "(" + (expr, skip) = _parse_tokens(tokens[(i+1):end], depth + 1) + push!(L, expr) + i += skip + elseif el == ")" + @assert depth > 0 "Missing open bracket..." + return (tuple(L...), i+1) + else + push!(L, el) + i += 1 + end + end + @assert depth == 0 "Missing close bracket..." + return (tuple(L...), i) +end + +""" +Takes a string and returns a tuple-based pseudo AST. + +Notes: all numbers are converted to Float64. No weird special characters are +parsed specially (eg, comma, pipe, hash, etc). +""" +function parse(s::AbstractString) + # First split into a flat list... + tokens = tokenize(s) + + # ... then convert any numbers ... + tokens = map(trynum, tokens) + + # ... then parse into nested tuples. + (expr, sz) = _parse_tokens(tokens) + + # Unwrap the first element and return that. + return expr[1] +end + +# parse("1") +# parse("((()) ())") +# parse("(a 134 ( 4 5 6) 2 ( ))") +# parse("(asdf 134 ( 4 5 6) 2 ( ))") +# parse("(1 2 3 -4567 123.25624 . -.)") +# parse("(1 2 3 -4567 123.25624 .1 1. -.1 -1. - . -.)") +# parse("(first (list 1 (+ 2 3) 9))") diff --git a/minimal.jl b/minimal.jl deleted file mode 100644 index 303b87a..0000000 --- a/minimal.jl +++ /dev/null @@ -1,128 +0,0 @@ - -# A partial Scheme implementation in Julia - -# null -> nothing -# pair -> Pair type -# boolean (true/false) -> true/false -# number -> Number -# identifier/symbol -> symbol - -is_atom(x) = x == () || !(x == nothing || - typeof(x) <: Tuple || - typeof(x) <: Array || - typeof(x) <: Dict) -is_null(x) = x == () -is_zero(x) = x == 0 -is_eq(a, b) = a == b -is_number(x) = typeof(x) <: Number -is_boolean(x) = x == true || x == false -is_builtin(x) = x in (:lambda, :quote, :cond, :else, :cons, :car, :cdr, - :isnull, :iseq, :isatom, :iszero, :isnumber, - :+, :-, :*, :/, +, -, *, /) - -identity_action(x, ctx) = x -lookup_action(x, ctx) = ctx[x] -quote_action(x, ctx) = length(x) == 2 ? x[2] : throw(ErrorException()) - -function cond_action(x, ctx) - for line in x[2:end] - if line[1] == :else - return meaning(line[2], ctx) - elseif meaning(line[1], ctx) - return meaning(line[2], ctx) - else - # "unspecified" - return nothing - end - end -end - -function lambda_action(x, ctx) - return (:procedure, x[2], x[3:end], copy(ctx)) -end - -function apply_action(x, ctx) - if is_builtin(x[1]) - action = x[1] - args = [meaning(y, ctx) for y in x[2:end]] - if action == :cons - return tuple(args[1], args[2]) - elseif action == :car - return args[1][1] - elseif action == :cdr - return args[1][2] - elseif action == :isnull - return is_null(args[1]) - elseif action == :iseq - return is_eq(args[1], args[2]) - elseif action == :isatom - return is_atom(args[1]) - elseif action == :iszero - return is_zero(args[1]) - elseif action == :isnumber - return is_number(args[1]) - elseif action == :+ || action == + - return args[1] + args[2] - elseif action == :- || action == - - return args[1] - args[2] - elseif action == :* || action == * - return args[1] * args[2] - elseif action == :/ || action == / - return args[1] / args[2] - else - throw(ErrorException("Unexpected builtin: $(x[0])")) - end - elseif typeof(x[1]) <: Tuple - proc = meaning(x[1], ctx) - if proc[1] != :procedure - throw(ErrorException("Not applicable: $(str(proc))")) - end - variables = proc[2] - body = proc[3] - closure = copy(proc[4]) - args = [meaning(y, ctx) for y in x[2:end]] - for i in 1:length(variables) - closure[variables[i]] = args[i] - end - ret = nothing - for expr in body - ret = meaning(expr, closure) - end - return ret - else - throw(ErrorException("Unexpected... thing...: $(x[1])")) - end -end - -function meaning(x, ctx) - action = nothing - if is_atom(x) - if is_number(x) || is_boolean(x) || is_builtin(x) - return identity_action(x, ctx) - elseif typeof(x) <: Symbol - return lookup_action(x, ctx) - end - elseif typeof(x) <: Tuple - if x[1] == :quote - return quote_action(x, ctx) - elseif x[1] == :cond - return cond_action(x, ctx) - elseif x[1] == :lambda - return lambda_action(x, ctx) - elseif typeof(x[1]) <: Tuple - return apply_action(x, ctx) - else # some other identifier, either builtin or not - return apply_action(x, ctx) - end - end - throw(ErrorException("Unexpected expression: $x")) -end - -function value(ast) - return meaning(ast, Dict()) -end - -function test_minimal_scheme() - @assert 6 == value( ((:lambda, (:x, ), (+, 1, :x)), 5) ) - value( (:car, (:quote, (1, 2, 3, 4))) ) -end diff --git a/minimal.py b/minimal.py deleted file mode 100644 index 8a282da..0000000 --- a/minimal.py +++ /dev/null @@ -1,158 +0,0 @@ -""" - null -> None - pair -> - boolean (true/false) -> True/False - number -> number - identifier/symbol -> string - - - const (atomic values) - lambda - quote (s-expr "one level down") - identifier (a symbol to be looked up in the context) - cond (conditional expression) -""" - -def is_atom(x): - return x is () or type(x) not in (None, tuple, list, dict) - -def is_boolean(x): - return x in (True, False) - -def is_number(x): - return type(x) in (int, float, long) - -def is_zero(x): - return x == 0 - -def is_null(x): - return x is () - -def is_eq(a, b): - return a == b - -def is_builtin(x): - return x in ('lambda', 'quote', 'cond', 'else', 'cons', 'car', 'cdr', - 'null?', 'eq?', 'atom?', 'zero?', 'number?', - '+', '-', '*', '/') - -# because python does not allow circular function definitions, and action -# functions call out to meaning(), which depends on some actions, we'll use an -# "action lookup table" to handle function references ourself. -# A more "pythonic" way to do this might be to use an object. -actions = dict() - -def meaning(x, ctx): - action = None - if is_atom(x): - if is_number(x) or is_boolean(x) or is_builtin(x): - action = actions['identity'] - else: # an identifier - action = actions['lookup'] - elif type(x) is tuple: - if x[0] is 'quote': - action = actions['quote'] - elif x[0] is 'cond': - action = actions['cond'] - elif x[0] is 'lambda': - action = actions['lambda'] - elif type(x[0]) is tuple: - action = actions['apply'] - else: # some other identifier, either builtin or not - action = actions['apply'] - else: - raise ValueError("Unexpected expression: %s" % x) - return action(x, ctx) - -def meaning_list(l, ctx): - return tuple([meaning(x, ctx) for x in l]) - -def identity_action(x, ctx): - return x -actions['identity'] = identity_action - -def lookup_action(x, ctx): - if not x in ctx: - ValueError("Unknown identifier: %s" % x) - else: - return ctx[x] -actions['lookup'] = lookup_action - -def quote_action(x, ctx): - if len(x) != 2: - ValueError("Improper quote usage: %s" % x) - return x[1] -actions['quote'] = quote_action - -def cond_action(x, ctx): - for line in x[1:]: - if line[0] == 'else': - return meaning(line[1], ctx) - elif meaning(line[0], ctx): - return meanint(line[1], ctx) - else: - # "unspecified" - return None -actions['cond'] = cond_action - -def lambda_action(x, ctx): - return ('procedure', x[1], x[2:], ctx.copy()) -actions['lambda'] = lambda_action - -def apply_action(x, ctx): - if is_builtin(x[0]): - args = meaning_list(x[1:], ctx) - if x[0] is 'cons': - return (args[0], ) + args[1] - elif x[0] is 'car': - return args[0][0] - elif x[0] is 'cdr': - return args[0][1] - elif x[0] is 'null?': - return is_null(args[0]) - elif x[0] is 'eq?': - return is_eq(args[0], args[1]) - elif x[0] is 'atom?': - return is_atom(args[0]) - elif x[0] is 'zero?': - return is_zero(args[0]) - elif x[0] is 'number?': - return is_number(args[0]) - elif x[0] is '+': - return args[0] + args[1] - elif x[0] is '-': - return args[0] - args[1] - elif x[0] is '*': - return args[0] * args[1] - elif x[0] is '/': - return args[0] / args[1] - else: - raise Exception("Unexpected builtin: %s" % x[0]) - elif type(x[0]) is tuple: - proc = meaning(x[0], ctx) - if proc[0] is not 'procedure': - raise Exception("Not applicable: %s" % str(proc)) - variables = proc[1] - body = proc[2] - closure = proc[3].copy() - args = meaning_list(x[1:], ctx) - for i in range(len(variables)): - closure[variables[i]] = args[i] - for expr in body: - ret = meaning(expr, closure) - return ret - else: - raise Exception("Unexpected... thing...: %s" % str(x[0])) -actions['apply'] = apply_action - -def value(x): - return meaning(x, dict()) - -def test(): - # ((lambda (x) (+ 1 x)) 5) ; 6 - v = value( (('lambda', ('x',), ('+', 1, 'x')), 5) ) - assert(v is 6) - return True - -if __name__=='__main__': - print(test()) diff --git a/minimal.rs b/minimal.rs deleted file mode 100644 index 15220cb..0000000 --- a/minimal.rs +++ /dev/null @@ -1,474 +0,0 @@ - -// A partial Scheme implementation in Rust -// Build with: rustc minimal.rs -o minimal-rust - -use std::io; -use std::io::Write; -use std::collections::HashMap; - -//////////// Types and Constants - -// There doesn't seem to be a symbol or quote type in Rust, so i'm going to use strings and vectors - -// XXX: how to avoid the '16' here? -const SCHEME_BUILTINS: [&'static str; 16] = ["lambda", "quote", "cond", "else", "cons", "car", "cdr", - "null?", "eq?", "atom?", "zero?", "number?", "+", "-", "*", "/"]; - -#[derive(Clone, PartialEq)] -enum SchemeExpr<'a> { - SchemeNull, - SchemeTrue, - SchemeFalse, - SchemeNum(f64), - SchemeBuiltin(&'a str), - SchemeSymbol(&'a str), - SchemeStr(&'a str), - SchemeProcedure( - Vec<&'a str>, - Vec>, - HashMap<&'a str, SchemeExpr<'a>>), - SchemeList(Vec>), - SchemeQuote(Vec>), -} - -//////////// Lexing, Parsing, and Printing - -fn is_scheme_whitespace(c: char) -> bool{ - " \r\n".find(c) != None -} -fn is_scheme_sep(c: char) -> bool { - "()".find(c) != None -} - -fn is_valid_symbol(s: &str) -> bool { - // TODO: this could be an 'any' or 'filter' call? - if s.len() == 0 { - return false; - } - for c in s.chars() { - if !c.is_alphabetic() && c != '-' { - return false; - } - } - return true; -} - -// TODO: need to expand prefix notation stuff like `(1 2 3) to (quote 1 2 3) here? -fn scheme_tokenize<'a>(raw_str: &'a str) -> Result, &'static str> { - let mut ret = Vec::<&str>::new(); - let mut food: usize = 0; - let mut quoted: bool = false; - for (i, c) in raw_str.chars().enumerate() { - if quoted { - if c == '"' && raw_str.chars().collect::>()[i-1] != '\\' { - ret.push(&raw_str[i-food-1..i+1]); - quoted = false; - food = 0; - } else if raw_str.len() == i+1 { - return Err("unmatched quote char"); - } else { - food += 1; - } - } else if c == '"' { - if food > 0 { - return Err("unexpected quote char"); - } - if raw_str.len() == i+1 { - return Err("unmatched (trailing) quote char"); - } - quoted = true; - } else if is_scheme_whitespace(c) || is_scheme_sep(c) { - if food > 0 { - ret.push(&raw_str[i-food..i]); - } - if is_scheme_sep(c) { - ret.push(&raw_str[i..i+1]); - } - food = 0; - } else if raw_str.len() == i+1 { - ret.push(&raw_str[i-food..]); - } else { - food += 1; - } - } - return Ok(ret); -} - -fn scheme_parse_token(token: &str) -> Result { - - // First match on easy stuff - match token { - "#t" => return Ok(SchemeExpr::SchemeTrue), - "#f" => return Ok(SchemeExpr::SchemeFalse), - ")" => return Ok(SchemeExpr::SchemeNull), - _ => () - } - - // Is it a builtin? - if SCHEME_BUILTINS.contains(&token) { - return Ok(SchemeExpr::SchemeBuiltin(token)); - } - - // Try to parse as a number - match token.parse::() { - Ok(x) => return Ok(SchemeExpr::SchemeNum(x)), - Err(_) => () - } - - // Is it a string? - if token.starts_with("\"") && token.ends_with("\"") { - return Ok(SchemeExpr::SchemeStr(token)); - } - - // If it's all alphas, must be a symbol - if is_valid_symbol(token) { - return Ok(SchemeExpr::SchemeSymbol(token)); - } - - return Err("unparsable token"); -} - -fn scheme_parse<'a>(tokens: &Vec<&'a str>, depth: u32) -> Result<(SchemeExpr<'a>, usize), &'static str> { - let mut ret = Vec::::new(); - let mut i: usize = 0; - if tokens.len() == 0 { - return Ok((SchemeExpr::SchemeNull, 0)); - } else if tokens.len() == 1 { - let expr = try!(scheme_parse_token(tokens[0])); - return Ok((expr, 1)); - } - while i < tokens.len() { - match tokens[i] { - "(" => { - let (expr, skip) = try!(scheme_parse(&tokens[i+1..].to_vec(), depth+1)); - ret.push(expr); - i += skip;}, - ")" => { - if depth == 0 { - return Err("missing an open bracket"); - } - return Ok((SchemeExpr::SchemeList(ret), i+1));}, - token => { - let expr = try!(scheme_parse_token(token)); - ret.push(expr); - } - } - i += 1; - } - if depth > 0 { - return Err("missing a close bracket"); - } - let rlen = ret.len(); - if depth == 0 && rlen == 1 { - return Ok((ret.pop().unwrap(), rlen)); - } else { - return Ok((SchemeExpr::SchemeList(ret), rlen)); - } -} - -fn scheme_repr(ast: &SchemeExpr) -> Result { - return match ast { - &SchemeExpr::SchemeTrue => Ok("#t".to_string()), - &SchemeExpr::SchemeFalse => Ok("#f".to_string()), - &SchemeExpr::SchemeNull => Ok("'()".to_string()), - &SchemeExpr::SchemeNum(num) => Ok(format!("{}", num).to_string()), - &SchemeExpr::SchemeBuiltin(b)=> Ok(b.to_string()), - &SchemeExpr::SchemeStr(s)=> Ok(s.to_string()), - &SchemeExpr::SchemeSymbol(s)=> Ok(s.to_string()), - &SchemeExpr::SchemeProcedure(ref binds, ref body, _) => { - let mut ret = "(lambda (".to_string(); - for bind in binds { - ret = ret + &bind + " "; - } - ret = ret + ") "; - for expr in body { - ret = ret + &try!(scheme_repr(&expr)); - } - ret = ret + ")"; - Ok(ret) - }, - &SchemeExpr::SchemeList(ref list) => { - let mut ret: String = - list.iter().fold("(".to_string(), - |acc, ref el| acc + " " + &scheme_repr(&el).unwrap()); - ret.push_str(" )"); - Ok(ret) - }, - &SchemeExpr::SchemeQuote(ref list) => { - let mut ret: String = - list.iter().fold("(quote ".to_string(), - |acc, ref el| acc + " " + &scheme_repr(&el).unwrap()); - ret.push_str(" )"); - Ok(ret) - }, - } -} - -//////////// Expression Evaluation - -#[allow(unused_variables)] -fn quote_action<'a>(list: &Vec>, ctx: HashMap<&str, SchemeExpr<'a>>) -> Result, &'static str> { - // XXX: why can't I '.map()' here? (try .iter().skip(1)...) - let mut body = Vec::::new(); - for el in list[1..].to_vec() { - body.push(el.clone()); - } - Ok(SchemeExpr::SchemeQuote(body)) -} - -fn cond_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { - for line in list.iter().skip(1) { - match line { - &SchemeExpr::SchemeList(ref inner) => { - if inner.len() != 2 { - return Err("cond must contain tuples of (predicate, value) (len !=2)"); - } - let pred = &inner[0]; - let val = &inner[1]; - let m = try!(scheme_meaning(&pred, ctx.clone())); - if m != SchemeExpr::SchemeFalse && m != SchemeExpr::SchemeNull { - return scheme_meaning(&val, ctx); - } }, - _ => { - return Err("cond must contain tuples of (predicate, value)"); }, - } - } - // "undefined", return empty tuple - Ok(SchemeExpr::SchemeNull) -} - -fn lambda_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { - if list.len() < 3 { - return Err("lambda must have a bind and at least one body expr"); - } - let mut binds = Vec::<&str>::new(); - let bind_list = match &list[1] { - &SchemeExpr::SchemeList(ref bl) => bl, - _ => { return Err("second arg to lambda must be a list of binds") }, - }; - for bind in bind_list { - match bind { - &SchemeExpr::SchemeSymbol(name) => - binds.push(name), - _ => return Err("lambda binds must all be non-builtin symbols") - } - } - let body = list.iter().skip(2).map(|x| x.clone()).collect(); - Ok(SchemeExpr::SchemeProcedure(binds, body, ctx.clone())) -} - -fn apply_math_op<'a>(action: &'a str, args: Vec) -> Result, &'static str> { - if args.len() < 2 { - return Err("math builtins take two or more args"); - } - let mut vals = Vec::::new(); - for arg in args { - match arg { - SchemeExpr::SchemeNum(x) => { vals.push(x) }, - _ => { return Err("math builtins take only numerical types") }, - } - } - - let ret: f64 = match action { - "+" => vals.iter().fold(0., |a, &b| a+b), - "*" => vals.iter().fold(1., |a, &b| a * b), - "-" => vals[1..].iter().fold(vals[0], |a, &b| a - b), - "/" => vals[1..].iter().fold(vals[0], |a, &b| a / b), - _ => { return Err("unimplemented math operation"); }, - }; - Ok(SchemeExpr::SchemeNum(ret)) -} - -fn apply_typecheck<'a>(action: &'a str, args: Vec) -> Result, &'static str> { - if args.len() != 1 { - return Err("typecheck builtins take a single argument"); - } - let arg: &SchemeExpr = &args[0]; - let ret: bool = match action { - "null?" => *arg == SchemeExpr::SchemeNull, - "zero?" => *arg == SchemeExpr::SchemeNum(0.0), - "number?" => match *arg { - SchemeExpr::SchemeNum(_) => true, - _ => false}, - "atom?" => match *arg { - SchemeExpr::SchemeNull | - SchemeExpr::SchemeTrue | - SchemeExpr::SchemeFalse | - SchemeExpr::SchemeNum(_) => true, - _ => false}, - _ => { return Err("unimplemented typecheck builtin"); }, - }; - if ret { - Ok(SchemeExpr::SchemeTrue) - } else { - Ok(SchemeExpr::SchemeFalse) - } -} - -fn apply_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { - if list.len() == 0 { - // TODO: is this correct? - return Ok(SchemeExpr::SchemeNull); - } - let action = &list[0]; - let args: Vec = list.iter().skip(1).map(|x| scheme_meaning(x, ctx.clone()).unwrap()).collect(); - match action { - &SchemeExpr::SchemeBuiltin(builtin) => { - return match builtin { - "+" | "-" | "*" | "/" => apply_math_op(builtin, args), - "null?" | "number?" | "zero?" | "atom?" => apply_typecheck(builtin, args), - "eq?" => { - if args.len() != 2 { - return Err("eq? takes only two arguments"); - } - if args[0] == args[1] { - return Ok(SchemeExpr::SchemeTrue) - } else { - return Ok(SchemeExpr::SchemeFalse) - } - }, - "car" => { - if args.len() != 1 { - return Err("car takes a single list argument"); - } - match &args[0] { - &SchemeExpr::SchemeList(ref list) => { - Ok(list[0].clone()) - }, - _ => Err("cdr takes only lists") - } - }, - "cdr" => { - if args.len() != 1 { - return Err("cdr takes a single list argument"); - } - match &args[0] { - &SchemeExpr::SchemeList(ref list) => { - Ok(SchemeExpr::SchemeList(list[1..].to_vec())) - }, - _ => Err("car takes only lists") - } - }, - "cons" => { - if args.len() != 2 { - return Err("cons takes two arguments"); - } - match &args[1] { - &SchemeExpr::SchemeList(ref list) => { - let mut ret = vec![args[0].clone()]; - ret.extend_from_slice(list); - Ok(SchemeExpr::SchemeList(ret)) - }, - _ => Err("cdr takes only lists") - } - }, - _ => Err("unimplemented builtin"), - }; }, - &SchemeExpr::SchemeList(_) => { - let procedure: SchemeExpr = try!(scheme_meaning(&action, ctx.clone())); - match procedure { - SchemeExpr::SchemeProcedure(binds, body, proc_ctx) => { - // This block of code implements procedure (lambda) application - if body.len() != 1 { - return Err("prodedure must have single-expression body"); - } - if binds.len() != args.len() { - return Err("wrong number of args to procedure"); - } - let mut closure = proc_ctx.clone(); - for (name, arg) in binds.iter().zip(args) { - closure.insert(name, arg.clone()); - } - return scheme_meaning(&body[0], closure); - }, - _ => { return Err("non-procedure at head of expression"); }, - } }, - _ => { return Err("apply called with something non-applicable"); }, - } -} - -fn scheme_meaning<'a>(ast: &SchemeExpr<'a>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { - return match ast { - // "identity actions" - &SchemeExpr::SchemeTrue => Ok(ast.clone()), - &SchemeExpr::SchemeFalse => Ok(ast.clone()), - &SchemeExpr::SchemeNull => Ok(ast.clone()), - &SchemeExpr::SchemeStr(_) => Ok(ast.clone()), - &SchemeExpr::SchemeNum(_) => Ok(ast.clone()), - &SchemeExpr::SchemeBuiltin(_) => Ok(ast.clone()), - &SchemeExpr::SchemeProcedure(_, _, _) => Ok(ast.clone()), - &SchemeExpr::SchemeQuote(ref list) - => Ok(SchemeExpr::SchemeList(list.clone())), - &SchemeExpr::SchemeSymbol(sym) => match ctx.get(sym) { - // the "lookup action" - Some(val) => Ok(val.clone()), - None => Err("symbol not defined"), - }, - &SchemeExpr::SchemeList(ref list) => { - if list.len() == 0 { - return Ok(SchemeExpr::SchemeNull); - } - match list[0] { - SchemeExpr::SchemeBuiltin("quote") => - quote_action(&list, ctx), - SchemeExpr::SchemeBuiltin("cond") => - cond_action(&list, ctx), - SchemeExpr::SchemeBuiltin("lambda") => - lambda_action(&list, ctx), - SchemeExpr::SchemeBuiltin(_) => - apply_action(&list, ctx), - SchemeExpr::SchemeProcedure(_, _, _) => - apply_action(&list, ctx), - SchemeExpr::SchemeList(_) => - apply_action(&list, ctx), - _ => Ok(SchemeExpr::SchemeNull) - } - }, - } -} - -fn scheme_eval<'a>(ast: &'a SchemeExpr) -> Result, &'static str> { - let ctx = HashMap::<&str, SchemeExpr>::new(); - Ok(try!(scheme_meaning(ast, ctx))) -} - -//////////// Top-Level Program - -fn main() { - - let stdin = io::stdin(); - let mut stdout = io::stdout(); - - loop { - let raw_input = &mut String::new(); - stdout.write(b"\nminimal-rust> ").unwrap(); - stdout.flush().unwrap(); - stdin.read_line(raw_input).unwrap(); - let raw_input = raw_input; // UGH - if raw_input.len() == 0 { - stdout.write(b"\nCiao!\n").unwrap(); - return; - } - let tokens = match scheme_tokenize(&raw_input) { - Ok(tokens) => { - println!("Tokens: {}", tokens.join(", ")); // debug - tokens}, - Err(e) => { - println!("couldn't tokenize: {}", e); - continue}}; - let ast = match scheme_parse(&tokens, 0) { - Ok((ast, _)) => { - println!("AST: {}", scheme_repr(&ast).unwrap()); - ast}, - Err(e) => { - println!("couldn't parse: {}", e); - continue}}; - let resp = match scheme_eval(&ast) { - Ok(x) => x, - Err(e) => { - println!("couldn't eval: {}", e); - continue}}; - println!("{}", scheme_repr(&resp).unwrap()); - } -} - diff --git a/python/minimal.py b/python/minimal.py new file mode 100644 index 0000000..8a282da --- /dev/null +++ b/python/minimal.py @@ -0,0 +1,158 @@ +""" + null -> None + pair -> + boolean (true/false) -> True/False + number -> number + identifier/symbol -> string + + + const (atomic values) + lambda + quote (s-expr "one level down") + identifier (a symbol to be looked up in the context) + cond (conditional expression) +""" + +def is_atom(x): + return x is () or type(x) not in (None, tuple, list, dict) + +def is_boolean(x): + return x in (True, False) + +def is_number(x): + return type(x) in (int, float, long) + +def is_zero(x): + return x == 0 + +def is_null(x): + return x is () + +def is_eq(a, b): + return a == b + +def is_builtin(x): + return x in ('lambda', 'quote', 'cond', 'else', 'cons', 'car', 'cdr', + 'null?', 'eq?', 'atom?', 'zero?', 'number?', + '+', '-', '*', '/') + +# because python does not allow circular function definitions, and action +# functions call out to meaning(), which depends on some actions, we'll use an +# "action lookup table" to handle function references ourself. +# A more "pythonic" way to do this might be to use an object. +actions = dict() + +def meaning(x, ctx): + action = None + if is_atom(x): + if is_number(x) or is_boolean(x) or is_builtin(x): + action = actions['identity'] + else: # an identifier + action = actions['lookup'] + elif type(x) is tuple: + if x[0] is 'quote': + action = actions['quote'] + elif x[0] is 'cond': + action = actions['cond'] + elif x[0] is 'lambda': + action = actions['lambda'] + elif type(x[0]) is tuple: + action = actions['apply'] + else: # some other identifier, either builtin or not + action = actions['apply'] + else: + raise ValueError("Unexpected expression: %s" % x) + return action(x, ctx) + +def meaning_list(l, ctx): + return tuple([meaning(x, ctx) for x in l]) + +def identity_action(x, ctx): + return x +actions['identity'] = identity_action + +def lookup_action(x, ctx): + if not x in ctx: + ValueError("Unknown identifier: %s" % x) + else: + return ctx[x] +actions['lookup'] = lookup_action + +def quote_action(x, ctx): + if len(x) != 2: + ValueError("Improper quote usage: %s" % x) + return x[1] +actions['quote'] = quote_action + +def cond_action(x, ctx): + for line in x[1:]: + if line[0] == 'else': + return meaning(line[1], ctx) + elif meaning(line[0], ctx): + return meanint(line[1], ctx) + else: + # "unspecified" + return None +actions['cond'] = cond_action + +def lambda_action(x, ctx): + return ('procedure', x[1], x[2:], ctx.copy()) +actions['lambda'] = lambda_action + +def apply_action(x, ctx): + if is_builtin(x[0]): + args = meaning_list(x[1:], ctx) + if x[0] is 'cons': + return (args[0], ) + args[1] + elif x[0] is 'car': + return args[0][0] + elif x[0] is 'cdr': + return args[0][1] + elif x[0] is 'null?': + return is_null(args[0]) + elif x[0] is 'eq?': + return is_eq(args[0], args[1]) + elif x[0] is 'atom?': + return is_atom(args[0]) + elif x[0] is 'zero?': + return is_zero(args[0]) + elif x[0] is 'number?': + return is_number(args[0]) + elif x[0] is '+': + return args[0] + args[1] + elif x[0] is '-': + return args[0] - args[1] + elif x[0] is '*': + return args[0] * args[1] + elif x[0] is '/': + return args[0] / args[1] + else: + raise Exception("Unexpected builtin: %s" % x[0]) + elif type(x[0]) is tuple: + proc = meaning(x[0], ctx) + if proc[0] is not 'procedure': + raise Exception("Not applicable: %s" % str(proc)) + variables = proc[1] + body = proc[2] + closure = proc[3].copy() + args = meaning_list(x[1:], ctx) + for i in range(len(variables)): + closure[variables[i]] = args[i] + for expr in body: + ret = meaning(expr, closure) + return ret + else: + raise Exception("Unexpected... thing...: %s" % str(x[0])) +actions['apply'] = apply_action + +def value(x): + return meaning(x, dict()) + +def test(): + # ((lambda (x) (+ 1 x)) 5) ; 6 + v = value( (('lambda', ('x',), ('+', 1, 'x')), 5) ) + assert(v is 6) + return True + +if __name__=='__main__': + print(test()) diff --git a/python/sexpr.py b/python/sexpr.py new file mode 100644 index 0000000..61bb09c --- /dev/null +++ b/python/sexpr.py @@ -0,0 +1,40 @@ + +def tokenize(s, sep="()", ws=" \t\n"): + L = [] + food = 0 + for i, c in enumerate(s): + if c in sep or c in ws: + if food > 0: + L.append(s[i-food:i]) + if c in sep: + L.append(c) + food = 0 + elif i+1 == len(s): + L.append(s[i-food:]) + else: + food += 1 + return L + +def _parse_tokens(tokens, depth=0): + L = [] + i = 0 + while i < len(tokens): + el = tokens[i] + if el == '(': + expr, skip = _parse_tokens(tokens[i+1:], depth+1) + L.append(expr) + i += skip + 1 + elif el == ')': + assert depth > 0, "Missing open bracket..." + return L, i+1 + else: + L.append(el) + i += 1 + assert depth == 0, "Missing close bracket..." + return L, i + +def parse(s): + tokens = tokenize(s) + expr, size = _parse_tokens(tokens) + return expr[0] + diff --git a/rust/minimal.rs b/rust/minimal.rs new file mode 100644 index 0000000..15220cb --- /dev/null +++ b/rust/minimal.rs @@ -0,0 +1,474 @@ + +// A partial Scheme implementation in Rust +// Build with: rustc minimal.rs -o minimal-rust + +use std::io; +use std::io::Write; +use std::collections::HashMap; + +//////////// Types and Constants + +// There doesn't seem to be a symbol or quote type in Rust, so i'm going to use strings and vectors + +// XXX: how to avoid the '16' here? +const SCHEME_BUILTINS: [&'static str; 16] = ["lambda", "quote", "cond", "else", "cons", "car", "cdr", + "null?", "eq?", "atom?", "zero?", "number?", "+", "-", "*", "/"]; + +#[derive(Clone, PartialEq)] +enum SchemeExpr<'a> { + SchemeNull, + SchemeTrue, + SchemeFalse, + SchemeNum(f64), + SchemeBuiltin(&'a str), + SchemeSymbol(&'a str), + SchemeStr(&'a str), + SchemeProcedure( + Vec<&'a str>, + Vec>, + HashMap<&'a str, SchemeExpr<'a>>), + SchemeList(Vec>), + SchemeQuote(Vec>), +} + +//////////// Lexing, Parsing, and Printing + +fn is_scheme_whitespace(c: char) -> bool{ + " \r\n".find(c) != None +} +fn is_scheme_sep(c: char) -> bool { + "()".find(c) != None +} + +fn is_valid_symbol(s: &str) -> bool { + // TODO: this could be an 'any' or 'filter' call? + if s.len() == 0 { + return false; + } + for c in s.chars() { + if !c.is_alphabetic() && c != '-' { + return false; + } + } + return true; +} + +// TODO: need to expand prefix notation stuff like `(1 2 3) to (quote 1 2 3) here? +fn scheme_tokenize<'a>(raw_str: &'a str) -> Result, &'static str> { + let mut ret = Vec::<&str>::new(); + let mut food: usize = 0; + let mut quoted: bool = false; + for (i, c) in raw_str.chars().enumerate() { + if quoted { + if c == '"' && raw_str.chars().collect::>()[i-1] != '\\' { + ret.push(&raw_str[i-food-1..i+1]); + quoted = false; + food = 0; + } else if raw_str.len() == i+1 { + return Err("unmatched quote char"); + } else { + food += 1; + } + } else if c == '"' { + if food > 0 { + return Err("unexpected quote char"); + } + if raw_str.len() == i+1 { + return Err("unmatched (trailing) quote char"); + } + quoted = true; + } else if is_scheme_whitespace(c) || is_scheme_sep(c) { + if food > 0 { + ret.push(&raw_str[i-food..i]); + } + if is_scheme_sep(c) { + ret.push(&raw_str[i..i+1]); + } + food = 0; + } else if raw_str.len() == i+1 { + ret.push(&raw_str[i-food..]); + } else { + food += 1; + } + } + return Ok(ret); +} + +fn scheme_parse_token(token: &str) -> Result { + + // First match on easy stuff + match token { + "#t" => return Ok(SchemeExpr::SchemeTrue), + "#f" => return Ok(SchemeExpr::SchemeFalse), + ")" => return Ok(SchemeExpr::SchemeNull), + _ => () + } + + // Is it a builtin? + if SCHEME_BUILTINS.contains(&token) { + return Ok(SchemeExpr::SchemeBuiltin(token)); + } + + // Try to parse as a number + match token.parse::() { + Ok(x) => return Ok(SchemeExpr::SchemeNum(x)), + Err(_) => () + } + + // Is it a string? + if token.starts_with("\"") && token.ends_with("\"") { + return Ok(SchemeExpr::SchemeStr(token)); + } + + // If it's all alphas, must be a symbol + if is_valid_symbol(token) { + return Ok(SchemeExpr::SchemeSymbol(token)); + } + + return Err("unparsable token"); +} + +fn scheme_parse<'a>(tokens: &Vec<&'a str>, depth: u32) -> Result<(SchemeExpr<'a>, usize), &'static str> { + let mut ret = Vec::::new(); + let mut i: usize = 0; + if tokens.len() == 0 { + return Ok((SchemeExpr::SchemeNull, 0)); + } else if tokens.len() == 1 { + let expr = try!(scheme_parse_token(tokens[0])); + return Ok((expr, 1)); + } + while i < tokens.len() { + match tokens[i] { + "(" => { + let (expr, skip) = try!(scheme_parse(&tokens[i+1..].to_vec(), depth+1)); + ret.push(expr); + i += skip;}, + ")" => { + if depth == 0 { + return Err("missing an open bracket"); + } + return Ok((SchemeExpr::SchemeList(ret), i+1));}, + token => { + let expr = try!(scheme_parse_token(token)); + ret.push(expr); + } + } + i += 1; + } + if depth > 0 { + return Err("missing a close bracket"); + } + let rlen = ret.len(); + if depth == 0 && rlen == 1 { + return Ok((ret.pop().unwrap(), rlen)); + } else { + return Ok((SchemeExpr::SchemeList(ret), rlen)); + } +} + +fn scheme_repr(ast: &SchemeExpr) -> Result { + return match ast { + &SchemeExpr::SchemeTrue => Ok("#t".to_string()), + &SchemeExpr::SchemeFalse => Ok("#f".to_string()), + &SchemeExpr::SchemeNull => Ok("'()".to_string()), + &SchemeExpr::SchemeNum(num) => Ok(format!("{}", num).to_string()), + &SchemeExpr::SchemeBuiltin(b)=> Ok(b.to_string()), + &SchemeExpr::SchemeStr(s)=> Ok(s.to_string()), + &SchemeExpr::SchemeSymbol(s)=> Ok(s.to_string()), + &SchemeExpr::SchemeProcedure(ref binds, ref body, _) => { + let mut ret = "(lambda (".to_string(); + for bind in binds { + ret = ret + &bind + " "; + } + ret = ret + ") "; + for expr in body { + ret = ret + &try!(scheme_repr(&expr)); + } + ret = ret + ")"; + Ok(ret) + }, + &SchemeExpr::SchemeList(ref list) => { + let mut ret: String = + list.iter().fold("(".to_string(), + |acc, ref el| acc + " " + &scheme_repr(&el).unwrap()); + ret.push_str(" )"); + Ok(ret) + }, + &SchemeExpr::SchemeQuote(ref list) => { + let mut ret: String = + list.iter().fold("(quote ".to_string(), + |acc, ref el| acc + " " + &scheme_repr(&el).unwrap()); + ret.push_str(" )"); + Ok(ret) + }, + } +} + +//////////// Expression Evaluation + +#[allow(unused_variables)] +fn quote_action<'a>(list: &Vec>, ctx: HashMap<&str, SchemeExpr<'a>>) -> Result, &'static str> { + // XXX: why can't I '.map()' here? (try .iter().skip(1)...) + let mut body = Vec::::new(); + for el in list[1..].to_vec() { + body.push(el.clone()); + } + Ok(SchemeExpr::SchemeQuote(body)) +} + +fn cond_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { + for line in list.iter().skip(1) { + match line { + &SchemeExpr::SchemeList(ref inner) => { + if inner.len() != 2 { + return Err("cond must contain tuples of (predicate, value) (len !=2)"); + } + let pred = &inner[0]; + let val = &inner[1]; + let m = try!(scheme_meaning(&pred, ctx.clone())); + if m != SchemeExpr::SchemeFalse && m != SchemeExpr::SchemeNull { + return scheme_meaning(&val, ctx); + } }, + _ => { + return Err("cond must contain tuples of (predicate, value)"); }, + } + } + // "undefined", return empty tuple + Ok(SchemeExpr::SchemeNull) +} + +fn lambda_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { + if list.len() < 3 { + return Err("lambda must have a bind and at least one body expr"); + } + let mut binds = Vec::<&str>::new(); + let bind_list = match &list[1] { + &SchemeExpr::SchemeList(ref bl) => bl, + _ => { return Err("second arg to lambda must be a list of binds") }, + }; + for bind in bind_list { + match bind { + &SchemeExpr::SchemeSymbol(name) => + binds.push(name), + _ => return Err("lambda binds must all be non-builtin symbols") + } + } + let body = list.iter().skip(2).map(|x| x.clone()).collect(); + Ok(SchemeExpr::SchemeProcedure(binds, body, ctx.clone())) +} + +fn apply_math_op<'a>(action: &'a str, args: Vec) -> Result, &'static str> { + if args.len() < 2 { + return Err("math builtins take two or more args"); + } + let mut vals = Vec::::new(); + for arg in args { + match arg { + SchemeExpr::SchemeNum(x) => { vals.push(x) }, + _ => { return Err("math builtins take only numerical types") }, + } + } + + let ret: f64 = match action { + "+" => vals.iter().fold(0., |a, &b| a+b), + "*" => vals.iter().fold(1., |a, &b| a * b), + "-" => vals[1..].iter().fold(vals[0], |a, &b| a - b), + "/" => vals[1..].iter().fold(vals[0], |a, &b| a / b), + _ => { return Err("unimplemented math operation"); }, + }; + Ok(SchemeExpr::SchemeNum(ret)) +} + +fn apply_typecheck<'a>(action: &'a str, args: Vec) -> Result, &'static str> { + if args.len() != 1 { + return Err("typecheck builtins take a single argument"); + } + let arg: &SchemeExpr = &args[0]; + let ret: bool = match action { + "null?" => *arg == SchemeExpr::SchemeNull, + "zero?" => *arg == SchemeExpr::SchemeNum(0.0), + "number?" => match *arg { + SchemeExpr::SchemeNum(_) => true, + _ => false}, + "atom?" => match *arg { + SchemeExpr::SchemeNull | + SchemeExpr::SchemeTrue | + SchemeExpr::SchemeFalse | + SchemeExpr::SchemeNum(_) => true, + _ => false}, + _ => { return Err("unimplemented typecheck builtin"); }, + }; + if ret { + Ok(SchemeExpr::SchemeTrue) + } else { + Ok(SchemeExpr::SchemeFalse) + } +} + +fn apply_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { + if list.len() == 0 { + // TODO: is this correct? + return Ok(SchemeExpr::SchemeNull); + } + let action = &list[0]; + let args: Vec = list.iter().skip(1).map(|x| scheme_meaning(x, ctx.clone()).unwrap()).collect(); + match action { + &SchemeExpr::SchemeBuiltin(builtin) => { + return match builtin { + "+" | "-" | "*" | "/" => apply_math_op(builtin, args), + "null?" | "number?" | "zero?" | "atom?" => apply_typecheck(builtin, args), + "eq?" => { + if args.len() != 2 { + return Err("eq? takes only two arguments"); + } + if args[0] == args[1] { + return Ok(SchemeExpr::SchemeTrue) + } else { + return Ok(SchemeExpr::SchemeFalse) + } + }, + "car" => { + if args.len() != 1 { + return Err("car takes a single list argument"); + } + match &args[0] { + &SchemeExpr::SchemeList(ref list) => { + Ok(list[0].clone()) + }, + _ => Err("cdr takes only lists") + } + }, + "cdr" => { + if args.len() != 1 { + return Err("cdr takes a single list argument"); + } + match &args[0] { + &SchemeExpr::SchemeList(ref list) => { + Ok(SchemeExpr::SchemeList(list[1..].to_vec())) + }, + _ => Err("car takes only lists") + } + }, + "cons" => { + if args.len() != 2 { + return Err("cons takes two arguments"); + } + match &args[1] { + &SchemeExpr::SchemeList(ref list) => { + let mut ret = vec![args[0].clone()]; + ret.extend_from_slice(list); + Ok(SchemeExpr::SchemeList(ret)) + }, + _ => Err("cdr takes only lists") + } + }, + _ => Err("unimplemented builtin"), + }; }, + &SchemeExpr::SchemeList(_) => { + let procedure: SchemeExpr = try!(scheme_meaning(&action, ctx.clone())); + match procedure { + SchemeExpr::SchemeProcedure(binds, body, proc_ctx) => { + // This block of code implements procedure (lambda) application + if body.len() != 1 { + return Err("prodedure must have single-expression body"); + } + if binds.len() != args.len() { + return Err("wrong number of args to procedure"); + } + let mut closure = proc_ctx.clone(); + for (name, arg) in binds.iter().zip(args) { + closure.insert(name, arg.clone()); + } + return scheme_meaning(&body[0], closure); + }, + _ => { return Err("non-procedure at head of expression"); }, + } }, + _ => { return Err("apply called with something non-applicable"); }, + } +} + +fn scheme_meaning<'a>(ast: &SchemeExpr<'a>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { + return match ast { + // "identity actions" + &SchemeExpr::SchemeTrue => Ok(ast.clone()), + &SchemeExpr::SchemeFalse => Ok(ast.clone()), + &SchemeExpr::SchemeNull => Ok(ast.clone()), + &SchemeExpr::SchemeStr(_) => Ok(ast.clone()), + &SchemeExpr::SchemeNum(_) => Ok(ast.clone()), + &SchemeExpr::SchemeBuiltin(_) => Ok(ast.clone()), + &SchemeExpr::SchemeProcedure(_, _, _) => Ok(ast.clone()), + &SchemeExpr::SchemeQuote(ref list) + => Ok(SchemeExpr::SchemeList(list.clone())), + &SchemeExpr::SchemeSymbol(sym) => match ctx.get(sym) { + // the "lookup action" + Some(val) => Ok(val.clone()), + None => Err("symbol not defined"), + }, + &SchemeExpr::SchemeList(ref list) => { + if list.len() == 0 { + return Ok(SchemeExpr::SchemeNull); + } + match list[0] { + SchemeExpr::SchemeBuiltin("quote") => + quote_action(&list, ctx), + SchemeExpr::SchemeBuiltin("cond") => + cond_action(&list, ctx), + SchemeExpr::SchemeBuiltin("lambda") => + lambda_action(&list, ctx), + SchemeExpr::SchemeBuiltin(_) => + apply_action(&list, ctx), + SchemeExpr::SchemeProcedure(_, _, _) => + apply_action(&list, ctx), + SchemeExpr::SchemeList(_) => + apply_action(&list, ctx), + _ => Ok(SchemeExpr::SchemeNull) + } + }, + } +} + +fn scheme_eval<'a>(ast: &'a SchemeExpr) -> Result, &'static str> { + let ctx = HashMap::<&str, SchemeExpr>::new(); + Ok(try!(scheme_meaning(ast, ctx))) +} + +//////////// Top-Level Program + +fn main() { + + let stdin = io::stdin(); + let mut stdout = io::stdout(); + + loop { + let raw_input = &mut String::new(); + stdout.write(b"\nminimal-rust> ").unwrap(); + stdout.flush().unwrap(); + stdin.read_line(raw_input).unwrap(); + let raw_input = raw_input; // UGH + if raw_input.len() == 0 { + stdout.write(b"\nCiao!\n").unwrap(); + return; + } + let tokens = match scheme_tokenize(&raw_input) { + Ok(tokens) => { + println!("Tokens: {}", tokens.join(", ")); // debug + tokens}, + Err(e) => { + println!("couldn't tokenize: {}", e); + continue}}; + let ast = match scheme_parse(&tokens, 0) { + Ok((ast, _)) => { + println!("AST: {}", scheme_repr(&ast).unwrap()); + ast}, + Err(e) => { + println!("couldn't parse: {}", e); + continue}}; + let resp = match scheme_eval(&ast) { + Ok(x) => x, + Err(e) => { + println!("couldn't eval: {}", e); + continue}}; + println!("{}", scheme_repr(&resp).unwrap()); + } +} + diff --git a/sexpr.jl b/sexpr.jl deleted file mode 100644 index 1a0ba3c..0000000 --- a/sexpr.jl +++ /dev/null @@ -1,119 +0,0 @@ - -""" -Takes a string 's' and will convert it to an Int64 or Float64 (if possible), or -return the string if not. -""" -function trynum(s::AbstractString) - # Test for: only number chars, and optionally a single decimal (period), - # but not just a single decimal on it's own ("." is not a number). - # Also allow a '-' in the first position. - # Could have just try/caught around Julia's float(), used below. - decimal_count = 0 - dash_count = 0 - for (i, c) in enumerate(s) - if c == '.' - decimal_count += 1 - elseif c == '-' && i == 1 && length(s) > 1 - dash_count += 1 - elseif !(c in "1234567890") - return s - end - end - if decimal_count > 1 || decimal_count + dash_count >= length(s) - return s - end - # Haven't written our own string-to-number function; use Julia's - if decimal_count > 0 - return float(s) - else - # Julia 0.4.3 complains with "use parse(Int,s) instead" of int(s) - return parse(Int, s) - end -end - -""" -Take a string 's' and splits it into elements (based on 'ws' white space -characters) and tuples (based on 'sep' separators). -""" -function tokenize(s::AbstractString; sep="()", ws=" \t\n") - L = AbstractString[] - food = 0 # num of yummy non-whitespace characters we have just eaten - for (i, c) in enumerate(s) - if c in sep || c in ws - if food > 0 - push!(L, s[i-food:i-1]) - end - if c in sep - push!(L, string(c)) - end - food = 0 - elseif i == length(s) - push!(L, s[i-food:end]) - # will break next iteration - else - food += 1 - end - end - # Convert Array of strings to an (immutable) Tuple - return tuple(L...) -end - -""" -Helper for `parse()`. - -Returns two values: the parsed expression, and the number of tokens consumed. - -Note that this function always returns a Tuple, even if only a single token is -passed: calling code must unwrap. Also, this will only parse out the first -complete expression, silently discarding trailing elements. - -Should probably use value exceptions instead of @assert on failure -""" -function _parse_tokens(tokens, depth=0) - L = [] - i = 1 - while i <= length(tokens) - el = tokens[i] - if el == "(" - (expr, skip) = _parse_tokens(tokens[(i+1):end], depth + 1) - push!(L, expr) - i += skip - elseif el == ")" - @assert depth > 0 "Missing open bracket..." - return (tuple(L...), i+1) - else - push!(L, el) - i += 1 - end - end - @assert depth == 0 "Missing close bracket..." - return (tuple(L...), i) -end - -""" -Takes a string and returns a tuple-based pseudo AST. - -Notes: all numbers are converted to Float64. No weird special characters are -parsed specially (eg, comma, pipe, hash, etc). -""" -function parse(s::AbstractString) - # First split into a flat list... - tokens = tokenize(s) - - # ... then convert any numbers ... - tokens = map(trynum, tokens) - - # ... then parse into nested tuples. - (expr, sz) = _parse_tokens(tokens) - - # Unwrap the first element and return that. - return expr[1] -end - -# parse("1") -# parse("((()) ())") -# parse("(a 134 ( 4 5 6) 2 ( ))") -# parse("(asdf 134 ( 4 5 6) 2 ( ))") -# parse("(1 2 3 -4567 123.25624 . -.)") -# parse("(1 2 3 -4567 123.25624 .1 1. -.1 -1. - . -.)") -# parse("(first (list 1 (+ 2 3) 9))") diff --git a/sexpr.py b/sexpr.py deleted file mode 100644 index 61bb09c..0000000 --- a/sexpr.py +++ /dev/null @@ -1,40 +0,0 @@ - -def tokenize(s, sep="()", ws=" \t\n"): - L = [] - food = 0 - for i, c in enumerate(s): - if c in sep or c in ws: - if food > 0: - L.append(s[i-food:i]) - if c in sep: - L.append(c) - food = 0 - elif i+1 == len(s): - L.append(s[i-food:]) - else: - food += 1 - return L - -def _parse_tokens(tokens, depth=0): - L = [] - i = 0 - while i < len(tokens): - el = tokens[i] - if el == '(': - expr, skip = _parse_tokens(tokens[i+1:], depth+1) - L.append(expr) - i += skip + 1 - elif el == ')': - assert depth > 0, "Missing open bracket..." - return L, i+1 - else: - L.append(el) - i += 1 - assert depth == 0, "Missing close bracket..." - return L, i - -def parse(s): - tokens = tokenize(s) - expr, size = _parse_tokens(tokens) - return expr[0] - -- cgit v1.2.3