--- /dev/null
+#ifndef INCLUDE_MAL_H
+#define INCLUDE_MAL_H
+
+#include "Debug.h"
+#include "RefCountedPtr.h"
+#include "String.h"
+#include "Validation.h"
+
+#include <vector>
+
+class malValue;
+typedef RefCountedPtr<malValue> malValuePtr;
+typedef std::vector<malValuePtr> malValueVec;
+
+// step*.cpp
+extern malValuePtr EVAL(malValuePtr ast);
+extern String rep(const String& input);
+
+// Reader.cpp
+extern malValuePtr readStr(const String& input);
+
+#endif // INCLUDE_MAL_H
CXXFLAGS=-O3 -Wall $(DEBUG) $(INCPATHS) -std=c++11
LDFLAGS=-O3 $(DEBUG) $(LIBPATHS) -L. -lreadline -lhistory
-LIBSOURCES=ReadLine.cpp String.cpp
+LIBSOURCES=Reader.cpp ReadLine.cpp String.cpp Types.cpp
LIBOBJS=$(LIBSOURCES:%.cpp=%.o)
MAINS=$(wildcard step*.cpp)
--- /dev/null
+#include "MAL.h"
+#include "Types.h"
+
+#include <regex>
+
+typedef std::regex Regex;
+typedef std::sregex_iterator RegexIter;
+
+static const Regex tokenRegex("[\\s,]*(~@|[\\[\\]{}()'`~^@]|\"(?:\\\\.|[^\\\\\"])*\"|;.*|[^\\s\\[\\]{}('\"`,;)]+)");
+static const Regex intRegex("^[-+]?\\d+$");
+static const Regex closeRegex("[\\)\\]}]");
+
+class Tokeniser
+{
+public:
+ Tokeniser(const String& input);
+
+ String peek() const {
+ ASSERT(!eof(), "Tokeniser reading past EOF in peek");
+ return m_iter->str(1);
+ }
+
+ String next() {
+ ASSERT(!eof(), "Tokeniser reading past EOF in next");
+ String ret = peek();
+ checkPrefix();
+ ++m_iter;
+ skipWhitespace();
+ return ret;
+ }
+
+ bool eof() const {
+ return m_iter == m_end;
+ }
+
+private:
+ void skipWhitespace();
+ void checkPrefix();
+
+ RegexIter m_iter;
+ RegexIter m_end;
+};
+
+Tokeniser::Tokeniser(const String& input)
+: m_iter(input.begin(), input.end(), tokenRegex)
+, m_end()
+{
+ skipWhitespace();
+}
+
+static bool isWhitespace(const String& token)
+{
+ return token.empty() || (token[0] == ';');
+}
+
+void Tokeniser::checkPrefix()
+{
+ // This is the unmatched portion before the match.
+ auto prefix = m_iter->prefix();
+
+ if (prefix.length() == 0) {
+ return;
+ }
+
+ const String& text = prefix.str();
+ if (text == "\"") {
+ ASSERT(false, "Expected \", got EOF");
+ }
+ ASSERT(false, "Unexpected \"%s\"", text.c_str());
+}
+
+void Tokeniser::skipWhitespace()
+{
+ while (!eof() && isWhitespace(peek())) {
+ checkPrefix();
+ ++m_iter;
+ }
+}
+
+static malValuePtr readAtom(Tokeniser& tokeniser);
+static malValuePtr readForm(Tokeniser& tokeniser);
+static void readList(Tokeniser& tokeniser, malValueVec* items,
+ const String& end);
+static malValuePtr processMacro(Tokeniser& tokeniser, const String& symbol);
+
+malValuePtr readStr(const String& input)
+{
+ Tokeniser tokeniser(input);
+ if (tokeniser.eof()) {
+ throw malEmptyInputException();
+ }
+ return readForm(tokeniser);
+}
+
+static malValuePtr readForm(Tokeniser& tokeniser)
+{
+ ASSERT(!tokeniser.eof(), "Expected form, got EOF");
+ String token = tokeniser.peek();
+
+ ASSERT(!std::regex_match(token, closeRegex),
+ "Unexpected \"%s\"", token.c_str());
+
+ if (token == "(") {
+ tokeniser.next();
+ std::unique_ptr<malValueVec> items(new malValueVec);
+ readList(tokeniser, items.get(), ")");
+ return mal::list(items.release());
+ }
+ if (token == "[") {
+ tokeniser.next();
+ std::unique_ptr<malValueVec> items(new malValueVec);
+ readList(tokeniser, items.get(), "]");
+ return mal::vector(items.release());
+ }
+ if (token == "{") {
+ tokeniser.next();
+ std::unique_ptr<malValueVec> items(new malValueVec);
+ readList(tokeniser, items.get(), "}");
+ return mal::hash(items.release());
+ }
+ return readAtom(tokeniser);
+}
+
+static malValuePtr readAtom(Tokeniser& tokeniser)
+{
+ struct ReaderMacro {
+ const char* token;
+ const char* symbol;
+ };
+ ReaderMacro macroTable[] = {
+ { "@", "deref" },
+ { "`", "quasiquote" },
+ { "'", "quote" },
+ { "~@", "splice-unquote" },
+ { "~", "unquote" },
+ };
+ const ReaderMacro* macroTableEnd = macroTable + ARRAY_SIZE(macroTable);
+
+ struct Constant {
+ const char* token;
+ malValuePtr value;
+ };
+ Constant constTable[] = {
+ { "false", mal::falseValue() },
+ { "nil", mal::nilValue() },
+ { "true", mal::trueValue() },
+ };
+ const Constant* constTableEnd = constTable + ARRAY_SIZE(constTable);
+
+ String token = tokeniser.next();
+ if (token[0] == '"') {
+ return mal::string(unescape(token));
+ }
+ if (token[0] == ':') {
+ return mal::keyword(token);
+ }
+ if (token == "^") {
+ malValuePtr meta = readForm(tokeniser);
+ malValuePtr value = readForm(tokeniser);
+ // Note that meta and value switch places
+ return mal::list(mal::symbol("with-meta"), value, meta);
+ }
+ for (Constant* it = constTable; it != constTableEnd; ++it) {
+ if (token == it->token) {
+ return it->value;
+ }
+ }
+ for (ReaderMacro *it = macroTable; it < macroTableEnd; ++it) {
+ if (token == it->token) {
+ return processMacro(tokeniser, it->symbol);
+ }
+ }
+ if (std::regex_match(token, intRegex)) {
+ return mal::integer(token);
+ }
+ return mal::symbol(token);
+}
+
+static void readList(Tokeniser& tokeniser, malValueVec* items,
+ const String& end)
+{
+ while (1) {
+ ASSERT(!tokeniser.eof(), "Expected \"%s\", got EOF", end.c_str());
+ if (tokeniser.peek() == end) {
+ tokeniser.next();
+ return;
+ }
+ items->push_back(readForm(tokeniser));
+ }
+}
+
+static malValuePtr processMacro(Tokeniser& tokeniser, const String& symbol)
+{
+ return mal::list(mal::symbol(symbol), readForm(tokeniser));
+}
--- /dev/null
+#ifndef INCLUDE_REFCOUNTEDPTR_H
+#define INCLUDE_REFCOUNTEDPTR_H
+
+#include "Debug.h"
+
+#include <cstddef>
+
+class RefCounted {
+public:
+ RefCounted() : m_refCount(0) { }
+ virtual ~RefCounted() { }
+
+ const RefCounted* acquire() const { m_refCount++; return this; }
+ int release() const { return --m_refCount; }
+ int refCount() const { return m_refCount; }
+
+private:
+ RefCounted(const RefCounted&); // no copy ctor
+ RefCounted& operator = (const RefCounted&); // no assignments
+
+ mutable int m_refCount;
+};
+
+template<class T>
+class RefCountedPtr {
+public:
+ RefCountedPtr() : m_object(0) { }
+
+ RefCountedPtr(T* object) : m_object(0)
+ { acquire(object); }
+
+ RefCountedPtr(const RefCountedPtr& rhs) : m_object(0)
+ { acquire(rhs.m_object); }
+
+ const RefCountedPtr& operator = (const RefCountedPtr& rhs) {
+ acquire(rhs.m_object);
+ return *this;
+ }
+
+ bool operator == (const RefCountedPtr& rhs) const {
+ return m_object == rhs.m_object;
+ }
+
+ bool operator != (const RefCountedPtr& rhs) const {
+ return m_object != rhs.m_object;
+ }
+
+ operator bool () const {
+ return m_object != NULL;
+ }
+
+ ~RefCountedPtr() {
+ release();
+ }
+
+ T* operator -> () const { return m_object; }
+ T* ptr() const { return m_object; }
+
+private:
+ void acquire(T* object) {
+ if (object != NULL) {
+ object->acquire();
+ }
+ release();
+ m_object = object;
+ }
+
+ void release() {
+ if ((m_object != NULL) && (m_object->release() == 0)) {
+ delete m_object;
+ }
+ }
+
+ T* m_object;
+};
+
+#endif // INCLUDE_REFCOUNTEDPTR_H
--- /dev/null
+#ifndef INCLUDE_STATICLIST_H
+#define INCLUDE_STATICLIST_H
+
+template<typename T>
+class StaticList
+{
+public:
+ StaticList() : m_head(NULL) { }
+
+ class Iterator;
+ Iterator begin() { return Iterator(m_head); }
+ Iterator end() { return Iterator(NULL); }
+
+ class Node {
+ public:
+ Node(StaticList<T>& list, T item)
+ : m_item(item), m_next(list.m_head) {
+ list.m_head = this;
+ }
+
+ private:
+ friend class Iterator;
+ T m_item;
+ Node* m_next;
+ };
+
+ class Iterator {
+ public:
+ Iterator& operator ++ () {
+ m_node = m_node->m_next;
+ return *this;
+ }
+
+ T& operator * () { return m_node->m_item; }
+ bool operator != (const Iterator& that) {
+ return m_node != that.m_node;
+ }
+
+ private:
+ friend class StaticList<T>;
+ Iterator(Node* node) : m_node(node) { }
+ Node* m_node;
+ };
+
+private:
+ friend class Node;
+ Node* m_head;
+};
+
+#endif // INCLUDE_STATICLIST_H
+#include "Debug.h"
#include "String.h"
+#include <stdarg.h>
+#include <stdio.h>
#include <stdlib.h>
+#include <string.h>
+
+// Adapted from: http://stackoverflow.com/questions/2342162
+String stringPrintf(const char* fmt, ...) {
+ int size = strlen(fmt); // make a guess
+ String str;
+ va_list ap;
+ while (1) {
+ str.resize(size);
+ va_start(ap, fmt);
+ int n = vsnprintf((char *)str.data(), size, fmt, ap);
+ va_end(ap);
+ if (n > -1 && n < size) { // Everything worked
+ str.resize(n);
+ return str;
+ }
+ if (n > -1) // Needed size returned
+ size = n + 1; // For null char
+ else
+ size *= 2; // Guess at a larger size (OS specific)
+ }
+ return str;
+}
String copyAndFree(char* mallocedString)
{
free(mallocedString);
return ret;
}
+
+String escape(const String& in)
+{
+ String out;
+ out.reserve(in.size() * 2 + 2); // each char may get escaped + two "'s
+ out += '"';
+ for (auto it = in.begin(), end = in.end(); it != end; ++it) {
+ char c = *it;
+ switch (c) {
+ case '\\': out += "\\\\"; break;
+ case '\n': out += "\\n"; break;
+ case '"': out += "\\\""; break;
+ default: out += c; break;
+ };
+ }
+ out += '"';
+ out.shrink_to_fit();
+ return out;
+}
+
+static char unescape(char c)
+{
+ switch (c) {
+ case '\\': return '\\';
+ case 'n': return '\n';
+ case '"': return '"';
+ default: return c;
+ }
+}
+
+String unescape(const String& in)
+{
+ String out;
+ out.reserve(in.size()); // unescaped string will always be shorter
+
+ // in will have double-quotes at either end, so move the iterators in
+ for (auto it = in.begin()+1, end = in.end()-1; it != end; ++it) {
+ char c = *it;
+ if (c == '\\') {
+ ++it;
+ if (it != end) {
+ out += unescape(*it);
+ }
+ }
+ else {
+ out += c;
+ }
+ }
+ out.shrink_to_fit();
+ return out;
+}
+
--- /dev/null
+#include "Debug.h"
+#include "Types.h"
+
+#include <algorithm>
+#include <memory>
+#include <typeinfo>
+
+namespace mal {
+ malValuePtr falseValue() {
+ static malValuePtr c(new malConstant("false"));
+ return malValuePtr(c);
+ };
+
+ malValuePtr hash(malValueVec* items) {
+ return malValuePtr(new malHash(items));
+ };
+
+ malValuePtr integer(int value) {
+ return malValuePtr(new malInteger(value));
+ }
+
+ malValuePtr integer(const String& token) {
+ return integer(std::stoi(token));
+ };
+
+ malValuePtr keyword(const String& token) {
+ return malValuePtr(new malKeyword(token));
+ };
+
+ malValuePtr list(malValueVec* items) {
+ return malValuePtr(new malList(items));
+ };
+
+ malValuePtr list(malValuePtr a) {
+ malValueVec* items = new malValueVec(1);
+ items->at(0) = a;
+ return malValuePtr(new malList(items));
+ }
+
+ malValuePtr list(malValuePtr a, malValuePtr b) {
+ malValueVec* items = new malValueVec(2);
+ items->at(0) = a;
+ items->at(1) = b;
+ return malValuePtr(new malList(items));
+ }
+
+ malValuePtr list(malValuePtr a, malValuePtr b, malValuePtr c) {
+ malValueVec* items = new malValueVec(3);
+ items->at(0) = a;
+ items->at(1) = b;
+ items->at(2) = c;
+ return malValuePtr(new malList(items));
+ }
+
+ malValuePtr nilValue() {
+ static malValuePtr c(new malConstant("nil"));
+ return malValuePtr(c);
+ };
+
+ malValuePtr string(const String& token) {
+ return malValuePtr(new malString(token));
+ }
+
+ malValuePtr symbol(const String& token) {
+ return malValuePtr(new malSymbol(token));
+ };
+
+ malValuePtr trueValue() {
+ static malValuePtr c(new malConstant("true"));
+ return malValuePtr(c);
+ };
+
+ malValuePtr vector(malValueVec* items) {
+ return malValuePtr(new malVector(items));
+ };
+};
+
+static String makeHashKey(malValuePtr key)
+{
+ if (malString* skey = dynamic_cast<malString*>(key.ptr())) {
+ return skey->print(true);
+ }
+ else if (malKeyword* kkey = dynamic_cast<malKeyword*>(key.ptr())) {
+ return kkey->print(true);
+ }
+ ASSERT(false, "%s is not a string or keyword", key->print(true).c_str());
+}
+
+static malHash::Map createMap(malValueVec* items)
+{
+ 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);
+ }
+ return map;
+}
+
+malHash::malHash(malValueVec* items)
+: m_map(createMap(items))
+{
+
+}
+
+String malHash::print(bool readably) const
+{
+ String s = "{";
+
+ auto it = m_map.begin(), end = m_map.end();
+ if (it != end) {
+ s += it->first + " " + it->second->print(readably);
+ ++it;
+ }
+ for ( ; it != end; ++it) {
+ s += " " + it->first + " " + it->second->print(readably);
+ }
+
+ return s + "}";
+}
+
+String malList::print(bool readably) const
+{
+ return '(' + malSequence::print(readably) + ')';
+}
+
+malSequence::malSequence(malValueVec* items)
+: m_items(items)
+{
+
+}
+
+malSequence::~malSequence()
+{
+ delete m_items;
+}
+
+String malSequence::print(bool readably) const
+{
+ String str;
+ auto end = m_items->cend();
+ auto it = m_items->cbegin();
+ if (it != end) {
+ str += (*it)->print(readably);
+ ++it;
+ }
+ for ( ; it != end; ++it) {
+ str += " ";
+ str += (*it)->print(readably);
+ }
+ return str;
+}
+
+String malString::escapedValue() const
+{
+ return escape(value());
+}
+
+String malString::print(bool readably) const
+{
+ return readably ? escapedValue() : value();
+}
+
+String malVector::print(bool readably) const
+{
+ return '[' + malSequence::print(readably) + ']';
+}
--- /dev/null
+#ifndef INCLUDE_TYPES_H
+#define INCLUDE_TYPES_H
+
+#include "MAL.h"
+
+#include <exception>
+#include <map>
+
+#define ARRAY_SIZE(a) (sizeof(a)/(sizeof(*(a))))
+
+class malEmptyInputException : public std::exception { };
+
+class malValue : public RefCounted {
+public:
+ malValue() {
+ TRACE_OBJECT("Creating malValue %p\n", this);
+ }
+ virtual ~malValue() {
+ TRACE_OBJECT("Destroying malValue %p\n", this);
+ }
+
+ virtual String print(bool readably) const = 0;
+};
+
+class malConstant : public malValue {
+public:
+ malConstant(String name) : m_name(name) { }
+
+ virtual String print(bool readably) const { return m_name; }
+
+private:
+ const String m_name;
+};
+
+class malInteger : public malValue {
+public:
+ malInteger(int value) : m_value(value) { }
+
+ virtual String print(bool readably) const {
+ return std::to_string(m_value);
+ }
+
+private:
+ const int m_value;
+};
+
+class malStringBase : public malValue {
+public:
+ malStringBase(const String& token)
+ : m_value(token) { }
+
+ virtual String print(bool readably) const { return m_value; }
+
+ String value() const { return m_value; }
+
+private:
+ const String m_value;
+};
+
+class malString : public malStringBase {
+public:
+ malString(const String& token)
+ : malStringBase(token) { }
+
+ virtual String print(bool readably) const;
+
+ String escapedValue() const;
+};
+
+class malKeyword : public malStringBase {
+public:
+ malKeyword(const String& token)
+ : malStringBase(token) { }
+};
+
+class malSymbol : public malStringBase {
+public:
+ malSymbol(const String& token)
+ : malStringBase(token) { }
+};
+
+class malSequence : public malValue {
+public:
+ malSequence(malValueVec* items);
+ virtual ~malSequence();
+
+ virtual String print(bool readably) const;
+
+private:
+ malValueVec* const m_items;
+};
+
+class malList : public malSequence {
+public:
+ malList(malValueVec* items) : malSequence(items) { }
+
+ virtual String print(bool readably) const;
+};
+
+class malVector : public malSequence {
+public:
+ malVector(malValueVec* items) : malSequence(items) { }
+
+ virtual String print(bool readably) const;
+};
+
+class malHash : public malValue {
+public:
+ typedef std::map<String, malValuePtr> Map;
+
+ malHash(malValueVec* items);
+
+ virtual String print(bool readably) const;
+
+private:
+ const Map m_map;
+};
+
+namespace mal {
+ malValuePtr falseValue();
+ malValuePtr hash(malValueVec* items);
+ malValuePtr integer(int value);
+ malValuePtr integer(const String& token);
+ malValuePtr keyword(const String& token);
+ malValuePtr list(malValueVec* items);
+ malValuePtr list(malValuePtr a);
+ malValuePtr list(malValuePtr a, malValuePtr b);
+ malValuePtr list(malValuePtr a, malValuePtr b, malValuePtr c);
+ malValuePtr nilValue();
+ malValuePtr string(const String& token);
+ malValuePtr symbol(const String& token);
+ malValuePtr trueValue();
+ malValuePtr vector(malValueVec* items);
+};
+
+#endif // INCLUDE_TYPES_H
--- /dev/null
+#ifndef INCLUDE_VALIDATION_H
+#define INCLUDE_VALIDATION_H
+
+#include "String.h"
+
+#define ASSERT(condition, ...) \
+ if (!(condition)) { throw STRF(__VA_ARGS__); } else { }
+
+#endif // INCLUDE_VALIDATION_H
--- /dev/null
+#include "MAL.h"
+
+#include "ReadLine.h"
+#include "Types.h"
+
+#include <iostream>
+#include <memory>
+
+malValuePtr READ(const String& input);
+String PRINT(malValuePtr ast);
+
+static ReadLine s_readLine("~/.mal-history");
+
+int main(int argc, char* argv[])
+{
+ String prompt = "user> ";
+ String input;
+ while (s_readLine.get(prompt, input)) {
+ String out;
+ try {
+ out = rep(input);
+ }
+ catch (malEmptyInputException&) {
+ continue; // no output
+ }
+ catch (String& s) {
+ out = s;
+ };
+ std::cout << out << "\n";
+ }
+ return 0;
+}
+
+String rep(const String& input)
+{
+ return PRINT(EVAL(READ(input)));
+}
+
+malValuePtr READ(const String& input)
+{
+ return readStr(input);
+}
+
+malValuePtr EVAL(malValuePtr ast)
+{
+ return ast;
+}
+
+String PRINT(malValuePtr ast)
+{
+ return ast->print(true);
+}