path: root/src/language.h

// 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_