Consolidate parse() and typecheck()

26 files changed, 867 insertions, 1033 deletions

diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index a8ece9f6cd..9023be3c59 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -392,6 +392,7 @@ set(MBGL_CORE_FILES
     # style/expression
     include/mbgl/style/expression/array_assertion.hpp
     include/mbgl/style/expression/case.hpp
+    include/mbgl/style/expression/check_subtype.hpp
     include/mbgl/style/expression/coalesce.hpp
     include/mbgl/style/expression/compound_expression.hpp
     include/mbgl/style/expression/curve.hpp
@@ -403,9 +404,9 @@ set(MBGL_CORE_FILES
     include/mbgl/style/expression/parsing_context.hpp
     include/mbgl/style/expression/type.hpp
     include/mbgl/style/expression/value.hpp
+    src/mbgl/style/expression/check_subtype.cpp
     src/mbgl/style/expression/compound_expression.cpp
     src/mbgl/style/expression/match.cpp
-    src/mbgl/style/expression/type.cpp
     src/mbgl/style/expression/value.cpp
 
     # style/function
diff --git a/include/mbgl/style/expression/array_assertion.hpp b/include/mbgl/style/expression/array_assertion.hpp
index ce78b82453..238fe2223d 100644
--- a/include/mbgl/style/expression/array_assertion.hpp
+++ b/include/mbgl/style/expression/array_assertion.hpp
@@ -4,6 +4,7 @@
 #include <memory>
 #include <mbgl/util/optional.hpp>
 #include <mbgl/util/variant.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
 #include <mbgl/style/expression/expression.hpp>
 #include <mbgl/style/expression/type.hpp>
 #include <mbgl/style/expression/parsing_context.hpp>
@@ -15,10 +16,10 @@ namespace style {
 namespace expression {
 
 
-class TypedArrayAssertion : public TypedExpression  {
+class ArrayAssertion : public Expression  {
 public:
-    TypedArrayAssertion(type::Array type, std::unique_ptr<TypedExpression> input_) :
-        TypedExpression(type),
+    ArrayAssertion(type::Array type, std::unique_ptr<Expression> input_) :
+        Expression(type),
         input(std::move(input_))
     {}
     
@@ -35,40 +36,19 @@ public:
         if (!result) {
             return result.error();
         }
-        auto error = matchType(getType(), typeOf(*result));
-        if (error) {
-            return EvaluationError { *error };
+        type::Type expected = getType();
+        type::Type actual = typeOf(*result);
+        if (checkSubtype(expected, actual)) {
+            return EvaluationError {
+                "Expected value to be of type " + toString(expected) +
+                ", but found " + toString(actual) + " instead."
+            };
         }
         return *result;
     }
-private:
-    std::unique_ptr<TypedExpression> input;
-};
-
-class UntypedArrayAssertion : public UntypedExpression {
-public:
-    UntypedArrayAssertion(std::string key_,
-                          type::Type itemType_,
-                          optional<std::size_t> length_,
-                          std::unique_ptr<UntypedExpression> input_
-    ) : UntypedExpression(key_),
-        itemType(itemType_),
-        length(length_),
-        input(std::move(input_))
-    {}
-
-    TypecheckResult typecheck(std::vector<CompileError>& errors) const override {
-        auto checkedInput = input->typecheck(errors);
-        if (!checkedInput) {
-            return TypecheckResult();
-        }
-        return TypecheckResult(std::make_unique<TypedArrayAssertion>(
-            type::Array(itemType, length), std::move(*checkedInput))
-        );
-    }
     
     template <class V>
-    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+    static ParseResult parse(const V& value, ParsingContext ctx) {
         using namespace mbgl::style::conversion;
         
         static std::unordered_map<std::string, type::Type> itemTypes {
@@ -79,56 +59,52 @@ public:
     
         auto length = arrayLength(value);
         if (length < 2 || length > 4) {
-            return CompileError {
-                "Expected 1, 2, or 3 arguments, but found " + std::to_string(length - 1) + " instead.",
-                ctx.key()
-            };
+            ctx.error("Expected 1, 2, or 3 arguments, but found " + std::to_string(length - 1) + " instead.");
+            return ParseResult();
         }
         
-        auto input = parseExpression(arrayMember(value, length - 1), ParsingContext(ctx, {length - 1}, {"array"}));
-        if (input.template is<CompileError>()) {
-            return input;
-        }
-
         optional<type::Type> itemType;
         optional<std::size_t> N;
         if (length > 2) {
-            auto type = toString(arrayMember(value, 2));
-            if (!type || itemTypes.find(*type) == itemTypes.end()) {
-                return CompileError {
+            optional<std::string> itemTypeName = toString(arrayMember(value, 1));
+            auto it = itemTypeName ? itemTypes.find(*itemTypeName) : itemTypes.end();
+            if (it == itemTypes.end()) {
+                ctx.error(
                     "The item type argument of \"array\" must be one of string, number, boolean",
-                    ctx.key(2)
-                };
+                    1
+                );
+                return ParseResult();
             }
-            itemType = itemTypes.at(*type);
+            itemType = it->second;
         } else {
             itemType = {type::Value};
         }
         
         if (length > 3) {
-            auto n = toNumber(arrayMember(value, 3));
+            auto n = toNumber(arrayMember(value, 2));
             if (!n || *n != ceilf(*n)) {
-                return CompileError {
+                ctx.error(
                     "The length argument to \"array\" must be a positive integer literal.",
-                    ctx.key(3)
-                };
+                    2
+                );
+                return ParseResult();
             }
             N = optional<std::size_t>(*n);
         }
+        
+        auto input = parseExpression(arrayMember(value, length - 1), ParsingContext(ctx, length - 1, {type::Value}));
+        if (!input) {
+            return input;
+        }
+
     
-        return std::make_unique<UntypedArrayAssertion>(
-            ctx.key(),
-            *itemType,
-            N,
-            std::move(input.template get<std::unique_ptr<UntypedExpression>>())
-        );
+        return ParseResult(std::make_unique<ArrayAssertion>(
+            type::Array(*itemType, N),
+            std::move(*input)
+        ));
     }
-
 private:
-    
-    type::Type itemType;
-    optional<std::size_t> length;
-    std::unique_ptr<UntypedExpression> input;
+    std::unique_ptr<Expression> input;
 };
 
 } // namespace expression
diff --git a/include/mbgl/style/expression/case.hpp b/include/mbgl/style/expression/case.hpp
index 1e9f8757bf..eaed011e5d 100644
--- a/include/mbgl/style/expression/case.hpp
+++ b/include/mbgl/style/expression/case.hpp
@@ -1,5 +1,6 @@
 #pragma once
 
+#include <mbgl/style/expression/check_subtype.hpp>
 #include <mbgl/style/expression/expression.hpp>
 #include <mbgl/style/expression/parsing_context.hpp>
 #include <mbgl/style/conversion.hpp>
@@ -8,13 +9,12 @@ namespace mbgl {
 namespace style {
 namespace expression {
 
-class TypedCase : public TypedExpression {
+class Case : public Expression {
 public:
-    using Case = std::pair<std::unique_ptr<TypedExpression>, std::unique_ptr<TypedExpression>>;
+    using Branch = std::pair<std::unique_ptr<Expression>, std::unique_ptr<Expression>>;
     
-    TypedCase(std::vector<Case> cases_,
-              std::unique_ptr<TypedExpression> otherwise_
-    ) : TypedExpression(otherwise_->getType()),
+    Case(type::Type type, std::vector<Branch> cases_, std::unique_ptr<Expression> otherwise_
+    ) : Expression(type),
         cases(std::move(cases_)),
         otherwise(std::move(otherwise_))
     {}
@@ -52,121 +52,62 @@ public:
         
         return otherwise->evaluate(params);
     }
-
-private:
-    std::unique_ptr<TypedExpression> input;
-    std::vector<Case> cases;
-    std::unique_ptr<TypedExpression> otherwise;
-};
-
-class UntypedCase : public UntypedExpression {
-public:
-    using Cases = std::vector<std::pair<std::unique_ptr<UntypedExpression>, std::unique_ptr<UntypedExpression>>>;
-    
-    UntypedCase(std::string key,
-                 Cases cases_,
-                 std::unique_ptr<UntypedExpression> otherwise_)
-    :   UntypedExpression(key),
-        cases(std::move(cases_)),
-        otherwise(std::move(otherwise_))
-    {}
     
+        
     template <class V>
-    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+    static ParseResult parse(const V& value, ParsingContext ctx) {
         using namespace mbgl::style::conversion;
         
         assert(isArray(value));
         auto length = arrayLength(value);
         if (length < 4) {
-            return CompileError {
-                "Expected at least 3 arguments, but found only " + std::to_string(length - 1) + ".",
-                ctx.key()
-            };
+            ctx.error("Expected at least 3 arguments, but found only " + std::to_string(length - 1) + ".");
+            return ParseResult();
         }
         
         // Expect even-length array: ["case", 2 * (n pairs)..., otherwise]
         if (length % 2 != 0) {
-            return CompileError {
-                "Missing final output value for \"case\" expression.",
-                ctx.key()
-            };
-        }
-        
-        auto otherwise = parseExpression(arrayMember(value, length - 1), ParsingContext(ctx, {length - 1}, {"case"}));
-        if (otherwise.template is<CompileError>()) {
-            return otherwise;
+            ctx.error("Expected an odd number of arguments");
+            return ParseResult();
         }
         
-        Cases cases;
+        optional<type::Type> outputType = ctx.expected;
+
+        std::vector<Branch> branches;
         for (size_t i = 1; i + 1 < length; i += 2) {
-            auto condition = parseExpression(arrayMember(value, i), ParsingContext(ctx, {i}, {"case"}));
-            if (condition.template is<CompileError>()) {
-                return condition.template get<CompileError>();
+            auto test = parseExpression(arrayMember(value, i), ParsingContext(ctx, i, {type::Boolean}));
+            if (!test) {
+                return test;
             }
 
-            auto output = parseExpression(arrayMember(value, i + 1), ParsingContext(ctx, {i + 1}, {"case"}));
-            if (output.template is<CompileError>()) {
-                return output.template get<CompileError>();
+            auto output = parseExpression(arrayMember(value, i + 1), ParsingContext(ctx, i + 1, outputType));
+            if (!output) {
+                return output;
             }
-
-            cases.push_back(std::make_pair(
-                std::move(condition.template get<std::unique_ptr<UntypedExpression>>()),
-                std::move(output.template get<std::unique_ptr<UntypedExpression>>()))
-            );
-        }
-        
-        return std::make_unique<UntypedCase>(ctx.key(),
-                                             std::move(cases),
-                                             std::move(otherwise.template get<std::unique_ptr<UntypedExpression>>()));
-    }
-    
-    TypecheckResult typecheck(std::vector<CompileError>& errors) const override {
-        auto checkedOtherwise = otherwise->typecheck(errors);
-        if (!checkedOtherwise) {
-            return TypecheckResult();
-        }
-
-        optional<type::Type> outputType;
-        std::vector<TypedCase::Case> checkedCases;
-        for (const auto& pair : cases) {
-            auto condition = pair.first->typecheck(errors);
-            if (!condition) continue;
-            auto error = matchType(type::Boolean, (*condition)->getType());
-            if (error) {
-                errors.push_back({ *error, pair.first->getKey() });
-            }
-
-            auto output = pair.second->typecheck(errors);
-            if (!output) continue;
+            
             if (!outputType) {
                 outputType = (*output)->getType();
-            } else {
-                error = matchType(*outputType, (*output)->getType());
-                if (error) {
-                    errors.push_back({ *error, pair.second->getKey() });
-                }
-            }
-            
-            if (errors.size() == 0) {
-                checkedCases.emplace_back(std::move(*condition), std::move(*output));
             }
+
+            branches.push_back(std::make_pair(std::move(*test), std::move(*output)));
         }
         
-        auto error = matchType(*outputType, (*checkedOtherwise)->getType());
-        if (error) {
-            errors.push_back({ *error, otherwise->getKey() });
-        }
+        assert(outputType);
         
-        if (errors.size() > 0) {
-            return TypecheckResult();
+        auto otherwise = parseExpression(arrayMember(value, length - 1), ParsingContext(ctx, length - 1, outputType));
+        if (!otherwise) {
+            return otherwise;
         }
+        
+        return ParseResult(std::make_unique<Case>(*outputType,
+                                      std::move(branches),
+                                      std::move(*otherwise)));
+    }
 
-        return TypecheckResult(std::make_unique<TypedCase>(std::move(checkedCases), std::move(*checkedOtherwise)));
-    };
-    
 private:
-    Cases cases;
-    std::unique_ptr<UntypedExpression> otherwise;
+    std::unique_ptr<Expression> input;
+    std::vector<Branch> cases;
+    std::unique_ptr<Expression> otherwise;
 };
 
 } // namespace expression
diff --git a/include/mbgl/style/expression/check_subtype.hpp b/include/mbgl/style/expression/check_subtype.hpp
new file mode 100644
index 0000000000..02ebe3ed1c
--- /dev/null
+++ b/include/mbgl/style/expression/check_subtype.hpp
@@ -0,0 +1,16 @@
+#pragma once
+
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/type.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+namespace type {
+
+optional<std::string> checkSubtype(const Type& expected, const Type& t, optional<ParsingContext> context = {});
+
+} // namespace type
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/coalesce.hpp b/include/mbgl/style/expression/coalesce.hpp
index 5c7cc0c7c1..ab64f2e8bc 100644
--- a/include/mbgl/style/expression/coalesce.hpp
+++ b/include/mbgl/style/expression/coalesce.hpp
@@ -10,11 +10,11 @@ namespace mbgl {
 namespace style {
 namespace expression {
 
-class TypedCoalesce : public TypedExpression {
+class Coalesce : public Expression {
 public:
-    using Args = std::vector<std::unique_ptr<TypedExpression>>;
-    TypedCoalesce(const type::Type& type, Args args_) :
-        TypedExpression(type),
+    using Args = std::vector<std::unique_ptr<Expression>>;
+    Coalesce(const type::Type& type, Args args_) :
+        Expression(type),
         args(std::move(args_))
     {}
     
@@ -44,69 +44,33 @@ public:
         return true;
     }
     
-private:
-    Args args;
-};
-
-class UntypedCoalesce : public UntypedExpression {
-public:
-    using Args = std::vector<std::unique_ptr<UntypedExpression>>;
-    
-    UntypedCoalesce(const std::string& key, Args args_) :
-        UntypedExpression(key),
-        args(std::move(args_))
-    {}
-    
     template <typename V>
-    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+    static ParseResult parse(const V& value, ParsingContext ctx) {
         using namespace mbgl::style::conversion;
         assert(isArray(value));
         auto length = arrayLength(value);
         if (length < 2) {
-            return CompileError {
-                "Expected at least one argument to \"coalesce\".",
-                ctx.key()
-            };
+            ctx.error("Expected at least one argument.");
+            return ParseResult();
         }
         
         Args args;
+        optional<type::Type> outputType = ctx.expected;
         for (std::size_t i = 1; i < length; i++) {
-            auto parsed = parseExpression(arrayMember(value, i), ParsingContext(ctx, {i}, {"coalesce"}));
-            if (parsed.template is<CompileError>()) {
+            auto parsed = parseExpression(arrayMember(value, i), ParsingContext(ctx, i, outputType));
+            if (!parsed) {
                 return parsed;
             }
-            args.push_back(std::move(parsed.template get<std::unique_ptr<UntypedExpression>>()));
-        }
-        return std::make_unique<UntypedCoalesce>(ctx.key(), std::move(args));
-    }
-    
-    TypecheckResult typecheck(std::vector<CompileError>& errors) const override {
-        optional<type::Type> outputType;
-        TypedCoalesce::Args checkedArgs;
-        
-        for (const auto& arg : args) {
-            auto checked = arg->typecheck(errors);
-            if (!checked) {
-                continue;
-            }
             if (!outputType) {
-                outputType = (*checked)->getType();
-            } else {
-                const auto& error = matchType(*outputType, (*checked)->getType());
-                if (error) {
-                    errors.push_back({ *error, arg->getKey() });
-                    continue;
-                }
+                outputType = (*parsed)->getType();
             }
-            
-            checkedArgs.push_back(std::move(*checked));
+            args.push_back(std::move(*parsed));
         }
         
-        if (errors.size() > 0) return TypecheckResult();
-        
-        return TypecheckResult(std::make_unique<TypedCoalesce>(*outputType, std::move(checkedArgs)));
+        assert(outputType);
+        return ParseResult(std::make_unique<Coalesce>(*outputType, std::move(args)));
     }
-
+    
 private:
     Args args;
 };
diff --git a/include/mbgl/style/expression/compound_expression.hpp b/include/mbgl/style/expression/compound_expression.hpp
index cbdcb115e4..c09edaeea8 100644
--- a/include/mbgl/style/expression/compound_expression.hpp
+++ b/include/mbgl/style/expression/compound_expression.hpp
@@ -6,6 +6,7 @@
 #include <mbgl/util/optional.hpp>
 #include <mbgl/util/variant.hpp>
 #include <mbgl/util/color.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
 #include <mbgl/style/expression/expression.hpp>
 #include <mbgl/style/expression/type.hpp>
 #include <mbgl/style/expression/value.hpp>
@@ -35,7 +36,7 @@ struct SignatureBase {
         params(params_)
     {}
     virtual ~SignatureBase() {}
-    virtual std::unique_ptr<TypedExpression> makeTypedExpression(std::vector<std::unique_ptr<TypedExpression>>) const = 0;
+    virtual std::unique_ptr<Expression> makeExpression(std::vector<std::unique_ptr<Expression>>) const = 0;
     type::Type result;
     variant<std::vector<type::Type>, VarargsType> params;
 };
@@ -48,7 +49,7 @@ struct Signature;
 // where T1, T2, etc. are the types of successfully-evaluated subexpressions.
 template <class R, class... Params>
 struct Signature<R (const EvaluationParameters&, Params...)> : SignatureBase {
-    using Args = std::array<std::unique_ptr<TypedExpression>, sizeof...(Params)>;
+    using Args = std::array<std::unique_ptr<Expression>, sizeof...(Params)>;
     
     Signature(R (*evaluate_)(const EvaluationParameters&, Params...),
               bool isFeatureConstant_ = true,
@@ -62,7 +63,7 @@ struct Signature<R (const EvaluationParameters&, Params...)> : SignatureBase {
         zoomConstant(isZoomConstant_)
     {}
     
-    std::unique_ptr<TypedExpression> makeTypedExpression(std::vector<std::unique_ptr<TypedExpression>> args) const override;
+    std::unique_ptr<Expression> makeExpression(std::vector<std::unique_ptr<Expression>> args) const override;
     
     bool isFeatureConstant() const { return featureConstant; }
     bool isZoomConstant() const { return zoomConstant; }
@@ -93,7 +94,7 @@ private:
 // an alias for vector<T>).
 template <class R, typename T>
 struct Signature<R (const Varargs<T>&)> : SignatureBase {
-    using Args = std::vector<std::unique_ptr<TypedExpression>>;
+    using Args = std::vector<std::unique_ptr<Expression>>;
     
     Signature(R (*evaluate_)(const Varargs<T>&)) :
         SignatureBase(
@@ -103,7 +104,7 @@ struct Signature<R (const Varargs<T>&)> : SignatureBase {
         evaluate(evaluate_)
     {}
     
-    std::unique_ptr<TypedExpression> makeTypedExpression(std::vector<std::unique_ptr<TypedExpression>> args) const override;
+    std::unique_ptr<Expression> makeExpression(std::vector<std::unique_ptr<Expression>> args) const override;
     
     bool isFeatureConstant() const { return true; }
     bool isZoomConstant() const { return true; }
@@ -126,7 +127,7 @@ struct Signature<R (const Varargs<T>&)> : SignatureBase {
 // where T1, T2, etc. are the types of successfully-evaluated subexpressions.
 template <class R, class... Params>
 struct Signature<R (Params...)> : SignatureBase {
-    using Args = std::array<std::unique_ptr<TypedExpression>, sizeof...(Params)>;
+    using Args = std::array<std::unique_ptr<Expression>, sizeof...(Params)>;
     
     Signature(R (*evaluate_)(Params...)) :
         SignatureBase(
@@ -142,7 +143,7 @@ struct Signature<R (Params...)> : SignatureBase {
         return applyImpl(evaluationParameters, args, std::index_sequence_for<Params...>{});
     }
     
-    std::unique_ptr<TypedExpression> makeTypedExpression(std::vector<std::unique_ptr<TypedExpression>> args) const override;
+    std::unique_ptr<Expression> makeExpression(std::vector<std::unique_ptr<Expression>> args) const override;
     
     R (*evaluate)(Params...);
 private:
@@ -179,18 +180,14 @@ struct Signature<Lambda, std::enable_if_t<std::is_class<Lambda>::value>>
     : Signature<decltype(&Lambda::operator())>
 { using Signature<decltype(&Lambda::operator())>::Signature; };
 
-
-struct CompoundExpression {
-    using Definition = std::vector<std::unique_ptr<SignatureBase>>;
-    static std::unordered_map<std::string, Definition> definitions;
-};
-
 template <typename Signature>
-class TypedCompoundExpression : public TypedExpression {
+class CompoundExpression : public Expression {
 public:
-    TypedCompoundExpression(Signature signature_,
-                            typename Signature::Args args_) :
-        TypedExpression(signature_.result),
+    using Args = typename Signature::Args;
+    
+    CompoundExpression(Signature signature_,
+                       typename Signature::Args args_) :
+        Expression(signature_.result),
         signature(signature_),
         args(std::move(args_))
     {}
@@ -225,110 +222,116 @@ private:
 };
 
 
-class UntypedCompoundExpression : public UntypedExpression {
-public:
-    using Args = std::vector<std::unique_ptr<UntypedExpression>>;
-    
-    UntypedCompoundExpression(std::string key, std::string name_, std::vector<std::unique_ptr<UntypedExpression>> args_) :
-        UntypedExpression(key),
-        name(name_),
-        args(std::move(args_))
-    {}
+struct CompoundExpressions {
+    using Definition = std::vector<std::unique_ptr<SignatureBase>>;
+    static std::unordered_map<std::string, Definition> definitions;
     
     template <class V>
-    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+    static ParseResult parse(const V& value, ParsingContext ctx) {
         using namespace mbgl::style::conversion;
         assert(isArray(value) && arrayLength(value) > 0);
         const auto& name = toString(arrayMember(value, 0));
         assert(name);
         
-        if (CompoundExpression::definitions.find(*name) == CompoundExpression::definitions.end()) {
-            return CompileError {
+        auto it = definitions.find(*name);
+        if (it == definitions.end()) {
+            ctx.error(
                 std::string("Unknown expression \"") + *name + "\". If you wanted a literal array, use [\"literal\", [...]].",
-                ctx.key(0)
-            };
+                0
+            );
+            return ParseResult();
         }
-        
-        std::vector<std::unique_ptr<UntypedExpression>> args;
+        const Definition& definition = it->second;
+
+        // parse subexpressions first
+        std::vector<std::unique_ptr<Expression>> args;
         auto length = arrayLength(value);
         for (std::size_t i = 1; i < length; i++) {
-            auto parsed = parseExpression(arrayMember(value, i), ParsingContext(ctx, {i}, name));
-            if (parsed.template is<CompileError>()) {
+            auto parsed = parseExpression(arrayMember(value, i), ParsingContext(ctx, i));
+            if (!parsed) {
                 return parsed;
             }
-            args.push_back(std::move(parsed.template get<std::unique_ptr<UntypedExpression>>()));
+            args.push_back(std::move(*parsed));
         }
         
-        return std::make_unique<UntypedCompoundExpression>(ctx.key(), *name, std::move(args));
+        return create(definition, std::move(args), ctx);
     }
+    
+    static ParseResult create(const Definition& definition,
+                              std::vector<std::unique_ptr<Expression>> args,
+                              ParsingContext ctx)
+    {
+        std::vector<ParsingError> currentSignatureErrors;
 
-    TypecheckResult typecheck(std::vector<CompileError>& errors) const override {
-        const auto& definition = CompoundExpression::definitions.at(name);
+        ParsingContext signatureContext(currentSignatureErrors);
+        signatureContext.key = ctx.key;
         
-        std::vector<CompileError> currentSignatureErrors;
         for (const auto& signature : definition) {
             currentSignatureErrors.clear();
-            std::vector<std::unique_ptr<TypedExpression>> checkedArgs;
+            
+            
             if (signature->params.is<std::vector<type::Type>>()) {
                 const auto& params = signature->params.get<std::vector<type::Type>>();
                 if (params.size() != args.size()) {
-                    currentSignatureErrors.emplace_back(CompileError {
+                    signatureContext.error(
                         "Expected " + std::to_string(params.size()) +
-                        " arguments, but found " + std::to_string(args.size()) + " instead.",
-                        getKey()
-                    });
+                        " arguments, but found " + std::to_string(args.size()) + " instead."
+                    );
                     continue;
                 }
 
                 for (std::size_t i = 0; i < args.size(); i++) {
                     const auto& arg = args.at(i);
-                    auto checked = arg->typecheck(currentSignatureErrors);
-                    if (checked) {
-                        const auto& param = params.at(i);
-                        const auto& error = matchType(param, (*checked)->getType());
-                        if (error) {
-                            currentSignatureErrors.emplace_back(CompileError {
-                                *error,
-                                getKey()
-                            });
-                        } else {
-                            checkedArgs.push_back(std::move(*checked));
-                        }
-                    }
+                    checkSubtype(params.at(i), arg->getType(), ParsingContext(signatureContext, i + 1));
                 }
             } else if (signature->params.is<VarargsType>()) {
                 const auto& paramType = signature->params.get<VarargsType>().type;
                 for (std::size_t i = 0; i < args.size(); i++) {
                     const auto& arg = args.at(i);
-                    auto checked = arg->typecheck(currentSignatureErrors);
-                    if (checked) {
-                        const auto& error = matchType(paramType, (*checked)->getType());
-                        if (error) {
-                            currentSignatureErrors.emplace_back(CompileError {
-                                *error,
-                                getKey()
-                            });
-                        } else {
-                            checkedArgs.push_back(std::move(*checked));
-                        }
-                    }
+                    checkSubtype(paramType, arg->getType(), ParsingContext(signatureContext, i + 1));
                 }
             }
             
             if (currentSignatureErrors.size() == 0) {
-                return signature->makeTypedExpression(std::move(checkedArgs));
+                return ParseResult(signature->makeExpression(std::move(args)));
             }
         }
         
-        errors.insert(errors.end(), currentSignatureErrors.begin(), currentSignatureErrors.end());
-        return {};
+        if (definition.size() == 1) {
+            ctx.errors.insert(ctx.errors.end(), currentSignatureErrors.begin(), currentSignatureErrors.end());
+        } else {
+            std::string signatures;
+            for (const auto& signature : definition) {
+                signatures += (signatures.size() > 0 ? " | " : "");
+                signature->params.match(
+                    [&](const VarargsType& varargs) {
+                        signatures += "(" + toString(varargs.type) + ")";
+                    },
+                    [&](const std::vector<type::Type>& params) {
+                        signatures += "(";
+                        for (const type::Type& param : params) {
+                            signatures += toString(param);
+                        }
+                        signatures += ")";
+                    }
+                );
+                
+            }
+            std::string actualTypes = "(";
+            for (const auto& arg : args) {
+                if (actualTypes.size() > 0) {
+                    actualTypes += ", ";
+                }
+                actualTypes += toString(arg->getType());
+            }
+            ctx.error("Expected arguments of type ${signatures}, but found (${actualTypes}) instead.");
+        }
+        
+        return ParseResult();
     }
-    
-private:
-    std::string name;
-    std::vector<std::unique_ptr<UntypedExpression>> args;
 };
 
+
 } // namespace expression
 } // namespace style
 } // namespace mbgl
diff --git a/include/mbgl/style/expression/curve.hpp b/include/mbgl/style/expression/curve.hpp
index e0c9fae534..08a9573e71 100644
--- a/include/mbgl/style/expression/curve.hpp
+++ b/include/mbgl/style/expression/curve.hpp
@@ -7,53 +7,13 @@
 #include <mbgl/style/conversion.hpp>
 
 namespace mbgl {
-
-namespace util {
-
-struct InterpolateExpressionValue {
-    const double t;
-    
-    template <typename T, typename Enabled = void>
-    optional<Value> operator()(const T&, const T&) const {
-        return optional<Value>();
-    };
-    
-    template <typename T, typename std::enable_if_t<Interpolatable<T>::value>>
-    optional<Value> operator()(const T& a, const T& b) const {
-        return util::interpolate(a, b, t);
-    }
-    
-    template <typename T, typename U>
-    optional<Value> operator()(const T&, const U&) const {
-        return {};
-    }
-};
-
-template<>
-struct Interpolator<std::vector<Value>> {
-    std::vector<Value> operator()(const std::vector<Value>& a, const std::vector<Value>& b, const double t) const {
-        assert(a.size() == b.size());
-        if (a.size() == 0) return {};
-        std::vector<Value> result;
-        InterpolateExpressionValue visitor {t};
-        for (std::size_t i = 0; i < a.size(); i++) {
-            const auto& v = Value::binary_visit(a[i], b[i], visitor);
-            assert(v);
-            result.push_back(*v);
-        }
-        return result;
-    }
-};
-
-} // namespace util
-
 namespace style {
 namespace expression {
 
-template <class T = void>
+template <class T>
 class ExponentialCurve {
 public:
-    using Stops = std::map<float, std::unique_ptr<TypedExpression>>;
+    using Stops = std::map<float, std::unique_ptr<Expression>>;
 
     ExponentialCurve(Stops stops_, float base_)
         : stops(std::move(stops_)),
@@ -78,15 +38,16 @@ public:
             if (!lower) { return lower.error(); }
             const auto& upper = it->second->template evaluate<T>(parameters);
             if (!upper) { return upper.error(); }
-            return util::interpolate(*lower, *upper,
+            T result = util::interpolate(*lower, *upper,
                 util::interpolationFactor(base, { std::prev(it)->first, it->first }, x));
+            return toExpressionValue(result);
         }
     }
 };
 
 class StepCurve {
 public:
-    using Stops = std::map<float, std::unique_ptr<TypedExpression>>;
+    using Stops = std::map<float, std::unique_ptr<Expression>>;
     StepCurve(Stops stops_) : stops(std::move(stops_)) {}
     
     Stops stops;
@@ -107,11 +68,19 @@ public:
     }
 };
 
-template <typename Curve>
-class TypedCurve : public TypedExpression {
+namespace detail {
+
+// used for storing intermediate state during parsing
+struct ExponentialInterpolation { float base; std::string name = "exponential"; };
+struct StepInterpolation {};
+
+}
+
+template <typename CurveType>
+class Curve : public Expression {
 public:
-    TypedCurve(const type::Type& type, std::unique_ptr<TypedExpression> input_, Curve curve_) :
-        TypedExpression(type),
+    Curve(const type::Type& type, std::unique_ptr<Expression> input_, CurveType curve_) :
+        Expression(type),
         input(std::move(input_)),
         curve(std::move(curve_))
     {}
@@ -139,199 +108,154 @@ public:
     }
     
 private:
-    std::unique_ptr<TypedExpression> input;
-    Curve curve;
+    std::unique_ptr<Expression> input;
+    CurveType curve;
 };
 
-struct ExponentialInterpolation { float base; std::string name = "exponential"; };
-struct StepInterpolation {};
-
-class UntypedCurve : public UntypedExpression {
-public:
-    using Stops = std::vector<std::pair<float, std::unique_ptr<UntypedExpression>>>;
-    using Interpolation = variant<
-        StepInterpolation,
-        ExponentialInterpolation>;
-    UntypedCurve(const std::string& key,
-                 std::unique_ptr<UntypedExpression> input_,
-                 Stops stops_,
-                 Interpolation interpolation_
-    ) : UntypedExpression(key),
-        input(std::move(input_)),
-        stops(std::move(stops_)),
-        interpolation(interpolation_)
-    {}
-    
+struct ParseCurve {
     template <typename V>
-    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+    static ParseResult parse(const V& value, ParsingContext ctx) {
         using namespace mbgl::style::conversion;
         assert(isArray(value));
         auto length = arrayLength(value);
-        if (length < 4) {
-            return CompileError {
-                "Expected at least 3 arguments, but found only " + std::to_string(length - 1) + ".",
-                ctx.key()
-            };
+        if (length < 5) {
+            ctx.error("Expected at least 4 arguments, but found only " + std::to_string(length - 1) + ".");
+            return ParseResult();
         }
         
         // [curve, interp, input, 2 * (n pairs)...]
         if (length % 2 != 1) {
-            return CompileError {
-                "Missing final output value for \"curve\" expression.",
-                ctx.key()
-            };
+            ctx.error("Expected an even number of arguments.");
+            return ParseResult();
         }
         
         const auto& interp = arrayMember(value, 1);
         if (!isArray(interp) || arrayLength(interp) == 0) {
-            return CompileError {
-                "Expected an interpolation type expression, e.g. [\"linear\"].",
-                ctx.key(1)
-            };
+            ctx.error("Expected an interpolation type expression.");
+            return ParseResult();
         }
+
+        variant<detail::StepInterpolation,
+                detail::ExponentialInterpolation> interpolation;
         
-        Interpolation interpolation;
         const auto& interpName = toString(arrayMember(interp, 0));
         if (interpName && *interpName == "step") {
-            interpolation = StepInterpolation {};
+            interpolation = detail::StepInterpolation{};
         } else if (interpName && *interpName == "linear") {
-            interpolation = ExponentialInterpolation { 1.0f, "linear" };
+            interpolation = detail::ExponentialInterpolation { 1.0f, "linear" };
         } else if (interpName && *interpName == "exponential") {
             optional<double> base;
             if (arrayLength(interp) == 2) {
                 base = toDouble(arrayMember(interp, 1));
             }
             if (!base) {
-                return CompileError {
-                    "Exponential interpolation requires a numeric base",
-                    ctx.key(1)
-                };
+                ctx.error("Exponential interpolation requires a numeric base.");
+                return ParseResult();
             }
-            interpolation = ExponentialInterpolation { static_cast<float>(*base) };
+            interpolation = detail::ExponentialInterpolation { static_cast<float>(*base) };
         } else {
-            std::string name = interpName ? *interpName : "";
-            return CompileError {
-                "Unknown interpolation type " + name,
-                ctx.key(1)
-            };
+            ctx.error("Unknown interpolation type " + (interpName ? *interpName : ""));
+            return ParseResult();
         }
         
-        auto input = parseExpression(arrayMember(value, 2), ParsingContext(ctx, {2}, {"curve"}));
-        if (input.template is<CompileError>()) {
+        ParseResult input = parseExpression(arrayMember(value, 2), ParsingContext(ctx, 2, {type::Number}));
+        if (!input) {
             return input;
         }
         
-        Stops stops;
+        std::map<float, std::unique_ptr<Expression>> stops;
+        optional<type::Type> outputType = ctx.expected;
+        
         double previous = - std::numeric_limits<double>::infinity();
         for (std::size_t i = 3; i + 1 < length; i += 2) {
-            const auto& inputValue = toDouble(arrayMember(value, i));
-            if (!inputValue) {
-                return CompileError {
-                    "Input/output pairs for \"curve\" expressions must be defined using literal numeric values (not computed expressions) for the input values.",
-                    ctx.key(i)
-                };
-            }
-            if (*inputValue < previous) {
-                return CompileError {
-                    "Input/output pairs for \"curve\" expressions must be arranged with input values in strictly ascending order.",
-                    ctx.key(i)
-                };
+            const auto& label = toDouble(arrayMember(value, i));
+            if (!label) {
+                ctx.error("Input/output pairs for \"curve\" expressions must be defined using literal numeric values (not computed expressions) for the input values.");
+                return ParseResult();
             }
-            previous = *inputValue;
             
-            auto output = parseExpression(arrayMember(value, i + 1), ParsingContext(ctx, {i + 1}, {"curve"}));
-            if (output.template is<CompileError>()) {
-                return output;
+            if (*label < previous) {
+                ctx.error(
+                    "Input/output pairs for \"curve\" expressions must be arranged with input values in strictly ascending order."
+                );
+                return ParseResult();
             }
-            stops.push_back(std::make_pair(
-                *inputValue,
-                std::move(output.template get<std::unique_ptr<UntypedExpression>>())
-            ));
-        }
-        
-        return std::make_unique<UntypedCurve>(ctx.key(),
-                                              std::move(input.template get<std::unique_ptr<UntypedExpression>>()),
-                                              std::move(stops),
-                                              interpolation);
-    }
-    
-    TypecheckResult typecheck(std::vector<CompileError>& errors) const override {
-        auto checkedInput = input->typecheck(errors);
-        if (!checkedInput) {
-            return TypecheckResult();
-        }
-        auto error = matchType(type::Number, (*checkedInput)->getType());
-        if (error) {
-            errors.push_back({*error, input->getKey()});
-        }
-        
-        optional<type::Type> outputType;
-        std::map<float, std::unique_ptr<TypedExpression>> checkedStops;
-        for (const auto& stop : stops) {
-            auto checkedOutput = stop.second->typecheck(errors);
-            if (!checkedOutput) {
-                continue;
+            previous = *label;
+            
+            auto output = parseExpression(arrayMember(value, i + 1), ParsingContext(ctx, i + 1, outputType));
+            if (!output) {
+                return ParseResult();
             }
             if (!outputType) {
-                outputType = (*checkedOutput)->getType();
-            } else {
-                error = matchType(*outputType, (*checkedOutput)->getType());
-                if (error) {
-                    errors.push_back({ *error, stop.second->getKey() });
-                    continue;
-                }
+                outputType = (*output)->getType();
             }
-            checkedStops.emplace(stop.first, std::move(*checkedOutput));
+
+            stops.emplace(*label, std::move(*output));
         }
         
-        if (errors.size() > 0) return TypecheckResult();
+        assert(outputType);
+        
+        if (
+            !interpolation.template is<detail::StepInterpolation>() &&
+            *outputType != type::Number &&
+            *outputType != type::Color &&
+            !(
+                outputType->is<type::Array>() &&
+                outputType->get<type::Array>().itemType == type::Number
+            )
+        )
+        {
+            ctx.error("Type " + toString(*outputType) +
+                " is not interpolatable, and thus cannot be used as a " +
+                *interpName + " curve's output type");
+            return ParseResult();
+        }
         
         return interpolation.match(
-            [&](const StepInterpolation&) -> TypecheckResult {
-                return {std::make_unique<TypedCurve<StepCurve>>(
-                        *outputType,
-                        std::move(*checkedInput),
-                        StepCurve(std::move(checkedStops)))};
+            [&](const detail::StepInterpolation&) -> ParseResult {
+                return ParseResult(std::make_unique<Curve<StepCurve>>(
+                    *outputType,
+                    std::move(*input),
+                    StepCurve(std::move(stops))
+                ));
             },
-            [&](const ExponentialInterpolation& interp) {
-                TypecheckResult result = outputType->match(
-                    [&](const type::NumberType&) -> TypecheckResult {
-                        return makeExponential<float>(*outputType, std::move(*checkedInput), std::move(checkedStops), interp.base);
+            [&](const detail::ExponentialInterpolation& exponentialInterpolation) -> ParseResult {
+                const float base = exponentialInterpolation.base;
+                return outputType->match(
+                    [&](const type::NumberType&) -> ParseResult {
+                        return ParseResult(std::make_unique<Curve<ExponentialCurve<float>>>(
+                            *outputType,
+                            std::move(*input),
+                            ExponentialCurve<float>(std::move(stops), base)
+                        ));
                     },
-                    [&](const type::ColorType&) -> TypecheckResult {
-                        return makeExponential<mbgl::Color>(*outputType, std::move(*checkedInput), std::move(checkedStops), interp.base);
+                    [&](const type::ColorType&) -> ParseResult {
+                        return ParseResult(std::make_unique<Curve<ExponentialCurve<mbgl::Color>>>(
+                            *outputType,
+                            std::move(*input),
+                            ExponentialCurve<mbgl::Color>(std::move(stops), base)
+                        ));
                     },
-                    [&](const type::Array& arrayType) -> TypecheckResult {
-                        if (toString(arrayType.itemType) == type::Number.getName() && arrayType.N) {
-                            return makeExponential<std::vector<Value>>(*outputType, std::move(*checkedInput), std::move(checkedStops), interp.base);
+                    [&](const type::Array& arrayType) -> ParseResult {
+                        if (arrayType.itemType == type::Number && arrayType.N) {
+                            return ParseResult(std::make_unique<Curve<ExponentialCurve<std::vector<float>>>>(
+                                *outputType,
+                                std::move(*input),
+                                ExponentialCurve<std::vector<float>>(std::move(stops), base)
+                            ));
                         } else {
-                            return TypecheckResult();
+                            assert(false); // interpolability already checked above.
+                            return ParseResult();
                         }
                     },
-                    [&](const auto&) { return TypecheckResult(); }
+                    [&](const auto&) {
+                        assert(false); // interpolability already checked above.
+                        return ParseResult();
+                    }
                 );
-                if (!result) {
-                    errors.push_back({"Type " + toString(*outputType) + " is not interpolatable, and thus cannot be used as an exponential curve's output type", stops.begin()->second->getKey() });
-                }
-                return result;
             }
         );
     }
-    
-    
-private:
-    template <typename T>
-    std::unique_ptr<TypedExpression> makeExponential(const type::Type type, std::unique_ptr<TypedExpression> checkedInput, std::map<float, std::unique_ptr<TypedExpression>> checkedStops, float base) const {
-        return std::make_unique<TypedCurve<ExponentialCurve<T>>>(
-            type,
-            std::move(checkedInput),
-            ExponentialCurve<T>(std::move(checkedStops), base)
-        );
-    }
-
-    std::unique_ptr<UntypedExpression> input;
-    Stops stops;
-    Interpolation interpolation;
 };
 
 } // namespace expression
diff --git a/include/mbgl/style/expression/expression.hpp b/include/mbgl/style/expression/expression.hpp
index e512d7355c..0e2137c798 100644
--- a/include/mbgl/style/expression/expression.hpp
+++ b/include/mbgl/style/expression/expression.hpp
@@ -74,15 +74,10 @@ struct EvaluationResult : public Result<Value> {
     {}
 };
 
-struct CompileError {
-    std::string message;
-    std::string key;
-};
-
-class TypedExpression {
+class Expression {
 public:
-    TypedExpression(type::Type type_) : type(type_) {}
-    virtual ~TypedExpression() {};
+    Expression(type::Type type_) : type(type_) {}
+    virtual ~Expression() {};
     
     virtual bool isFeatureConstant() const = 0;
     virtual bool isZoomConstant() const = 0;
@@ -110,28 +105,13 @@ public:
     
     EvaluationResult evaluate(float z, const Feature& feature) const;
     
-    type::Type getType() const { return type; }
+    type::Type getType() const { return type; };
     
 private:
     type::Type type;
 };
 
-using TypecheckResult = optional<std::unique_ptr<TypedExpression>>;
-
-class UntypedExpression {
-public:
-    UntypedExpression(std::string key_) : key(key_) {}
-    virtual ~UntypedExpression() {}
-    
-    std::string getKey() const { return key; }
-    virtual TypecheckResult typecheck(std::vector<CompileError>& errors) const = 0;
-private:
-    std::string key;
-};
-
-using ParseResult = variant<CompileError, std::unique_ptr<UntypedExpression>>;
-template <class V>
-ParseResult parseExpression(const V& value, const ParsingContext& context);
+using ParseResult = optional<std::unique_ptr<Expression>>;
 
 
 } // namespace expression
diff --git a/include/mbgl/style/expression/literal.hpp b/include/mbgl/style/expression/literal.hpp
index a18570592c..7a3e4ba0cc 100644
--- a/include/mbgl/style/expression/literal.hpp
+++ b/include/mbgl/style/expression/literal.hpp
@@ -16,34 +16,38 @@ namespace mbgl {
 namespace style {
 namespace expression {
 
-class TypedLiteral : public TypedExpression {
+class Literal : public Expression {
 public:
-    TypedLiteral(Value value_) : TypedExpression(typeOf(value_)), value(value_) {}
+    Literal(Value value_) : Expression(typeOf(value_)), value(value_) {}
+    Literal(type::Array type, std::vector<Value> value_) : Expression(type), value(value_) {}
     EvaluationResult evaluate(const EvaluationParameters&) const override {
         return value;
     }
     bool isFeatureConstant() const override { return true; }
     bool isZoomConstant() const override { return true; }
-private:
-    Value value;
-};
-
-class UntypedLiteral : public UntypedExpression {
-public:
-    UntypedLiteral(std::string key_, Value value_) : UntypedExpression(key_), value(value_) {}
-
-    TypecheckResult typecheck(std::vector<CompileError>&) const override {
-        return {std::make_unique<TypedLiteral>(value)};
-    }
     
-    Value getValue() const { return value; }
-
     template <class V>
-    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+    static ParseResult parse(const V& value, ParsingContext ctx) {
         const Value& parsedValue = parseValue(value);
-        return std::make_unique<UntypedLiteral>(ctx.key(), parsedValue);
+        
+        // special case: infer the item type if possible for zero-length arrays
+        if (
+            ctx.expected &&
+            ctx.expected->template is<type::Array>() &&
+            parsedValue.template is<std::vector<Value>>()
+        ) {
+            auto type = typeOf(parsedValue).template get<type::Array>();
+            auto expected = ctx.expected->template get<type::Array>();
+            if (
+                type.N && (*type.N == 0) &&
+                (!expected.N || (*expected.N == 0))
+            ) {
+                return ParseResult(std::make_unique<Literal>(expected, parsedValue.template get<std::vector<Value>>()));
+            }
+        }
+        return ParseResult(std::make_unique<Literal>(parsedValue));
     }
-
+    
 private:
     template <class V>
     static Value parseValue(const V& value) {
@@ -75,7 +79,6 @@ private:
     Value value;
 };
 
-
 } // namespace expression
 } // namespace style
 } // namespace mbgl
diff --git a/include/mbgl/style/expression/match.hpp b/include/mbgl/style/expression/match.hpp
index bd0096e044..8a265930f3 100644
--- a/include/mbgl/style/expression/match.hpp
+++ b/include/mbgl/style/expression/match.hpp
@@ -1,5 +1,6 @@
 #pragma once
 
+#include <mbgl/style/expression/check_subtype.hpp>
 #include <mbgl/style/expression/expression.hpp>
 #include <mbgl/style/expression/parsing_context.hpp>
 #include <mbgl/style/conversion.hpp>
@@ -9,32 +10,21 @@ namespace style {
 namespace expression {
 
 using InputType = variant<int64_t, std::string>;
-using MatchKey = variant<InputType, std::vector<InputType>>;
 
 template <typename T>
-class TypedMatch : public TypedExpression {
+class Match : public Expression {
 public:
-    TypedMatch(std::unique_ptr<TypedExpression> input_,
-               std::vector<std::pair<MatchKey, std::unique_ptr<TypedExpression>>> cases_,
-               std::unique_ptr<TypedExpression> otherwise_
-    ) : TypedExpression(otherwise_->getType()),
+    using Cases = std::unordered_map<T, std::shared_ptr<Expression>>;
+
+    Match(type::Type type,
+          std::unique_ptr<Expression> input_,
+          Cases cases_,
+          std::unique_ptr<Expression> otherwise_
+    ) : Expression(type),
         input(std::move(input_)),
+        cases(std::move(cases_)),
         otherwise(std::move(otherwise_))
-    {
-        for(auto& pair : cases_) {
-            pair.first.match(
-                [&](const InputType& key) {
-                    cases.emplace(key.get<T>(), std::move(pair.second));
-                },
-                [&](const std::vector<InputType>& keys) {
-                    std::shared_ptr<TypedExpression> output = std::move(pair.second);
-                    for (const auto& key : keys) {
-                        cases.emplace(key.get<T>(), output);
-                    }
-                }
-            );
-        }
-    }
+    {}
     
     bool isFeatureConstant() const override {
         if (!input->isFeatureConstant()) { return false; }
@@ -54,122 +44,110 @@ public:
         return true;
     }
     
-    EvaluationResult evaluate(const EvaluationParameters& params) const override {
-        const auto& inputValue = evaluateInput(params);
-        if (!inputValue) {
-            return inputValue.error();
-        }
-        if (cases.find(*inputValue) == cases.end()) {
-            return otherwise->evaluate(params);
-        }
-        return cases.at(*inputValue)->evaluate(params);
-    }
-
+    EvaluationResult evaluate(const EvaluationParameters& params) const override;
+    
 private:
-    Result<T> evaluateInput(const EvaluationParameters& params) const;
-
-    std::unique_ptr<TypedExpression> input;
-    std::unordered_map<T, std::shared_ptr<TypedExpression>> cases;
-    std::unique_ptr<TypedExpression> otherwise;
+    
+    std::unique_ptr<Expression> input;
+    Cases cases;
+    std::unique_ptr<Expression> otherwise;
 };
 
-class UntypedMatch : public UntypedExpression {
-public:
-    using Cases = std::vector<std::pair<MatchKey, std::unique_ptr<UntypedExpression>>>;
-    
-    UntypedMatch(std::string key,
-                 std::unique_ptr<UntypedExpression> input_,
-                 Cases cases_,
-                 std::unique_ptr<UntypedExpression> otherwise_,
-                 const type::Type& inputType_) :
-        UntypedExpression(key),
-        input(std::move(input_)),
-        cases(std::move(cases_)),
-        otherwise(std::move(otherwise_)),
-        inputType(inputType_)
-    {}
-    
+struct ParseMatch {
     template <class V>
-    static ParseResult parse(const V& value, const ParsingContext& ctx) {
+    static ParseResult parse(const V& value, ParsingContext ctx) {
         using namespace mbgl::style::conversion;
         
         assert(isArray(value));
         auto length = arrayLength(value);
-        if (length < 3) {
-            return CompileError {
-                "Expected at least 2 arguments, but found only " + std::to_string(length - 1) + ".",
-                ctx.key()
-            };
+        if (length < 5) {
+            ctx.error(
+                "Expected at least 4 arguments, but found only " + std::to_string(length - 1) + "."
+            );
+            return ParseResult();
         }
         
         // Expect odd-length array: ["match", input, 2 * (n pairs)..., otherwise]
         if (length % 2 != 1) {
-            return CompileError {
-                "Missing final output value for \"match\" expression.",
-                ctx.key()
-            };
-        }
-        
-        auto parsedInput = parseExpression(arrayMember(value, 1), ParsingContext(ctx, {1}, {"match"}));
-        if (parsedInput.template is<CompileError>()) {
-            return parsedInput;
-        }
-        
-        auto otherwise = parseExpression(arrayMember(value, length - 1), ParsingContext(ctx, {length - 1}, {"match"}));
-        if (otherwise.template is<CompileError>()) {
-            return otherwise;
+            ctx.error("Expected an even number of arguments.");
+            return ParseResult();
         }
         
-        Cases cases;
         optional<type::Type> inputType;
+        optional<type::Type> outputType = ctx.expected;
+        std::vector<std::pair<std::vector<InputType>,
+                              std::unique_ptr<Expression>>> cases;
+        
         for (size_t i = 2; i + 1 < length; i += 2) {
-            auto output = parseExpression(arrayMember(value, i + 1), ParsingContext(ctx, {i + 1}, {"match"}));
-            if (output.template is<CompileError>()) {
-                return output.template get<CompileError>();
-            }
+            const auto& label = arrayMember(value, i);
 
-            const auto& inputArg = arrayMember(value, i);
+            ParsingContext labelContext(ctx, i);
+            std::vector<InputType> labels;
             // Match pair inputs are provided as either a literal value or a
             // raw JSON array of string / number / boolean values.
-            if (isArray(inputArg)) {
-                auto groupLength = arrayLength(inputArg);
-                if (groupLength == 0) return CompileError {
-                    "Expected at least one input value.",
-                    ctx.key(i)
-                };
-                std::vector<InputType> inputGroup;
+            if (isArray(label)) {
+                auto groupLength = arrayLength(label);
+                if (groupLength == 0) {
+                    labelContext.error("Expected at least one branch label.");
+                    return ParseResult();
+                }
+                
                 for (size_t j = 0; j < groupLength; j++) {
-                    const auto& inputValue = parseInputValue(arrayMember(inputArg, j), ctx.key(i), inputType);
-                    if (inputValue.template is<CompileError>()) {
-                        return inputValue.template get<CompileError>();
+                    const optional<InputType>& inputValue = parseInputValue(arrayMember(label, j), ParsingContext(ctx, i), inputType);
+                    if (!inputValue) {
+                        return ParseResult();
                     }
-                    inputGroup.emplace_back(inputValue.template get<InputType>());
+                    labels.push_back(*inputValue);
                 }
-                cases.push_back(std::make_pair(
-                    inputGroup,
-                    std::move(output.template get<std::unique_ptr<UntypedExpression>>()))
-                );
             } else {
-                const auto& inputValue = parseInputValue(inputArg, ctx.key(i), inputType);
-                if (inputValue.template is<CompileError>()) {
-                    return inputValue.template get<CompileError>();
+                const optional<InputType>& inputValue = parseInputValue(label, ParsingContext(ctx, i), inputType);
+                if (!inputValue) {
+                    return ParseResult();
                 }
-                cases.push_back(std::make_pair(
-                    inputValue.template get<InputType>(),
-                    std::move(output.template get<std::unique_ptr<UntypedExpression>>()))
-                );
+                labels.push_back(*inputValue);
             }
+            
+            ParseResult output = parseExpression(arrayMember(value, i + 1), ParsingContext(ctx, i + 1, outputType));
+            if (!output) {
+                return ParseResult();
+            }
+            
+            if (!outputType) {
+                outputType = (*output)->getType();
+            }
+            
+            cases.push_back(std::make_pair(std::move(labels), std::move(*output)));
+        }
+        
+        auto input = parseExpression(arrayMember(value, 1), ParsingContext(ctx, 1, inputType));
+        if (!input) {
+            return ParseResult();
+        }
+        
+        auto otherwise = parseExpression(arrayMember(value, length - 1), ParsingContext(ctx, length - 1, outputType));
+        if (!otherwise) {
+            return ParseResult();
         }
         
-        return std::make_unique<UntypedMatch>(ctx.key(),
-                                              std::move(parsedInput.template get<std::unique_ptr<UntypedExpression>>()),
-                                              std::move(cases),
-                                              std::move(otherwise.template get<std::unique_ptr<UntypedExpression>>()),
-                                              *inputType);
+        assert(inputType && outputType);
+        
+        return inputType->match(
+            [&](const type::NumberType&) {
+                return create<int64_t>(*outputType, std::move(*input), std::move(cases), std::move(*otherwise), ctx);
+            },
+            [&](const type::StringType&) {
+                return create<std::string>(*outputType, std::move(*input), std::move(cases), std::move(*otherwise), ctx);
+            },
+            [&](const auto&) {
+                assert(false);
+                return ParseResult();
+            }
+        );
     }
-    
+
+private:
     template <typename V>
-    static variant<CompileError, InputType> parseInputValue(const V& input, const std::string& key, optional<type::Type>& inputType) {
+    static optional<InputType> parseInputValue(const V& input, ParsingContext ctx, optional<type::Type>& inputType) {
         using namespace mbgl::style::conversion;
         optional<InputType> result;
         optional<type::Type> type;
@@ -182,81 +160,51 @@ public:
             type = {type::String};
             result = {value->template get<std::string>()};
         } else {
-            return CompileError {
-                "Match inputs must be either literal integer or string values or arrays of integer or string values.",
-                key
-            };
+            ctx.error("Branch labels must be numbers or strings.");
+            return optional<InputType>();
         }
         
         if (!inputType) {
             inputType = type;
-        } else {
-            const auto& expected = toString(*inputType);
-            const auto& actual = toString(*type);
-            // TODO: replace with real == check
-            if (expected != actual) {
-                return CompileError {
-                    "Expected " + expected + " but found " + actual + " instead.",
-                    key
-                };
-            }
+        } else if (checkSubtype(*inputType, *type, ctx)) {
+            return optional<InputType>();
         }
         
-        return *result;
+        return result;
     }
     
-    TypecheckResult typecheck(std::vector<CompileError>& errors) const override {
-        auto checkedInput = input->typecheck(errors);
-        if (!checkedInput) {
-            return TypecheckResult();
-        }
-        auto checkedOtherwise = otherwise->typecheck(errors);
-        if (!checkedOtherwise) {
-            return TypecheckResult();
-        }
-
-        auto error = matchType(inputType, (*checkedInput)->getType());
-        if (error) {
-            errors.push_back({ *error, input->getKey() });
-        }
+    template <typename T>
+    static ParseResult create(type::Type outputType,
+                              std::unique_ptr<Expression>input,
+                              std::vector<std::pair<std::vector<InputType>,
+                                                    std::unique_ptr<Expression>>> cases,
+                              std::unique_ptr<Expression> otherwise,
+                              ParsingContext ctx) {
+        typename Match<T>::Cases typedCases;
         
-        optional<type::Type> outputType;
-        std::vector<std::pair<MatchKey, std::unique_ptr<TypedExpression>>> checkedCases;
-        for (const auto& pair : cases) {
-            auto checkedOutput = pair.second->typecheck(errors);
-            if (!checkedOutput) continue;
-            if (!outputType) {
-                outputType = (*checkedOutput)->getType();
-            } else {
-                error = matchType(*outputType, (*checkedOutput)->getType());
-                if (error) {
-                    errors.push_back({ *error, pair.second->getKey() });
-                    continue;
+        std::size_t index = 2;
+        for (std::pair<std::vector<InputType>,
+                       std::unique_ptr<Expression>>& pair : cases) {
+            std::shared_ptr<Expression> result = std::move(pair.second);
+            for (const InputType& label : pair.first) {
+                const T& typedLabel = label.template get<T>();
+                if (typedCases.find(typedLabel) != typedCases.end()) {
+                    ctx.error("Branch labels must be unique.", index);
+                    return ParseResult();
                 }
+                typedCases.emplace(typedLabel, result);
             }
-            checkedCases.emplace_back(pair.first, std::move(*checkedOutput));
-        }
-        
-        error = matchType(*outputType, (*checkedOtherwise)->getType());
-        if (error) {
-            errors.push_back({ *error, otherwise->getKey() });
-        }
-        
-        if (inputType.is<type::StringType>()) {
-            return TypecheckResult(std::make_unique<TypedMatch<std::string>>(
-                std::move(*checkedInput), std::move(checkedCases), std::move(*checkedOtherwise)
-            ));
-        } else if (inputType.is<type::NumberType>()) {
-            return TypecheckResult(std::make_unique<TypedMatch<int64_t>>(
-                std::move(*checkedInput), std::move(checkedCases), std::move(*checkedOtherwise)
-            ));
-        }
-        
-        assert(false);
-        return TypecheckResult();
+            
+            index += 2;
+        }
+        return ParseResult(std::make_unique<Match<T>>(
+            outputType,
+            std::move(input),
+            std::move(typedCases),
+            std::move(otherwise)
+        ));
     }
-    
-private:
+
     static bool isIntegerValue(const mbgl::Value& v) {
         return v.match(
             [] (uint64_t) { return true; },
@@ -265,11 +213,6 @@ private:
             [] (const auto&) { return false; }
         );
     }
-
-    std::unique_ptr<UntypedExpression> input;
-    Cases cases;
-    std::unique_ptr<UntypedExpression> otherwise;
-    type::Type inputType;
 };
 
 } // namespace expression
diff --git a/include/mbgl/style/expression/parse.hpp b/include/mbgl/style/expression/parse.hpp
index 89d4354d76..2c83913f03 100644
--- a/include/mbgl/style/expression/parse.hpp
+++ b/include/mbgl/style/expression/parse.hpp
@@ -4,6 +4,7 @@
 #include <mbgl/style/conversion.hpp>
 #include <mbgl/style/expression/array_assertion.hpp>
 #include <mbgl/style/expression/case.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
 #include <mbgl/style/expression/coalesce.hpp>
 #include <mbgl/style/expression/compound_expression.hpp>
 #include <mbgl/style/expression/curve.hpp>
@@ -36,64 +37,71 @@ std::string getJSType(const V& value) {
     );
 }
 
-using ParseResult = variant<CompileError, std::unique_ptr<UntypedExpression>>;
-
 template <class V>
-ParseResult parseExpression(const V& value, const ParsingContext& context)
+ParseResult parseExpression(const V& value, ParsingContext context)
 {
     using namespace mbgl::style::conversion;
     
+    ParseResult parsed;
+    
     if (isArray(value)) {
         const std::size_t length = arrayLength(value);
         if (length == 0) {
-            CompileError error = {
-                "Expected an array with at least one element. If you wanted a literal array, use [\"literal\", []].",
-                context.key()
-            };
-            return error;
+            context.error("Expected an array with at least one element. If you wanted a literal array, use [\"literal\", []].");
+            return ParseResult();
         }
         
         const optional<std::string>& op = toString(arrayMember(value, 0));
         if (!op) {
-            CompileError error = {
+            context.error(
                 "Expression name must be a string, but found " + getJSType(arrayMember(value, 0)) +
                     " instead. If you wanted a literal array, use [\"literal\", [...]].",
-                context.key(0)
-            };
-            return error;
+                0
+            );
+            return ParseResult();
         }
         
         if (*op == "literal") {
-            if (length != 2) return CompileError {
-                "'literal' expression requires exactly one argument, but found " + std::to_string(length - 1) + " instead.",
-                context.key()
-            };
-            return UntypedLiteral::parse(arrayMember(value, 1), ParsingContext(context, {1}, {"literal"}));
-        }
-        
-        if (*op == "match") {
-            return UntypedMatch::parse(value, context);
+            if (length != 2) {
+                context.error(
+                    "'literal' expression requires exactly one argument, but found " + std::to_string(length - 1) + " instead."
+                );
+                return ParseResult();
+            }
+            
+            parsed = Literal::parse(arrayMember(value, 1), ParsingContext(context, 1, context.expected));
+        } else if (*op == "match") {
+            parsed = ParseMatch::parse(value, context);
         } else if (*op == "curve") {
-            return UntypedCurve::parse(value, context);
+            parsed = ParseCurve::parse(value, context);
         } else if (*op == "coalesce") {
-            return UntypedCoalesce::parse(value, context);
+            parsed = Coalesce::parse(value, context);
         } else if (*op == "case") {
-            return UntypedCase::parse(value, context);
+            parsed = Case::parse(value, context);
         } else if (*op == "array") {
-            return UntypedArrayAssertion::parse(value, context);
+            parsed = ArrayAssertion::parse(value, context);
+        } else {
+            parsed = CompoundExpressions::parse(value, context);
+        }
+    } else {
+        if (isObject(value)) {
+            context.error("Bare objects invalid. Use [\"literal\", {...}] instead.");
+            return ParseResult();
         }
         
-        return UntypedCompoundExpression::parse(value, context);
+        parsed = Literal::parse(value, context);
     }
     
-    if (isObject(value)) {
-        return CompileError {
-            "Bare objects invalid. Use [\"literal\", {...}] instead.",
-            context.key()
-        };
+    if (!parsed) {
+        assert(context.errors.size() > 0);
+    } else if (context.expected) {
+        checkSubtype(*(context.expected), (*parsed)->getType(), context);
+        if (context.errors.size() > 0) {
+            return ParseResult();
+        }
     }
     
-    return UntypedLiteral::parse(value, context);
+    return parsed;
 }
 
 
diff --git a/include/mbgl/style/expression/parsing_context.hpp b/include/mbgl/style/expression/parsing_context.hpp
index 7898da790d..b93b1419bf 100644
--- a/include/mbgl/style/expression/parsing_context.hpp
+++ b/include/mbgl/style/expression/parsing_context.hpp
@@ -3,36 +3,41 @@
 #include <string>
 #include <vector>
 #include <mbgl/util/optional.hpp>
+#include <mbgl/style/expression/type.hpp>
 
 namespace mbgl {
 namespace style {
 namespace expression {
 
+struct ParsingError {
+    std::string message;
+    std::string key;
+};
+
 class ParsingContext {
 public:
-    ParsingContext() {}
-    ParsingContext(ParsingContext previous,
-                   optional<size_t> index,
-                   optional<std::string> name) :
-                   path(previous.path),
-                   ancestors(previous.ancestors)
-    {
-        if (index) path.emplace_back(*index);
-        if (name) ancestors.emplace_back(*name);
-    }
+    ParsingContext(std::vector<ParsingError>& errors_, optional<type::Type> expected_ = {})
+        : errors(errors_),
+          expected(expected_)
+    {}
     
-    std::string key() const {
-        std::string result;
-        for(auto const& index : path) { result += "[" + std::to_string(index) + "]"; }
-        return result;
+    ParsingContext(const ParsingContext previous, std::size_t index_, optional<type::Type> expected_ = {})
+        : key(previous.key + "[" + std::to_string(index_) + "]"),
+          errors(previous.errors),
+          expected(expected_)
+    {}
+
+    void error(std::string message) {
+        errors.push_back({message, key});
     }
     
-    std::string key(size_t lastIndex) const {
-        return key() + "[" + std::to_string(lastIndex) + "]";
+    void  error(std::string message, std::size_t child) {
+        errors.push_back({message, key + "[" + std::to_string(child) + "]"});
     }
-    
-    std::vector<size_t> path;
-    std::vector<std::string> ancestors;
+
+    std::string key;
+    std::vector<ParsingError>& errors;
+    optional<type::Type> expected;
 };
 
 } // namespace expression
diff --git a/include/mbgl/style/expression/type.hpp b/include/mbgl/style/expression/type.hpp
index 995440dfde..3ad2faa3c8 100644
--- a/include/mbgl/style/expression/type.hpp
+++ b/include/mbgl/style/expression/type.hpp
@@ -5,6 +5,7 @@
 #include <mbgl/util/optional.hpp>
 #include <mbgl/util/variant.hpp>
 
+
 namespace mbgl {
 namespace style {
 namespace expression {
@@ -16,36 +17,43 @@ std::string toString(const T& t);
 struct NullType {
     constexpr NullType() {}
     std::string getName() const { return "Null"; }
+    bool operator==(const NullType&) const { return true; }
 };
 
 struct NumberType {
     constexpr NumberType() {}
     std::string getName() const { return "Number"; }
+    bool operator==(const NumberType&) const { return true; }
 };
 
 struct BooleanType {
     constexpr BooleanType() {}
     std::string getName() const { return "Boolean"; }
+    bool operator==(const BooleanType&) const { return true; }
 };
 
 struct StringType {
     constexpr StringType() {}
     std::string getName() const { return "String"; }
+    bool operator==(const StringType&) const { return true; }
 };
 
 struct ColorType {
     constexpr ColorType() {}
     std::string getName() const { return "Color"; }
+    bool operator==(const ColorType&) const { return true; }
 };
 
 struct ObjectType {
     constexpr ObjectType() {}
     std::string getName() const { return "Object"; }
+    bool operator==(const ObjectType&) const { return true; }
 };
 
 struct ValueType {
     constexpr ValueType() {}
     std::string getName() const { return "Value"; }
+    bool operator==(const ValueType&) const { return true; }
 };
 
 constexpr NullType Null;
@@ -56,14 +64,6 @@ constexpr ColorType Color;
 constexpr ValueType Value;
 constexpr ObjectType Object;
 
-class Typename {
-public:
-    Typename(std::string name_) : name(name_) {}
-    std::string getName() const { return name; }
-private:
-    std::string name;
-};
-
 struct Array;
 
 using Type = variant<
@@ -74,7 +74,6 @@ using Type = variant<
     ColorType,
     ObjectType,
     ValueType,
-    Typename,
     mapbox::util::recursive_wrapper<Array>>;
 
 struct Array {
@@ -90,6 +89,8 @@ struct Array {
             return "Array<" + toString(itemType) + ">";
         }
     }
+
+    bool operator==(const Array& rhs) const { return itemType == rhs.itemType && N == rhs.N; }
     
     Type itemType;
     optional<std::size_t> N;
@@ -98,18 +99,6 @@ struct Array {
 template <class T>
 std::string toString(const T& t) { return t.match([&] (const auto& t) { return t.getName(); }); }
 
-bool isGeneric(const Type& t);
-Type resolveTypenamesIfPossible(const Type&, const std::unordered_map<std::string, Type>&);
-
-optional<std::string> matchType(const Type& expected, const Type& t);
-
-enum TypenameScope { expected, actual };
-optional<std::string> matchType(const Type& expected,
-                                const Type& t,
-                                std::unordered_map<std::string, Type>& typenames,
-                                TypenameScope scope = TypenameScope::expected);
-
-
 } // namespace type
 } // namespace expression
 } // namespace style
diff --git a/include/mbgl/style/function/camera_function.hpp b/include/mbgl/style/function/camera_function.hpp
index 3d33c814cb..5a0f5ffe4a 100644
--- a/include/mbgl/style/function/camera_function.hpp
+++ b/include/mbgl/style/function/camera_function.hpp
@@ -44,7 +44,7 @@ public:
     Stops stops;
 
 private:
-    std::shared_ptr<expression::TypedExpression> expression;
+    std::shared_ptr<expression::Expression> expression;
 };
 
 } // namespace style
diff --git a/include/mbgl/style/function/convert.hpp b/include/mbgl/style/function/convert.hpp
index ae439faa54..ad42f3f9d2 100644
--- a/include/mbgl/style/function/convert.hpp
+++ b/include/mbgl/style/function/convert.hpp
@@ -29,88 +29,135 @@ struct Convert {
     // TODO: Organize. Where should each of these actually go?
 
     template <typename T>
-    static std::unique_ptr<UntypedLiteral> makeLiteral(const T& value) {
-        return std::make_unique<UntypedLiteral>("", Value(toExpressionValue(value)));
+    static std::unique_ptr<Literal> makeLiteral(const T& value) {
+        return std::make_unique<Literal>(Value(toExpressionValue(value)));
     }
     
-    static std::unique_ptr<UntypedExpression> makeGet(const std::string& type, const std::string& property) {
-        UntypedCompoundExpression::Args getArgs;
+    static std::unique_ptr<Expression> makeGet(const std::string& type, const std::string& property, ParsingContext ctx) {
+        std::vector<std::unique_ptr<Expression>> getArgs;
         getArgs.push_back(makeLiteral(property));
-        auto get = std::make_unique<UntypedCompoundExpression>("", "get", std::move(getArgs));
-        UntypedCompoundExpression::Args assertionArgs;
-        assertionArgs.push_back(std::move(get));
-        return std::make_unique<UntypedCompoundExpression>("", type, std::move(assertionArgs));
+        ParseResult get = CompoundExpressions::create(CompoundExpressions::definitions.at("get"),
+                                                      std::move(getArgs),
+                                                      ctx);
+
+        std::vector<std::unique_ptr<Expression>> assertionArgs;
+        assertionArgs.push_back(std::move(*get));
+        
+        return std::move(*(CompoundExpressions::create(CompoundExpressions::definitions.at(type),
+                                                       std::move(assertionArgs),
+                                                       ctx)));
     }
     
-    static std::unique_ptr<UntypedExpression> makeZoom() {
-        return std::make_unique<UntypedCompoundExpression>("", "zoom", UntypedCompoundExpression::Args());
+    static std::unique_ptr<Expression> makeZoom(ParsingContext ctx) {
+        return std::move(*(CompoundExpressions::create(CompoundExpressions::definitions.at("zoom"),
+                                                       std::vector<std::unique_ptr<Expression>>(),
+                                                       ctx)));
     }
 
     template <typename T>
-    static std::unique_ptr<UntypedExpression> makeCoalesceToDefault(std::unique_ptr<UntypedExpression> main, optional<T> defaultValue) {
+    static ParseResult makeCoalesceToDefault(std::unique_ptr<Expression> main, optional<T> defaultValue) {
         if (!defaultValue) {
-            return main;
+            return ParseResult(std::move(main));
         }
         
-        UntypedCoalesce::Args args;
+        Coalesce::Args args;
         args.push_back(std::move(main));
         args.push_back(makeLiteral(*defaultValue));
-        return(std::make_unique<UntypedCoalesce>("", std::move(args)));
+        return ParseResult(std::make_unique<Coalesce>(valueTypeToExpressionType<T>(), std::move(args)));
     }
-
+    
     template <typename T>
-    static std::unique_ptr<TypedExpression> makeCurve(std::unique_ptr<UntypedExpression> input,
-                                                      UntypedCurve::Interpolation interpolation,
-                                                      const std::map<float, T>& stops,
-                                                      optional<T> defaultValue)
-    {
-        UntypedCurve::Stops convertedStops;
+    static std::map<float, std::unique_ptr<Expression>> convertStops(const std::map<float, T>& stops) {
+        std::map<float, std::unique_ptr<Expression>> convertedStops;
         for(const auto& stop : stops) {
-            convertedStops.push_back(std::make_pair(
+            convertedStops.emplace(
                 stop.first,
                 makeLiteral(stop.second)
-            ));
+            );
         }
+        return convertedStops;
+    }
+    
+    template <typename T>
+    static ParseResult makeExponentialCurve(std::unique_ptr<Expression> input,
+                                                            const ExponentialStops<T>& stops,
+                                                            optional<T> defaultValue)
+    {
+        std::map<float, std::unique_ptr<Expression>> convertedStops = convertStops(stops.stops);
+        ParseResult curve = valueTypeToExpressionType<T>().match(
+            [&](const type::NumberType& t) -> ParseResult {
+                return ParseResult(std::make_unique<Curve<ExponentialCurve<float>>>(
+                    t,
+                    std::move(input),
+                    ExponentialCurve<float>(std::move(convertedStops), stops.base)
+                ));
+            },
+            [&](const type::ColorType& t) -> ParseResult {
+                return ParseResult(std::make_unique<Curve<ExponentialCurve<mbgl::Color>>>(
+                    t,
+                    std::move(input),
+                    ExponentialCurve<mbgl::Color>(std::move(convertedStops), stops.base)
+                ));
+            },
+            [&](const type::Array& arrayType) -> ParseResult {
+                if (arrayType.itemType == type::Number && arrayType.N) {
+                    return ParseResult(std::make_unique<Curve<ExponentialCurve<std::vector<Value>>>>(
+                        arrayType,
+                        std::move(input),
+                        ExponentialCurve<std::vector<Value>>(std::move(convertedStops), stops.base)
+                    ));
+                } else {
+                    // never: interpolability ensured by ExponentialStops<T>.
+                    return ParseResult();
+                }
+            },
+            [&](const auto&) -> ParseResult {
+                // never: interpolability ensured by ExponentialStops<T>.
+                return ParseResult();
+            }
+        );
         
-        std::unique_ptr<UntypedExpression> curve = std::make_unique<UntypedCurve>("", std::move(input), std::move(convertedStops), interpolation);
-        
-        std::vector<CompileError> errors;
-        auto checked = makeCoalesceToDefault(std::move(curve), defaultValue)->typecheck(errors);
-        assert(checked);
-        return std::move(*checked);
+        assert(curve);
+        return makeCoalesceToDefault(std::move(*curve), defaultValue);
+    }
+    
+    template <typename T>
+    static ParseResult makeStepCurve(std::unique_ptr<Expression> input,
+                                     const IntervalStops<T>& stops,
+                                     optional<T> defaultValue)
+    {
+        std::map<float, std::unique_ptr<Expression>> convertedStops = convertStops(stops.stops);
+        auto curve = std::make_unique<Curve<StepCurve>>(valueTypeToExpressionType<T>(),
+                                                                  std::move(input),
+                                                                  StepCurve(std::move(convertedStops)));
+        return makeCoalesceToDefault(std::move(curve), defaultValue);
     }
     
     template <typename Key, typename T>
-    static std::unique_ptr<UntypedExpression> makeMatch(std::unique_ptr<UntypedExpression> input,
+    static ParseResult makeMatch(std::unique_ptr<Expression> input,
                                                         const CategoricalStops<T>& stops) {
         // match expression
-        UntypedMatch::Cases cases;
-        optional<type::Type> inputType;
+        typename Match<Key>::Cases cases;
         for(const auto& stop : stops.stops) {
-            if (!inputType) {
-                inputType = stop.first.template is<std::string>() ?
-                    type::Type(type::String) : type::Type(type::Number);
-            }
             assert(stop.first.template is<Key>());
             auto key = stop.first.template get<Key>();
-            cases.push_back(std::make_pair(
+            cases.emplace(
                 std::move(key),
                 makeLiteral(stop.second)
-            ));
+            );
         }
         
-        return std::make_unique<UntypedMatch>("",
-                                             std::move(input),
-                                             std::move(cases),
-                                             makeLiteral(Null),
-                                             *inputType);
+        return ParseResult(std::make_unique<Match<Key>>(valueTypeToExpressionType<T>(),
+                                            std::move(input),
+                                            std::move(cases),
+                                            makeLiteral(Null)));
     }
     
     template <typename T>
-    static std::unique_ptr<UntypedExpression> makeCase(std::unique_ptr<UntypedExpression> input,
+    static ParseResult makeCase(std::unique_ptr<Expression> input,
                                                        const CategoricalStops<T>& stops) {
         // case expression
-        UntypedCase::Cases cases;
+        std::vector<typename Case::Branch> cases;
         auto true_case = stops.stops.find(true) == stops.stops.end() ?
             makeLiteral(Null) :
             makeLiteral(stops.stops.at(true));
@@ -118,97 +165,115 @@ struct Convert {
             makeLiteral(Null) :
             makeLiteral(stops.stops.at(false));
         cases.push_back(std::make_pair(std::move(input), std::move(true_case)));
-        return std::make_unique<UntypedCase>("", std::move(cases), std::move(false_case));
+        return ParseResult(std::make_unique<Case>(valueTypeToExpressionType<T>(), std::move(cases), std::move(false_case)));
     }
     
     template <typename T>
-    static std::unique_ptr<TypedExpression> toExpression(const ExponentialStops<T>& stops)
+    static std::unique_ptr<Expression> toExpression(const ExponentialStops<T>& stops)
     {
-        return makeCurve(makeZoom(), ExponentialInterpolation{stops.base}, stops.stops, {});
+        std::vector<ParsingError> errors;
+        ParseResult e = makeExponentialCurve(makeZoom(ParsingContext(errors)), stops, optional<T>());
+        assert(e);
+        return std::move(*e);
     }
     
     template <typename T>
-    static std::unique_ptr<TypedExpression> toExpression(const IntervalStops<T>& stops)
+    static std::unique_ptr<Expression> toExpression(const IntervalStops<T>& stops)
     {
-        return makeCurve(makeZoom(), StepInterpolation(), stops.stops, {});
+        std::vector<ParsingError> errors;
+        ParseResult e = makeStepCurve(makeZoom(ParsingContext(errors)), stops, optional<T>());
+        assert(e);
+        return std::move(*e);
     }
     
     template <typename T>
-    static std::unique_ptr<TypedExpression> toExpression(const std::string& property,
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
                                                   const ExponentialStops<T>& stops,
                                                   optional<T> defaultValue)
     {
-        return makeCurve(makeGet("number", property), ExponentialInterpolation{stops.base}, stops.stops, defaultValue);
+        std::vector<ParsingError> errors;
+        ParseResult e = makeExponentialCurve(makeGet("number", property, ParsingContext(errors)), stops, defaultValue);
+        assert(e);
+        return std::move(*e);
     }
     
     template <typename T>
-    static std::unique_ptr<TypedExpression> toExpression(const std::string& property,
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
                                                   const IntervalStops<T>& stops,
                                                   optional<T> defaultValue)
     {
-        return makeCurve(makeGet("number", property), StepInterpolation(), stops.stops, defaultValue);
+        std::vector<ParsingError> errors;
+        ParseResult e = makeStepCurve(makeGet("number", property, ParsingContext(errors)), stops, defaultValue);
+        assert(e);
+        return std::move(*e);
     }
     
     template <typename T>
-    static std::unique_ptr<TypedExpression> toExpression(const std::string& property,
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
                                                   const CategoricalStops<T>& stops,
                                                   optional<T> defaultValue)
     {
         assert(stops.stops.size() > 0);
 
+        std::vector<ParsingError> errors;
+
         const auto& firstKey = stops.stops.begin()->first;
-        auto expr = firstKey.match(
+        ParseResult expr = firstKey.match(
             [&](bool) {
-                auto input = makeGet("boolean", property);
+                auto input = makeGet("boolean", property, ParsingContext(errors));
                 return makeCase(std::move(input), stops);
             },
             [&](const std::string&) {
-                auto input = makeGet("string", property);
+                auto input = makeGet("string", property, ParsingContext(errors));
                 return makeMatch<std::string>(std::move(input), stops);
             },
             [&](int64_t) {
-                auto input = makeGet("number", property);
+                auto input = makeGet("number", property, ParsingContext(errors));
                 return makeMatch<int64_t>(std::move(input), stops);
             }
 
         );
         
-        std::vector<CompileError> errors;
-        auto checked = makeCoalesceToDefault(std::move(expr), defaultValue)->typecheck(errors);
-        assert(checked);
-        return std::move(*checked);
+        assert(expr);
+        
+        ParseResult e = makeCoalesceToDefault(std::move(*expr), defaultValue);
+        assert(e);
+        return std::move(*e);
     }
     
     template <typename T>
-    static std::unique_ptr<TypedExpression> toExpression(const std::string& property,
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
                                                   const IdentityStops<T>&,
                                                   optional<T> defaultValue)
     {
-        auto input = valueTypeToExpressionType<T>().match(
+        std::vector<ParsingError> errors;
+
+        std::unique_ptr<Expression> input = valueTypeToExpressionType<T>().match(
             [&] (const type::StringType&) {
-                return makeGet("string", property);
+                return makeGet("string", property, ParsingContext(errors));
             },
             [&] (const type::NumberType&) {
-                return makeGet("number", property);
+                return makeGet("number", property, ParsingContext(errors));
             },
             [&] (const type::BooleanType&) {
-                return makeGet("boolean", property);
+                return makeGet("boolean", property, ParsingContext(errors));
             },
             [&] (const type::Array& arr) {
-                UntypedCompoundExpression::Args getArgs;
+                std::vector<std::unique_ptr<Expression>> getArgs;
                 getArgs.push_back(makeLiteral(property));
-                auto get = std::make_unique<UntypedCompoundExpression>("", "get", std::move(getArgs));
-                return std::make_unique<UntypedArrayAssertion>("", arr.itemType, arr.N, std::move(get));
+                auto get = CompoundExpressions::create(CompoundExpressions::definitions.at("get"),
+                                                       std::move(getArgs),
+                                                       ParsingContext(errors));
+                return std::make_unique<ArrayAssertion>(arr, std::move(*get));
             },
-            [&] (const auto&) -> std::unique_ptr<UntypedExpression> {
+            [&] (const auto&) -> std::unique_ptr<Expression> {
                 return makeLiteral(Null);
             }
         );
         
-        std::vector<CompileError> errors;
-        auto checked = makeCoalesceToDefault(std::move(input), defaultValue)->typecheck(errors);
-        assert(checked);
-        return std::move(*checked);
+        ParseResult e = makeCoalesceToDefault(std::move(input), defaultValue);
+        assert(e);
+        return std::move(*e);
     }
 };
 
diff --git a/include/mbgl/style/function/source_function.hpp b/include/mbgl/style/function/source_function.hpp
index a25fda0a91..0ae8357d7b 100644
--- a/include/mbgl/style/function/source_function.hpp
+++ b/include/mbgl/style/function/source_function.hpp
@@ -61,7 +61,7 @@ public:
     optional<T> defaultValue;
 
 private:
-    std::shared_ptr<expression::TypedExpression> expression;
+    std::shared_ptr<expression::Expression> expression;
 };
 
 } // namespace style
diff --git a/include/mbgl/util/interpolate.hpp b/include/mbgl/util/interpolate.hpp
index 6738987598..4853385ad5 100644
--- a/include/mbgl/util/interpolate.hpp
+++ b/include/mbgl/util/interpolate.hpp
@@ -47,6 +47,22 @@ public:
     }
 };
 
+// Only safe if vectors are guaranteed at runtime to be the same length.
+template<>
+struct Interpolator<std::vector<float>> {
+    std::vector<float> operator()(const std::vector<float>& a,
+                                  const std::vector<float>& b,
+                                  const double t) const {
+        assert(a.size() == b.size());
+        if (a.size() == 0) return {};
+        std::vector<float> result;
+        for (std::size_t i = 0; i < a.size(); i++) {
+            result.push_back(interpolate(a[i], b[i], t));
+        }
+        return result;
+    }
+};
+
 template <>
 struct Interpolator<style::Position> {
 public:
@@ -101,5 +117,7 @@ struct Interpolatable
       std::true_type,
       std::false_type> {};
 
+
+
 } // namespace util
 } // namespace mbgl
diff --git a/platform/node/src/node_expression.cpp b/platform/node/src/node_expression.cpp
index d5c0865b1f..c72fc26702 100644
--- a/platform/node/src/node_expression.cpp
+++ b/platform/node/src/node_expression.cpp
@@ -29,32 +29,59 @@ void NodeExpression::Init(v8::Local<v8::Object> target) {
     Nan::Set(target, Nan::New("Expression").ToLocalChecked(), tpl->GetFunction());
 }
 
+type::Type parseType(v8::Local<v8::Object> type) {
+    static std::unordered_map<std::string, type::Type> types = {
+        {"String", type::String},
+        {"Number", type::Number},
+        {"Boolean", type::Boolean},
+        {"Object", type::Object},
+        {"Color", type::Color},
+        {"Value", type::Value}
+    };
+    
+    v8::Local<v8::Value> v8kind = Nan::Get(type, Nan::New("kind").ToLocalChecked()).ToLocalChecked();
+    std::string kind(*v8::String::Utf8Value(v8kind));
+    
+    if (kind == "Array") {
+        type::Type itemType = parseType(Nan::Get(type, Nan::New("itemType").ToLocalChecked()).ToLocalChecked()->ToObject());
+        mbgl::optional<std::size_t> N;
+        
+        v8::Local<v8::String> Nkey = Nan::New("N").ToLocalChecked();
+        if (Nan::Has(type, Nkey).FromMaybe(false)) {
+            N = Nan::Get(type, Nkey).ToLocalChecked()->ToInt32()->Value();
+        }
+        return type::Array(itemType, N);
+    }
+    
+    return types.at(kind);
+}
+
 void NodeExpression::Parse(const Nan::FunctionCallbackInfo<v8::Value>& info) {
     v8::Local<v8::Function> cons = Nan::New(constructor);
     
     if (info.Length() < 1 || info[0]->IsUndefined()) {
         return Nan::ThrowTypeError("Requires a JSON style expression argument.");
     }
+    
+    mbgl::optional<type::Type> expected;
+    if (info.Length() > 1 && info[1]->IsObject()) {
+        expected = parseType(info[1]->ToObject());
+    }
 
     auto expr = info[0];
 
     try {
-        std::vector<CompileError> errors;
-        auto parsed = parseExpression(expr, ParsingContext());
-        if (parsed.template is<std::unique_ptr<UntypedExpression>>()) {
-            const auto& e = parsed.template get<std::unique_ptr<UntypedExpression>>();
-            auto checked = e->typecheck(errors);
-            if (checked) {
-                auto nodeExpr = new NodeExpression(std::move(*checked));
-                const int argc = 0;
-                v8::Local<v8::Value> argv[0] = {};
-                auto wrapped = Nan::NewInstance(cons, argc, argv).ToLocalChecked();
-                nodeExpr->Wrap(wrapped);
-                info.GetReturnValue().Set(wrapped);
-                return;
-            }
-        } else {
-            errors.emplace_back(parsed.template get<CompileError>());
+        std::vector<ParsingError> errors;
+        ParseResult parsed = parseExpression(expr, ParsingContext(errors, expected));
+        if (parsed) {
+            assert(errors.size() == 0);
+            auto nodeExpr = new NodeExpression(std::move(*parsed));
+            const int argc = 0;
+            v8::Local<v8::Value> argv[0] = {};
+            auto wrapped = Nan::NewInstance(cons, argc, argv).ToLocalChecked();
+            nodeExpr->Wrap(wrapped);
+            info.GetReturnValue().Set(wrapped);
+            return;
         }
         
         v8::Local<v8::Array> result = Nan::New<v8::Array>();
diff --git a/platform/node/src/node_expression.hpp b/platform/node/src/node_expression.hpp
index 9bedc9421b..e977b58288 100644
--- a/platform/node/src/node_expression.hpp
+++ b/platform/node/src/node_expression.hpp
@@ -22,7 +22,7 @@ public:
     static void Init(v8::Local<v8::Object>);
 
 private:
-    NodeExpression(std::unique_ptr<TypedExpression> expression_) :
+    NodeExpression(std::unique_ptr<Expression> expression_) :
         expression(std::move(expression_))
     {};
 
@@ -34,7 +34,7 @@ private:
     static void IsZoomConstant(const Nan::FunctionCallbackInfo<v8::Value>&);
     static Nan::Persistent<v8::Function> constructor;
 
-    std::unique_ptr<TypedExpression> expression;
+    std::unique_ptr<Expression> expression;
 };
 
 } // namespace node_mbgl
diff --git a/platform/node/test/expression.test.js b/platform/node/test/expression.test.js
index 842faa7350..5ee1e75d86 100644
--- a/platform/node/test/expression.test.js
+++ b/platform/node/test/expression.test.js
@@ -10,43 +10,43 @@ if (process.argv[1] === __filename && process.argv.length > 2) {
 }
 
 suite.run('native', {tests: tests}, (fixture) => {
-    const compileResult = {};
-    const testResult = {
-        compileResult
+    const compiled = {};
+    const result = {
+        compiled
     };
 
-    const expression = mbgl.Expression.parse(fixture.expression);
+    const expression = mbgl.Expression.parse(fixture.expression, fixture.expectExpressionType);
 
     if (expression instanceof mbgl.Expression) {
-        compileResult.result = 'success';
-        compileResult.isFeatureConstant = expression.isFeatureConstant();
-        compileResult.isZoomConstant = expression.isZoomConstant();
-        compileResult.type = expression.getType();
-        if (fixture.evaluate) {
-            const evaluateResults = [];
-            for (const input of fixture.evaluate) {
-                const zoom = typeof input[0].zoom === 'number' ?
-                    input[0].zoom : -1;
-
-                const feature = Object.assign({
-                    type: 'Feature',
-                    properties: {},
-                    geometry: { type: 'Point', coordinates: [0, 0] }
-                }, input[1])
-
-                const output = expression.evaluate(zoom, feature);
-                evaluateResults.push(output);
-            }
-
-            if (evaluateResults.length) {
-                testResult.evaluateResults = evaluateResults;
-            }
+        compiled.result = 'success';
+        compiled.isFeatureConstant = expression.isFeatureConstant();
+        compiled.isZoomConstant = expression.isZoomConstant();
+        compiled.type = expression.getType();
+
+        const evaluate = fixture.inputs || [];
+        const evaluateResults = [];
+        for (const input of evaluate) {
+            const zoom = typeof input[0].zoom === 'number' ?
+                input[0].zoom : -1;
+
+            const feature = Object.assign({
+                type: 'Feature',
+                properties: {},
+                geometry: { type: 'Point', coordinates: [0, 0] }
+            }, input[1])
+
+            const output = expression.evaluate(zoom, feature);
+            evaluateResults.push(output);
+        }
+
+        if (fixture.inputs) {
+            result.outputs = evaluateResults;
         }
     } else {
-        compileResult.result = 'error';
-        compileResult.errors = expression;
+        compiled.result = 'error';
+        compiled.errors = expression;
     }
 
-    return testResult;
+    return result;
 });
 
diff --git a/src/mbgl/style/expression/check_subtype.cpp b/src/mbgl/style/expression/check_subtype.cpp
new file mode 100644
index 0000000000..9a70bdde9e
--- /dev/null
+++ b/src/mbgl/style/expression/check_subtype.cpp
@@ -0,0 +1,61 @@
+#include <mbgl/style/expression/check_subtype.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+namespace type {
+
+std::string errorMessage(const Type& expected, const Type& t) {
+    return {"Expected " + toString(expected) + " but found " + toString(t) + " instead."};
+}
+
+optional<std::string> checkSubtype(const Type& expected, const Type& t, optional<ParsingContext> context) {
+    if (t.is<NullType>()) return {};
+    
+    optional<std::string> result = expected.match(
+        [&] (const Array& expectedArray) -> optional<std::string> {
+            if (!t.is<Array>()) { return {errorMessage(expected, t)}; }
+            const auto& actualArray = t.get<Array>();
+            const auto err = checkSubtype(expectedArray.itemType, actualArray.itemType);
+            if (err) return { errorMessage(expected, t) };
+            if (expectedArray.N && expectedArray.N != actualArray.N) return { errorMessage(expected, t) };
+            return {};
+        },
+        [&] (const ValueType&) -> optional<std::string> {
+            if (t.is<ValueType>()) return {};
+            
+            const Type members[] = {
+                Null,
+                Boolean,
+                Number,
+                String,
+                Object,
+                Array(Value)
+            };
+            
+            for (const auto& member : members) {
+                const auto err = checkSubtype(member, t);
+                if (!err) {
+                    return {};
+                }
+            }
+            return { errorMessage(expected, t) };
+        },
+        [&] (const auto&) -> optional<std::string> {
+            if (expected != t) {
+                return { errorMessage(expected, t) };
+            }
+            return {};
+        }
+    );
+    
+    if (result && context) {
+        context->error(*result);
+    }
+    return result;
+}
+
+} // namespace type
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/compound_expression.cpp b/src/mbgl/style/expression/compound_expression.cpp
index 8a15da644c..e235c3007d 100644
--- a/src/mbgl/style/expression/compound_expression.cpp
+++ b/src/mbgl/style/expression/compound_expression.cpp
@@ -15,25 +15,25 @@ namespace detail {
 } // namespace detail
 
 template <class R, class... Params>
-std::unique_ptr<TypedExpression> Signature<R (const EvaluationParameters&, Params...)>::makeTypedExpression(std::vector<std::unique_ptr<TypedExpression>> args) const {
+std::unique_ptr<Expression> Signature<R (const EvaluationParameters&, Params...)>::makeExpression(std::vector<std::unique_ptr<Expression>> args) const {
     typename Signature::Args argsArray;
     std::copy_n(std::make_move_iterator(args.begin()), sizeof...(Params), argsArray.begin());
-    return std::make_unique<TypedCompoundExpression<Signature>>(*this, std::move(argsArray));
+    return std::make_unique<CompoundExpression<Signature>>(*this, std::move(argsArray));
 };
 
 template <typename R, typename T>
-std::unique_ptr<TypedExpression> Signature<R (const Varargs<T>&)>::makeTypedExpression(std::vector<std::unique_ptr<TypedExpression>> args) const {
-    return std::make_unique<TypedCompoundExpression<Signature>>(*this, std::move(args));
+std::unique_ptr<Expression> Signature<R (const Varargs<T>&)>::makeExpression(std::vector<std::unique_ptr<Expression>> args) const {
+    return std::make_unique<CompoundExpression<Signature>>(*this, std::move(args));
 };
 
 template <class R, class... Params>
-std::unique_ptr<TypedExpression> Signature<R (Params...)>::makeTypedExpression(std::vector<std::unique_ptr<TypedExpression>> args) const {
+std::unique_ptr<Expression> Signature<R (Params...)>::makeExpression(std::vector<std::unique_ptr<Expression>> args) const {
     typename Signature::Args argsArray;
     std::copy_n(std::make_move_iterator(args.begin()), sizeof...(Params), argsArray.begin());
-    return std::make_unique<TypedCompoundExpression<Signature>>(*this, std::move(argsArray));
+    return std::make_unique<CompoundExpression<Signature>>(*this, std::move(argsArray));
 };
 
-using Definition = CompoundExpression::Definition;
+using Definition = CompoundExpressions::Definition;
 
 // Helper for creating expression Definigion from one or more lambdas
 template <typename ...Evals, typename std::enable_if_t<sizeof...(Evals) != 0, int> = 0>
@@ -180,13 +180,13 @@ Result<mbgl::Color> rgba(float r, float g, float b, float a) {
 }
 
 template <typename ...Entries>
-std::unordered_map<std::string, CompoundExpression::Definition> initializeDefinitions(Entries... entries) {
-    std::unordered_map<std::string, CompoundExpression::Definition> definitions;
+std::unordered_map<std::string, CompoundExpressions::Definition> initializeDefinitions(Entries... entries) {
+    std::unordered_map<std::string, CompoundExpressions::Definition> definitions;
     expand_pack(definitions.insert(std::move(entries)));
     return definitions;
 }
 
-std::unordered_map<std::string, CompoundExpression::Definition> CompoundExpression::definitions = initializeDefinitions(
+std::unordered_map<std::string, Definition> CompoundExpressions::definitions = initializeDefinitions(
     define("e", []() -> Result<float> { return 2.718281828459045f; }),
     define("pi", []() -> Result<float> { return 3.141592653589793f; }),
     define("ln2", []() -> Result<float> { return 0.6931471805599453; }),
@@ -311,7 +311,30 @@ std::unordered_map<std::string, CompoundExpression::Definition> CompoundExpressi
         }
         return sum;
     }),
-    define("-", [](float a, float b) -> Result<float> { return a - b; })
+    define("-", [](float a, float b) -> Result<float> { return a - b; }),
+    define("*", [](const Varargs<float>& args) -> Result<float> {
+        float prod = 1.0f;
+        for (auto arg : args) {
+            prod *= arg;
+        }
+        return prod;
+    }),
+    define("/", [](float a, float b) -> Result<float> { return a / b; }),
+    
+    define("&&", [](const Varargs<bool>& args) -> Result<bool> {
+        bool result = true;
+        for (auto arg : args) result = result && arg;
+        return result;
+    }),
+    
+    define("||", [](const Varargs<bool>& args) -> Result<bool> {
+        bool result = false;
+        for (auto arg : args) result = result || arg;
+        return result;
+    }),
+    
+    define("!", [](bool e) -> Result<bool> { return !e; })
+    
 );
 
 } // namespace expression
diff --git a/src/mbgl/style/expression/match.cpp b/src/mbgl/style/expression/match.cpp
index 9286e96d50..933977b0a7 100644
--- a/src/mbgl/style/expression/match.cpp
+++ b/src/mbgl/style/expression/match.cpp
@@ -4,28 +4,35 @@ namespace mbgl {
 namespace style {
 namespace expression {
 
-template<> Result<std::string> TypedMatch<std::string>::evaluateInput(const EvaluationParameters& params) const {
-    const auto& inputValue = input->evaluate<std::string>(params);
+template<> EvaluationResult Match<std::string>::evaluate(const EvaluationParameters& params) const {
+    const Result<std::string>& inputValue = input->evaluate<std::string>(params);
     if (!inputValue) {
         return inputValue.error();
     }
-    return *inputValue;
+
+    auto it = cases.find(*inputValue);
+    if (it != cases.end()) {
+        return (*it).second->evaluate(params);
+    }
+
+    return otherwise->evaluate(params);
 }
 
-template<> Result<int64_t> TypedMatch<int64_t>::evaluateInput(const EvaluationParameters& params) const {
+template<> EvaluationResult Match<int64_t>::evaluate(const EvaluationParameters& params) const {
     const auto& inputValue = input->evaluate<float>(params);
     if (!inputValue) {
         return inputValue.error();
     }
+    
     int64_t rounded = ceilf(*inputValue);
     if (*inputValue == rounded) {
-        return rounded;
-    } else {
-        return EvaluationError {
-            "Input to \"match\" must be an integer value; found " +
-            std::to_string(*inputValue) + " instead ."
-        };
+        auto it = cases.find(rounded);
+        if (it != cases.end()) {
+            return (*it).second->evaluate(params);
+        }
     }
+    
+    return otherwise->evaluate(params);
 }
 
 } // namespace expression
diff --git a/src/mbgl/style/expression/type.cpp b/src/mbgl/style/expression/type.cpp
deleted file mode 100644
index 2e4a6eb3f5..0000000000
--- a/src/mbgl/style/expression/type.cpp
+++ /dev/null
@@ -1,120 +0,0 @@
-#include <mbgl/style/expression/type.hpp>
-
-namespace mbgl {
-namespace style {
-namespace expression {
-namespace type {
-
-bool isGeneric(const Type& t) {
-    return t.match(
-        [&](const Array& arr) { return isGeneric(arr.itemType); },
-        [&](const Typename&) { return true; },
-        [&](const auto&) { return false; }
-    );
-}
-
-Type resolveTypenamesIfPossible(const Type& t, const std::unordered_map<std::string, Type>& map) {
-    if (!isGeneric(t)) return t;
-    return t.match(
-        [&](const Typename& t) -> Type {
-            if (map.find(t.getName()) == map.end()) {
-                return t;
-            } else {
-                return map.at(t.getName());
-            }
-        },
-        [&](const Array& arr) {
-            return Array(resolveTypenamesIfPossible(arr.itemType, map), arr.N);
-        },
-        [&](const auto&) { return t; }
-    );
-}
-
-inline std::string errorMessage(const Type& expected, const Type& t) {
-    return {"Expected " + toString(expected) + " but found " + toString(t) + " instead."};
-}
-
-optional<std::string> matchType(const Type& expected, const Type& t) {
-    // TODO this is wasteful; just make typenames param optional.
-    std::unordered_map<std::string, Type> typenames;
-    return matchType(expected, t, typenames);
-}
-
-optional<std::string> matchType(const Type& expected,
-                                const Type& t,
-                                std::unordered_map<std::string, Type>& typenames,
-                                TypenameScope scope) {
-    if (expected.is<Typename>()) {
-        const auto& name = expected.get<Typename>().getName();
-        if (
-            scope == TypenameScope::expected &&
-            !isGeneric(t) &&
-            !t.is<NullType>() &&
-            typenames.find(name) == typenames.end()
-        ) {
-            typenames.emplace(name, t);
-        }
-        return {};
-    }
-    
-    if (t.is<Typename>()) {
-        const auto& name = t.get<Typename>().getName();
-        if (
-            scope == TypenameScope::actual &&
-            !isGeneric(expected) &&
-            !expected.is<NullType>() &&
-            typenames.find(name) == typenames.end()
-        ) {
-            typenames.emplace(name, expected);
-        }
-        return {};
-    }
-    
-    if (t.is<NullType>()) return {};
-    
-    return expected.match(
-        [&] (const Array& expectedArray) -> optional<std::string> {
-            if (!t.is<Array>()) { return {errorMessage(expected, t)}; }
-            const auto& tArr = t.get<Array>();
-            const auto err = matchType(expectedArray.itemType, tArr.itemType, typenames);
-            if (err) return { errorMessage(expected, t) + " (" + (*err) + ")" };
-            if (expectedArray.N && expectedArray.N != tArr.N) return { errorMessage(expected, t) };
-            return {};
-        },
-        [&] (const ValueType&) -> optional<std::string> {
-            if (t.is<ValueType>()) return {};
-            
-            const Type members[] = {
-                Null,
-                Boolean,
-                Number,
-                String,
-                Object,
-                Array(Value)
-            };
-            
-            for (const auto& member : members) {
-                std::unordered_map<std::string, Type> memberTypenames;
-                const auto err = matchType(member, t, memberTypenames, scope);
-                if (!err) {
-                    typenames.insert(memberTypenames.begin(), memberTypenames.end());
-                    return {};
-                }
-            }
-            return { errorMessage(expected, t) };
-        },
-        [&] (const auto&) -> optional<std::string> {
-            // TODO silly to stringify for this; implement == / != operators instead.
-            if (toString(expected) != toString(t)) {
-                return { errorMessage(expected, t) };
-            }
-            return {};
-        }
-    );
-}
-
-
-} // namespace type
-} // namespace expression
-} // namespace style
-} // namespace mbgl
diff --git a/src/mbgl/style/expression/value.cpp b/src/mbgl/style/expression/value.cpp
index 7c30c457d8..f1cf685e91 100644
--- a/src/mbgl/style/expression/value.cpp
+++ b/src/mbgl/style/expression/value.cpp
@@ -143,7 +143,7 @@ struct Converter<std::array<T, N>> {
 template <typename T>
 struct Converter<std::vector<T>> {
     static Value toExpressionValue(const std::vector<T>& value) {
-        std::vector<Value> v;
+        std::vector<Value> v(value.size());
         std::copy(value.begin(), value.end(), v.begin());
         return v;
     }
diff --git a/src/mbgl/style/function/expression.cpp b/src/mbgl/style/function/expression.cpp
index 4fef6e45d9..841c1a6190 100644
--- a/src/mbgl/style/function/expression.cpp
+++ b/src/mbgl/style/function/expression.cpp
@@ -27,7 +27,7 @@ public:
 };
 
 
-EvaluationResult TypedExpression::evaluate(float z, const Feature& feature) const {
+EvaluationResult Expression::evaluate(float z, const Feature& feature) const {
     GeoJSONFeature f(feature);
     return this->evaluate(EvaluationParameters {z, &f});
 }