diff options
Diffstat (limited to 'julia')
| -rw-r--r-- | julia/minimal.jl | 128 | ||||
| -rw-r--r-- | julia/sexpr.jl | 119 |
2 files changed, 247 insertions, 0 deletions
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))") |