Implement expressions

50 files changed, 4411 insertions, 147 deletions

diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index 7621283e7e..b0a4741873 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -364,10 +364,12 @@ set(MBGL_CORE_FILES
     include/mbgl/style/conversion/constant.hpp
     include/mbgl/style/conversion/coordinate.hpp
     include/mbgl/style/conversion/data_driven_property_value.hpp
+    include/mbgl/style/conversion/expression.hpp
     include/mbgl/style/conversion/filter.hpp
     include/mbgl/style/conversion/function.hpp
     include/mbgl/style/conversion/geojson.hpp
     include/mbgl/style/conversion/geojson_options.hpp
+    include/mbgl/style/conversion/get_json_type.hpp
     include/mbgl/style/conversion/layer.hpp
     include/mbgl/style/conversion/light.hpp
     include/mbgl/style/conversion/position.hpp
@@ -391,6 +393,34 @@ set(MBGL_CORE_FILES
     src/mbgl/style/conversion/tileset.cpp
     src/mbgl/style/conversion/transition_options.cpp
 
+    # style/expression
+    include/mbgl/style/expression/array_assertion.hpp
+    include/mbgl/style/expression/at.hpp
+    include/mbgl/style/expression/case.hpp
+    include/mbgl/style/expression/check_subtype.hpp
+    include/mbgl/style/expression/coalesce.hpp
+    include/mbgl/style/expression/compound_expression.hpp
+    include/mbgl/style/expression/curve.hpp
+    include/mbgl/style/expression/expression.hpp
+    include/mbgl/style/expression/let.hpp
+    include/mbgl/style/expression/literal.hpp
+    include/mbgl/style/expression/match.hpp
+    include/mbgl/style/expression/parsing_context.hpp
+    include/mbgl/style/expression/type.hpp
+    include/mbgl/style/expression/value.hpp
+    src/mbgl/style/expression/array_assertion.cpp
+    src/mbgl/style/expression/at.cpp
+    src/mbgl/style/expression/case.cpp
+    src/mbgl/style/expression/check_subtype.cpp
+    src/mbgl/style/expression/coalesce.cpp
+    src/mbgl/style/expression/compound_expression.cpp
+    src/mbgl/style/expression/curve.cpp
+    src/mbgl/style/expression/let.cpp
+    src/mbgl/style/expression/literal.cpp
+    src/mbgl/style/expression/match.cpp
+    src/mbgl/style/expression/parsing_context.cpp
+    src/mbgl/style/expression/value.cpp
+
     # style/function
     include/mbgl/style/function/camera_function.hpp
     include/mbgl/style/function/categorical_stops.hpp
@@ -398,11 +428,13 @@ set(MBGL_CORE_FILES
     include/mbgl/style/function/composite_exponential_stops.hpp
     include/mbgl/style/function/composite_function.hpp
     include/mbgl/style/function/composite_interval_stops.hpp
+    include/mbgl/style/function/convert.hpp
     include/mbgl/style/function/exponential_stops.hpp
     include/mbgl/style/function/identity_stops.hpp
     include/mbgl/style/function/interval_stops.hpp
     include/mbgl/style/function/source_function.hpp
     src/mbgl/style/function/categorical_stops.cpp
+    src/mbgl/style/function/expression.cpp
     src/mbgl/style/function/identity_stops.cpp
 
     # style/layers
diff --git a/cmake/node.cmake b/cmake/node.cmake
index 388a98b68f..3f7bcdb784 100644
--- a/cmake/node.cmake
+++ b/cmake/node.cmake
@@ -22,6 +22,8 @@ target_sources(mbgl-node
     PRIVATE platform/node/src/node_feature.cpp
     PRIVATE platform/node/src/node_thread_pool.hpp
     PRIVATE platform/node/src/node_thread_pool.cpp
+    PRIVATE platform/node/src/node_expression.hpp
+    PRIVATE platform/node/src/node_expression.cpp
     PRIVATE platform/node/src/util/async_queue.hpp
 )
 
@@ -94,6 +96,17 @@ xcode_create_scheme(
 xcode_create_scheme(
     TARGET mbgl-node
     TYPE node
+    NAME "node expression tests"
+    ARGS
+        "platform/node/test/expression.test.js"
+    OPTIONAL_ARGS
+        "group"
+        "test"
+)
+
+xcode_create_scheme(
+    TARGET mbgl-node
+    TYPE node
     NAME "node-benchmark"
     ARGS
         "platform/node/test/benchmark.js"
diff --git a/include/mbgl/style/conversion/data_driven_property_value.hpp b/include/mbgl/style/conversion/data_driven_property_value.hpp
index 1e54c15a49..186dced0af 100644
--- a/include/mbgl/style/conversion/data_driven_property_value.hpp
+++ b/include/mbgl/style/conversion/data_driven_property_value.hpp
@@ -4,6 +4,8 @@
 #include <mbgl/style/conversion.hpp>
 #include <mbgl/style/conversion/constant.hpp>
 #include <mbgl/style/conversion/function.hpp>
+#include <mbgl/style/conversion/expression.hpp>
+#include <mbgl/style/expression/curve.hpp>
 
 namespace mbgl {
 namespace style {
@@ -20,6 +22,27 @@ struct Converter<DataDrivenPropertyValue<T>> {
                 return {};
             }
             return DataDrivenPropertyValue<T>(*constant);
+        } else if (objectMember(value, "expression")) {
+            optional<std::unique_ptr<Expression>> expression = convert<std::unique_ptr<Expression>>(
+                *objectMember(value, "expression"),
+                error,
+                valueTypeToExpressionType<T>());
+            
+            if (!expression) {
+                return {};
+            }
+            if ((*expression)->isFeatureConstant()) {
+                return DataDrivenPropertyValue<T>(CameraFunction<T>(std::move(*expression)));
+            } else if ((*expression)->isZoomConstant()) {
+                return DataDrivenPropertyValue<T>(SourceFunction<T>(std::move(*expression)));
+            } else {
+                if (!CompositeFunction<T>::Curve::findZoomCurve(expression->get())) {
+                    error = { R"("zoom" expression may only be used as input to a top-level "curve" expression.)" };
+                    return {};
+                }
+            
+                return DataDrivenPropertyValue<T>(CompositeFunction<T>(std::move(*expression)));
+            }
         } else if (!objectMember(value, "property")) {
             optional<CameraFunction<T>> function = convert<CameraFunction<T>>(value, error);
             if (!function) {
diff --git a/include/mbgl/style/conversion/expression.hpp b/include/mbgl/style/conversion/expression.hpp
new file mode 100644
index 0000000000..31c5f629f0
--- /dev/null
+++ b/include/mbgl/style/conversion/expression.hpp
@@ -0,0 +1,35 @@
+#pragma once
+
+#include <memory>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace conversion {
+
+using namespace mbgl::style::expression;
+
+template<> struct Converter<std::unique_ptr<Expression>> {
+    optional<std::unique_ptr<Expression>> operator()(const mbgl::style::conversion::Convertible& value, Error& error, type::Type expected) const {
+        std::vector<ParsingError> errors;
+        ParseResult parsed = ParsingContext(errors, expected).parse(value);
+        if (parsed) {
+            return std::move(*parsed);
+        }
+        std::string combinedError;
+        for (const ParsingError& parsingError : errors) {
+            if (combinedError.size() > 0) {
+                combinedError += "\n";
+            }
+            combinedError += parsingError.key + ": " + parsingError.message;
+        }
+        error = { combinedError };
+        return {};
+    };
+};
+
+} // namespace conversion
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/conversion/get_json_type.hpp b/include/mbgl/style/conversion/get_json_type.hpp
new file mode 100644
index 0000000000..ce1c5d711a
--- /dev/null
+++ b/include/mbgl/style/conversion/get_json_type.hpp
@@ -0,0 +1,38 @@
+#pragma once
+
+#include <string>
+
+namespace mbgl {
+namespace style {
+namespace conversion {
+
+template <class V>
+std::string getJSONType(const V& value) {
+    using namespace mbgl::style::conversion;
+    
+    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/include/mbgl/style/conversion/property_value.hpp b/include/mbgl/style/conversion/property_value.hpp
index c7f971ec91..6cf85019bc 100644
--- a/include/mbgl/style/conversion/property_value.hpp
+++ b/include/mbgl/style/conversion/property_value.hpp
@@ -4,6 +4,8 @@
 #include <mbgl/style/conversion.hpp>
 #include <mbgl/style/conversion/constant.hpp>
 #include <mbgl/style/conversion/function.hpp>
+#include <mbgl/style/conversion/expression.hpp>
+#include <mbgl/style/expression/value.hpp>
 
 namespace mbgl {
 namespace style {
@@ -14,6 +16,17 @@ struct Converter<PropertyValue<T>> {
     optional<PropertyValue<T>> operator()(const Convertible& value, Error& error) const {
         if (isUndefined(value)) {
             return PropertyValue<T>();
+        } else if (isObject(value) && objectMember(value, "expression")) {
+            optional<std::unique_ptr<Expression>> expression = convert<std::unique_ptr<Expression>>(*objectMember(value, "expression"), error, valueTypeToExpressionType<T>());
+            if (!expression) {
+                return {};
+            }
+            if ((*expression)->isFeatureConstant()) {
+                return { CameraFunction<T>(std::move(*expression)) };
+            } else {
+                error = { "data-driven style property not supported " };
+                return {};
+            }
         } else if (isObject(value)) {
             optional<CameraFunction<T>> function = convert<CameraFunction<T>>(value, error);
             if (!function) {
diff --git a/include/mbgl/style/expression/array_assertion.hpp b/include/mbgl/style/expression/array_assertion.hpp
new file mode 100644
index 0000000000..6bf23f14da
--- /dev/null
+++ b/include/mbgl/style/expression/array_assertion.hpp
@@ -0,0 +1,37 @@
+#pragma once
+
+#include <vector>
+#include <memory>
+#include <mbgl/util/optional.hpp>
+#include <mbgl/util/variant.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+
+class ArrayAssertion : public Expression  {
+public:
+    ArrayAssertion(type::Array type_, std::unique_ptr<Expression> input_) :
+        Expression(type_),
+        input(std::move(input_))
+    {}
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext ctx);
+
+    EvaluationResult evaluate(const EvaluationParameters& params) const override;
+    void accept(std::function<void(const Expression*)> visit) const override;
+
+private:
+    std::unique_ptr<Expression> input;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/at.hpp b/include/mbgl/style/expression/at.hpp
new file mode 100644
index 0000000000..6d2c3ea88a
--- /dev/null
+++ b/include/mbgl/style/expression/at.hpp
@@ -0,0 +1,30 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class At : public Expression {
+public:
+    At(std::unique_ptr<Expression> index_, std::unique_ptr<Expression> input_) :
+        Expression(input_->getType().get<type::Array>().itemType),
+        index(std::move(index_)),
+        input(std::move(input_))
+    {}
+    
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext ctx);
+    
+    EvaluationResult evaluate(const EvaluationParameters& params) const override;
+    void accept(std::function<void(const Expression*)>) const override;
+
+private:
+    std::unique_ptr<Expression> index;
+    std::unique_ptr<Expression> input;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/case.hpp b/include/mbgl/style/expression/case.hpp
new file mode 100644
index 0000000000..bb68058141
--- /dev/null
+++ b/include/mbgl/style/expression/case.hpp
@@ -0,0 +1,32 @@
+#pragma once
+
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Case : public Expression {
+public:
+    using Branch = std::pair<std::unique_ptr<Expression>, std::unique_ptr<Expression>>;
+
+    Case(type::Type type_, std::vector<Branch> branches_, std::unique_ptr<Expression> otherwise_)
+        : Expression(type_), branches(std::move(branches_)), otherwise(std::move(otherwise_)) {
+    }
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext ctx);
+
+    EvaluationResult evaluate(const EvaluationParameters& params) const override;
+    void accept(std::function<void(const Expression*)> visit) const override;
+
+private:
+    std::vector<Branch> branches;
+    std::unique_ptr<Expression> otherwise;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/check_subtype.hpp b/include/mbgl/style/expression/check_subtype.hpp
new file mode 100644
index 0000000000..b866b80cd8
--- /dev/null
+++ b/include/mbgl/style/expression/check_subtype.hpp
@@ -0,0 +1,18 @@
+#pragma once
+
+#include <memory>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/util/optional.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+namespace type {
+
+optional<std::string> checkSubtype(const Type& expected, const Type& t);
+
+} // namespace type
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/coalesce.hpp b/include/mbgl/style/expression/coalesce.hpp
new file mode 100644
index 0000000000..eaf9d0c0d1
--- /dev/null
+++ b/include/mbgl/style/expression/coalesce.hpp
@@ -0,0 +1,42 @@
+#pragma once
+
+#include <map>
+#include <mbgl/util/interpolate.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Coalesce : public Expression {
+public:
+    using Args = std::vector<std::unique_ptr<Expression>>;
+    Coalesce(const type::Type& type_, Args args_) :
+        Expression(type_),
+        args(std::move(args_))
+    {}
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext ctx);
+
+
+    EvaluationResult evaluate(const EvaluationParameters& params) const override;
+    
+    void accept(std::function<void(const Expression*)> visit) const override;
+
+    std::size_t getLength() const {
+        return args.size();
+    }
+    
+    Expression* getChild(std::size_t i) const {
+        return args.at(i).get();
+    }
+    
+private:
+    Args args;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/compound_expression.hpp b/include/mbgl/style/expression/compound_expression.hpp
new file mode 100644
index 0000000000..07b6fecb82
--- /dev/null
+++ b/include/mbgl/style/expression/compound_expression.hpp
@@ -0,0 +1,133 @@
+#pragma once
+
+#include <array>
+#include <vector>
+#include <memory>
+#include <mbgl/util/optional.hpp>
+#include <mbgl/util/variant.hpp>
+#include <mbgl/util/color.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/expression/value.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+/*
+    CompoundExpression provides a mechanism for implementing an expression
+    simply by providing a list of pure functions of the form
+    (const T0& arg0, const T1& arg1, ...) -> Result<U> where T0, T1, ..., U are
+    member types of mbgl::style::expression::Value.
+ 
+    The majority of expressions specified in the style-spec are implemented in
+    this fashion (see compound_expression.cpp).
+*/
+
+
+/*
+    Represents the parameter list for an expression that takes an arbitrary
+    number of arguments (of a specific type).
+*/
+struct VarargsType { type::Type type; };
+template <typename T>
+struct Varargs : std::vector<T> { using std::vector<T>::vector; };
+
+namespace detail {
+// Base class for the Signature<Fn> structs that are used to determine the
+// each CompoundExpression definition's type::Type data from the type of its
+// "evaluate" function.
+struct SignatureBase {
+    SignatureBase(type::Type result_, variant<std::vector<type::Type>, VarargsType> params_) :
+        result(std::move(result_)),
+        params(std::move(params_))
+    {}
+    virtual ~SignatureBase() = default;
+    virtual std::unique_ptr<Expression> makeExpression(const std::string& name, std::vector<std::unique_ptr<Expression>>) const = 0;
+    type::Type result;
+    variant<std::vector<type::Type>, VarargsType> params;
+};
+} // namespace detail
+
+
+/*
+    Common base class for CompoundExpression<Signature> instances.  Used to
+    allow downcasting (and access to things like name & parameter list) during
+    an Expression tree traversal.
+*/
+class CompoundExpressionBase : public Expression {
+public:
+    CompoundExpressionBase(std::string name_, const detail::SignatureBase& signature) :
+        Expression(signature.result),
+        name(std::move(name_)),
+        params(signature.params)
+    {}
+
+    std::string getName() const { return name; }
+    optional<std::size_t> getParameterCount() const {
+        return params.match(
+            [&](const VarargsType&) { return optional<std::size_t>(); },
+            [&](const std::vector<type::Type>& p) -> optional<std::size_t> { return p.size(); }
+        );
+    }
+    
+private:
+    std::string name;
+    variant<std::vector<type::Type>, VarargsType> params;
+};
+
+template <typename Signature>
+class CompoundExpression : public CompoundExpressionBase {
+public:
+    using Args = typename Signature::Args;
+    
+    CompoundExpression(const std::string& name_,
+                       Signature signature_,
+                       typename Signature::Args args_) :
+        CompoundExpressionBase(name_, signature_),
+        signature(signature_),
+        args(std::move(args_))
+    {}
+    
+    EvaluationResult evaluate(const EvaluationParameters& evaluationParams) const override {
+        return signature.apply(evaluationParams, args);
+    }
+    
+    void accept(std::function<void(const Expression*)> visitor) const override {
+        visitor(this);
+        for (const std::unique_ptr<Expression>& e : args) {
+            e->accept(visitor);
+        }
+    }
+    
+private:
+    Signature signature;
+    typename Signature::Args args;
+};
+
+/*
+    Holds the map of expression name => implementation (which is just one or
+    more evaluation functions, each wrapped in a Signature struct).
+*/
+struct CompoundExpressionRegistry {
+    using Definition = std::vector<std::unique_ptr<detail::SignatureBase>>;
+    static std::unordered_map<std::string, Definition> definitions;
+};
+
+ParseResult parseCompoundExpression(const std::string name, const mbgl::style::conversion::Convertible& value, ParsingContext ctx);
+
+ParseResult createCompoundExpression(const std::string& name,
+                                     const CompoundExpressionRegistry::Definition& definition,
+                                     std::vector<std::unique_ptr<Expression>> args,
+                                     ParsingContext ctx);
+    
+ParseResult createCompoundExpression(const std::string& name,
+                                     std::vector<std::unique_ptr<Expression>> args,
+                                     ParsingContext ctx);
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/curve.hpp b/include/mbgl/style/expression/curve.hpp
new file mode 100644
index 0000000000..494d256415
--- /dev/null
+++ b/include/mbgl/style/expression/curve.hpp
@@ -0,0 +1,212 @@
+#pragma once
+
+#include <map>
+#include <mbgl/util/interpolate.hpp>
+#include <mbgl/util/range.hpp>
+#include <mbgl/util/unitbezier.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/coalesce.hpp>
+#include <mbgl/style/expression/let.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class StepInterpolator {
+public:
+    double interpolationFactor(const Range<double>&, const double&) const {
+        return 0;
+    }
+    
+};
+
+class ExponentialInterpolator {
+public:
+    ExponentialInterpolator(double base_) : base(base_) {}
+
+    double base;
+    
+    double interpolationFactor(const Range<double>& inputLevels, const double& input) const {
+        return util::interpolationFactor(base,
+                                         Range<float> {
+                                            static_cast<float>(inputLevels.min),
+                                            static_cast<float>(inputLevels.max)
+                                         },
+                                         input);
+    }
+};
+
+class CubicBezierInterpolator {
+public:
+    CubicBezierInterpolator(double x1_, double y1_, double x2_, double y2_) : ub(x1_, y1_, x2_, y2_) {}
+    
+    double interpolationFactor(const Range<double>& inputLevels, const double& input) const {
+        return ub.solve(input / (inputLevels.max - inputLevels.min), 1e-6);
+    }
+    
+    util::UnitBezier ub;
+};
+
+
+ParseResult parseCurve(const mbgl::style::conversion::Convertible& value, ParsingContext ctx);
+
+
+template <typename T>
+class Curve : public Expression {
+public:
+    using Interpolator = std::conditional_t<
+        util::Interpolatable<T>::value,
+        variant<StepInterpolator,
+                ExponentialInterpolator,
+                CubicBezierInterpolator>,
+        variant<StepInterpolator>>;
+    
+    Curve(const type::Type& type_,
+          Interpolator interpolator_,
+          std::unique_ptr<Expression> input_,
+          std::map<double, std::unique_ptr<Expression>> stops_
+    ) : Expression(type_),
+        interpolator(std::move(interpolator_)),
+        input(std::move(input_)),
+        stops(std::move(stops_))
+    {}
+    
+    EvaluationResult evaluate(const EvaluationParameters& params) const override {
+        const EvaluationResult evaluatedInput = input->evaluate(params);
+        if (!evaluatedInput) { return evaluatedInput.error(); }
+        float x = *fromExpressionValue<float>(*evaluatedInput);
+        
+        if (stops.empty()) {
+            return EvaluationError { "No stops in exponential 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 {
+            float t = interpolationFactor({ std::prev(it)->first, it->first }, x);
+            
+            if (t == 0.0f) {
+                return std::prev(it)->second->evaluate(params);
+            }
+            if (t == 1.0f) {
+                return it->second->evaluate(params);
+            }
+            
+            EvaluationResult lower = std::prev(it)->second->evaluate(params);
+            if (!lower) {
+                return lower.error();
+            }
+            EvaluationResult upper = it->second->evaluate(params);
+            if (!upper) {
+                return upper.error();
+            }
+
+            return interpolate({*lower, *upper}, t);
+        }
+        
+    }
+    
+    void accept(std::function<void(const Expression*)> visit) const override {
+        visit(this);
+        input->accept(visit);
+        
+        for (auto it = stops.begin(); it != stops.end(); it++) {
+            it->second->accept(visit);
+        }
+    }
+    
+    static optional<Curve*> findZoomCurve(expression::Expression* e) {
+        if (auto curve = dynamic_cast<Curve*>(e)) {
+            auto z = dynamic_cast<CompoundExpressionBase*>(curve->input.get());
+            if (z && z->getName() == "zoom") {
+                return {curve};
+            } else {
+                return optional<Curve*>();
+            }
+        } else if (auto let = dynamic_cast<Let*>(e)) {
+            return findZoomCurve(let->getResult());
+        } else if (auto coalesce = dynamic_cast<Coalesce*>(e)) {
+            std::size_t length = coalesce->getLength();
+            for (std::size_t i = 0; i < length; i++) {
+                optional<Curve*> childCurve = findZoomCurve(coalesce->getChild(i));
+                if (!childCurve) {
+                    continue;
+                } else {
+                    return childCurve;
+                }
+            }
+        }
+        
+        return optional<Curve*>();
+    }
+
+    // Return the smallest range of stops that covers the interval [lower, upper]
+    Range<float> getCoveringStops(const double lower, const double upper) const {
+        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)
+        };
+    }
+    
+    double interpolationFactor(const Range<double>& inputLevels, const double& inputValue) const {
+        return interpolator.match(
+            [&](const auto& interp) { return interp.interpolationFactor(inputLevels, inputValue); }
+        );
+    }
+    
+private:
+    template <typename OutputType = T>
+    static EvaluationResult interpolate(const Range<Value>&, const double&,
+                                        typename std::enable_if<!util::Interpolatable<OutputType>::value>::type* = nullptr) {
+        // Assume that Curve::evaluate() will always short circuit due to
+        // interpolationFactor always returning 0.
+        assert(false);
+        return Null;
+    }
+    
+    template <typename OutputType = T>
+    static EvaluationResult interpolate(const Range<Value>& outputs, const double& t,
+                                        typename std::enable_if<util::Interpolatable<OutputType>::value>::type* = nullptr) {
+        optional<T> lower = fromExpressionValue<T>(outputs.min);
+        if (!lower) {
+            // TODO - refactor fromExpressionValue to return EvaluationResult<T> so as to
+            // consolidate DRY up producing this error message.
+            return EvaluationError {
+                "Expected value to be of type " + toString(valueTypeToExpressionType<T>()) +
+                ", but found " + toString(typeOf(outputs.min)) + " instead."
+            };
+        }
+        const optional<T> upper = fromExpressionValue<T>(outputs.max);
+        if (!upper) {
+            return EvaluationError {
+                "Expected value to be of type " + toString(valueTypeToExpressionType<T>()) +
+                ", but found " + toString(typeOf(outputs.min)) + " instead."
+            };
+        }
+        T result = util::interpolate(*lower, *upper, t);
+        return toExpressionValue(result);
+    }
+    
+
+    const Interpolator interpolator;
+    const std::unique_ptr<Expression> input;
+    const std::map<double, std::unique_ptr<Expression>> stops;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/expression.hpp b/include/mbgl/style/expression/expression.hpp
new file mode 100644
index 0000000000..9441c0e818
--- /dev/null
+++ b/include/mbgl/style/expression/expression.hpp
@@ -0,0 +1,125 @@
+#pragma once
+
+#include <array>
+#include <vector>
+#include <memory>
+#include <mbgl/util/optional.hpp>
+#include <mbgl/util/variant.hpp>
+#include <mbgl/util/color.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/expression/value.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+
+namespace mbgl {
+
+class GeometryTileFeature;
+
+namespace style {
+namespace expression {
+
+struct EvaluationError {
+    std::string message;
+};
+
+struct EvaluationParameters {
+    EvaluationParameters(float zoom_) : zoom(zoom_), feature(nullptr) {}
+    EvaluationParameters(GeometryTileFeature const * feature_) : zoom(optional<float>()), feature(feature_) {}
+    EvaluationParameters(float zoom_, GeometryTileFeature const * feature_) :
+        zoom(zoom_), feature(feature_)
+    {}
+    
+    optional<float> zoom;
+    GeometryTileFeature const * feature;
+};
+
+template<typename T>
+class Result : private variant<EvaluationError, T> {
+public:
+    using variant<EvaluationError, T>::variant;
+    using Value = T;
+    
+    explicit operator bool () const {
+        return this->template is<T>();
+    }
+    
+    // optional does some type trait magic for this one, so this might
+    // be problematic as is.
+    const T* operator->() const {
+        assert(this->template is<T>());
+        return std::addressof(this->template get<T>());
+    }
+    
+    T* operator->() {
+        assert(this->template is<T>());
+        return std::addressof(this->template get<T>());
+    }
+    
+    T& operator*() {
+        assert(this->template is<T>());
+        return this->template get<T>();
+    }
+    
+    const T& operator*() const {
+        assert(this->template is<T>());
+        return this->template get<T>();
+    }
+    
+    const EvaluationError& error() const {
+        assert(this->template is<EvaluationError>());
+        return this->template get<EvaluationError>();
+    }
+};
+
+struct EvaluationResult : public Result<Value> {
+    using Result::Result;
+    
+    EvaluationResult(const std::array<double, 4>& arr) :
+        Result(toExpressionValue(arr))
+    {}
+    
+    // used only for the special (private) "error" expression
+    EvaluationResult(const type::ErrorType&) {
+        assert(false);
+    }
+};
+
+/*
+    Expression is an abstract class that serves as an interface and base class
+    for particular expression implementations.
+
+    CompoundExpression implements the majority of expressions in the spec by
+    inferring the argument and output from a simple function (const T0& arg0,
+    const T1& arg1, ...) -> Result<U> where T0, T1, ..., U are member types of
+    mbgl::style::expression::Value.
+    
+    The other Expression subclasses (Let, Curve, Match, etc.) exist in order to
+    implement expressions that need specialized parsing, type checking, or
+    evaluation logic that can't be handled by CompoundExpression's inference
+    mechanism.
+    
+    Each Expression subclass has an accompanying 
+    template <class V> ParseResult ParseXxxx::parse(const V&, ParsingContext),
+    found in style/expression/parse/xxxx.hpp, which handles parsing a style-spec
+    JSON representation of the expression.
+*/
+class Expression {
+public:
+    Expression(type::Type type_) : type(std::move(type_)) {}
+    virtual ~Expression() = default;
+    
+    virtual EvaluationResult evaluate(const EvaluationParameters& params) const = 0;
+    
+    virtual void accept(std::function<void(const Expression*)>) const = 0;
+
+    bool isFeatureConstant() const;
+    bool isZoomConstant() const;
+    EvaluationResult evaluate(float z, const Feature& feature) const;
+    type::Type getType() const { return type; };
+    
+private:
+    type::Type type;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/let.hpp b/include/mbgl/style/expression/let.hpp
new file mode 100644
index 0000000000..5e6e3a1696
--- /dev/null
+++ b/include/mbgl/style/expression/let.hpp
@@ -0,0 +1,55 @@
+#pragma once
+
+#include <map>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Let : public Expression {
+public:
+    using Bindings = std::map<std::string, std::shared_ptr<Expression>>;
+    
+    Let(Bindings bindings_, std::unique_ptr<Expression> result_) :
+        Expression(result_->getType()),
+        bindings(std::move(bindings_)),
+        result(std::move(result_))
+    {}
+    
+    static ParseResult parse(const mbgl::style::conversion::Convertible&, ParsingContext);
+    
+    EvaluationResult evaluate(const EvaluationParameters& params) const override;
+    void accept(std::function<void(const Expression*)>) const override;
+    
+    Expression* getResult() const {
+        return result.get();
+    }
+
+private:
+    Bindings bindings;
+    std::unique_ptr<Expression> result;
+};
+
+class Var : public Expression {
+public:
+    Var(std::string name_, std::shared_ptr<Expression> value_) :
+        Expression(value_->getType()),
+        name(std::move(name_)),
+        value(value_)
+    {}
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible&, ParsingContext);
+
+    EvaluationResult evaluate(const EvaluationParameters& params) const override;
+    void accept(std::function<void(const Expression*)>) const override;
+
+private:
+    std::string name;
+    std::shared_ptr<Expression> value;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/literal.hpp b/include/mbgl/style/expression/literal.hpp
new file mode 100644
index 0000000000..18c2b56e92
--- /dev/null
+++ b/include/mbgl/style/expression/literal.hpp
@@ -0,0 +1,39 @@
+#pragma once
+
+#include <vector>
+#include <memory>
+#include <mbgl/util/optional.hpp>
+#include <mbgl/util/variant.hpp>
+#include <mbgl/util/color.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/expression/value.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Literal : public Expression {
+public:
+    Literal(Value value_) : Expression(typeOf(value_)), value(value_) {}
+    Literal(type::Array type_, std::vector<Value> value_) : Expression(type_), value(value_) {}
+    EvaluationResult evaluate(const EvaluationParameters&) const override {
+        return value;
+    }
+    
+    static ParseResult parse(const mbgl::style::conversion::Convertible&, ParsingContext);
+
+    void accept(std::function<void(const Expression*)> visit) const override {
+        visit(this);
+    }
+    
+private:
+    Value value;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/match.hpp b/include/mbgl/style/expression/match.hpp
new file mode 100644
index 0000000000..3038097868
--- /dev/null
+++ b/include/mbgl/style/expression/match.hpp
@@ -0,0 +1,44 @@
+#pragma once
+
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+using InputType = variant<int64_t, std::string>;
+
+template <typename T>
+class Match : public Expression {
+public:
+    using Branches = std::unordered_map<T, std::shared_ptr<Expression>>;
+
+    Match(type::Type type_,
+          std::unique_ptr<Expression> input_,
+          Branches branches_,
+          std::unique_ptr<Expression> otherwise_
+    ) : Expression(type_),
+        input(std::move(input_)),
+        branches(std::move(branches_)),
+        otherwise(std::move(otherwise_))
+    {}
+
+    void accept(std::function<void(const Expression*)> visit) const override;
+
+    EvaluationResult evaluate(const EvaluationParameters& params) const override;
+    
+private:
+    
+    std::unique_ptr<Expression> input;
+    Branches branches;
+    std::unique_ptr<Expression> otherwise;
+};
+
+ParseResult parseMatch(const mbgl::style::conversion::Convertible& value, ParsingContext ctx);
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/parsing_context.hpp b/include/mbgl/style/expression/parsing_context.hpp
new file mode 100644
index 0000000000..5cdde71346
--- /dev/null
+++ b/include/mbgl/style/expression/parsing_context.hpp
@@ -0,0 +1,117 @@
+#pragma once
+
+#include <map>
+#include <string>
+#include <vector>
+#include <mbgl/util/optional.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/conversion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Expression;
+
+struct ParsingError {
+    std::string message;
+    std::string key;
+};
+
+using ParseResult = optional<std::unique_ptr<Expression>>;
+
+namespace detail {
+
+struct Scope {
+    Scope(const std::map<std::string, std::shared_ptr<Expression>>& bindings_, std::shared_ptr<Scope> parent_ = nullptr) :
+        bindings(bindings_),
+        parent(std::move(parent_))
+    {}
+
+    const std::map<std::string, std::shared_ptr<Expression>>& bindings;
+    std::shared_ptr<Scope> parent;
+    
+    optional<std::shared_ptr<Expression>> get(const std::string& name) {
+        auto it = bindings.find(name);
+        if (it != bindings.end()) {
+            return {it->second};
+        } else if (parent) {
+            return parent->get(name);
+        } else {
+            return optional<std::shared_ptr<Expression>>();
+        }
+    }
+};
+
+} // namespace detail
+
+class ParsingContext {
+public:
+    ParsingContext(std::vector<ParsingError>& errors_, optional<type::Type> expected_ = {})
+        : errors(errors_),
+          expected(std::move(expected_))
+    {}
+
+    ParsingContext concat(std::size_t index_, optional<type::Type> expected_ = {}) {
+        return ParsingContext(key + "[" + std::to_string(index_) + "]",
+                              errors,
+                              std::move(expected_),
+                              scope);
+    }
+    
+    ParsingContext concat(std::size_t index_,
+                          optional<type::Type> expected_,
+                          const std::map<std::string, std::shared_ptr<Expression>>& bindings) {
+        return ParsingContext(key + "[" + std::to_string(index_) + "]",
+                              errors,
+                              std::move(expected_),
+                              std::make_shared<detail::Scope>(bindings, scope));
+
+    }
+    
+    /*
+        Parse the given style-spec JSON value into an Expression object.
+        Specifically, this function is responsible for determining the expression
+        type (either Literal, or the one named in value[0]) and dispatching to the
+        appropriate ParseXxxx::parse(const V&, ParsingContext) method.
+    */
+    ParseResult parse(const mbgl::style::conversion::Convertible& value);
+    
+    /*
+        Check whether `t` is a subtype of `expected`, collecting an error if not.
+     */
+    optional<std::string> checkType(const type::Type& t);
+    
+    optional<std::shared_ptr<Expression>> getBinding(const std::string name) {
+        if (!scope) return optional<std::shared_ptr<Expression>>();
+        return scope->get(name);
+    }
+
+    void error(std::string message) {
+        errors.push_back({message, key});
+    }
+    
+    void  error(std::string message, std::size_t child) {
+        errors.push_back({message, key + "[" + std::to_string(child) + "]"});
+    }
+
+    std::string key;
+    std::vector<ParsingError>& errors;
+    optional<type::Type> expected;
+    std::shared_ptr<detail::Scope> scope;
+
+private:
+    ParsingContext(std::string key_,
+                   std::vector<ParsingError>& errors_,
+                   optional<type::Type> expected_,
+                   std::shared_ptr<detail::Scope> scope_)
+        : key(std::move(key_)),
+          errors(errors_),
+          expected(std::move(expected_)),
+          scope(scope_)
+    {}
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/type.hpp b/include/mbgl/style/expression/type.hpp
new file mode 100644
index 0000000000..a730b884a3
--- /dev/null
+++ b/include/mbgl/style/expression/type.hpp
@@ -0,0 +1,113 @@
+#pragma once
+
+#include <unordered_map>
+#include <vector>
+#include <mbgl/util/optional.hpp>
+#include <mbgl/util/variant.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+namespace type {
+
+template <class T>
+std::string toString(const T& t);
+
+struct NullType {
+    constexpr NullType() = default;
+    std::string getName() const { return "null"; }
+    bool operator==(const NullType&) const { return true; }
+};
+
+struct NumberType {
+    constexpr NumberType() = default;
+    std::string getName() const { return "number"; }
+    bool operator==(const NumberType&) const { return true; }
+};
+
+struct BooleanType {
+    constexpr BooleanType() = default;
+    std::string getName() const { return "boolean"; }
+    bool operator==(const BooleanType&) const { return true; }
+};
+
+struct StringType {
+    constexpr StringType() = default;
+    std::string getName() const { return "string"; }
+    bool operator==(const StringType&) const { return true; }
+};
+
+struct ColorType {
+    constexpr ColorType() = default;
+    std::string getName() const { return "color"; }
+    bool operator==(const ColorType&) const { return true; }
+};
+
+struct ObjectType {
+    constexpr ObjectType() = default;
+    std::string getName() const { return "object"; }
+    bool operator==(const ObjectType&) const { return true; }
+};
+
+struct ErrorType {
+    constexpr ErrorType() = default;
+    std::string getName() const { return "error"; }
+    bool operator==(const ErrorType&) const { return true; }
+};
+
+struct ValueType {
+    constexpr ValueType() = default;
+    std::string getName() const { return "value"; }
+    bool operator==(const ValueType&) const { return true; }
+};
+
+constexpr NullType Null;
+constexpr NumberType Number;
+constexpr StringType String;
+constexpr BooleanType Boolean;
+constexpr ColorType Color;
+constexpr ValueType Value;
+constexpr ObjectType Object;
+constexpr ErrorType Error;
+
+struct Array;
+
+using Type = variant<
+    NullType,
+    NumberType,
+    BooleanType,
+    StringType,
+    ColorType,
+    ObjectType,
+    ValueType,
+    mapbox::util::recursive_wrapper<Array>,
+    ErrorType>;
+
+struct Array {
+    Array(Type itemType_) : itemType(std::move(itemType_)) {}
+    Array(Type itemType_, std::size_t N_) : itemType(std::move(itemType_)), N(N_) {}
+    Array(Type itemType_, optional<std::size_t> N_) : itemType(std::move(itemType_)), N(std::move(N_)) {}
+    std::string getName() const {
+        if (N) {
+            return "array<" + toString(itemType) + ", " + std::to_string(*N) + ">";
+        } else if (itemType == Value) {
+            return "array";
+        } else {
+            return "array<" + toString(itemType) + ">";
+        }
+    }
+
+    bool operator==(const Array& rhs) const { return itemType == rhs.itemType && N == rhs.N; }
+    
+    Type itemType;
+    optional<std::size_t> N;
+};
+    
+template <class T>
+std::string toString(const T& type) { return type.match([&] (const auto& t) { return t.getName(); }); }
+
+} // namespace type
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/value.hpp b/include/mbgl/style/expression/value.hpp
new file mode 100644
index 0000000000..18f4e3ba99
--- /dev/null
+++ b/include/mbgl/style/expression/value.hpp
@@ -0,0 +1,152 @@
+#pragma once
+
+#include <array>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/position.hpp>
+#include <mbgl/style/types.hpp>
+#include <mbgl/util/color.hpp>
+#include <mbgl/util/enum.hpp>
+#include <mbgl/util/feature.hpp>
+#include <mbgl/util/variant.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+struct Value;
+
+using ValueBase = variant<
+    NullValue,
+    bool,
+    double,
+    std::string,
+    mbgl::Color,
+    mapbox::util::recursive_wrapper<std::vector<Value>>,
+    mapbox::util::recursive_wrapper<std::unordered_map<std::string, Value>>>;
+struct Value : ValueBase {
+    using ValueBase::ValueBase;
+    
+    // Javascript's Number.MAX_SAFE_INTEGER
+    static uint64_t maxSafeInteger() { return 9007199254740991ULL; }
+    
+    static bool isSafeInteger(uint64_t x) { return x <= maxSafeInteger(); };
+    static bool isSafeInteger(int64_t x) {
+        return static_cast<uint64_t>(x > 0 ? x : -x) <= maxSafeInteger();
+    }
+    static bool isSafeInteger(double x) {
+        return static_cast<uint64_t>(x > 0 ? x : -x) <= maxSafeInteger();
+    }
+    
+};
+
+constexpr NullValue Null = NullValue();
+
+type::Type typeOf(const Value& value);
+std::string stringify(const Value& value);
+
+/*
+  Returns a Type object representing the expression type that corresponds to
+  the value type T.  (Specialized for primitives and specific array types in
+  the .cpp.)
+*/
+template <typename T>
+type::Type valueTypeToExpressionType();
+
+/*
+  Conversions between style value types and expression::Value
+*/
+
+// no-op overloads
+Value toExpressionValue(const Value&);
+
+// T = Value (just wrap in optional)
+template <typename T>
+std::enable_if_t<std::is_same<T, Value>::value,
+optional<T>> fromExpressionValue(const Value& v)
+{
+    return optional<T>(v);
+}
+
+// T = member type of Value
+template <typename T>
+std::enable_if_t< std::is_convertible<T, Value>::value && !std::is_same<T, Value>::value,
+optional<T>> fromExpressionValue(const Value& v)
+{
+    return v.template is<T>() ? v.template get<T>() : optional<T>();
+}
+
+// real conversions
+template <typename T, typename Enable = std::enable_if_t< !std::is_convertible<T, Value>::value >>
+Value toExpressionValue(const T& value);
+
+template <typename T>
+std::enable_if_t< !std::is_convertible<T, Value>::value,
+optional<T>> fromExpressionValue(const Value& v);
+
+
+
+template <class T, class Enable = void>
+struct ValueConverter {
+    using ExpressionType = T;
+    
+    static Value toExpressionValue(const T& value) {
+        return Value(value);
+    }
+    static optional<T> fromExpressionValue(const Value& value) {
+        return value.template is<T>() ? value.template get<T>() : optional<T>();
+    }
+};
+
+template <>
+struct ValueConverter<float> {
+    using ExpressionType = double;
+    static type::Type expressionType() { return type::Number; }
+    static Value toExpressionValue(const float& value);
+    static optional<float> fromExpressionValue(const Value& value);
+};
+
+template<>
+struct ValueConverter<mbgl::Value> {
+    static Value toExpressionValue(const mbgl::Value& value);
+};
+
+template <typename T, std::size_t N>
+struct ValueConverter<std::array<T, N>> {
+    using ExpressionType = std::vector<Value>;
+    static type::Type expressionType() {
+        return type::Array(valueTypeToExpressionType<T>(), N);
+    }
+    static Value toExpressionValue(const std::array<T, N>& value);
+    static optional<std::array<T, N>> fromExpressionValue(const Value& value);
+};
+
+template <typename T>
+struct ValueConverter<std::vector<T>> {
+    using ExpressionType = std::vector<Value>;
+    static type::Type expressionType() {
+        return type::Array(valueTypeToExpressionType<T>());
+    }
+    static Value toExpressionValue(const std::vector<T>& value);
+    static optional<std::vector<T>> fromExpressionValue(const Value& value);
+};
+
+template <>
+struct ValueConverter<Position> {
+    using ExpressionType = std::vector<Value>;
+    static type::Type expressionType() { return type::Array(type::Number, 3); }
+    static Value toExpressionValue(const mbgl::style::Position& value);
+    static optional<Position> fromExpressionValue(const Value& v);
+};
+
+template <typename T>
+struct ValueConverter<T, std::enable_if_t< std::is_enum<T>::value >> {
+    using ExpressionType = std::string;
+    static type::Type expressionType() { return type::String; }
+    static Value toExpressionValue(const T& value);
+    static optional<T> fromExpressionValue(const Value& value);
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/function/camera_function.hpp b/include/mbgl/style/function/camera_function.hpp
index 7fde365b3d..0dc962fb3a 100644
--- a/include/mbgl/style/function/camera_function.hpp
+++ b/include/mbgl/style/function/camera_function.hpp
@@ -1,5 +1,9 @@
 #pragma once
 
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/curve.hpp>
+#include <mbgl/style/expression/value.hpp>
+#include <mbgl/style/function/convert.hpp>
 #include <mbgl/style/function/exponential_stops.hpp>
 #include <mbgl/style/function/interval_stops.hpp>
 #include <mbgl/util/interpolate.hpp>
@@ -11,6 +15,8 @@ namespace style {
 template <class T>
 class CameraFunction {
 public:
+    using Curve = expression::Curve<typename expression::ValueConverter<T>::ExpressionType>;
+    
     using Stops = std::conditional_t<
         util::Interpolatable<T>::value,
         variant<
@@ -18,15 +24,38 @@ public:
             IntervalStops<T>>,
         variant<
             IntervalStops<T>>>;
+    
+    CameraFunction(std::unique_ptr<expression::Expression> expression_)
+        : expression(std::move(expression_)),
+          zoomCurve(*Curve::findZoomCurve(expression.get()))
+    {
+        assert(!expression->isZoomConstant());
+        assert(expression->isFeatureConstant());
+    }
 
     CameraFunction(Stops stops_)
-        : stops(std::move(stops_)) {
-    }
+        : stops(std::move(stops_)),
+          expression(stops.match([&] (const auto& s) {
+            return expression::Convert::toExpression(s);
+          })),
+          zoomCurve(*Curve::findZoomCurve(expression.get()))
+    {}
 
     T evaluate(float zoom) const {
-        return stops.match([&] (const auto& s) {
-            return s.evaluate(zoom).value_or(T());
-        });
+        const expression::EvaluationResult result = expression->evaluate(expression::EvaluationParameters(zoom, nullptr));
+        if (result) {
+           const optional<T> typed = expression::fromExpressionValue<T>(*result);
+           return typed ? *typed : T();
+        }
+        return T();
+    }
+    
+    float interpolationFactor(const Range<float>& inputLevels, const float& inputValue) const {
+        return zoomCurve->interpolationFactor(Range<double> { inputLevels.min, inputLevels.max }, inputValue);
+    }
+    
+    Range<float> getCoveringStops(const float lower, const float upper) const {
+        return zoomCurve->getCoveringStops(lower, upper);
     }
     
     friend bool operator==(const CameraFunction& lhs,
@@ -34,8 +63,14 @@ public:
         return lhs.stops == rhs.stops;
     }
 
-    Stops stops;
     bool useIntegerZoom = false;
+    
+    // retained for compatibility with pre-expression function API
+    Stops stops;
+
+private:
+    std::shared_ptr<expression::Expression> expression;
+    const Curve* zoomCurve;
 };
 
 } // namespace style
diff --git a/include/mbgl/style/function/composite_function.hpp b/include/mbgl/style/function/composite_function.hpp
index 7b524b6021..57c1fe18cb 100644
--- a/include/mbgl/style/function/composite_function.hpp
+++ b/include/mbgl/style/function/composite_function.hpp
@@ -1,5 +1,9 @@
 #pragma once
 
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/curve.hpp>
+#include <mbgl/style/expression/value.hpp>
+#include <mbgl/style/function/convert.hpp>
 #include <mbgl/style/function/composite_exponential_stops.hpp>
 #include <mbgl/style/function/composite_interval_stops.hpp>
 #include <mbgl/style/function/composite_categorical_stops.hpp>
@@ -43,87 +47,51 @@ public:
             CompositeIntervalStops<T>,
             CompositeCategoricalStops<T>>>;
 
-    CompositeFunction(std::string property_, Stops stops_, optional<T> defaultValue_ = {})
-        : property(std::move(property_)),
-          stops(std::move(stops_)),
-          defaultValue(std::move(defaultValue_)) {
-    }
-
-    struct CoveringRanges {
-        float zoom;
-        Range<float> coveringZoomRange;
-        Range<InnerStops> coveringStopsRange;
-    };
-
-    // Return the relevant stop zoom values and inner stops that bracket a given zoom level. This
-    // is the first step toward evaluating the function, and is used for in the course of both partial
-    // evaluation of data-driven paint properties, and full evaluation of data-driven layout properties.
-    CoveringRanges coveringRanges(float zoom) const {
-        return stops.match(
-            [&] (const auto& s) {
-                assert(!s.stops.empty());
-                auto minIt = s.stops.lower_bound(zoom);
-                auto maxIt = s.stops.upper_bound(zoom);
-                
-                // lower_bound yields first element >= zoom, but we want the *last*
-                // element <= zoom, so if we found a stop > zoom, back up by one.
-                if (minIt != s.stops.begin() && minIt != s.stops.end() && minIt->first > zoom) {
-                    minIt--;
-                }
-                
-                return CoveringRanges {
-                    zoom,
-                    Range<float> {
-                        minIt == s.stops.end() ? s.stops.rbegin()->first : minIt->first,
-                        maxIt == s.stops.end() ? s.stops.rbegin()->first : maxIt->first
-                    },
-                    Range<InnerStops> {
-                        s.innerStops(minIt == s.stops.end() ? s.stops.rbegin()->second : minIt->second),
-                        s.innerStops(maxIt == s.stops.end() ? s.stops.rbegin()->second : maxIt->second)
-                    }
-                };
-            }
-        );
-    }
+    using Curve = expression::Curve<typename expression::ValueConverter<T>::ExpressionType>;
 
-    // Given a range of zoom values (typically two adjacent integer zoom levels, e.g. 5.0 and 6.0),
-    // return the covering ranges for both. This is used in the course of partial evaluation for
-    // data-driven paint properties.
-    Range<CoveringRanges> rangeOfCoveringRanges(Range<float> zoomRange) {
-        return Range<CoveringRanges> {
-            coveringRanges(zoomRange.min),
-            coveringRanges(zoomRange.max)
-        };
+    CompositeFunction(std::unique_ptr<expression::Expression> expression_)
+    :   expression(std::move(expression_)),
+        zoomCurve(*Curve::findZoomCurve(expression.get()))
+    {
+        assert(!expression->isZoomConstant());
+        assert(!expression->isFeatureConstant());
     }
 
-    // Given the covering ranges for range of zoom values (typically two adjacent integer zoom levels,
-    // e.g. 5.0 and 6.0), and a feature, return the results of fully evaluating the function for that
-    // feature at each of the two zoom levels. These two results are what go into the paint vertex buffers
-    // for vertices associated with this feature. The shader will interpolate between them at render time.
+    CompositeFunction(std::string property_, Stops stops_, optional<T> defaultValue_ = {})
+    :   property(std::move(property_)),
+        stops(std::move(stops_)),
+        defaultValue(std::move(defaultValue_)),
+        expression(stops.match([&] (const auto& s) {
+            return expression::Convert::toExpression(property, s, defaultValue);
+        })),
+        zoomCurve(*Curve::findZoomCurve(expression.get()))
+    {}
+
+    // Return the range obtained by evaluating the function at each of the zoom levels in zoomRange
     template <class Feature>
-    Range<T> evaluate(const Range<CoveringRanges>& ranges, const Feature& feature, T finalDefaultValue) {
-        optional<Value> value = feature.getValue(property);
-        if (!value) {
-            return Range<T> {
-                defaultValue.value_or(finalDefaultValue),
-                defaultValue.value_or(finalDefaultValue)
-            };
-        }
+    Range<T> evaluate(const Range<float>& zoomRange, const Feature& feature, T finalDefaultValue) {
         return Range<T> {
-            evaluateFinal(ranges.min, *value, finalDefaultValue),
-            evaluateFinal(ranges.max, *value, finalDefaultValue)
+            evaluate(zoomRange.min, feature, finalDefaultValue),
+            evaluate(zoomRange.max, feature, finalDefaultValue)
         };
     }
 
-    // Fully evaluate the function for a zoom value and feature. This is used when evaluating data-driven
-    // layout properties.
     template <class Feature>
     T evaluate(float zoom, const Feature& feature, T finalDefaultValue) const {
-        optional<Value> value = feature.getValue(property);
-        if (!value) {
-            return defaultValue.value_or(finalDefaultValue);
+        const expression::EvaluationResult result = expression->evaluate(expression::EvaluationParameters({zoom}, &feature));
+        if (result) {
+            const optional<T> typed = expression::fromExpressionValue<T>(*result);
+            return typed ? *typed : finalDefaultValue;
         }
-        return evaluateFinal(coveringRanges(zoom), *value, finalDefaultValue);
+        return finalDefaultValue;
+    }
+    
+    float interpolationFactor(const Range<float>& inputLevels, const float& inputValue) const {
+        return zoomCurve->interpolationFactor(Range<double> { inputLevels.min, inputLevels.max }, inputValue);
+    }
+    
+    Range<float> getCoveringStops(const float lower, const float upper) const {
+        return zoomCurve->getCoveringStops(lower, upper);
     }
 
     friend bool operator==(const CompositeFunction& lhs,
@@ -136,17 +104,10 @@ public:
     Stops stops;
     optional<T> defaultValue;
     bool useIntegerZoom = false;
-
+    
 private:
-    T evaluateFinal(const CoveringRanges& ranges, const Value& value, T finalDefaultValue) const {
-        auto eval = [&] (const auto& s) {
-            return s.evaluate(value).value_or(defaultValue.value_or(finalDefaultValue));
-        };
-        return util::interpolate(
-            ranges.coveringStopsRange.min.match(eval),
-            ranges.coveringStopsRange.max.match(eval),
-            util::interpolationFactor(1.0f, ranges.coveringZoomRange, ranges.zoom));
-    }
+    std::shared_ptr<expression::Expression> expression;
+    const Curve* zoomCurve;
 };
 
 } // namespace style
diff --git a/include/mbgl/style/function/convert.hpp b/include/mbgl/style/function/convert.hpp
new file mode 100644
index 0000000000..1082b06971
--- /dev/null
+++ b/include/mbgl/style/function/convert.hpp
@@ -0,0 +1,363 @@
+#pragma once
+
+#include <mbgl/util/enum.hpp>
+#include <mbgl/style/types.hpp>
+#include <mbgl/style/expression/array_assertion.hpp>
+#include <mbgl/style/expression/case.hpp>
+#include <mbgl/style/expression/coalesce.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/curve.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/literal.hpp>
+#include <mbgl/style/expression/match.hpp>
+
+#include <mbgl/style/function/exponential_stops.hpp>
+#include <mbgl/style/function/interval_stops.hpp>
+#include <mbgl/style/function/categorical_stops.hpp>
+#include <mbgl/style/function/composite_exponential_stops.hpp>
+#include <mbgl/style/function/composite_interval_stops.hpp>
+#include <mbgl/style/function/composite_categorical_stops.hpp>
+#include <mbgl/style/function/identity_stops.hpp>
+
+#include <string>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+namespace detail {
+
+class ErrorExpression : public Expression {
+public:
+    ErrorExpression(std::string message_) : Expression(type::Error), message(std::move(message_)) {}
+    void accept(std::function<void(const Expression*)> visit) const override {
+        visit(this);
+    }
+
+    EvaluationResult evaluate(const EvaluationParameters&) const override {
+        return EvaluationError{message};
+    }
+
+private:
+    std::string message;
+};
+
+} // namespace detail
+
+
+// Create expressions representing 'classic' (i.e. stop-based) style functions
+
+struct Convert {
+    template <typename T>
+    static std::unique_ptr<Literal> makeLiteral(const T& value) {
+        return std::make_unique<Literal>(Value(toExpressionValue(value)));
+    }
+    
+    static std::unique_ptr<Expression> makeGet(const std::string& type, const std::string& property, ParsingContext ctx) {
+        std::vector<std::unique_ptr<Expression>> getArgs;
+        getArgs.push_back(makeLiteral(property));
+        ParseResult get = createCompoundExpression("get", std::move(getArgs), ctx);
+
+        std::vector<std::unique_ptr<Expression>> assertionArgs;
+        assertionArgs.push_back(std::move(*get));
+        
+        return std::move(*(createCompoundExpression(type, std::move(assertionArgs), ctx)));
+    }
+    
+    static std::unique_ptr<Expression> makeZoom(ParsingContext ctx) {
+        return std::move(*(createCompoundExpression("zoom", std::vector<std::unique_ptr<Expression>>(), ctx)));
+    }
+    
+    static std::unique_ptr<Expression> makeError(std::string message) {
+        return std::make_unique<detail::ErrorExpression>(message);
+    }
+
+
+    template <typename T>
+    static ParseResult makeCoalesceToDefault(std::unique_ptr<Expression> main, optional<T> defaultValue) {
+        if (!defaultValue) {
+            return ParseResult(std::move(main));
+        }
+        
+        Coalesce::Args args;
+        args.push_back(std::move(main));
+        args.push_back(makeLiteral(*defaultValue));
+        return ParseResult(std::make_unique<Coalesce>(valueTypeToExpressionType<T>(), std::move(args)));
+    }
+    
+    template <typename T>
+    static std::map<double, std::unique_ptr<Expression>> convertStops(const std::map<float, T>& stops) {
+        std::map<double, std::unique_ptr<Expression>> convertedStops;
+        for(const std::pair<float, T>& stop : stops) {
+            convertedStops.emplace(
+                stop.first,
+                makeLiteral(stop.second)
+            );
+        }
+        return convertedStops;
+    }
+    
+    template <typename T>
+    static ParseResult makeCurve(std::unique_ptr<Expression> input,
+                                 std::map<double, std::unique_ptr<Expression>> convertedStops,
+                                 typename Curve<typename ValueConverter<T>::ExpressionType>::Interpolator interpolator,
+                                 optional<T> defaultValue)
+    {
+        ParseResult curve = ParseResult(std::make_unique<Curve<typename ValueConverter<T>::ExpressionType>>(
+            valueTypeToExpressionType<T>(),
+            std::move(interpolator),
+            std::move(input),
+            std::move(convertedStops)
+        ));
+        assert(curve);
+        return makeCoalesceToDefault(std::move(*curve), defaultValue);
+    }
+    
+    template <typename Key, typename T>
+    static ParseResult makeMatch(std::unique_ptr<Expression> input,
+                                 const std::map<CategoricalValue, T>& stops) {
+        // match expression
+        typename Match<Key>::Branches branches;
+        for(const std::pair<CategoricalValue, T>& stop : stops) {
+            assert(stop.first.template is<Key>());
+            Key key = stop.first.template get<Key>();
+            branches.emplace(
+                std::move(key),
+                makeLiteral(stop.second)
+            );
+        }
+        
+        return ParseResult(std::make_unique<Match<Key>>(valueTypeToExpressionType<T>(),
+                                            std::move(input),
+                                            std::move(branches),
+                                            makeError("No matching label")));
+    }
+    
+    template <typename T>
+    static ParseResult makeCase(std::unique_ptr<Expression> input,
+                                const std::map<CategoricalValue, T>& stops) {
+        // case expression
+        std::vector<typename Case::Branch> branches;
+        
+        auto it = stops.find(true);
+        std::unique_ptr<Expression> true_case = it == stops.end() ?
+            makeError("No matching label") :
+            makeLiteral(it->second);
+
+        it = stops.find(false);
+        std::unique_ptr<Expression> false_case = it == stops.end() ?
+            makeError("No matching label") :
+            makeLiteral(it->second);
+
+        branches.push_back(std::make_pair(std::move(input), std::move(true_case)));
+        return ParseResult(std::make_unique<Case>(valueTypeToExpressionType<T>(), std::move(branches), std::move(false_case)));
+    }
+    
+    template <typename T>
+    static ParseResult convertCategoricalStops(std::map<CategoricalValue, T> stops, const std::string& property) {
+        assert(stops.size() > 0);
+
+        std::vector<ParsingError> errors;
+        ParsingContext ctx(errors);
+
+        const CategoricalValue& firstKey = stops.begin()->first;
+        return firstKey.match(
+            [&](bool) {
+                return makeCase(makeGet("boolean", property, ctx), stops);
+            },
+            [&](const std::string&) {
+                return makeMatch<std::string>(makeGet("string", property, ctx), stops);
+            },
+            [&](int64_t) {
+                return makeMatch<int64_t>(makeGet("number", property, ctx), stops);
+            }
+        );
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const ExponentialStops<T>& stops)
+    {
+        std::vector<ParsingError> errors;
+        ParseResult e = makeCurve(makeZoom(ParsingContext(errors)),
+                                           convertStops(stops.stops),
+                                           ExponentialInterpolator(stops.base),
+                                           optional<T>());
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const IntervalStops<T>& stops)
+    {
+        std::vector<ParsingError> errors;
+        ParseResult e = makeCurve(makeZoom(ParsingContext(errors)), convertStops(stops.stops), StepInterpolator(), optional<T>());
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const ExponentialStops<T>& stops,
+                                                  optional<T> defaultValue)
+    {
+        std::vector<ParsingError> errors;
+        ParseResult e = makeCurve(makeGet("number", property, ParsingContext(errors)),
+                                          convertStops(stops.stops),
+                                          ExponentialInterpolator(stops.base),
+                                          defaultValue);
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const IntervalStops<T>& stops,
+                                                  optional<T> defaultValue)
+    {
+        std::vector<ParsingError> errors;
+        std::unique_ptr<Expression> get = makeGet("number", property, ParsingContext(errors));
+        ParseResult e = makeCurve(std::move(get), convertStops(stops.stops), StepInterpolator(), defaultValue);
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const CategoricalStops<T>& stops,
+                                                  optional<T> defaultValue)
+    {
+        ParseResult expr = convertCategoricalStops(stops.stops, property);
+        assert(expr);
+        ParseResult e = makeCoalesceToDefault(std::move(*expr), defaultValue);
+        assert(e);
+        return std::move(*e);
+    }
+
+    template <typename T>
+    static typename Curve<std::enable_if_t<util::Interpolatable<T>::value, T>>::Interpolator zoomInterpolator() {
+        return ExponentialInterpolator(1.0);
+    }
+    
+    template <typename T>
+    static typename Curve<std::enable_if_t<!util::Interpolatable<T>::value, T>>::Interpolator zoomInterpolator() {
+        return StepInterpolator();
+    }
+
+
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const CompositeExponentialStops<T>& stops,
+                                                  optional<T> defaultValue)
+    {
+        std::vector<ParsingError> errors;
+        std::map<double, std::unique_ptr<Expression>> outerStops;
+        for (const std::pair<float, std::map<float, T>>& stop : stops.stops) {
+            std::unique_ptr<Expression> get = makeGet("number", property, ParsingContext(errors));
+            ParseResult innerCurve = makeCurve(std::move(get),
+                                               convertStops(stop.second),
+                                               ExponentialInterpolator(stops.base),
+                                               defaultValue);
+            assert(innerCurve);
+            outerStops.emplace(stop.first, std::move(*innerCurve));
+        }
+        ParseResult outerCurve = makeCurve(makeZoom(ParsingContext(errors)),
+                                           std::move(outerStops),
+                                           zoomInterpolator<T>(),
+                                           defaultValue);
+        assert(outerCurve);
+        ParseResult e = makeCoalesceToDefault(std::move(*outerCurve), defaultValue);
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const CompositeIntervalStops<T>& stops,
+                                                  optional<T> defaultValue)
+    {
+        std::vector<ParsingError> errors;
+        std::map<double, std::unique_ptr<Expression>> outerStops;
+        for (const std::pair<float, std::map<float, T>>& stop : stops.stops) {
+            std::unique_ptr<Expression> get = makeGet("number", property, ParsingContext(errors));
+            ParseResult innerCurve = makeCurve(std::move(get), convertStops(stop.second), StepInterpolator(), defaultValue);
+            assert(innerCurve);
+            outerStops.emplace(stop.first, std::move(*innerCurve));
+        }
+        ParseResult outerCurve = makeCurve(makeZoom(ParsingContext(errors)),
+                                           std::move(outerStops),
+                                           zoomInterpolator<T>(),
+                                           defaultValue);
+        assert(outerCurve);
+        ParseResult e = makeCoalesceToDefault(std::move(*outerCurve), defaultValue);
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const CompositeCategoricalStops<T>& stops,
+                                                  optional<T> defaultValue)
+    {
+        std::vector<ParsingError> errors;
+        std::map<double, std::unique_ptr<Expression>> outerStops;
+        for (const std::pair<float, std::map<CategoricalValue, T>>& stop : stops.stops) {
+            ParseResult innerCurve = convertCategoricalStops(stop.second, property);
+            assert(innerCurve);
+            outerStops.emplace(stop.first, std::move(*innerCurve));
+        }
+        ParseResult outerCurve = makeCurve(makeZoom(ParsingContext(errors)),
+                                           std::move(outerStops),
+                                           zoomInterpolator<T>(),
+                                           defaultValue);
+        assert(outerCurve);
+        ParseResult e = makeCoalesceToDefault(std::move(*outerCurve), defaultValue);
+        assert(e);
+        return std::move(*e);
+    }
+
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const IdentityStops<T>&,
+                                                  optional<T> defaultValue)
+    {
+        std::vector<ParsingError> errors;
+
+        std::unique_ptr<Expression> input = valueTypeToExpressionType<T>().match(
+            [&] (const type::StringType&) {
+                return makeGet("string", property, ParsingContext(errors));
+            },
+            [&] (const type::NumberType&) {
+                return makeGet("number", property, ParsingContext(errors));
+            },
+            [&] (const type::BooleanType&) {
+                return makeGet("boolean", property, ParsingContext(errors));
+            },
+            [&] (const type::ColorType&) {
+                std::vector<std::unique_ptr<Expression>> args;
+                args.push_back(makeGet("string", property, ParsingContext(errors)));
+                ParseResult color = createCompoundExpression("to-color", std::move(args), ParsingContext(errors));
+                assert(color);
+                return std::move(*color);
+            },
+            [&] (const type::Array& arr) {
+                std::vector<std::unique_ptr<Expression>> getArgs;
+                getArgs.push_back(makeLiteral(property));
+                ParseResult get = createCompoundExpression("get", std::move(getArgs), ParsingContext(errors));
+                return std::make_unique<ArrayAssertion>(arr, std::move(*get));
+            },
+            [&] (const auto&) -> std::unique_ptr<Expression> {
+                return makeLiteral(Null);
+            }
+        );
+        
+        ParseResult e = makeCoalesceToDefault(std::move(input), defaultValue);
+        assert(e);
+        return std::move(*e);
+    }
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/function/source_function.hpp b/include/mbgl/style/function/source_function.hpp
index 9c2ad101ec..5525429821 100644
--- a/include/mbgl/style/function/source_function.hpp
+++ b/include/mbgl/style/function/source_function.hpp
@@ -1,5 +1,7 @@
 #pragma once
 
+#include <mbgl/style/function/convert.hpp>
+
 #include <mbgl/style/function/exponential_stops.hpp>
 #include <mbgl/style/function/interval_stops.hpp>
 #include <mbgl/style/function/categorical_stops.hpp>
@@ -27,21 +29,30 @@ public:
             CategoricalStops<T>,
             IdentityStops<T>>>;
 
+    SourceFunction(std::unique_ptr<expression::Expression> expression_)
+        : expression(std::move(expression_))
+    {
+        assert(expression->isZoomConstant());
+        assert(!expression->isFeatureConstant());
+    }
+    
     SourceFunction(std::string property_, Stops stops_, optional<T> defaultValue_ = {})
         : property(std::move(property_)),
           stops(std::move(stops_)),
-          defaultValue(std::move(defaultValue_)) {
-    }
+          defaultValue(std::move(defaultValue_)),
+          expression(stops.match([&] (const auto& s) {
+            return expression::Convert::toExpression(property, s, defaultValue);
+          }))
+    {}
 
     template <class Feature>
     T evaluate(const Feature& feature, T finalDefaultValue) const {
-        optional<Value> v = feature.getValue(property);
-        if (!v) {
-            return defaultValue.value_or(finalDefaultValue);
+        const expression::EvaluationResult result = expression->evaluate(expression::EvaluationParameters(&feature));
+        if (result) {
+            const optional<T> typed = expression::fromExpressionValue<T>(*result);
+            return typed ? *typed : finalDefaultValue;
         }
-        return stops.match([&] (const auto& s) -> T {
-            return s.evaluate(*v).value_or(defaultValue.value_or(finalDefaultValue));
-        });
+        return finalDefaultValue;
     }
 
     friend bool operator==(const SourceFunction& lhs,
@@ -50,10 +61,15 @@ public:
             == std::tie(rhs.property, rhs.stops, rhs.defaultValue);
     }
 
+    bool useIntegerZoom = false;
+
+    // retained for compatibility with pre-expression function API
     std::string property;
     Stops stops;
     optional<T> defaultValue;
-    bool useIntegerZoom = false;
+
+private:
+    std::shared_ptr<expression::Expression> expression;
 };
 
 } // namespace style
diff --git a/include/mbgl/util/enum.hpp b/include/mbgl/util/enum.hpp
index 369ca86bfd..608befd3c4 100644
--- a/include/mbgl/util/enum.hpp
+++ b/include/mbgl/util/enum.hpp
@@ -11,6 +11,7 @@ namespace mbgl {
 template <typename T>
 class Enum {
 public:
+    using Type = T;
     static const char * toString(T);
     static optional<T> toEnum(const std::string&);
 };
diff --git a/include/mbgl/util/interpolate.hpp b/include/mbgl/util/interpolate.hpp
index 6738987598..aff730a0a2 100644
--- a/include/mbgl/util/interpolate.hpp
+++ b/include/mbgl/util/interpolate.hpp
@@ -3,6 +3,7 @@
 #include <mbgl/util/color.hpp>
 #include <mbgl/util/range.hpp>
 #include <mbgl/style/position.hpp>
+#include <mbgl/style/expression/value.hpp>
 
 #include <array>
 #include <vector>
@@ -47,6 +48,36 @@ public:
     }
 };
 
+
+// In order to accept Array<Number, N> as an output value for Curve
+// expressions, we need to have an interpolatable std::vector type.
+// However, style properties like line-dasharray are represented using
+// std::vector<float>, and should NOT be considered interpolatable.
+// So, we use std::vector<Value> to represent expression array values,
+// asserting that (a) the vectors are the same size, and (b) they contain
+// only numeric values.  (These invariants should be relatively safe,
+// being enforced by the expression type system.)
+template<>
+struct Interpolator<std::vector<style::expression::Value>> {
+    std::vector<style::expression::Value> operator()(const std::vector<style::expression::Value>& a,
+                                  const std::vector<style::expression::Value>& b,
+                                  const double t) const {
+        assert(a.size() == b.size());
+        if (a.size() == 0) return {};
+        std::vector<style::expression::Value> result;
+        for (std::size_t i = 0; i < a.size(); i++) {
+            assert(a[i].template is<double>());
+            assert(b[i].template is<double>());
+            style::expression::Value item = interpolate(
+                a[i].template get<double>(),
+                b[i].template get<double>(),
+                t);
+            result.push_back(item);
+        }
+        return result;
+    }
+};
+
 template <>
 struct Interpolator<style::Position> {
 public:
@@ -101,5 +132,7 @@ struct Interpolatable
       std::true_type,
       std::false_type> {};
 
+
+
 } // namespace util
 } // namespace mbgl
diff --git a/mapbox-gl-js b/mapbox-gl-js
-Subproject cecd21c9dcf87e4b1a5282b3a071f409c164398
+Subproject 3eced30265619a2f4bfa91b615d58651e0326cd
diff --git a/package.json b/package.json
index edb41f1f68..4ff4b32735 100644
--- a/package.json
+++ b/package.json
@@ -13,7 +13,7 @@
   },
   "license": "BSD-2-Clause",
   "dependencies": {
-    "nan": "^2.4.0",
+    "nan": "^2.6.2",
     "node-pre-gyp": "^0.6.37",
     "npm-run-all": "^4.0.2"
   },
@@ -23,6 +23,7 @@
     "ejs": "^2.4.1",
     "express": "^4.11.1",
     "flow-remove-types": "^1.2.1",
+    "json-stringify-pretty-compact": "^1.0.4",
     "lodash": "^4.16.4",
     "mapbox-gl-styles": "2.0.2",
     "pixelmatch": "^4.0.2",
@@ -38,7 +39,8 @@
     "install": "node-pre-gyp install --fallback-to-build=false || make node",
     "test": "tape platform/node/test/js/**/*.test.js",
     "test-memory": "node --expose-gc platform/node/test/memory.test.js",
-    "test-suite": "run-s test-render test-query",
+    "test-suite": "run-s test-render test-query test-expressions",
+    "test-expressions": "node platform/node/test/expression.test.js",
     "test-render": "node platform/node/test/render.test.js",
     "test-query": "node platform/node/test/query.test.js"
   },
diff --git a/platform/node/src/node_expression.cpp b/platform/node/src/node_expression.cpp
new file mode 100644
index 0000000000..e75478320c
--- /dev/null
+++ b/platform/node/src/node_expression.cpp
@@ -0,0 +1,223 @@
+#include "node_conversion.hpp"
+#include "node_expression.hpp"
+
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion/geojson.hpp>
+#include <mbgl/util/geojson.hpp>
+#include <nan.h>
+
+using namespace mbgl::style;
+using namespace mbgl::style::expression;
+
+namespace node_mbgl {
+
+Nan::Persistent<v8::Function> NodeExpression::constructor;
+
+void NodeExpression::Init(v8::Local<v8::Object> target) {
+    v8::Local<v8::FunctionTemplate> tpl = Nan::New<v8::FunctionTemplate>(New);
+    tpl->SetClassName(Nan::New("Expression").ToLocalChecked());
+    tpl->InstanceTemplate()->SetInternalFieldCount(1); // what is this doing?
+
+    Nan::SetPrototypeMethod(tpl, "evaluate", Evaluate);
+    Nan::SetPrototypeMethod(tpl, "getType", GetType);
+    Nan::SetPrototypeMethod(tpl, "isFeatureConstant", IsFeatureConstant);
+    Nan::SetPrototypeMethod(tpl, "isZoomConstant", IsZoomConstant);
+
+    Nan::SetMethod(tpl, "parse", Parse);
+
+    constructor.Reset(tpl->GetFunction()); // what is this doing?
+    Nan::Set(target, Nan::New("Expression").ToLocalChecked(), tpl->GetFunction());
+}
+
+type::Type parseType(v8::Local<v8::Object> type) {
+    static std::unordered_map<std::string, type::Type> types = {
+        {"string", type::String},
+        {"number", type::Number},
+        {"noolean", type::Boolean},
+        {"object", type::Object},
+        {"color", type::Color},
+        {"value", type::Value}
+    };
+    
+    v8::Local<v8::Value> v8kind = Nan::Get(type, Nan::New("kind").ToLocalChecked()).ToLocalChecked();
+    std::string kind(*v8::String::Utf8Value(v8kind));
+    
+    if (kind == "array") {
+        type::Type itemType = parseType(Nan::Get(type, Nan::New("itemType").ToLocalChecked()).ToLocalChecked()->ToObject());
+        mbgl::optional<std::size_t> N;
+        
+        v8::Local<v8::String> Nkey = Nan::New("N").ToLocalChecked();
+        if (Nan::Has(type, Nkey).FromMaybe(false)) {
+            N = Nan::Get(type, Nkey).ToLocalChecked()->ToInt32()->Value();
+        }
+        return type::Array(itemType, N);
+    }
+    
+    return types[kind];
+}
+
+void NodeExpression::Parse(const Nan::FunctionCallbackInfo<v8::Value>& info) {
+    v8::Local<v8::Function> cons = Nan::New(constructor);
+    
+    if (info.Length() < 1 || info[0]->IsUndefined()) {
+        return Nan::ThrowTypeError("Requires a JSON style expression argument.");
+    }
+    
+    mbgl::optional<type::Type> expected;
+    if (info.Length() > 1 && info[1]->IsObject()) {
+        expected = parseType(info[1]->ToObject());
+    }
+
+    auto expr = info[0];
+
+    try {
+        std::vector<ParsingError> errors;
+        ParseResult parsed = ParsingContext(errors, expected).parse(mbgl::style::conversion::Convertible(expr));
+        if (parsed) {
+            assert(errors.size() == 0);
+            auto nodeExpr = new NodeExpression(std::move(*parsed));
+            const int argc = 0;
+            v8::Local<v8::Value> argv[0] = {};
+            auto wrapped = Nan::NewInstance(cons, argc, argv).ToLocalChecked();
+            nodeExpr->Wrap(wrapped);
+            info.GetReturnValue().Set(wrapped);
+            return;
+        }
+        
+        v8::Local<v8::Array> result = Nan::New<v8::Array>();
+        for (std::size_t i = 0; i < errors.size(); i++) {
+            const auto& error = errors[i];
+            v8::Local<v8::Object> err = Nan::New<v8::Object>();
+            Nan::Set(err,
+                    Nan::New("key").ToLocalChecked(),
+                    Nan::New(error.key.c_str()).ToLocalChecked());
+            Nan::Set(err,
+                    Nan::New("error").ToLocalChecked(),
+                    Nan::New(error.message.c_str()).ToLocalChecked());
+            Nan::Set(result, Nan::New((uint32_t)i), err);
+        }
+        info.GetReturnValue().Set(result);
+    } catch(std::exception &ex) {
+        return Nan::ThrowError(ex.what());
+    }
+}
+
+void NodeExpression::New(const Nan::FunctionCallbackInfo<v8::Value>& info) {
+    if (!info.IsConstructCall()) {
+        return Nan::ThrowTypeError("Use the new operator to create new Expression objects");
+    }
+
+    info.GetReturnValue().Set(info.This());
+}
+
+struct ToValue {
+    v8::Local<v8::Value> operator()(mbgl::NullValue) {
+        Nan::EscapableHandleScope scope;
+        return scope.Escape(Nan::Null());
+    }
+
+    v8::Local<v8::Value> operator()(bool t) {
+        Nan::EscapableHandleScope scope;
+        return scope.Escape(Nan::New(t));
+    }
+
+    v8::Local<v8::Value> operator()(double t) {
+        Nan::EscapableHandleScope scope;
+        return scope.Escape(Nan::New(t));
+    }
+
+    v8::Local<v8::Value> operator()(const std::string& t) {
+        Nan::EscapableHandleScope scope;
+        return scope.Escape(Nan::New(t).ToLocalChecked());
+    }
+
+    v8::Local<v8::Value> operator()(const std::vector<Value>& array) {
+        Nan::EscapableHandleScope scope;
+        v8::Local<v8::Array> result = Nan::New<v8::Array>();
+        for (unsigned int i = 0; i < array.size(); i++) {
+            result->Set(i, toJS(array[i]));
+        }
+        return scope.Escape(result);
+    }
+    
+    v8::Local<v8::Value> operator()(const mbgl::Color& color) {
+        return operator()(std::vector<Value> {
+            static_cast<double>(color.r),
+            static_cast<double>(color.g),
+            static_cast<double>(color.b),
+            static_cast<double>(color.a)
+        });
+    }
+
+    v8::Local<v8::Value> operator()(const std::unordered_map<std::string, Value>& map) {
+        Nan::EscapableHandleScope scope;
+        v8::Local<v8::Object> result = Nan::New<v8::Object>();
+        for (const auto& entry : map) {
+            Nan::Set(result, Nan::New(entry.first).ToLocalChecked(), toJS(entry.second));
+        }
+
+        return scope.Escape(result);
+    }
+};
+
+v8::Local<v8::Value> toJS(const Value& value) {
+    return Value::visit(value, ToValue());
+}
+
+void NodeExpression::Evaluate(const Nan::FunctionCallbackInfo<v8::Value>& info) {
+    NodeExpression* nodeExpr = ObjectWrap::Unwrap<NodeExpression>(info.Holder());
+    const std::unique_ptr<Expression>& expression = nodeExpr->expression;
+
+    if (info.Length() < 2) {
+        return Nan::ThrowTypeError("Requires arguments zoom and feature arguments.");
+    }
+
+    float zoom = info[0]->NumberValue();
+
+    Nan::JSON NanJSON;
+    conversion::Error conversionError;
+    mbgl::optional<mbgl::GeoJSON> geoJSON = conversion::convert<mbgl::GeoJSON>(info[1], conversionError);
+    if (!geoJSON) {
+        Nan::ThrowTypeError(conversionError.message.c_str());
+        return;
+    }
+
+    try {
+        mapbox::geojson::feature feature = geoJSON->get<mapbox::geojson::feature>();
+        auto result = expression->evaluate(zoom, feature);
+        if (result) {
+            info.GetReturnValue().Set(toJS(*result));
+        } else {
+            v8::Local<v8::Object> res = Nan::New<v8::Object>();
+            Nan::Set(res,
+                    Nan::New("error").ToLocalChecked(),
+                    Nan::New(result.error().message.c_str()).ToLocalChecked());
+            info.GetReturnValue().Set(res);
+        }
+    } catch(std::exception &ex) {
+        return Nan::ThrowTypeError(ex.what());
+    }
+}
+
+void NodeExpression::GetType(const Nan::FunctionCallbackInfo<v8::Value>& info) {
+    NodeExpression* nodeExpr = ObjectWrap::Unwrap<NodeExpression>(info.Holder());
+    const std::unique_ptr<Expression>& expression = nodeExpr->expression;
+
+    const type::Type type = expression->getType();
+    const std::string name = type.match([&] (const auto& t) { return t.getName(); });
+    info.GetReturnValue().Set(Nan::New(name.c_str()).ToLocalChecked());
+}
+
+void NodeExpression::IsFeatureConstant(const Nan::FunctionCallbackInfo<v8::Value>& info) {
+    NodeExpression* nodeExpr = ObjectWrap::Unwrap<NodeExpression>(info.Holder());
+    const std::unique_ptr<Expression>& expression = nodeExpr->expression;
+    info.GetReturnValue().Set(Nan::New(expression->isFeatureConstant()));
+}
+
+void NodeExpression::IsZoomConstant(const Nan::FunctionCallbackInfo<v8::Value>& info) {
+    NodeExpression* nodeExpr = ObjectWrap::Unwrap<NodeExpression>(info.Holder());
+    const std::unique_ptr<Expression>& expression = nodeExpr->expression;
+    info.GetReturnValue().Set(Nan::New(expression->isZoomConstant()));
+}
+
+} // namespace node_mbgl
diff --git a/platform/node/src/node_expression.hpp b/platform/node/src/node_expression.hpp
new file mode 100644
index 0000000000..e977b58288
--- /dev/null
+++ b/platform/node/src/node_expression.hpp
@@ -0,0 +1,40 @@
+#pragma once
+
+#include <exception>
+#include <memory>
+#include <mbgl/style/conversion.hpp>
+#include <mbgl/style/expression/expression.hpp>
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <nan.h>
+#pragma GCC diagnostic pop
+
+using namespace mbgl::style::expression;
+
+namespace node_mbgl {
+
+v8::Local<v8::Value> toJS(const Value&);
+
+class NodeExpression : public Nan::ObjectWrap {
+public:
+    static void Init(v8::Local<v8::Object>);
+
+private:
+    NodeExpression(std::unique_ptr<Expression> expression_) :
+        expression(std::move(expression_))
+    {};
+
+    static void New(const Nan::FunctionCallbackInfo<v8::Value>&);
+    static void Parse(const Nan::FunctionCallbackInfo<v8::Value>&);
+    static void Evaluate(const Nan::FunctionCallbackInfo<v8::Value>&);
+    static void GetType(const Nan::FunctionCallbackInfo<v8::Value>&);
+    static void IsFeatureConstant(const Nan::FunctionCallbackInfo<v8::Value>&);
+    static void IsZoomConstant(const Nan::FunctionCallbackInfo<v8::Value>&);
+    static Nan::Persistent<v8::Function> constructor;
+
+    std::unique_ptr<Expression> expression;
+};
+
+} // namespace node_mbgl
diff --git a/platform/node/src/node_mapbox_gl_native.cpp b/platform/node/src/node_mapbox_gl_native.cpp
index cdcc982220..96e96e4298 100644
--- a/platform/node/src/node_mapbox_gl_native.cpp
+++ b/platform/node/src/node_mapbox_gl_native.cpp
@@ -10,6 +10,7 @@
 #include "node_map.hpp"
 #include "node_logging.hpp"
 #include "node_request.hpp"
+#include "node_expression.hpp"
 
 void RegisterModule(v8::Local<v8::Object> target, v8::Local<v8::Object> module) {
     // This has the effect of:
@@ -20,6 +21,7 @@ void RegisterModule(v8::Local<v8::Object> target, v8::Local<v8::Object> module)
 
     node_mbgl::NodeMap::Init(target);
     node_mbgl::NodeRequest::Init();
+    node_mbgl::NodeExpression::Init(target);
 
     // Exports Resource constants.
     v8::Local<v8::Object> resource = Nan::New<v8::Object>();
diff --git a/platform/node/test/expression.test.js b/platform/node/test/expression.test.js
new file mode 100644
index 0000000000..b54dd342e5
--- /dev/null
+++ b/platform/node/test/expression.test.js
@@ -0,0 +1,73 @@
+'use strict';
+
+var suite = require('../../../mapbox-gl-js/test/integration').expression;
+var mbgl = require('../index');
+
+var tests;
+
+if (process.argv[1] === __filename && process.argv.length > 2) {
+    tests = process.argv.slice(2);
+}
+
+function getExpectedType(spec) {
+    if (spec.type === 'array') {
+        const itemType = getExpectedType({ type: spec.value });
+        const array = {
+            kind: 'array',
+            itemType: itemType || { kind: 'value' },
+        };
+        if (typeof spec.length === 'number') {
+            array.N = spec.length;
+        }
+        return array;
+    }
+
+    if (spec.type === 'enum') {
+        return { kind: 'string' };
+    }
+
+    return typeof spec.type === 'string' ? {kind: spec.type} : null;
+}
+
+suite.run('native', {tests: tests}, (fixture) => {
+    const compiled = {};
+    const result = {
+        compiled
+    };
+
+    const spec = fixture.propertySpec || {};
+    const expression = mbgl.Expression.parse(fixture.expression, getExpectedType(spec));
+
+    if (expression instanceof mbgl.Expression) {
+        compiled.result = 'success';
+        compiled.isFeatureConstant = expression.isFeatureConstant();
+        compiled.isZoomConstant = expression.isZoomConstant();
+        compiled.type = expression.getType();
+
+        const evaluate = fixture.inputs || [];
+        const evaluateResults = [];
+        for (const input of evaluate) {
+            const zoom = typeof input[0].zoom === 'number' ?
+                input[0].zoom : -1;
+
+            const feature = Object.assign({
+                type: 'Feature',
+                properties: {},
+                geometry: { type: 'Point', coordinates: [0, 0] }
+            }, input[1])
+
+            const output = expression.evaluate(zoom, feature);
+            evaluateResults.push(output);
+        }
+
+        if (fixture.inputs) {
+            result.outputs = evaluateResults;
+        }
+    } else {
+        compiled.result = 'error';
+        compiled.errors = expression;
+    }
+
+    return result;
+});
+
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/stringify.hpp b/src/mbgl/style/conversion/stringify.hpp
index 6ae6fede42..df786e5b91 100644
--- a/src/mbgl/style/conversion/stringify.hpp
+++ b/src/mbgl/style/conversion/stringify.hpp
@@ -76,7 +76,7 @@ void stringify(Writer& writer, const std::array<float, 4>& v) {
 }
 
 template <class Writer>
-void stringify(Writer&, const Value&);
+void stringify(Writer&, const mbgl::Value&);
 
 template <class Writer, class T>
 void stringify(Writer& writer, const std::vector<T>& v) {
diff --git a/src/mbgl/style/expression/array_assertion.cpp b/src/mbgl/style/expression/array_assertion.cpp
new file mode 100644
index 0000000000..6acd76897c
--- /dev/null
+++ b/src/mbgl/style/expression/array_assertion.cpp
@@ -0,0 +1,85 @@
+#include <mbgl/style/expression/array_assertion.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult ArrayAssertion::evaluate(const EvaluationParameters& 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::accept(std::function<void(const Expression*)> visit) const {
+    visit(this);
+    input->accept(visit);
+}
+
+ParseResult ArrayAssertion::parse(const mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+
+    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.concat(length - 1, {type::Value}).parse(arrayMember(value, length - 1));
+    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/at.cpp b/src/mbgl/style/expression/at.cpp
new file mode 100644
index 0000000000..042a902979
--- /dev/null
+++ b/src/mbgl/style/expression/at.cpp
@@ -0,0 +1,62 @@
+#include <mbgl/style/expression/at.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult At::evaluate(const EvaluationParameters& 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 = *fromExpressionValue<double>(*evaluatedIndex);
+    const auto inputArray = *fromExpressionValue<std::vector<Value>>(*evaluatedInput);
+    
+    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::accept(std::function<void(const Expression*)> visit) const {
+    visit(this);
+    index->accept(visit);
+    input->accept(visit);
+}
+
+ParseResult At::parse(const mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+    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.concat(1, {type::Number}).parse(arrayMember(value, 1));
+    ParseResult input = ctx.concat(2, {type::Array(ctx.expected ? *ctx.expected : type::Value)}).parse(arrayMember(value, 2));
+
+    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/case.cpp b/src/mbgl/style/expression/case.cpp
new file mode 100644
index 0000000000..499f345454
--- /dev/null
+++ b/src/mbgl/style/expression/case.cpp
@@ -0,0 +1,84 @@
+#include <mbgl/style/expression/case.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Case::evaluate(const EvaluationParameters& 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::accept(std::function<void(const Expression*)> visit) const {
+    visit(this);
+    for (const Branch& branch : branches) {
+        branch.first->accept(visit);
+        branch.second->accept(visit);
+    }
+    otherwise->accept(visit);
+}
+
+ParseResult Case::parse(const mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+
+    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.expected && *ctx.expected != type::Value) {
+        outputType = ctx.expected;
+    }
+
+    std::vector<Case::Branch> branches;
+    for (size_t i = 1; i + 1 < length; i += 2) {
+        auto test = ctx.concat(i, {type::Boolean}).parse(arrayMember(value, i));
+        if (!test) {
+            return test;
+        }
+
+        auto output = ctx.concat(i + 1, outputType).parse(arrayMember(value, i + 1));
+        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.concat(length - 1, outputType).parse(arrayMember(value, length - 1));
+    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..ab0181812d
--- /dev/null
+++ b/src/mbgl/style/expression/coalesce.cpp
@@ -0,0 +1,55 @@
+#include <mbgl/style/expression/coalesce.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Coalesce::evaluate(const EvaluationParameters& params) const {
+    for (auto it = args.begin(); it != args.end(); it++) {
+        const EvaluationResult result = (*it)->evaluate(params);
+        if (!result || *result != Null || std::next(it) == args.end()) return result;
+    }
+    
+    return Null;
+}
+
+void Coalesce::accept(std::function<void(const Expression*)> visit) const {
+    visit(this);
+    for (const std::unique_ptr<Expression>& arg : args) {
+        arg->accept(visit);
+    }
+}
+
+ParseResult Coalesce::parse(const mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+    assert(isArray(value));
+    auto length = arrayLength(value);
+    if (length < 2) {
+        ctx.error("Expected at least one argument.");
+        return ParseResult();
+    }
+ 
+    Coalesce::Args args;
+    optional<type::Type> outputType;
+    if (ctx.expected && *ctx.expected != type::Value) {
+        outputType = ctx.expected;
+    }
+
+    for (std::size_t i = 1; i < length; i++) {
+        auto parsed = ctx.concat(i, outputType).parse(arrayMember(value, i));
+        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/compound_expression.cpp b/src/mbgl/style/expression/compound_expression.cpp
new file mode 100644
index 0000000000..d6f0e4c553
--- /dev/null
+++ b/src/mbgl/style/expression/compound_expression.cpp
@@ -0,0 +1,673 @@
+#include <mbgl/style/expression/compound_expression.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 EvaluationParameters&, 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 EvaluationParameters& 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 EvaluationParameters& 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 EvaluationParameters& evaluationParameters, const Args& args) const {
+        Varargs<T> evaluated;
+        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 EvaluationParameters&, Params...)> : SignatureBase {
+    using Args = std::array<std::unique_ptr<Expression>, sizeof...(Params)>;
+    
+    Signature(R (*evaluate_)(const EvaluationParameters&, 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 EvaluationParameters& evaluationParameters, const Args& args) const {
+        return applyImpl(evaluationParameters, args, std::index_sequence_for<Params...>{});
+    }
+    
+private:
+    template <std::size_t ...I>
+    EvaluationResult applyImpl(const EvaluationParameters& 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 EvaluationParameters&, 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<T> assertion(const Value& v) {
+    if (!v.is<T>()) {
+        return EvaluationError {
+            "Expected value to be of type " + toString(valueTypeToExpressionType<T>()) +
+            ", but found " + toString(typeOf(v)) + " instead."
+        };
+    }
+    return v.get<T>();
+}
+
+std::string stringifyColor(double r, double g, double b, double a) {
+    return stringify(r) + ", " +
+        stringify(g) + ", " +
+        stringify(b) + ", " +
+        stringify(a);
+}
+Result<mbgl::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 mbgl::Color(r / 255, g / 255, b / 255, a);
+}
+
+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("number", assertion<double>);
+    define("string", assertion<std::string>);
+    define("boolean", assertion<bool>);
+    define("object", assertion<std::unordered_map<std::string, Value>>);
+    
+    define("to-string", [](const Value& value) -> Result<std::string> {
+        return value.match(
+            [](const std::unordered_map<std::string, Value>&) -> Result<std::string> {
+                return EvaluationError {
+                    R"(Expected a primitive value in ["string", ...], but found Object instead.)"
+                };
+            },
+            [](const std::vector<Value>& v) -> Result<std::string> {
+                return EvaluationError {
+                    R"(Expected a primitive value in ["string", ...], but found )" + toString(typeOf(v)) + " instead."
+                };
+            },
+            [](const auto& v) -> Result<std::string> { return stringify(v); }
+        );
+    });
+    define("to-number", [](const Value& v) -> Result<double> {
+        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;
+    });
+    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 mbgl::Color& color) -> Result<std::array<double, 4>> {
+        return std::array<double, 4> {{ color.r, color.g, color.b, color.a }};
+    });
+    
+    define("to-color", [](const Value& colorValue) -> Result<mbgl::Color> {
+        return colorValue.match(
+            [&](const std::string& colorString) -> Result<mbgl::Color> {
+                const optional<mbgl::Color> result = mbgl::Color::parse(colorString);
+                if (result) {
+                    return *result;
+                } else {
+                    return EvaluationError{
+                        "Could not parse color from value '" + colorString + "'"
+                    };
+                }
+            },
+            [&](const std::vector<Value>& components) -> Result<mbgl::Color> {
+                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) {
+                    return {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
+                    )};
+                } else {
+                    return EvaluationError{
+                        "Could not parse color from value '" + stringify(colorValue) + "'"
+                    };
+                }
+            },
+            [&](const auto&) -> Result<mbgl::Color> {
+                return EvaluationError{
+                    "Could not parse color from value '" + stringify(colorValue) + "'"
+                };
+            }
+        );
+    
+    });
+    
+    define("rgba", rgba);
+    define("rgb", [](double r, double g, double b) { return rgba(r, g, b, 1.0f); });
+    
+    define("zoom", [](const EvaluationParameters& params) -> Result<double> {
+        if (!params.zoom) {
+            return EvaluationError {
+                "The 'zoom' expression is unavailable in the current evaluation context."
+            };
+        }
+        return *(params.zoom);
+    });
+    
+    define("has", [](const EvaluationParameters& 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 EvaluationParameters& 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 EvaluationParameters& 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 EvaluationParameters& 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 EvaluationParameters& 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("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("any", [](const Varargs<bool>& args) -> Result<bool> {
+        bool result = false;
+        for (auto arg : args) result = result || arg;
+        return result;
+    });
+    define("all", [](const Varargs<bool>& args) -> Result<bool> {
+        bool result = true;
+        for (bool arg : args) result = result && arg;
+        return result;
+    });
+    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();
+
+
+ParseResult parseCompoundExpression(const std::string name, const mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+    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;
+    
+    std::vector<std::unique_ptr<Expression>> args;
+    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
+    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.concat(i, expected).parse(arrayMember(value, i));
+        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)
+{
+    std::vector<ParsingError> currentSignatureErrors;
+
+    ParsingContext signatureContext(currentSignatureErrors);
+    signatureContext.key = ctx.key;
+    
+    for (const std::unique_ptr<detail::SignatureBase>& signature : definition) {
+        currentSignatureErrors.clear();
+        
+        
+        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];
+                signatureContext.concat(i + 1, params.at(i)).checkType(arg->getType());
+            }
+        } 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];
+                signatureContext.concat(i + 1, paramType).checkType(arg->getType());
+            }
+        }
+        
+        if (currentSignatureErrors.size() == 0) {
+            return ParseResult(signature->makeExpression(name, std::move(args)));
+        }
+    }
+    
+    if (definition.size() == 1) {
+        ctx.errors.insert(ctx.errors.end(), currentSignatureErrors.begin(), currentSignatureErrors.end());
+    } else {
+        std::string signatures;
+        for (const auto& signature : definition) {
+            signatures += (signatures.size() > 0 ? " | " : "");
+            signature->params.match(
+                [&](const VarargsType& varargs) {
+                    signatures += "(" + toString(varargs.type) + ")";
+                },
+                [&](const std::vector<type::Type>& params) {
+                    signatures += "(";
+                    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/curve.cpp b/src/mbgl/style/expression/curve.cpp
new file mode 100644
index 0000000000..028ccaf928
--- /dev/null
+++ b/src/mbgl/style/expression/curve.cpp
@@ -0,0 +1,246 @@
+
+#include <mbgl/style/expression/curve.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+using Interpolator = variant<StepInterpolator,
+                             ExponentialInterpolator,
+                             CubicBezierInterpolator>;
+
+ParseResult parseCurve(const mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+    assert(isArray(value));
+
+    auto length = arrayLength(value);
+
+    // first parse interpolation, because further validation of the input depends upon
+    // whether or not this is a step curve
+    if (length < 2) {
+        ctx.error("Expected an interpolation type expression.");
+        return ParseResult();
+    }
+    const mbgl::style::conversion::Convertible& interp = arrayMember(value, 1);
+    if (!isArray(interp) || arrayLength(interp) == 0) {
+        ctx.error("Expected an interpolation type expression.");
+        return ParseResult();
+    }
+
+    Interpolator interpolator;
+    bool isStep = false;
+    
+    const optional<std::string> interpName = toString(arrayMember(interp, 0));
+    ParsingContext interpContext = ctx.concat(1);
+    if (interpName && *interpName == "step") {
+        interpolator = StepInterpolator();
+        isStep = true;
+    } else 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) {
+            interpContext.error("Exponential interpolation requires a numeric base.", 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
+        ) {
+            interpContext.error("Cubic bezier interpolation requires four numeric arguments with values between 0 and 1.");
+            return ParseResult();
+            
+        }
+        interpolator = CubicBezierInterpolator(*x1, *y1, *x2, *y2);
+    } else {
+        interpContext.error("Unknown interpolation type " + (interpName ? *interpName : ""), 0);
+        return ParseResult();
+    }
+    
+    std::size_t minArgs = isStep ? 5 : 4;
+    if (length - 1 < minArgs) {
+        ctx.error("Expected at least " + std::to_string(minArgs) + " arguments, but found only " + std::to_string(length - 1) + ".");
+        return ParseResult();
+    }
+    
+    bool parity = minArgs % 2;
+    // [curve, interp, input, 2 * (n pairs)...]
+    if ((length - 1) % 2 != parity) {
+        ctx.error("Expected an " + std::string(parity ? "odd" : "even") + " number of arguments.");
+        return ParseResult();
+    }
+    
+    
+    ParseResult input = ctx.concat(2, {type::Number}).parse(arrayMember(value, 2));
+    if (!input) {
+        return input;
+    }
+    
+    std::map<double, std::unique_ptr<Expression>> stops;
+    optional<type::Type> outputType;
+    if (ctx.expected && *ctx.expected != type::Value) {
+        outputType = ctx.expected;
+    }
+    
+    double previous = - std::numeric_limits<double>::infinity();
+    
+    // If this is a step curve, the definition begins with an output value rather
+    // than an input level, so consume that output value before proceeding into the
+    // "stops" loop below.
+    if (isStep) {
+        auto output = ctx.concat(3, outputType).parse(arrayMember(value, 3));
+        if (!output) {
+            return ParseResult();
+        }
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+        stops.emplace(-std::numeric_limits<double>::infinity(), std::move(*output));
+    }
+    
+    for (std::size_t i = isStep ? 4 : 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 "curve" 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 "curve" expressions must be arranged with input values in strictly ascending order.)",
+                i
+            );
+            return ParseResult();
+        }
+        previous = *label;
+        
+        auto output = ctx.concat(i + 1, outputType).parse(arrayMember(value, i + 1));
+        if (!output) {
+            return ParseResult();
+        }
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+
+        stops.emplace(*label, std::move(*output));
+    }
+    
+    assert(outputType);
+    
+    if (
+        !interpolator.template is<StepInterpolator>() &&
+        *outputType != type::Number &&
+        *outputType != type::Color &&
+        !(
+            outputType->is<type::Array>() &&
+            outputType->get<type::Array>().itemType == type::Number
+        )
+    )
+    {
+        ctx.error("Type " + toString(*outputType) +
+            " is not interpolatable, and thus cannot be used as a " +
+            *interpName + " curve's output type.");
+        return ParseResult();
+    }
+    
+    return outputType->match(
+        [&](const type::NumberType&) -> ParseResult {
+            return interpolator.match([&](const auto& interpolator_) {
+                return ParseResult(std::make_unique<Curve<double>>(
+                    *outputType, interpolator_, std::move(*input), std::move(stops)
+                ));
+            });
+        },
+        [&](const type::ColorType&) -> ParseResult {
+            return interpolator.match([&](const auto& interpolator_) {
+                return ParseResult(std::make_unique<Curve<mbgl::Color>>(
+                    *outputType, interpolator_, std::move(*input), std::move(stops)
+                ));
+            });
+        },
+        [&](const type::Array& arrayType) -> ParseResult {
+            return interpolator.match(
+                [&](const StepInterpolator& stepInterpolator) {
+                    return ParseResult(std::make_unique<Curve<std::vector<Value>>>(
+                        *outputType, stepInterpolator, std::move(*input), std::move(stops)
+                    ));
+                },
+                [&](const auto& continuousInterpolator) {
+                    if (arrayType.itemType != type::Number || !arrayType.N) {
+                        assert(false); // interpolability already checked above.
+                        return ParseResult();
+                    }
+                    return ParseResult(std::make_unique<Curve<std::vector<Value>>>(
+                        *outputType, continuousInterpolator, std::move(*input), std::move(stops)
+                    ));
+                }
+            );
+        },
+        [&](const auto&) {
+            // Null, Boolean, String, Object, Value output types only support step interpolation
+            return interpolator.match(
+                [&](const StepInterpolator& stepInterpolator) {
+                    return ParseResult(std::make_unique<Curve<double>>(
+                        *outputType, stepInterpolator, std::move(*input), std::move(stops)
+                    ));
+                },
+                [&](const auto&) {
+                    assert(false); // interpolability already checked above.
+                    return ParseResult();
+                }
+            );
+        }
+    );
+}
+
+} // 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..4dbffc4560
--- /dev/null
+++ b/src/mbgl/style/expression/let.cpp
@@ -0,0 +1,95 @@
+#include <mbgl/style/expression/let.hpp>
+#include <mbgl/style/conversion/get_json_type.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Let::evaluate(const EvaluationParameters& params) const {
+    return result->evaluate(params);
+}
+
+void Let::accept(std::function<void(const Expression*)> visit) const {
+    visit(this);
+    for (auto it = bindings.begin(); it != bindings.end(); it++) {
+        it->second->accept(visit);
+    }
+    result->accept(visit);
+}
+
+ParseResult Let::parse(const mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+    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.concat(i + 1).parse(arrayMember(value, i + 1));
+        if (!bindingValue) {
+            return ParseResult();
+        }
+        
+        bindings_.emplace(*name, std::move(*bindingValue));
+    }
+
+    auto resultContext = ctx.concat(length - 1, ctx.expected, bindings_);
+    ParseResult result_ = resultContext.parse(arrayMember(value, length - 1));
+    if (!result_) {
+        return ParseResult();
+    }
+
+    return ParseResult(std::make_unique<Let>(std::move(bindings_), std::move(*result_)));
+}
+
+EvaluationResult Var::evaluate(const EvaluationParameters& params) const {
+    return value->evaluate(params);
+}
+
+void Var::accept(std::function<void(const Expression*)> visit) const {
+    visit(this);
+}
+
+ParseResult Var::parse(const mbgl::style::conversion::Convertible& value_, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+    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..402e56de96
--- /dev/null
+++ b/src/mbgl/style/expression/literal.cpp
@@ -0,0 +1,92 @@
+
+#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)};
+    }
+}
+
+optional<Value> parseValue(const mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+    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);
+    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 mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    const optional<Value> parsedValue = parseValue(value, ctx);
+
+    if (!parsedValue) {
+        return ParseResult();
+    }
+
+    // special case: infer the item type if possible for zero-length arrays
+    if (
+        ctx.expected &&
+        ctx.expected->template is<type::Array>() &&
+        parsedValue->template is<std::vector<Value>>()
+    ) {
+        auto type = typeOf(*parsedValue).template get<type::Array>();
+        auto expected = ctx.expected->template get<type::Array>();
+        if (
+            type.N && (*type.N == 0) &&
+            (!expected.N || (*expected.N == 0))
+        ) {
+            return ParseResult(std::make_unique<Literal>(expected, parsedValue->template get<std::vector<Value>>()));
+        }
+    }
+    return ParseResult(std::make_unique<Literal>(*parsedValue));
+}
+
+} // 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..ad3dae684a
--- /dev/null
+++ b/src/mbgl/style/expression/match.cpp
@@ -0,0 +1,241 @@
+#include <mbgl/style/expression/match.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+template <typename T>
+void Match<T>::accept(std::function<void(const Expression*)> visit) const {
+    visit(this);
+    input->accept(visit);
+    for (const std::pair<T, std::shared_ptr<Expression>>& branch : branches) {
+        branch.second->accept(visit);
+    }
+    otherwise->accept(visit);
+}
+
+template<> EvaluationResult Match<std::string>::evaluate(const EvaluationParameters& 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 EvaluationParameters& 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>;
+
+
+optional<InputType> parseInputValue(const mbgl::style::conversion::Convertible& input, ParsingContext ctx, 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)) {
+                    ctx.error("Branch labels must be integers no larger than " + std::to_string(Value::maxSafeInteger()) + ".");
+                } else {
+                    type = {type::Number};
+                    result = {static_cast<int64_t>(n)};
+                }
+            },
+            [&] (int64_t n) {
+                if (!Value::isSafeInteger(n)) {
+                    ctx.error("Branch labels must be integers no larger than " + std::to_string(Value::maxSafeInteger()) + ".");
+                } else {
+                    type = {type::Number};
+                    result = {n};
+                }
+            },
+            [&] (double n) {
+                if (!Value::isSafeInteger(n)) {
+                    ctx.error("Branch labels must be integers no larger than " + std::to_string(Value::maxSafeInteger()) + ".");
+                } else if (n != std::floor(n)) {
+                    ctx.error("Numeric branch labels must be integer values.");
+                } else {
+                    type = {type::Number};
+                    result = {static_cast<int64_t>(n)};
+                }
+            },
+            [&] (const std::string& s) {
+                type = {type::String};
+                result = {s};
+            },
+            [&] (const auto&) {
+                ctx.error("Branch labels must be numbers or strings.");
+            }
+        );
+    } else {
+        ctx.error("Branch labels must be numbers or strings.");
+    }
+
+    if (!type) {
+        return result;
+    }
+
+    if (!inputType) {
+        inputType = type;
+    } else if (ctx.checkType(*type)) {
+        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;
+    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 mbgl::style::conversion::Convertible& value, ParsingContext ctx) {
+    using namespace mbgl::style::conversion;
+
+    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.expected && *ctx.expected != type::Value) {
+        outputType = ctx.expected;
+    }
+
+    std::vector<std::pair<std::vector<InputType>,
+                          std::unique_ptr<Expression>>> branches;
+
+    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.concat(i).error("Expected at least one branch label.");
+                return ParseResult();
+            }
+            
+            for (size_t j = 0; j < groupLength; j++) {
+                const optional<InputType> inputValue = parseInputValue(arrayMember(label, j), ctx.concat(i, inputType), inputType);
+                if (!inputValue) {
+                    return ParseResult();
+                }
+                labels.push_back(*inputValue);
+            }
+        } else {
+            const optional<InputType> inputValue = parseInputValue(label, ctx.concat(i, inputType), inputType);
+            if (!inputValue) {
+                return ParseResult();
+            }
+            labels.push_back(*inputValue);
+        }
+        
+        ParseResult output = ctx.concat(i + 1, outputType).parse(arrayMember(value, i + 1));
+        if (!output) {
+            return ParseResult();
+        }
+        
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+        
+        branches.push_back(std::make_pair(std::move(labels), std::move(*output)));
+    }
+
+    auto input = ctx.concat(1, inputType).parse(arrayMember(value, 1));
+    if (!input) {
+        return ParseResult();
+    }
+
+    auto otherwise = ctx.concat(length - 1, outputType).parse(arrayMember(value, length - 1));
+    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&) {
+            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..4e7a9dedad
--- /dev/null
+++ b/src/mbgl/style/expression/parsing_context.cpp
@@ -0,0 +1,122 @@
+
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/at.hpp>
+#include <mbgl/style/expression/array_assertion.hpp>
+#include <mbgl/style/expression/case.hpp>
+#include <mbgl/style/expression/coalesce.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/curve.hpp>
+#include <mbgl/style/expression/let.hpp>
+#include <mbgl/style/expression/literal.hpp>
+#include <mbgl/style/expression/match.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/conversion/get_json_type.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+ParseResult ParsingContext::parse(const mbgl::style::conversion::Convertible& value)
+{
+    using namespace mbgl::style::conversion;
+    
+    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();
+        }
+        
+        if (*op == "literal") {
+            if (length != 2) {
+                error(
+                    "'literal' expression requires exactly one argument, but found " + std::to_string(length - 1) + " instead."
+                );
+                return ParseResult();
+            }
+            
+            parsed = Literal::parse(arrayMember(value, 1), *this);
+        } else if (*op == "match") {
+            parsed = parseMatch(value, *this);
+        } else if (*op == "curve") {
+            parsed = parseCurve(value, *this);
+        } else if (*op == "coalesce") {
+            parsed = Coalesce::parse(value, *this);
+        } else if (*op == "case") {
+            parsed = Case::parse(value, *this);
+        } else if (*op == "array") {
+            parsed = ArrayAssertion::parse(value, *this);
+        } else if (*op == "let") {
+            parsed = Let::parse(value, *this);
+        } else if (*op == "var") {
+            parsed = Var::parse(value, *this);
+        } else if (*op == "at") {
+            parsed = At::parse(value, *this);
+        } else {
+            parsed = parseCompoundExpression(*op, value, *this);
+        }
+    } else {
+        if (isObject(value)) {
+            error(R"(Bare objects invalid. Use ["literal", {...}] instead.)");
+            return ParseResult();
+        }
+        
+        parsed = Literal::parse(value, *this);
+    }
+    
+    if (!parsed) {
+        assert(errors.size() > 0);
+    } else if (expected) {
+        auto wrapForType = [&](const std::string& wrapper, std::unique_ptr<Expression> expression) {
+            std::vector<std::unique_ptr<Expression>> args;
+            args.push_back(std::move(expression));
+            return createCompoundExpression(wrapper, std::move(args), *this);
+        };
+        
+        const type::Type actual = (*parsed)->getType();
+        if (*expected == type::Color && (actual == type::String || actual == type::Value)) {
+            parsed = wrapForType("to-color", std::move(*parsed));
+        } else if (*expected != type::Value && actual == type::Value) {
+            if (*expected == type::String) {
+                parsed = wrapForType("string", std::move(*parsed));
+            } else if (*expected == type::Number) {
+                parsed = wrapForType("number", std::move(*parsed));
+            } else if (*expected == type::Boolean) {
+                parsed = wrapForType("boolean", std::move(*parsed));
+            }
+        }
+    
+        checkType((*parsed)->getType());
+        if (errors.size() > 0) {
+            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/value.cpp b/src/mbgl/style/expression/value.cpp
new file mode 100644
index 0000000000..b0ae9d3217
--- /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 mbgl::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);
+                const std::string tname = type::toString(t);
+                if (!itemType) {
+                    itemType = {t};
+                } else if (type::toString(*itemType) == tname) {
+                    continue;
+                } else {
+                    itemType = {type::Value};
+                    break;
+                }
+            }
+            
+            if (!itemType) { itemType = {type::Value}; }
+
+            return type::Array(*itemType, 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 mbgl::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.String(entry.first);
+                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;
+        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;
+        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 mbgl::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;
+    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;
+            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<mbgl::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..ccbc59a5f0
--- /dev/null
+++ b/src/mbgl/style/function/expression.cpp
@@ -0,0 +1,69 @@
+#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>();
+    }
+};
+
+bool Expression::isFeatureConstant() const {
+    bool featureConstant = true;
+    accept([&](const Expression* expression) {
+        if (auto e = dynamic_cast<const CompoundExpressionBase*>(expression)) {
+            const std::string name = e->getName();
+            if (name == "get" || name == "has") {
+                optional<std::size_t> parameterCount = e->getParameterCount();
+                featureConstant = featureConstant && (parameterCount && *parameterCount > 1);
+            } else {
+                featureConstant = featureConstant && !(
+                    name == "properties" ||
+                    name == "geometry-type" ||
+                    name == "id"
+                );
+            }
+        }
+    });
+    return featureConstant;
+}
+
+bool Expression::isZoomConstant() const {
+    bool zoomConstant = true;
+    accept([&](const Expression* expression) {
+        if (auto e = dynamic_cast<const CompoundExpressionBase*>(expression)) {
+            if (e->getName() == "zoom") {
+                zoomConstant = false;
+            }
+        }
+    });
+    return zoomConstant;
+}
+
+EvaluationResult Expression::evaluate(float z, const Feature& feature) const {
+    GeoJSONFeature f(feature);
+    return this->evaluate(EvaluationParameters(z, &f));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/test/style/conversion/function.test.cpp b/test/style/conversion/function.test.cpp
index 9e8a6b3a7f..10683458ed 100644
--- a/test/style/conversion/function.test.cpp
+++ b/test/style/conversion/function.test.cpp
@@ -3,6 +3,8 @@
 #include <mbgl/style/conversion/json.hpp>
 #include <mbgl/style/conversion/constant.hpp>
 #include <mbgl/style/conversion/function.hpp>
+#include <mbgl/style/conversion/data_driven_property_value.hpp>
+#include <mbgl/util/rapidjson.hpp>
 
 using namespace mbgl;
 using namespace mbgl::style;
@@ -50,3 +52,37 @@ TEST(StyleConversion, Function) {
     ASSERT_FALSE(fn9);
     ASSERT_EQ("function base must be a number", error.message);
 }
+
+TEST(StyleConversion, CompositeFunctionExpression) {
+    Error error;
+
+    auto parseFunction = [&](const std::string& src) {
+        JSDocument doc;
+        doc.Parse<0>(src);
+        return convert<DataDrivenPropertyValue<float>>(doc, error);
+    };
+
+    auto fn1 = parseFunction(R"({"expression": ["curve", ["linear"], ["zoom"], 0, ["number", ["get", "x"]], 10, 10]})");
+    ASSERT_TRUE(fn1);
+    
+    auto fn2 = parseFunction(R"({
+        "expression": ["coalesce", ["curve", ["linear"], ["zoom"], 0, ["number", ["get", "x"]], 10, 10], 0]
+    })");
+    ASSERT_TRUE(fn2);
+
+//    auto fn3 = parseFunction(R"({
+//        "expression": ["let", "a", 0, ["curve", ["linear"], ["zoom"], 0, ["number", ["get", "x"]], 10, 10] ]
+//    })");
+//    ASSERT_TRUE(fn3);
+
+//    auto fn4 = parseFunction(R"({
+//        "expression": ["coalesce", ["let", "a", 0, ["curve", ["linear"], ["zoom"], 0, ["number", ["get", "x"]], 10, 10], 0 ]
+//    })");
+//    ASSERT_TRUE(fn4);
+
+    auto fn5 = parseFunction(R"({
+        "expression": ["coalesce", ["curve", ["linear"], ["number", ["get", "x"]], 0, ["zoom"], 10, 10], 0]
+    })");
+    ASSERT_FALSE(fn5);
+    ASSERT_EQ(R"("zoom" expression may only be used as input to a top-level "curve" expression.)", error.message);
+}
diff --git a/test/style/conversion/stringify.test.cpp b/test/style/conversion/stringify.test.cpp
index 0b2940a0e0..4b0e828b31 100644
--- a/test/style/conversion/stringify.test.cpp
+++ b/test/style/conversion/stringify.test.cpp
@@ -69,9 +69,9 @@ TEST(Stringify, Map) {
 }
 
 TEST(Stringify, Value) {
-    ASSERT_EQ(stringify(Value(true)), "true");
-    ASSERT_EQ(stringify(Value(uint64_t(0))), "0");
-    ASSERT_EQ(stringify(Value(1.2)), "1.2");
+    ASSERT_EQ(stringify(mbgl::Value(true)), "true");
+    ASSERT_EQ(stringify(mbgl::Value(uint64_t(0))), "0");
+    ASSERT_EQ(stringify(mbgl::Value(1.2)), "1.2");
 }
 
 TEST(Stringify, Filter) {