1 files changed, 230 insertions, 0 deletions
diff --git a/src/language.h b/src/language.h
new file mode 100644
index 0000000..75c191c
--- /dev/null
+++ b/src/language.h
@@ -0,0 +1,230 @@
+// Copyright 2021 Benjamin Barenblat
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+
+// The programming language implemented on the EC abstract machine.
+
+#ifndef EC_SRC_LANGUAGE_H_
+#define EC_SRC_LANGUAGE_H_
+
+#include <memory>
+#include <ostream>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "src/error.h"
+#include "third_party/abseil/absl/container/flat_hash_map.h"
+#include "third_party/abseil/absl/strings/str_cat.h"
+#include "third_party/abseil/absl/strings/string_view.h"
+
+namespace ec {
+
+class LanguageError : public Error {
+ public:
+  using Error::Error;
+};
+
+// The stack underflowed.
+class StackUnderflow : public LanguageError {
+ public:
+  explicit StackUnderflow(absl::string_view op)
+      : LanguageError(absl::StrCat(op, ": too few arguments")) {}
+};
+
+// A lookup failed.
+class UndefinedName : public LanguageError {
+ public:
+  explicit UndefinedName(absl::string_view name)
+      : LanguageError(absl::StrCat(name, ": undefined")) {}
+};
+
+// A function had a type error.
+class TypeError : public LanguageError {
+ public:
+  using LanguageError::LanguageError;
+};
+
+class Term;
+
+// The EC abstract machine. The machine exclusively works with constant terms
+// stored on the heap. This representation makes copying the machine state
+// relatively cheap, which supports undo.
+struct State {
+  // Initializes the machine to the "factory reset" state--an empty stack and an
+  // environment populated only by builtin operations.
+  State() noexcept;
+
+  State(const State&) = default;
+  State& operator=(const State&) = default;
+  State(State&&) noexcept = default;
+  State& operator=(State&&) noexcept = default;
+
+  std::vector<std::shared_ptr<const Term>> stack;  // grows to the right
+  absl::flat_hash_map<std::string, std::shared_ptr<const Term>> environment;
+};
+
+// An abstract base class for language terms themselves.
+class Term {
+ public:
+  virtual ~Term() = default;
+
+  // Fully evaluates the term, mutating the state as necessary.
+  //
+  // This function is required only to provide the basic exception safety
+  // guarantee. You should thus save a copy of State before evaluation and
+  // restore it if an exception is thrown. This pushes some bookkeeping out to
+  // callers, but that probably already exists, since callers likely want to
+  // implement some form of undo feature.
+  virtual void Evaluate(State&) const = 0;
+
+  std::shared_ptr<Term> Clone() const {
+    return std::shared_ptr<Term>(CloneImpl());
+  }
+
+  // Produces a human-readable representation of the term. This will be called
+  // to display it on the stack.
+  virtual std::string Show() const noexcept = 0;
+
+  // Produces an engineer-readable representation of the term. This will be used
+  // in internal errors and for testing.
+  virtual std::string DebugString() const noexcept = 0;
+
+ private:
+  // Duplicates the term onto the heap.
+  virtual Term* CloneImpl() const = 0;
+};
+
+inline std::ostream& operator<<(std::ostream& out, const Term& t) noexcept {
+  return out << t.DebugString();
+}
+
+// A self-evaluating term. Evaluating it pushes it.
+class GroundTerm : public Term {
+ public:
+  // Convenience function to create a const GroundTerm on the heap.
+  static std::shared_ptr<const GroundTerm> Make(double value) noexcept {
+    return std::make_shared<const GroundTerm>(value);
+  }
+
+  explicit GroundTerm(double value) noexcept : value_(value) {}
+
+  GroundTerm(const GroundTerm&) noexcept = default;
+  GroundTerm& operator=(const GroundTerm&) noexcept = default;
+  GroundTerm(GroundTerm&&) noexcept = default;
+  GroundTerm& operator=(GroundTerm&&) noexcept = default;
+
+  void Evaluate(State& state) const noexcept override;
+
+  std::shared_ptr<GroundTerm> Clone() const noexcept {
+    return std::shared_ptr<GroundTerm>(CloneImpl());
+  }
+
+  std::string Show() const noexcept override;
+
+  std::string DebugString() const noexcept override;
+
+  bool operator==(const GroundTerm& other) const noexcept {
+    return value_ == other.value_;
+  }
+
+  double value() const noexcept { return value_; }
+
+ private:
+  GroundTerm* CloneImpl() const noexcept override;
+
+  double value_;
+};
+
+// A term whose implementation is a C++ function. Evaluating it mutates the
+// machine state by that function.
+class ForeignProgramTerm : public Term {
+ public:
+  // Convenience function to create a const ForeignProgramTerm on the heap.
+  static std::shared_ptr<const ForeignProgramTerm> Make(
+      void (*impl)(State&)) noexcept {
+    return std::make_shared<const ForeignProgramTerm>(impl);
+  }
+
+  explicit ForeignProgramTerm(void (*impl)(State&)) noexcept : impl_(impl) {}
+
+  ForeignProgramTerm(const ForeignProgramTerm&) noexcept = default;
+  ForeignProgramTerm& operator=(const ForeignProgramTerm&) noexcept = default;
+  ForeignProgramTerm(ForeignProgramTerm&&) noexcept = default;
+  ForeignProgramTerm& operator=(ForeignProgramTerm&&) noexcept = default;
+
+  void Evaluate(State&) const override;
+
+  std::shared_ptr<ForeignProgramTerm> Clone() const noexcept {
+    return std::shared_ptr<ForeignProgramTerm>(CloneImpl());
+  }
+
+  std::string Show() const noexcept override;
+
+  std::string DebugString() const noexcept override;
+
+ private:
+  ForeignProgramTerm* CloneImpl() const noexcept override;
+
+  void (*impl_)(State&);
+};
+
+// An identifier name. Evaluating it looks it up in the environment and pushes
+// the result onto the stack.
+class SymbolTerm : public Term {
+ public:
+  // Convenience function to create a const SymbolTerm on the heap.
+  static std::shared_ptr<const SymbolTerm> Make(std::string name) noexcept {
+    return std::make_shared<const SymbolTerm>(std::move(name));
+  }
+
+  explicit SymbolTerm(std::string name) noexcept : name_(std::move(name)) {}
+
+  SymbolTerm(const SymbolTerm&) noexcept = default;
+  SymbolTerm& operator=(const SymbolTerm&) noexcept = default;
+  SymbolTerm(SymbolTerm&&) noexcept = default;
+  SymbolTerm& operator=(SymbolTerm&&) noexcept = default;
+
+  void Evaluate(State&) const override;
+
+  std::shared_ptr<SymbolTerm> Clone() const noexcept {
+    return std::shared_ptr<SymbolTerm>(CloneImpl());
+  }
+
+  std::string Show() const noexcept override;
+
+  std::string DebugString() const noexcept override;
+
+  bool operator==(const SymbolTerm& other) const noexcept {
+    return name_ == other.name_;
+  }
+
+ private:
+  SymbolTerm* CloneImpl() const noexcept override;
+
+  std::string name_;
+};
+
+// A convenience function for rendering stack elements.
+void FormatStackElement(std::string*, std::shared_ptr<const Term>) noexcept;
+
+// An EC program.
+using Program = std::vector<std::shared_ptr<const Term>>;
+
+// A batch-mode evaluator for whole programs. Like Term::Evaluate, this function
+// provides only the basic exception safety guarantee.
+void EvaluateAll(const Program&, State&);
+
+}  // namespace ec
+
+#endif  // EC_SRC_LANGUAGE_H_