Implement Expressions (#9439)

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

33 files changed, 2087 insertions, 101 deletions

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..65c5ebe188
--- /dev/null
+++ b/include/mbgl/style/expression/parsing_context.hpp
@@ -0,0 +1,147 @@
+#pragma once
+
+#include <mbgl/util/optional.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 + "[" + std::to_string(child) + "]"});
+    }
+    
+    void error(std::string message, std::size_t child, std::size_t grandchild) {
+        errors->push_back({message, key + "[" + std::to_string(child) + "][" + std::to_string(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..d801cd3ac9
--- /dev/null
+++ b/include/mbgl/style/expression/type.hpp
@@ -0,0 +1,111 @@
+#pragma once
+
+#include <mbgl/util/optional.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) + ", " + std::to_string(*N) + ">";
+        } else if (itemType == Value) {
+            return "array";
+        } else {
+            return "array<" + toString(itemType) + ">";
+        }
+    }
+
+    bool operator==(const Array& rhs) const { return itemType == rhs.itemType && N == rhs.N; }
+    
+    Type itemType;
+    optional<std::size_t> N;
+};
+    
+template <class T>
+std::string toString(const T& type) { return type.match([&] (const auto& t) { return t.getName(); }); }
+
+} // namespace type
+} // namespace expression
+} // namespace style
+} // namespace mbgl
diff --git a/include/mbgl/style/expression/value.hpp b/include/mbgl/style/expression/value.hpp
new file mode 100644
index 0000000000..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/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;