4
\$\begingroup\$

I've been starting to migrate some C++ code from imperative to more of a functional style. I'm new to functional programming so I'm trying to get a sense of how well this code fits into the functional programming paradigm.

The purpose of the code is to scan tokens from CSV files, and currently passes all the written tests I have.

Here's the header.

#pragma once

#include <cstddef>

/// Enumerates the several types of CSV tokens.
enum class csvTokenType {
  /// A null token.
  Null,
  /// A newline sequence.
  Newline,
  /// A separator character.
  Separator,
  /// A quoted cell.
  QuotedCell,
  /// An unquoted cell.
  UnquotedCell
};

/// Contains data belonging to a token.
class csvToken final {
  /// The type of this token.
  csvTokenType type;
  /// The character data belonging to the token.
  const char* data;
  /// The number of characters in the token.
  size_t size;
public:
  /// Constructs a null token.
  csvToken() noexcept : type(csvTokenType::Null), data(""), size(0) { }
  /// Constructs a CSV token.
  /// @param t The type to assign the token.
  /// @param d The data to assign the token.
  /// @param s The size of the data being assigned to the token.
  csvToken(csvTokenType t, const char* d, size_t s) noexcept : type(t), data(d), size(s) { }
  /// Indicates if this is a valid token or not.
  /// @returns True if it's a valid token, false otherwise.
  operator bool () const noexcept {
    return type != csvTokenType::Null;
  }
  /// Checks for token type equality.
  /// @param otherType The type of token to check for.
  /// @returns True if the types are equal, false otherwise.
  bool operator == (csvTokenType otherType) const noexcept {
    return type == otherType;
  }
  /// Checks for equality with string data.
  /// @param str The string to check.
  /// @returns True if the strings are equal, false otherwise.
  bool operator == (const char* str) const noexcept;
};

/// Scans for a token.
/// @param data The data to scan.
/// @param size The size of the data to scan.
/// @returns The resultant token.
csvToken csvScan(const char* data, size_t size) noexcept;

Here's the implementation.

#include "csvScan.hpp"

#include <algorithm>

#include <string.h>

namespace {

/// A simple class for quick and safe
/// string scanning.
struct csvStringView final {
  /// The string data.
  const char* data;
  /// The size of the string.
  size_t size;
  /// Constructs the string view.
  csvStringView(const char* d, size_t s) noexcept : data(d), size(s) { }
  /// Gets a character at a specified offset.
  /// @param i The offset of the character to get.
  /// @returns The character at the specified offset.
  /// If the offset is out of bounds, then zero is returned instead.
  char operator [] (size_t i) const noexcept {
    return (i < size) ? data[i] : 0;
  }
  /// Returns a beginning iterator.
  /// @returns The beginning iterator.
  const char* begin() const noexcept {
    return data;
  }
  /// Returns the ending iterator.
  /// @returns The ending iterator.
  const char* end() const noexcept {
    return data + size;
  }
};

/// Returns the first non-null token
/// generated by one of the functions in the parameter list.
/// @tparam FirstMatcher The type of the first callable token scanner.
/// @tparam OtherMatchers The type of the other callable token scanners.
/// @param strView The string view to scan.
/// @param firstMatcher The first token scanner.
/// @param otherMatchers The other token scanners.
/// @returns The first non-null token from the given matchers.
template <typename FirstMatcher, typename... OtherMatchers>
csvToken csvFirstMatch(const csvStringView& strView, FirstMatcher firstMatcher, OtherMatchers... otherMatchers) {

  auto token = firstMatcher(strView);

  return token ? token : csvFirstMatch(strView, otherMatchers...);
}

/// The last resort matching function.
/// @tparam LastMatcher The type of the last token matcher.
/// @param strView The string view being scanned.
/// @param lastMatcher The last token matcher.
/// @returns The resultant token.
template <typename LastMatcher>
csvToken csvFirstMatch(const csvStringView& strView, LastMatcher lastMatcher) {
  return lastMatcher(strView);
}

/// Indicates if a character is
/// a separator or not.
/// @param c The character to check.
/// @returns True if the character is
/// a separator, false if it is not.
bool csvIsSeparator(char c) noexcept {
  return (c == ',') || (c == ';') || (c == '\t');
}

/// Indicates if the specified character
/// can be part of a newline sequence.
/// @param c The character to check.
/// @returns True if the character can
/// be part of a newline sequence, false otherwise.
bool csvIsNewline(char c) noexcept {
  return (c == '\n') || (c == '\r');
}

/// Indicates if the specified
/// character can terminate an unquoted cell.
/// @param c The character to check.
/// @returns True if the character can terminate
/// the call, false otherwise.
bool csvIsCellTerminal(char c) noexcept {
  return csvIsSeparator(c) || csvIsNewline(c);
}

/// Attempts to scan a separator character.
/// @param strView The string view to scan.
/// @returns The resultant token.
csvToken csvScanSeparator(const csvStringView& strView) noexcept {

  bool match = csvIsSeparator(strView[0]);

  csvToken goodToken(csvTokenType::Separator, strView.data, 1);

  return match ? goodToken : csvToken();
}

/// Attempts to scan a line feed.
/// @param strView The string being scanned.
/// @returns The resultant token.
csvToken csvScanLF(const csvStringView& strView) noexcept {

  csvToken goodToken(csvTokenType::Newline, strView.data, 1);

  auto match = (strView[0] == '\n');

  return match ? goodToken : csvToken();
}

/// Attempts to scan a line feed.
/// @param strView The string being scanned.
/// @returns The resultant token.
csvToken csvScanCRLF(const csvStringView& strView) noexcept {

  csvToken goodToken(csvTokenType::Newline, strView.data, 2);

  auto match = (strView[0] == '\r') && (strView[1] == '\n');

  return match ? goodToken : csvToken();
}

/// Attempts to scan any known newline sequence.
/// @param strView The string being scanned.
/// @returns The resultant token.
csvToken csvScanNewline(const csvStringView& strView) noexcept {
  return csvFirstMatch(strView, csvScanCRLF, csvScanLF);
}

/// Scans the contents of an unquoted cell.
/// @param strView The string view to scan.
/// @returns The resultant token.
csvToken csvScanUnquotedCell(const csvStringView& strView) noexcept {

  const auto* it = std::find_if(strView.begin(), strView.end(), csvIsCellTerminal);

  auto match = (it != strView.end());

  csvToken goodToken(csvTokenType::UnquotedCell, strView.begin(), it - strView.begin());

  return match ? goodToken : csvToken();
}

/// Scans a string view.
/// @param strView The string view to scan.
/// @returns The resultant token.
csvToken csvScan(const csvStringView& strView) noexcept {
  return csvFirstMatch(strView, csvScanSeparator, csvScanNewline, csvScanUnquotedCell);
}

} // namespace

bool csvToken::operator == (const char* str) const noexcept {

  size_t strSize = strlen(str);

  return (size == strSize) && (memcmp(str, data, strSize) == 0);
}

csvToken csvScan(const char* data, size_t size) noexcept {

  csvStringView strView(data, size);

  return csvScan(strView);
}
\$\endgroup\$
  • \$\begingroup\$ A usage example would be nice. \$\endgroup\$ – Martin York Jul 11 at 16:37
2
\$\begingroup\$

Your code isn't functional, neither in the sense of working properly, nor in the sense of respecting the principles of functional programming.

To parse a file, you need a way to consume the file. How would you do it with your function?

csvStringView fh = readFile(filepath.csv);
csvToken tok = csvFirstMatch(fh); 
// ???

You could imagine to compute a new string_view from the token length:

// ...
auto fh2 = remove_prefix(fh, tok.length);
csvToken tok2 = csvFirstMatch(fh2);

But you'll need to do it an unspecified number of times. So either you do this in a loop, but a loop isn't functional, or you muscle-up your parsing function to return not only the token, but also the stream:

std::pair<Token, std::string_view> parse_token(std::string_view stream);

That's well and good, but once you consider it, you realize you need to take up a new challenge: how will you chain or compose in any way two calls to parse_token if the return type isn't the same as the argument type?

The answer is actually quite obvious since we're talking about functional programming: you need a function to do that. Let's say we want to combine several parsers in an either/or way. We have a parse_quoted_cell and parse_unquoted_cell for instance and want to have the result of the fitting one:

auto parse_result = parse_quoted_cell(stream);
if (parse_result.first.type == Token::failure)
    return parse_unquoted_cell(stream);
return parse_result;

That can be easily generalized:

using Parse_result = std::pair<Token, Stream>;
using Parser = std::function<Parse_result(Stream)>;

Parser either_or(Parser f, Parser s) {
    return [f,s](Stream s) {
        auto res = f(stream);
        if (res.first.type == Token::failure) return s(stream);
        return res;
    };
}

"Either / or" isn't the only composition type you need. There's also an "and then". For instance, to parse a cell, you need to either parse a quoted or an unquoted cell, but also either a separator or the end of file. How would you do that? With a function, of course, and it would look like this:

Parser and_then(Parser f, Parser s) {
    return [f,s](Stream s) {
        auto res = f(stream);
        if (res.first.type == Token::failure) return res;
        auto res2 = s(res.second);
        return Parse_result(combine(res.first, res2.first), res2.second);
    };
}

Now we can create our cell parser from our building blocks:

Parser parse_cell = and_then(either_or(parse_quoted_cell, parse_unquoted_cell),
                             either_or(parse_separator, parse_eof));

It is rather interesting to see that parse_quoted_cell can itself be built from other building blocks:

Parser parse_quoted_cell = and_then(and_then(parse_quote, parse_unquoted_cell),
                                    parse_quote);

There are many cases where the same parser must be applied an unknown number of times. For instance, to parse the whole file, parse_cell should be applied repeatedly, until the end of file:

Parser parse_file = repeat(parse_cell);

where repeat can be defined recursively:

Parser repeat(Parser p) {
     return [p](Stream s) {
        auto res = p(stream);
        if (res.first.type == Token::failure) return res;
        auto res2 = repeat(p)(res.second);
        return Parse_result(combine(res.first, res2.first), res2.second);
    };
}

I admit that I didn't review your code in detail, but I feel like you should think the whole thing through again and then submit a revised program for a more detailed review.

\$\endgroup\$
  • \$\begingroup\$ Parsing a quoted cell can't be done the way you described it because different characters are allowed in a quoted cell then in a non quoted one. I'll revise and post again once it's done, thanks! \$\endgroup\$ – tay10r Jul 11 at 11:55
  • \$\begingroup\$ @tay10r: you're right, I've over-simplified the csv part. I think the functional canvas is still valid though. \$\endgroup\$ – papagaga Jul 11 at 12:14
  • \$\begingroup\$ @papagada yeah you had some good feedback. I didn't plan on making the parser functional, hence the scan function being designed that way. Now though I'm kind of thinking on giving it a shot. Thanks for your feedback! \$\endgroup\$ – tay10r Jul 11 at 12:19
  • \$\begingroup\$ After reading this a bit more closely, the only thing you suggested that I didn't already implement in the code that I posted is the recursive repeat function. The either_or and and_then are implemented by the csvFirstMatch function. I don't think I would ever recursively parse a file, because doing that with a large enough CSV file would cause a stackoverflow. \$\endgroup\$ – tay10r Jul 11 at 14:15
  • \$\begingroup\$ @tay10r: either_or and and_then can't be implemented inside a function, because their purpose is to compose functions into new, more powerful functions. But even that is besides the main point: you need a way to consume the file progressively, and the only way to do it functionally is to return the partially consumed file along with the parsed token. And there's no way around recursive parsing either if you want to keep your program functional. But it's perfectly respectable no to commit to functional programming \$\endgroup\$ – papagaga Jul 11 at 14:49
1
\$\begingroup\$

A small observation on the includes and namespaces:

We have #include <cstddef>, but then use size_t in the global namespace, which is not portable according to the standard. We should be using std::size_t instead.

In the other file, we include the C compatibility header <string.h> - prefer to include <cstring> in new code, so that the names are available unambiguously in the std namespace (e.g. std::memcmp).

\$\endgroup\$
  • \$\begingroup\$ Interesting, I didn't know size_t to not be portable in the global namespace. I was more looking to see how this code does in a functional paradigm but I'm glad you pointed this out! \$\endgroup\$ – tay10r Jul 11 at 11:57
  • \$\begingroup\$ @tay10r If you include <stdef.h> then size_t is in the global namespace (and may be in standard). If you include <cstddef> then size_t is in standard (and may by in the global namespace). Basically if you use the C++ header files the wrap the C standard library all the types are placed in the standard namespace. If you use the C language headers this has no concept of namespaces and thus places them in global scope. Note: The implications from this are that when writting C++ you should use the C++ header files and use the version that is in the standard namespace. \$\endgroup\$ – Martin York Jul 11 at 16:34
0
\$\begingroup\$

My main observation is that there seem to be a lot of free standing functions:

csvToken csvFirstMatch(const csvStringView& strView, FirstMatcher firstMatcher, OtherMatchers... otherMatchers)
csvToken csvFirstMatch(const csvStringView& strView, LastMatcher lastMatcher)
bool csvIsNewline(char c) noexcept
bool csvIsCellTerminal(char c) noexcept
csvToken csvScanSeparator(const csvStringView& strView) noexcept
csvToken csvScanLF(const csvStringView& strView) noexcept
csvToken csvScanCRLF(const csvStringView& strView) noexcept
csvToken csvScanNewline(const csvStringView& strView) noexcept
csvToken csvScanUnquotedCell(const csvStringView& strView) noexcept
csvToken csvScan(const csvStringView& strView) noexcept

And three classes

enum class csvTokenType
class csvToken final
struct csvStringView final

But it does not spring out at my how to use this.
Personally I would like to see something like:

CSVFile   file("FileName");
for(auto loop = file.begin(); loop != file.end(); ++loop) {
    // loop is now an iterator to a token.
}

// If you can do that with C++11
// Then the simpler syntax for C++14 make it easier:

CSVString  data(stringLoadedFromASourceThatIsNotAFile);
for(auto const& token: data) {
    // token is now a reference to the next token in the loop.
}
\$\endgroup\$
  • \$\begingroup\$ What's your point about free standing functions? The suggestions you made are confusing. What is being iterated in CSVFile? Is the the rows or columns? Anyone reading that is not going to know what's going on, especially since you named the iterator loop instead of something more standard (like it). \$\endgroup\$ – tay10r Jul 11 at 21:58
  • \$\begingroup\$ -1 because the code you suggested makes the style more imperative instead of functional. I clearly stated in the post that I wanted to know how well my code fits into the functional paradigm. \$\endgroup\$ – tay10r Jul 11 at 22:01
  • \$\begingroup\$ @tay10r Sad :-( The -1 will affect my score. Sorry you did not understand my review of your code. I'll refrain from further updates. \$\endgroup\$ – Martin York Jul 11 at 23:36
  • \$\begingroup\$ @MartinYork Apparently the OP doesn't know what functional means at all, so +1 to compensate :) \$\endgroup\$ – L. F. Jul 16 at 0:27
  • \$\begingroup\$ @tay10r Functional programming never means more functions. This post is helping you make your code more functional. \$\endgroup\$ – L. F. Jul 16 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.