mvoe implementations into subdirs

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))")