Bump Mapbox GL Native

mapbox-gl-native @ 92608f58858d77c17a65ae9b29758e74bb2da7d2

73 files changed, 5131 insertions, 189 deletions

diff --git a/include/mbgl/renderer/renderer.hpp b/include/mbgl/renderer/renderer.hpp
index 21d411afd0..0937e9334b 100644
--- a/include/mbgl/renderer/renderer.hpp
+++ b/include/mbgl/renderer/renderer.hpp
@@ -40,6 +40,8 @@ public:
     std::vector<Feature> queryRenderedFeatures(const ScreenBox& box, const RenderedQueryOptions& options = {}) const;
     std::vector<Feature> querySourceFeatures(const std::string& sourceID, const SourceQueryOptions& options = {}) const;
     AnnotationIDs queryPointAnnotations(const ScreenBox& box) const;
+    AnnotationIDs queryShapeAnnotations(const ScreenBox& box) const;
+    AnnotationIDs getAnnotationIDs(const std::vector<Feature>&) const;
 
     // Debug
     void dumpDebugLogs();
diff --git a/include/mbgl/style/conversion/data_driven_property_value.hpp b/include/mbgl/style/conversion/data_driven_property_value.hpp
index 1e54c15a49..8880d28fb1 100644
--- a/include/mbgl/style/conversion/data_driven_property_value.hpp
+++ b/include/mbgl/style/conversion/data_driven_property_value.hpp
@@ -4,6 +4,13 @@
 #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/is_expression.hpp>
+#include <mbgl/style/expression/is_constant.hpp>
+#include <mbgl/style/expression/find_zoom_curve.hpp>
+
+#include <unordered_set>
+
 
 namespace mbgl {
 namespace style {
@@ -11,9 +18,27 @@ namespace conversion {
 
 template <class T>
 struct Converter<DataDrivenPropertyValue<T>> {
+
     optional<DataDrivenPropertyValue<T>> operator()(const Convertible& value, Error& error) const {
         if (isUndefined(value)) {
             return DataDrivenPropertyValue<T>();
+        } else if (expression::isExpression(value)) {
+            optional<std::unique_ptr<Expression>> expression = convert<std::unique_ptr<Expression>>(
+                value,
+                error,
+                valueTypeToExpressionType<T>());
+            
+            if (!expression) {
+                return {};
+            }
+            
+            if (isFeatureConstant(**expression)) {
+                return DataDrivenPropertyValue<T>(CameraFunction<T>(std::move(*expression)));
+            } else if (isZoomConstant(**expression)) {
+                return DataDrivenPropertyValue<T>(SourceFunction<T>(std::move(*expression)));
+            } else {
+                return DataDrivenPropertyValue<T>(CompositeFunction<T>(std::move(*expression)));
+            }
         } else if (!isObject(value)) {
             optional<T> constant = convert<T>(value, error);
             if (!constant) {
diff --git a/include/mbgl/style/conversion/expression.hpp b/include/mbgl/style/conversion/expression.hpp
new file mode 100644
index 0000000000..c5fcf906a7
--- /dev/null
+++ b/include/mbgl/style/conversion/expression.hpp
@@ -0,0 +1,39 @@
+#pragma once
+
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/conversion.hpp>
+
+#include <memory>
+
+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 Convertible& value, Error& error, type::Type expected) const {
+        ParsingContext ctx(optional<type::Type> {expected});
+        ParseResult parsed = ctx.parse(value);
+        if (parsed) {
+            return std::move(*parsed);
+        }
+        std::string combinedError;
+        for (const ParsingError& parsingError : ctx.getErrors()) {
+            if (combinedError.size() > 0) {
+                combinedError += "\n";
+            }
+            if (parsingError.key.size() > 0) {
+                combinedError += parsingError.key + ": ";
+            }
+            combinedError += 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..f7efebccce
--- /dev/null
+++ b/include/mbgl/style/conversion/get_json_type.hpp
@@ -0,0 +1,14 @@
+#pragma once
+
+#include <mbgl/style/conversion.hpp>
+#include <string>
+
+namespace mbgl {
+namespace style {
+namespace conversion {
+
+std::string getJSONType(const Convertible& value);
+
+} // 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..97117de2ec 100644
--- a/include/mbgl/style/conversion/property_value.hpp
+++ b/include/mbgl/style/conversion/property_value.hpp
@@ -4,6 +4,11 @@
 #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>
+#include <mbgl/style/expression/is_constant.hpp>
+#include <mbgl/style/expression/is_expression.hpp>
+#include <mbgl/style/expression/find_zoom_curve.hpp>
 
 namespace mbgl {
 namespace style {
@@ -14,6 +19,17 @@ struct Converter<PropertyValue<T>> {
     optional<PropertyValue<T>> operator()(const Convertible& value, Error& error) const {
         if (isUndefined(value)) {
             return PropertyValue<T>();
+        } else if (isExpression(value)) {
+            optional<std::unique_ptr<Expression>> expression = convert<std::unique_ptr<Expression>>(value, error, valueTypeToExpressionType<T>());
+            if (!expression) {
+                return {};
+            }
+            if (isFeatureConstant(**expression)) {
+                return { CameraFunction<T>(std::move(*expression)) };
+            } else {
+                error = { "property expressions 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..2516eea024
--- /dev/null
+++ b/include/mbgl/style/expression/array_assertion.hpp
@@ -0,0 +1,39 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+#include <memory>
+
+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 EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>& visit) const override;
+
+    bool operator==(const Expression& e) const override {
+        if (auto rhs = dynamic_cast<const ArrayAssertion*>(&e)) {
+            return getType() == rhs->getType() && *input == *(rhs->input);
+        }
+        return false;
+    }
+
+private:
+    std::unique_ptr<Expression> input;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/assertion.hpp b/include/mbgl/style/expression/assertion.hpp
new file mode 100644
index 0000000000..504d49f4e5
--- /dev/null
+++ b/include/mbgl/style/expression/assertion.hpp
@@ -0,0 +1,33 @@
+#pragma once
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/conversion.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <memory>
+#include <vector>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Assertion : public Expression  {
+public:
+    Assertion(type::Type type_, std::vector<std::unique_ptr<Expression>> inputs_) :
+        Expression(type_),
+        inputs(std::move(inputs_))
+    {}
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext& ctx);
+
+    EvaluationResult evaluate(const EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>& visit) const override;
+    
+    bool operator==(const Expression& e) const override;
+
+private:
+    std::vector<std::unique_ptr<Expression>> inputs;
+};
+
+} // 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..e3eefa4fe8
--- /dev/null
+++ b/include/mbgl/style/expression/at.hpp
@@ -0,0 +1,38 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/conversion.hpp>
+#include <memory>
+
+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 EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>&) const override;
+
+    bool operator==(const Expression& e) const override {
+        if (auto rhs = dynamic_cast<const At*>(&e)) {
+            return *index == *(rhs->index) && *input == *(rhs->input);
+        }
+        return false;
+    }
+
+private:
+    std::unique_ptr<Expression> index;
+    std::unique_ptr<Expression> input;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/boolean_operator.hpp b/include/mbgl/style/expression/boolean_operator.hpp
new file mode 100644
index 0000000000..01231d706b
--- /dev/null
+++ b/include/mbgl/style/expression/boolean_operator.hpp
@@ -0,0 +1,49 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/conversion.hpp>
+#include <memory>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Any : public Expression  {
+public:
+    Any(std::vector<std::unique_ptr<Expression>> inputs_) :
+        Expression(type::Boolean),
+        inputs(std::move(inputs_))
+    {}
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext& ctx);
+
+    EvaluationResult evaluate(const EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>& visit) const override;
+    bool operator==(const Expression& e) const override;
+
+private:
+    std::vector<std::unique_ptr<Expression>> inputs;
+};
+
+class All : public Expression  {
+public:
+    All(std::vector<std::unique_ptr<Expression>> inputs_) :
+        Expression(type::Boolean),
+        inputs(std::move(inputs_))
+    {}
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext& ctx);
+
+    EvaluationResult evaluate(const EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>& visit) const override;
+
+    bool operator==(const Expression& e) const override;
+
+private:
+    std::vector<std::unique_ptr<Expression>> inputs;
+};
+
+} // 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..ece2fe0329
--- /dev/null
+++ b/include/mbgl/style/expression/case.hpp
@@ -0,0 +1,36 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/conversion.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+
+#include <memory>
+#include <vector>
+
+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 EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>& visit) const override;
+    
+    bool operator==(const Expression& e) 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..90e5169de7
--- /dev/null
+++ b/include/mbgl/style/expression/check_subtype.hpp
@@ -0,0 +1,17 @@
+#pragma once
+
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/util/optional.hpp>
+#include <memory>
+
+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..4e6a9b3793
--- /dev/null
+++ b/include/mbgl/style/expression/coalesce.hpp
@@ -0,0 +1,45 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/conversion.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+
+#include <memory>
+#include <map>
+
+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 EvaluationContext& params) const override;
+    
+    void eachChild(const std::function<void(const Expression&)>& visit) const override;
+
+    bool operator==(const Expression& e) 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/coercion.hpp b/include/mbgl/style/expression/coercion.hpp
new file mode 100644
index 0000000000..665bb7ce7c
--- /dev/null
+++ b/include/mbgl/style/expression/coercion.hpp
@@ -0,0 +1,34 @@
+#pragma once
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/conversion.hpp>
+#include <memory>
+#include <vector>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+/**
+ * Special form for error-coalescing coercion expressions "to-number",
+ * "to-color".  Since these coercions can fail at runtime, they accept multiple
+ * arguments, only evaluating one at a time until one succeeds.
+ */
+class Coercion : public Expression  {
+public:
+    Coercion(type::Type type_, std::vector<std::unique_ptr<Expression>> inputs_);
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext& ctx);
+
+    EvaluationResult evaluate(const EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>& visit) const override;
+
+    bool operator==(const Expression& e) const override;
+private:
+    EvaluationResult (*coerceSingleValue) (const Value& v);
+    std::vector<std::unique_ptr<Expression>> inputs;
+};
+
+} // 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..fc3edbfd4a
--- /dev/null
+++ b/include/mbgl/style/expression/compound_expression.hpp
@@ -0,0 +1,138 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/conversion.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/expression/value.hpp>
+
+#include <mbgl/util/optional.hpp>
+#include <mbgl/util/variant.hpp>
+
+#include <memory>
+#include <vector>
+
+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 EvaluationContext& evaluationParams) const override {
+        return signature.apply(evaluationParams, args);
+    }
+    
+    void eachChild(const std::function<void(const Expression&)>& visit) const override {
+        for (const std::unique_ptr<Expression>& e : args) {
+            visit(*e);
+        }
+    }
+
+    bool operator==(const Expression& e) const override {
+        if (auto rhs = dynamic_cast<const CompoundExpression*>(&e)) {
+            return getName() == rhs->getName() && Expression::childrenEqual(args, rhs->args);
+        }
+        return false;
+    }
+    
+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/expression.hpp b/include/mbgl/style/expression/expression.hpp
new file mode 100644
index 0000000000..1954d8b090
--- /dev/null
+++ b/include/mbgl/style/expression/expression.hpp
@@ -0,0 +1,169 @@
+#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 {
+
+class EvaluationError {
+public:
+    std::string message;
+};
+
+class EvaluationContext {
+public:
+    EvaluationContext(float zoom_) : zoom(zoom_), feature(nullptr) {}
+    EvaluationContext(GeometryTileFeature const * feature_) : zoom(optional<float>()), feature(feature_) {}
+    EvaluationContext(float zoom_, GeometryTileFeature const * feature_) :
+        zoom(zoom_), feature(feature_)
+    {}
+    EvaluationContext(optional<float> zoom_, GeometryTileFeature const * feature_, optional<double> heatmapDensity_) :
+        zoom(std::move(zoom_)), feature(feature_), heatmapDensity(std::move(heatmapDensity_))
+    {}
+    
+    optional<float> zoom;
+    GeometryTileFeature const * feature;
+    optional<double> heatmapDensity;
+};
+
+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>();
+    }
+};
+
+class EvaluationResult : public Result<Value> {
+public:
+    using Result::Result; // NOLINT
+    
+    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 also provides a static
+    ParseResult ExpressionClass::parse(const V&, ParsingContext),
+    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 EvaluationContext& params) const = 0;
+    virtual void eachChild(const std::function<void(const Expression&)>&) const = 0;
+    virtual bool operator==(const Expression&) const = 0;
+    bool operator!=(const Expression& rhs) const {
+        return !operator==(rhs);
+    }
+
+    type::Type getType() const { return type; };
+    
+    EvaluationResult evaluate(optional<float> zoom, const Feature& feature, optional<double> heatmapDensity) const;
+
+protected:
+    template <typename T>
+    static bool childrenEqual(const T& lhs, const T& rhs) {
+        if (lhs.size() != rhs.size()) return false;
+        for (auto leftChild = lhs.begin(), rightChild = rhs.begin();
+             leftChild != lhs.end();
+             leftChild++, rightChild++)
+         {
+             if (!Expression::childEqual(*leftChild, *rightChild)) return false;
+         }
+         return true;
+    }
+    
+    static bool childEqual(const std::unique_ptr<Expression>& lhs, const std::unique_ptr<Expression>& rhs) {
+        return *lhs == *rhs;
+    }
+    
+    template <typename T>
+    static bool childEqual(const std::pair<T, std::unique_ptr<Expression>>& lhs,
+                           const std::pair<T, std::unique_ptr<Expression>>& rhs) {
+        return lhs.first == rhs.first && *(lhs.second) == *(rhs.second);
+    }
+    
+    template <typename T>
+    static bool childEqual(const std::pair<T, std::shared_ptr<Expression>>& lhs,
+                           const std::pair<T, std::shared_ptr<Expression>>& rhs) {
+        return lhs.first == rhs.first && *(lhs.second) == *(rhs.second);
+    }
+    
+    static bool childEqual(const std::pair<std::unique_ptr<Expression>, std::unique_ptr<Expression>>& lhs,
+                           const std::pair<std::unique_ptr<Expression>, std::unique_ptr<Expression>>& rhs) {
+        return *(lhs.first) == *(rhs.first) && *(lhs.second) == *(rhs.second);
+    }
+    
+    
+
+private:
+    type::Type type;
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/find_zoom_curve.hpp b/include/mbgl/style/expression/find_zoom_curve.hpp
new file mode 100644
index 0000000000..6301938033
--- /dev/null
+++ b/include/mbgl/style/expression/find_zoom_curve.hpp
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/interpolate.hpp>
+#include <mbgl/style/expression/step.hpp>
+
+#include <mbgl/util/variant.hpp>
+#include <mbgl/util/optional.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+optional<variant<const InterpolateBase*, const Step*, ParsingError>> findZoomCurve(const expression::Expression* e);
+
+variant<const InterpolateBase*, const Step*> findZoomCurveChecked(const expression::Expression* e);
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/get_covering_stops.hpp b/include/mbgl/style/expression/get_covering_stops.hpp
new file mode 100644
index 0000000000..157aefe7bc
--- /dev/null
+++ b/include/mbgl/style/expression/get_covering_stops.hpp
@@ -0,0 +1,18 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/util/range.hpp>
+#include <memory>
+#include <map>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+// Return the smallest range of stops that covers the interval [lower, upper]
+Range<float> getCoveringStops(const std::map<double, std::unique_ptr<Expression>>& stops,
+                              const double lower, const double upper);
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/interpolate.hpp b/include/mbgl/style/expression/interpolate.hpp
new file mode 100644
index 0000000000..2dcb5a32a4
--- /dev/null
+++ b/include/mbgl/style/expression/interpolate.hpp
@@ -0,0 +1,177 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/get_covering_stops.hpp>
+#include <mbgl/style/conversion.hpp>
+
+#include <mbgl/util/interpolate.hpp>
+#include <mbgl/util/range.hpp>
+#include <mbgl/util/unitbezier.hpp>
+
+#include <memory>
+#include <map>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+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);
+    }
+    
+    bool operator==(const ExponentialInterpolator& rhs) const {
+        return base == rhs.base;
+    }
+};
+
+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);
+    }
+    
+    bool operator==(const CubicBezierInterpolator& rhs) const {
+        return ub == rhs.ub;
+    }
+    
+    util::UnitBezier ub;
+};
+
+
+ParseResult parseInterpolate(const mbgl::style::conversion::Convertible& value, ParsingContext& ctx);
+
+class InterpolateBase : public Expression {
+public:
+    using Interpolator = variant<ExponentialInterpolator, CubicBezierInterpolator>;
+
+    InterpolateBase(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_))
+    {}
+
+    const std::unique_ptr<Expression>& getInput() const { return input; }
+
+    void eachChild(const std::function<void(const Expression&)>& visit) const override {
+        visit(*input);
+        for (const std::pair<const double, const std::unique_ptr<Expression>&>& stop : stops) {
+            visit(*stop.second);
+        }
+    }
+    
+    // Return the smallest range of stops that covers the interval [lower, upper]
+    Range<float> getCoveringStops(const double lower, const double upper) const {
+        return ::mbgl::style::expression::getCoveringStops(stops, lower, upper);
+    }
+    
+    double interpolationFactor(const Range<double>& inputLevels, const double inputValue) const {
+        return interpolator.match(
+            [&](const auto& interp) { return interp.interpolationFactor(inputLevels, inputValue); }
+        );
+    }
+
+protected:
+    const Interpolator interpolator;
+    const std::unique_ptr<Expression> input;
+    const std::map<double, std::unique_ptr<Expression>> stops;
+};
+
+template <typename T>
+class Interpolate : public InterpolateBase {
+public:
+    Interpolate(type::Type type_,
+          Interpolator interpolator_,
+          std::unique_ptr<Expression> input_,
+          std::map<double, std::unique_ptr<Expression>> stops_
+    ) : InterpolateBase(std::move(type_), std::move(interpolator_), std::move(input_), std::move(stops_))
+    {
+        static_assert(util::Interpolatable<T>::value, "Interpolate expression requires an interpolatable value type.");
+    }
+    
+    EvaluationResult evaluate(const EvaluationContext& 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();
+            }
+
+            if (!lower->is<T>()) {
+                return EvaluationError {
+                    "Expected value to be of type " + toString(valueTypeToExpressionType<T>()) +
+                    ", but found " + toString(typeOf(*lower)) + " instead."
+                };
+            }
+            
+            if (!upper->is<T>()) {
+                return EvaluationError {
+                    "Expected value to be of type " + toString(valueTypeToExpressionType<T>()) +
+                    ", but found " + toString(typeOf(*upper)) + " instead."
+                };
+            }
+            return util::interpolate(lower->get<T>(), upper->get<T>(), t);
+        }
+    }
+    
+    bool operator==(const Expression& e) const override {
+        if (auto rhs = dynamic_cast<const Interpolate*>(&e)) {
+            if (interpolator != rhs->interpolator ||
+                *input != *(rhs->input) ||
+                stops.size() != rhs->stops.size())
+            {
+                return false;
+            }
+            
+            return Expression::childrenEqual(stops, rhs->stops);
+        }
+        return false;
+    }
+};
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/is_constant.hpp b/include/mbgl/style/expression/is_constant.hpp
new file mode 100644
index 0000000000..29e03ccbc0
--- /dev/null
+++ b/include/mbgl/style/expression/is_constant.hpp
@@ -0,0 +1,35 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+template <typename T>
+bool isGlobalPropertyConstant(const Expression& expression, const T& properties) {
+    if (auto e = dynamic_cast<const CompoundExpressionBase*>(&expression)) {
+        for (const std::string& property : properties) {
+            if (e->getName() == property) {
+                return false;
+            }
+        }
+    }
+    
+    bool isConstant = true;
+    expression.eachChild([&](const Expression& e) {
+        if (isConstant && !isGlobalPropertyConstant(e, properties)) {
+            isConstant = false;
+        }
+    });
+    return isConstant;
+};
+
+bool isFeatureConstant(const Expression& expression);
+bool isZoomConstant(const Expression& e);
+
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/is_expression.hpp b/include/mbgl/style/expression/is_expression.hpp
new file mode 100644
index 0000000000..77c489619c
--- /dev/null
+++ b/include/mbgl/style/expression/is_expression.hpp
@@ -0,0 +1,13 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+bool isExpression(const conversion::Convertible& value);
+
+} // 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..aaa16ca0c2
--- /dev/null
+++ b/include/mbgl/style/expression/let.hpp
@@ -0,0 +1,72 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+#include <memory>
+#include <map>
+
+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 EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>&) const override;
+
+    bool operator==(const Expression& e) const override {
+        if (auto rhs = dynamic_cast<const Let*>(&e)) {
+            return *result == *(rhs->result);
+        }
+        return false;
+    }
+
+    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 EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>&) const override;
+
+    bool operator==(const Expression& e) const override {
+        if (auto rhs = dynamic_cast<const Var*>(&e)) {
+            return *value == *(rhs->value);
+        }
+        return false;
+    }
+    
+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..a0819c7e73
--- /dev/null
+++ b/include/mbgl/style/expression/literal.hpp
@@ -0,0 +1,38 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+#include <memory>
+
+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 EvaluationContext&) const override {
+        return value;
+    }
+    
+    static ParseResult parse(const mbgl::style::conversion::Convertible&, ParsingContext&);
+
+    void eachChild(const std::function<void(const Expression&)>&) const override {}
+    
+    bool operator==(const Expression& e) const override {
+        if (auto rhs = dynamic_cast<const Literal*>(&e)) {
+            return value == rhs->value;
+        }
+        return false;
+    }
+    
+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..e17fe96bfe
--- /dev/null
+++ b/include/mbgl/style/expression/match.hpp
@@ -0,0 +1,45 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+#include <memory>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+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 eachChild(const std::function<void(const Expression&)>& visit) const override;
+
+    bool operator==(const Expression& e) const override;
+
+    EvaluationResult evaluate(const EvaluationContext& 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..a983789cbd
--- /dev/null
+++ b/include/mbgl/style/expression/parsing_context.hpp
@@ -0,0 +1,148 @@
+#pragma once
+
+#include <mbgl/util/optional.hpp>
+#include <mbgl/util/string.hpp>
+#include <mbgl/style/expression/type.hpp>
+#include <mbgl/style/conversion.hpp>
+
+#include <map>
+#include <string>
+#include <vector>
+#include <memory>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Expression;
+
+struct ParsingError {
+    std::string message;
+    std::string key;
+    bool operator==(const ParsingError& rhs) const { return message == rhs.message && key == rhs.key; }
+};
+
+using ParseResult = optional<std::unique_ptr<Expression>>;
+
+namespace detail {
+
+class Scope {
+public:
+    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() : errors(std::make_shared<std::vector<ParsingError>>()) {}
+    ParsingContext(std::string key_) : key(std::move(key_)), errors(std::make_shared<std::vector<ParsingError>>()) {}
+    explicit ParsingContext(optional<type::Type> expected_)
+        : expected(std::move(expected_)),
+          errors(std::make_shared<std::vector<ParsingError>>())
+    {}
+    ParsingContext(ParsingContext&&) = default;
+    
+    ParsingContext(const ParsingContext&) = delete;
+    ParsingContext& operator=(const ParsingContext&) = delete;
+
+    std::string getKey() const { return key; }
+    optional<type::Type> getExpected() const { return expected; }
+    const std::vector<ParsingError>& getErrors() const { return *errors; }
+
+    /*
+        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);
+    
+    /*
+        Parse a child expression.
+    */
+    ParseResult parse(const mbgl::style::conversion::Convertible&,
+                      std::size_t,
+                      optional<type::Type> = {});
+    
+    /*
+        Parse a child expression.
+    */
+    ParseResult parse(const mbgl::style::conversion::Convertible&,
+                      std::size_t index,
+                      optional<type::Type>,
+                      const std::map<std::string, std::shared_ptr<Expression>>&);
+
+    /*
+        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 + "[" + util::toString(child) + "]"});
+    }
+    
+    void error(std::string message, std::size_t child, std::size_t grandchild) {
+        errors->push_back({message, key + "[" + util::toString(child) + "][" + util::toString(grandchild) + "]"});
+    }
+    
+    void appendErrors(ParsingContext&& ctx) {
+        errors->reserve(errors->size() + ctx.errors->size());
+        std::move(ctx.errors->begin(), ctx.errors->end(), std::inserter(*errors, errors->end()));
+        ctx.errors->clear();
+    }
+    
+    void clearErrors() {
+        errors->clear();
+    }
+    
+private:
+    ParsingContext(std::string key_,
+                   std::shared_ptr<std::vector<ParsingError>> errors_,
+                   optional<type::Type> expected_,
+                   std::shared_ptr<detail::Scope> scope_)
+        : key(std::move(key_)),
+          expected(std::move(expected_)),
+          scope(std::move(scope_)),
+        errors(std::move(errors_))
+    {}
+    
+    std::string key;
+    optional<type::Type> expected;
+    std::shared_ptr<detail::Scope> scope;
+    std::shared_ptr<std::vector<ParsingError>> errors;
+};
+
+using ParseFunction = ParseResult (*)(const conversion::Convertible&, ParsingContext&);
+using ExpressionRegistry = std::unordered_map<std::string, ParseFunction>;
+const ExpressionRegistry& getExpressionRegistry();
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/step.hpp b/include/mbgl/style/expression/step.hpp
new file mode 100644
index 0000000000..e3c49bc609
--- /dev/null
+++ b/include/mbgl/style/expression/step.hpp
@@ -0,0 +1,45 @@
+
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/conversion.hpp>
+
+#include <mbgl/util/range.hpp>
+
+#include <memory>
+#include <map>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class Step : public Expression {
+public:
+    Step(const type::Type& type_,
+          std::unique_ptr<Expression> input_,
+          std::map<double, std::unique_ptr<Expression>> stops_
+    ) : Expression(type_),
+        input(std::move(input_)),
+        stops(std::move(stops_))
+    {}
+
+    EvaluationResult evaluate(const EvaluationContext& params) const override;
+    void eachChild(const std::function<void(const Expression&)>& visit) const override;
+
+    const std::unique_ptr<Expression>& getInput() const { return input; }
+    Range<float> getCoveringStops(const double lower, const double upper) const;
+
+    bool operator==(const Expression& e) const override;
+
+    static ParseResult parse(const mbgl::style::conversion::Convertible& value, ParsingContext& ctx);
+
+private:
+    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/type.hpp b/include/mbgl/style/expression/type.hpp
new file mode 100644
index 0000000000..da59eb001c
--- /dev/null
+++ b/include/mbgl/style/expression/type.hpp
@@ -0,0 +1,112 @@
+#pragma once
+
+#include <mbgl/util/optional.hpp>
+#include <mbgl/util/string.hpp>
+#include <mbgl/util/variant.hpp>
+#include <vector>
+
+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 {
+    explicit 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) + ", " + util::toString(*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..8baa9d2dba
--- /dev/null
+++ b/include/mbgl/style/expression/value.hpp
@@ -0,0 +1,153 @@
+#pragma once
+
+#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>
+
+#include <array>
+#include <vector>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+struct Value;
+
+using ValueBase = variant<
+    NullValue,
+    bool,
+    double,
+    std::string,
+    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..25b38e3616 100644
--- a/include/mbgl/style/function/camera_function.hpp
+++ b/include/mbgl/style/function/camera_function.hpp
@@ -1,10 +1,18 @@
 #pragma once
 
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/interpolate.hpp>
+#include <mbgl/style/expression/step.hpp>
+#include <mbgl/style/expression/find_zoom_curve.hpp>
+#include <mbgl/style/expression/value.hpp>
+#include <mbgl/style/expression/is_constant.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>
 #include <mbgl/util/variant.hpp>
 
+
 namespace mbgl {
 namespace style {
 
@@ -18,24 +26,60 @@ public:
             IntervalStops<T>>,
         variant<
             IntervalStops<T>>>;
+    
+    CameraFunction(std::unique_ptr<expression::Expression> expression_)
+         : expression(std::move(expression_)),
+           zoomCurve(expression::findZoomCurveChecked(expression.get()))
+    {
+        assert(!expression::isZoomConstant(*expression));
+        assert(expression::isFeatureConstant(*expression));
+    }
 
     CameraFunction(Stops stops_)
-        : stops(std::move(stops_)) {
-    }
+        : stops(std::move(stops_)),
+          expression(stops.match([&] (const auto& s) {
+            return expression::Convert::toExpression(s);
+          })),
+          zoomCurve(expression::findZoomCurveChecked(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::EvaluationContext(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.match(
+            [&](const expression::InterpolateBase* z) {
+                return z->interpolationFactor(Range<double> { inputLevels.min, inputLevels.max }, inputValue);
+            },
+            [&](const expression::Step*) { return 0.0f; }
+        );
+    }
+    
+    Range<float> getCoveringStops(const float lower, const float upper) const {
+        return zoomCurve.match(
+            [&](auto z) { return z->getCoveringStops(lower, upper); }
+        );
     }
     
     friend bool operator==(const CameraFunction& lhs,
                            const CameraFunction& rhs) {
-        return lhs.stops == rhs.stops;
+        return *lhs.expression == *rhs.expression;
     }
 
-    Stops stops;
     bool useIntegerZoom = false;
+    
+    // retained for compatibility with pre-expression function API
+    Stops stops;
+
+private:
+    std::shared_ptr<expression::Expression> expression;
+    const variant<const expression::InterpolateBase*, const expression::Step*> zoomCurve;
 };
 
 } // namespace style
diff --git a/include/mbgl/style/function/composite_function.hpp b/include/mbgl/style/function/composite_function.hpp
index 7b524b6021..b44bf8e6fe 100644
--- a/include/mbgl/style/function/composite_function.hpp
+++ b/include/mbgl/style/function/composite_function.hpp
@@ -1,5 +1,12 @@
 #pragma once
 
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/interpolate.hpp>
+#include <mbgl/style/expression/step.hpp>
+#include <mbgl/style/expression/find_zoom_curve.hpp>
+#include <mbgl/style/expression/value.hpp>
+#include <mbgl/style/expression/is_constant.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,110 +50,71 @@ 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)
-                    }
-                };
-            }
-        );
+    CompositeFunction(std::unique_ptr<expression::Expression> expression_)
+    :   expression(std::move(expression_)),
+        zoomCurve(expression::findZoomCurveChecked(expression.get()))
+    {
+        assert(!expression::isZoomConstant(*expression));
+        assert(!expression::isFeatureConstant(*expression));
     }
 
-    // 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)
-        };
-    }
-
-    // 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);
+        })),
+        zoomCurve(expression::findZoomCurveChecked(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::EvaluationContext({zoom}, &feature));
+        if (result) {
+            const optional<T> typed = expression::fromExpressionValue<T>(*result);
+            return typed ? *typed : defaultValue ? *defaultValue : finalDefaultValue;
         }
-        return evaluateFinal(coveringRanges(zoom), *value, finalDefaultValue);
+        return defaultValue ? *defaultValue : finalDefaultValue;
+    }
+    
+    float interpolationFactor(const Range<float>& inputLevels, const float inputValue) const {
+        return zoomCurve.match(
+            [&](const expression::InterpolateBase* z) {
+                return z->interpolationFactor(Range<double> { inputLevels.min, inputLevels.max }, inputValue);
+            },
+            [&](const expression::Step*) { return 0.0f; }
+        );
+    }
+    
+    Range<float> getCoveringStops(const float lower, const float upper) const {
+        return zoomCurve.match(
+            [&](auto z) { return z->getCoveringStops(lower, upper); }
+        );
     }
 
     friend bool operator==(const CompositeFunction& lhs,
                            const CompositeFunction& rhs) {
-        return std::tie(lhs.property, lhs.stops, lhs.defaultValue)
-            == std::tie(rhs.property, rhs.stops, rhs.defaultValue);
+        return *lhs.expression == *rhs.expression;
     }
 
     std::string property;
     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 variant<const expression::InterpolateBase*, const expression::Step*> 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..ed35b4bf14
--- /dev/null
+++ b/include/mbgl/style/function/convert.hpp
@@ -0,0 +1,351 @@
+#pragma once
+
+#include <mbgl/style/expression/array_assertion.hpp>
+#include <mbgl/style/expression/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/coercion.hpp>
+#include <mbgl/style/expression/interpolate.hpp>
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/literal.hpp>
+#include <mbgl/style/expression/match.hpp>
+#include <mbgl/style/expression/step.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 <mbgl/util/enum.hpp>
+#include <mbgl/style/types.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 eachChild(const std::function<void(const Expression&)>&) const override {}
+    
+    bool operator==(const Expression& e) const override {
+        return dynamic_cast<const ErrorExpression*>(&e);
+    }
+
+    EvaluationResult evaluate(const EvaluationContext&) 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(type::Type 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);
+        assert(get);
+        assert(ctx.getErrors().size() == 0);
+
+        std::vector<std::unique_ptr<Expression>> assertionArgs;
+        assertionArgs.push_back(std::move(*get));
+        
+        return std::make_unique<Assertion>(type, std::move(assertionArgs));
+    }
+    
+    static std::unique_ptr<Expression> makeZoom() {
+        ParsingContext ctx;
+        ParseResult zoom = createCompoundExpression("zoom", std::vector<std::unique_ptr<Expression>>(), ctx);
+        assert(zoom);
+        assert(ctx.getErrors().size() == 0);
+        return std::move(*zoom);
+    }
+    
+    static std::unique_ptr<Expression> makeError(std::string message) {
+        return std::make_unique<detail::ErrorExpression>(message);
+    }
+    
+    template <typename OutputType>
+    static ParseResult makeInterpolate(type::Type type,
+                                 std::unique_ptr<Expression> input,
+                                 std::map<double, std::unique_ptr<Expression>> convertedStops,
+                                 typename Interpolate<OutputType>::Interpolator interpolator)
+    {
+        ParseResult curve = ParseResult(std::make_unique<Interpolate<OutputType>>(
+            std::move(type),
+            std::move(interpolator),
+            std::move(input),
+            std::move(convertedStops)
+        ));
+        assert(curve);
+        return std::move(*curve);
+    }
+    
+    template <typename Key>
+    static ParseResult makeMatch(type::Type type,
+                                 std::unique_ptr<Expression> input,
+                                 std::map<CategoricalValue, std::unique_ptr<Expression>> stops) {
+        // match expression
+        typename Match<Key>::Branches branches;
+        for(auto it = stops.begin(); it != stops.end(); it++) {
+            assert(it->first.template is<Key>());
+            Key key = it->first.template get<Key>();
+            branches.emplace(
+                std::move(key),
+                std::move(it->second)
+            );
+        }
+        
+        return ParseResult(std::make_unique<Match<Key>>(std::move(type),
+                                            std::move(input),
+                                            std::move(branches),
+                                            makeError("No matching label")));
+    }
+    
+    static ParseResult makeCase(type::Type type,
+                                std::unique_ptr<Expression> input,
+                                std::map<CategoricalValue, std::unique_ptr<Expression>> 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") :
+            std::move(it->second);
+
+        it = stops.find(false);
+        std::unique_ptr<Expression> false_case = it == stops.end() ?
+            makeError("No matching label") :
+            std::move(it->second);
+
+        branches.push_back(std::make_pair(std::move(input), std::move(true_case)));
+        return ParseResult(std::make_unique<Case>(std::move(type), std::move(branches), std::move(false_case)));
+    }
+    
+    template <typename T>
+    static ParseResult fromCategoricalStops(std::map<CategoricalValue, T> stops, const std::string& property) {
+        assert(stops.size() > 0);
+
+        std::map<CategoricalValue, std::unique_ptr<Expression>> convertedStops;
+        for(const std::pair<CategoricalValue, T>& stop : stops) {
+            convertedStops.emplace(
+                stop.first,
+                makeLiteral(stop.second)
+            );
+        }
+        
+        type::Type type = valueTypeToExpressionType<T>();
+
+        const CategoricalValue& firstKey = stops.begin()->first;
+        return firstKey.match(
+            [&](bool) {
+                return makeCase(type, makeGet(type::Boolean, property), std::move(convertedStops));
+            },
+            [&](const std::string&) {
+                return makeMatch<std::string>(type, makeGet(type::String, property), std::move(convertedStops));
+            },
+            [&](int64_t) {
+                return makeMatch<int64_t>(type, makeGet(type::Number, property), std::move(convertedStops));
+            }
+        );
+    }
+    
+    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 std::unique_ptr<Expression> toExpression(const ExponentialStops<T>& stops)
+    {
+        ParseResult e = makeInterpolate<typename ValueConverter<T>::ExpressionType>(
+                                         valueTypeToExpressionType<T>(),
+                                         makeZoom(),
+                                         convertStops(stops.stops),
+                                         ExponentialInterpolator(stops.base));
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const IntervalStops<T>& stops)
+    {
+        ParseResult e(std::make_unique<Step>(valueTypeToExpressionType<T>(),
+                                             makeZoom(),
+                                             convertStops(stops.stops)));
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const ExponentialStops<T>& stops)
+    {
+        ParseResult e = makeInterpolate<typename ValueConverter<T>::ExpressionType>(valueTypeToExpressionType<T>(),
+                                                                     makeGet(type::Number, property),
+                                                                     convertStops(stops.stops),
+                                                                     ExponentialInterpolator(stops.base));
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const IntervalStops<T>& stops)
+    {
+        std::unique_ptr<Expression> get = makeGet(type::Number, property);
+        ParseResult e(std::make_unique<Step>(valueTypeToExpressionType<T>(),
+                                             std::move(get),
+                                             convertStops(stops.stops)));
+        assert(e);
+        return std::move(*e);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const CategoricalStops<T>& stops)
+    {
+        ParseResult expr = fromCategoricalStops(stops.stops, property);
+        assert(expr);
+        return std::move(*expr);
+    }
+
+    // interpolatable zoom curve
+    template <typename T>
+    static typename std::enable_if_t<util::Interpolatable<T>::value,
+    ParseResult> makeZoomCurve(std::map<double, std::unique_ptr<Expression>> stops) {
+        return makeInterpolate<typename ValueConverter<T>::ExpressionType>(valueTypeToExpressionType<T>(),
+                                                                           makeZoom(),
+                                                                           std::move(stops),
+                                                                           ExponentialInterpolator(1.0));
+    }
+    
+    // non-interpolatable zoom curve
+    template <typename T>
+    static typename std::enable_if_t<!util::Interpolatable<T>::value,
+    ParseResult> makeZoomCurve(std::map<double, std::unique_ptr<Expression>> stops) {
+        return ParseResult(std::make_unique<Step>(valueTypeToExpressionType<T>(), makeZoom(), std::move(stops)));
+    }
+
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const CompositeExponentialStops<T>& stops)
+    {
+        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(type::Number, property);
+            ParseResult innerInterpolate = makeInterpolate<typename ValueConverter<T>::ExpressionType>(valueTypeToExpressionType<T>(),
+                                                                                  std::move(get),
+                                                                                  convertStops(stop.second),
+                                                                                  ExponentialInterpolator(stops.base));
+            assert(innerInterpolate);
+            outerStops.emplace(stop.first, std::move(*innerInterpolate));
+        }
+        
+        ParseResult zoomCurve = makeZoomCurve<T>(std::move(outerStops));
+        assert(zoomCurve);
+        return std::move(*zoomCurve);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const CompositeIntervalStops<T>& stops)
+    {
+        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(type::Number, property);
+            ParseResult innerInterpolate(std::make_unique<Step>(valueTypeToExpressionType<T>(),
+                                                                std::move(get),
+                                                                convertStops(stop.second)));
+            assert(innerInterpolate);
+            outerStops.emplace(stop.first, std::move(*innerInterpolate));
+        }
+
+        ParseResult zoomCurve = makeZoomCurve<T>(std::move(outerStops));
+        assert(zoomCurve);
+        return std::move(*zoomCurve);
+    }
+    
+    template <typename T>
+    static std::unique_ptr<Expression> toExpression(const std::string& property,
+                                                  const CompositeCategoricalStops<T>& stops)
+    {
+        std::map<double, std::unique_ptr<Expression>> outerStops;
+        for (const std::pair<float, std::map<CategoricalValue, T>>& stop : stops.stops) {
+            ParseResult innerInterpolate = fromCategoricalStops(stop.second, property);
+            assert(innerInterpolate);
+            outerStops.emplace(stop.first, std::move(*innerInterpolate));
+        }
+        
+        ParseResult zoomCurve = makeZoomCurve<T>(std::move(outerStops));
+        assert(zoomCurve);
+        return std::move(*zoomCurve);
+    }
+
+    
+    static std::unique_ptr<Expression> fromIdentityFunction(type::Type type, const std::string& property)
+    {
+        std::unique_ptr<Expression> input = type.match(
+            [&] (const type::StringType&) {
+                return makeGet(type::String, property);
+            },
+            [&] (const type::NumberType&) {
+                return makeGet(type::Number, property);
+            },
+            [&] (const type::BooleanType&) {
+                return makeGet(type::Boolean, property);
+            },
+            [&] (const type::ColorType&) {
+                std::vector<std::unique_ptr<Expression>> args;
+                args.push_back(makeGet(type::String, property));
+                return std::make_unique<Coercion>(type::Color, std::move(args));
+            },
+            [&] (const type::Array& arr) {
+                std::vector<std::unique_ptr<Expression>> getArgs;
+                getArgs.push_back(makeLiteral(property));
+                ParsingContext ctx;
+                ParseResult get = createCompoundExpression("get", std::move(getArgs), ctx);
+                assert(get);
+                assert(ctx.getErrors().size() == 0);
+                return std::make_unique<ArrayAssertion>(arr, std::move(*get));
+            },
+            [&] (const auto&) -> std::unique_ptr<Expression> {
+                return makeLiteral(Null);
+            }
+        );
+        
+        return input;
+    }
+};
+
+} // 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..02e4b604e2 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/expression/is_constant.hpp>
+#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,33 +29,48 @@ public:
             CategoricalStops<T>,
             IdentityStops<T>>>;
 
+    SourceFunction(std::unique_ptr<expression::Expression> expression_)
+        : expression(std::move(expression_))
+    {
+        assert(expression::isZoomConstant(*expression));
+        assert(!expression::isFeatureConstant(*expression));
+    }
+    
     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 IdentityStops<T>&) {
+              return expression::Convert::fromIdentityFunction(expression::valueTypeToExpressionType<T>(), property);
+          }, [&] (const auto& s) {
+              return expression::Convert::toExpression(property, s);
+          }))
+    {}
 
     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::EvaluationContext(&feature));
+        if (result) {
+            const optional<T> typed = expression::fromExpressionValue<T>(*result);
+            return typed ? *typed : defaultValue ? *defaultValue : finalDefaultValue;
         }
-        return stops.match([&] (const auto& s) -> T {
-            return s.evaluate(*v).value_or(defaultValue.value_or(finalDefaultValue));
-        });
+        return defaultValue ? *defaultValue : finalDefaultValue;
     }
 
     friend bool operator==(const SourceFunction& lhs,
                            const SourceFunction& rhs) {
-        return std::tie(lhs.property, lhs.stops, lhs.defaultValue)
-            == std::tie(rhs.property, rhs.stops, rhs.defaultValue);
+        return *lhs.expression == *rhs.expression;
     }
 
+    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/include/mbgl/util/string.hpp b/include/mbgl/util/string.hpp
index 82d317c620..13498ccb92 100644
--- a/include/mbgl/util/string.hpp
+++ b/include/mbgl/util/string.hpp
@@ -25,6 +25,10 @@ inline int stoi(const std::string &str)
     return atoi(str.c_str());
 }
 
+inline float stof(const std::string &str) {
+    return static_cast<float>(atof(str.c_str()));
+}
+
 } // namespace std
 
 #endif
@@ -65,5 +69,9 @@ inline std::string toString(std::exception_ptr error) {
     }
 }
 
+inline float stof(const std::string& str) {
+    return std::stof(str);
+}
+
 } // namespace util
 } // namespace mbgl
diff --git a/include/mbgl/util/unitbezier.hpp b/include/mbgl/util/unitbezier.hpp
index 6e644e2d1f..92f23d6718 100644
--- a/include/mbgl/util/unitbezier.hpp
+++ b/include/mbgl/util/unitbezier.hpp
@@ -26,6 +26,7 @@
 #pragma once
 
 #include <cmath>
+#include <tuple>
 
 namespace mbgl {
 namespace util {
@@ -102,6 +103,11 @@ struct UnitBezier {
     double solve(double x, double epsilon) const {
         return sampleCurveY(solveCurveX(x, epsilon));
     }
+    
+    bool operator==(const UnitBezier& rhs) const {
+        return std::tie(cx, bx, ax, cy, by, ay) ==
+            std::tie(rhs.cx, rhs.bx, rhs.ax, rhs.cy, rhs.by, rhs.ay);
+    }
 
 private:
     const double cx;
diff --git a/mapbox-gl-native.pro b/mapbox-gl-native.pro
index 38742c0499..bfbf0622d5 100644
--- a/mapbox-gl-native.pro
+++ b/mapbox-gl-native.pro
@@ -186,13 +186,36 @@ SOURCES += \
     src/mbgl/style/conversion/filter.cpp \
     src/mbgl/style/conversion/geojson.cpp \
     src/mbgl/style/conversion/geojson_options.cpp \
+    src/mbgl/style/conversion/get_json_type.cpp \
     src/mbgl/style/conversion/layer.cpp \
     src/mbgl/style/conversion/light.cpp \
     src/mbgl/style/conversion/position.cpp \
     src/mbgl/style/conversion/source.cpp \
     src/mbgl/style/conversion/tileset.cpp \
     src/mbgl/style/conversion/transition_options.cpp \
+    src/mbgl/style/expression/array_assertion.cpp \
+    src/mbgl/style/expression/assertion.cpp \
+    src/mbgl/style/expression/at.cpp \
+    src/mbgl/style/expression/boolean_operator.cpp \
+    src/mbgl/style/expression/case.cpp \
+    src/mbgl/style/expression/check_subtype.cpp \
+    src/mbgl/style/expression/coalesce.cpp \
+    src/mbgl/style/expression/coercion.cpp \
+    src/mbgl/style/expression/compound_expression.cpp \
+    src/mbgl/style/expression/find_zoom_curve.cpp \
+    src/mbgl/style/expression/get_covering_stops.cpp \
+    src/mbgl/style/expression/interpolate.cpp \
+    src/mbgl/style/expression/is_constant.cpp \
+    src/mbgl/style/expression/is_expression.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/step.cpp \
+    src/mbgl/style/expression/util.cpp \
+    src/mbgl/style/expression/value.cpp \
     src/mbgl/style/function/categorical_stops.cpp \
+    src/mbgl/style/function/expression.cpp \
     src/mbgl/style/function/identity_stops.cpp \
     src/mbgl/style/image.cpp \
     src/mbgl/style/image_impl.cpp \
diff --git a/platform/qt/src/http_file_source.cpp b/platform/qt/src/http_file_source.cpp
index 573b707c27..6e70693241 100644
--- a/platform/qt/src/http_file_source.cpp
+++ b/platform/qt/src/http_file_source.cpp
@@ -80,9 +80,10 @@ void HTTPFileSource::Impl::onReplyFinished()
         return;
     }
 
+    QByteArray data = reply->readAll();
     QVector<HTTPRequest*>& requestsVector = it.value().second;
     for (auto req : requestsVector) {
-        req->handleNetworkReply(reply);
+        req->handleNetworkReply(reply, data);
     }
 
     m_pending.erase(it);
diff --git a/platform/qt/src/http_request.cpp b/platform/qt/src/http_request.cpp
index 386a2d9ef4..ea3f388bd5 100644
--- a/platform/qt/src/http_request.cpp
+++ b/platform/qt/src/http_request.cpp
@@ -52,7 +52,7 @@ QNetworkRequest HTTPRequest::networkRequest() const
     return req;
 }
 
-void HTTPRequest::handleNetworkReply(QNetworkReply *reply)
+void HTTPRequest::handleNetworkReply(QNetworkReply *reply, const QByteArray& data)
 {
     m_handled = true;
 
@@ -98,11 +98,10 @@ void HTTPRequest::handleNetworkReply(QNetworkReply *reply)
 
     switch(responseCode) {
     case 200: {
-        QByteArray bytes = reply->readAll();
-        if (bytes.isEmpty()) {
+        if (data.isEmpty()) {
             response.data = std::make_shared<std::string>();
         } else {
-            response.data = std::make_shared<std::string>(bytes.constData(), bytes.size());
+            response.data = std::make_shared<std::string>(data.constData(), data.size());
         }
         break;
     }
diff --git a/platform/qt/src/http_request.hpp b/platform/qt/src/http_request.hpp
index 959f97759a..b4d476d586 100644
--- a/platform/qt/src/http_request.hpp
+++ b/platform/qt/src/http_request.hpp
@@ -20,7 +20,7 @@ public:
     QUrl requestUrl() const;
     QNetworkRequest networkRequest() const;
 
-    void handleNetworkReply(QNetworkReply *);
+    void handleNetworkReply(QNetworkReply *, const QByteArray& data);
 
 private:
     HTTPFileSource::Impl* m_context;
diff --git a/platform/qt/src/qmapboxgl.cpp b/platform/qt/src/qmapboxgl.cpp
index 740bb90202..fc281fdf1d 100644
--- a/platform/qt/src/qmapboxgl.cpp
+++ b/platform/qt/src/qmapboxgl.cpp
@@ -1578,7 +1578,9 @@ mbgl::Size QMapboxGLPrivate::getFramebufferSize() const {
 
 void QMapboxGLPrivate::updateAssumedState() {
     assumeFramebufferBinding(fbObject);
+#if QT_VERSION >= 0x050600
     assumeViewport(0, 0, getFramebufferSize());
+#endif
 }
 
 void QMapboxGLPrivate::bind() {
diff --git a/platform/qt/src/sqlite3.cpp b/platform/qt/src/sqlite3.cpp
index 7d47ae552b..2f3db12f33 100644
--- a/platform/qt/src/sqlite3.cpp
+++ b/platform/qt/src/sqlite3.cpp
@@ -6,6 +6,7 @@
 #include <QStringList>
 #include <QThread>
 #include <QVariant>
+#include <QAtomicInt>
 
 #include <cassert>
 #include <cstring>
@@ -60,20 +61,26 @@ void checkDatabaseOpenError(const QSqlDatabase &db) {
     }
 }
 
+namespace {
+    QString incrementCounter() {
+        static QAtomicInt count = 0;
+        return QString::number(count.fetchAndAddAcquire(1));
+    }
+}
+
 class DatabaseImpl {
 public:
-    DatabaseImpl(const char* filename, int flags) {
-        static uint64_t count = 0;
-        const QString connectionName = QString::number(uint64_t(QThread::currentThread())) + QString::number(count++);
-
+    DatabaseImpl(const char* filename, int flags)
+        : connectionName(QString::number(uint64_t(QThread::currentThread())) + incrementCounter())
+    {
         if (!QSqlDatabase::drivers().contains("QSQLITE")) {
             throw Exception { Exception::Code::CANTOPEN, "SQLite driver not found." };
         }
 
         assert(!QSqlDatabase::contains(connectionName));
-        db.reset(new QSqlDatabase(QSqlDatabase::addDatabase("QSQLITE", connectionName)));
+        auto db = QSqlDatabase::addDatabase("QSQLITE", connectionName);
 
-        QString connectOptions = db->connectOptions();
+        QString connectOptions = db.connectOptions();
         if (flags & OpenFlag::ReadOnly) {
             if (!connectOptions.isEmpty()) connectOptions.append(';');
             connectOptions.append("QSQLITE_OPEN_READONLY");
@@ -83,26 +90,26 @@ public:
             connectOptions.append("QSQLITE_ENABLE_SHARED_CACHE");
         }
 
-        db->setConnectOptions(connectOptions);
-        db->setDatabaseName(QString(filename));
+        db.setConnectOptions(connectOptions);
+        db.setDatabaseName(QString(filename));
 
-        if (!db->open()) {
-            checkDatabaseOpenError(*db);
+        if (!db.open()) {
+            checkDatabaseOpenError(db);
         }
     }
 
     ~DatabaseImpl() {
-        db->close();
-        checkDatabaseError(*db);
+        auto db = QSqlDatabase::database(connectionName);
+        db.close();
+        checkDatabaseError(db);
     }
 
-    QScopedPointer<QSqlDatabase> db;
+    QString connectionName;
 };
 
 class StatementImpl {
 public:
     StatementImpl(const QString& sql, const QSqlDatabase& db) : query(db) {
-        query.setForwardOnly(true);
         if (!query.prepare(sql)) {
             checkQueryError(query);
         }
@@ -147,17 +154,18 @@ void Database::setBusyTimeout(std::chrono::milliseconds timeout) {
     // internally to int, so we need to make sure the limits apply.
     std::string timeoutStr = mbgl::util::toString(timeout.count() & INT_MAX);
 
-    QString connectOptions = impl->db->connectOptions();
+    auto db = QSqlDatabase::database(impl->connectionName);
+    QString connectOptions = db.connectOptions();
     if (connectOptions.isEmpty()) {
         if (!connectOptions.isEmpty()) connectOptions.append(';');
         connectOptions.append("QSQLITE_BUSY_TIMEOUT=").append(QString::fromStdString(timeoutStr));
     }
-    if (impl->db->isOpen()) {
-        impl->db->close();
+    if (db.isOpen()) {
+        db.close();
     }
-    impl->db->setConnectOptions(connectOptions);
-    if (!impl->db->open()) {
-        checkDatabaseOpenError(*impl->db);
+    db.setConnectOptions(connectOptions);
+    if (!db.open()) {
+        checkDatabaseOpenError(db);
     }
 }
 
@@ -169,9 +177,9 @@ void Database::exec(const std::string &sql) {
         if (!statement.endsWith(';')) {
             statement.append(';');
         }
-        QSqlQuery query(*impl->db);
-        query.setForwardOnly(true);
+        QSqlQuery query(QSqlDatabase::database(impl->connectionName));
         query.prepare(statement);
+
         if (!query.exec()) {
             checkQueryError(query);
         }
@@ -183,7 +191,7 @@ Statement Database::prepare(const char *query) {
 }
 
 Statement::Statement(Database *db, const char *sql)
-        : impl(std::make_unique<StatementImpl>(QString(sql), *db->impl->db)) {
+        : impl(std::make_unique<StatementImpl>(QString(sql), QSqlDatabase::database(db->impl->connectionName))) {
     assert(impl);
 }
 
@@ -269,9 +277,13 @@ void Statement::bind(int offset, const char* value, std::size_t length, bool ret
         throw std::range_error("value too long");
     }
 
+    // Qt SQLite driver treats QByteArray as blob: we need to explicitly
+    // declare the variant type as string.
+    QVariant text(QVariant::Type::String);
+    text.setValue(retain ? QByteArray(value, length) : QByteArray::fromRawData(value, length));
+
     // Field numbering starts at 0.
-    impl->query.bindValue(offset - 1, retain ? QByteArray(value, length) :
-            QByteArray::fromRawData(value, length), QSql::In);
+    impl->query.bindValue(offset - 1, std::move(text), QSql::In);
 
     checkQueryError(impl->query);
 }
@@ -281,7 +293,12 @@ void Statement::bind(int offset, const std::string& value, bool retain) {
 }
 
 void Statement::bindBlob(int offset, const void* value_, std::size_t length, bool retain) {
+    assert(impl);
     const char* value = reinterpret_cast<const char*>(value_);
+    if (length > std::numeric_limits<int>::max()) {
+        // Kept for consistence with the default implementation.
+        throw std::range_error("value too long");
+    }
 
     // Field numbering starts at 0.
     impl->query.bindValue(offset - 1, retain ? QByteArray(value, length) :
@@ -296,20 +313,20 @@ void Statement::bindBlob(int offset, const std::vector<uint8_t>& value, bool ret
 
 bool Statement::run() {
     assert(impl);
-    if (impl->query.isValid()) {
-        return impl->query.next();
-    }
 
-    assert(!impl->query.isActive());
-    impl->query.setForwardOnly(true);
-    if (!impl->query.exec()) {
-        checkQueryError(impl->query);
+    if (!impl->query.isValid()) {
+       if (impl->query.exec()) {
+           impl->lastInsertRowId = impl->query.lastInsertId().value<int64_t>();
+           impl->changes = impl->query.numRowsAffected();
+       } else {
+           checkQueryError(impl->query);
+       }
     }
 
-    impl->lastInsertRowId = impl->query.lastInsertId().value<int64_t>();
-    impl->changes = impl->query.numRowsAffected();
+    const bool hasNext = impl->query.next();
+    if (!hasNext) impl->query.finish();
 
-    return impl->query.next();
+    return hasNext;
 }
 
 template bool Statement::get(int);
diff --git a/src/mbgl/annotation/annotation_manager.cpp b/src/mbgl/annotation/annotation_manager.cpp
index 1f2d01e9eb..a4d53bbd3f 100644
--- a/src/mbgl/annotation/annotation_manager.cpp
+++ b/src/mbgl/annotation/annotation_manager.cpp
@@ -18,6 +18,7 @@ using namespace style;
 
 const std::string AnnotationManager::SourceID = "com.mapbox.annotations";
 const std::string AnnotationManager::PointLayerID = "com.mapbox.annotations.points";
+const std::string AnnotationManager::ShapeLayerID = "com.mapbox.annotations.shape.";
 
 AnnotationManager::AnnotationManager(Style& style_)
         : style(style_) {
diff --git a/src/mbgl/annotation/annotation_manager.hpp b/src/mbgl/annotation/annotation_manager.hpp
index a028a8f1ba..22b25cd2ac 100644
--- a/src/mbgl/annotation/annotation_manager.hpp
+++ b/src/mbgl/annotation/annotation_manager.hpp
@@ -46,6 +46,7 @@ public:
 
     static const std::string SourceID;
     static const std::string PointLayerID;
+    static const std::string ShapeLayerID;
 
 private:
     void add(const AnnotationID&, const SymbolAnnotation&, const uint8_t);
diff --git a/src/mbgl/annotation/shape_annotation_impl.cpp b/src/mbgl/annotation/shape_annotation_impl.cpp
index 0c1a631ad8..9288159b6a 100644
--- a/src/mbgl/annotation/shape_annotation_impl.cpp
+++ b/src/mbgl/annotation/shape_annotation_impl.cpp
@@ -1,5 +1,6 @@
 #include <mbgl/annotation/shape_annotation_impl.hpp>
 #include <mbgl/annotation/annotation_tile.hpp>
+#include <mbgl/annotation/annotation_manager.hpp>
 #include <mbgl/tile/tile_id.hpp>
 #include <mbgl/math/wrap.hpp>
 #include <mbgl/math/clamp.hpp>
@@ -15,7 +16,7 @@ namespace geojsonvt = mapbox::geojsonvt;
 ShapeAnnotationImpl::ShapeAnnotationImpl(const AnnotationID id_, const uint8_t maxZoom_)
     : id(id_),
       maxZoom(maxZoom_),
-      layerID("com.mapbox.annotations.shape." + util::toString(id)) {
+      layerID(AnnotationManager::ShapeLayerID + util::toString(id)) {
 }
 
 void ShapeAnnotationImpl::updateTileData(const CanonicalTileID& tileID, AnnotationTileData& data) {
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/renderer/renderer.cpp b/src/mbgl/renderer/renderer.cpp
index e915f5e146..8953b419f7 100644
--- a/src/mbgl/renderer/renderer.cpp
+++ b/src/mbgl/renderer/renderer.cpp
@@ -57,6 +57,21 @@ AnnotationIDs Renderer::queryPointAnnotations(const ScreenBox& box) const {
     RenderedQueryOptions options;
     options.layerIDs = {{ AnnotationManager::PointLayerID }};
     auto features = queryRenderedFeatures(box, options);
+    return getAnnotationIDs(features);
+}
+
+AnnotationIDs Renderer::queryShapeAnnotations(const ScreenBox& box) const {
+    auto features = impl->queryShapeAnnotations({
+        box.min,
+        {box.max.x, box.min.y},
+        box.max,
+        {box.min.x, box.max.y},
+        box.min
+    });
+    return getAnnotationIDs(features);
+}
+    
+AnnotationIDs Renderer::getAnnotationIDs(const std::vector<Feature>& features) const {
     std::set<AnnotationID> set;
     for (auto &feature : features) {
         assert(feature.id);
diff --git a/src/mbgl/renderer/renderer_impl.cpp b/src/mbgl/renderer/renderer_impl.cpp
index 9ff5a3b6dd..5987e69374 100644
--- a/src/mbgl/renderer/renderer_impl.cpp
+++ b/src/mbgl/renderer/renderer_impl.cpp
@@ -635,6 +635,10 @@ std::vector<Feature> Renderer::Impl::queryRenderedFeatures(const ScreenLineStrin
         }
     }
 
+    return queryRenderedFeatures(geometry, options, layers);
+}
+
+std::vector<Feature> Renderer::Impl::queryRenderedFeatures(const ScreenLineString& geometry, const RenderedQueryOptions& options, const std::vector<const RenderLayer*>& layers) const {
     std::unordered_set<std::string> sourceIDs;
     for (const RenderLayer* layer : layers) {
         sourceIDs.emplace(layer->baseImpl->source);
@@ -669,6 +673,21 @@ std::vector<Feature> Renderer::Impl::queryRenderedFeatures(const ScreenLineStrin
     return result;
 }
 
+std::vector<Feature> Renderer::Impl::queryShapeAnnotations(const ScreenLineString& geometry) const {
+    std::vector<const RenderLayer*> shapeAnnotationLayers;
+    RenderedQueryOptions options;
+    for (const auto& layerImpl : *layerImpls) {
+        if (std::mismatch(layerImpl->id.begin(), layerImpl->id.end(),
+                          AnnotationManager::ShapeLayerID.begin(), AnnotationManager::ShapeLayerID.end()).second == AnnotationManager::ShapeLayerID.end()) {
+            if (const RenderLayer* layer = getRenderLayer(layerImpl->id)) {
+                shapeAnnotationLayers.emplace_back(layer);
+            }
+        }
+    }
+
+    return queryRenderedFeatures(geometry, options, shapeAnnotationLayers);
+}
+
 std::vector<Feature> Renderer::Impl::querySourceFeatures(const std::string& sourceID, const SourceQueryOptions& options) const {
     const RenderSource* source = getRenderSource(sourceID);
     if (!source) return {};
diff --git a/src/mbgl/renderer/renderer_impl.hpp b/src/mbgl/renderer/renderer_impl.hpp
index 043253a834..720e01ed53 100644
--- a/src/mbgl/renderer/renderer_impl.hpp
+++ b/src/mbgl/renderer/renderer_impl.hpp
@@ -49,6 +49,7 @@ public:
 
     std::vector<Feature> queryRenderedFeatures(const ScreenLineString&, const RenderedQueryOptions&) const;
     std::vector<Feature> querySourceFeatures(const std::string& sourceID, const SourceQueryOptions&) const;
+    std::vector<Feature> queryShapeAnnotations(const ScreenLineString&) const;
 
     void onLowMemory();
     void dumDebugLogs();
@@ -61,6 +62,8 @@ private:
 
           RenderLayer* getRenderLayer(const std::string& id);
     const RenderLayer* getRenderLayer(const std::string& id) const;
+                           
+    std::vector<Feature> queryRenderedFeatures(const ScreenLineString&, const RenderedQueryOptions&, const std::vector<const RenderLayer*>&) const;
 
     // GlyphManagerObserver implementation.
     void onGlyphsError(const FontStack&, const GlyphRange&, std::exception_ptr) override;
diff --git a/src/mbgl/style/conversion/get_json_type.cpp b/src/mbgl/style/conversion/get_json_type.cpp
new file mode 100644
index 0000000000..cd3b4608b1
--- /dev/null
+++ b/src/mbgl/style/conversion/get_json_type.cpp
@@ -0,0 +1,34 @@
+#include <mbgl/style/conversion/get_json_type.hpp>
+#include <mbgl/util/feature.hpp>
+
+namespace mbgl {
+namespace style {
+namespace conversion {
+
+std::string getJSONType(const Convertible& value) {
+    if (isUndefined(value)) {
+        return "null";
+    }
+    if (isArray(value)) {
+        return "array";
+    }
+    if (isObject(value)) {
+        return "object";
+    }
+    optional<mbgl::Value> v = toValue(value);
+
+    // Since we've already checked the non-atomic types above, value must then
+    // be a string, number, or boolean -- thus, assume that the toValue()
+    // conversion succeeds.
+    assert(v);
+
+    return v->match(
+        [&] (const std::string&) { return "string"; },
+        [&] (bool) { return "boolean"; },
+        [&] (auto) { return "number"; }
+    );
+}
+
+} // namespace conversion
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/array_assertion.cpp b/src/mbgl/style/expression/array_assertion.cpp
new file mode 100644
index 0000000000..29f6a47b10
--- /dev/null
+++ b/src/mbgl/style/expression/array_assertion.cpp
@@ -0,0 +1,86 @@
+#include <mbgl/style/expression/array_assertion.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult ArrayAssertion::evaluate(const EvaluationContext& params) const {
+    auto result = input->evaluate(params);
+    if (!result) {
+        return result.error();
+    }
+    type::Type expected = getType();
+    type::Type actual = typeOf(*result);
+    if (checkSubtype(expected, actual)) {
+        return EvaluationError {
+            "Expected value to be of type " + toString(expected) +
+            ", but found " + toString(actual) + " instead."
+        };
+    }
+    return *result;
+}
+
+void ArrayAssertion::eachChild(const std::function<void(const Expression&)>& visit) const {
+    visit(*input);
+}
+
+using namespace mbgl::style::conversion;
+ParseResult ArrayAssertion::parse(const Convertible& value, ParsingContext& ctx) {
+
+    static std::unordered_map<std::string, type::Type> itemTypes {
+        {"string", type::String},
+        {"number", type::Number},
+        {"boolean", type::Boolean}
+    };
+
+    auto length = arrayLength(value);
+    if (length < 2 || length > 4) {
+        ctx.error("Expected 1, 2, or 3 arguments, but found " + util::toString(length - 1) + " instead.");
+        return ParseResult();
+    }
+
+    optional<type::Type> itemType;
+    optional<std::size_t> N;
+    if (length > 2) {
+        optional<std::string> itemTypeName = toString(arrayMember(value, 1));
+        auto it = itemTypeName ? itemTypes.find(*itemTypeName) : itemTypes.end();
+        if (it == itemTypes.end()) {
+            ctx.error(
+                R"(The item type argument of "array" must be one of string, number, boolean)",
+                1
+            );
+            return ParseResult();
+        }
+        itemType = it->second;
+    } else {
+        itemType = {type::Value};
+    }
+
+    if (length > 3) {
+        auto n = toNumber(arrayMember(value, 2));
+        if (!n || *n != std::floor(*n)) {
+            ctx.error(
+                R"(The length argument to "array" must be a positive integer literal.)",
+                2
+            );
+            return ParseResult();
+        }
+        N = optional<std::size_t>(*n);
+    }
+
+    auto input = ctx.parse(arrayMember(value, length - 1), length - 1, {type::Value});
+    if (!input) {
+        return input;
+    }
+
+    return ParseResult(std::make_unique<ArrayAssertion>(
+        type::Array(*itemType, N),
+        std::move(*input)
+    ));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/assertion.cpp b/src/mbgl/style/expression/assertion.cpp
new file mode 100644
index 0000000000..a17c53cf54
--- /dev/null
+++ b/src/mbgl/style/expression/assertion.cpp
@@ -0,0 +1,73 @@
+#include <mbgl/style/expression/assertion.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+using namespace mbgl::style::conversion;
+ParseResult Assertion::parse(const Convertible& value, ParsingContext& ctx) {
+    static std::unordered_map<std::string, type::Type> types {
+        {"string", type::String},
+        {"number", type::Number},
+        {"boolean", type::Boolean},
+        {"object", type::Object}
+    };
+
+    std::size_t length = arrayLength(value);
+
+    if (length < 2) {
+        ctx.error("Expected at least one argument.");
+        return ParseResult();
+    }
+
+    auto it = types.find(*toString(arrayMember(value, 0)));
+    assert(it != types.end());
+    
+    std::vector<std::unique_ptr<Expression>> parsed;
+    parsed.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        ParseResult input = ctx.parse(arrayMember(value, i), i, {type::Value});
+        if (!input) return ParseResult();
+        parsed.push_back(std::move(*input));
+    }
+
+    return ParseResult(std::make_unique<Assertion>(it->second, std::move(parsed)));
+}
+
+EvaluationResult Assertion::evaluate(const EvaluationContext& params) const {
+    for (std::size_t i = 0; i < inputs.size(); i++) {
+        EvaluationResult value = inputs[i]->evaluate(params);
+        if (!value) return value;
+        if (!type::checkSubtype(getType(), typeOf(*value))) {
+            return value;
+        } else if (i == inputs.size() - 1) {
+            return EvaluationError {
+                "Expected value to be of type " + toString(getType()) +
+                ", but found " + toString(typeOf(*value)) + " instead."
+            };
+        }
+    }
+
+    assert(false);
+    return EvaluationError { "Unreachable" };
+};
+
+void Assertion::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for(const std::unique_ptr<Expression>& input : inputs) {
+        visit(*input);
+    }
+};
+
+bool Assertion::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Assertion*>(&e)) {
+        return getType() == rhs->getType() && Expression::childrenEqual(inputs, rhs->inputs);
+    }
+    return false;
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
+
diff --git a/src/mbgl/style/expression/at.cpp b/src/mbgl/style/expression/at.cpp
new file mode 100644
index 0000000000..e447d33bc7
--- /dev/null
+++ b/src/mbgl/style/expression/at.cpp
@@ -0,0 +1,64 @@
+#include <mbgl/style/expression/at.hpp>
+#include <mbgl/util/string.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult At::evaluate(const EvaluationContext& params) const {
+    const EvaluationResult evaluatedIndex = index->evaluate(params);
+    const EvaluationResult evaluatedInput = input->evaluate(params);
+    if (!evaluatedIndex) {
+        return evaluatedIndex.error();
+    }
+    if (!evaluatedInput) {
+        return evaluatedInput.error();
+    }
+    
+    const auto i = evaluatedIndex->get<double>();
+    const auto inputArray = evaluatedInput->get<std::vector<Value>>();
+    
+    if (i < 0 || i >= inputArray.size()) {
+        return EvaluationError {
+            "Array index out of bounds: " + stringify(i) +
+            " > " + util::toString(inputArray.size()) + "."
+        };
+    }
+    if (i != std::floor(i)) {
+        return EvaluationError {
+            "Array index must be an integer, but found " + stringify(i) + " instead."
+        };
+    }
+    return inputArray[static_cast<std::size_t>(i)];
+}
+
+void At::eachChild(const std::function<void(const Expression&)>& visit) const {
+    visit(*index);
+    visit(*input);
+}
+
+using namespace mbgl::style::conversion;
+ParseResult At::parse(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+
+    std::size_t length = arrayLength(value);
+    if (length != 3) {
+        ctx.error("Expected 2 arguments, but found " + util::toString(length - 1) + " instead.");
+        return ParseResult();
+    }
+
+    ParseResult index = ctx.parse(arrayMember(value, 1), 1, {type::Number});
+    
+    type::Type inputType = type::Array(ctx.getExpected() ? *ctx.getExpected() : type::Value);
+    ParseResult input = ctx.parse(arrayMember(value, 2), 2, {inputType});
+
+    if (!index || !input) return ParseResult();
+
+    return ParseResult(std::make_unique<At>(std::move(*index), std::move(*input)));
+
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/boolean_operator.cpp b/src/mbgl/style/expression/boolean_operator.cpp
new file mode 100644
index 0000000000..88797f965a
--- /dev/null
+++ b/src/mbgl/style/expression/boolean_operator.cpp
@@ -0,0 +1,87 @@
+#include <mbgl/style/expression/boolean_operator.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Any::evaluate(const EvaluationContext& params) const {
+    for (auto it = inputs.begin(); it != inputs.end(); it++) {
+        const EvaluationResult result = (*it)->evaluate(params);
+        if (!result) return result;
+        if (result->get<bool>()) return EvaluationResult(true);
+    }
+    return EvaluationResult(false);
+}
+
+void Any::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (const std::unique_ptr<Expression>& input : inputs) {
+        visit(*input);
+    }
+}
+
+bool Any::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Any*>(&e)) {
+        return Expression::childrenEqual(inputs, rhs->inputs);
+    }
+    return false;
+}
+
+
+EvaluationResult All::evaluate(const EvaluationContext& params) const {
+    for (auto it = inputs.begin(); it != inputs.end(); it++) {
+        const EvaluationResult result = (*it)->evaluate(params);
+        if (!result) return result;
+        if (!result->get<bool>()) return EvaluationResult(false);
+    }
+    return EvaluationResult(true);
+}
+
+void All::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (const std::unique_ptr<Expression>& input : inputs) {
+        visit(*input);
+    }
+}
+
+bool All::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const All*>(&e)) {
+        return Expression::childrenEqual(inputs, rhs->inputs);
+    }
+    return false;
+}
+
+using namespace mbgl::style::conversion;
+
+template <class T>
+ParseResult parseBooleanOp(const Convertible& value, ParsingContext& ctx) {
+    
+    assert(isArray(value));
+    auto length = arrayLength(value);
+ 
+    std::vector<std::unique_ptr<Expression>> parsedInputs;
+    
+    parsedInputs.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        auto parsed = ctx.parse(arrayMember(value, i), i, {type::Boolean});
+        if (!parsed) {
+            return parsed;
+        }
+        
+        parsedInputs.push_back(std::move(*parsed));
+    }
+ 
+    return ParseResult(std::make_unique<T>(std::move(parsedInputs)));
+}
+
+ParseResult Any::parse(const Convertible& value, ParsingContext& ctx) {
+    return parseBooleanOp<Any>(value, ctx);
+}
+
+ParseResult All::parse(const Convertible& value, ParsingContext& ctx) {
+    return parseBooleanOp<All>(value, ctx);
+}
+
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
diff --git a/src/mbgl/style/expression/case.cpp b/src/mbgl/style/expression/case.cpp
new file mode 100644
index 0000000000..049f258606
--- /dev/null
+++ b/src/mbgl/style/expression/case.cpp
@@ -0,0 +1,91 @@
+#include <mbgl/style/expression/case.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Case::evaluate(const EvaluationContext& params) const {
+    for (const auto& branch : branches) {
+        const EvaluationResult evaluatedTest = branch.first->evaluate(params);
+        if (!evaluatedTest) {
+            return evaluatedTest.error();
+        }
+        if (evaluatedTest->get<bool>()) {
+            return branch.second->evaluate(params);
+        }
+    }
+    
+    return otherwise->evaluate(params);
+}
+
+void Case::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (const Branch& branch : branches) {
+        visit(*branch.first);
+        visit(*branch.second);
+    }
+    visit(*otherwise);
+}
+
+bool Case::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Case*>(&e)) {
+        return *otherwise == *(rhs->otherwise) && Expression::childrenEqual(branches, rhs->branches);
+    }
+    return false;
+}
+
+using namespace mbgl::style::conversion;
+ParseResult Case::parse(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+    auto length = arrayLength(value);
+    if (length < 4) {
+        ctx.error("Expected at least 3 arguments, but found only " + util::toString(length - 1) + ".");
+        return ParseResult();
+    }
+
+    // Expect even-length array: ["case", 2 * (n pairs)..., otherwise]
+    if (length % 2 != 0) {
+        ctx.error("Expected an odd number of arguments");
+        return ParseResult();
+    }
+
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+
+    std::vector<Case::Branch> branches;
+    branches.reserve((length - 2) / 2);
+    for (size_t i = 1; i + 1 < length; i += 2) {
+        auto test = ctx.parse(arrayMember(value, i), i, {type::Boolean});
+        if (!test) {
+            return test;
+        }
+
+        auto output = ctx.parse(arrayMember(value, i + 1), i + 1, outputType);
+        if (!output) {
+            return output;
+        }
+        
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+
+        branches.push_back(std::make_pair(std::move(*test), std::move(*output)));
+    }
+
+    assert(outputType);
+
+    auto otherwise = ctx.parse(arrayMember(value, length - 1), length - 1, outputType);
+    if (!otherwise) {
+        return otherwise;
+    }
+
+    return ParseResult(std::make_unique<Case>(*outputType,
+                                  std::move(branches),
+                                  std::move(*otherwise)));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/check_subtype.cpp b/src/mbgl/style/expression/check_subtype.cpp
new file mode 100644
index 0000000000..04a1643f0c
--- /dev/null
+++ b/src/mbgl/style/expression/check_subtype.cpp
@@ -0,0 +1,60 @@
+#include <string>
+#include <mbgl/style/expression/check_subtype.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+namespace type {
+
+std::string errorMessage(const Type& expected, const Type& t) {
+    return {"Expected " + toString(expected) + " but found " + toString(t) + " instead."};
+}
+
+optional<std::string> checkSubtype(const Type& expected, const Type& t) {
+    if (t.is<ErrorType>()) return {};
+    
+    optional<std::string> result = expected.match(
+        [&] (const Array& expectedArray) -> optional<std::string> {
+            if (!t.is<Array>()) { return {errorMessage(expected, t)}; }
+            const auto& actualArray = t.get<Array>();
+            const auto err = checkSubtype(expectedArray.itemType, actualArray.itemType);
+            if (err) return { errorMessage(expected, t) };
+            if (expectedArray.N && expectedArray.N != actualArray.N) return { errorMessage(expected, t) };
+            return {};
+        },
+        [&] (const ValueType&) -> optional<std::string> {
+            if (t.is<ValueType>()) return {};
+            
+            const Type members[] = {
+                Null,
+                Boolean,
+                Number,
+                String,
+                Object,
+                Color,
+                Array(Value)
+            };
+            
+            for (const auto& member : members) {
+                const auto err = checkSubtype(member, t);
+                if (!err) {
+                    return {};
+                }
+            }
+            return { errorMessage(expected, t) };
+        },
+        [&] (const auto&) -> optional<std::string> {
+            if (expected != t) {
+                return { errorMessage(expected, t) };
+            }
+            return {};
+        }
+    );
+    
+    return result;
+}
+
+} // namespace type
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/coalesce.cpp b/src/mbgl/style/expression/coalesce.cpp
new file mode 100644
index 0000000000..bfde3c7581
--- /dev/null
+++ b/src/mbgl/style/expression/coalesce.cpp
@@ -0,0 +1,62 @@
+#include <mbgl/style/expression/coalesce.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Coalesce::evaluate(const EvaluationContext& params) const {
+    EvaluationResult result = Null;
+    for (const auto& arg : args) {
+        result = arg->evaluate(params);
+        if (!result || *result != Null) break;
+    }
+    return result;
+}
+
+void Coalesce::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (const std::unique_ptr<Expression>& arg : args) {
+        visit(*arg);
+    }
+}
+
+bool Coalesce::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Coalesce*>(&e)) {
+        return Expression::childrenEqual(args, rhs->args);
+    }
+    return false;
+}
+
+using namespace mbgl::style::conversion;
+ParseResult Coalesce::parse(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+    auto length = arrayLength(value);
+    if (length < 2) {
+        ctx.error("Expected at least one argument.");
+        return ParseResult();
+    }
+ 
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+
+    Coalesce::Args args;
+    args.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        auto parsed = ctx.parse(arrayMember(value, i), i, outputType);
+        if (!parsed) {
+            return parsed;
+        }
+        if (!outputType) {
+            outputType = (*parsed)->getType();
+        }
+        args.push_back(std::move(*parsed));
+    }
+ 
+    assert(outputType);
+    return ParseResult(std::make_unique<Coalesce>(*outputType, std::move(args)));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/coercion.cpp b/src/mbgl/style/expression/coercion.cpp
new file mode 100644
index 0000000000..8ed8e160dd
--- /dev/null
+++ b/src/mbgl/style/expression/coercion.cpp
@@ -0,0 +1,144 @@
+#include <mbgl/style/expression/coercion.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/util.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult toNumber(const Value& v) {
+    optional<double> result = v.match(
+        [](const double f) -> optional<double> { return f; },
+        [](const std::string& s) -> optional<double> {
+            try {
+                return util::stof(s);
+            } catch(std::exception) {
+                return optional<double>();
+            }
+        },
+        [](const auto&) { return optional<double>(); }
+    );
+    if (!result) {
+        return EvaluationError {
+            "Could not convert " + stringify(v) + " to number."
+        };
+    }
+    return *result;
+}
+
+EvaluationResult toColor(const Value& colorValue) {
+    return colorValue.match(
+        [&](const std::string& colorString) -> EvaluationResult {
+            const optional<Color> result = Color::parse(colorString);
+            if (result) {
+                return *result;
+            } else {
+                return EvaluationError{
+                    "Could not parse color from value '" + colorString + "'"
+                };
+            }
+        },
+        [&](const std::vector<Value>& components) -> EvaluationResult {
+            std::size_t len = components.size();
+            bool isNumeric = std::all_of(components.begin(), components.end(), [](const Value& item) {
+                return item.template is<double>();
+            });
+            if ((len == 3 || len == 4) && isNumeric) {
+                Result<Color> c = {rgba(
+                    components[0].template get<double>(),
+                    components[1].template get<double>(),
+                    components[2].template get<double>(),
+                    len == 4 ? components[3].template get<double>() : 1.0
+                )};
+                if (!c) return c.error();
+                return *c;
+            } else {
+                return EvaluationError{
+                    "Invalid rbga value " + stringify(colorValue) + ": expected an array containing either three or four numeric values."
+                };
+            }
+        },
+        [&](const auto&) -> EvaluationResult {
+            return EvaluationError{
+                "Could not parse color from value '" + stringify(colorValue) + "'"
+            };
+        }
+    );
+}
+
+Coercion::Coercion(type::Type type_, std::vector<std::unique_ptr<Expression>> inputs_) :
+    Expression(std::move(type_)),
+    inputs(std::move(inputs_))
+{
+    type::Type t = getType();
+    if (t.is<type::NumberType>()) {
+        coerceSingleValue = toNumber;
+    } else if (t.is<type::ColorType>()) {
+        coerceSingleValue = toColor;
+    } else {
+        assert(false);
+    }
+}
+
+using namespace mbgl::style::conversion;
+ParseResult Coercion::parse(const Convertible& value, ParsingContext& ctx) {
+    static std::unordered_map<std::string, type::Type> types {
+        {"to-number", type::Number},
+        {"to-color", type::Color}
+    };
+
+    std::size_t length = arrayLength(value);
+
+    if (length < 2) {
+        ctx.error("Expected at least one argument.");
+        return ParseResult();
+    }
+
+    auto it = types.find(*toString(arrayMember(value, 0)));
+    assert(it != types.end());
+    
+    std::vector<std::unique_ptr<Expression>> parsed;
+    parsed.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        ParseResult input = ctx.parse(arrayMember(value, i), i, {type::Value});
+        if (!input) return ParseResult();
+        parsed.push_back(std::move(*input));
+    }
+
+    return ParseResult(std::make_unique<Coercion>(it->second, std::move(parsed)));
+}
+
+EvaluationResult Coercion::evaluate(const EvaluationContext& params) const {
+    for (std::size_t i = 0; i < inputs.size(); i++) {
+        EvaluationResult value = inputs[i]->evaluate(params);
+        if (!value) return value;
+        EvaluationResult coerced = coerceSingleValue(*value);
+        if (coerced || i == inputs.size() - 1) {
+            return coerced;
+        }
+    }
+
+    assert(false);
+    return EvaluationError { "Unreachable" };
+};
+
+void Coercion::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for(const std::unique_ptr<Expression>& input : inputs) {
+        visit(*input);
+    }
+};
+
+bool Coercion::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Coercion*>(&e)) {
+        return getType() == rhs->getType() && Expression::childrenEqual(inputs, rhs->inputs);
+    }
+    return false;
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
+
+
diff --git a/src/mbgl/style/expression/compound_expression.cpp b/src/mbgl/style/expression/compound_expression.cpp
new file mode 100644
index 0000000000..fa79357560
--- /dev/null
+++ b/src/mbgl/style/expression/compound_expression.cpp
@@ -0,0 +1,573 @@
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/util.hpp>
+#include <mbgl/tile/geometry_tile_data.hpp>
+#include <mbgl/math/log2.hpp>
+#include <mbgl/util/ignore.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+namespace detail {
+
+/*
+    The Signature<Fn> structs are wrappers around an "evaluate()" function whose
+    purpose is to extract the necessary Type data from the evaluate function's
+    type.  There are three key (partial) specializations:
+    
+    Signature<R (Params...)>:
+    Wraps a simple evaluate function (const T0&, const T1&, ...) -> Result<U>
+ 
+    Signature<R (const Varargs<T>&)>:
+    Wraps an evaluate function that takes an arbitrary number of arguments (via
+    a Varargs<T>, which is just an alias for std::vector).
+ 
+    Signature<R (const EvaluationContext&, Params...)>:
+    Wraps an evaluate function that needs to access the expression evaluation
+    parameters in addition to its subexpressions, i.e.,
+    (const EvaluationParams& const T0&, const T1&, ...) -> Result<U>.  Needed
+    for expressions like ["zoom"], ["get", key], etc.
+    
+    In each of the above evaluate signatures, T0, T1, etc. are the types of
+    the successfully evaluated subexpressions.
+*/
+template <class, class Enable = void>
+struct Signature;
+
+// Simple evaluate function (const T0&, const T1&, ...) -> Result<U>
+template <class R, class... Params>
+struct Signature<R (Params...)> : SignatureBase {
+    using Args = std::array<std::unique_ptr<Expression>, sizeof...(Params)>;
+    
+    Signature(R (*evaluate_)(Params...)) :
+        SignatureBase(
+            valueTypeToExpressionType<std::decay_t<typename R::Value>>(),
+            std::vector<type::Type> {valueTypeToExpressionType<std::decay_t<Params>>()...}
+        ),
+        evaluate(evaluate_)
+    {}
+    
+    EvaluationResult apply(const EvaluationContext& evaluationParameters, const Args& args) const {
+        return applyImpl(evaluationParameters, args, std::index_sequence_for<Params...>{});
+    }
+    
+    std::unique_ptr<Expression> makeExpression(const std::string& name,
+                                               std::vector<std::unique_ptr<Expression>> args) const override {
+        typename Signature::Args argsArray;
+        std::copy_n(std::make_move_iterator(args.begin()), sizeof...(Params), argsArray.begin());
+        return std::make_unique<CompoundExpression<Signature>>(name, *this, std::move(argsArray));
+    }
+
+    R (*evaluate)(Params...);
+private:
+    template <std::size_t ...I>
+    EvaluationResult applyImpl(const EvaluationContext& evaluationParameters, const Args& args, std::index_sequence<I...>) const {
+        const std::array<EvaluationResult, sizeof...(I)> evaluated = {{std::get<I>(args)->evaluate(evaluationParameters)...}};
+        for (const auto& arg : evaluated) {
+            if(!arg) return arg.error();
+        }
+        const R value = evaluate(*fromExpressionValue<std::decay_t<Params>>(*(evaluated[I]))...);
+        if (!value) return value.error();
+        return *value;
+    }
+};
+
+// Varargs evaluate function (const Varargs<T>&) -> Result<U>
+template <class R, typename T>
+struct Signature<R (const Varargs<T>&)> : SignatureBase {
+    using Args = std::vector<std::unique_ptr<Expression>>;
+    
+    Signature(R (*evaluate_)(const Varargs<T>&)) :
+        SignatureBase(
+            valueTypeToExpressionType<std::decay_t<typename R::Value>>(),
+            VarargsType { valueTypeToExpressionType<T>() }
+        ),
+        evaluate(evaluate_)
+    {}
+    
+    std::unique_ptr<Expression> makeExpression(const std::string& name,
+                                               std::vector<std::unique_ptr<Expression>> args) const override  {
+        return std::make_unique<CompoundExpression<Signature>>(name, *this, std::move(args));
+    };
+    
+    EvaluationResult apply(const EvaluationContext& evaluationParameters, const Args& args) const {
+        Varargs<T> evaluated;
+        evaluated.reserve(args.size());
+        for (const auto& arg : args) {
+            const EvaluationResult evaluatedArg = arg->evaluate(evaluationParameters);
+            if(!evaluatedArg) return evaluatedArg.error();
+            evaluated.push_back(*fromExpressionValue<std::decay_t<T>>(*evaluatedArg));
+        }
+        const R value = evaluate(evaluated);
+        if (!value) return value.error();
+        return *value;
+    }
+    
+    R (*evaluate)(const Varargs<T>&);
+};
+
+// Evaluate function needing parameter access,
+// (const EvaluationParams&, const T0&, const T1&, ...) -> Result<U>
+template <class R, class... Params>
+struct Signature<R (const EvaluationContext&, Params...)> : SignatureBase {
+    using Args = std::array<std::unique_ptr<Expression>, sizeof...(Params)>;
+    
+    Signature(R (*evaluate_)(const EvaluationContext&, Params...)) :
+        SignatureBase(
+            valueTypeToExpressionType<std::decay_t<typename R::Value>>(),
+            std::vector<type::Type> {valueTypeToExpressionType<std::decay_t<Params>>()...}
+        ),
+        evaluate(evaluate_)
+    {}
+    
+    std::unique_ptr<Expression> makeExpression(const std::string& name,
+                                               std::vector<std::unique_ptr<Expression>> args) const override {
+        typename Signature::Args argsArray;
+        std::copy_n(std::make_move_iterator(args.begin()), sizeof...(Params), argsArray.begin());
+        return std::make_unique<CompoundExpression<Signature>>(name, *this, std::move(argsArray));
+    }
+    
+    EvaluationResult apply(const EvaluationContext& evaluationParameters, const Args& args) const {
+        return applyImpl(evaluationParameters, args, std::index_sequence_for<Params...>{});
+    }
+    
+private:
+    template <std::size_t ...I>
+    EvaluationResult applyImpl(const EvaluationContext& evaluationParameters, const Args& args, std::index_sequence<I...>) const {
+        const std::array<EvaluationResult, sizeof...(I)> evaluated = {{std::get<I>(args)->evaluate(evaluationParameters)...}};
+        for (const auto& arg : evaluated) {
+            if(!arg) return arg.error();
+        }
+        // TODO: assert correct runtime type of each arg value
+        const R value = evaluate(evaluationParameters, *fromExpressionValue<std::decay_t<Params>>(*(evaluated[I]))...);
+        if (!value) return value.error();
+        return *value;
+    }
+    
+    R (*evaluate)(const EvaluationContext&, Params...);
+};
+
+// Machinery to pull out function types from class methods, lambdas, etc.
+template <class R, class... Params>
+struct Signature<R (*)(Params...)>
+    : Signature<R (Params...)>
+{ using Signature<R (Params...)>::Signature; };
+
+template <class T, class R, class... Params>
+struct Signature<R (T::*)(Params...) const>
+    : Signature<R (Params...)>
+{ using Signature<R (Params...)>::Signature;  };
+
+template <class T, class R, class... Params>
+struct Signature<R (T::*)(Params...)>
+    : Signature<R (Params...)>
+{ using Signature<R (Params...)>::Signature; };
+
+template <class Lambda>
+struct Signature<Lambda, std::enable_if_t<std::is_class<Lambda>::value>>
+    : Signature<decltype(&Lambda::operator())>
+{ using Signature<decltype(&Lambda::operator())>::Signature; };
+
+} // namespace detail
+
+using Definition = CompoundExpressionRegistry::Definition;
+
+template <typename T>
+Result<bool> equal(const T& lhs, const T& rhs) { return lhs == rhs; }
+
+template <typename T>
+Result<bool> notEqual(const T& lhs, const T& rhs) { return lhs != rhs; }
+
+template <typename Fn>
+static std::unique_ptr<detail::SignatureBase> makeSignature(Fn evaluateFunction) {
+    return std::make_unique<detail::Signature<Fn>>(evaluateFunction);
+}
+
+std::unordered_map<std::string, CompoundExpressionRegistry::Definition> initializeDefinitions() {
+    std::unordered_map<std::string, CompoundExpressionRegistry::Definition> definitions;
+    auto define = [&](std::string name, auto fn) {
+        definitions[name].push_back(makeSignature(fn));
+    };
+    
+    define("e", []() -> Result<double> { return 2.718281828459045; });
+    define("pi", []() -> Result<double> { return 3.141592653589793; });
+    define("ln2", []() -> Result<double> { return 0.6931471805599453; });
+
+    define("typeof", [](const Value& v) -> Result<std::string> { return toString(typeOf(v)); });
+    
+    define("to-string", [](const Value& value) -> Result<std::string> {
+        return value.match(
+            [](const Color& c) -> Result<std::string> { return c.stringify(); }, // avoid quoting
+            [](const std::string& s) -> Result<std::string> { return s; }, // avoid quoting
+            [](const auto& v) -> Result<std::string> { return stringify(v); }
+        );
+    });
+    
+    define("to-boolean", [](const Value& v) -> Result<bool> {
+        return v.match(
+            [&] (double f) { return (bool)f; },
+            [&] (const std::string& s) { return s.length() > 0; },
+            [&] (bool b) { return b; },
+            [&] (const NullValue&) { return false; },
+            [&] (const auto&) { return true; }
+        );
+    });
+    define("to-rgba", [](const Color& color) -> Result<std::array<double, 4>> {
+        return std::array<double, 4> {{ color.r, color.g, color.b, color.a }};
+    });
+    
+    define("rgba", rgba);
+    define("rgb", [](double r, double g, double b) { return rgba(r, g, b, 1.0f); });
+    
+    define("zoom", [](const EvaluationContext& params) -> Result<double> {
+        if (!params.zoom) {
+            return EvaluationError {
+                "The 'zoom' expression is unavailable in the current evaluation context."
+            };
+        }
+        return *(params.zoom);
+    });
+    
+    define("heatmap-density", [](const EvaluationContext& params) -> Result<double> {
+        if (!params.heatmapDensity) {
+            return EvaluationError {
+                "The 'heatmap-density' expression is unavailable in the current evaluation context."
+            };
+        }
+        return *(params.heatmapDensity);
+    });
+    
+    define("has", [](const EvaluationContext& params, const std::string& key) -> Result<bool> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+        
+        return params.feature->getValue(key) ? true : false;
+    });
+    define("has", [](const std::string& key, const std::unordered_map<std::string, Value>& object) -> Result<bool> {
+        return object.find(key) != object.end();
+    });
+    
+    define("get", [](const EvaluationContext& params, const std::string& key) -> Result<Value> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+
+        auto propertyValue = params.feature->getValue(key);
+        if (!propertyValue) {
+            return Null;
+        }
+        return Value(toExpressionValue(*propertyValue));
+    });
+    define("get", [](const std::string& key, const std::unordered_map<std::string, Value>& object) -> Result<Value> {
+        if (object.find(key) == object.end()) {
+            return Null;
+        }
+        return object.at(key);
+    });
+    
+    define("length", [](const std::vector<Value>& arr) -> Result<double> {
+        return arr.size();
+    });
+    define("length", [] (const std::string s) -> Result<double> {
+        return s.size();
+    });
+    
+    define("properties", [](const EvaluationContext& params) -> Result<std::unordered_map<std::string, Value>> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+        std::unordered_map<std::string, Value> result;
+        const PropertyMap properties = params.feature->getProperties();
+        for (const auto& entry : properties) {
+            result[entry.first] = toExpressionValue(entry.second);
+        }
+        return result;
+    });
+    
+    define("geometry-type", [](const EvaluationContext& params) -> Result<std::string> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+    
+        auto type = params.feature->getType();
+        if (type == FeatureType::Point) {
+            return "Point";
+        } else if (type == FeatureType::LineString) {
+            return "LineString";
+        } else if (type == FeatureType::Polygon) {
+            return "Polygon";
+        } else {
+            return "Unknown";
+        }
+    });
+    
+    define("id", [](const EvaluationContext& params) -> Result<Value> {
+        if (!params.feature) {
+            return EvaluationError {
+                "Feature data is unavailable in the current evaluation context."
+            };
+        }
+    
+        auto id = params.feature->getID();
+        if (!id) {
+            return Null;
+        }
+        return id->match(
+            [](const auto& idValue) {
+                return toExpressionValue(mbgl::Value(idValue));
+            }
+        );
+    });
+    
+    define("+", [](const Varargs<double>& args) -> Result<double> {
+        double sum = 0.0f;
+        for (auto arg : args) {
+            sum += arg;
+        }
+        return sum;
+    });
+    define("-", [](double a, double b) -> Result<double> { return a - b; });
+    define("-", [](double a) -> Result<double> { return -a; });
+    define("*", [](const Varargs<double>& args) -> Result<double> {
+        double prod = 1.0f;
+        for (auto arg : args) {
+            prod *= arg;
+        }
+        return prod;
+    });
+    define("/", [](double a, double b) -> Result<double> { return a / b; });
+    define("%", [](double a, double b) -> Result<double> { return fmod(a, b); });
+    define("^", [](double a, double b) -> Result<double> { return pow(a, b); });
+    define("sqrt", [](double x) -> Result<double> { return sqrt(x); });
+    define("log10", [](double x) -> Result<double> { return log10(x); });
+    define("ln", [](double x) -> Result<double> { return log(x); });
+    define("log2", [](double x) -> Result<double> { return util::log2(x); });
+    define("sin", [](double x) -> Result<double> { return sin(x); });
+    define("cos", [](double x) -> Result<double> { return cos(x); });
+    define("tan", [](double x) -> Result<double> { return tan(x); });
+    define("asin", [](double x) -> Result<double> { return asin(x); });
+    define("acos", [](double x) -> Result<double> { return acos(x); });
+    define("atan", [](double x) -> Result<double> { return atan(x); });
+    
+    define("min", [](const Varargs<double>& args) -> Result<double> {
+        double result = std::numeric_limits<double>::infinity();
+        for (double arg : args) {
+            result = fmin(arg, result);
+        }
+        return result;
+    });
+    define("max", [](const Varargs<double>& args) -> Result<double> {
+        double result = -std::numeric_limits<double>::infinity();
+        for (double arg : args) {
+            result = fmax(arg, result);
+        }
+        return result;
+    });
+    
+    define("==", equal<double>);
+    define("==", equal<const std::string&>);
+    define("==", equal<bool>);
+    define("==", equal<NullValue>);
+
+    define("!=", notEqual<double>);
+    define("!=", notEqual<const std::string&>);
+    define("!=", notEqual<bool>);
+    define("!=", notEqual<NullValue>);
+
+    define(">", [](double lhs, double rhs) -> Result<bool> { return lhs > rhs; });
+    define(">", [](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs > rhs; });
+    define(">=", [](double lhs, double rhs) -> Result<bool> { return lhs >= rhs; });
+    define(">=",[](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs >= rhs; });
+    define("<", [](double lhs, double rhs) -> Result<bool> { return lhs < rhs; });
+    define("<", [](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs < rhs; });
+    define("<=", [](double lhs, double rhs) -> Result<bool> { return lhs <= rhs; });
+    define("<=", [](const std::string& lhs, const std::string& rhs) -> Result<bool> { return lhs <= rhs; });
+    
+    define("!", [](bool e) -> Result<bool> { return !e; });
+    
+    define("upcase", [](const std::string& input) -> Result<std::string> {
+        std::string s = input;
+        std::transform(s.begin(), s.end(), s.begin(),
+                       [](unsigned char c){ return std::toupper(c); });
+        return s;
+    });
+    define("downcase", [](const std::string& input) -> Result<std::string> {
+        std::string s = input;
+        std::transform(s.begin(), s.end(), s.begin(),
+                       [](unsigned char c){ return std::tolower(c); });
+        return s;
+    });
+    define("concat", [](const Varargs<std::string>& args) -> Result<std::string> {
+        std::string s;
+        for (const std::string& arg : args) {
+            s += arg;
+        }
+        return s;
+    });
+    define("error", [](const std::string& input) -> Result<type::ErrorType> {
+        return EvaluationError { input };
+    });
+    
+    return definitions;
+}
+
+std::unordered_map<std::string, Definition> CompoundExpressionRegistry::definitions = initializeDefinitions();
+
+using namespace mbgl::style::conversion;
+ParseResult parseCompoundExpression(const std::string name, const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value) && arrayLength(value) > 0);
+
+    auto it = CompoundExpressionRegistry::definitions.find(name);
+    if (it == CompoundExpressionRegistry::definitions.end()) {
+        ctx.error(
+             R"(Unknown expression ")" + name + R"(". If you wanted a literal array, use ["literal", [...]].)",
+            0
+        );
+        return ParseResult();
+    }
+    const CompoundExpressionRegistry::Definition& definition = it->second;
+    
+    auto length = arrayLength(value);
+
+    // Check if we have a single signature with the correct number of
+    // parameters. If so, then use that signature's parameter types for parsing
+    // (and inferring the types of) the arguments.
+    optional<std::size_t> singleMatchingSignature;
+    for (std::size_t j = 0; j < definition.size(); j++) {
+        const std::unique_ptr<detail::SignatureBase>& signature = definition[j];
+        if (
+            signature->params.is<VarargsType>() ||
+            signature->params.get<std::vector<type::Type>>().size() == length - 1
+        ) {
+            if (singleMatchingSignature) {
+                singleMatchingSignature = {};
+            } else {
+                singleMatchingSignature = j;
+            }
+        }
+    }
+
+    // parse subexpressions first
+    std::vector<std::unique_ptr<Expression>> args;
+    args.reserve(length - 1);
+    for (std::size_t i = 1; i < length; i++) {
+        optional<type::Type> expected;
+        
+        if (singleMatchingSignature) {
+            expected = definition[*singleMatchingSignature]->params.match(
+                [](const VarargsType& varargs) { return varargs.type; },
+                [&](const std::vector<type::Type>& params_) { return params_[i - 1]; }
+            );
+        }
+    
+        auto parsed = ctx.parse(arrayMember(value, i), i, expected);
+        if (!parsed) {
+            return parsed;
+        }
+        args.push_back(std::move(*parsed));
+    }
+    return createCompoundExpression(name, definition, std::move(args), ctx);
+}
+
+
+ParseResult createCompoundExpression(const std::string& name,
+                                     std::vector<std::unique_ptr<Expression>> args,
+                                     ParsingContext& ctx)
+{
+    return createCompoundExpression(name, CompoundExpressionRegistry::definitions.at(name), std::move(args), ctx);
+}
+
+
+ParseResult createCompoundExpression(const std::string& name,
+                                     const Definition& definition,
+                                     std::vector<std::unique_ptr<Expression>> args,
+                                     ParsingContext& ctx)
+{
+    ParsingContext signatureContext(ctx.getKey());
+    
+    for (const std::unique_ptr<detail::SignatureBase>& signature : definition) {
+        signatureContext.clearErrors();
+        
+        if (signature->params.is<std::vector<type::Type>>()) {
+            const std::vector<type::Type>& params = signature->params.get<std::vector<type::Type>>();
+            if (params.size() != args.size()) {
+                signatureContext.error(
+                    "Expected " + util::toString(params.size()) +
+                    " arguments, but found " + util::toString(args.size()) + " instead."
+                );
+                continue;
+            }
+
+            for (std::size_t i = 0; i < args.size(); i++) {
+                const std::unique_ptr<Expression>& arg = args[i];
+                optional<std::string> err = type::checkSubtype(params.at(i), arg->getType());
+                if (err) {
+                    signatureContext.error(*err, i + 1);
+                }
+            }
+        } else if (signature->params.is<VarargsType>()) {
+            const type::Type& paramType = signature->params.get<VarargsType>().type;
+            for (std::size_t i = 0; i < args.size(); i++) {
+                const std::unique_ptr<Expression>& arg = args[i];
+                optional<std::string> err = type::checkSubtype(paramType, arg->getType());
+                if (err) {
+                    signatureContext.error(*err, i + 1);
+                }
+            }
+        }
+        
+        if (signatureContext.getErrors().size() == 0) {
+            return ParseResult(signature->makeExpression(name, std::move(args)));
+        }
+    }
+    
+    if (definition.size() == 1) {
+        ctx.appendErrors(std::move(signatureContext));
+    } else {
+        std::string signatures;
+        for (const auto& signature : definition) {
+            signatures += (signatures.size() > 0 ? " | " : "");
+            signature->params.match(
+                [&](const VarargsType& varargs) {
+                    signatures += "(" + toString(varargs.type) + ")";
+                },
+                [&](const std::vector<type::Type>& params) {
+                    signatures += "(";
+                    bool first = true;
+                    for (const type::Type& param : params) {
+                        if (!first) signatures += ", ";
+                        signatures += toString(param);
+                        first = false;
+                    }
+                    signatures += ")";
+                }
+            );
+            
+        }
+        std::string actualTypes;
+        for (const auto& arg : args) {
+            if (actualTypes.size() > 0) {
+                actualTypes += ", ";
+            }
+            actualTypes += toString(arg->getType());
+        }
+        ctx.error("Expected arguments of type " + signatures + ", but found (" + actualTypes + ") instead.");
+    }
+    
+    return ParseResult();
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/find_zoom_curve.cpp b/src/mbgl/style/expression/find_zoom_curve.cpp
new file mode 100644
index 0000000000..5d39e0791e
--- /dev/null
+++ b/src/mbgl/style/expression/find_zoom_curve.cpp
@@ -0,0 +1,76 @@
+#include <mbgl/style/expression/find_zoom_curve.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/let.hpp>
+#include <mbgl/style/expression/coalesce.hpp>
+
+#include <mbgl/util/variant.hpp>
+#include <mbgl/util/optional.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+optional<variant<const InterpolateBase*, const Step*, ParsingError>> findZoomCurve(const expression::Expression* e) {
+    optional<variant<const InterpolateBase*, const Step*, ParsingError>> result;
+    
+    if (auto let = dynamic_cast<const Let*>(e)) {
+        result = findZoomCurve(let->getResult());
+    } else if (auto coalesce = dynamic_cast<const Coalesce*>(e)) {
+        std::size_t length = coalesce->getLength();
+        for (std::size_t i = 0; i < length; i++) {
+            result = findZoomCurve(coalesce->getChild(i));
+            if (result) {
+                break;
+            }
+        }
+    } else if (auto curve = dynamic_cast<const InterpolateBase*>(e)) {
+        auto z = dynamic_cast<CompoundExpressionBase*>(curve->getInput().get());
+        if (z && z->getName() == "zoom") {
+            result = {curve};
+        }
+    } else if (auto step = dynamic_cast<const Step*>(e)) {
+        auto z = dynamic_cast<CompoundExpressionBase*>(step->getInput().get());
+        if (z && z->getName() == "zoom") {
+            result = {step};
+        }
+    }
+    
+    if (result && result->is<ParsingError>()) {
+        return result;
+    }
+    
+    e->eachChild([&](const Expression& child) {
+        optional<variant<const InterpolateBase*, const Step*, ParsingError>> childResult(findZoomCurve(&child));
+        if (childResult) {
+            if (childResult->is<ParsingError>()) {
+                result = childResult;
+            } else if (!result && childResult) {
+                result = {ParsingError {
+                    R"("zoom" expression may only be used as input to a top-level "step" or "interpolate" expression.)", ""
+                }};
+            } else if (result && childResult && result != childResult) {
+                result = {ParsingError {
+                    R"(Only one zoom-based "step" or "interpolate" subexpression may be used in an expression.)", ""
+                }};
+            }
+        }
+    });
+
+    return result;
+}
+
+variant<const InterpolateBase*, const Step*> findZoomCurveChecked(const expression::Expression* e) {
+    return findZoomCurve(e)->match(
+        [](const ParsingError&) -> variant<const InterpolateBase*, const Step*> {
+            assert(false);
+            return {};
+        },
+        [](auto zoomCurve) -> variant<const InterpolateBase*, const Step*> {
+            return {std::move(zoomCurve)};
+        }
+    );
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/get_covering_stops.cpp b/src/mbgl/style/expression/get_covering_stops.cpp
new file mode 100644
index 0000000000..c9f87d93ac
--- /dev/null
+++ b/src/mbgl/style/expression/get_covering_stops.cpp
@@ -0,0 +1,26 @@
+#include <mbgl/style/expression/get_covering_stops.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+Range<float> getCoveringStops(const std::map<double, std::unique_ptr<Expression>>& stops,
+                              const double lower, const double upper) {
+    assert(!stops.empty());
+    auto minIt = stops.lower_bound(lower);
+    auto maxIt = stops.lower_bound(upper);
+
+    // lower_bound yields first element >= lowerZoom, but we want the *last*
+    // element <= lowerZoom, so if we found a stop > lowerZoom, back up by one.
+    if (minIt != stops.begin() && minIt != stops.end() && minIt->first > lower) {
+        minIt--;
+    }
+    return Range<float> {
+        static_cast<float>(minIt == stops.end() ? stops.rbegin()->first : minIt->first),
+        static_cast<float>(maxIt == stops.end() ? stops.rbegin()->first : maxIt->first)
+    };
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/interpolate.cpp b/src/mbgl/style/expression/interpolate.cpp
new file mode 100644
index 0000000000..5ddfca8e9f
--- /dev/null
+++ b/src/mbgl/style/expression/interpolate.cpp
@@ -0,0 +1,211 @@
+#include <mbgl/style/expression/interpolate.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+using Interpolator = variant<ExponentialInterpolator,
+                             CubicBezierInterpolator>;
+
+using namespace mbgl::style::conversion;
+
+ParseResult parseInterpolate(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+
+    auto length = arrayLength(value);
+
+    if (length < 2) {
+        ctx.error("Expected an interpolation type expression.");
+        return ParseResult();
+    }
+
+    const Convertible& interp = arrayMember(value, 1);
+    if (!isArray(interp) || arrayLength(interp) == 0) {
+        ctx.error("Expected an interpolation type expression.");
+        return ParseResult();
+    }
+
+    optional<Interpolator> interpolator;
+    
+    const optional<std::string> interpName = toString(arrayMember(interp, 0));
+    if (interpName && *interpName == "linear") {
+        interpolator = {ExponentialInterpolator(1.0)};
+    } else if (interpName && *interpName == "exponential") {
+        optional<double> base;
+        if (arrayLength(interp) == 2) {
+            base = toDouble(arrayMember(interp, 1));
+        }
+        if (!base) {
+            ctx.error("Exponential interpolation requires a numeric base.", 1, 1);
+            return ParseResult();
+        }
+        interpolator = {ExponentialInterpolator(*base)};
+    } else if (interpName && *interpName == "cubic-bezier") {
+        optional<double> x1;
+        optional<double> y1;
+        optional<double> x2;
+        optional<double> y2;
+        if (arrayLength(interp) == 5) {
+            x1 = toDouble(arrayMember(interp, 1));
+            y1 = toDouble(arrayMember(interp, 2));
+            x2 = toDouble(arrayMember(interp, 3));
+            y2 = toDouble(arrayMember(interp, 4));
+        }
+        if (
+            !x1 || !y1 || !x2 || !y2 ||
+            *x1 < 0 || *x1 > 1 ||
+            *y1 < 0 || *y1 > 1 ||
+            *x2 < 0 || *x2 > 1 ||
+            *y2 < 0 || *y2 > 1
+        ) {
+            ctx.error("Cubic bezier interpolation requires four numeric arguments with values between 0 and 1.", 1);
+            return ParseResult();
+            
+        }
+        interpolator = {CubicBezierInterpolator(*x1, *y1, *x2, *y2)};
+    }
+    
+    if (!interpolator) {
+        ctx.error("Unknown interpolation type " + (interpName ? *interpName : ""), 1, 0);
+        return ParseResult();
+    }
+    
+    std::size_t minArgs = 4;
+    if (length - 1 < minArgs) {
+        ctx.error("Expected at least 4 arguments, but found only " + util::toString(length - 1) + ".");
+        return ParseResult();
+    }
+    
+    // [interpolation, interp_type, input, 2 * (n pairs)...]
+    if ((length - 1) % 2 != 0) {
+        ctx.error("Expected an even number of arguments.");
+        return ParseResult();
+    }
+    
+    ParseResult input = ctx.parse(arrayMember(value, 2), 2, {type::Number});
+    if (!input) {
+        return input;
+    }
+
+    std::map<double, std::unique_ptr<Expression>> stops;
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+    
+    double previous = - std::numeric_limits<double>::infinity();
+    
+    for (std::size_t i = 3; i + 1 < length; i += 2) {
+        const optional<mbgl::Value> labelValue = toValue(arrayMember(value, i));
+        optional<double> label;
+        optional<std::string> labelError;
+        if (labelValue) {
+            labelValue->match(
+                [&](uint64_t n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](int64_t n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](double n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](const auto&) {}
+            );
+        }
+        if (!label) {
+            ctx.error(labelError ? *labelError :
+                R"(Input/output pairs for "interpolate" expressions must be defined using literal numeric values (not computed expressions) for the input values.)",
+                i);
+            return ParseResult();
+        }
+        
+        if (*label <= previous) {
+            ctx.error(
+                R"(Input/output pairs for "interpolate" expressions must be arranged with input values in strictly ascending order.)",
+                i
+            );
+            return ParseResult();
+        }
+        previous = *label;
+        
+        auto output = ctx.parse(arrayMember(value, i + 1), i + 1, outputType);
+        if (!output) {
+            return ParseResult();
+        }
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+
+        stops.emplace(*label, std::move(*output));
+    }
+    
+    assert(outputType);
+    
+    if (
+        *outputType != type::Number &&
+        *outputType != type::Color &&
+        !(
+            outputType->is<type::Array>() &&
+            outputType->get<type::Array>().itemType == type::Number &&
+            outputType->get<type::Array>().N
+        )
+    )
+    {
+        ctx.error("Type " + toString(*outputType) + " is not interpolatable.");
+        return ParseResult();
+    }
+    
+    return outputType->match(
+        [&](const type::NumberType&) -> ParseResult {
+            return interpolator->match([&](const auto& interpolator_) {
+                return ParseResult(std::make_unique<Interpolate<double>>(
+                    *outputType, interpolator_, std::move(*input), std::move(stops)
+                ));
+            });
+        },
+        [&](const type::ColorType&) -> ParseResult {
+            return interpolator->match([&](const auto& interpolator_) {
+                return ParseResult(std::make_unique<Interpolate<Color>>(
+                    *outputType, interpolator_, std::move(*input), std::move(stops)
+                ));
+            });
+        },
+        [&](const type::Array& arrayType) -> ParseResult {
+            return interpolator->match(
+                [&](const auto& continuousInterpolator) {
+                    if (arrayType.itemType != type::Number || !arrayType.N) {
+                        assert(false); // interpolability already checked above.
+                        return ParseResult();
+                    }
+                    return ParseResult(std::make_unique<Interpolate<std::vector<Value>>>(
+                        *outputType, continuousInterpolator, std::move(*input), std::move(stops)
+                    ));
+                }
+            );
+        },
+        [&](const auto&) {
+            // unreachable: Null, Boolean, String, Object, Value output types
+            // are not interpolatable, and interpolability was already checked above
+            assert(false);
+            return ParseResult();
+        }
+    );
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/is_constant.cpp b/src/mbgl/style/expression/is_constant.cpp
new file mode 100644
index 0000000000..0ebb37faa9
--- /dev/null
+++ b/src/mbgl/style/expression/is_constant.cpp
@@ -0,0 +1,40 @@
+#include <mbgl/style/expression/is_constant.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+bool isFeatureConstant(const Expression& expression) {
+    if (auto e = dynamic_cast<const CompoundExpressionBase*>(&expression)) {
+        const std::string name = e->getName();
+        optional<std::size_t> parameterCount = e->getParameterCount();
+        if (name == "get" && parameterCount && *parameterCount == 1) {
+            return false;
+        } else if (name == "has" && parameterCount && *parameterCount == 1) {
+            return false;
+        } else if (
+            name == "properties" ||
+            name == "geometry-type" ||
+            name == "id"
+        ) {
+            return false;
+        }
+    }
+
+    bool featureConstant = true;
+    expression.eachChild([&](const Expression& e) {
+        if (featureConstant && !isFeatureConstant(e)) {
+            featureConstant = false;
+        }
+    });
+    return featureConstant;
+}
+
+bool isZoomConstant(const Expression& e) {
+    return isGlobalPropertyConstant(e, std::array<std::string, 1>{{"zoom"}});
+}
+
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/is_expression.cpp b/src/mbgl/style/expression/is_expression.cpp
new file mode 100644
index 0000000000..77212f6a1e
--- /dev/null
+++ b/src/mbgl/style/expression/is_expression.cpp
@@ -0,0 +1,29 @@
+#include <mbgl/style/expression/is_expression.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+
+#include <mbgl/style/conversion.hpp>
+
+#include <unordered_set>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+using namespace mbgl::style::conversion;
+
+bool isExpression(const Convertible& value) {
+    const ExpressionRegistry& registry = getExpressionRegistry();
+
+    if (!isArray(value) || arrayLength(value) == 0) return false;
+    optional<std::string> name = toString(arrayMember(value, 0));
+    if (!name) return false;
+    
+    return (registry.find(*name) != registry.end()) ||
+        (CompoundExpressionRegistry::definitions.find(*name) != CompoundExpressionRegistry::definitions.end());
+}
+
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/let.cpp b/src/mbgl/style/expression/let.cpp
new file mode 100644
index 0000000000..561e8515d4
--- /dev/null
+++ b/src/mbgl/style/expression/let.cpp
@@ -0,0 +1,92 @@
+#include <mbgl/style/expression/let.hpp>
+#include <mbgl/style/conversion/get_json_type.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Let::evaluate(const EvaluationContext& params) const {
+    return result->evaluate(params);
+}
+
+void Let::eachChild(const std::function<void(const Expression&)>& visit) const {
+    for (auto it = bindings.begin(); it != bindings.end(); it++) {
+        visit(*it->second);
+    }
+    visit(*result);
+}
+
+using namespace mbgl::style::conversion;
+
+ParseResult Let::parse(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+
+    std::size_t length = arrayLength(value);
+
+    if (length < 4) {
+        ctx.error("Expected at least 3 arguments, but found " + util::toString(length - 1) + " instead.");
+        return ParseResult();
+    }
+
+    std::map<std::string, std::shared_ptr<Expression>> bindings_;
+    for(std::size_t i = 1; i < length - 1; i += 2) {
+        optional<std::string> name = toString(arrayMember(value, i));
+        if (!name) {
+            ctx.error("Expected string, but found " + getJSONType(arrayMember(value, i)) + " instead.", i);
+            return ParseResult();
+        }
+        
+        bool isValidName = std::all_of(name->begin(), name->end(), [](unsigned char c) {
+            return std::isalnum(c) || c == '_';
+        });
+        if (!isValidName) {
+            ctx.error("Variable names must contain only alphanumeric characters or '_'.", 1);
+            return ParseResult();
+        }
+        
+        ParseResult bindingValue = ctx.parse(arrayMember(value, i + 1), i + 1);
+        if (!bindingValue) {
+            return ParseResult();
+        }
+        
+        bindings_.emplace(*name, std::move(*bindingValue));
+    }
+
+    ParseResult result_ = ctx.parse(arrayMember(value, length - 1), length - 1, ctx.getExpected(), bindings_);
+    if (!result_) {
+        return ParseResult();
+    }
+
+    return ParseResult(std::make_unique<Let>(std::move(bindings_), std::move(*result_)));
+}
+
+EvaluationResult Var::evaluate(const EvaluationContext& params) const {
+    return value->evaluate(params);
+}
+
+void Var::eachChild(const std::function<void(const Expression&)>&) const {}
+
+ParseResult Var::parse(const Convertible& value_, ParsingContext& ctx) {
+    assert(isArray(value_));
+
+    if (arrayLength(value_) != 2 || !toString(arrayMember(value_, 1))) {
+        ctx.error("'var' expression requires exactly one string literal argument.");
+        return ParseResult();
+    }
+
+    std::string name_ = *toString(arrayMember(value_, 1));
+
+    optional<std::shared_ptr<Expression>> bindingValue = ctx.getBinding(name_);
+    if (!bindingValue) {
+        ctx.error(R"(Unknown variable ")" + name_ +  R"(". Make sure ")" +
+            name_ + R"(" has been bound in an enclosing "let" expression before using it.)", 1);
+        return ParseResult();
+    }
+
+    return ParseResult(std::make_unique<Var>(name_, std::move(*bindingValue)));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/literal.cpp b/src/mbgl/style/expression/literal.cpp
new file mode 100644
index 0000000000..7e79fcbfe6
--- /dev/null
+++ b/src/mbgl/style/expression/literal.cpp
@@ -0,0 +1,108 @@
+#include <mbgl/style/expression/literal.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+template <typename T>
+optional<Value> checkNumber(T n) {
+    if (n > std::numeric_limits<double>::max()) {
+        return {std::numeric_limits<double>::infinity()};
+    } else {
+        return {static_cast<double>(n)};
+    }
+}
+
+using namespace mbgl::style::conversion;
+optional<Value> parseValue(const Convertible& value, ParsingContext& ctx) {
+    if (isUndefined(value)) return {Null};
+    if (isObject(value)) {
+        std::unordered_map<std::string, Value> result;
+        bool error = false;
+        eachMember(value, [&] (const std::string& k, const mbgl::style::conversion::Convertible& v) -> optional<conversion::Error> {
+            if (!error) {
+                optional<Value> memberValue = parseValue(v, ctx);
+                if (memberValue) {
+                    result.emplace(k, *memberValue);
+                } else {
+                    error = true;
+                }
+            }
+            return {};
+        });
+        return error ? optional<Value>() : optional<Value>(result);
+    }
+    
+    if (isArray(value)) {
+        std::vector<Value> result;
+        const auto length = arrayLength(value);
+        for(std::size_t i = 0; i < length; i++) {
+            optional<Value> item = parseValue(arrayMember(value, i), ctx);
+            if (item) {
+                result.emplace_back(*item);
+            } else {
+                return optional<Value>();
+            }
+        }
+        return optional<Value>(result);
+    }
+    
+    optional<mbgl::Value> v = toValue(value);
+    // since value represents a JSON value, if it's not undefined, object, or
+    // array, it must be convertible to mbgl::Value
+    assert(v);
+    
+    return v->match(
+        [&](uint64_t n) { return checkNumber(n); },
+        [&](int64_t n) { return checkNumber(n); },
+        [&](double n) { return checkNumber(n); },
+        [&](const auto&) {
+            return optional<Value>(toExpressionValue(*v));
+        }
+    );
+}
+
+ParseResult Literal::parse(const Convertible& value, ParsingContext& ctx) {
+    if (isObject(value)) {
+        ctx.error(R"(Bare objects invalid. Use ["literal", {...}] instead.)");
+        return ParseResult();
+    } else if (isArray(value)) {
+        // object or array value, quoted with ["literal", value]
+        if (arrayLength(value) != 2) {
+            ctx.error("'literal' expression requires exactly one argument, but found " + util::toString(arrayLength(value) - 1) + " instead.");
+            return ParseResult();
+        }
+        const optional<Value> parsedValue = parseValue(arrayMember(value, 1), ctx);
+        if (!parsedValue) {
+            return ParseResult();
+        }
+        
+        // special case: infer the item type if possible for zero-length arrays
+        if (
+            ctx.getExpected() &&
+            ctx.getExpected()->template is<type::Array>() &&
+            parsedValue->template is<std::vector<Value>>()
+        ) {
+            auto type = typeOf(*parsedValue).template get<type::Array>();
+            auto expected = ctx.getExpected()->template get<type::Array>();
+            if (
+                type.N && (*type.N == 0) &&
+                (!expected.N || (*expected.N == 0))
+            ) {
+                return ParseResult(std::make_unique<Literal>(expected, parsedValue->template get<std::vector<Value>>()));
+            }
+        }
+        
+        return ParseResult(std::make_unique<Literal>(*parsedValue));
+    } else {
+        // bare primitive value (string, number, boolean, null)
+        const optional<Value> parsedValue = parseValue(value, ctx);
+        return ParseResult(std::make_unique<Literal>(*parsedValue));
+    }
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
diff --git a/src/mbgl/style/expression/match.cpp b/src/mbgl/style/expression/match.cpp
new file mode 100644
index 0000000000..35356747c9
--- /dev/null
+++ b/src/mbgl/style/expression/match.cpp
@@ -0,0 +1,263 @@
+#include <mbgl/style/expression/match.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+template <typename T>
+void Match<T>::eachChild(const std::function<void(const Expression&)>& visit) const {
+    visit(*input);
+    for (const std::pair<T, std::shared_ptr<Expression>>& branch : branches) {
+        visit(*branch.second);
+    }
+    visit(*otherwise);
+}
+
+template <typename T>
+bool Match<T>::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Match*>(&e)) {
+        return (*input == *(rhs->input) &&
+                *otherwise == *(rhs->otherwise) &&
+                Expression::childrenEqual(branches, rhs->branches));
+    }
+    return false;
+}
+
+
+template<> EvaluationResult Match<std::string>::evaluate(const EvaluationContext& params) const {
+    const EvaluationResult inputValue = input->evaluate(params);
+    if (!inputValue) {
+        return inputValue.error();
+    }
+
+    auto it = branches.find(inputValue->get<std::string>());
+    if (it != branches.end()) {
+        return (*it).second->evaluate(params);
+    }
+
+    return otherwise->evaluate(params);
+}
+
+template<> EvaluationResult Match<int64_t>::evaluate(const EvaluationContext& params) const {
+    const EvaluationResult inputValue = input->evaluate(params);
+    if (!inputValue) {
+        return inputValue.error();
+    }
+    
+    const auto numeric = inputValue->get<double>();
+    int64_t rounded = std::floor(numeric);
+    if (numeric == rounded) {
+        auto it = branches.find(rounded);
+        if (it != branches.end()) {
+            return (*it).second->evaluate(params);
+        }
+    }
+    
+    return otherwise->evaluate(params);
+}
+
+template class Match<int64_t>;
+template class Match<std::string>;
+
+using InputType = variant<int64_t, std::string>;
+
+using namespace mbgl::style::conversion;
+optional<InputType> parseInputValue(const Convertible& input, ParsingContext& parentContext, std::size_t index, optional<type::Type>& inputType) {
+    using namespace mbgl::style::conversion;
+    optional<InputType> result;
+    optional<type::Type> type;
+
+    auto value = toValue(input);
+
+    if (value) {
+        value->match(
+            [&] (uint64_t n) {
+                if (!Value::isSafeInteger(n)) {
+                    parentContext.error("Branch labels must be integers no larger than " + util::toString(Value::maxSafeInteger()) + ".", index);
+                } else {
+                    type = {type::Number};
+                    result = {static_cast<int64_t>(n)};
+                }
+            },
+            [&] (int64_t n) {
+                if (!Value::isSafeInteger(n)) {
+                    parentContext.error("Branch labels must be integers no larger than " + util::toString(Value::maxSafeInteger()) + ".", index);
+                } else {
+                    type = {type::Number};
+                    result = {n};
+                }
+            },
+            [&] (double n) {
+                if (!Value::isSafeInteger(n)) {
+                    parentContext.error("Branch labels must be integers no larger than " + util::toString(Value::maxSafeInteger()) + ".", index);
+                } else if (n != std::floor(n)) {
+                    parentContext.error("Numeric branch labels must be integer values.", index);
+                } else {
+                    type = {type::Number};
+                    result = {static_cast<int64_t>(n)};
+                }
+            },
+            [&] (const std::string& s) {
+                type = {type::String};
+                result = {s};
+            },
+            [&] (const auto&) {
+                parentContext.error("Branch labels must be numbers or strings.", index);
+            }
+        );
+    } else {
+        parentContext.error("Branch labels must be numbers or strings.", index);
+    }
+
+    if (!type) {
+        return result;
+    }
+
+    if (!inputType) {
+        inputType = type;
+    } else {
+        optional<std::string> err = type::checkSubtype(*inputType, *type);
+        if (err) {
+            parentContext.error(*err, index);
+            return optional<InputType>();
+        }
+    }
+
+    return result;
+}
+
+template <typename T>
+static ParseResult create(type::Type outputType,
+                          std::unique_ptr<Expression>input,
+                          std::vector<std::pair<std::vector<InputType>,
+                                                std::unique_ptr<Expression>>> branches,
+                          std::unique_ptr<Expression> otherwise,
+                          ParsingContext& ctx) {
+    typename Match<T>::Branches typedBranches;
+    
+    std::size_t index = 2;
+
+    typedBranches.reserve(branches.size());
+    for (std::pair<std::vector<InputType>,
+                   std::unique_ptr<Expression>>& pair : branches) {
+        std::shared_ptr<Expression> result = std::move(pair.second);
+        for (const InputType& label : pair.first) {
+            const auto& typedLabel = label.template get<T>();
+            if (typedBranches.find(typedLabel) != typedBranches.end()) {
+                ctx.error("Branch labels must be unique.", index);
+                return ParseResult();
+            }
+            typedBranches.emplace(typedLabel, result);
+        }
+        
+        index += 2;
+    }
+    return ParseResult(std::make_unique<Match<T>>(
+        outputType,
+        std::move(input),
+        std::move(typedBranches),
+        std::move(otherwise)
+    ));
+}
+
+ParseResult parseMatch(const Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+    auto length = arrayLength(value);
+    if (length < 5) {
+        ctx.error(
+            "Expected at least 4 arguments, but found only " + util::toString(length - 1) + "."
+        );
+        return ParseResult();
+    }
+
+    // Expect odd-length array: ["match", input, 2 * (n pairs)..., otherwise]
+    if (length % 2 != 1) {
+        ctx.error("Expected an even number of arguments.");
+        return ParseResult();
+    }
+
+    optional<type::Type> inputType;
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+
+    std::vector<std::pair<std::vector<InputType>,
+                          std::unique_ptr<Expression>>> branches;
+
+    branches.reserve((length - 3) / 2);
+    for (size_t i = 2; i + 1 < length; i += 2) {
+        const auto& label = arrayMember(value, i);
+
+        std::vector<InputType> labels;
+        // Match pair inputs are provided as either a literal value or a
+        // raw JSON array of string / number / boolean values.
+        if (isArray(label)) {
+            auto groupLength = arrayLength(label);
+            if (groupLength == 0) {
+                ctx.error("Expected at least one branch label.", i);
+                return ParseResult();
+            }
+            
+            labels.reserve(groupLength);
+            for (size_t j = 0; j < groupLength; j++) {
+                const optional<InputType> inputValue = parseInputValue(arrayMember(label, j), ctx, i, inputType);
+                if (!inputValue) {
+                    return ParseResult();
+                }
+                labels.push_back(*inputValue);
+            }
+        } else {
+            const optional<InputType> inputValue = parseInputValue(label, ctx, i, inputType);
+            if (!inputValue) {
+                return ParseResult();
+            }
+            labels.push_back(*inputValue);
+        }
+        
+        ParseResult output = ctx.parse(arrayMember(value, i + 1), i + 1, outputType);
+        if (!output) {
+            return ParseResult();
+        }
+        
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+        
+        branches.push_back(std::make_pair(std::move(labels), std::move(*output)));
+    }
+
+    auto input = ctx.parse(arrayMember(value, 1), 1, inputType);
+    if (!input) {
+        return ParseResult();
+    }
+
+    auto otherwise = ctx.parse(arrayMember(value, length - 1), length - 1, outputType);
+    if (!otherwise) {
+        return ParseResult();
+    }
+
+    assert(inputType && outputType);
+
+    return inputType->match(
+        [&](const type::NumberType&) {
+            return create<int64_t>(*outputType, std::move(*input), std::move(branches), std::move(*otherwise), ctx);
+        },
+        [&](const type::StringType&) {
+            return create<std::string>(*outputType, std::move(*input), std::move(branches), std::move(*otherwise), ctx);
+        },
+        [&](const auto&) {
+            // unreachable: inputType is set by parseInputValue(), which only
+            // accepts string and (integer) numeric values.
+            assert(false);
+            return ParseResult();
+        }
+    );
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/parsing_context.cpp b/src/mbgl/style/expression/parsing_context.cpp
new file mode 100644
index 0000000000..501ba2749f
--- /dev/null
+++ b/src/mbgl/style/expression/parsing_context.cpp
@@ -0,0 +1,208 @@
+
+#include <mbgl/style/expression/parsing_context.hpp>
+#include <mbgl/style/expression/check_subtype.hpp>
+#include <mbgl/style/expression/is_constant.hpp>
+#include <mbgl/style/expression/type.hpp>
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/at.hpp>
+#include <mbgl/style/expression/array_assertion.hpp>
+#include <mbgl/style/expression/assertion.hpp>
+#include <mbgl/style/expression/boolean_operator.hpp>
+#include <mbgl/style/expression/case.hpp>
+#include <mbgl/style/expression/coalesce.hpp>
+#include <mbgl/style/expression/coercion.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/style/expression/interpolate.hpp>
+#include <mbgl/style/expression/let.hpp>
+#include <mbgl/style/expression/literal.hpp>
+#include <mbgl/style/expression/match.hpp>
+#include <mbgl/style/expression/step.hpp>
+
+#include <mbgl/style/expression/find_zoom_curve.hpp>
+
+#include <mbgl/style/conversion/get_json_type.hpp>
+
+#include <mbgl/util/string.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+bool isConstant(const Expression& expression) {
+    if (dynamic_cast<const Var*>(&expression)) {
+        return false;
+    }
+    
+    if (auto compound = dynamic_cast<const CompoundExpressionBase*>(&expression)) {
+        if (compound->getName() == "error") {
+            return false;
+        }
+    }
+    
+    bool literalArgs = true;
+    expression.eachChild([&](const Expression& child) {
+        if (!dynamic_cast<const Literal*>(&child)) {
+            literalArgs = false;
+        }
+    });
+    if (!literalArgs) {
+        return false;
+    }
+    
+    return isFeatureConstant(expression) &&
+        isGlobalPropertyConstant(expression, std::array<std::string, 2>{{"zoom", "heatmap-density"}});
+}
+
+using namespace mbgl::style::conversion;
+
+ParseResult ParsingContext::parse(const Convertible& value, std::size_t index_, optional<type::Type> expected_) {
+    ParsingContext child(key + "[" + util::toString(index_) + "]",
+                         errors,
+                         std::move(expected_),
+                         scope);
+    return child.parse(value);
+}
+
+ParseResult ParsingContext::parse(const Convertible& value, std::size_t index_, optional<type::Type> expected_,
+                                  const std::map<std::string, std::shared_ptr<Expression>>& bindings) {
+    ParsingContext child(key + "[" + util::toString(index_) + "]",
+                         errors,
+                         std::move(expected_),
+                         std::make_shared<detail::Scope>(bindings, scope));
+    return child.parse(value);
+}
+
+const ExpressionRegistry& getExpressionRegistry() {
+    static ExpressionRegistry registry {{
+        {"all", All::parse},
+        {"any", Any::parse},
+        {"array", ArrayAssertion::parse},
+        {"at", At::parse},
+        {"boolean", Assertion::parse},
+        {"case", Case::parse},
+        {"coalesce", Coalesce::parse},
+        {"interpolate", parseInterpolate},
+        {"let", Let::parse},
+        {"literal", Literal::parse},
+        {"match", parseMatch},
+        {"number", Assertion::parse},
+        {"object", Assertion::parse},
+        {"step", Step::parse},
+        {"string", Assertion::parse},
+        {"to-color", Coercion::parse},
+        {"to-number", Coercion::parse},
+        {"var", Var::parse}
+    }};
+    return registry;
+}
+
+ParseResult ParsingContext::parse(const Convertible& value)
+{
+    ParseResult parsed;
+    
+    if (isArray(value)) {
+        const std::size_t length = arrayLength(value);
+        if (length == 0) {
+            error(R"(Expected an array with at least one element. If you wanted a literal array, use ["literal", []].)");
+            return ParseResult();
+        }
+        
+        const optional<std::string> op = toString(arrayMember(value, 0));
+        if (!op) {
+            error(
+                "Expression name must be a string, but found " + getJSONType(arrayMember(value, 0)) +
+                    R"( instead. If you wanted a literal array, use ["literal", [...]].)",
+                0
+            );
+            return ParseResult();
+        }
+        
+        const ExpressionRegistry& registry = getExpressionRegistry();
+        auto parseFunction = registry.find(*op);
+        if (parseFunction != registry.end()) {
+            parsed = parseFunction->second(value, *this);
+        } else {
+            parsed = parseCompoundExpression(*op, value, *this);
+        }
+    } else {
+        parsed = Literal::parse(value, *this);
+    }
+    
+    if (!parsed) {
+        assert(errors->size() > 0);
+    } else if (expected) {
+        auto wrapForType = [&](const type::Type& target, std::unique_ptr<Expression> expression) -> std::unique_ptr<Expression> {
+            std::vector<std::unique_ptr<Expression>> args;
+            args.push_back(std::move(expression));
+            if (target == type::Color) {
+                return std::make_unique<Coercion>(target, std::move(args));
+            } else {
+                return std::make_unique<Assertion>(target, std::move(args));
+            }
+        };
+        
+        const type::Type actual = (*parsed)->getType();
+        if (*expected == type::Color && (actual == type::String || actual == type::Value)) {
+            parsed = wrapForType(type::Color, std::move(*parsed));
+        } else if ((*expected == type::String || *expected == type::Number || *expected == type::Boolean) && actual == type::Value) {
+            parsed = wrapForType(*expected, std::move(*parsed));
+        }
+    
+        checkType((*parsed)->getType());
+        if (errors->size() > 0) {
+            return ParseResult();
+        }
+    }
+    
+    // If an expression's arguments are all literals, we can evaluate
+    // it immediately and replace it with a literal value in the
+    // parsed result.
+    if (parsed && !dynamic_cast<Literal *>(parsed->get()) && isConstant(**parsed)) {
+        EvaluationContext params(nullptr);
+        EvaluationResult evaluated((*parsed)->evaluate(params));
+        if (!evaluated) {
+            error(evaluated.error().message);
+            return ParseResult();
+        }
+        
+        const type::Type type = (*parsed)->getType();
+        if (type.is<type::Array>()) {
+            // keep the original expression's array type, even if the evaluated
+            // type is more specific.
+            return ParseResult(std::make_unique<Literal>(
+                  type.get<type::Array>(),
+                  evaluated->get<std::vector<Value>>())
+            );
+        } else {
+            return ParseResult(std::make_unique<Literal>(*evaluated));
+        }
+    }
+
+    // if this is the root expression, enforce constraints on the use ["zoom"].
+    if (key.size() == 0 && parsed && !isZoomConstant(**parsed)) {
+        optional<variant<const InterpolateBase*, const Step*, ParsingError>> zoomCurve = findZoomCurve(parsed->get());
+        if (!zoomCurve) {
+            error(R"("zoom" expression may only be used as input to a top-level "step" or "interpolate" expression.)");
+            return ParseResult();
+        } else if (zoomCurve->is<ParsingError>()) {
+            error(zoomCurve->get<ParsingError>().message);
+            return ParseResult();
+        }
+    }
+
+    return parsed;
+}
+
+optional<std::string> ParsingContext::checkType(const type::Type& t) {
+    assert(expected);
+    optional<std::string> err = type::checkSubtype(*expected, t);
+    if (err) {
+        error(*err);
+    }
+    return err;
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/step.cpp b/src/mbgl/style/expression/step.cpp
new file mode 100644
index 0000000000..bfcb6fd270
--- /dev/null
+++ b/src/mbgl/style/expression/step.cpp
@@ -0,0 +1,152 @@
+#include <mbgl/style/expression/step.hpp>
+#include <mbgl/style/expression/get_covering_stops.hpp>
+#include <mbgl/util/string.hpp>
+
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+EvaluationResult Step::evaluate(const EvaluationContext& params) const {
+    const EvaluationResult evaluatedInput = input->evaluate(params);
+    if (!evaluatedInput) { return evaluatedInput.error(); }
+    float x = *fromExpressionValue<float>(*evaluatedInput);
+
+    if (stops.empty()) {
+        return EvaluationError { "No stops in step curve." };
+    }
+
+    auto it = stops.upper_bound(x);
+    if (it == stops.end()) {
+        return stops.rbegin()->second->evaluate(params);
+    } else if (it == stops.begin()) {
+        return stops.begin()->second->evaluate(params);
+    } else {
+        return std::prev(it)->second->evaluate(params);
+    }
+}
+
+void Step::eachChild(const std::function<void(const Expression&)>& visit) const {
+    visit(*input);
+    for (auto it = stops.begin(); it != stops.end(); it++) {
+        visit(*it->second);
+    }
+}
+
+bool Step::operator==(const Expression& e) const {
+    if (auto rhs = dynamic_cast<const Step*>(&e)) {
+        return *input == *(rhs->input) && Expression::childrenEqual(stops, rhs->stops);
+    }
+    return false;
+}
+
+Range<float> Step::getCoveringStops(const double lower, const double upper) const {
+    return ::mbgl::style::expression::getCoveringStops(stops, lower, upper);
+}
+
+
+ParseResult Step::parse(const mbgl::style::conversion::Convertible& value, ParsingContext& ctx) {
+    assert(isArray(value));
+
+    auto length = arrayLength(value);
+
+    if (length - 1 < 4) {
+        ctx.error("Expected at least 4 arguments, but found only " + util::toString(length - 1) + ".");
+        return ParseResult();
+    }
+    
+    // [step, input, firstOutput_value, 2 * (n pairs)...]
+    if ((length - 1) % 2 != 0) {
+        ctx.error("Expected an even number of arguments.");
+        return ParseResult();
+    }
+    
+    ParseResult input = ctx.parse(arrayMember(value, 1), 1, {type::Number});
+    if (!input) {
+        return input;
+    }
+    
+    std::map<double, std::unique_ptr<Expression>> stops;
+    optional<type::Type> outputType;
+    if (ctx.getExpected() && *ctx.getExpected() != type::Value) {
+        outputType = ctx.getExpected();
+    }
+    
+    double previous = - std::numeric_limits<double>::infinity();
+    
+    // consume the first output value, which doesn't have a corresponding input value,
+    // before proceeding into the "stops" loop below.
+    auto firstOutput = ctx.parse(arrayMember(value, 2), 2, outputType);
+    if (!firstOutput) {
+        return ParseResult();
+    }
+    if (!outputType) {
+        outputType = (*firstOutput)->getType();
+    }
+    stops.emplace(-std::numeric_limits<double>::infinity(), std::move(*firstOutput));
+    
+    
+    for (std::size_t i = 3; i + 1 < length; i += 2) {
+        const optional<mbgl::Value> labelValue = toValue(arrayMember(value, i));
+        optional<double> label;
+        if (labelValue) {
+            labelValue->match(
+                [&](uint64_t n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](int64_t n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](double n) {
+                    if (n > std::numeric_limits<double>::max()) {
+                        label = {std::numeric_limits<double>::infinity()};
+                    } else {
+                        label = {static_cast<double>(n)};
+                    }
+                },
+                [&](const auto&) {}
+            );
+        }
+        if (!label) {
+            ctx.error(R"(Input/output pairs for "step" expressions must be defined using literal numeric values (not computed expressions) for the input values.)", i);
+            return ParseResult();
+        }
+        
+        if (*label <= previous) {
+            ctx.error(
+                R"(Input/output pairs for "step" expressions must be arranged with input values in strictly ascending order.)",
+                i
+            );
+            return ParseResult();
+        }
+        previous = *label;
+        
+        auto output = ctx.parse(arrayMember(value, i + 1), i + 1, outputType);
+        if (!output) {
+            return ParseResult();
+        }
+        if (!outputType) {
+            outputType = (*output)->getType();
+        }
+
+        stops.emplace(*label, std::move(*output));
+    }
+    
+    assert(outputType);
+    
+    return ParseResult(std::make_unique<Step>(*outputType, std::move(*input), std::move(stops)));
+}
+
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
diff --git a/src/mbgl/style/expression/util.cpp b/src/mbgl/style/expression/util.cpp
new file mode 100644
index 0000000000..f198fb3e1b
--- /dev/null
+++ b/src/mbgl/style/expression/util.cpp
@@ -0,0 +1,39 @@
+
+#include <mbgl/style/expression/util.hpp>
+#include <mbgl/style/expression/value.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+std::string stringifyColor(double r, double g, double b, double a) {
+    return stringify(r) + ", " +
+        stringify(g) + ", " +
+        stringify(b) + ", " +
+        stringify(a);
+}
+
+Result<Color> rgba(double r, double g, double b, double a) {
+    if (
+        r < 0 || r > 255 ||
+        g < 0 || g > 255 ||
+        b < 0 || b > 255
+    ) {
+        return EvaluationError {
+            "Invalid rgba value [" + stringifyColor(r, g, b, a)  +
+            "]: 'r', 'g', and 'b' must be between 0 and 255."
+        };
+    }
+    if (a < 0 || a > 1) {
+        return EvaluationError {
+            "Invalid rgba value [" + stringifyColor(r, g, b, a)  +
+            "]: 'a' must be between 0 and 1."
+        };
+    }
+    return Color(r / 255, g / 255, b / 255, a);
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
+
diff --git a/src/mbgl/style/expression/util.hpp b/src/mbgl/style/expression/util.hpp
new file mode 100644
index 0000000000..b6fc408ed9
--- /dev/null
+++ b/src/mbgl/style/expression/util.hpp
@@ -0,0 +1,14 @@
+#pragma once
+
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/util/color.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+Result<Color> rgba(double r, double g, double b, double a);
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/expression/value.cpp b/src/mbgl/style/expression/value.cpp
new file mode 100644
index 0000000000..b75f471ce3
--- /dev/null
+++ b/src/mbgl/style/expression/value.cpp
@@ -0,0 +1,322 @@
+#include <rapidjson/writer.h>
+#include <rapidjson/stringbuffer.h>
+#include <mbgl/style/expression/value.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+type::Type typeOf(const Value& value) {
+    return value.match(
+        [&](bool) -> type::Type { return type::Boolean; },
+        [&](double) -> type::Type { return type::Number; },
+        [&](const std::string&) -> type::Type { return type::String; },
+        [&](const Color&) -> type::Type { return type::Color; },
+        [&](const NullValue&) -> type::Type { return type::Null; },
+        [&](const std::unordered_map<std::string, Value>&) -> type::Type { return type::Object; },
+        [&](const std::vector<Value>& arr) -> type::Type {
+            optional<type::Type> itemType;
+            for (const auto& item : arr) {
+                const type::Type t = typeOf(item);
+                if (!itemType) {
+                    itemType = {t};
+                } else if (*itemType == t) {
+                    continue;
+                } else {
+                    itemType = {type::Value};
+                    break;
+                }
+            }
+
+            return type::Array(itemType.value_or(type::Value), arr.size());
+        }
+    );
+}
+
+void writeJSON(rapidjson::Writer<rapidjson::StringBuffer>& writer, const Value& value) {
+    value.match(
+        [&] (const NullValue&) { writer.Null(); },
+        [&] (bool b) { writer.Bool(b); },
+        [&] (double f) {
+            // make sure integer values are stringified without trailing ".0".
+            f == std::floor(f) ? writer.Int(f) : writer.Double(f);
+        },
+        [&] (const std::string& s) { writer.String(s); },
+        [&] (const Color& c) { writer.String(c.stringify()); },
+        [&] (const std::vector<Value>& arr) {
+            writer.StartArray();
+            for(const auto& item : arr) {
+                writeJSON(writer, item);
+            }
+            writer.EndArray();
+        },
+        [&] (const std::unordered_map<std::string, Value>& obj) {
+            writer.StartObject();
+            for(const auto& entry : obj) {
+                writer.Key(entry.first.c_str());
+                writeJSON(writer, entry.second);
+            }
+            writer.EndObject();
+        }
+    );
+}
+
+std::string stringify(const Value& value) {
+    rapidjson::StringBuffer buffer;
+    rapidjson::Writer<rapidjson::StringBuffer> writer(buffer);
+    writeJSON(writer, value);
+    return buffer.GetString();
+}
+
+struct FromMBGLValue {
+    Value operator()(const std::vector<mbgl::Value>& v) {
+        std::vector<Value> result;
+        result.reserve(v.size());
+        for(const auto& item : v) {
+            result.emplace_back(toExpressionValue(item));
+        }
+        return result;
+    }
+    
+    Value operator()(const std::unordered_map<std::string, mbgl::Value>& v) {
+        std::unordered_map<std::string, Value> result;
+        result.reserve(v.size());
+        for(const auto& entry : v) {
+            result.emplace(entry.first, toExpressionValue(entry.second));
+        }
+        return result;
+    }
+    
+    Value operator()(const std::string& s) { return s; }
+    Value operator()(const bool b) { return b; }
+    Value operator()(const NullValue) { return Null; }
+    Value operator()(const double v) { return v; }
+    Value operator()(const uint64_t& v) {
+        return static_cast<double>(v);
+    }
+    Value operator()(const int64_t& v) {
+        return static_cast<double>(v);
+    }
+};
+
+Value ValueConverter<mbgl::Value>::toExpressionValue(const mbgl::Value& value) {
+    return mbgl::Value::visit(value, FromMBGLValue());
+}
+
+Value ValueConverter<float>::toExpressionValue(const float value) {
+    return static_cast<double>(value);
+}
+
+optional<float> ValueConverter<float>::fromExpressionValue(const Value& value) {
+    if (value.template is<double>()) {
+        double v = value.template get<double>();
+        if (v <= std::numeric_limits<float>::max()) {
+            return static_cast<float>(v);
+        }
+    }
+    return optional<float>();
+}
+
+
+template <typename T, typename Container>
+std::vector<Value> toArrayValue(const Container& value) {
+    std::vector<Value> result;
+    result.reserve(value.size());
+    for (const T& item : value) {
+        result.push_back(ValueConverter<T>::toExpressionValue(item));
+    }
+    return result;
+}
+
+template <typename T, std::size_t N>
+Value ValueConverter<std::array<T, N>>::toExpressionValue(const std::array<T, N>& value) {
+    return toArrayValue<T>(value);
+}
+
+template <typename T, std::size_t N>
+optional<std::array<T, N>> ValueConverter<std::array<T, N>>::fromExpressionValue(const Value& value) {
+    return value.match(
+        [&] (const std::vector<Value>& v) -> optional<std::array<T, N>> {
+            if (v.size() != N) return optional<std::array<T, N>>();
+                std::array<T, N> result;
+                auto it = result.begin();
+                for(const Value& item : v) {
+                    optional<T> convertedItem = ValueConverter<T>::fromExpressionValue(item);
+                    if (!convertedItem) {
+                        return optional<std::array<T, N>>();
+                    }
+                    *it = *convertedItem;
+                    it = std::next(it);
+                }
+                return result;
+        },
+        [&] (const auto&) { return optional<std::array<T, N>>(); }
+    );
+}
+
+
+template <typename T>
+Value ValueConverter<std::vector<T>>::toExpressionValue(const std::vector<T>& value) {
+    return toArrayValue<T>(value);
+}
+
+template <typename T>
+optional<std::vector<T>> ValueConverter<std::vector<T>>::fromExpressionValue(const Value& value) {
+    return value.match(
+        [&] (const std::vector<Value>& v) -> optional<std::vector<T>> {
+            std::vector<T> result;
+            result.reserve(v.size());
+            for(const Value& item : v) {
+                optional<T> convertedItem = ValueConverter<T>::fromExpressionValue(item);
+                if (!convertedItem) {
+                    return optional<std::vector<T>>();
+                }
+                result.push_back(*convertedItem);
+            }
+            return result;
+        },
+        [&] (const auto&) { return optional<std::vector<T>>(); }
+    );
+}
+
+Value ValueConverter<Position>::toExpressionValue(const mbgl::style::Position& value) {
+    return ValueConverter<std::array<float, 3>>::toExpressionValue(value.getSpherical());
+}
+
+optional<Position> ValueConverter<Position>::fromExpressionValue(const Value& v) {
+    auto pos = ValueConverter<std::array<float, 3>>::fromExpressionValue(v);
+    return pos ? optional<Position>(Position(*pos)) : optional<Position>();
+}
+
+template <typename T>
+Value ValueConverter<T, std::enable_if_t< std::is_enum<T>::value >>::toExpressionValue(const T& value) {
+    return std::string(Enum<T>::toString(value));
+}
+
+template <typename T>
+optional<T> ValueConverter<T, std::enable_if_t< std::is_enum<T>::value >>::fromExpressionValue(const Value& value) {
+    return value.match(
+        [&] (const std::string& v) { return Enum<T>::toEnum(v); },
+        [&] (const auto&) { return optional<T>(); }
+    );
+}
+
+
+Value toExpressionValue(const Value& v) {
+    return v;
+}
+
+template <typename T, typename Enable>
+Value toExpressionValue(const T& value) {
+    return ValueConverter<T>::toExpressionValue(value);
+}
+
+optional<Value> fromExpressionValue(const Value& v) {
+    return optional<Value>(v);
+}
+
+template <typename T>
+std::enable_if_t< !std::is_convertible<T, Value>::value,
+optional<T>> fromExpressionValue(const Value& v)
+{
+    return ValueConverter<T>::fromExpressionValue(v);
+}
+
+template <typename T>
+type::Type valueTypeToExpressionType() {
+    return ValueConverter<T>::expressionType();
+}
+
+template <> type::Type valueTypeToExpressionType<Value>() { return type::Value; }
+template <> type::Type valueTypeToExpressionType<NullValue>() { return type::Null; }
+template <> type::Type valueTypeToExpressionType<bool>() { return type::Boolean; }
+template <> type::Type valueTypeToExpressionType<double>() { return type::Number; }
+template <> type::Type valueTypeToExpressionType<std::string>() { return type::String; }
+template <> type::Type valueTypeToExpressionType<Color>() { return type::Color; }
+template <> type::Type valueTypeToExpressionType<std::unordered_map<std::string, Value>>() { return type::Object; }
+template <> type::Type valueTypeToExpressionType<std::vector<Value>>() { return type::Array(type::Value); }
+
+// used only for the special (and private) "error" expression
+template <> type::Type valueTypeToExpressionType<type::ErrorType>() { return type::Error; }
+
+
+template Value toExpressionValue(const mbgl::Value&);
+
+
+// for to_rgba expression
+template type::Type valueTypeToExpressionType<std::array<double, 4>>();
+template optional<std::array<double, 4>> fromExpressionValue<std::array<double, 4>>(const Value&);
+template Value toExpressionValue(const std::array<double, 4>&);
+
+// layout/paint property types
+template type::Type valueTypeToExpressionType<float>();
+template optional<float> fromExpressionValue<float>(const Value&);
+template Value toExpressionValue(const float&);
+
+template type::Type valueTypeToExpressionType<std::array<float, 2>>();
+template optional<std::array<float, 2>> fromExpressionValue<std::array<float, 2>>(const Value&);
+template Value toExpressionValue(const std::array<float, 2>&);
+
+template type::Type valueTypeToExpressionType<std::array<float, 4>>();
+template optional<std::array<float, 4>> fromExpressionValue<std::array<float, 4>>(const Value&);
+template Value toExpressionValue(const std::array<float, 4>&);
+
+template type::Type valueTypeToExpressionType<std::vector<float>>();
+template optional<std::vector<float>> fromExpressionValue<std::vector<float>>(const Value&);
+template Value toExpressionValue(const std::vector<float>&);
+
+template type::Type valueTypeToExpressionType<std::vector<std::string>>();
+template optional<std::vector<std::string>> fromExpressionValue<std::vector<std::string>>(const Value&);
+template Value toExpressionValue(const std::vector<std::string>&);
+
+template type::Type valueTypeToExpressionType<AlignmentType>();
+template optional<AlignmentType> fromExpressionValue<AlignmentType>(const Value&);
+template Value toExpressionValue(const AlignmentType&);
+
+template type::Type valueTypeToExpressionType<CirclePitchScaleType>();
+template optional<CirclePitchScaleType> fromExpressionValue<CirclePitchScaleType>(const Value&);
+template Value toExpressionValue(const CirclePitchScaleType&);
+
+template type::Type valueTypeToExpressionType<IconTextFitType>();
+template optional<IconTextFitType> fromExpressionValue<IconTextFitType>(const Value&);
+template Value toExpressionValue(const IconTextFitType&);
+
+template type::Type valueTypeToExpressionType<LineCapType>();
+template optional<LineCapType> fromExpressionValue<LineCapType>(const Value&);
+template Value toExpressionValue(const LineCapType&);
+
+template type::Type valueTypeToExpressionType<LineJoinType>();
+template optional<LineJoinType> fromExpressionValue<LineJoinType>(const Value&);
+template Value toExpressionValue(const LineJoinType&);
+
+template type::Type valueTypeToExpressionType<SymbolPlacementType>();
+template optional<SymbolPlacementType> fromExpressionValue<SymbolPlacementType>(const Value&);
+template Value toExpressionValue(const SymbolPlacementType&);
+
+template type::Type valueTypeToExpressionType<SymbolAnchorType>();
+template optional<SymbolAnchorType> fromExpressionValue<SymbolAnchorType>(const Value&);
+template Value toExpressionValue(const SymbolAnchorType&);
+
+template type::Type valueTypeToExpressionType<TextJustifyType>();
+template optional<TextJustifyType> fromExpressionValue<TextJustifyType>(const Value&);
+template Value toExpressionValue(const TextJustifyType&);
+
+template type::Type valueTypeToExpressionType<TextTransformType>();
+template optional<TextTransformType> fromExpressionValue<TextTransformType>(const Value&);
+template Value toExpressionValue(const TextTransformType&);
+
+template type::Type valueTypeToExpressionType<TranslateAnchorType>();
+template optional<TranslateAnchorType> fromExpressionValue<TranslateAnchorType>(const Value&);
+template Value toExpressionValue(const TranslateAnchorType&);
+
+template type::Type valueTypeToExpressionType<LightAnchorType>();
+template optional<LightAnchorType> fromExpressionValue<LightAnchorType>(const Value&);
+template Value toExpressionValue(const LightAnchorType&);
+
+template type::Type valueTypeToExpressionType<Position>();
+template optional<Position> fromExpressionValue<Position>(const Value&);
+template Value toExpressionValue(const Position&);
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/function/expression.cpp b/src/mbgl/style/function/expression.cpp
new file mode 100644
index 0000000000..d9dbbfa1d3
--- /dev/null
+++ b/src/mbgl/style/function/expression.cpp
@@ -0,0 +1,38 @@
+#include <mbgl/style/expression/expression.hpp>
+#include <mbgl/style/expression/compound_expression.hpp>
+#include <mbgl/tile/geometry_tile_data.hpp>
+
+namespace mbgl {
+namespace style {
+namespace expression {
+
+class GeoJSONFeature : public GeometryTileFeature {
+public:
+    const Feature& feature;
+
+    GeoJSONFeature(const Feature& feature_) : feature(feature_) {}
+
+    FeatureType getType() const override  {
+        return apply_visitor(ToFeatureType(), feature.geometry);
+    }
+    PropertyMap getProperties() const override { return feature.properties; }
+    optional<FeatureIdentifier> getID() const override { return feature.id; }
+    GeometryCollection getGeometries() const override { return {}; }
+    optional<mbgl::Value> getValue(const std::string& key) const override {
+        auto it = feature.properties.find(key);
+        if (it != feature.properties.end()) {
+            return optional<mbgl::Value>(it->second);
+        }
+        return optional<mbgl::Value>();
+    }
+};
+
+
+EvaluationResult Expression::evaluate(optional<float> zoom, const Feature& feature, optional<double> heatmapDensity) const {
+    GeoJSONFeature f(feature);
+    return this->evaluate(EvaluationContext(zoom, &f, heatmapDensity));
+}
+
+} // namespace expression
+} // namespace style
+} // namespace mbgl