Implement Expressions (#9439)

Ports https://github.com/mapbox/mapbox-gl-js/pull/4777 (and its several follow-ups)

26 files changed, 2897 insertions, 46 deletions

diff --git a/src/mbgl/programs/symbol_program.hpp b/src/mbgl/programs/symbol_program.hpp
index a7abf94f56..5065b364f7 100644
--- a/src/mbgl/programs/symbol_program.hpp
+++ b/src/mbgl/programs/symbol_program.hpp
@@ -128,23 +128,6 @@ public:
     }
 };
 
-// Return the smallest range of stops that covers the interval [lowerZoom, upperZoom]
-template <class Stops>
-Range<float> getCoveringStops(Stops s, float lowerZoom, float upperZoom) {
-    assert(!s.stops.empty());
-    auto minIt = s.stops.lower_bound(lowerZoom);
-    auto maxIt = s.stops.lower_bound(upperZoom);
-    
-    // lower_bound yields first element >= lowerZoom, but we want the *last*
-    // element <= lowerZoom, so if we found a stop > lowerZoom, back up by one.
-    if (minIt != s.stops.begin() && minIt != s.stops.end() && minIt->first > lowerZoom) {
-        minIt--;
-    }
-    return Range<float> {
-        minIt == s.stops.end() ? s.stops.rbegin()->first : minIt->first,
-        maxIt == s.stops.end() ? s.stops.rbegin()->first : maxIt->first
-    };
-}
 
 class ConstantSymbolSizeBinder final : public SymbolSizeBinder {
 public:
@@ -155,19 +138,12 @@ public:
       : layoutSize(defaultValue) {}
     
     ConstantSymbolSizeBinder(const float tileZoom, const style::CameraFunction<float>& function_, const float /*defaultValue*/)
-      : layoutSize(function_.evaluate(tileZoom + 1)) {
-        function_.stops.match(
-            [&] (const style::ExponentialStops<float>& stops) {
-                const auto& zoomLevels = getCoveringStops(stops, tileZoom, tileZoom + 1);
-                coveringRanges = std::make_tuple(
-                    zoomLevels,
-                    Range<float> { function_.evaluate(zoomLevels.min), function_.evaluate(zoomLevels.max) }
-                );
-                functionInterpolationBase = stops.base;
-            },
-            [&] (const style::IntervalStops<float>&) {
-                function = function_;
-            }
+      : layoutSize(function_.evaluate(tileZoom + 1)),
+        function(function_) {
+        const Range<float> zoomLevels = function_.getCoveringStops(tileZoom, tileZoom + 1);
+        coveringRanges = std::make_tuple(
+            zoomLevels,
+            Range<float> { function_.evaluate(zoomLevels.min), function_.evaluate(zoomLevels.max) }
         );
     }
     
@@ -185,7 +161,7 @@ public:
             const Range<float>& zoomLevels = std::get<0>(*coveringRanges);
             const Range<float>& sizeLevels = std::get<1>(*coveringRanges);
             float t = util::clamp(
-                util::interpolationFactor(*functionInterpolationBase, zoomLevels, currentZoom),
+                function->interpolationFactor(zoomLevels, currentZoom),
                 0.0f, 1.0f
             );
             size = sizeLevels.min + t * (sizeLevels.max - sizeLevels.min);
@@ -198,10 +174,7 @@ public:
     }
     
     float layoutSize;
-    // used for exponential functions
     optional<std::tuple<Range<float>, Range<float>>> coveringRanges;
-    optional<float> functionInterpolationBase;
-    // used for interval functions
     optional<style::CameraFunction<float>> function;
 };
 
@@ -226,7 +199,7 @@ public:
         return { true, false, unused, unused, unused };
     }
     
-    const style::SourceFunction<float>& function;
+    style::SourceFunction<float> function;
     const float defaultValue;
 };
 
@@ -237,9 +210,7 @@ public:
         : function(function_),
           defaultValue(defaultValue_),
           layoutZoom(tileZoom + 1),
-          coveringZoomStops(function.stops.match(
-            [&] (const auto& stops) {
-            return getCoveringStops(stops, tileZoom, tileZoom + 1); }))
+          coveringZoomStops(function.getCoveringStops(tileZoom, tileZoom + 1))
     {}
 
     Range<float> getVertexSizeData(const GeometryTileFeature& feature) override {
@@ -251,7 +222,7 @@ public:
     
     ZoomEvaluatedSize evaluateForZoom(float currentZoom) const override {
         float sizeInterpolationT = util::clamp(
-            util::interpolationFactor(1.0f, coveringZoomStops, currentZoom),
+            function.interpolationFactor(coveringZoomStops, currentZoom),
             0.0f, 1.0f
         );
 
@@ -259,7 +230,7 @@ public:
         return { false, false, sizeInterpolationT, unused, unused };
     }
     
-    const style::CompositeFunction<float>& function;
+    style::CompositeFunction<float> function;
     const float defaultValue;
     float layoutZoom;
     Range<float> coveringZoomStops;
diff --git a/src/mbgl/renderer/paint_property_binder.hpp b/src/mbgl/renderer/paint_property_binder.hpp
index 652948c8df..3a49882f12 100644
--- a/src/mbgl/renderer/paint_property_binder.hpp
+++ b/src/mbgl/renderer/paint_property_binder.hpp
@@ -190,11 +190,11 @@ public:
     CompositeFunctionPaintPropertyBinder(style::CompositeFunction<T> function_, float zoom, T defaultValue_)
         : function(std::move(function_)),
           defaultValue(std::move(defaultValue_)),
-          rangeOfCoveringRanges(function.rangeOfCoveringRanges({zoom, zoom + 1})) {
+          zoomRange({zoom, zoom + 1}) {
     }
 
     void populateVertexVector(const GeometryTileFeature& feature, std::size_t length) override {
-        Range<T> range = function.evaluate(rangeOfCoveringRanges, feature, defaultValue);
+        Range<T> range = function.evaluate(zoomRange, feature, defaultValue);
         this->statistics.add(range.min);
         this->statistics.add(range.max);
         AttributeValue value = zoomInterpolatedAttributeValue(
@@ -219,9 +219,9 @@ public:
 
     float interpolationFactor(float currentZoom) const override {
         if (function.useIntegerZoom) {
-            return util::interpolationFactor(1.0f, { rangeOfCoveringRanges.min.zoom, rangeOfCoveringRanges.max.zoom }, std::floor(currentZoom));
+            return function.interpolationFactor(zoomRange, std::floor(currentZoom));
         } else {
-            return util::interpolationFactor(1.0f, { rangeOfCoveringRanges.min.zoom, rangeOfCoveringRanges.max.zoom }, currentZoom);
+            return function.interpolationFactor(zoomRange, currentZoom);
         }
     }
 
@@ -237,8 +237,7 @@ public:
 private:
     style::CompositeFunction<T> function;
     T defaultValue;
-    using CoveringRanges = typename style::CompositeFunction<T>::CoveringRanges;
-    Range<CoveringRanges> rangeOfCoveringRanges;
+    Range<float> zoomRange;
     gl::VertexVector<Vertex> vertexVector;
     optional<gl::VertexBuffer<Vertex>> vertexBuffer;
 };
diff --git a/src/mbgl/style/conversion/get_json_type.cpp b/src/mbgl/style/conversion/get_json_type.cpp
new file mode 100644
index 0000000000..cd3b4608b1
--- /dev/null
+++ b/src/mbgl/style/conversion/get_json_type.cpp
@@ -0,0 +1,34 @@
+#include <mbgl/style/conversion/get_json_type.hpp>
+#include <mbgl/util/feature.hpp>
+
+namespace mbgl {
+namespace style {
+namespace conversion {
+
+std::string getJSONType(const Convertible& value) {
+    if (isUndefined(value)) {
+        return "null";
+    }
+    if (isArray(value)) {
+        return "array";
+    }
+    if (isObject(value)) {
+        return "object";
+    }
+    optional<mbgl::Value> v = toValue(value);
+
+    // Since we've already checked the non-atomic types above, value must then
+    // be a string, number, or boolean -- thus, assume that the toValue()
+    // conversion succeeds.
+    assert(v);
+
+    return v->match(
+        [&] (const std::string&) { return "string"; },
+        [&] (bool) { return "boolean"; },
+        [&] (auto) { return "number"; }
+    );
+}
+
+} // namespace conversion
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/array_assertion.cpp b/src/mbgl/style/expression/array_assertion.cpp
new file mode 100644
index 0000000000..a62f67fbb5
--- /dev/null
+++ b/src/mbgl/style/expression/array_assertion.cpp
@@ -0,0 +1,85 @@
+#include <mbgl/style/expression/array_assertion.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult ArrayAssertion::evaluate(const EvaluationContext& params) const {
+    auto result = input->evaluate(params);
+    if (!result) {
+        return result.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;
+}
+
+void ArrayAssertion::eachChild(const std::function<void(const Expression&)>& visit) const {
+    visit(*input);
+}
+
+using namespace mbgl::style::conversion;
+ParseResult ArrayAssertion::parse(const Convertible& value, ParsingContext& ctx) {
+
+    static std::unordered_map<std::string, type::Type> itemTypes {
+        {"string", type::String},
+        {"number", type::Number},
+        {"boolean", type::Boolean}
+    };
+
+    auto length = arrayLength(value);
+    if (length < 2 || length > 4) {
+        ctx.error("Expected 1, 2, or 3 arguments, but found " + std::to_string(length - 1) + " instead.");
+        return ParseResult();
+    }
+
+    optional<type::Type> itemType;
+    optional<std::size_t> N;
+    if (length > 2) {
+        optional<std::string> itemTypeName = toString(arrayMember(value, 1));
+        auto it = itemTypeName ? itemTypes.find(*itemTypeName) : itemTypes.end();
+        if (it == itemTypes.end()) {
+            ctx.error(
+                R"(The item type argument of "array" must be one of string, number, boolean)",
+                1
+            );
+            return ParseResult();
+        }
+        itemType = it->second;
+    } else {
+        itemType = {type::Value};
+    }
+
+    if (length > 3) {
+        auto n = toNumber(arrayMember(value, 2));
+        if (!n || *n != std::floor(*n)) {
+            ctx.error(
+                R"(The length argument to "array" must be a positive integer literal.)",
+                2
+            );
+            return ParseResult();
+        }
+        N = optional<std::size_t>(*n);
+    }
+
+    auto input = ctx.parse(arrayMember(value, length - 1), length - 1, {type::Value});
+    if (!input) {
+        return input;
+    }
+
+    return ParseResult(std::make_unique<ArrayAssertion>(
+        type::Array(*itemType, N),
+        std::move(*input)
+    ));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/assertion.cpp b/src/mbgl/style/expression/assertion.cpp
new file mode 100644
index 0000000000..a17c53cf54
--- /dev/null
+++ b/src/mbgl/style/expression/assertion.cpp
@@ -0,0 +1,73 @@
+#include <mbgl/style/expression/assertion.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+using namespace mbgl::style::conversion;
+ParseResult Assertion::parse(const Convertible& value, ParsingContext& ctx) {
+    static std::unordered_map<std::string, type::Type> types {
+        {"string", type::String},
+        {"number", type::Number},
+        {"boolean", type::Boolean},
+        {"object", type::Object}
+    };
+
+    std::size_t length = arrayLength(value);
+
+    if (length < 2) {
+        ctx.error("Expected at least one argument.");
+        return ParseResult();
+    }
+
+    auto it = types.find(*toString(arrayMember(value, 0)));
+    assert(it != types.end());
+    
+    std::vector<std::unique_ptr<Expression>> parsed;
+    parsed.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        ParseResult input = ctx.parse(arrayMember(value, i), i, {type::Value});
+        if (!input) return ParseResult();
+        parsed.push_back(std::move(*input));
+    }
+
+    return ParseResult(std::make_unique<Assertion>(it->second, std::move(parsed)));
+}
+
+EvaluationResult Assertion::evaluate(const EvaluationContext& params) const {
+    for (std::size_t i = 0; i < inputs.size(); i++) {
+        EvaluationResult value = inputs[i]->evaluate(params);
+        if (!value) return value;
+        if (!type::checkSubtype(getType(), typeOf(*value))) {
+            return value;
+        } else if (i == inputs.size() - 1) {
+            return EvaluationError {
+                "Expected value to be of type " + toString(getType()) +
+                ", but found " + toString(typeOf(*value)) + " instead."
+            };
+        }
+    }
+
+    assert(false);
+    return EvaluationError { "Unreachable" };
+};
+
+void Assertion::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for(const std::unique_ptr<Expression>& input : inputs) {
+        visit(*input);
+    }
+};
+
+bool Assertion::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Assertion*>(&e)) {
+        return getType() == rhs->getType() && Expression::childrenEqual(inputs, rhs->inputs);
+    }
+    return false;
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
+
diff --git a/src/mbgl/style/expression/at.cpp b/src/mbgl/style/expression/at.cpp
new file mode 100644
index 0000000000..d9beb63b52
--- /dev/null
+++ b/src/mbgl/style/expression/at.cpp
@@ -0,0 +1,63 @@
+#include <mbgl/style/expression/at.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult At::evaluate(const EvaluationContext& params) const {
+    const EvaluationResult evaluatedIndex = index->evaluate(params);
+    const EvaluationResult evaluatedInput = input->evaluate(params);
+    if (!evaluatedIndex) {
+        return evaluatedIndex.error();
+    }
+    if (!evaluatedInput) {
+        return evaluatedInput.error();
+    }
+    
+    const auto i = evaluatedIndex->get<double>();
+    const auto inputArray = evaluatedInput->get<std::vector<Value>>();
+    
+    if (i < 0 || i >= inputArray.size()) {
+        return EvaluationError {
+            "Array index out of bounds: " + stringify(i) +
+            " > " + std::to_string(inputArray.size()) + "."
+        };
+    }
+    if (i != std::floor(i)) {
+        return EvaluationError {
+            "Array index must be an integer, but found " + stringify(i) + " instead."
+        };
+    }
+    return inputArray[static_cast<std::size_t>(i)];
+}
+
+void At::eachChild(const std::function<void(const Expression&)>& visit) const {
+    visit(*index);
+    visit(*input);
+}
+
+using namespace mbgl::style::conversion;
+ParseResult At::parse(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+
+    std::size_t length = arrayLength(value);
+    if (length != 3) {
+        ctx.error("Expected 2 arguments, but found " + std::to_string(length - 1) + " instead.");
+        return ParseResult();
+    }
+
+    ParseResult index = ctx.parse(arrayMember(value, 1), 1, {type::Number});
+    
+    type::Type inputType = type::Array(ctx.getExpected() ? *ctx.getExpected() : type::Value);
+    ParseResult input = ctx.parse(arrayMember(value, 2), 2, {inputType});
+
+    if (!index || !input) return ParseResult();
+
+    return ParseResult(std::make_unique<At>(std::move(*index), std::move(*input)));
+
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/boolean_operator.cpp b/src/mbgl/style/expression/boolean_operator.cpp
new file mode 100644
index 0000000000..88797f965a
--- /dev/null
+++ b/src/mbgl/style/expression/boolean_operator.cpp
@@ -0,0 +1,87 @@
+#include <mbgl/style/expression/boolean_operator.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Any::evaluate(const EvaluationContext& params) const {
+    for (auto it = inputs.begin(); it != inputs.end(); it++) {
+        const EvaluationResult result = (*it)->evaluate(params);
+        if (!result) return result;
+        if (result->get<bool>()) return EvaluationResult(true);
+    }
+    return EvaluationResult(false);
+}
+
+void Any::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (const std::unique_ptr<Expression>& input : inputs) {
+        visit(*input);
+    }
+}
+
+bool Any::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Any*>(&e)) {
+        return Expression::childrenEqual(inputs, rhs->inputs);
+    }
+    return false;
+}
+
+
+EvaluationResult All::evaluate(const EvaluationContext& params) const {
+    for (auto it = inputs.begin(); it != inputs.end(); it++) {
+        const EvaluationResult result = (*it)->evaluate(params);
+        if (!result) return result;
+        if (!result->get<bool>()) return EvaluationResult(false);
+    }
+    return EvaluationResult(true);
+}
+
+void All::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (const std::unique_ptr<Expression>& input : inputs) {
+        visit(*input);
+    }
+}
+
+bool All::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const All*>(&e)) {
+        return Expression::childrenEqual(inputs, rhs->inputs);
+    }
+    return false;
+}
+
+using namespace mbgl::style::conversion;
+
+template <class T>
+ParseResult parseBooleanOp(const Convertible& value, ParsingContext& ctx) {
+    
+    assert(isArray(value));
+    auto length = arrayLength(value);
+ 
+    std::vector<std::unique_ptr<Expression>> parsedInputs;
+    
+    parsedInputs.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        auto parsed = ctx.parse(arrayMember(value, i), i, {type::Boolean});
+        if (!parsed) {
+            return parsed;
+        }
+        
+        parsedInputs.push_back(std::move(*parsed));
+    }
+ 
+    return ParseResult(std::make_unique<T>(std::move(parsedInputs)));
+}
+
+ParseResult Any::parse(const Convertible& value, ParsingContext& ctx) {
+    return parseBooleanOp<Any>(value, ctx);
+}
+
+ParseResult All::parse(const Convertible& value, ParsingContext& ctx) {
+    return parseBooleanOp<All>(value, ctx);
+}
+
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
diff --git a/src/mbgl/style/expression/case.cpp b/src/mbgl/style/expression/case.cpp
new file mode 100644
index 0000000000..a435b71fc5
--- /dev/null
+++ b/src/mbgl/style/expression/case.cpp
@@ -0,0 +1,90 @@
+#include <mbgl/style/expression/case.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Case::evaluate(const EvaluationContext& params) const {
+    for (const auto& branch : branches) {
+        const EvaluationResult evaluatedTest = branch.first->evaluate(params);
+        if (!evaluatedTest) {
+            return evaluatedTest.error();
+        }
+        if (evaluatedTest->get<bool>()) {
+            return branch.second->evaluate(params);
+        }
+    }
+    
+    return otherwise->evaluate(params);
+}
+
+void Case::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (const Branch& branch : branches) {
+        visit(*branch.first);
+        visit(*branch.second);
+    }
+    visit(*otherwise);
+}
+
+bool Case::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Case*>(&e)) {
+        return *otherwise == *(rhs->otherwise) && Expression::childrenEqual(branches, rhs->branches);
+    }
+    return false;
+}
+
+using namespace mbgl::style::conversion;
+ParseResult Case::parse(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+    auto length = arrayLength(value);
+    if (length < 4) {
+        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) {
+        ctx.error("Expected an odd number of arguments");
+        return ParseResult();
+    }
+
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+
+    std::vector<Case::Branch> branches;
+    branches.reserve((length - 2) / 2);
+    for (size_t i = 1; i + 1 < length; i += 2) {
+        auto test = ctx.parse(arrayMember(value, i), i, {type::Boolean});
+        if (!test) {
+            return test;
+        }
+
+        auto output = ctx.parse(arrayMember(value, i + 1), i + 1, outputType);
+        if (!output) {
+            return output;
+        }
+        
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+
+        branches.push_back(std::make_pair(std::move(*test), std::move(*output)));
+    }
+
+    assert(outputType);
+
+    auto otherwise = ctx.parse(arrayMember(value, length - 1), length - 1, outputType);
+    if (!otherwise) {
+        return otherwise;
+    }
+
+    return ParseResult(std::make_unique<Case>(*outputType,
+                                  std::move(branches),
+                                  std::move(*otherwise)));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/check_subtype.cpp b/src/mbgl/style/expression/check_subtype.cpp
new file mode 100644
index 0000000000..04a1643f0c
--- /dev/null
+++ b/src/mbgl/style/expression/check_subtype.cpp
@@ -0,0 +1,60 @@
+#include <string>
+#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) {
+    if (t.is<ErrorType>()) 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,
+                Color,
+                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 {};
+        }
+    );
+    
+    return result;
+}
+
+} // namespace type
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/coalesce.cpp b/src/mbgl/style/expression/coalesce.cpp
new file mode 100644
index 0000000000..bfde3c7581
--- /dev/null
+++ b/src/mbgl/style/expression/coalesce.cpp
@@ -0,0 +1,62 @@
+#include <mbgl/style/expression/coalesce.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Coalesce::evaluate(const EvaluationContext& params) const {
+    EvaluationResult result = Null;
+    for (const auto& arg : args) {
+        result = arg->evaluate(params);
+        if (!result || *result != Null) break;
+    }
+    return result;
+}
+
+void Coalesce::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (const std::unique_ptr<Expression>& arg : args) {
+        visit(*arg);
+    }
+}
+
+bool Coalesce::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Coalesce*>(&e)) {
+        return Expression::childrenEqual(args, rhs->args);
+    }
+    return false;
+}
+
+using namespace mbgl::style::conversion;
+ParseResult Coalesce::parse(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+    auto length = arrayLength(value);
+    if (length < 2) {
+        ctx.error("Expected at least one argument.");
+        return ParseResult();
+    }
+ 
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+
+    Coalesce::Args args;
+    args.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        auto parsed = ctx.parse(arrayMember(value, i), i, outputType);
+        if (!parsed) {
+            return parsed;
+        }
+        if (!outputType) {
+            outputType = (*parsed)->getType();
+        }
+        args.push_back(std::move(*parsed));
+    }
+ 
+    assert(outputType);
+    return ParseResult(std::make_unique<Coalesce>(*outputType, std::move(args)));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/coercion.cpp b/src/mbgl/style/expression/coercion.cpp
new file mode 100644
index 0000000000..f2042ffd8f
--- /dev/null
+++ b/src/mbgl/style/expression/coercion.cpp
@@ -0,0 +1,143 @@
+#include <mbgl/style/expression/coercion.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/util.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult toNumber(const Value& v) {
+    optional<double> result = v.match(
+        [](const double f) -> optional<double> { return f; },
+        [](const std::string& s) -> optional<double> {
+            try {
+                return std::stof(s);
+            } catch(std::exception) {
+                return optional<double>();
+            }
+        },
+        [](const auto&) { return optional<double>(); }
+    );
+    if (!result) {
+        return EvaluationError {
+            "Could not convert " + stringify(v) + " to number."
+        };
+    }
+    return *result;
+}
+
+EvaluationResult toColor(const Value& colorValue) {
+    return colorValue.match(
+        [&](const std::string& colorString) -> EvaluationResult {
+            const optional<Color> result = Color::parse(colorString);
+            if (result) {
+                return *result;
+            } else {
+                return EvaluationError{
+                    "Could not parse color from value '" + colorString + "'"
+                };
+            }
+        },
+        [&](const std::vector<Value>& components) -> EvaluationResult {
+            std::size_t len = components.size();
+            bool isNumeric = std::all_of(components.begin(), components.end(), [](const Value& item) {
+                return item.template is<double>();
+            });
+            if ((len == 3 || len == 4) && isNumeric) {
+                Result<Color> c = {rgba(
+                    components[0].template get<double>(),
+                    components[1].template get<double>(),
+                    components[2].template get<double>(),
+                    len == 4 ? components[3].template get<double>() : 1.0
+                )};
+                if (!c) return c.error();
+                return *c;
+            } else {
+                return EvaluationError{
+                    "Invalid rbga value " + stringify(colorValue) + ": expected an array containing either three or four numeric values."
+                };
+            }
+        },
+        [&](const auto&) -> EvaluationResult {
+            return EvaluationError{
+                "Could not parse color from value '" + stringify(colorValue) + "'"
+            };
+        }
+    );
+}
+
+Coercion::Coercion(type::Type type_, std::vector<std::unique_ptr<Expression>> inputs_) :
+    Expression(std::move(type_)),
+    inputs(std::move(inputs_))
+{
+    type::Type t = getType();
+    if (t.is<type::NumberType>()) {
+        coerceSingleValue = toNumber;
+    } else if (t.is<type::ColorType>()) {
+        coerceSingleValue = toColor;
+    } else {
+        assert(false);
+    }
+}
+
+using namespace mbgl::style::conversion;
+ParseResult Coercion::parse(const Convertible& value, ParsingContext& ctx) {
+    static std::unordered_map<std::string, type::Type> types {
+        {"to-number", type::Number},
+        {"to-color", type::Color}
+    };
+
+    std::size_t length = arrayLength(value);
+
+    if (length < 2) {
+        ctx.error("Expected at least one argument.");
+        return ParseResult();
+    }
+
+    auto it = types.find(*toString(arrayMember(value, 0)));
+    assert(it != types.end());
+    
+    std::vector<std::unique_ptr<Expression>> parsed;
+    parsed.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        ParseResult input = ctx.parse(arrayMember(value, i), i, {type::Value});
+        if (!input) return ParseResult();
+        parsed.push_back(std::move(*input));
+    }
+
+    return ParseResult(std::make_unique<Coercion>(it->second, std::move(parsed)));
+}
+
+EvaluationResult Coercion::evaluate(const EvaluationContext& params) const {
+    for (std::size_t i = 0; i < inputs.size(); i++) {
+        EvaluationResult value = inputs[i]->evaluate(params);
+        if (!value) return value;
+        EvaluationResult coerced = coerceSingleValue(*value);
+        if (coerced || i == inputs.size() - 1) {
+            return coerced;
+        }
+    }
+
+    assert(false);
+    return EvaluationError { "Unreachable" };
+};
+
+void Coercion::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for(const std::unique_ptr<Expression>& input : inputs) {
+        visit(*input);
+    }
+};
+
+bool Coercion::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Coercion*>(&e)) {
+        return getType() == rhs->getType() && Expression::childrenEqual(inputs, rhs->inputs);
+    }
+    return false;
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
+
+
diff --git a/src/mbgl/style/expression/compound_expression.cpp b/src/mbgl/style/expression/compound_expression.cpp
new file mode 100644
index 0000000000..c1e0639562
--- /dev/null
+++ b/src/mbgl/style/expression/compound_expression.cpp
@@ -0,0 +1,571 @@
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/util.hpp>
+#include <mbgl/tile/geometry_tile_data.hpp>
+#include <mbgl/util/ignore.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+namespace detail {
+
+/*
+    The Signature<Fn> structs are wrappers around an "evaluate()" function whose
+    purpose is to extract the necessary Type data from the evaluate function's
+    type.  There are three key (partial) specializations:
+    
+    Signature<R (Params...)>:
+    Wraps a simple evaluate function (const T0&, const T1&, ...) -> Result<U>
+ 
+    Signature<R (const Varargs<T>&)>:
+    Wraps an evaluate function that takes an arbitrary number of arguments (via
+    a Varargs<T>, which is just an alias for std::vector).
+ 
+    Signature<R (const EvaluationContext&, Params...)>:
+    Wraps an evaluate function that needs to access the expression evaluation
+    parameters in addition to its subexpressions, i.e.,
+    (const EvaluationParams& const T0&, const T1&, ...) -> Result<U>.  Needed
+    for expressions like ["zoom"], ["get", key], etc.
+    
+    In each of the above evaluate signatures, T0, T1, etc. are the types of
+    the successfully evaluated subexpressions.
+*/
+template <class, class Enable = void>
+struct Signature;
+
+// Simple evaluate function (const T0&, const T1&, ...) -> Result<U>
+template <class R, class... Params>
+struct Signature<R (Params...)> : SignatureBase {
+    using Args = std::array<std::unique_ptr<Expression>, sizeof...(Params)>;
+    
+    Signature(R (*evaluate_)(Params...)) :
+        SignatureBase(
+            valueTypeToExpressionType<std::decay_t<typename R::Value>>(),
+            std::vector<type::Type> {valueTypeToExpressionType<std::decay_t<Params>>()...}
+        ),
+        evaluate(evaluate_)
+    {}
+    
+    EvaluationResult apply(const EvaluationContext& evaluationParameters, const Args& args) const {
+        return applyImpl(evaluationParameters, args, std::index_sequence_for<Params...>{});
+    }
+    
+    std::unique_ptr<Expression> makeExpression(const std::string& name,
+                                               std::vector<std::unique_ptr<Expression>> args) const override {
+        typename Signature::Args argsArray;
+        std::copy_n(std::make_move_iterator(args.begin()), sizeof...(Params), argsArray.begin());
+        return std::make_unique<CompoundExpression<Signature>>(name, *this, std::move(argsArray));
+    }
+
+    R (*evaluate)(Params...);
+private:
+    template <std::size_t ...I>
+    EvaluationResult applyImpl(const EvaluationContext& evaluationParameters, const Args& args, std::index_sequence<I...>) const {
+        const std::array<EvaluationResult, sizeof...(I)> evaluated = {{std::get<I>(args)->evaluate(evaluationParameters)...}};
+        for (const auto& arg : evaluated) {
+            if(!arg) return arg.error();
+        }
+        const R value = evaluate(*fromExpressionValue<std::decay_t<Params>>(*(evaluated[I]))...);
+        if (!value) return value.error();
+        return *value;
+    }
+};
+
+// Varargs evaluate function (const Varargs<T>&) -> Result<U>
+template <class R, typename T>
+struct Signature<R (const Varargs<T>&)> : SignatureBase {
+    using Args = std::vector<std::unique_ptr<Expression>>;
+    
+    Signature(R (*evaluate_)(const Varargs<T>&)) :
+        SignatureBase(
+            valueTypeToExpressionType<std::decay_t<typename R::Value>>(),
+            VarargsType { valueTypeToExpressionType<T>() }
+        ),
+        evaluate(evaluate_)
+    {}
+    
+    std::unique_ptr<Expression> makeExpression(const std::string& name,
+                                               std::vector<std::unique_ptr<Expression>> args) const override  {
+        return std::make_unique<CompoundExpression<Signature>>(name, *this, std::move(args));
+    };
+    
+    EvaluationResult apply(const EvaluationContext& evaluationParameters, const Args& args) const {
+        Varargs<T> evaluated;
+        evaluated.reserve(args.size());
+        for (const auto& arg : args) {
+            const EvaluationResult evaluatedArg = arg->evaluate(evaluationParameters);
+            if(!evaluatedArg) return evaluatedArg.error();
+            evaluated.push_back(*fromExpressionValue<std::decay_t<T>>(*evaluatedArg));
+        }
+        const R value = evaluate(evaluated);
+        if (!value) return value.error();
+        return *value;
+    }
+    
+    R (*evaluate)(const Varargs<T>&);
+};
+
+// Evaluate function needing parameter access,
+// (const EvaluationParams&, const T0&, const T1&, ...) -> Result<U>
+template <class R, class... Params>
+struct Signature<R (const EvaluationContext&, Params...)> : SignatureBase {
+    using Args = std::array<std::unique_ptr<Expression>, sizeof...(Params)>;
+    
+    Signature(R (*evaluate_)(const EvaluationContext&, Params...)) :
+        SignatureBase(
+            valueTypeToExpressionType<std::decay_t<typename R::Value>>(),
+            std::vector<type::Type> {valueTypeToExpressionType<std::decay_t<Params>>()...}
+        ),
+        evaluate(evaluate_)
+    {}
+    
+    std::unique_ptr<Expression> makeExpression(const std::string& name,
+                                               std::vector<std::unique_ptr<Expression>> args) const override {
+        typename Signature::Args argsArray;
+        std::copy_n(std::make_move_iterator(args.begin()), sizeof...(Params), argsArray.begin());
+        return std::make_unique<CompoundExpression<Signature>>(name, *this, std::move(argsArray));
+    }
+    
+    EvaluationResult apply(const EvaluationContext& evaluationParameters, const Args& args) const {
+        return applyImpl(evaluationParameters, args, std::index_sequence_for<Params...>{});
+    }
+    
+private:
+    template <std::size_t ...I>
+    EvaluationResult applyImpl(const EvaluationContext& evaluationParameters, const Args& args, std::index_sequence<I...>) const {
+        const std::array<EvaluationResult, sizeof...(I)> evaluated = {{std::get<I>(args)->evaluate(evaluationParameters)...}};
+        for (const auto& arg : evaluated) {
+            if(!arg) return arg.error();
+        }
+        // TODO: assert correct runtime type of each arg value
+        const R value = evaluate(evaluationParameters, *fromExpressionValue<std::decay_t<Params>>(*(evaluated[I]))...);
+        if (!value) return value.error();
+        return *value;
+    }
+    
+    R (*evaluate)(const EvaluationContext&, Params...);
+};
+
+// Machinery to pull out function types from class methods, lambdas, etc.
+template <class R, class... Params>
+struct Signature<R (*)(Params...)>
+    : Signature<R (Params...)>
+{ using Signature<R (Params...)>::Signature; };
+
+template <class T, class R, class... Params>
+struct Signature<R (T::*)(Params...) const>
+    : Signature<R (Params...)>
+{ using Signature<R (Params...)>::Signature;  };
+
+template <class T, class R, class... Params>
+struct Signature<R (T::*)(Params...)>
+    : Signature<R (Params...)>
+{ using Signature<R (Params...)>::Signature; };
+
+template <class Lambda>
+struct Signature<Lambda, std::enable_if_t<std::is_class<Lambda>::value>>
+    : Signature<decltype(&Lambda::operator())>
+{ using Signature<decltype(&Lambda::operator())>::Signature; };
+
+} // namespace detail
+
+using Definition = CompoundExpressionRegistry::Definition;
+
+template <typename T>
+Result<bool> equal(const T& lhs, const T& rhs) { return lhs == rhs; }
+
+template <typename T>
+Result<bool> notEqual(const T& lhs, const T& rhs) { return lhs != rhs; }
+
+template <typename Fn>
+static std::unique_ptr<detail::SignatureBase> makeSignature(Fn evaluateFunction) {
+    return std::make_unique<detail::Signature<Fn>>(evaluateFunction);
+}
+
+std::unordered_map<std::string, CompoundExpressionRegistry::Definition> initializeDefinitions() {
+    std::unordered_map<std::string, CompoundExpressionRegistry::Definition> definitions;
+    auto define = [&](std::string name, auto fn) {
+        definitions[name].push_back(makeSignature(fn));
+    };
+    
+    define("e", []() -> Result<double> { return 2.718281828459045; });
+    define("pi", []() -> Result<double> { return 3.141592653589793; });
+    define("ln2", []() -> Result<double> { return 0.6931471805599453; });
+
+    define("typeof", [](const Value& v) -> Result<std::string> { return toString(typeOf(v)); });
+    
+    define("to-string", [](const Value& value) -> Result<std::string> {
+        return value.match(
+            [](const Color& c) -> Result<std::string> { return c.stringify(); }, // avoid quoting
+            [](const std::string& s) -> Result<std::string> { return s; }, // avoid quoting
+            [](const auto& v) -> Result<std::string> { return stringify(v); }
+        );
+    });
+    
+    define("to-boolean", [](const Value& v) -> Result<bool> {
+        return v.match(
+            [&] (double f) { return (bool)f; },
+            [&] (const std::string& s) { return s.length() > 0; },
+            [&] (bool b) { return b; },
+            [&] (const NullValue&) { return false; },
+            [&] (const auto&) { return true; }
+        );
+    });
+    define("to-rgba", [](const Color& color) -> Result<std::array<double, 4>> {
+        return std::array<double, 4> {{ color.r, color.g, color.b, color.a }};
+    });
+    
+    define("rgba", rgba);
+    define("rgb", [](double r, double g, double b) { return rgba(r, g, b, 1.0f); });
+    
+    define("zoom", [](const EvaluationContext& params) -> Result<double> {
+        if (!params.zoom) {
+            return EvaluationError {
+                "The 'zoom' expression is unavailable in the current evaluation context."
+            };
+        }
+        return *(params.zoom);
+    });
+    
+    define("heatmap-density", [](const EvaluationContext& params) -> Result<double> {
+        if (!params.heatmapDensity) {
+            return EvaluationError {
+                "The 'heatmap-density' expression is unavailable in the current evaluation context."
+            };
+        }
+        return *(params.heatmapDensity);
+    });
+    
+    define("has", [](const EvaluationContext& params, const std::string& key) -> Result<bool> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+        
+        return params.feature->getValue(key) ? true : false;
+    });
+    define("has", [](const std::string& key, const std::unordered_map<std::string, Value>& object) -> Result<bool> {
+        return object.find(key) != object.end();
+    });
+    
+    define("get", [](const EvaluationContext& params, const std::string& key) -> Result<Value> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+
+        auto propertyValue = params.feature->getValue(key);
+        if (!propertyValue) {
+            return Null;
+        }
+        return Value(toExpressionValue(*propertyValue));
+    });
+    define("get", [](const std::string& key, const std::unordered_map<std::string, Value>& object) -> Result<Value> {
+        if (object.find(key) == object.end()) {
+            return Null;
+        }
+        return object.at(key);
+    });
+    
+    define("length", [](const std::vector<Value>& arr) -> Result<double> {
+        return arr.size();
+    });
+    define("length", [] (const std::string s) -> Result<double> {
+        return s.size();
+    });
+    
+    define("properties", [](const EvaluationContext& params) -> Result<std::unordered_map<std::string, Value>> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+        std::unordered_map<std::string, Value> result;
+        const PropertyMap properties = params.feature->getProperties();
+        for (const auto& entry : properties) {
+            result[entry.first] = toExpressionValue(entry.second);
+        }
+        return result;
+    });
+    
+    define("geometry-type", [](const EvaluationContext& params) -> Result<std::string> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+    
+        auto type = params.feature->getType();
+        if (type == FeatureType::Point) {
+            return "Point";
+        } else if (type == FeatureType::LineString) {
+            return "LineString";
+        } else if (type == FeatureType::Polygon) {
+            return "Polygon";
+        } else {
+            return "Unknown";
+        }
+    });
+    
+    define("id", [](const EvaluationContext& params) -> Result<Value> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+    
+        auto id = params.feature->getID();
+        if (!id) {
+            return Null;
+        }
+        return id->match(
+            [](const auto& idValue) {
+                return toExpressionValue(mbgl::Value(idValue));
+            }
+        );
+    });
+    
+    define("+", [](const Varargs<double>& args) -> Result<double> {
+        double sum = 0.0f;
+        for (auto arg : args) {
+            sum += arg;
+        }
+        return sum;
+    });
+    define("-", [](double a, double b) -> Result<double> { return a - b; });
+    define("-", [](double a) -> Result<double> { return -a; });
+    define("*", [](const Varargs<double>& args) -> Result<double> {
+        double prod = 1.0f;
+        for (auto arg : args) {
+            prod *= arg;
+        }
+        return prod;
+    });
+    define("/", [](double a, double b) -> Result<double> { return a / b; });
+    define("%", [](double a, double b) -> Result<double> { return fmod(a, b); });
+    define("^", [](double a, double b) -> Result<double> { return pow(a, b); });
+    define("sqrt", [](double x) -> Result<double> { return sqrt(x); });
+    define("log10", [](double x) -> Result<double> { return log10(x); });
+    define("ln", [](double x) -> Result<double> { return log(x); });
+    define("log2", [](double x) -> Result<double> { return log2(x); });
+    define("sin", [](double x) -> Result<double> { return sin(x); });
+    define("cos", [](double x) -> Result<double> { return cos(x); });
+    define("tan", [](double x) -> Result<double> { return tan(x); });
+    define("asin", [](double x) -> Result<double> { return asin(x); });
+    define("acos", [](double x) -> Result<double> { return acos(x); });
+    define("atan", [](double x) -> Result<double> { return atan(x); });
+    
+    define("min", [](const Varargs<double>& args) -> Result<double> {
+        double result = std::numeric_limits<double>::infinity();
+        for (double arg : args) {
+            result = fmin(arg, result);
+        }
+        return result;
+    });
+    define("max", [](const Varargs<double>& args) -> Result<double> {
+        double result = -std::numeric_limits<double>::infinity();
+        for (double arg : args) {
+            result = fmax(arg, result);
+        }
+        return result;
+    });
+    
+    define("==", equal<double>);
+    define("==", equal<const std::string&>);
+    define("==", equal<bool>);
+    define("==", equal<NullValue>);
+
+    define("!=", notEqual<double>);
+    define("!=", notEqual<const std::string&>);
+    define("!=", notEqual<bool>);
+    define("!=", notEqual<NullValue>);
+
+    define(">", [](double lhs, double rhs) -> Result<bool> { return lhs > rhs; });
+    define(">", [](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs > rhs; });
+    define(">=", [](double lhs, double rhs) -> Result<bool> { return lhs >= rhs; });
+    define(">=",[](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs >= rhs; });
+    define("<", [](double lhs, double rhs) -> Result<bool> { return lhs < rhs; });
+    define("<", [](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs < rhs; });
+    define("<=", [](double lhs, double rhs) -> Result<bool> { return lhs <= rhs; });
+    define("<=", [](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs <= rhs; });
+    
+    define("!", [](bool e) -> Result<bool> { return !e; });
+    
+    define("upcase", [](const std::string& input) -> Result<std::string> {
+        std::string s = input;
+        std::transform(s.begin(), s.end(), s.begin(),
+                       [](unsigned char c){ return std::toupper(c); });
+        return s;
+    });
+    define("downcase", [](const std::string& input) -> Result<std::string> {
+        std::string s = input;
+        std::transform(s.begin(), s.end(), s.begin(),
+                       [](unsigned char c){ return std::tolower(c); });
+        return s;
+    });
+    define("concat", [](const Varargs<std::string>& args) -> Result<std::string> {
+        std::string s;
+        for (const std::string& arg : args) {
+            s += arg;
+        }
+        return s;
+    });
+    define("error", [](const std::string& input) -> Result<type::ErrorType> {
+        return EvaluationError { input };
+    });
+    
+    return definitions;
+}
+
+std::unordered_map<std::string, Definition> CompoundExpressionRegistry::definitions = initializeDefinitions();
+
+using namespace mbgl::style::conversion;
+ParseResult parseCompoundExpression(const std::string name, const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value) && arrayLength(value) > 0);
+
+    auto it = CompoundExpressionRegistry::definitions.find(name);
+    if (it == CompoundExpressionRegistry::definitions.end()) {
+        ctx.error(
+             R"(Unknown expression ")" + name + R"(". If you wanted a literal array, use ["literal", [...]].)",
+            0
+        );
+        return ParseResult();
+    }
+    const CompoundExpressionRegistry::Definition& definition = it->second;
+    
+    auto length = arrayLength(value);
+
+    // Check if we have a single signature with the correct number of
+    // parameters. If so, then use that signature's parameter types for parsing
+    // (and inferring the types of) the arguments.
+    optional<std::size_t> singleMatchingSignature;
+    for (std::size_t j = 0; j < definition.size(); j++) {
+        const std::unique_ptr<detail::SignatureBase>& signature = definition[j];
+        if (
+            signature->params.is<VarargsType>() ||
+            signature->params.get<std::vector<type::Type>>().size() == length - 1
+        ) {
+            if (singleMatchingSignature) {
+                singleMatchingSignature = {};
+            } else {
+                singleMatchingSignature = j;
+            }
+        }
+    }
+
+    // parse subexpressions first
+    std::vector<std::unique_ptr<Expression>> args;
+    args.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        optional<type::Type> expected;
+        
+        if (singleMatchingSignature) {
+            expected = definition[*singleMatchingSignature]->params.match(
+                [](const VarargsType& varargs) { return varargs.type; },
+                [&](const std::vector<type::Type>& params_) { return params_[i - 1]; }
+            );
+        }
+    
+        auto parsed = ctx.parse(arrayMember(value, i), i, expected);
+        if (!parsed) {
+            return parsed;
+        }
+        args.push_back(std::move(*parsed));
+    }
+    return createCompoundExpression(name, definition, std::move(args), ctx);
+}
+
+
+ParseResult createCompoundExpression(const std::string& name,
+                                     std::vector<std::unique_ptr<Expression>> args,
+                                     ParsingContext& ctx)
+{
+    return createCompoundExpression(name, CompoundExpressionRegistry::definitions.at(name), std::move(args), ctx);
+}
+
+
+ParseResult createCompoundExpression(const std::string& name,
+                                     const Definition& definition,
+                                     std::vector<std::unique_ptr<Expression>> args,
+                                     ParsingContext& ctx)
+{
+    ParsingContext signatureContext(ctx.getKey());
+    
+    for (const std::unique_ptr<detail::SignatureBase>& signature : definition) {
+        signatureContext.clearErrors();
+        
+        if (signature->params.is<std::vector<type::Type>>()) {
+            const std::vector<type::Type>& params = signature->params.get<std::vector<type::Type>>();
+            if (params.size() != args.size()) {
+                signatureContext.error(
+                    "Expected " + std::to_string(params.size()) +
+                    " arguments, but found " + std::to_string(args.size()) + " instead."
+                );
+                continue;
+            }
+
+            for (std::size_t i = 0; i < args.size(); i++) {
+                const std::unique_ptr<Expression>& arg = args[i];
+                optional<std::string> err = type::checkSubtype(params.at(i), arg->getType());
+                if (err) {
+                    signatureContext.error(*err, i + 1);
+                }
+            }
+        } else if (signature->params.is<VarargsType>()) {
+            const type::Type& paramType = signature->params.get<VarargsType>().type;
+            for (std::size_t i = 0; i < args.size(); i++) {
+                const std::unique_ptr<Expression>& arg = args[i];
+                optional<std::string> err = type::checkSubtype(paramType, arg->getType());
+                if (err) {
+                    signatureContext.error(*err, i + 1);
+                }
+            }
+        }
+        
+        if (signatureContext.getErrors().size() == 0) {
+            return ParseResult(signature->makeExpression(name, std::move(args)));
+        }
+    }
+    
+    if (definition.size() == 1) {
+        ctx.appendErrors(std::move(signatureContext));
+    } 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 += "(";
+                    bool first = true;
+                    for (const type::Type& param : params) {
+                        if (!first) signatures += ", ";
+                        signatures += toString(param);
+                        first = false;
+                    }
+                    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();
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/find_zoom_curve.cpp b/src/mbgl/style/expression/find_zoom_curve.cpp
new file mode 100644
index 0000000000..5d39e0791e
--- /dev/null
+++ b/src/mbgl/style/expression/find_zoom_curve.cpp
@@ -0,0 +1,76 @@
+#include <mbgl/style/expression/find_zoom_curve.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/let.hpp>
+#include <mbgl/style/expression/coalesce.hpp>
+
+#include <mbgl/util/variant.hpp>
+#include <mbgl/util/optional.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+optional<variant<const InterpolateBase*, const Step*, ParsingError>> findZoomCurve(const expression::Expression* e) {
+    optional<variant<const InterpolateBase*, const Step*, ParsingError>> result;
+    
+    if (auto let = dynamic_cast<const Let*>(e)) {
+        result = findZoomCurve(let->getResult());
+    } else if (auto coalesce = dynamic_cast<const Coalesce*>(e)) {
+        std::size_t length = coalesce->getLength();
+        for (std::size_t i = 0; i < length; i++) {
+            result = findZoomCurve(coalesce->getChild(i));
+            if (result) {
+                break;
+            }
+        }
+    } else if (auto curve = dynamic_cast<const InterpolateBase*>(e)) {
+        auto z = dynamic_cast<CompoundExpressionBase*>(curve->getInput().get());
+        if (z && z->getName() == "zoom") {
+            result = {curve};
+        }
+    } else if (auto step = dynamic_cast<const Step*>(e)) {
+        auto z = dynamic_cast<CompoundExpressionBase*>(step->getInput().get());
+        if (z && z->getName() == "zoom") {
+            result = {step};
+        }
+    }
+    
+    if (result && result->is<ParsingError>()) {
+        return result;
+    }
+    
+    e->eachChild([&](const Expression& child) {
+        optional<variant<const InterpolateBase*, const Step*, ParsingError>> childResult(findZoomCurve(&child));
+        if (childResult) {
+            if (childResult->is<ParsingError>()) {
+                result = childResult;
+            } else if (!result && childResult) {
+                result = {ParsingError {
+                    R"("zoom" expression may only be used as input to a top-level "step" or "interpolate" expression.)", ""
+                }};
+            } else if (result && childResult && result != childResult) {
+                result = {ParsingError {
+                    R"(Only one zoom-based "step" or "interpolate" subexpression may be used in an expression.)", ""
+                }};
+            }
+        }
+    });
+
+    return result;
+}
+
+variant<const InterpolateBase*, const Step*> findZoomCurveChecked(const expression::Expression* e) {
+    return findZoomCurve(e)->match(
+        [](const ParsingError&) -> variant<const InterpolateBase*, const Step*> {
+            assert(false);
+            return {};
+        },
+        [](auto zoomCurve) -> variant<const InterpolateBase*, const Step*> {
+            return {std::move(zoomCurve)};
+        }
+    );
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/get_covering_stops.cpp b/src/mbgl/style/expression/get_covering_stops.cpp
new file mode 100644
index 0000000000..c9f87d93ac
--- /dev/null
+++ b/src/mbgl/style/expression/get_covering_stops.cpp
@@ -0,0 +1,26 @@
+#include <mbgl/style/expression/get_covering_stops.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+Range<float> getCoveringStops(const std::map<double, std::unique_ptr<Expression>>& stops,
+                              const double lower, const double upper) {
+    assert(!stops.empty());
+    auto minIt = stops.lower_bound(lower);
+    auto maxIt = stops.lower_bound(upper);
+
+    // lower_bound yields first element >= lowerZoom, but we want the *last*
+    // element <= lowerZoom, so if we found a stop > lowerZoom, back up by one.
+    if (minIt != stops.begin() && minIt != stops.end() && minIt->first > lower) {
+        minIt--;
+    }
+    return Range<float> {
+        static_cast<float>(minIt == stops.end() ? stops.rbegin()->first : minIt->first),
+        static_cast<float>(maxIt == stops.end() ? stops.rbegin()->first : maxIt->first)
+    };
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/interpolate.cpp b/src/mbgl/style/expression/interpolate.cpp
new file mode 100644
index 0000000000..020aba9dce
--- /dev/null
+++ b/src/mbgl/style/expression/interpolate.cpp
@@ -0,0 +1,211 @@
+
+#include <mbgl/style/expression/interpolate.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+using Interpolator = variant<ExponentialInterpolator,
+                             CubicBezierInterpolator>;
+
+using namespace mbgl::style::conversion;
+
+ParseResult parseInterpolate(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+
+    auto length = arrayLength(value);
+
+    if (length < 2) {
+        ctx.error("Expected an interpolation type expression.");
+        return ParseResult();
+    }
+
+    const Convertible& interp = arrayMember(value, 1);
+    if (!isArray(interp) || arrayLength(interp) == 0) {
+        ctx.error("Expected an interpolation type expression.");
+        return ParseResult();
+    }
+
+    optional<Interpolator> interpolator;
+    
+    const optional<std::string> interpName = toString(arrayMember(interp, 0));
+    if (interpName && *interpName == "linear") {
+        interpolator = {ExponentialInterpolator(1.0)};
+    } else if (interpName && *interpName == "exponential") {
+        optional<double> base;
+        if (arrayLength(interp) == 2) {
+            base = toDouble(arrayMember(interp, 1));
+        }
+        if (!base) {
+            ctx.error("Exponential interpolation requires a numeric base.", 1, 1);
+            return ParseResult();
+        }
+        interpolator = {ExponentialInterpolator(*base)};
+    } else if (interpName && *interpName == "cubic-bezier") {
+        optional<double> x1;
+        optional<double> y1;
+        optional<double> x2;
+        optional<double> y2;
+        if (arrayLength(interp) == 5) {
+            x1 = toDouble(arrayMember(interp, 1));
+            y1 = toDouble(arrayMember(interp, 2));
+            x2 = toDouble(arrayMember(interp, 3));
+            y2 = toDouble(arrayMember(interp, 4));
+        }
+        if (
+            !x1 || !y1 || !x2 || !y2 ||
+            *x1 < 0 || *x1 > 1 ||
+            *y1 < 0 || *y1 > 1 ||
+            *x2 < 0 || *x2 > 1 ||
+            *y2 < 0 || *y2 > 1
+        ) {
+            ctx.error("Cubic bezier interpolation requires four numeric arguments with values between 0 and 1.", 1);
+            return ParseResult();
+            
+        }
+        interpolator = {CubicBezierInterpolator(*x1, *y1, *x2, *y2)};
+    }
+    
+    if (!interpolator) {
+        ctx.error("Unknown interpolation type " + (interpName ? *interpName : ""), 1, 0);
+        return ParseResult();
+    }
+    
+    std::size_t minArgs = 4;
+    if (length - 1 < minArgs) {
+        ctx.error("Expected at least 4 arguments, but found only " + std::to_string(length - 1) + ".");
+        return ParseResult();
+    }
+    
+    // [interpolation, interp_type, input, 2 * (n pairs)...]
+    if ((length - 1) % 2 != 0) {
+        ctx.error("Expected an even number of arguments.");
+        return ParseResult();
+    }
+    
+    ParseResult input = ctx.parse(arrayMember(value, 2), 2, {type::Number});
+    if (!input) {
+        return input;
+    }
+
+    std::map<double, std::unique_ptr<Expression>> stops;
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+    
+    double previous = - std::numeric_limits<double>::infinity();
+    
+    for (std::size_t i = 3; i + 1 < length; i += 2) {
+        const optional<mbgl::Value> labelValue = toValue(arrayMember(value, i));
+        optional<double> label;
+        optional<std::string> labelError;
+        if (labelValue) {
+            labelValue->match(
+                [&](uint64_t n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](int64_t n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](double n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](const auto&) {}
+            );
+        }
+        if (!label) {
+            ctx.error(labelError ? *labelError :
+                R"(Input/output pairs for "interpolate" expressions must be defined using literal numeric values (not computed expressions) for the input values.)",
+                i);
+            return ParseResult();
+        }
+        
+        if (*label <= previous) {
+            ctx.error(
+                R"(Input/output pairs for "interpolate" expressions must be arranged with input values in strictly ascending order.)",
+                i
+            );
+            return ParseResult();
+        }
+        previous = *label;
+        
+        auto output = ctx.parse(arrayMember(value, i + 1), i + 1, outputType);
+        if (!output) {
+            return ParseResult();
+        }
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+
+        stops.emplace(*label, std::move(*output));
+    }
+    
+    assert(outputType);
+    
+    if (
+        *outputType != type::Number &&
+        *outputType != type::Color &&
+        !(
+            outputType->is<type::Array>() &&
+            outputType->get<type::Array>().itemType == type::Number &&
+            outputType->get<type::Array>().N
+        )
+    )
+    {
+        ctx.error("Type " + toString(*outputType) + " is not interpolatable.");
+        return ParseResult();
+    }
+    
+    return outputType->match(
+        [&](const type::NumberType&) -> ParseResult {
+            return interpolator->match([&](const auto& interpolator_) {
+                return ParseResult(std::make_unique<Interpolate<double>>(
+                    *outputType, interpolator_, std::move(*input), std::move(stops)
+                ));
+            });
+        },
+        [&](const type::ColorType&) -> ParseResult {
+            return interpolator->match([&](const auto& interpolator_) {
+                return ParseResult(std::make_unique<Interpolate<Color>>(
+                    *outputType, interpolator_, std::move(*input), std::move(stops)
+                ));
+            });
+        },
+        [&](const type::Array& arrayType) -> ParseResult {
+            return interpolator->match(
+                [&](const auto& continuousInterpolator) {
+                    if (arrayType.itemType != type::Number || !arrayType.N) {
+                        assert(false); // interpolability already checked above.
+                        return ParseResult();
+                    }
+                    return ParseResult(std::make_unique<Interpolate<std::vector<Value>>>(
+                        *outputType, continuousInterpolator, std::move(*input), std::move(stops)
+                    ));
+                }
+            );
+        },
+        [&](const auto&) {
+            // unreachable: Null, Boolean, String, Object, Value output types
+            // are not interpolatable, and interpolability was already checked above
+            assert(false);
+            return ParseResult();
+        }
+    );
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/is_constant.cpp b/src/mbgl/style/expression/is_constant.cpp
new file mode 100644
index 0000000000..0ebb37faa9
--- /dev/null
+++ b/src/mbgl/style/expression/is_constant.cpp
@@ -0,0 +1,40 @@
+#include <mbgl/style/expression/is_constant.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+bool isFeatureConstant(const Expression& expression) {
+    if (auto e = dynamic_cast<const CompoundExpressionBase*>(&expression)) {
+        const std::string name = e->getName();
+        optional<std::size_t> parameterCount = e->getParameterCount();
+        if (name == "get" && parameterCount && *parameterCount == 1) {
+            return false;
+        } else if (name == "has" && parameterCount && *parameterCount == 1) {
+            return false;
+        } else if (
+            name == "properties" ||
+            name == "geometry-type" ||
+            name == "id"
+        ) {
+            return false;
+        }
+    }
+
+    bool featureConstant = true;
+    expression.eachChild([&](const Expression& e) {
+        if (featureConstant && !isFeatureConstant(e)) {
+            featureConstant = false;
+        }
+    });
+    return featureConstant;
+}
+
+bool isZoomConstant(const Expression& e) {
+    return isGlobalPropertyConstant(e, std::array<std::string, 1>{{"zoom"}});
+}
+
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/is_expression.cpp b/src/mbgl/style/expression/is_expression.cpp
new file mode 100644
index 0000000000..77212f6a1e
--- /dev/null
+++ b/src/mbgl/style/expression/is_expression.cpp
@@ -0,0 +1,29 @@
+#include <mbgl/style/expression/is_expression.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+
+#include <mbgl/style/conversion.hpp>
+
+#include <unordered_set>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+using namespace mbgl::style::conversion;
+
+bool isExpression(const Convertible& value) {
+    const ExpressionRegistry& registry = getExpressionRegistry();
+
+    if (!isArray(value) || arrayLength(value) == 0) return false;
+    optional<std::string> name = toString(arrayMember(value, 0));
+    if (!name) return false;
+    
+    return (registry.find(*name) != registry.end()) ||
+        (CompoundExpressionRegistry::definitions.find(*name) != CompoundExpressionRegistry::definitions.end());
+}
+
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/let.cpp b/src/mbgl/style/expression/let.cpp
new file mode 100644
index 0000000000..8e206d3582
--- /dev/null
+++ b/src/mbgl/style/expression/let.cpp
@@ -0,0 +1,91 @@
+#include <mbgl/style/expression/let.hpp>
+#include <mbgl/style/conversion/get_json_type.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Let::evaluate(const EvaluationContext& params) const {
+    return result->evaluate(params);
+}
+
+void Let::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (auto it = bindings.begin(); it != bindings.end(); it++) {
+        visit(*it->second);
+    }
+    visit(*result);
+}
+
+using namespace mbgl::style::conversion;
+
+ParseResult Let::parse(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+
+    std::size_t length = arrayLength(value);
+
+    if (length < 4) {
+        ctx.error("Expected at least 3 arguments, but found " + std::to_string(length - 1) + " instead.");
+        return ParseResult();
+    }
+
+    std::map<std::string, std::shared_ptr<Expression>> bindings_;
+    for(std::size_t i = 1; i < length - 1; i += 2) {
+        optional<std::string> name = toString(arrayMember(value, i));
+        if (!name) {
+            ctx.error("Expected string, but found " + getJSONType(arrayMember(value, i)) + " instead.", i);
+            return ParseResult();
+        }
+        
+        bool isValidName = std::all_of(name->begin(), name->end(), [](unsigned char c) {
+            return std::isalnum(c) || c == '_';
+        });
+        if (!isValidName) {
+            ctx.error("Variable names must contain only alphanumeric characters or '_'.", 1);
+            return ParseResult();
+        }
+        
+        ParseResult bindingValue = ctx.parse(arrayMember(value, i + 1), i + 1);
+        if (!bindingValue) {
+            return ParseResult();
+        }
+        
+        bindings_.emplace(*name, std::move(*bindingValue));
+    }
+
+    ParseResult result_ = ctx.parse(arrayMember(value, length - 1), length - 1, ctx.getExpected(), bindings_);
+    if (!result_) {
+        return ParseResult();
+    }
+
+    return ParseResult(std::make_unique<Let>(std::move(bindings_), std::move(*result_)));
+}
+
+EvaluationResult Var::evaluate(const EvaluationContext& params) const {
+    return value->evaluate(params);
+}
+
+void Var::eachChild(const std::function<void(const Expression&)>&) const {}
+
+ParseResult Var::parse(const Convertible& value_, ParsingContext& ctx) {
+    assert(isArray(value_));
+
+    if (arrayLength(value_) != 2 || !toString(arrayMember(value_, 1))) {
+        ctx.error("'var' expression requires exactly one string literal argument.");
+        return ParseResult();
+    }
+
+    std::string name_ = *toString(arrayMember(value_, 1));
+
+    optional<std::shared_ptr<Expression>> bindingValue = ctx.getBinding(name_);
+    if (!bindingValue) {
+        ctx.error(R"(Unknown variable ")" + name_ +  R"(". Make sure ")" +
+            name_ + R"(" has been bound in an enclosing "let" expression before using it.)", 1);
+        return ParseResult();
+    }
+
+    return ParseResult(std::make_unique<Var>(name_, std::move(*bindingValue)));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/literal.cpp b/src/mbgl/style/expression/literal.cpp
new file mode 100644
index 0000000000..fc11878bea
--- /dev/null
+++ b/src/mbgl/style/expression/literal.cpp
@@ -0,0 +1,108 @@
+
+#include <mbgl/style/expression/literal.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+template <typename T>
+optional<Value> checkNumber(T n) {
+    if (n > std::numeric_limits<double>::max()) {
+        return {std::numeric_limits<double>::infinity()};
+    } else {
+        return {static_cast<double>(n)};
+    }
+}
+
+using namespace mbgl::style::conversion;
+optional<Value> parseValue(const Convertible& value, ParsingContext& ctx) {
+    if (isUndefined(value)) return {Null};
+    if (isObject(value)) {
+        std::unordered_map<std::string, Value> result;
+        bool error = false;
+        eachMember(value, [&] (const std::string& k, const mbgl::style::conversion::Convertible& v) -> optional<conversion::Error> {
+            if (!error) {
+                optional<Value> memberValue = parseValue(v, ctx);
+                if (memberValue) {
+                    result.emplace(k, *memberValue);
+                } else {
+                    error = true;
+                }
+            }
+            return {};
+        });
+        return error ? optional<Value>() : optional<Value>(result);
+    }
+    
+    if (isArray(value)) {
+        std::vector<Value> result;
+        const auto length = arrayLength(value);
+        for(std::size_t i = 0; i < length; i++) {
+            optional<Value> item = parseValue(arrayMember(value, i), ctx);
+            if (item) {
+                result.emplace_back(*item);
+            } else {
+                return optional<Value>();
+            }
+        }
+        return optional<Value>(result);
+    }
+    
+    optional<mbgl::Value> v = toValue(value);
+    // since value represents a JSON value, if it's not undefined, object, or
+    // array, it must be convertible to mbgl::Value
+    assert(v);
+    
+    return v->match(
+        [&](uint64_t n) { return checkNumber(n); },
+        [&](int64_t n) { return checkNumber(n); },
+        [&](double n) { return checkNumber(n); },
+        [&](const auto&) {
+            return optional<Value>(toExpressionValue(*v));
+        }
+    );
+}
+
+ParseResult Literal::parse(const Convertible& value, ParsingContext& ctx) {
+    if (isObject(value)) {
+        ctx.error(R"(Bare objects invalid. Use ["literal", {...}] instead.)");
+        return ParseResult();
+    } else if (isArray(value)) {
+        // object or array value, quoted with ["literal", value]
+        if (arrayLength(value) != 2) {
+            ctx.error("'literal' expression requires exactly one argument, but found " + std::to_string(arrayLength(value) - 1) + " instead.");
+            return ParseResult();
+        }
+        const optional<Value> parsedValue = parseValue(arrayMember(value, 1), ctx);
+        if (!parsedValue) {
+            return ParseResult();
+        }
+        
+        // special case: infer the item type if possible for zero-length arrays
+        if (
+            ctx.getExpected() &&
+            ctx.getExpected()->template is<type::Array>() &&
+            parsedValue->template is<std::vector<Value>>()
+        ) {
+            auto type = typeOf(*parsedValue).template get<type::Array>();
+            auto expected = ctx.getExpected()->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));
+    } else {
+        // bare primitive value (string, number, boolean, null)
+        const optional<Value> parsedValue = parseValue(value, ctx);
+        return ParseResult(std::make_unique<Literal>(*parsedValue));
+    }
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
diff --git a/src/mbgl/style/expression/match.cpp b/src/mbgl/style/expression/match.cpp
new file mode 100644
index 0000000000..6336eba1e6
--- /dev/null
+++ b/src/mbgl/style/expression/match.cpp
@@ -0,0 +1,262 @@
+#include <mbgl/style/expression/match.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+template <typename T>
+void Match<T>::eachChild(const std::function<void(const Expression&)>& visit) const {
+    visit(*input);
+    for (const std::pair<T, std::shared_ptr<Expression>>& branch : branches) {
+        visit(*branch.second);
+    }
+    visit(*otherwise);
+}
+
+template <typename T>
+bool Match<T>::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Match*>(&e)) {
+        return (*input == *(rhs->input) &&
+                *otherwise == *(rhs->otherwise) &&
+                Expression::childrenEqual(branches, rhs->branches));
+    }
+    return false;
+}
+
+
+template<> EvaluationResult Match<std::string>::evaluate(const EvaluationContext& params) const {
+    const EvaluationResult inputValue = input->evaluate(params);
+    if (!inputValue) {
+        return inputValue.error();
+    }
+
+    auto it = branches.find(inputValue->get<std::string>());
+    if (it != branches.end()) {
+        return (*it).second->evaluate(params);
+    }
+
+    return otherwise->evaluate(params);
+}
+
+template<> EvaluationResult Match<int64_t>::evaluate(const EvaluationContext& params) const {
+    const EvaluationResult inputValue = input->evaluate(params);
+    if (!inputValue) {
+        return inputValue.error();
+    }
+    
+    const auto numeric = inputValue->get<double>();
+    int64_t rounded = std::floor(numeric);
+    if (numeric == rounded) {
+        auto it = branches.find(rounded);
+        if (it != branches.end()) {
+            return (*it).second->evaluate(params);
+        }
+    }
+    
+    return otherwise->evaluate(params);
+}
+
+template class Match<int64_t>;
+template class Match<std::string>;
+
+using InputType = variant<int64_t, std::string>;
+
+using namespace mbgl::style::conversion;
+optional<InputType> parseInputValue(const Convertible& input, ParsingContext& parentContext, std::size_t index, optional<type::Type>& inputType) {
+    using namespace mbgl::style::conversion;
+    optional<InputType> result;
+    optional<type::Type> type;
+
+    auto value = toValue(input);
+
+    if (value) {
+        value->match(
+            [&] (uint64_t n) {
+                if (!Value::isSafeInteger(n)) {
+                    parentContext.error("Branch labels must be integers no larger than " + std::to_string(Value::maxSafeInteger()) + ".", index);
+                } else {
+                    type = {type::Number};
+                    result = {static_cast<int64_t>(n)};
+                }
+            },
+            [&] (int64_t n) {
+                if (!Value::isSafeInteger(n)) {
+                    parentContext.error("Branch labels must be integers no larger than " + std::to_string(Value::maxSafeInteger()) + ".", index);
+                } else {
+                    type = {type::Number};
+                    result = {n};
+                }
+            },
+            [&] (double n) {
+                if (!Value::isSafeInteger(n)) {
+                    parentContext.error("Branch labels must be integers no larger than " + std::to_string(Value::maxSafeInteger()) + ".", index);
+                } else if (n != std::floor(n)) {
+                    parentContext.error("Numeric branch labels must be integer values.", index);
+                } else {
+                    type = {type::Number};
+                    result = {static_cast<int64_t>(n)};
+                }
+            },
+            [&] (const std::string& s) {
+                type = {type::String};
+                result = {s};
+            },
+            [&] (const auto&) {
+                parentContext.error("Branch labels must be numbers or strings.", index);
+            }
+        );
+    } else {
+        parentContext.error("Branch labels must be numbers or strings.", index);
+    }
+
+    if (!type) {
+        return result;
+    }
+
+    if (!inputType) {
+        inputType = type;
+    } else {
+        optional<std::string> err = type::checkSubtype(*inputType, *type);
+        if (err) {
+            parentContext.error(*err, index);
+            return optional<InputType>();
+        }
+    }
+
+    return result;
+}
+
+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>>> branches,
+                          std::unique_ptr<Expression> otherwise,
+                          ParsingContext& ctx) {
+    typename Match<T>::Branches typedBranches;
+    
+    std::size_t index = 2;
+
+    typedBranches.reserve(branches.size());
+    for (std::pair<std::vector<InputType>,
+                   std::unique_ptr<Expression>>& pair : branches) {
+        std::shared_ptr<Expression> result = std::move(pair.second);
+        for (const InputType& label : pair.first) {
+            const auto& typedLabel = label.template get<T>();
+            if (typedBranches.find(typedLabel) != typedBranches.end()) {
+                ctx.error("Branch labels must be unique.", index);
+                return ParseResult();
+            }
+            typedBranches.emplace(typedLabel, result);
+        }
+        
+        index += 2;
+    }
+    return ParseResult(std::make_unique<Match<T>>(
+        outputType,
+        std::move(input),
+        std::move(typedBranches),
+        std::move(otherwise)
+    ));
+}
+
+ParseResult parseMatch(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+    auto length = arrayLength(value);
+    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) {
+        ctx.error("Expected an even number of arguments.");
+        return ParseResult();
+    }
+
+    optional<type::Type> inputType;
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+
+    std::vector<std::pair<std::vector<InputType>,
+                          std::unique_ptr<Expression>>> branches;
+
+    branches.reserve((length - 3) / 2);
+    for (size_t i = 2; i + 1 < length; i += 2) {
+        const auto& label = arrayMember(value, 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(label)) {
+            auto groupLength = arrayLength(label);
+            if (groupLength == 0) {
+                ctx.error("Expected at least one branch label.", i);
+                return ParseResult();
+            }
+            
+            labels.reserve(groupLength);
+            for (size_t j = 0; j < groupLength; j++) {
+                const optional<InputType> inputValue = parseInputValue(arrayMember(label, j), ctx, i, inputType);
+                if (!inputValue) {
+                    return ParseResult();
+                }
+                labels.push_back(*inputValue);
+            }
+        } else {
+            const optional<InputType> inputValue = parseInputValue(label, ctx, i, inputType);
+            if (!inputValue) {
+                return ParseResult();
+            }
+            labels.push_back(*inputValue);
+        }
+        
+        ParseResult output = ctx.parse(arrayMember(value, i + 1), i + 1, outputType);
+        if (!output) {
+            return ParseResult();
+        }
+        
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+        
+        branches.push_back(std::make_pair(std::move(labels), std::move(*output)));
+    }
+
+    auto input = ctx.parse(arrayMember(value, 1), 1, inputType);
+    if (!input) {
+        return ParseResult();
+    }
+
+    auto otherwise = ctx.parse(arrayMember(value, length - 1), length - 1, outputType);
+    if (!otherwise) {
+        return ParseResult();
+    }
+
+    assert(inputType && outputType);
+
+    return inputType->match(
+        [&](const type::NumberType&) {
+            return create<int64_t>(*outputType, std::move(*input), std::move(branches), std::move(*otherwise), ctx);
+        },
+        [&](const type::StringType&) {
+            return create<std::string>(*outputType, std::move(*input), std::move(branches), std::move(*otherwise), ctx);
+        },
+        [&](const auto&) {
+            // unreachable: inputType is set by parseInputValue(), which only
+            // accepts string and (integer) numeric values.
+            assert(false);
+            return ParseResult();
+        }
+    );
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/parsing_context.cpp b/src/mbgl/style/expression/parsing_context.cpp
new file mode 100644
index 0000000000..81cbdede59
--- /dev/null
+++ b/src/mbgl/style/expression/parsing_context.cpp
@@ -0,0 +1,206 @@
+
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/is_constant.hpp>
+#include <mbgl/style/expression/type.hpp>
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/at.hpp>
+#include <mbgl/style/expression/array_assertion.hpp>
+#include <mbgl/style/expression/assertion.hpp>
+#include <mbgl/style/expression/boolean_operator.hpp>
+#include <mbgl/style/expression/case.hpp>
+#include <mbgl/style/expression/coalesce.hpp>
+#include <mbgl/style/expression/coercion.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/interpolate.hpp>
+#include <mbgl/style/expression/let.hpp>
+#include <mbgl/style/expression/literal.hpp>
+#include <mbgl/style/expression/match.hpp>
+#include <mbgl/style/expression/step.hpp>
+
+#include <mbgl/style/expression/find_zoom_curve.hpp>
+
+#include <mbgl/style/conversion/get_json_type.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+bool isConstant(const Expression& expression) {
+    if (dynamic_cast<const Var*>(&expression)) {
+        return false;
+    }
+    
+    if (auto compound = dynamic_cast<const CompoundExpressionBase*>(&expression)) {
+        if (compound->getName() == "error") {
+            return false;
+        }
+    }
+    
+    bool literalArgs = true;
+    expression.eachChild([&](const Expression& child) {
+        if (!dynamic_cast<const Literal*>(&child)) {
+            literalArgs = false;
+        }
+    });
+    if (!literalArgs) {
+        return false;
+    }
+    
+    return isFeatureConstant(expression) &&
+        isGlobalPropertyConstant(expression, std::array<std::string, 2>{{"zoom", "heatmap-density"}});
+}
+
+using namespace mbgl::style::conversion;
+
+ParseResult ParsingContext::parse(const Convertible& value, std::size_t index_, optional<type::Type> expected_) {
+    ParsingContext child(key + "[" + std::to_string(index_) + "]",
+                         errors,
+                         std::move(expected_),
+                         scope);
+    return child.parse(value);
+}
+
+ParseResult ParsingContext::parse(const Convertible& value, std::size_t index_, optional<type::Type> expected_,
+                                  const std::map<std::string, std::shared_ptr<Expression>>& bindings) {
+    ParsingContext child(key + "[" + std::to_string(index_) + "]",
+                         errors,
+                         std::move(expected_),
+                         std::make_shared<detail::Scope>(bindings, scope));
+    return child.parse(value);
+}
+
+const ExpressionRegistry& getExpressionRegistry() {
+    static ExpressionRegistry registry {{
+        {"all", All::parse},
+        {"any", Any::parse},
+        {"array", ArrayAssertion::parse},
+        {"at", At::parse},
+        {"boolean", Assertion::parse},
+        {"case", Case::parse},
+        {"coalesce", Coalesce::parse},
+        {"interpolate", parseInterpolate},
+        {"let", Let::parse},
+        {"literal", Literal::parse},
+        {"match", parseMatch},
+        {"number", Assertion::parse},
+        {"object", Assertion::parse},
+        {"step", Step::parse},
+        {"string", Assertion::parse},
+        {"to-color", Coercion::parse},
+        {"to-number", Coercion::parse},
+        {"var", Var::parse}
+    }};
+    return registry;
+}
+
+ParseResult ParsingContext::parse(const Convertible& value)
+{
+    ParseResult parsed;
+    
+    if (isArray(value)) {
+        const std::size_t length = arrayLength(value);
+        if (length == 0) {
+            error(R"(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) {
+            error(
+                "Expression name must be a string, but found " + getJSONType(arrayMember(value, 0)) +
+                    R"( instead. If you wanted a literal array, use ["literal", [...]].)",
+                0
+            );
+            return ParseResult();
+        }
+        
+        const ExpressionRegistry& registry = getExpressionRegistry();
+        auto parseFunction = registry.find(*op);
+        if (parseFunction != registry.end()) {
+            parsed = parseFunction->second(value, *this);
+        } else {
+            parsed = parseCompoundExpression(*op, value, *this);
+        }
+    } else {
+        parsed = Literal::parse(value, *this);
+    }
+    
+    if (!parsed) {
+        assert(errors->size() > 0);
+    } else if (expected) {
+        auto wrapForType = [&](const type::Type& target, std::unique_ptr<Expression> expression) -> std::unique_ptr<Expression> {
+            std::vector<std::unique_ptr<Expression>> args;
+            args.push_back(std::move(expression));
+            if (target == type::Color) {
+                return std::make_unique<Coercion>(target, std::move(args));
+            } else {
+                return std::make_unique<Assertion>(target, std::move(args));
+            }
+        };
+        
+        const type::Type actual = (*parsed)->getType();
+        if (*expected == type::Color && (actual == type::String || actual == type::Value)) {
+            parsed = wrapForType(type::Color, std::move(*parsed));
+        } else if ((*expected == type::String || *expected == type::Number || *expected == type::Boolean) && actual == type::Value) {
+            parsed = wrapForType(*expected, std::move(*parsed));
+        }
+    
+        checkType((*parsed)->getType());
+        if (errors->size() > 0) {
+            return ParseResult();
+        }
+    }
+    
+    // If an expression's arguments are all literals, we can evaluate
+    // it immediately and replace it with a literal value in the
+    // parsed result.
+    if (parsed && !dynamic_cast<Literal *>(parsed->get()) && isConstant(**parsed)) {
+        EvaluationContext params(nullptr);
+        EvaluationResult evaluated((*parsed)->evaluate(params));
+        if (!evaluated) {
+            error(evaluated.error().message);
+            return ParseResult();
+        }
+        
+        const type::Type type = (*parsed)->getType();
+        if (type.is<type::Array>()) {
+            // keep the original expression's array type, even if the evaluated
+            // type is more specific.
+            return ParseResult(std::make_unique<Literal>(
+                  type.get<type::Array>(),
+                  evaluated->get<std::vector<Value>>())
+            );
+        } else {
+            return ParseResult(std::make_unique<Literal>(*evaluated));
+        }
+    }
+
+    // if this is the root expression, enforce constraints on the use ["zoom"].
+    if (key.size() == 0 && parsed && !isZoomConstant(**parsed)) {
+        optional<variant<const InterpolateBase*, const Step*, ParsingError>> zoomCurve = findZoomCurve(parsed->get());
+        if (!zoomCurve) {
+            error(R"("zoom" expression may only be used as input to a top-level "step" or "interpolate" expression.)");
+            return ParseResult();
+        } else if (zoomCurve->is<ParsingError>()) {
+            error(zoomCurve->get<ParsingError>().message);
+            return ParseResult();
+        }
+    }
+
+    return parsed;
+}
+
+optional<std::string> ParsingContext::checkType(const type::Type& t) {
+    assert(expected);
+    optional<std::string> err = type::checkSubtype(*expected, t);
+    if (err) {
+        error(*err);
+    }
+    return err;
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/step.cpp b/src/mbgl/style/expression/step.cpp
new file mode 100644
index 0000000000..2720e9257a
--- /dev/null
+++ b/src/mbgl/style/expression/step.cpp
@@ -0,0 +1,151 @@
+#include <mbgl/style/expression/step.hpp>
+#include <mbgl/style/expression/get_covering_stops.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Step::evaluate(const EvaluationContext& params) const {
+    const EvaluationResult evaluatedInput = input->evaluate(params);
+    if (!evaluatedInput) { return evaluatedInput.error(); }
+    float x = *fromExpressionValue<float>(*evaluatedInput);
+
+    if (stops.empty()) {
+        return EvaluationError { "No stops in step curve." };
+    }
+
+    auto it = stops.upper_bound(x);
+    if (it == stops.end()) {
+        return stops.rbegin()->second->evaluate(params);
+    } else if (it == stops.begin()) {
+        return stops.begin()->second->evaluate(params);
+    } else {
+        return std::prev(it)->second->evaluate(params);
+    }
+}
+
+void Step::eachChild(const std::function<void(const Expression&)>& visit) const {
+    visit(*input);
+    for (auto it = stops.begin(); it != stops.end(); it++) {
+        visit(*it->second);
+    }
+}
+
+bool Step::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Step*>(&e)) {
+        return *input == *(rhs->input) && Expression::childrenEqual(stops, rhs->stops);
+    }
+    return false;
+}
+
+Range<float> Step::getCoveringStops(const double lower, const double upper) const {
+    return ::mbgl::style::expression::getCoveringStops(stops, lower, upper);
+}
+
+
+ParseResult Step::parse(const mbgl::style::conversion::Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+
+    auto length = arrayLength(value);
+
+    if (length - 1 < 4) {
+        ctx.error("Expected at least 4 arguments, but found only " + std::to_string(length - 1) + ".");
+        return ParseResult();
+    }
+    
+    // [step, input, firstOutput_value, 2 * (n pairs)...]
+    if ((length - 1) % 2 != 0) {
+        ctx.error("Expected an even number of arguments.");
+        return ParseResult();
+    }
+    
+    ParseResult input = ctx.parse(arrayMember(value, 1), 1, {type::Number});
+    if (!input) {
+        return input;
+    }
+    
+    std::map<double, std::unique_ptr<Expression>> stops;
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+    
+    double previous = - std::numeric_limits<double>::infinity();
+    
+    // consume the first output value, which doesn't have a corresponding input value,
+    // before proceeding into the "stops" loop below.
+    auto firstOutput = ctx.parse(arrayMember(value, 2), 2, outputType);
+    if (!firstOutput) {
+        return ParseResult();
+    }
+    if (!outputType) {
+        outputType = (*firstOutput)->getType();
+    }
+    stops.emplace(-std::numeric_limits<double>::infinity(), std::move(*firstOutput));
+    
+    
+    for (std::size_t i = 3; i + 1 < length; i += 2) {
+        const optional<mbgl::Value> labelValue = toValue(arrayMember(value, i));
+        optional<double> label;
+        if (labelValue) {
+            labelValue->match(
+                [&](uint64_t n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](int64_t n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](double n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](const auto&) {}
+            );
+        }
+        if (!label) {
+            ctx.error(R"(Input/output pairs for "step" expressions must be defined using literal numeric values (not computed expressions) for the input values.)", i);
+            return ParseResult();
+        }
+        
+        if (*label <= previous) {
+            ctx.error(
+                R"(Input/output pairs for "step" expressions must be arranged with input values in strictly ascending order.)",
+                i
+            );
+            return ParseResult();
+        }
+        previous = *label;
+        
+        auto output = ctx.parse(arrayMember(value, i + 1), i + 1, outputType);
+        if (!output) {
+            return ParseResult();
+        }
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+
+        stops.emplace(*label, std::move(*output));
+    }
+    
+    assert(outputType);
+    
+    return ParseResult(std::make_unique<Step>(*outputType, std::move(*input), std::move(stops)));
+}
+
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
diff --git a/src/mbgl/style/expression/util.cpp b/src/mbgl/style/expression/util.cpp
new file mode 100644
index 0000000000..f198fb3e1b
--- /dev/null
+++ b/src/mbgl/style/expression/util.cpp
@@ -0,0 +1,39 @@
+
+#include <mbgl/style/expression/util.hpp>
+#include <mbgl/style/expression/value.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+std::string stringifyColor(double r, double g, double b, double a) {
+    return stringify(r) + ", " +
+        stringify(g) + ", " +
+        stringify(b) + ", " +
+        stringify(a);
+}
+
+Result<Color> rgba(double r, double g, double b, double a) {
+    if (
+        r < 0 || r > 255 ||
+        g < 0 || g > 255 ||
+        b < 0 || b > 255
+    ) {
+        return EvaluationError {
+            "Invalid rgba value [" + stringifyColor(r, g, b, a)  +
+            "]: 'r', 'g', and 'b' must be between 0 and 255."
+        };
+    }
+    if (a < 0 || a > 1) {
+        return EvaluationError {
+            "Invalid rgba value [" + stringifyColor(r, g, b, a)  +
+            "]: 'a' must be between 0 and 1."
+        };
+    }
+    return Color(r / 255, g / 255, b / 255, a);
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
diff --git a/src/mbgl/style/expression/util.hpp b/src/mbgl/style/expression/util.hpp
new file mode 100644
index 0000000000..b6fc408ed9
--- /dev/null
+++ b/src/mbgl/style/expression/util.hpp
@@ -0,0 +1,14 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/util/color.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+Result<Color> rgba(double r, double g, double b, double a);
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/value.cpp b/src/mbgl/style/expression/value.cpp
new file mode 100644
index 0000000000..b75f471ce3
--- /dev/null
+++ b/src/mbgl/style/expression/value.cpp
@@ -0,0 +1,322 @@
+#include <rapidjson/writer.h>
+#include <rapidjson/stringbuffer.h>
+#include <mbgl/style/expression/value.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+type::Type typeOf(const Value& value) {
+    return value.match(
+        [&](bool) -> type::Type { return type::Boolean; },
+        [&](double) -> type::Type { return type::Number; },
+        [&](const std::string&) -> type::Type { return type::String; },
+        [&](const Color&) -> type::Type { return type::Color; },
+        [&](const NullValue&) -> type::Type { return type::Null; },
+        [&](const std::unordered_map<std::string, Value>&) -> type::Type { return type::Object; },
+        [&](const std::vector<Value>& arr) -> type::Type {
+            optional<type::Type> itemType;
+            for (const auto& item : arr) {
+                const type::Type t = typeOf(item);
+                if (!itemType) {
+                    itemType = {t};
+                } else if (*itemType == t) {
+                    continue;
+                } else {
+                    itemType = {type::Value};
+                    break;
+                }
+            }
+
+            return type::Array(itemType.value_or(type::Value), arr.size());
+        }
+    );
+}
+
+void writeJSON(rapidjson::Writer<rapidjson::StringBuffer>& writer, const Value& value) {
+    value.match(
+        [&] (const NullValue&) { writer.Null(); },
+        [&] (bool b) { writer.Bool(b); },
+        [&] (double f) {
+            // make sure integer values are stringified without trailing ".0".
+            f == std::floor(f) ? writer.Int(f) : writer.Double(f);
+        },
+        [&] (const std::string& s) { writer.String(s); },
+        [&] (const Color& c) { writer.String(c.stringify()); },
+        [&] (const std::vector<Value>& arr) {
+            writer.StartArray();
+            for(const auto& item : arr) {
+                writeJSON(writer, item);
+            }
+            writer.EndArray();
+        },
+        [&] (const std::unordered_map<std::string, Value>& obj) {
+            writer.StartObject();
+            for(const auto& entry : obj) {
+                writer.Key(entry.first.c_str());
+                writeJSON(writer, entry.second);
+            }
+            writer.EndObject();
+        }
+    );
+}
+
+std::string stringify(const Value& value) {
+    rapidjson::StringBuffer buffer;
+    rapidjson::Writer<rapidjson::StringBuffer> writer(buffer);
+    writeJSON(writer, value);
+    return buffer.GetString();
+}
+
+struct FromMBGLValue {
+    Value operator()(const std::vector<mbgl::Value>& v) {
+        std::vector<Value> result;
+        result.reserve(v.size());
+        for(const auto& item : v) {
+            result.emplace_back(toExpressionValue(item));
+        }
+        return result;
+    }
+    
+    Value operator()(const std::unordered_map<std::string, mbgl::Value>& v) {
+        std::unordered_map<std::string, Value> result;
+        result.reserve(v.size());
+        for(const auto& entry : v) {
+            result.emplace(entry.first, toExpressionValue(entry.second));
+        }
+        return result;
+    }
+    
+    Value operator()(const std::string& s) { return s; }
+    Value operator()(const bool b) { return b; }
+    Value operator()(const NullValue) { return Null; }
+    Value operator()(const double v) { return v; }
+    Value operator()(const uint64_t& v) {
+        return static_cast<double>(v);
+    }
+    Value operator()(const int64_t& v) {
+        return static_cast<double>(v);
+    }
+};
+
+Value ValueConverter<mbgl::Value>::toExpressionValue(const mbgl::Value& value) {
+    return mbgl::Value::visit(value, FromMBGLValue());
+}
+
+Value ValueConverter<float>::toExpressionValue(const float value) {
+    return static_cast<double>(value);
+}
+
+optional<float> ValueConverter<float>::fromExpressionValue(const Value& value) {
+    if (value.template is<double>()) {
+        double v = value.template get<double>();
+        if (v <= std::numeric_limits<float>::max()) {
+            return static_cast<float>(v);
+        }
+    }
+    return optional<float>();
+}
+
+
+template <typename T, typename Container>
+std::vector<Value> toArrayValue(const Container& value) {
+    std::vector<Value> result;
+    result.reserve(value.size());
+    for (const T& item : value) {
+        result.push_back(ValueConverter<T>::toExpressionValue(item));
+    }
+    return result;
+}
+
+template <typename T, std::size_t N>
+Value ValueConverter<std::array<T, N>>::toExpressionValue(const std::array<T, N>& value) {
+    return toArrayValue<T>(value);
+}
+
+template <typename T, std::size_t N>
+optional<std::array<T, N>> ValueConverter<std::array<T, N>>::fromExpressionValue(const Value& value) {
+    return value.match(
+        [&] (const std::vector<Value>& v) -> optional<std::array<T, N>> {
+            if (v.size() != N) return optional<std::array<T, N>>();
+                std::array<T, N> result;
+                auto it = result.begin();
+                for(const Value& item : v) {
+                    optional<T> convertedItem = ValueConverter<T>::fromExpressionValue(item);
+                    if (!convertedItem) {
+                        return optional<std::array<T, N>>();
+                    }
+                    *it = *convertedItem;
+                    it = std::next(it);
+                }
+                return result;
+        },
+        [&] (const auto&) { return optional<std::array<T, N>>(); }
+    );
+}
+
+
+template <typename T>
+Value ValueConverter<std::vector<T>>::toExpressionValue(const std::vector<T>& value) {
+    return toArrayValue<T>(value);
+}
+
+template <typename T>
+optional<std::vector<T>> ValueConverter<std::vector<T>>::fromExpressionValue(const Value& value) {
+    return value.match(
+        [&] (const std::vector<Value>& v) -> optional<std::vector<T>> {
+            std::vector<T> result;
+            result.reserve(v.size());
+            for(const Value& item : v) {
+                optional<T> convertedItem = ValueConverter<T>::fromExpressionValue(item);
+                if (!convertedItem) {
+                    return optional<std::vector<T>>();
+                }
+                result.push_back(*convertedItem);
+            }
+            return result;
+        },
+        [&] (const auto&) { return optional<std::vector<T>>(); }
+    );
+}
+
+Value ValueConverter<Position>::toExpressionValue(const mbgl::style::Position& value) {
+    return ValueConverter<std::array<float, 3>>::toExpressionValue(value.getSpherical());
+}
+
+optional<Position> ValueConverter<Position>::fromExpressionValue(const Value& v) {
+    auto pos = ValueConverter<std::array<float, 3>>::fromExpressionValue(v);
+    return pos ? optional<Position>(Position(*pos)) : optional<Position>();
+}
+
+template <typename T>
+Value ValueConverter<T, std::enable_if_t< std::is_enum<T>::value >>::toExpressionValue(const T& value) {
+    return std::string(Enum<T>::toString(value));
+}
+
+template <typename T>
+optional<T> ValueConverter<T, std::enable_if_t< std::is_enum<T>::value >>::fromExpressionValue(const Value& value) {
+    return value.match(
+        [&] (const std::string& v) { return Enum<T>::toEnum(v); },
+        [&] (const auto&) { return optional<T>(); }
+    );
+}
+
+
+Value toExpressionValue(const Value& v) {
+    return v;
+}
+
+template <typename T, typename Enable>
+Value toExpressionValue(const T& value) {
+    return ValueConverter<T>::toExpressionValue(value);
+}
+
+optional<Value> fromExpressionValue(const Value& v) {
+    return optional<Value>(v);
+}
+
+template <typename T>
+std::enable_if_t< !std::is_convertible<T, Value>::value,
+optional<T>> fromExpressionValue(const Value& v)
+{
+    return ValueConverter<T>::fromExpressionValue(v);
+}
+
+template <typename T>
+type::Type valueTypeToExpressionType() {
+    return ValueConverter<T>::expressionType();
+}
+
+template <> type::Type valueTypeToExpressionType<Value>() { return type::Value; }
+template <> type::Type valueTypeToExpressionType<NullValue>() { return type::Null; }
+template <> type::Type valueTypeToExpressionType<bool>() { return type::Boolean; }
+template <> type::Type valueTypeToExpressionType<double>() { return type::Number; }
+template <> type::Type valueTypeToExpressionType<std::string>() { return type::String; }
+template <> type::Type valueTypeToExpressionType<Color>() { return type::Color; }
+template <> type::Type valueTypeToExpressionType<std::unordered_map<std::string, Value>>() { return type::Object; }
+template <> type::Type valueTypeToExpressionType<std::vector<Value>>() { return type::Array(type::Value); }
+
+// used only for the special (and private) "error" expression
+template <> type::Type valueTypeToExpressionType<type::ErrorType>() { return type::Error; }
+
+
+template Value toExpressionValue(const mbgl::Value&);
+
+
+// for to_rgba expression
+template type::Type valueTypeToExpressionType<std::array<double, 4>>();
+template optional<std::array<double, 4>> fromExpressionValue<std::array<double, 4>>(const Value&);
+template Value toExpressionValue(const std::array<double, 4>&);
+
+// layout/paint property types
+template type::Type valueTypeToExpressionType<float>();
+template optional<float> fromExpressionValue<float>(const Value&);
+template Value toExpressionValue(const float&);
+
+template type::Type valueTypeToExpressionType<std::array<float, 2>>();
+template optional<std::array<float, 2>> fromExpressionValue<std::array<float, 2>>(const Value&);
+template Value toExpressionValue(const std::array<float, 2>&);
+
+template type::Type valueTypeToExpressionType<std::array<float, 4>>();
+template optional<std::array<float, 4>> fromExpressionValue<std::array<float, 4>>(const Value&);
+template Value toExpressionValue(const std::array<float, 4>&);
+
+template type::Type valueTypeToExpressionType<std::vector<float>>();
+template optional<std::vector<float>> fromExpressionValue<std::vector<float>>(const Value&);
+template Value toExpressionValue(const std::vector<float>&);
+
+template type::Type valueTypeToExpressionType<std::vector<std::string>>();
+template optional<std::vector<std::string>> fromExpressionValue<std::vector<std::string>>(const Value&);
+template Value toExpressionValue(const std::vector<std::string>&);
+
+template type::Type valueTypeToExpressionType<AlignmentType>();
+template optional<AlignmentType> fromExpressionValue<AlignmentType>(const Value&);
+template Value toExpressionValue(const AlignmentType&);
+
+template type::Type valueTypeToExpressionType<CirclePitchScaleType>();
+template optional<CirclePitchScaleType> fromExpressionValue<CirclePitchScaleType>(const Value&);
+template Value toExpressionValue(const CirclePitchScaleType&);
+
+template type::Type valueTypeToExpressionType<IconTextFitType>();
+template optional<IconTextFitType> fromExpressionValue<IconTextFitType>(const Value&);
+template Value toExpressionValue(const IconTextFitType&);
+
+template type::Type valueTypeToExpressionType<LineCapType>();
+template optional<LineCapType> fromExpressionValue<LineCapType>(const Value&);
+template Value toExpressionValue(const LineCapType&);
+
+template type::Type valueTypeToExpressionType<LineJoinType>();
+template optional<LineJoinType> fromExpressionValue<LineJoinType>(const Value&);
+template Value toExpressionValue(const LineJoinType&);
+
+template type::Type valueTypeToExpressionType<SymbolPlacementType>();
+template optional<SymbolPlacementType> fromExpressionValue<SymbolPlacementType>(const Value&);
+template Value toExpressionValue(const SymbolPlacementType&);
+
+template type::Type valueTypeToExpressionType<SymbolAnchorType>();
+template optional<SymbolAnchorType> fromExpressionValue<SymbolAnchorType>(const Value&);
+template Value toExpressionValue(const SymbolAnchorType&);
+
+template type::Type valueTypeToExpressionType<TextJustifyType>();
+template optional<TextJustifyType> fromExpressionValue<TextJustifyType>(const Value&);
+template Value toExpressionValue(const TextJustifyType&);
+
+template type::Type valueTypeToExpressionType<TextTransformType>();
+template optional<TextTransformType> fromExpressionValue<TextTransformType>(const Value&);
+template Value toExpressionValue(const TextTransformType&);
+
+template type::Type valueTypeToExpressionType<TranslateAnchorType>();
+template optional<TranslateAnchorType> fromExpressionValue<TranslateAnchorType>(const Value&);
+template Value toExpressionValue(const TranslateAnchorType&);
+
+template type::Type valueTypeToExpressionType<LightAnchorType>();
+template optional<LightAnchorType> fromExpressionValue<LightAnchorType>(const Value&);
+template Value toExpressionValue(const LightAnchorType&);
+
+template type::Type valueTypeToExpressionType<Position>();
+template optional<Position> fromExpressionValue<Position>(const Value&);
+template Value toExpressionValue(const Position&);
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/function/expression.cpp b/src/mbgl/style/function/expression.cpp
new file mode 100644
index 0000000000..d9dbbfa1d3
--- /dev/null
+++ b/src/mbgl/style/function/expression.cpp
@@ -0,0 +1,38 @@
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/tile/geometry_tile_data.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class GeoJSONFeature : public GeometryTileFeature {
+public:
+    const Feature& feature;
+
+    GeoJSONFeature(const Feature& feature_) : feature(feature_) {}
+
+    FeatureType getType() const override  {
+        return apply_visitor(ToFeatureType(), feature.geometry);
+    }
+    PropertyMap getProperties() const override { return feature.properties; }
+    optional<FeatureIdentifier> getID() const override { return feature.id; }
+    GeometryCollection getGeometries() const override { return {}; }
+    optional<mbgl::Value> getValue(const std::string& key) const override {
+        auto it = feature.properties.find(key);
+        if (it != feature.properties.end()) {
+            return optional<mbgl::Value>(it->second);
+        }
+        return optional<mbgl::Value>();
+    }
+};
+
+
+EvaluationResult Expression::evaluate(optional<float> zoom, const Feature& feature, optional<double> heatmapDensity) const {
+    GeoJSONFeature f(feature);
+    return this->evaluate(EvaluationContext(zoom, &f, heatmapDensity));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl