My solution to Christopher Pisz' bobbleboard, in new dialect Expressive C++

[Alf P. Steinbach]

I took the fun-with-macros idea all the way to /a new dialect of/ C++,
with much of the operator notation replaced with readable words.

¹Tentative name: “Expressive C++”.

The macros, which serve as pseudo keywords, all start with `$`, which is
not valid in standard C++.

I therefore believe that this logical namespace is entirely unused, as
of yet, but strangely it is supported by the major compilers such as
g++, Visual C++ and clang. That is, they all support using `$` in
identifiers. I couldn't resist trying to use the feature.

This code requires compiler support also for some other language
extensions that I believe are present in both g++, Visual C++ and clang:

• `$` in names.
• `#pragma once`.
• `#pragma push_macro` and `#pragma pop_macro`.

The latter two pragmas are for use of the extended language in headers
without imposing those macros on client code.

• • •

The below code for Christopher's bobble-board word generation problem is
a rewrite of the pure C++11 solution that I posted earlier and does not
include any of the Expressive C++ machinery. The machinery is quite a
bit, so best discussed in small pieces. But for now: `$fail`, which
throws an exception, adds the qualified function name at the start of
the exception message (nice touch, if I may say so myself), and
$start_with_arguments at the bottom of the code, invokes the specified
function with the `main` arguments, catches any exception, and reports
the exception message on the narrow standard error stream.

Also worth noting up front, `$items_of` is so dirty that I haven't had
the courage to include it in the Expressive set of macros. It's defined
at the top of the source file. However, while dirty, it's delicious.

[code]
#include <p/expressive/all.hpp>
$using_all_from_namespace( progrock::expressive );

#include <algorithm> // std::(is_sorted, remove, sort, transform)
#include <assert.h> // assert
#include <ctype.h> // tolower
#include <fstream> // std::ifstream
#include <iostream>
#include <iterator> // std::(begin, end)
#include <vector> // std::vector
#include <string > // std::string

#define $items_of( collection ) std::begin( collection ), std::end(
collection )

namespace cppx {
$using_from_namespace( std, ostream, vector, runtime_error, string );

struct Position
{
Index x;
Index y;
};

inline $function operator<<( ref_<ostream> stream, ref_<const
Position> pos )
-> ref_<ostream>
{ return stream << "{" << pos.x << ", " << pos.y << "}"; }

template< class Item >
class Matrix
{
private:
struct Wrapped_item { Item object; }; // Avoid problems
with vector<bool>.

Size row_length_;
vector<Wrapped_item> items_;

$function index_for( Index x, Index y ) const
-> Index
{ return y*row_length_ + x; }

public:
$function size() const
-> Size
{ return row_length_; }

$function item( const Index x, const Index y ) const
-> Item
{ return items_[index_for( x, y )].object; }

$function item( const Index x, const Index y )
-> Item&
{ return items_[index_for( x, y )].object; }

Matrix(): Matrix{ 0 } {}

explicit Matrix( const Size size )
: row_length_( size )
, items_( size*size )
{}

};

inline $function to_lowercase( const char ch )
-> char
{ return $as<char>( tolower( $as<Byte>( ch ) ) ); }

inline $function starts_with( ref_<const string> prefix, ref_<const
string> s )
-> bool
{ return s.substr( 0, prefix.length() ) == prefix; }

} // namespace cppx

namespace app {
$using_all_from_namespace( std );
$using_all_from_namespace( cppx );

$function load_dictionary( ref_<const string> file_path )
-> vector<string>
{
ifstream data{ file_path };
$hopefully( not data.fail() )
or $fail( "Failed to open dictionary `" + file_path + "`." );

vector<string> result;
string word;
while( getline( data, word ) )
{
result.push_back( move( word ) );
}
return result;
}

$function chars_from( string s )
-> string
{
$let end_of_nonspaces = remove( $items_of( s ), ' ' );
string chars{ begin( s ), end_of_nonspaces };
transform( $items_of( chars ), begin( chars ), to_lowercase );
return chars;
}

$function load_bubble_board( ref_<const string> file_path )
-> Matrix<char>
{
ifstream data{ file_path };
$hopefully( not data.fail() )
or $fail( "Failed to open dictionary `" + file_path + "`." );

string line;
string chars; // Whitespace removed.
getline( data, line )
or fail( "Unable to read first line of `" + file_path + "`." );
chars = chars_from( line );
$let n = n_items_in( chars );
Matrix<char> result{ 2 + n };
for( Index x = 0; x < n; ++x ) { result.item( x + 1, 1 ) =
chars[x]; }
for( Index y = 1; y < n; ++y )
{
getline( data, line )
or $fail( "Unable to read line " + to_string( y + 1 ) +
" of `" + file_path + "`." );
chars = chars_from( line );
hopefully( n_items_in( chars ) == n )
or $fail( "Inconsistent row lengths in board data `" +
file_path + "`" );
for( Index x = 0; x < n; ++x ) { result.item( x + 1, y + 1
) = chars[x]; }
}
return result;
}

using Dictionary_iter = vector<string>::const_iterator;

$procedure recursively_append_words_from(
const Dictionary_iter start_dict_range,
const Dictionary_iter end_dict_range,
ref_<const Matrix<char>> chars,
const Position position,
ref_<Matrix<bool>> visited,
ref_<string> word,
ref_<vector<string>> result
)
{
$let original_word_length = word.length();
$let ch = chars.item( position.x, position.y );
if( ch == 'q' ) { word += "qu"; } else { word += ch; }
$let it_dict_entry = lower_bound( start_dict_range,
end_dict_range, word );

if( starts_with( word, *it_dict_entry ) )
{
$let length = word.length();
if( length >= 3 and length == it_dict_entry->length() )
{
result.push_back( word );
}
visited.item( position.x, position.y ) = true;
for( $each dy $in range( -1, +1 ) ) for( $each dx $in
range( -1, +1 ) )
{
Position const new_position = {position.x + dx,
position.y + dy};
if( not visited.item( new_position.x, new_position.y ) )
{
recursively_append_words_from(
it_dict_entry, end_dict_range, chars, new_position,
visited, word, result
);
}
}
visited.item( position.x, position.y ) = false;
}
word.resize( original_word_length );
}

$procedure append_words_from(
ref_<const vector<string>> dictionary,
ref_<const Matrix<char>> chars,
ref_<const Position> start,
ref_<vector<string>> result
)
{
string word;
$let n = chars.size();
Matrix<bool> visited{ n };

for( $each i $in i_up_to( n ) )
{
visited.item( i, 0 ) = true;
visited.item( 0, i ) = true;
visited.item( i, n - 1 ) = true;
visited.item( n - 1, i ) = true;
}

recursively_append_words_from(
$items_of( dictionary ), chars, start,
visited, word, result
);
}

$procedure cpp_main( ref_<const vector<string>> args )
{
$hopefully( n_items_in( args ) == 3 )
or $fail( "Usage: " + args[0] + " DICTIONARY BUBBLEBOARD" );

vector<string> const dictionary = load_dictionary( args[1] );
Matrix<char> const board = load_bubble_board( args[2] );

assert( is_sorted( $items_of( dictionary ) ) );
$let n = board.size();
vector<string> words;
for( $each y $in i_up_to( n ) ) for( $each x $in i_up_to( n ) )
{
append_words_from( dictionary, board, {x + 1, y + 1}, words );
}

sort( $items_of( words ) );
$let start_of_duplicates = unique( $items_of( words ) );
words.erase( start_of_duplicates, end( words ) );
for( $each word $in words )
{
cout << word << "\n";
}
}
} // namespace app

$start_with_arguments( app::cpp_main )
[/code]


• • •

The above code, plus the supporting machinery not shown here, was
compiled with MinGW g++ 6.3.0 and Visual C++ 2015 update 2.

I haven't tried clang, but as I think clang requires an option in order
to not warn about use of `$` in names.

Cheers!,

- Alf

Notes:
¹ I am aware that the name “Expressive C++” and its natural
abbreviations have been used for various things. E.g. “EC++” was/is (?)
a standard for limited C++ on embedded devices. “XC++” is some
mysterious Japanese C++ library project on SourceForge. And Eric
Niebler, author of the C++20 ranges library, has written something he's
called the Expressive C++ Series, but I don't know what that was.

[Alf P. Steinbach]

Oh, I forgot to fix the loops at the end there, to Expressive syntax:

$function load_bubble_board( ref_<const string> file_path )
-> Matrix<char>
{
ifstream data{ file_path };
$hopefully( not data.fail() )
or $fail( "Failed to open dictionary `" + file_path + "`." );

string line;
string chars; // Whitespace removed.
getline( data, line )
or fail( "Unable to read first line of `" + file_path + "`." );
chars = chars_from( line );
$let n = n_items_in( chars );
Matrix<char> result{ 2 + n };

for( $each x $in i_up_to( n ) ) { result.item( x + 1, 1 ) =
chars[x]; }
for( $each y $in range( 1, n - 1 ) )

{
getline( data, line )
or $fail( "Unable to read line " + to_string( y + 1 ) +
" of `" + file_path + "`." );
chars = chars_from( line );
hopefully( n_items_in( chars ) == n )
or $fail( "Inconsistent row lengths in board data `" +
file_path + "`" );

for( $each x $in i_up_to( n ) ) { result.item( x + 1, y + 1

) = chars[x]; }
}
return result;
}

As I recall from some years ago the generated machine code is the same.

So, this way of writing simple counting loops can be freely adopted even
without the Expressive `$`-keywords.


Cheers!,

- Alf