OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 9:26 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: reading s-expressions - problem with improper lists
PostPosted: Fri Sep 02, 2022 9:46 pm 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1925
Location: Athens, GA, USA
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:
(foo bar . quux)

In the test results, it is coming out as simply
Code:
(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:
#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:
#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:
#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:
    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;
    }

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: reading s-expressions - problem with improper lists
PostPosted: Fri Sep 02, 2022 10:52 pm 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1925
Location: Athens, GA, USA
Oh, I forgot the test output:
Code:
$ 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!

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: reading s-expressions - problem with improper lists
PostPosted: Sat Sep 03, 2022 10:22 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1925
Location: Athens, GA, USA
I did get that one problem fixed, but now I am creating additional test cases and finding new issues. So it goes.

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 27 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group