reading s-expressions - problem with improper lists

[Schol-R-LEA]

I am writing the (rather simplistic) reader code for `L, and have managed to get it working in all of the tests I've written, except for one: the case of an improper list (a Lisp list in which the last pair is a an ordered pair - that is to say, the CDR of the last pair is an atom rather than a null pointer) with more than two members, such as

Code: Select all

(foo bar . quux)

In the test results, it is coming out as simply

Code: Select all

(foo bar   quux)

While this is a minor issue, it is still something I would like to resolve, and getting more eyes on a problem is always a good idea.

Code: Select all

#ifndef ATOM_H
#define ATOM_H

#include <string>
#include <cstdint>


class Atom
{
public:
    Atom() {};
    virtual ~Atom() {};
    virtual std::string to_string() {return "";};
};


class Symbol: public Atom
{
private:
    std::string literal;


public:
    Symbol(std::string s): literal(s) {};
    std::string value() {return literal;};
    virtual std::string to_string() {return literal;};
};

class Dot: public Atom
{
private:

public:
    Dot() {};
};


class RightParen: public Atom
{
private:

public:
    RightParen() {};
};


class Number: public Atom
{
private:

public:
    Number() {};
};


class Integer64: public Number
{
private:
    long long literal;
public:
    Integer64(long long i): literal(i) {};
    long long value() {return literal;};
    virtual std::string to_string() {return std::to_string(literal);};
};


class FP_Double: public Number
{
private:
    double literal;
public:
    FP_Double(double i): literal(i) {};
    double value() {return literal;};
    virtual std::string to_string() {return std::to_string(literal);};
};


class Pair: public Atom
{
protected:
    Atom *car, *cdr;
public:
    Pair(): car(nullptr), cdr(nullptr) {};
    Pair(Atom* head): car(head), cdr(nullptr) {};
    Pair(Atom* head, Atom* tail): car(head), cdr(tail) {};
    virtual ~Pair();
    virtual std::string to_string();
    void set_car(Atom* a) {car = a;};
    void set_cdr(Atom* a) {cdr = a;};
    Atom* get_car() {return car;};
    Atom* get_cdr() {return cdr;};
};

#endif

Code: Select all

#include <iostream>
#include <string>
#include <typeinfo>
#include "atom.h"

Pair::~Pair()
{
    if (car != nullptr)
    {
        delete car;
        car = nullptr;
    }
    if (cdr != nullptr)
    {
        delete cdr;
        cdr = nullptr;
    }
}


std::string to_string_list_helper(Pair *p)
{

    std::string midpoint = " . ";

    if (p == nullptr)
    {
        return "";
    }

    if (p->get_car() == nullptr)
    {
        if (p->get_cdr() == nullptr)
        {
            return "";
        }
        else
        {
            return "()" + midpoint + p->get_cdr()->to_string();
        }
    }
    else if (p->get_cdr() == nullptr)
    {
        return p->get_car()->to_string();
    }
    else
    {
        if (typeid(*(p->get_cdr())) == typeid(Pair))
        {
            return p->get_car()->to_string()
                   + " " + to_string_list_helper(dynamic_cast<Pair *>(p->get_cdr()));
        }
        else
        {
            return p->get_car()->to_string() + midpoint + p->get_cdr()->to_string();
        }
    }
}


std::string Pair::to_string()
{
    return "(" + to_string_list_helper(dynamic_cast<Pair *>(this)) + ")";
}

Code: Select all

#include <fstream>
#include <ios>
#include <iostream>
#include <string>
#include <sstream>
#include <typeinfo>
#include "atom.h"
#include "read.h"


void read_src_file(std::stringstream& src, std::ifstream& src_file)
{
    while (src_file)
    {
        src << src_file.rdbuf();
    }
}



Atom* read_expression(std::stringstream& src)
{
    if (src.eof())
    {
        throw new unexpected_end_of_file_exception();
    }

    char ch;
    src >> ch;

    if (std::iswspace(ch))
    {
        return read_expression(src);
    }
    else if (ch == '.')
    {
        return new Dot();
    }
    else if (ch == '(')
    {
        return read_list(src);
    }
    else if (ch == ')')
    {
        return new RightParen();
    }
    else if (std::isdigit(ch))
    {
        return read_number(ch, src);
    }
    else
    {
        return (read_symbol(ch, src));
    }
}


Atom* read_list(std::stringstream& src)
{
    Atom* head = read_expression(src);

    if (head == nullptr)
    {
        return nullptr;
    }

    if(typeid(*head) == typeid(RightParen))
    {
        return nullptr;
    }

    Atom* tail = read_expression(src);

    if (typeid(*tail) == typeid(Dot))
    {
        return new Pair(head, read_expression(src));
    }
    else if(typeid(*tail) == typeid(RightParen))
    {
        return new Pair(head);
    }
    else
    {
        return new Pair(head, new Pair(tail, read_list(src)));
    }
}



Atom* read_symbol(char start_ch, std::stringstream& src)
{
    char ch = start_ch;
    std::string ostr = "";

    while (!src.eof())
    {
        ostr += ch;
        char temp = src.peek();

        if (std::iswspace(temp) || temp == '(' || temp == ')')
        {
            break;
        }
        src >> ch;
    }
    return new Symbol(ostr);
}



Atom* read_number(char start_ch, std::stringstream& src)
{
    char ch = start_ch;
    std::string ostr = "";
    bool fp = false;

    while (!src.eof())
    {
        if (ch == '.')
        {
            if (fp)
            {
                throw new invalid_numeric_value_exception();
            }
            else
            {
                fp = true;
            }
        }
        ostr += ch;
        char temp = src.peek();
        if (std::isdigit(temp) || temp == '.')
        {
            src >> ch;
        }
        else
        {
            break;
        }
    }

    if (fp)
    {
        return new FP_Double(std::strtod(ostr.c_str(), nullptr));
    }
    else
    {
        return new Integer64(std::strtol(ostr.c_str(), nullptr, 10));
    }
}

The Doctest test in question is:

Code: Select all

    TEST_CASE("improper list of three elements")
    {
        std::stringstream src;
        src << "(foo bar . quux)";
        Atom* test = read_expression(src);
        Pair* test_list = dynamic_cast<Pair*>(test);
        CHECK(typeid(*(test_list->get_car())) == typeid(Symbol));
        Symbol* test_car = dynamic_cast<Symbol*>(test_list->get_car());
        CHECK(test_car->value() == "foo");
        CHECK(typeid(*(test_list->get_cdr())) == typeid(Pair));
        Pair* test_cdr = dynamic_cast<Pair*>(test_list->get_cdr());
        Atom* test_cadr = test_cdr->get_car();
        CHECK(typeid(*test_cadr) == typeid(Symbol));
        Symbol* test_symbol = dynamic_cast<Symbol*>(test_cadr);
        CHECK(test_symbol->value() == "bar");
        Atom* test_cddr = test_cdr->get_cdr();
        test_symbol = dynamic_cast<Symbol*>(test_cddr);
        std::cout << typeid(*test_cddr).name() << std::endl;
        CHECK(typeid(*test_cddr) == typeid(Symbol));
        CHECK(test->to_string() == "(foo bar . quux)");
        delete test;
    }

[Schol-R-LEA]

Oh, I forgot the test output:

Code: Select all

$ bin/test-expr-reading 
[doctest] doctest version is "2.4.9"
[doctest] run with "--help" for options
4Pair
===============================================================================
tests/test-expr-reading.cpp:274:
TEST SUITE: reading s-expressions and converting them to strings
TEST CASE:  improper list of three elements

tests/test-expr-reading.cpp:291: ERROR: CHECK( typeid(*test_cddr) == typeid(Symbol) ) is NOT correct!
  values: CHECK( {?} == {?} )

tests/test-expr-reading.cpp:294: ERROR: CHECK( test->to_string() == "(foo bar . quux)" ) is NOT correct!
  values: CHECK( (foo bar  quux) == (foo bar . quux) )

===============================================================================
[doctest] test cases: 25 | 24 passed | 1 failed | 0 skipped
[doctest] assertions: 73 | 71 passed | 2 failed |
[doctest] Status: FAILURE!

[Schol-R-LEA]

I did get that one problem fixed, but now I am creating additional test cases and finding new issues. So it goes.