From 179e8eafe4702189de965fd652ed1f3a9e150d3a Mon Sep 17 00:00:00 2001 From: Stephen Thirlwall Date: Fri, 27 Mar 2015 09:04:35 +1100 Subject: [PATCH] c++11: step 2 Note that the optional tests for step 1 now fail because I no longer create a hash directly in the reader, rather handle this as a reader macro: { LIST } -> ( hash-map LIST ) This way, once the constructor has built the hash-map, the hash is now evaluated, and its evaluation procedure is a no-op. I'd like to do the same with vectors, but this isn't so easy, as we use vectors as parameter lists in fn* later on. ie. we'd have this situation, which is incorrect (and I don't see an obvious workaround) (fn* [params] body) -> (fn* (vector params) body) --- cpp/Environment.cpp | 19 ++++++ cpp/Environment.h | 20 +++++++ cpp/MAL.h | 10 +++- cpp/Makefile | 3 +- cpp/Reader.cpp | 3 +- cpp/Types.cpp | 89 +++++++++++++++++++++++----- cpp/Types.h | 63 +++++++++++++++++++- cpp/Validation.cpp | 33 +++++++++++ cpp/Validation.h | 5 ++ cpp/step1_read_print.cpp | 18 +++++- cpp/step2_eval.cpp | 125 +++++++++++++++++++++++++++++++++++++++ 11 files changed, 365 insertions(+), 23 deletions(-) create mode 100644 cpp/Environment.cpp create mode 100644 cpp/Environment.h create mode 100644 cpp/Validation.cpp create mode 100644 cpp/step2_eval.cpp diff --git a/cpp/Environment.cpp b/cpp/Environment.cpp new file mode 100644 index 00000000..9be35e5d --- /dev/null +++ b/cpp/Environment.cpp @@ -0,0 +1,19 @@ +#include "Environment.h" +#include "Types.h" + +#include + +malValuePtr malEnv::get(const String& symbol) +{ + auto it = m_map.find(symbol); + if (it != m_map.end()) { + return it->second; + } + ASSERT(false, "'%s' not found", symbol.c_str()); +} + +malValuePtr malEnv::set(const String& symbol, malValuePtr value) +{ + m_map[symbol] = value; + return value; +} diff --git a/cpp/Environment.h b/cpp/Environment.h new file mode 100644 index 00000000..145b45ae --- /dev/null +++ b/cpp/Environment.h @@ -0,0 +1,20 @@ +#ifndef INCLUDE_ENVIRONMENT_H +#define INCLUDE_ENVIRONMENT_H + +#include "MAL.h" + +#include + +class malEnv { +public: + malEnv() {} + + malValuePtr get(const String& symbol); + malValuePtr set(const String& symbol, malValuePtr value); + +private: + typedef std::map Map; + Map m_map; +}; + +#endif // INCLUDE_ENVIRONMENT_H diff --git a/cpp/MAL.h b/cpp/MAL.h index d9c8b8f7..524a75b3 100644 --- a/cpp/MAL.h +++ b/cpp/MAL.h @@ -11,10 +11,16 @@ class malValue; typedef RefCountedPtr malValuePtr; typedef std::vector malValueVec; +typedef malValueVec::iterator malValueIter; + +class malEnv; // step*.cpp -extern malValuePtr EVAL(malValuePtr ast); -extern String rep(const String& input); +extern malValuePtr APPLY(malValuePtr op, + malValueIter argsBegin, malValueIter argsEnd, + malEnv& env); +extern malValuePtr EVAL(malValuePtr ast, malEnv& env); +extern String rep(const String& input, malEnv& env); // Reader.cpp extern malValuePtr readStr(const String& input); diff --git a/cpp/Makefile b/cpp/Makefile index ef146ae2..5696562b 100644 --- a/cpp/Makefile +++ b/cpp/Makefile @@ -18,7 +18,8 @@ DEBUG=-ggdb CXXFLAGS=-O3 -Wall $(DEBUG) $(INCPATHS) -std=c++11 LDFLAGS=-O3 $(DEBUG) $(LIBPATHS) -L. -lreadline -lhistory -LIBSOURCES=Reader.cpp ReadLine.cpp String.cpp Types.cpp +LIBSOURCES=Environment.cpp Reader.cpp ReadLine.cpp String.cpp \ + Types.cpp Validation.cpp LIBOBJS=$(LIBSOURCES:%.cpp=%.o) MAINS=$(wildcard step*.cpp) diff --git a/cpp/Reader.cpp b/cpp/Reader.cpp index cf666285..4e0fe020 100644 --- a/cpp/Reader.cpp +++ b/cpp/Reader.cpp @@ -115,8 +115,9 @@ static malValuePtr readForm(Tokeniser& tokeniser) if (token == "{") { tokeniser.next(); std::unique_ptr items(new malValueVec); + items->push_back(mal::symbol("hash-map")); readList(tokeniser, items.get(), "}"); - return mal::hash(items.release()); + return mal::list(items.release()); } return readAtom(tokeniser); } diff --git a/cpp/Types.cpp b/cpp/Types.cpp index 59882ea5..9b6ebde2 100644 --- a/cpp/Types.cpp +++ b/cpp/Types.cpp @@ -1,4 +1,5 @@ #include "Debug.h" +#include "Environment.h" #include "Types.h" #include @@ -6,18 +7,22 @@ #include namespace mal { + malValuePtr builtin(const String& name, malBuiltIn::ApplyFunc handler) { + return malValuePtr(new malBuiltIn(name, handler)); + }; + malValuePtr falseValue() { static malValuePtr c(new malConstant("false")); return malValuePtr(c); }; - malValuePtr hash(malValueVec* items) { - return malValuePtr(new malHash(items)); - }; + malValuePtr hash(malValueIter argsBegin, malValueIter argsEnd) { + return malValuePtr(new malHash(argsBegin, argsEnd)); + } malValuePtr integer(int value) { return malValuePtr(new malInteger(value)); - } + }; malValuePtr integer(const String& token) { return integer(std::stoi(token)); @@ -75,31 +80,47 @@ namespace mal { }; }; +malValuePtr malBuiltIn::apply(malValueIter argsBegin, + malValueIter argsEnd, + malEnv& env) const +{ + return m_handler(m_name, argsBegin, argsEnd, env); +} + static String makeHashKey(malValuePtr key) { - if (malString* skey = dynamic_cast(key.ptr())) { + if (const malString* skey = DYNAMIC_CAST(malString, key)) { return skey->print(true); } - else if (malKeyword* kkey = dynamic_cast(key.ptr())) { + else if (const malKeyword* kkey = DYNAMIC_CAST(malKeyword, key)) { return kkey->print(true); } ASSERT(false, "%s is not a string or keyword", key->print(true).c_str()); } -static malHash::Map createMap(malValueVec* items) +static malHash::Map addToMap(malHash::Map& map, + malValueIter argsBegin, malValueIter argsEnd) { - int itemCount = items->size(); - ASSERT(itemCount % 2 == 0, "hash-map requires an even-sized list"); - - malHash::Map map; - for (int i = 0; i < itemCount; i += 2) { - map[makeHashKey(items->at(i))] = items->at(i+1); + // This is intended to be called with pre-evaluated arguments. + for (auto it = argsBegin; it != argsEnd; ++it) { + String key = makeHashKey(*it++); + map[key] = *it; } + return map; } -malHash::malHash(malValueVec* items) -: m_map(createMap(items)) +static malHash::Map createMap(malValueIter argsBegin, malValueIter argsEnd) +{ + ASSERT(std::distance(argsBegin, argsEnd) % 2 == 0, + "hash-map requires an even-sized list"); + + malHash::Map map; + return addToMap(map, argsBegin, argsEnd); +} + +malHash::malHash(malValueIter argsBegin, malValueIter argsEnd) +: m_map(createMap(argsBegin, argsEnd)) { } @@ -120,11 +141,29 @@ String malHash::print(bool readably) const return s + "}"; } +malValuePtr malList::eval(malEnv& env) +{ + if (count() == 0) { + return malValuePtr(this); + } + + std::unique_ptr items(evalItems(env)); + auto it = items->begin(); + malValuePtr op = *it; + return APPLY(op, ++it, items->end(), env); +} + String malList::print(bool readably) const { return '(' + malSequence::print(readably) + ')'; } +malValuePtr malValue::eval(malEnv& env) +{ + // Default case of eval is just to return the object itself. + return malValuePtr(this); +} + malSequence::malSequence(malValueVec* items) : m_items(items) { @@ -136,6 +175,16 @@ malSequence::~malSequence() delete m_items; } +malValueVec* malSequence::evalItems(malEnv& env) const +{ + malValueVec* items = new malValueVec;; + items->reserve(count()); + for (auto it = m_items->begin(), end = m_items->end(); it != end; ++it) { + items->push_back(EVAL(*it, env)); + } + return items; +} + String malSequence::print(bool readably) const { String str; @@ -162,6 +211,16 @@ String malString::print(bool readably) const return readably ? escapedValue() : value(); } +malValuePtr malSymbol::eval(malEnv& env) +{ + return env.get(value()); +} + +malValuePtr malVector::eval(malEnv& env) +{ + return mal::vector(evalItems(env)); +} + String malVector::print(bool readably) const { return '[' + malSequence::print(readably) + ']'; diff --git a/cpp/Types.h b/cpp/Types.h index 4e68cd77..81948504 100644 --- a/cpp/Types.h +++ b/cpp/Types.h @@ -19,9 +19,21 @@ public: TRACE_OBJECT("Destroying malValue %p\n", this); } + virtual malValuePtr eval(malEnv& env); + virtual String print(bool readably) const = 0; }; +template +T* value_cast(malValuePtr obj, const char* typeName) { + T* dest = dynamic_cast(obj.ptr()); + ASSERT(dest != NULL, "%s is not a %s", obj->print(true).c_str(), typeName); + return dest; +} + +#define VALUE_CAST(Type, Value) value_cast(Value, #Type) +#define DYNAMIC_CAST(Type, Value) (dynamic_cast((Value).ptr())) + class malConstant : public malValue { public: malConstant(String name) : m_name(name) { } @@ -40,6 +52,8 @@ public: return std::to_string(m_value); } + int value() const { return m_value; } + private: const int m_value; }; @@ -77,6 +91,8 @@ class malSymbol : public malStringBase { public: malSymbol(const String& token) : malStringBase(token) { } + + virtual malValuePtr eval(malEnv& env); }; class malSequence : public malValue { @@ -86,6 +102,12 @@ public: virtual String print(bool readably) const; + malValueVec* evalItems(malEnv& env) const; + int count() const { return m_items->size(); } + + malValueIter begin() const { return m_items->begin(); } + malValueIter end() const { return m_items->end(); } + private: malValueVec* const m_items; }; @@ -95,20 +117,31 @@ public: malList(malValueVec* items) : malSequence(items) { } virtual String print(bool readably) const; + virtual malValuePtr eval(malEnv& env); }; class malVector : public malSequence { public: malVector(malValueVec* items) : malSequence(items) { } + virtual malValuePtr eval(malEnv& env); virtual String print(bool readably) const; }; +class malApplicable : public malValue { +public: + malApplicable() { } + + virtual malValuePtr apply(malValueIter argsBegin, + malValueIter argsEnd, + malEnv& env) const = 0; +}; + class malHash : public malValue { public: typedef std::map Map; - malHash(malValueVec* items); + malHash(malValueIter argsBegin, malValueIter argsEnd); virtual String print(bool readably) const; @@ -116,9 +149,35 @@ private: const Map m_map; }; +class malBuiltIn : public malApplicable { +public: + typedef malValuePtr (ApplyFunc)(const String& name, + malValueIter argsBegin, + malValueIter argsEnd, + malEnv& env); + + malBuiltIn(const String& name, ApplyFunc* handler) + : m_name(name), m_handler(handler) { } + + virtual malValuePtr apply(malValueIter argsBegin, + malValueIter argsEnd, + malEnv& env) const; + + virtual String print(bool readably) const { + return STRF("#builtin-function(%s)", m_name.c_str()); + } + + String name() const { return m_name; } + +private: + const String m_name; + ApplyFunc* m_handler; +}; + namespace mal { + malValuePtr builtin(const String& name, malBuiltIn::ApplyFunc handler); malValuePtr falseValue(); - malValuePtr hash(malValueVec* items); + malValuePtr hash(malValueIter argsBegin, malValueIter argsEnd); malValuePtr integer(int value); malValuePtr integer(const String& token); malValuePtr keyword(const String& token); diff --git a/cpp/Validation.cpp b/cpp/Validation.cpp new file mode 100644 index 00000000..d15ef541 --- /dev/null +++ b/cpp/Validation.cpp @@ -0,0 +1,33 @@ +#include "Validation.h" + +int checkArgsIs(const char* name, int expected, int got) +{ + ASSERT(got == expected, + "\"%s\" expects %d arg%s, %d supplied", + name, expected, PLURAL(expected), got); + return got; +} + +int checkArgsBetween(const char* name, int min, int max, int got) +{ + ASSERT((got >= min) && (got <= max), + "\"%s\" expects between %d and %d arg%s, %d supplied", + name, min, max, PLURAL(max), got); + return got; +} + +int checkArgsAtLeast(const char* name, int min, int got) +{ + ASSERT(got >= min, + "\"%s\" expects at least %d arg%s, %d supplied", + name, min, PLURAL(min), got); + return got; +} + +int checkArgsEven(const char* name, int got) +{ + ASSERT(got % 2 == 0, + "\"%s\" expects an even number of args, %d supplied", + name, got); + return got; +} diff --git a/cpp/Validation.h b/cpp/Validation.h index d419655d..9845ff07 100644 --- a/cpp/Validation.h +++ b/cpp/Validation.h @@ -6,4 +6,9 @@ #define ASSERT(condition, ...) \ if (!(condition)) { throw STRF(__VA_ARGS__); } else { } +extern int checkArgsIs(const char* name, int expected, int got); +extern int checkArgsBetween(const char* name, int min, int max, int got); +extern int checkArgsAtLeast(const char* name, int min, int got); +extern int checkArgsEven(const char* name, int got); + #endif // INCLUDE_VALIDATION_H diff --git a/cpp/step1_read_print.cpp b/cpp/step1_read_print.cpp index 17ecb56b..b7d0957c 100644 --- a/cpp/step1_read_print.cpp +++ b/cpp/step1_read_print.cpp @@ -11,6 +11,9 @@ String PRINT(malValuePtr ast); static ReadLine s_readLine("~/.mal-history"); +static String rep(const String& input); +static malValuePtr EVAL(malValuePtr ast); + int main(int argc, char* argv[]) { String prompt = "user> "; @@ -31,7 +34,7 @@ int main(int argc, char* argv[]) return 0; } -String rep(const String& input) +static String rep(const String& input) { return PRINT(EVAL(READ(input))); } @@ -41,7 +44,7 @@ malValuePtr READ(const String& input) return readStr(input); } -malValuePtr EVAL(malValuePtr ast) +static malValuePtr EVAL(malValuePtr ast) { return ast; } @@ -50,3 +53,14 @@ String PRINT(malValuePtr ast) { return ast->print(true); } + +// These have been added after step 1 to keep the linker happy. +malValuePtr EVAL(malValuePtr ast, malEnv&) +{ + return ast; +} + +malValuePtr APPLY(malValuePtr ast, malValueIter, malValueIter, malEnv&) +{ + return ast; +} diff --git a/cpp/step2_eval.cpp b/cpp/step2_eval.cpp new file mode 100644 index 00000000..c68a8fdc --- /dev/null +++ b/cpp/step2_eval.cpp @@ -0,0 +1,125 @@ +#include "MAL.h" + +#include "Environment.h" +#include "ReadLine.h" +#include "Types.h" + +#include +#include + +malValuePtr READ(const String& input); +String PRINT(malValuePtr ast); + +static ReadLine s_readLine("~/.mal-history"); +static malBuiltIn::ApplyFunc + builtIn_add, builtIn_sub, builtIn_mul, builtIn_div, builtIn_hash_map; + +int main(int argc, char* argv[]) +{ + String prompt = "user> "; + String input; + malEnv replEnv; + replEnv.set("+", mal::builtin("+", &builtIn_add)); + replEnv.set("-", mal::builtin("-", &builtIn_sub)); + replEnv.set("*", mal::builtin("+", &builtIn_mul)); + replEnv.set("/", mal::builtin("/", &builtIn_div)); + replEnv.set("hash-map", mal::builtin("hash-map", &builtIn_hash_map)); + while (s_readLine.get(prompt, input)) { + String out; + try { + out = rep(input, replEnv); + } + catch (malEmptyInputException&) { + continue; // no output + } + catch (String& s) { + out = s; + }; + std::cout << out << "\n"; + } + return 0; +} + +String rep(const String& input, malEnv& env) +{ + return PRINT(EVAL(READ(input), env)); +} + +malValuePtr READ(const String& input) +{ + return readStr(input); +} + +malValuePtr EVAL(malValuePtr ast, malEnv& env) +{ + return ast->eval(env); +} + +String PRINT(malValuePtr ast) +{ + return ast->print(true); +} + +malValuePtr APPLY(malValuePtr op, malValueIter argsBegin, malValueIter argsEnd, + malEnv& env) +{ + const malApplicable* handler = DYNAMIC_CAST(malApplicable, op); + ASSERT(handler != NULL, "\"%s\" is not applicable", op->print(true).c_str()); + + return handler->apply(argsBegin, argsEnd, env); +} + +#define ARG(type, name) type* name = VALUE_CAST(type, *argsBegin++) + +#define CHECK_ARGS_IS(expected) \ + checkArgsIs(name.c_str(), expected, std::distance(argsBegin, argsEnd)) + +#define CHECK_ARGS_BETWEEN(min, max) \ + checkArgsBetween(name.c_str(), min, max, std::distance(argsBegin, argsEnd)) + + +static malValuePtr builtIn_add(const String& name, + malValueIter argsBegin, malValueIter argsEnd, malEnv& env) +{ + CHECK_ARGS_IS(2); + ARG(malInteger, lhs); + ARG(malInteger, rhs); + return mal::integer(lhs->value() + rhs->value()); +} + +static malValuePtr builtIn_sub(const String& name, + malValueIter argsBegin, malValueIter argsEnd, malEnv& env) +{ + int argCount = CHECK_ARGS_BETWEEN(1, 2); + ARG(malInteger, lhs); + if (argCount == 1) { + return mal::integer(- lhs->value()); + } + ARG(malInteger, rhs); + return mal::integer(lhs->value() - rhs->value()); +} + +static malValuePtr builtIn_mul(const String& name, + malValueIter argsBegin, malValueIter argsEnd, malEnv& env) +{ + CHECK_ARGS_IS(2); + ARG(malInteger, lhs); + ARG(malInteger, rhs); + return mal::integer(lhs->value() * rhs->value()); +} + +static malValuePtr builtIn_div(const String& name, + malValueIter argsBegin, malValueIter argsEnd, malEnv& env) +{ + CHECK_ARGS_IS(2); + ARG(malInteger, lhs); + ARG(malInteger, rhs); + ASSERT(rhs->value() != 0, "Division by zero"); \ + return mal::integer(lhs->value() / rhs->value()); +} + +static malValuePtr builtIn_hash_map(const String& name, + malValueIter argsBegin, malValueIter argsEnd, malEnv& env) +{ + return mal::hash(argsBegin, argsEnd); +} -- 2.20.1