tag:blogger.com,1999:blog-139608852024-03-17T01:21:52.385-07:00C++ TruthsA C++ blog on intermediate to advanced topics in C++ programming language features, standards, idioms, design patterns, and object-oriented programming in general.Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.comBlogger125125tag:blogger.com,1999:blog-13960885.post-39435846343678032472019-05-01T09:26:00.000-07:002019-05-25T17:32:42.297-07:00Bootstrapping a cmake project based on Hunter in Linux and Windows<div dir="ltr" style="text-align: left;" trbidi="on">
This is the third post in my exploration of the package managers for C++ in Linux and Windows environments. This time I tested out the Hunter package manager with the same toy C++ program with header-only boost-core and boost-optional and boost-filesystem (linking necessary) dependencies.
<br/><br/>
The previous blog posts in this series were about 1) <a href="http://cpptruths.blogspot.com/2019/03/bootstrapping-vcpkg-based-cmake-project.html">a simplistic use of vcpkg from cmake </a>and 2) a little more <a href="http://cpptruths.blogspot.com/2019/03/bootstrapping-vcpkg-based-cmake-project_31.html">sophisticated use of vcpkg with cmake</a>. The examples work for both Linux and Windows environments.
<h2>Recap</h2>
The following is a barebones C++ cmake project <code><a href="https://github.com/sutambe/cpptruths/tree/hunter_cmake_blog/cpp0x/hunter_test">hunter_test</a></code>
<pre class="brush:cpp">
hunter_test
├── CMakeLists.txt
├── include
│ └── driver.h
├── src
│ └── driver.cpp
└── test
└── driver_test.cpp
3 directories, 4 files
</pre>
The <code>driver.cpp</code> and <code>driver_test.cpp</code> files have just a main function that does nothing. <code>driver.h</code> is empty. The <code>CMakeLists.txt</code> looks as follows.
<pre class="brush:cmake">
cmake_minimum_required (VERSION 3.12)
project (vcpkg_test CXX)
set(CMAKE_CXX_STANDARD 17)
add_executable(driver src/driver.cpp)
target_include_directories(driver PUBLIC ${PROJECT_SOURCE_DIR}/include)
target_link_libraries(driver ${Boost_LIBRARIES})
enable_testing()
include(CTest)
add_executable(driver_test ${PROJECT_SOURCE_DIR}/test/driver_test.cpp)
add_test(NAME driver COMMAND driver_test)
</pre>
The <code>CMakeLists.txt</code> so far is independent of any package managers. Now, we'll start using Hunter.
<h2>Adding Hunter Package Manager to Your Cmake Project</h2>
This step is ridiculously simple. Hunter documentation provides <a href="https://docs.hunter.sh/en/latest/quick-start/boost-components.html">step-by-step instructions</a>. I really appreciate that.
<pre class="brush:cmake">
include("cmake/HunterGate.cmake")
HunterGate(URL "https://github.com/ruslo/hunter/archive/v0.23.165.tar.gz"
SHA1 "5a73f91df5f6109c0bb1104d0c0ee423f7bece79")
project (hunter_test CXX)
hunter_add_package(Boost COMPONENTS filesystem)
find_package(Boost 1.67 CONFIG REQUIRED COMPONENTS filesystem)
</pre>
Note that an additional cmake file <code>HunterGate.cmake</code> is added to the project. It lives under the <code>cmake</code> directory. It's the entry-point for Hunter. Including that file in our <code>CMakeLists.txt</code> allows us to call
<code>HunterGate</code> with a tar-ball for downloading the Hunter release. You can find the latest release URL and
SHA1 under <a href="https://github.com/ruslo/hunter/releases">ruslo/Hunter github releases</a>.
<br/><br/>
This is all that's needed to jumpstart the project in Linux environment. Invoking <code>cmake -B build</code> triggers Hunter in action. It downloads the necessary dependency sources and compiles them for you under <code>$HOME/.hunter</code>. As long as the code's include directives are following the best practices, the code will build smoothly. Specifically, I'm talking about the following two lines. Note the boost prefix.
<pre class="brush:cpp">
#include "boost/core/demangle.hpp"
#include "boost/filesystem.hpp"
</pre>
<h2>Hunter in Visual Studio 2019</h2>
There are two ways you can use Visual Studio with Hunter.
<br/><br/>
First, open the <code>CMakeLists.txt</code> in hunter_test in VS via File-->Open-->CMake...-->Select CMakeList.txt. This works but there's a caveat. The output of cmake is not redirected to the VS Build Output window immediately. In fact, it could take several minutes (or even hours). Obviously, it appears like VS is stuck. In the hunter_test project above with boost-core, boost-optional, and boost-filesystem dependencies, took about 21 minutes on my VM to finish the cmake generation step. This issue is tracked on the <a href="https://developercommunity.visualstudio.com/content/problem/555183/cmake-integration-output-mismatch-between-ide-and.html">VS Developer Community</a>.
<div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-JzIWXwideEw/XMscEOxIPRI/AAAAAAAAHPE/po9esDalOoUGVbBWN6NxozyFqDp_8r8oACLcBGAs/s1600/Screen%2BShot%2B2019-04-30%2Bat%2B8.12.03%2BPM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-JzIWXwideEw/XMscEOxIPRI/AAAAAAAAHPE/po9esDalOoUGVbBWN6NxozyFqDp_8r8oACLcBGAs/s1600/Screen%2BShot%2B2019-04-30%2Bat%2B8.12.03%2BPM.png" data-original-width="1117" data-original-height="857" /></a></div>
Recall that Hunter downloads dependency sources and builds them under the directory pointed by <code>$HUNTER_ROOT</code>. In my test runs, no output for this process was captured by Visual Studio. If Hunter fails to download and compile the sources for some dependencies, you might see some output.
<br/><br/>
I learned later that verbose cmake output can be enabled in Visual Studio. I found the output to be extra verbose due to %VSCMD_DEBUG% == 5.
<div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-GxJ09x5K1Zw/XOndlrr8mqI/AAAAAAAAHXU/mncYWkcdOp0HfbSfAzpbuQN5U_rm_dAfgCLcBGAs/s1600/enable-verbose-cmake-visual-studio.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-GxJ09x5K1Zw/XOndlrr8mqI/AAAAAAAAHXU/mncYWkcdOp0HfbSfAzpbuQN5U_rm_dAfgCLcBGAs/s1600/enable-verbose-cmake-visual-studio.jpg" data-original-width="547" data-original-height="309" /></a></div>
<h2>Classic Visual Studio Solution Generator</h2>
An alternative to Visual Studio's built-in cmake support is to use the classic solution file generator in cmake: <code>cmake -B build</code>. The generated solution file has the classic layout of various targets including ALL_BUILD, RUN_TESTS, ZERO_CHECK, and the main targets driver and driver_test. It builds fine. The tests run file. Here's the output of generating the build files.
<div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-rCuCqviam-0/XMhsgEhpNnI/AAAAAAAAHN0/mgXMI0p9FA8tUN50CZnPminotYxSfDcxwCLcBGAs/s1600/hunter-vs19-build.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-rCuCqviam-0/XMhsgEhpNnI/AAAAAAAAHN0/mgXMI0p9FA8tUN50CZnPminotYxSfDcxwCLcBGAs/s1600/hunter-vs19-build.png" data-original-width="979" data-original-height="472" /></a></div>
<h2>Conclusion</h2>
Visual Studio CMake integration works for Hunter-based projects. It has a few rough edges though. <strike>For now, you may be better off using cmake's native project generation for now rather than Visual Studio's "Open CMake Project" feature.</strike> You can still use the feature but remember that if one of your colleagues updates the HunterGate URL and SHA1 and if you open the project using the "Open CMake Project" feature, you might have to wait minutes to hours depending upon the number of dependencies rebuilt.
<br /></div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-54217437261485685012019-03-31T23:00:00.000-07:002019-05-01T09:29:44.504-07:00Bootstrapping a vcpkg-based project in Linux and Windows with idiomatic cmake<div dir="ltr" style="text-align: left;" trbidi="on">
This blog is part #2 in the series of trying out different package managers to bootstrap a cmake project. Checkout part #1 about <a href="http://cpptruths.blogspot.com/2019/03/bootstrapping-vcpkg-based-cmake-project.html">Bootstrapping a vcpkg-based cmake project in Visual Studio</a>. Part #3 is about <a href="http://cpptruths.blogspot.com/2019/05/bootstrapping-cmake-project-based-on.html">bootstrapping Hunter-based cmake project in Linux and Visual Studio</a>. The cmake code in the previous post works well on Linux too. After all, both cmake and vcpkg are designed for cross-platform build management. So what's new here?
<br/><br/>
This time around we'll get the same project off the ground in both Linux and Windows with cmake proper. Last time, the cmake script <code>CMakeLists.txt</code> felt like a poorly written bash script. Since that blogpost, I received a lot of feedback.
<br/><br/>
Feedback from Carlos ORyan (Google) forms the basis of this blog post. It would be more accurate to say that I'm downright stealing the cmake-vcpkg integration scripts he shared with me. They are open-source and available at <a href="https://github.com/coryan/google-cloud-cpp/tree/auto-vcpkg-prototype/super">google-cloud-cpp/super</a>. I've copied them nearly verbatim to my <a href="https://github.com/sutambe/cpptruths/commits/vcpkg_cmake_blog/cpp0x/vcpkg_test">vcpkg_cmake_blog</a> branch for ease of use and long term stability of the hyperlinks. Thanks Carlos!
<br/><br/>
The objective is the same: bootstrap a vcpkg-based cmake project. The mechanics are much more sophisticated and feel idiomatic cmake. Let's get started.
<br/>
<h2>Cmake Project Structure</h2>
<pre class="brush:bash">
vcpkg_test
├── cmake
│ ├── AutoVcpkg.cmake
│ └── VcpkgBootstrap.cmake
├── CMakeLists.txt
├── include
│ └── driver.h
├── src
│ └── driver.cpp
└── test
└── driver_test.cpp
</pre>
There're two more files under the cmake directory. These are cmake scripts designed to download, install, configure vcpkg instances in both Linux and Windows. They also expose suitable cmake function for use to use in <code>CMakeLists.txt</code>. This integration is much nicer (but also complex).
<br/><br/>
The <code>CMakeLists.txt</code> looks as follows.
<pre class="brush:cpp">
cmake_minimum_required (VERSION 3.12)
set(MY_PROJECT_DEPENDENCIES boost-core boost-optional boost-filesystem)
# This section of cmake is using AutoVcpkg to download, install, and configure vcpkg.
list(APPEND CMAKE_MODULE_PATH "${CMAKE_CURRENT_LIST_DIR}/cmake")
include(AutoVcpkg)
vcpkg_install(${MY_PROJECT_DEPENDENCIES})
message(STATUS "CMAKE_TOOLCHAIN_FILE=${CMAKE_TOOLCHAIN_FILE}")
# The CMakeLists from this point on is the same as that of part 1.
project (vcpkg_test CXX)
set(CMAKE_CXX_STANDARD 17)
find_package(Boost 1.67 REQUIRED COMPONENTS filesystem)
add_executable(driver src/driver.cpp)
target_include_directories(driver PUBLIC ${Boost_INCLUDE_DIRS} ${PROJECT_SOURCE_DIR}/include )
target_link_libraries(driver ${Boost_LIBRARIES})
enable_testing()
include(CTest)
add_executable(driver_test ${PROJECT_SOURCE_DIR}/test/driver_test.cpp)
add_test(NAME driver COMMAND driver_test)
</pre>
<code>find_package</code> finds and loads settings from an external project (package). <code>Boost_FOUND</code> will be set to indicate whether the Boost package was found. <code>add_executable</code> simply adds a target named driver to be built from the sources (<code>src/driver.cpp</code>). The Boost library dependencies are specified next for the <code>driver</code> target. First, a set of include directories are specified. Next, a set of libraries are specified. Note that boost-filesystem must be linked to driver program. Hence, <code>target_link_libraries</code> is essential. The variables <code>Boost_INCLUDE_DIRS</code>, <code>Boost_LIBRARIES</code> are set by <code>find_package</code> (only upon success).
<h2>vcpkg_install</h2>
Here's the full code of <a href="https://github.com/sutambe/cpptruths/blob/vcpkg_cmake_blog/cpp0x/vcpkg_test/cmake/AutoVcpkg.cmake">AutoVcpkg.cmake</a>. Here's the github branch <a href="https://github.com/sutambe/cpptruths/commits/vcpkg_cmake_blog_idiomatic/cpp0x/vcpkg_test">vcpkg_cmake_blog_idiomatic</a>.
<br/><br/>
We're including the files under cmake directory as "modules" and simply invoking them using <code>vcpkg_install</code>. The code is mostly self-explanatory. If you are new to cmake, you might have to stare at it for a while though.
<br/></br/>
The vcpkg-download is a separate cmake project. The CMakeLists.txt for this project is created while generating the build files for the driver project. I.e., It allows every project to bootstrap it's own vcpkg repository. This may or may not be desirable. For smaller project it might be an overkill. For large projects where controlling the exact library version separate from vcpkg repository HEAD is desirable, one might want a dedicated vcpkg instance. Here's the <a href="https://cmake.org/cmake/help/latest/module/ExternalProject.html">ExternalProject</a> vcpkg_download.
<pre class="brush:cmake">
cmake_minimum_required(VERSION 3.12)
project(vcpkg-download)
include(ExternalProject)
ExternalProject_Add(vcpkg
GIT_REPOSITORY @AUTO_VCPKG_GIT_REPOSITORY@
# GIT_TAG 52870c7595a63ade069ae51d5f4ee3a85fe4123f # TODO: Debug this
GIT_SHALLOW ON
SOURCE_DIR @AUTO_VCPKG_ROOT@
PATCH_COMMAND ""
CONFIGURE_COMMAND ""
BUILD_COMMAND ""
INSTALL_COMMAND ""
LOG_DOWNLOAD ON
LOG_CONFIGURE ON
LOG_INSTALL ON)
</pre>
So instead of simply forking off and launching <code>git clone</code> directly from cmake, this external project allows a plethora of options and configure the download step.
<br/><br/>
The vcpkg_download function spits out and runs this project (with another invocation of cmake) only if needed. I ended up passing additional flags to cmake on Windows. Having to pass additional flags like <code>CMAKE_EXE_LINKER_FLAGS, CMAKE_C_COMPILER, and CMAKE_CXX_COMPILER</code> (from parent to the nested invocation of cmake) indicates that cmake integration with Visual Studio is still rough on the edges. Here's a snippet.
<pre class="brush:cpp">
function (vcpkg_download)
if (DEFINED AUTO_VCPKG_ROOT)
return()
endif ()
set(AUTO_VCPKG_ROOT "${CMAKE_BINARY_DIR}/vcpkg")
# Generate the vcpkg_download project if necessary.
file(WRITE "${CMAKE_BINARY_DIR}/vcpkg-download/CMakeLists.txt" "${vcpkg_download_contents}")
if(WIN32)
get_filename_component(VC_COMPILER_PATH ${CMAKE_C_COMPILER} DIRECTORY)
set(VCRT_LIB_PATH "${VC_COMPILER_PATH}/../../../lib/x86")
execute_process(COMMAND "${CMAKE_COMMAND}"
"-H${CMAKE_BINARY_DIR}/vcpkg-download"
"-B${CMAKE_BINARY_DIR}/vcpkg-download"
"-DCMAKE_C_COMPILER:FILEPATH=${CMAKE_C_COMPILER}"
"-DCMAKE_CXX_COMPILER:FILEPATH=${CMAKE_CXX_COMPILER}"
"-DCMAKE_EXE_LINKER_FLAGS=/LIBPATH:\"${VCRT_LIB_PATH}\"")
execute_process(COMMAND "${CMAKE_COMMAND}"
"--build" "${CMAKE_BINARY_DIR}/vcpkg-download")
else()
# Linux here.
endif()
</pre>
If the previous step does not succeed in building vcpkg successfully (i.e., if <code>AUTO_VCPKG_EXECUTABLE</code> is undefined), there's plan B. The plan B is to do pretty much fork off a child cmake process and run vcpkg bootstrap.sh or bootstrap.bat directly. We saw a very simple version of it in <a href="http://cpptruths.blogspot.com/2019/03/bootstrapping-vcpkg-based-cmake-project.html">part #1</a>.
<pre class="brush:cmake">
function (vcpkg_bootstrap)
find_program(AUTO_VCPKG_EXECUTABLE vcpkg PATHS ${AUTO_VCPKG_ROOT})
if (NOT AUTO_VCPKG_EXECUTABLE)
execute_process(COMMAND ${CMAKE_COMMAND} -E copy "${CMAKE_CURRENT_LIST_DIR}/cmake/VcpkgBootstrap.cmake" "${AUTO_VCPKG_ROOT}")
execute_process(COMMAND ${CMAKE_COMMAND} -P "${AUTO_VCPKG_ROOT}/VcpkgBootstrap.cmake"
WORKING_DIRECTORY ${AUTO_VCPKG_ROOT})
endif ()
endfunction ()
###### VcpkgBootstrap.cmake file
find_program(VCPKG_EXECUTABLE
vcpkg PATHS "${CMAKE_CURRENT_LIST_DIR}")
if (NOT VCPKG_EXECUTABLE)
if (WIN32)
execute_process(COMMAND "${CMAKE_CURRENT_LIST_DIR}/bootstrap-vcpkg.bat"
WORKING_DIRECTORY "${CMAKE_CURRENT_LIST_DIR}")
else ()
execute_process(COMMAND "${CMAKE_CURRENT_LIST_DIR}/bootstrap-vcpkg.sh"
WORKING_DIRECTORY "${CMAKE_CURRENT_LIST_DIR}")
endif ()
endif ()
</pre>
At this point we've covered the gist. There are a lot of new things I learned about cmake.
<br/><br/>
The main differences between <a href="http://cpptruths.blogspot.com/2019/03/bootstrapping-vcpkg-based-cmake-project.html">part #1</a> and this cmake project are the following.
<ol>
<li>vcpkg is cloned from the github repository, compiled, and bootstrapped in the cmake <code>binary</code> directory. The directory you use for out-of-source builds (e.g., build). Previously, vcpkg is cloned, compiled, and bootstrapped in <code>$ENV{HOMEDRIVE}$ENV{HOMEPATH}/vcpkg_cpptruths</code></li>
<li>The <code>vcpkg-download</code> project is a real cmake project that generates a <code>Makefile</code> for bootstrapping vcpkg. On Windows, it generates a solution file under <code>$ENV{HOMEDRIVE}$ENV{HOMEPATH}\CMakeBuilds\...\build\x86-Debug\vcpkg-download</code>. Things are really meta at this point. cmake <a href="https://cmake.org/cmake/help/latest/module/ExternalProject.html">ExternalProject</a> is used for that. Some tweaks in execute_process were necessary to pass the right <code>${CMAKE_EXE_LINKER_FLAGS}</code>to build vcpkg with Visual Studio.</li>
</ol>
The projects seems to contain some meta targets that are unrelated to the main "driver" project. Here's how it looks like.
<a href="https://4.bp.blogspot.com/-VhRT_kKhTXI/XKGxzO7DO-I/AAAAAAAAGu8/SR-ehRssLycKcywQUf7VbrMCBwS3EYn_wCLcBGAs/s1600/vcpkg-download2.png" imageanchor="1" ><img border="0" src="https://4.bp.blogspot.com/-VhRT_kKhTXI/XKGxzO7DO-I/AAAAAAAAGu8/SR-ehRssLycKcywQUf7VbrMCBwS3EYn_wCLcBGAs/s1600/vcpkg-download2.png" data-original-width="1154" data-original-height="848" /></a>
<h2>Observations</h2>
There are a couple of things vcpkg.cmake could make the experience better.
<ol>
<li>GIT_TAG ... simply did not work for me in <code>ExternalProject_Add</code>. Cloning a specific tag/branch/commit hash of vcpkg is important for reproducible builds. Btw, Why aren't there any official releases of vcpkg? There's not a single tag as of this writing.</li>
<li>The technique is this post is lower level but feels much more well-integrated. However, the end effect is the same. Not sure if it's worth the increased complexity. Especially because I had to overcome vcpkg build error "LINK : fatal error LNK1104: cannot open file 'MSVCRTD.lib'" that did not happen in <a href="http://cpptruths.blogspot.com/2019/03/bootstrapping-vcpkg-based-cmake-project.html">part #1</a>. The resulting Visual Studio project has some cruft too.</li>
</ol>
<br /></div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-75282230151984695322019-03-25T11:32:00.002-07:002019-05-01T09:27:37.612-07:00Bootstrapping a vcpkg-based cmake project in Visual Studio<div dir="ltr" style="text-align: left;" trbidi="on">
After the last week's <a href="https://mvp.microsoft.com/summit">2019 Microsoft MVP Summit</a>, I decided to give <a href="https://github.com/Microsoft/vcpkg">Microsoft vcpkg</a> a shot. I've a cmake project at work and we target Linux using the <a href="https://github.com/ruslo/hunter">Hunter package manager</a>. So vcpkg had been on the back-burner for me.
<br/><br/>
I'm targeting a <strike>4 part</strike> 3 part blog series.
<ol>
<li>Bootstrapping a cmake project based on vcpkg in Visual Studio (this post)</li>
<li>Bootstrapping a cmake project based on vcpkg in Linux and Visual Studio with idiomatic cmake (<a href="http://cpptruths.blogspot.com/2019/03/bootstrapping-vcpkg-based-cmake-project_31.html">here</a>)</li>
<li>Bootstrapping a cmake project based on <a href="https://github.com/ruslo/hunter">Hunter</a> in Linux and Windows (<a href="http://cpptruths.blogspot.com/2019/05/bootstrapping-cmake-project-based-on.html">here</a>)</li>
</ol>
As of this writing I'm new to vcpkg. So I apologize in advance if you are annoyed by noob mistakes. Please leave a comment if you notice something.
<br/><br/>
If you prefer to clone/browse a github project. All contents in this blogpost are available under <a href="https://github.com/sutambe/cpptruths/commits/vcpkg_cmake_blog/cpp0x/vcpkg_test">cpptruths/cpp0x/vcpkg_test</a> (branch <a href="https://github.com/sutambe/cpptruths/commits/vcpkg_cmake_blog/cpp0x/vcpkg_test">vcpkg_cmake_blog</a>).
<br/><br/>
To start with, I've a barebones C++ project with nearly empty <code>driver.cpp</code> and <code>driver.h</code> files. Later, I'll add Boost core and optional as third party dependencies. Both are header-only. Later, we will add libraries requiring linking. So, let's get started.
<br/>
<h2>A barebones C++ cmake project</h2>
The following is the project structure of my near-empty C++ project <code>vcpkg_test</code>
<pre class="brush:cpp">
vcpkg_test
├── CMakeLists.txt
├── include
│ └── driver.h
├── src
│ └── driver.cpp
└── test
└── driver_test.cpp
3 directories, 4 files
</pre>
The <code>driver.cpp</code> and <code>driver_test.cpp</code> files have just a main function that does nothing. <code>driver.h</code> is empty. The <code>CMakeLists.txt</code> looks as follows.
<pre class="brush:cmake">
cmake_minimum_required (VERSION 3.12)
project (vcpkg_test CXX)
set(CMAKE_CXX_STANDARD 17)
add_executable(driver src/driver.cpp)
target_include_directories(driver PUBLIC ${PROJECT_SOURCE_DIR}/include)
target_link_libraries(driver ${Boost_LIBRARIES})
enable_testing()
include(CTest)
add_executable(driver_test ${PROJECT_SOURCE_DIR}/test/driver_test.cpp)
add_test(NAME driver COMMAND driver_test)
</pre>
See the <a href="https://cmake.org/cmake-tutorial/">cmake tutorial</a> if the above file is all greek. It builds two executables from the sources: driver and driver_test.
<br/><br/>
There're many ways to structure the project. In this project I've chosen to use only one <code>CMakeLists.txt</code> to build both the sources and the test. One could have added CMakeLists.txt in src and test sub-directories.
<br/></div>
<h2>Open cmake Project in Visual Studio</h2>
Visual Studio 2017+ has <a href="https://docs.microsoft.com/en-us/cpp/build/cmake-projects-in-visual-studio?view=vs-2017">built-in support for cmake projects</a>. Yes, you read that right! You can open the folder containing the top-level <code>CMakeLists.txt</code> and Visual Studio will figure out everything. The loaded project looks very clean.
<br/><br/>
Things used to be very different not too long ago. cmake's native solution generator used to add additional targets that are not visible in the <code>CMakeLists.txt</code> you wrote. I always wondered what magic was going on there.
<br/></br/>
Visual Studio runs cmake automatically on the <code>CMakeLists.txt</code>.
<div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-YOF4EBfXKN4/XJkAovfq7LI/AAAAAAAAGlA/8Cns8UOlVFEhrgyG6nYV4qi7j-bR_sqzgCLcBGAs/s1600/vs-cmake-output.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-YOF4EBfXKN4/XJkAovfq7LI/AAAAAAAAGlA/8Cns8UOlVFEhrgyG6nYV4qi7j-bR_sqzgCLcBGAs/s1600/vs-cmake-output.png" data-original-width="1097" data-original-height="518" /></a></div>
Project build and rebuild works as expected.
<div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-QuTbKpQlymg/XJkBSbTCKVI/AAAAAAAAGlI/46mbn3Bst_kuxRg0fGoRmvrwqEUbiZTZgCLcBGAs/s1600/vs-rebuild.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-QuTbKpQlymg/XJkBSbTCKVI/AAAAAAAAGlI/46mbn3Bst_kuxRg0fGoRmvrwqEUbiZTZgCLcBGAs/s1600/vs-rebuild.png" data-original-width="1014" data-original-height="222" /></a></div>
Targets <code>driver.exe</code> and <code>driver_test.exe</code> are available in the drop-down. Here's how my loaded project looks like. No cruft!
<div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-V_V9F9yBRNQ/XJkBqYZf69I/AAAAAAAAGlQ/EvIJYuKVOmUHv_LKbu4v2cdZ3Quz2yEkgCLcBGAs/s1600/vs-cmake-project.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-V_V9F9yBRNQ/XJkBqYZf69I/AAAAAAAAGlQ/EvIJYuKVOmUHv_LKbu4v2cdZ3Quz2yEkgCLcBGAs/s1600/vs-cmake-project.png" data-original-width="985" data-original-height="341" /></a></div>
So, that's how a toy C++ cmake project looks like. Let's use vcpkg to manage our third-party dependencies: boost-core and boost-optional.
<h2>Adding vcpkg to a cmake project</h2>
Here's a <a href="https://docs.microsoft.com/en-us/cpp/vcpkg?view=vs-2019">vcpkg tutorial</a> to get your cmake project off the ground in Visual Studio. However, my goal is to create a reproducible build with maximum automation when a user clones the project directory. Perhaps something that could run as-is on <a href="https://www.appveyor.com/">AppVeyor</a> CI servers. So the following <code>CMakeLists.txt</code> expects only Visual Studio 2017+ installed on a Windows machine.
<br/><br/>
The script clones the vcpkg repository and bootstraps it as necessary. We also change the <code>CMAKE_TOOLCHAIN_FILE</code> variable to point to the vcpkg instance the script downloaded and bootstrapped. This allows cmake to discover, include, and link packages managed by vcpkg. </li>Here're the changes to <code>CMakeLists.txt</code>.
<pre class="brush:cmake">
cmake_minimum_required (VERSION 3.12)
set(MY_PROJECT_DEPENDENCIES boost-core boost-optional boost-filesystem)
if(NOT DEFINED ${CMAKE_TOOLCHAIN_FILE})
if(NOT DEFINED ENV{VCPKG_ROOT})
if(WIN32)
set(VCPKG_ROOT $ENV{HOMEDRIVE}$ENV{HOMEPATH}/vcpkg_cpptruths)
else()
set(VCPKG_ROOT $ENV{HOME}/.vcpkg_cpptruths)
endif()
else()
set(VCPKG_ROOT $ENV{VCPKG_ROOT})
endif()
if(NOT EXISTS ${VCPKG_ROOT})
message("Cloning vcpkg in ${VCPKG_ROOT}")
execute_process(COMMAND git clone https://github.com/Microsoft/vcpkg.git ${VCPKG_ROOT})
# If a reproducible build is desired (and potentially old libraries are # ok), uncomment the
# following line and pin the vcpkg repository to a specific githash.
# execute_process(COMMAND git checkout 745a0aea597771a580d0b0f4886ea1e3a94dbca6 WORKING_DIRECTORY ${VCPKG_ROOT})
else()
# The following command has no effect if the vcpkg repository is in a detached head state.
message("Auto-updating vcpkg in ${VCPKG_ROOT}")
execute_process(COMMAND git pull WORKING_DIRECTORY ${VCPKG_ROOT})
endif()
if(NOT EXISTS ${VCPKG_ROOT}/README.md)
message(FATAL_ERROR "***** FATAL ERROR: Could not clone vcpkg *****")
endif()
if(WIN32)
set(BOOST_INCLUDEDIR ${VCPKG_ROOT}/installed/x86-windows/include)
set(VCPKG_EXEC ${VCPKG_ROOT}/vcpkg.exe)
set(VCPKG_BOOTSTRAP ${VCPKG_ROOT}/bootstrap-vcpkg.bat)
else()
set(VCPKG_EXEC ${VCPKG_ROOT}/vcpkg)
set(VCPKG_BOOTSTRAP ${VCPKG_ROOT}/bootstrap-vcpkg.sh)
endif()
if(NOT EXISTS ${VCPKG_EXEC})
message("Bootstrapping vcpkg in ${VCPKG_ROOT}")
execute_process(COMMAND ${VCPKG_BOOTSTRAP} WORKING_DIRECTORY ${VCPKG_ROOT})
endif()
if(NOT EXISTS ${VCPKG_EXEC})
message(FATAL_ERROR "***** FATAL ERROR: Could not bootstrap vcpkg *****")
endif()
set(CMAKE_TOOLCHAIN_FILE ${VCPKG_ROOT}/scripts/buildsystems/vcpkg.cmake CACHE STRING "")
message(STATUS "***** Checking project third party dependencies in ${VCPKG_ROOT} *****")
execute_process(COMMAND ${VCPKG_EXEC} install ${MY_PROJECT_DEPENDENCIES} WORKING_DIRECTORY ${VCPKG_ROOT})
endif()
</pre>
If everything goes well, the cmake script clones vcpkg repository under <code>$ENV{HOMEDRIVE}$ENV{HOMEPATH}/vcpkg_cpptruths</code> and bootstraps it (i.e., there're no pre-installed packages). From now on it will automatically use the <code>CMAKE_TOOLCHAIN_FILE</code> from this directory. Of course, you can override the <code>CMAKE_TOOLCHAIN_FILE</code> at the command prompt to point to a different vcpkg instance all different toolchain altogether. Also, feel free to change the path vcpkg_cpptruths to something you like.
<div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-FETCA2arqpw/XJkHYWc7LVI/AAAAAAAAGlc/JzhyE-3l2C4Sl6xwFQCoizVG1nrj9WA1ACLcBGAs/s1600/build-vcpkg.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-FETCA2arqpw/XJkHYWc7LVI/AAAAAAAAGlc/JzhyE-3l2C4Sl6xwFQCoizVG1nrj9WA1ACLcBGAs/s1600/build-vcpkg.png" data-original-width="951" data-original-height="307" /></a></div>
<h2>Managing third-party dependencies with vcpkg</h2>
Now is the time to add the boost dependencies. Three steps are needed.
<ol>
<li>Write code that uses boost-core and boost-optional</li>
<li>Instruct vcpkg to download and install boost-core and boost-optional</li>
<li>Update <code>CMakeLists.txt</code> with the right dependencies</li>
</ol>
Here's my test code that uses boost-core and boost-optional.
<pre class="brush:cpp">
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <typeinfo>
#include "boost/core/demangle.hpp"
#include "boost/filesystem.hpp"
#include "driver.h"
void check_exists(const char *filename) {
using namespace boost::filesystem;
path p(filename);
if (exists(p)) { // does p actually exist?
if (is_regular_file(p)) // is p a regular file?
std::cout << p << " size is " << file_size(p) << '\n';
else if (is_directory(p)) // is p a directory?
std::cout << p << " is a directory\n";
else
std::cout << p << " exists, but is neither a regular file nor a directory\n";
}
else
std::cout << p << " does not exist\n";
}
int main() {
std::srand(static_cast<unsigned int>(std::time(0)));
boost::optional<int> i = Generator::get_even_random_number();
if (i) {
std::cout << std::sqrt(static_cast<float>(*i)) << "\n";
std::cout << boost::core::demangle(typeid(boost::optional<int>).name()) << "\n";
}
check_exists("driver");
}
</pre>
For #2, you could open a shell and run <code>vcpkg install boost-core boost-optional boost-filesystem</code>. It's simple. However, I want a reproducible automatic build setup. So I'm going to have cmake run the same vcpkg command and install the dependencies it's going to use later.
<pre class="brush:cmake">
set(MY_PROJECT_DEPENDENCIES boost-core boost-optional boost-filesystem)
message(STATUS "***** Checking project third party dependencies in ${VCPKG_ROOT} *****")
execute_process(COMMAND ${VCPKG_ROOT}/vcpkg.exe install ${MY_PROJECT_DEPENDENCIES} WORKING_DIRECTORY ${VCPKG_ROOT})
</pre>
The <code>execute_process</code> command gets the job done. However, I'm not sure, if there's a better to do the same thing. Take a look at <a href="http://cpptruths.blogspot.com/2019/03/bootstrapping-vcpkg-based-cmake-project_31.html">part #2 with idiomatic cmake</a>. Is there a higher-level cmake function(s) in vcpkg.cmake that would install the libraries in the vcpkg instance (pointed by the <code>CMAKE_TOOLCHAIN_FILE</code>).
<br/><br/>
Saving the file <code>CMakeLists.txt</code> in Visual Studio runs it and installs the packages in <code>${MY_PROJECT_DEPENDENCIES}</code>.
<div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-9FtjEObu_Bc/XJkPEqZC_2I/AAAAAAAAGlo/aBsmo1Hyr1ciMFmGIDyrz-sF2f3JnnAtgCLcBGAs/s1600/cmake-vcpkg-boost.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-9FtjEObu_Bc/XJkPEqZC_2I/AAAAAAAAGlo/aBsmo1Hyr1ciMFmGIDyrz-sF2f3JnnAtgCLcBGAs/s1600/cmake-vcpkg-boost.png" data-original-width="1005" data-original-height="534" /></a></div>
Now we update <code>CMakeLists.txt</code> to look for boost libraries. This part step is platform and package-manger independent.
<pre class="brush:cmake">
find_package(Boost 1.67 REQUIRED COMPONENTS filesystem)
add_executable(driver src/driver.cpp)
target_include_directories(driver PUBLIC ${Boost_INCLUDE_DIR} ${PROJECT_SOURCE_DIR}/include)
target_link_libraries(driver ${Boost_LIBRARIES})
</pre>
<code>find_package</code> finds and loads settings from an external project (package). <code>Boost_FOUND</code> will be set to indicate whether the Boost package was found. <code>add_executable</code> simply adds a target named driver to be built from the sources (<code>src/driver.cpp</code>). The Boost library dependencies are specified next for the <code>driver</code> target. First, a set of include directories are specified. Next, a set of libraries are specified. Note that boost-filesystem must be linked to driver program. Hence, <code>target_link_libraries</code> is essential. The variables <code>Boost_INCLUDE_DIR</code>, <code>Boost_LIBRARIES</code> are set by <code>find_package</code> (only upon success).
<br/><br/>
You may have to regenerate the cmake cache as the <code>CMAKE_TOOLCHAIN_FILE</code> has been updated. You can do that by right-clicking on <code>CMakeLists.txt</code>.
<br/><br/>
At this point the code builds and runs cleanly for me. No squiggles.
<div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-8NdaJTYapZQ/XJkWV7KpIAI/AAAAAAAAGl4/WzkFsFipoaQQFTngDbFa6KaWgaqsvgLwQCLcBGAs/s1600/vcpkg-driver-code.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-8NdaJTYapZQ/XJkWV7KpIAI/AAAAAAAAGl4/WzkFsFipoaQQFTngDbFa6KaWgaqsvgLwQCLcBGAs/s1600/vcpkg-driver-code.png" data-original-width="1118" data-original-height="528" /></a></div>
<h2>Observations</h2>
Some things I noted would make the experience nicer in Visual Studio 2019.
<ol>
<li>The Open Project/Solution dialog box did not show <code>CMakeLists.txt</code> under "All Project Files" drop down. First-class support should make the experience seamless.</li>
<li>If vcpkg is integrated with Visual Studio such that libraries get installed in the right vcpkg instance, that would be great. </li>
<li>It would be nice to have cmake functions in vcpkg.cmake that would install libraries in the vcpkg instance. I received responses from multiple people who had some ground work here.
<ol><li>See <a href="https://github.com/vector-of-bool/pmm">Package Manager Manager</a> (pmm) mentioned on <a href="https://www.reddit.com/r/cpp/comments/b5r79e/bootstrapping_a_vcpkgbased_cmake_project_in/ejg2ipg?utm_source=share&utm_medium=web2x">reddit/r/cpp</a>.</li>
<li><a href="https://github.com/coryan/google-cloud-cpp/tree/auto-vcpkg-prototype/super">Google-cloud-cpp/super</a> project uses cmake functionality such as ExternalProject_Add and other friends to bootstrap a vcpkg instance.</li>
</ol></li>
<li>After updating <code>CMakeLists.txt</code>, the output of cmake is not displayed in the IDE right-away. It takes a good minute and it appears like Visual Studio is stuck. Seems like cmake does not flush output to the IDE window right-away.</code></li>
</ol>Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-15177988209338338332019-02-08T19:16:00.000-08:002019-02-12T09:31:24.126-08:00Review of Manning's Functional Programming in C++<div dir="ltr" style="text-align: left;" trbidi="on">
Last year I reviewed the pre-print manuscript of Manning's <a href="https://www.manning.com/books/functional-programming-in-c-plus-plus">Functional Programming in C++</a> written by Ivan Čukić. <br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://www.manning.com/books/functional-programming-in-c-plus-plus" target="_blank"><img border="0" data-original-height="562" data-original-width="449" height="320" src="https://2.bp.blogspot.com/-c3QsUDlhEDE/XFdbPpPPD2I/AAAAAAAADG8/Sc0Zky9LXEgJpMYmk-HfECqll4qegbxnQCLcBGAs/s320/fp-in-cpp-front.png" width="254" /></a><span id="goog_411361742"></span><a href="https://www.blogger.com/"></a><span id="goog_411361743"></span></div>
I really enjoyed reading the book. I enthusiastically support that the book
<br />
<blockquote>
Offers precise, easy-to-understand, and engaging explanations of functional concepts.</blockquote>
<h2>Who is this book for</h2>
This book expects a reasonable working knowledge of C++, its modern syntax, and semantics from the readers. Therefore, reading this book might require a companion book for C++ beginners. I think that’s fair because FP is an advanced topic. C++ is getting more and more powerful day by day. While there are many FP topics that could be discussed in such a book, I like the practicality of the topics selected in this book.
<br/><br/>
Here's the table of contents at a glance.
<div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ng2qS8amCH8/XF8Nau2cePI/AAAAAAAADIQ/6EUQQRMQgZwSAhiag7ZZLq9NxAaEIA_8ACLcBGAs/s1600/fpcpp-contents.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-ng2qS8amCH8/XF8Nau2cePI/AAAAAAAADIQ/6EUQQRMQgZwSAhiag7ZZLq9NxAaEIA_8ACLcBGAs/s400/fpcpp-contents.png" width="400" height="373" data-original-width="1050" data-original-height="980" /></a></div>
This is a solid coverage of functional programming concepts to get a determined programmer going from zero-to-sixty in a matter of weeks. Others have shared their thoughts on this book as well. See Rangarajan Krishnamoorthy's <a href="https://www.rangakrish.com/index.php/2018/12/02/book-review-functional-programming-in-c/#comments">commentary</a> on this book.
<br/><br/>
I found 4 chapters in the book really instructive.
<ul>
<li>Getting Started With Functional Programming (Chapter 2): This is my favorite because this is where your mind start to bend and you feel it! The esoteric idea of passing and returning functions starts to make sense and its power becomes apparent. One also realizes that C++ was never far from that idea anyway. Function Objects, my friends! A specific thing I learned from this chapter was the "generality of fold": First comes recursion; then comes the stack size limitation of recursion; then comes tail-call optimization; then comes incremental updates to the state (mutable or immutable); and finally comes fold. It goes deeper than that though.</li>
<li>Lazy Evaluation (Chapter 6): This is where you find expression templates and generalized memoization. I liked the discussion of computing Fibonacci with a fixed-size (forgetful) cache. I wrote a <a href="http://cpptruths.blogspot.com/2012/01/general-purpose-automatic-memoization.html">blogpost on memoization</a> a long time back.</li>
<li>Ranges (chapter 7): The <a href="https://ericniebler.github.io/range-v3/">Ranges library</a> is perhaps the largest and the most visible aspect of functional programming in C++. The book describes uses of the ranges library through a number of examples of filter, transform, and even infinite ranges. Ranges are now in C++20.
<div class="separator" style="clear: both; text-align: center;"><a href="http://ericniebler.com/2018/12/05/standard-ranges/" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-sb_YioTkc98/XF8bsBoL-9I/AAAAAAAADIc/Qus4eZB0qygw5KXohNVSFfUmdDhYgBLqACLcBGAs/s400/ranges.png" width="400" height="208" data-original-width="1168" data-original-height="608" /></a></div> </li>
<li>Monads (Chapter 10): This topic is fascinating. I've bought FP books to read the chapter on monads primarily. This book makes it this difficult topic approachable by dissecting <code>std::optional</code> and chainable futures---libraries that C++ programmers are probably familiar with already.</li>
</ul>
<br/>
Having said that there are a number of places I would have done/written something differently. In short, this blogpost is a soft critic of the book. Everything below has been provided as feedback to the editor.<br />
<h2>General Thoughts</h2>
If there was room for more content in the book, I would have loved to see the following.
<ul>
<li>A dedicated section on <a href="https://en.cppreference.com/w/cpp/language/fold">C++ fold expressions</a>. My personal opinion is that this book isn't complete without discussing C++ fold expressions in a dedicated section. fold expression are used in this book. The index at the end does not mention it. I can't imagine this is a pre-requisite!</li>
<li>Discussion of the ideas of <i>entering</i> a monad and <i>existing</i> a monad. The notion that, once a pipeline has begun, the logic is weaved around the same monad as much as possible and only at the end one breaks out of the monad because side-effects must be materialized or one needs a full collection to pass to a non-monadic library. In my experience, I’ve seen rookie engineers to use the monadic api just for one or two steps (like map/filter). I’ve sensed a block against going after much longer monadic chains. The examples in the book are great. But in practice people may stay away from long chains due to very high logical density.</li>
<li><b>Algebraic API Design.</b> map/filter/reduce/groupBy/flatmap return the same type—the algebraic type—in many cases a monad. It’s not a coincidence. It’s a fundamental aspect of the functional design. It’s a tell-tale sign of a functional api. It’s an algebra and operations on algebra return objects from the same algebra. It is elegantly represented using (1) the fluent api style (2) operator overloading (a sophisticated version of 1). As functional libraries in C++ tend to use operator overloading, one might miss the easier starting point which is the fluent api. I’ve found algebraic api design for <a href="https://www.slideshare.net/SumantTambe/c-generators-and-propertybased-testing#20">random number generators</a> quite instructive.</li>
<li><b>Notion of monad as higher-ranked typeclass.</b> C++ can model the monad typeclass using template template parameter. I’ve not found any practical uses of such a template but I think it would be fun to discuss. I've discussed it in <a href="http://cpptruths.blogspot.com/2017/01/folding-monadic-functions.html">folding monadic functions</a>.
<pre class="brush:cpp">
template<template <typename> class M>
struct monad
{
template <class T, class Func>
static auto bind(M<T>& m, Func&& func) -> decltype(func(m));
};
</pre></li>
<li>Algebraic list/tree data structures. Conceptually using cons/cdr lisp primitives and/or with <code>std::variant</code> and <code>std::recursive_wrapper</code>.
<li>Well-known names of <code>accumulate</code>, <code>transform</code>, and <code>mbind</code>, which are <code>reduce</code>, <code>map</code> and <code>flatmap</code>. The entire book does not mention <code>flatmap</code> anywhere! I think minimally, names used in other common libraries/languages would be quite instructive.</li>
<li>Currying functions of arbitrary is not discussed. Interested readers can checkout previous blogpost on <a href="http://cpptruths.blogspot.com/2016/11/dependently-typed-curried-printf.html">currying arbitrary functions</a> (see later half).</li>
<li>The difference between returning a function pointer and returning a function object or a stateful lambda. For many good C programmers returning a function pointer would be familiar but it’s still not functional programming. Bringing the distinction out would clarify a lot of things.</li>
<li>This book explains argument-dependent lookup (static polymorphism) without an example. It’s much easier to understand if there’s an example code to look at. I would suggest to introduce argument-dependent lookup much earlier in the book with an example.</li>
</li>
</ul>
<h2>Section-wise</h2>
<ul>
<li>In section 2.4.4, it may be worthwhile to discuss the guarantees <code>std::accumulate</code> makes regarding making copies of the intermediate result in to the user-supplied function. For ints it won’t matter but for <code>std::vector</code> it would. I checked that <code>std::accumulate</code> (before C++20) requires that init value type be copy-assignable and copy-constructible. It looks like pre-C++20 <code>std::accumulate</code> can be used to avoid copies either by returning a reference or by using <code>std::ref</code> and <code>std::reference_wrapper</code>. Full example code on <a href="https://wandbox.org/permlink/a6DcJEJ7t0Yc7gk4">Wandbox</a>.</li>
<pre class="brush:cpp">
using Vector = std::vector<int>;
void nocopy_accumulate(Vector &v) {
Vector init;
Vector v2 = std::accumulate(v.begin(), v.end(), std::ref(init),
[](std::reference_wrapper<Vector> v, int i) {
v.get().push_back(i);
return v;
});
std::cout << "size of v2 = " << v2.size() << "\n";
}
</pre>
<li>Chapter 3: Lambdas and function objects are introduced here. The chapter does not discuss what we can not do with lambdas. I.e., We can pass them around, make copies, but we can't assign them. This causes pain in writing <code>ListMonad::flatMap</code> in C++, which may have to cache and update the nested function (lambda) returned by the inner function. That's not a problem with function objects. C++20 likely not have this restriction on lambdas anymore.</li>
<li>Section 4.1.2 A Rudimentary bind implementation. I always thought <code><a href="https://en.cppreference.com/w/cpp/utility/functional/bind">std::bind</a></code> is too much magic. It will be quite rewarding to the reader to understand some C++ mechanics that can implement a simple bind function. In this case, I referring to static polymorphism (<code>bind_helper</code> below). It's worth learning to see how lambdas make <code>std::bind</code> nearly irrelevant. So here's an example of implementing a rudimentary <code>std::bind</code>. This implementation calls the function right-away when both arguments are provided. Unlike <code>std::bind</code>. These semantics are closer to functional languages. A true variadic bind could be an exercise for the reader. Live code on <a href="https://wandbox.org/permlink/Rx3Roi39rzDly315">Wandbox</a>.
<pre class="brush:cpp">
#include <iostream>
#include <utility>
struct Arg1 {} _1;
struct Arg2 {} _2;
template <class Func, class A1, class A2>
auto bind_helper(Func f, A1 a1, A2 a2) {
return f(a1,a2);
}
template <class Func>
auto bind_helper(Func f, Arg2, Arg1) {
return [f](auto first_arg, auto second_arg) {
return f(second_arg, first_arg);
};
}
template <class Func>
auto bind_helper(Func f, Arg1, Arg2) {
return [f](auto first_arg, auto second_arg) {
return f(first_arg, second_arg);
};
}
template <class Func, class A2>
auto bind_helper(Func f, Arg1, A2 a2) {
return [f, a2](auto first_arg) {
return f(first_arg, a2);
};
}
template <class Func, class A1>
auto bind_helper(Func f, A1 a1, Arg1) {
return [f,a1](auto second_arg) {
return f(a1, second_arg);
};
}
template <class Func, class A1, class A2>
auto bind(Func&& f, A1&& a1, A2&&a2) {
return bind_helper(std::forward<Func>(f), std::forward<A1>(a1), std::forward<A2>(a2));
}
int main()
{
std::cout << std::boolalpha << bind(std::greater<int>(), _1, 42)(43) << "\n"; // true
std::cout << std::boolalpha << bind(std::greater<int>(), 42, _1)(43) << "\n"; // false
std::cout << std::boolalpha << bind(std::greater<int>(), _1, _2)(43, 42) << "\n"; // true
std::cout << std::boolalpha << bind(std::greater<int>(), _2, _1)(43, 42) << "\n"; // false
}
</pre>
</li>
<li>Section 7.3. Mixing left and right associative operators. The code like <code>"words |= action::sort | action::unique"</code> is too much magic. I think it’s worth talking the operator associativity magic going on here. <code>|=</code> is right-to-left associative and <code>|</code> is left-to-right associative. Because of that what’s really happening here is more like <code>words |= (action::sort | action::unique);</code>.</li>
<li>Section 10.6 Handling State with Monads: Looking at the title and the text underneath one would think that State monad is discussed. For instance, the following two lines <ol><li>"The simplest way is to pass each function the current state along with its regular arguments: the function should return the new state."</li>
<li>"This log is the state you want to change"</li></ol>
Changing state (not just appending) is hallmark of the State monad. However, the monad discussed in this section is the Writer monad. I did some reading on <a href="https://stackoverflow.com/a/22140063">stackoverflow</a>. I think this section should not confuse with state monad as the computation is NOT dependent on existence of a state. Usage of empty <code>std::string</code> in the constructor of <code>with_log</code> confirms that a monoid is used (as necessary in the Writer monad). There's a note at the bottom of the page though, which calls out Writer monad.</li>
<li>Listing 11.7, Using fold expressions without a prior introduction. Chapter 2 discussed folds but never the fold expressions.</li>
<li>Section 12.6 and listing 12.11: What kind of monad is <code>with_client</code>? Is there a well-known counter-part in other languages/libraries. It looks like a product type to me and that’s it. It’s generic on <code>MessageType</code> but that alone does not make it a monad. The closest I can think of is the Writer monad because it's a tuple. A transform can be defined on it so it’s may be a Functor. But how about mbind? Any given <code>with_client<with_client<std::string>></code> has two <code>tcp::sockets</code> in them. Which one would survive when <code>mbind</code> flattens them?</li>
<li>Independent of whether it’s a monad or not, I don’t agree with the suggestion here that one should try to find a monad in every generic type. That seems to be the tone of the paragraph. When you have a hammer, everything starts looking like a nail. IMO, construction and usage of a monad should be given a very deep thought. Once an application is coded in a monad, in reality, it’s going be very hard to change to a different monad or a different stack of monads.</li>
<li>Section 13.1 mentions <i>"some people say that once you successfully compile a functional program, it is bound to work correctly"</i>. I think this was said in the context of Haskell only and not other less pure functional languages. It may be much more true in case of Idris etc languages.</li>
<li>Section 13.4 Testing monad-based Systems: There are two claims/suggestions made in this section.
<ol>
<li>Page 283, <i>"freely switch between different monads"</i>
<li>Page 285, <i>"just change the definitions of transform and filter"</i>
</ol>
I’m not a fan of the above two arguments. In my experience, changing monads is significantly hard.
<ul>
<li>The examples in the book suggest changing (reimplementing) transform and filter for collections while moving away from production reactive streams to testing the same pipeline. In practice, one would use something like RxCPP or something equally sophisticated to implement reactive streams. It might be <code>std::future</code> with <code>.then</code> chaining. As these are specialized monads, there are api functions that would make sense only in them. For example, Consider operators in Rx <code>combine_latest</code>, <code>debounce</code>, <code>subscribe_on</code>, <code>produce_on</code>, <code>delay</code>, <code>timeout</code>. They don’t appear to have an obvious replacement in other monads. How would one go about testing a pipeline that has used these operators?</li>
<li>I’ll try to answer my own question here. I think it might work out in case of reactive streams and collections because they are duals of each other. That’s a theoretical argument. In practice, one would drive the reactive stream directly by using <code>Subjects</code> from Rx. From the book it would be a replacement of <code>boost::asio::server</code> with a predefined array of input data. However, in general, it is probably harder than it looks.</li>
<li>Rewriting large swatch of operators for two or more monads would be a big deterrent to the adoption of this paradigm.</li>
</ul>
</li>
</ul>
<h2>Nit Picks</h2>
<ul>
<li>Collections vs. Containers: I think <code>collection</code> is a Java concept. In C++ we’ve containers. So <code>container<T></code> might be a better choice here. </li>
</ul>
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-31198469368551258862019-02-03T12:34:00.002-08:002019-02-08T21:27:18.066-08:00Unit Testing C++ Templates and Mock Injection Using Traits<div dir="ltr" style="text-align: left;" trbidi="on">
Unit testing your template code comes up from time to time. (You test your templates, right?) Some templates are easy to test. No others. Sometimes it's not clear how to about injecting mock code into the template code that's under test. I've seen several reasons why code injection becomes challenging.<br />
<br />
Here I've outlined some examples below with roughly increasing code injection difficulty.
<ol>
<li>Template accepts a type argument and an object of the same type by reference in constructor</li>
<li>Template accepts a type argument. Makes a copy of the constructor argument or simply does not take one</li>
<li>Template accepts a type argument and instantiates multiple interrelated templates without virtual functions</li>
</ol>
Lets start with the easy ones.<br />
<h2>Template accepts a type argument and an object of the same type by reference in constructor</h2>
This one appears straight-forward because the unit test simply instantiates the template under test with a mock type. Some assertion might be tested in the mock class. And that's about it.<br />
<br />
Of course, testing with just a single type argument says nothing about rest of the infinite number of types that one could pass to the template. A fancy way to say the same thing is templates are <i>universally quantified</i> so we might have to get little more clever for more scientific testing. More on that later.<br />
<br />
For example,
<pre class="brush:cpp">
template <class T>
class TemplateUnderTest {
T *t_;
public:
TemplateUnderTest(T *t) : t_(t) {}
void SomeMethod() {
t->DoSomething();
t->DoSomeOtherThing();
}
};
struct MockT {
void DoSomething() {
// Some assertions here.
}
void DoSomeOtherThing() {
// Some more assertions here.
}
};
class UnitTest {
void Test1() {
MockT mock;
TemplateUnderTest<MockT> test(&mock);
test.SomeMethod();
assert(DoSomethingWasCalled(mock));
assert(DoSomeOtherThingWasCalled(mock));
}
};
</pre>
<h2>Template accepts a type argument. Makes a copy of the constructor argument or simply does not take one</h2>
In this case accessing the object inside the template might be inaccessible due to access privileges. <code>friend</code> classes could be used.
<pre class="brush:cpp">
template <class T>
class TemplateUnderTest {
T t_;
friend class UnitTest;
public:
void SomeMethod() {
t.DoSomething();
t.DoSomeOtherThing();
}
};
class UnitTest {
void Test2() {
TemplateUnderTest<MockT> test;
test.SomeMethod();
assert(DoSomethingWasCalled(test.t_)); // access guts
assert(DoSomeOtherThingWasCalled(test.t_)); // access guts
}
};
</pre>
The <code>UnitTest::Test2</code> can simply reach into the guts of <code>TemplateUnderTest</code> and verify the assertions on the internal copy of <code>MockT</code>.
<h2>Template accepts a type argument and instantiates multiple interrelated templates without virtual functions</h2>
For this case, I'll take a real-life example: <a href="https://grpc.io/docs/tutorials/async/helloasync-cpp.html">Asynchronous Google RPC</a>
<br/>
In C++ async gRPC, there's something called <code>CallData</code>, which as the name suggests, stores the <i>data related to an RPC call</i>. A <code>CallData</code> template can handle multiple RPC of different types. So it's not uncommon to make it a template.
<br/>
A generic <code>CallData</code> accepts two type arguments <code>Request</code> and <code>Response</code>. This is how it may look like
<pre class="brush:cpp">
template <class Request, class Response>
class CallData {
grpc::ServerCompletionQueue *cq_;
grpc::ServerContext context_;
grpc::ServerAsyncResponseWriter<Response> responder_;
// ... some more state
public:
using RequestType = Request;
using ResponseType = Response;
CallData(grpc::ServerCompletionQueue *q)
: cq_(q),
responder_(&context_)
{}
void HandleRequest(Request *req); // application-specific code
Response *GetResponse(); // application-specific code
};
</pre>
The unit test for <code>CallData</code> template must verify the behavior of <code>HandleRequest</code> and <code>HandleResponse</code>. These functions call a number of functions of the members. So making sure they are called in correctly is paramount to the correctness of <code>CallData</code>. However, there's a catch.
<ol>
<li>Some types from <code>grpc</code> namespace are instantiated internally and not passed via the constructor. <code>ServerAsyncResponseWriter</code> and <code>ServerContext</code>, for example.</li>
<li><code>grpc::ServerCompletionQueue</code> is passed as an argument to the constructor but it has no <code>virtual</code> functions. Only <code>virtual</code> destructor.
<li><code>grpc::ServerContext</code> is created internally and has no <code>virtual</code> functions</li>
</ol>
The question is how to test <code>CallData</code> without using full-blown gRPC in the tests? How to mock <code>ServerCompletionQueue</code>? How to mock <code>ServerAsyncResponseWriter</code>, which is itself a template? and on and on...
<br/><br/>
Without <code>virtual</code> functions, substituting custom behavior becomes challenging. Hardcoded types such as <code>grpc::ServerAsyncResponseWriter</code> are impossible to mock because, well, they are hardcoded and not injected.
</br/><br/>
It makes little sense to start passing them as constructor arguments. Even if do that, it may be meaningless because they may be <code>final</code> classes or simply have no <code>virtual</code> functions.
<br/><br/>
So, what gives?
<h1>Solution: Traits</h1>
<div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-tudOig05pA4/XF5i8oCEFiI/AAAAAAAADH8/OyYK5kW7V00NhbkrMd07tj_4GLed_UjsgCLcBGAs/s1600/unit-test-template.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-tudOig05pA4/XF5i8oCEFiI/AAAAAAAADH8/OyYK5kW7V00NhbkrMd07tj_4GLed_UjsgCLcBGAs/s1600/unit-test-template.png" data-original-width="1442" data-original-height="548" /></a></div>
Instead of injecting custom behavior by inheriting from a common type (as done in Object-Oriented programming), INJECT THE TYPE ITSELF. We use traits for that. We specialize the traits differently depending upon whether it's production code or unit test code.
<br/><br/>
Consider the following <code>CallDataTraits</code>
<pre class="brush:cpp">
template <class CallData>
class CallDataTraits {
using ServerCompletionQueue = grpc::ServerCompletionQueue;
using ServerContext = grpc::ServerContext;
using ServerAsyncResponseWriter = grpc::ServerAsyncResponseWrite<typename CallData::ResponseType>;
};
</pre>
This is the primary template for the trait and used for "production" code. Let's use it in the <code>CallData</code> template.
<pre class="brush:cpp">
/// Unit testable CallData
template <class Request, class Response>
class CallData {
typename CallDataTraits<CallData>::ServerCompletionQueue *cq_;
typename CallDataTraits<CallData>::ServerContext context_;
typename CallDataTraits<CallData>::ServerAsyncResponseWriter responder_;
// ... some more state
public:
using RequestType = Request;
using ResponseType = Response;
CallData(typename CallDataTraits<CallData>::ServerCompletionQueue *q)
: cq_(q),
responder_(&context_)
{}
void HandleRequest(Request *req); // application-specific code
Response *GetResponse(); // application-specific code
};
</pre>
Given the above code, it's clear that production code is still using the types from the <code>grpc</code> namespace. However, we can easily replace the grpc types with mock types. Checkout below.
<pre class="brush:cpp">
/// In unit test code
struct TestRequest{};
struct TestResponse{};
struct MockServerCompletionQueue{};
struct MockServerContext{};
struct MockServerAsyncResponseWriter{};
/// We want to unit test this type.
using CallDataUnderTest = CallData<TestRequest, TestResponse>;
/// A specialization of CallDataTraits for unit testing purposes only.
template <>
class CallDataTraits<CallDataUnderTest> {
using ServerCompletionQueue = MockServerCompletionQueue;
using ServerContext = MockServerContext;
using ServerAsyncResponseWriter = MockServerAsyncResponseWrite;
};
MockServerCompletionQueue mock_queue;
CallDataUnderTest cdut(&mock_queue); // Now injected with mock types.
</pre>
Traits allowed us to choose the types injected in <code>CallData</code> depending upon the situation. This technique has zero performance overhead as no unnecessary virtual functions were created to inject functionality. The technique can be used with <code>final</code> classes as well.
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-69843184495028077872018-12-09T10:59:00.001-08:002018-12-09T11:18:03.304-08:00Simple Template Currying<div dir="ltr" style="text-align: left;" trbidi="on">
Currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions, each with a single argument. I've discussed Currying on this blog previously in <a href="http://cpptruths.blogspot.com/2014/03/fun-with-lambdas-c14-style-part-1.html">Fun With Lambdas C++14 Style</a> and <a href="http://cpptruths.blogspot.com/2016/11/dependently-typed-curried-printf.html">Dependently-Typed Curried printf</a>. Both blogposts discuss currying of functions proper. I.e., they discuss how C++ can treat functions as values at runtime.
<br/><br/>
However, currying is not limited to just functions. Types can also be curried---if they take type arguments. In C++, we call them templates. Templates are "functions" at type level. For example, passing two type arguments <code>std::string</code> and <code>int</code> to <code>std::map</code> gives <code>std::map<std::string, int></code>. So <code>std::map</code> is a type-level function that takes two (type) arguments and gives another type as a result. They are also known as type constructors.
<br/><br/>
So, the question today is: Can C++ templates be curried? As it turns out, they can be. Rather easily. So, here we go...
<pre class="brush:cpp">
#include <type_traits>
#include <functional>
#include <map>
#include <iostream>
template <template <class...> class C, class... T, class D = C<T...>>
constexpr std::true_type valid(std::nullptr_t);
template <template <class...> class C, class... T>
constexpr std::false_type valid(...);
template <class TrueFalse, template <class...> class C, class... ArgsSoFar>
struct curry_impl;
template <template <class...> class C, class... ArgsSoFar>
struct curry_impl<std::true_type, C, ArgsSoFar...> {
using type = C<ArgsSoFar...>;
};
template <template <class...> class C, class... ArgsSoFar>
struct curry_impl<std::false_type, C, ArgsSoFar...> {
template <class... MoreArgs>
using apply = curry_impl<decltype(valid<C, ArgsSoFar..., MoreArgs...>(nullptr)), C, ArgsSoFar..., MoreArgs...>;
};
template <template <class...> class C>
struct curry {
template <class... U>
using apply = curry_impl<decltype(valid<C, U...>(nullptr)), C, U...>;
};
int main(void) {
using CurriedIsSame = curry<std::is_same>;
static_assert(curry<std::is_same>::apply<int>::apply<int>::type::value);
curry<std::less>::apply<int>::type less;
std::cout << std::boolalpha << less(5, 4); // prints false
using CurriedMap = curry<std::map>;
using MapType = CurriedMap::apply<int>::apply<long, std::less<int>, std::allocator<std::pair<const int, long>>>::type;
static_assert(std::is_same<MapType, std::map<int, long>>::value);
}
</pre>
<a href="https://wandbox.org/permlink/YlKo7yUKdbgoszu1">Wandbox</a>
<br/><br/>
The technique is very simple. There's a function called <code>valid</code> that has two overloads. The first one returns <code>std::true_type</code> only if <code>C<T..></code> is a valid instantiation of template <code>C</code> with argument list <code>T...</code>. Otherwise, it returns <code>std::false_type</code>. <code>C</code> is type constructor that we would like to curry. This function uses the SFINAE idiom.
<br/><br/>
<code>curry_impl</code> is the core implementation of template currying. It has two specializations. The <code>std::true_type</code> specialization is selected when <code>valid</code> returns <code>std::true_type</code>. I.e., curried version of the type constructor has received the minimum number of type arguments to form a complete type. In other words, <code>ArgsSoFar</code> are enough. <code>curry_impl<C, ArgsSoFar...>::type</code> is same as instantiation of the type constructor with the valid type arguments (<code>C<ArgsSoFar...></code>).
<br/><br/>
Note that C++ allows templates to have default type arguments. Therefore, a template could be instantiated by providing "minimum" number of arguments. For example, <code>std::map</code> could be instantiated in three ways giving the same type:
<ul>
<li><code>std::map<int, long></code></li>
<li><code>std::map<int, long, std::less<int>></code></li>
<li><code>std::map<int, long, std::less<int>, std::pair<const int, long>></code></li>
</ul>
<br />
When <code>ArgsSoFar</code> are not enough, <code>curry_impl<std::false_type></code> carries the partial list of type arguments (<code>ArgsSoFar</code>) at class template level. It allows passing one or more type arguments (<code>MoreArgs</code>) to the type constructor through the <code>apply</code> typedef. When <code>ArgsSoFar</code> and <code>MoreArgs</code> are enough to form a valid instantiation, <code>curry_impl<std::true_type></code> is chosen which yields the fully instantiated type.
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-35822569879821215352018-11-17T20:10:00.001-08:002018-11-18T14:48:54.135-08:00Non-colliding Efficient type_info::hash_code Across Shared Libraries<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
C++ standard library has <code>std::type_info</code> and <code>std::type_index</code> to get run-time type information about a type. There are some efficiency and robustness issues in using them (especially when dynamically loaded libraries are involved.)
<br/><br/>
TL;DR; The <code>-D__GXX_MERGED_TYPEINFO_NAMES -rdynamic</code> compiler/linker options (for both the main program and the library) generates code that uses pointer comparison in <code>std::type_info::operator==()</code>.
<br/><br/>
The <code>typeid</code> keyword is used to obtain a type's run-time type information. Quoting cppreference.
<blockquote>The <code>typeid</code> expression is an lvalue expression which refers to an object with <b>static storage duration</b>, of the polymorphic type <code>const std::type_info</code> or of some type derived from it.</blockquote>
<code>std::type_info</code> objects can not be put in <code>std::vector</code> because they are non-copyable and non-assignable. Of course, you can have a <code>std::vector<const std::type_info *></code> as the object returned by <code>typeid</code> has static storage duration. You could also use <code>std::vector<std::type_index></code>. <code>std::type_index</code> contains a pointer to <code>std::type_info</code> and therefore, copies are possible and cheap. It's also safer to use <code>std::type_index</code> because for associative containers, <code>std::type_index</code> delegates less-then, equality, and greater-than to the underlying <code>std::type_info</code> object. And that's what you want. Just using <code>const std::type_info *</code> would do pointer comparisons. The result may be different.
<br/>
<br/>
The real question I'm seeking an answer to is
<blockquote>Is C++ typeid machinery reliable for determining uniqueness of polymorphic types robustly, efficiently, portably, and across dynamically loaded modules?</blockquote>
This seems like a tall order. There's one caveat though. "Portability" for me is limited to RHEL7 Linux, MacOS 10.x, and may be Windows 10 with really latest toolchains (clang++ 7.x, g++ 8.x, Visual Studio 2017). I'm not worried about other platforms at the moment.
<br/>
<h2>Robustness</h2>
The first step is to check if <code>std::type_info</code> or <code>std::type_index</code> is the same for the same type and not same for different types.
<br/>
We've a few things to use for comparisons:
<ul>
<li><code>std::type_info::operator==()</code></li>
<li><code>std::type_info::name()</code></li>
<li><code>std::type_info::hash_code()</code></li>
<li><code>std::type_info *</code></li>
</ul>
Consider <code>type_info::operator==</code>. Equality comparison between two <code>type_info</code> objects returns true for the same types and false for different types even when dynamically loaded libraries are involved. The question is how fast is it. We'll look at that a little later.
<br/><br/>
The worst function for determining equality appears to be <code>type_info::name</code>. Quoting cppreference: "No guarantees are given; in particular, the returned string can be identical for several types". I'm really bummed by that.
<br/><br/>
Next is <code>type_info::hash_code</code>. As hashes for two different types can collide, it is useless for determining type equality. The only thing C++17 standard (n4713) says is
<blockquote>Within a single execution of the program, it shall return the same value for any two <code>type_info</code> objects which compare equal.</blockquote> Hash calculation could also be slow as it would be typically <code>O(n)</code> where n is the length of the mangled name. There's one implementation-specific hack though. Certain preprocessor macros (discussed below) enable <code>type_info::hash_code</code> to return a pointer to <code>type_info</code> object. That's super-fast. But does it provide guarantees of uniqueness? May be so.
<br/><br/>
That brings us to the last option: <code>std::type_info *</code>. If <code>std::type_info::operator==()</code> is implemented in terms of pointer comparisons, then we might get the best of both worlds. Fast, reliable <code>type_info</code> comparisons. Is there a way? Read on...
<br/><br/>
However, when shared libraries (.so on Linux, .dll on Windows) are in the picture, no such guarantee can be given. And it makes sense. As shared-library and the main program could be compiled completely independently, expecting that <code>typeid(Foo)</code> is the same object in main and dynamically loaded libraries is wishful thinking. We'll tackle this issue after the next section.
<h2>Efficiency</h2>
If you look at <code>std::type_info</code> in libc++ and libstdc++ you will discover a couple of macros that directly determine efficiency of the comparison operators. It's <code>_LIBCPP_HAS_NONUNIQUE_TYPEINFO</code> in libc++ and <code>__GXX_MERGED_TYPEINFO_NAMES</code> in libstdc++ respectively. In the respective library implementations, they control whether <code>std::type_info</code> comparisons are simply pointer comparisons or much more expensive <code>const char *</code> comparisons. With long names of template instantiations, the cost of <code>strcmp</code>-like operations could be high.
<br/><br/>
If you are interested in detailed performance numbers and library code, you may want to checkout <a href="https://dholmes215.github.io/c++/2017/06/30/fun-with-typeid.html">Fun with typeid() blogpost by David Holmes</a>. The long and the short of it is that with <code>_LIBCPP_HAS_NONUNIQUE_TYPEINFO</code> disabled in libc++ and <code>__GXX_MERGED_TYPEINFO_NAMES</code> enabled in libstdc++, performance of <code>std::type_info</code> and <code>std::type_index</code> comparisons is an order of magnitude better (due to just pointer comparisons).
<br/><br/>
On my MacOS machine, <code>_LIBCPP_HAS_NONUNIQUE_TYPEINFO</code> is not defined by default. So things are good. On my RHEL7 box, <code>__GXX_MERGED_TYPEINFO_NAMES</code> is not defined. There's explanation why that's the case in libstdc++. It reads something like this.
<br/><br/>
<pre class="brush:bash">
// Determine whether typeinfo names for the same type are merged (in which
// case comparison can just compare pointers) or not (in which case strings
// must be compared), and whether comparison is to be implemented inline or
// not.
// We used to do inline pointer comparison by default if weak symbols
// are available, but even with weak symbols sometimes names are not merged
// when objects are loaded with RTLD_LOCAL, so now we always use strcmp by
// default.
// For ABI compatibility, we do the strcmp inline if weak symbols
// are available, and out-of-line if not. Out-of-line pointer comparison
// is used where the object files are to be portable to multiple systems,
// some of which may not be able to use pointer comparison, but the
// particular system for which libstdc++ is being built can use pointer
// comparison; in particular for most ARM EABI systems, where the ABI
// specifies out-of-line comparison.
// The compiler's target configuration
// can override the defaults by defining __GXX_TYPEINFO_EQUALITY_INLINE to
// 1 or 0 to indicate whether or not comparison is inline, and
// __GXX_MERGED_TYPEINFO_NAMES to 1 or 0 to indicate whether or not pointer
// comparison can be used.
</pre>
Thats' dense! I'm unclear about what merged really means in this context. What is being merged with what? Anyone?
<br/><br/>
The best part is the last sentence. The standard library authors are permitting setting an otherwise internal macro (starts with __) to enable pointer comparisons. So there seems to be light at the end of the tunnel.
<br/><br/>
One thing I'm not 100% sure is the keyword "target configuration". A compiler's target configuration is the machine assembly code is generated for. On my machine, <code>gcc -v</code> prints <code>Target: x86_64-redhat-linux</code>. I.e., the resulting code is suitable for running on <code>x86_64-redhat-linux</code>---a native build. I'm unclear whether the compiler and the standard library itself should be built with the same preprocessor macro. If you are curious about what <i>build</i>, <i>host</i>, and <i>target</i> machines are for a compiler, see <a href="https://gcc.gnu.org/onlinedocs/gccint/Configure-Terms.html">gcc configure terms and history</a>.
<br/><br/>
The following invocation of the compiler seems to produce code that uses pointer comparisons in <code>type_info::operator==</code>.
<pre class="brush:bash">
g++ -std=c++11 -D__GXX_MERGED_TYPEINFO_NAMES -ldl -o test test.cpp
</pre>
<h2>Dynamically Loaded Libraries</h2>
There's another wrinkle which appears to be around dynamic loading of shared libraries. Something about "weak symbols" and <code>RTLD_LOCAL</code>. What in the world are those things?
<br/><br/>
In the man pages for <code>dlopen</code>---a library function to load shared library files (*.so) at run-time---you will find <code>RTLD_LOCAL</code>. Quoting man pages:
<blockquote>This is the converse of <code>RTLD_GLOBAL</code>, and the default if neither flag is specified. Symbols defined in this library are not made available to resolve references in subsequently loaded libraries.</blockquote>
So if your program uses dynamically loaded libraries and the libraries rely on a globally known definition of <code>std::type_info(Foo)</code> object, you might be out of luck if the libraries are opened using default flags or explicitly with <code>RTLD_LOCAL</code>. Such libraries, even if compiled with <code>__GXX_TYPEINFO_EQUALITY_INLINE</code>, will use their own local definitions of <code>std::type_info(Foo)</code>. Obviously, if your program relies on a global unique definition, as in <code>std::set<std::type_index></code> or some similar shenanigans, your program is likely to explode.
<br/><br/>
Ok, so, I can't open the libraries with <code>RTLD_LOCAL</code> or default. I've to use <code>RTLD_GLOBAL</code>. Easy.
<br/><br/>
To be extra careful, I threw in a run-time check to ensure the main program and the shared-library file agree on the definition of <code>std::type_info</code> of Foo.
<br/><br/>
The Foo header file.
<pre class="brush:cpp">
// Foo.h
#ifndef FOO_H
#define FOO_H
namespace test {
class Foo {
virtual ~Foo() = default;
};
}
using namespace test;
extern "C" void foo(const std::type_info &);
#endif // FOO_H
</pre>
The Foo implementation file.
<pre class="brush:cpp">
// Foo.cpp (shared-library implementation)
#include <iostream>
#include <typeinfo>
#include <cassert>
#include "foo.h"
void test(const std::type_info &other)
{
assert(other == typeid(Foo));
std::cout << "typeid equality = " << std::boolalpha << (other == typeid(Foo)) << std::endl;
assert(other.hash_code() == typeid(Foo).hash_code());
std::cout << "typeid hash_code equality = " << std::boolalpha << (other.hash_code() == typeid(Foo).hash_code()) << std::endl;
std::cout << "typeid name: module=" << typeid(Foo).name() << ", other=" << other.name() << std::endl;
}
</pre>
And the main program (robust_typeid.cpp)
<pre class="brush:cpp">
#include <typeinfo>
#include <iostream>
#include <string>
#include <unistd.h>
#include <dlfcn.h>
#include "foo.h"
int main(void) {
char cwd[1024];
getcwd(cwd, sizeof(cwd));
std::string path = std::string(cwd) + "/libfoo.so";
void *handle = dlopen(path.c_str(), RTLD_GLOBAL);
std::cout << "handle = " << handle << "\n";
using TestFunctionType = void (*)(const std::type_info &);
TestFunctionType foo_ptr = reinterpret_cast<TestFunctionType>(dlsym(handle, "test"));
if(test_ptr)
test_ptr(typeid(Foo));
if(handle)
dlclose(handle);
}
</pre>
The program loads libfoo.so dynamically and calls the <code>test</code> function in the library. The main module passes a reference to <code>Foo</code>'s <code>std::type_info</code> object (as observed by the main module) to function <code>test</code>. The function checks if they agree on the uniqueness of <code>std::type_info</code> object for <code>Foo</code>.
<br/><br/>
Finally, the compiler options.
<pre class="brush:bash">
// Create libfoo.so
$ clang++ -std=c++11 -D__GXX_MERGED_TYPEINFO_NAMES -fpic -shared foo.cpp -o libfoo.so
// Create the main program
$ clang++ -std=c++11 -D__GXX_MERGED_TYPEINFO_NAMES -ldl -o robust_typeid robust_typeid.cpp
// Run
$ /.robust_typeid
</pre>
It crashes with an assertion failure. Ouch!
<pre class="brush:bash">
handle = 0x85dcf0
robust_typeid: foo.cpp:9: void test(const std::type_info &): Assertion <code>other == typeid(Foo)</code> failed.
Aborted (core dumped)
</pre>
Suspicion turned to be right. Something's not right.
<br/><br/>
With some google-foo, I found gcc's linker flag <code>-rdynamic</code> or <code>-export-dynamic</code>. Quoting man pages:
<blockquote>This instructs the linker to add all symbols, not only used ones, to the dynamic symbol table. This option is needed for some uses of <code>dlopen</code></blockquote>
Let's try.
<div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-YKpFkQFD3Os/W_HDK9KA_VI/AAAAAAAADCE/EyepLj02ljozhp9IBvkl9-yDZJuhLMITQCLcBGAs/s1600/robust-typeid-screenshot2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-YKpFkQFD3Os/W_HDK9KA_VI/AAAAAAAADCE/EyepLj02ljozhp9IBvkl9-yDZJuhLMITQCLcBGAs/s1600/robust-typeid-screenshot2.png" data-original-width="744" data-original-height="245" /></a></div>
Voilla!
<br/><br/>
These two options seem to enable the best of both worlds: fast, reliable <code>type_info</code> comparisons. Additionally, the <code>type_info::hash_code</code> function returns a pointer. Does that make it non-colliding? Is <code>-D__GXX_MERGED_TYPEINFO_NAMES -rdynamic</code> really a silver bullet? Let me know what you think. Comment on <a href="https://www.reddit.com/r/cpp/comments/9y4ufz/noncolliding_efficient_type_infohash_code_across">reddit/r/cpp</a>.
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-36484880175172828322018-10-22T11:02:00.000-07:002019-05-15T21:18:05.857-07:00Chained Functions Break Reference Lifetime Extension <div dir="ltr" style="text-align: left;" trbidi="on">
I discovered a reference lifetime extension gotcha.
<br/><br/>
<b>TL;DR;</b> Chained functions (that return a reference to <code>*this</code>) do not trigger C++ reference lifetime extension. Four ways out: First, don't rely on lifetime extension---make a copy; Second, have all chained functions return <code>*this</code> by-value; Third, use rvalue reference qualified overloads and have only them return by-value; Fourth, have a last chained <code>ExtendLifetime()</code> function that returns a prvalue (of type *this).
<h2>C++ Reference Lifetime Extension</h2>
C++ has a feature called "reference lifetime extension". Consider the following.
<pre class="brush:cpp">
std::array<std::string, 5> create_array_of_strings();
{
const std::array<std::string, 5> &arr = create_array_of_strings();
// Only inspect arr here.
} // arr out of scope. The temporary pointed to by arr destroyed here.
</pre>
The temporary <code>std::array</code> returned by <code>create_array_of_strings()</code> is not destroyed after the function returns. Instead the "lifetime" of the temporary <code>std::array</code> is extended till the end of lifetime of reference <code>arr</code>. This feature saves you from coping the object when all you want to do is to inspect it's state. Without this feature, the <code>std::array</code> must be copied in a local variable. A move would be attempted but move-constructor for <code>std::array</code> just copies rhs to lhs. So this feature has been helpful since pre-move-semantics days of C++.
<br/><br/>
It works even when a direct public member of the temporary object is assigned to a const reference. For example,
<pre class="brush:cpp">
struct Person {
struct Name {
std::string first_name;
std::string last_name;
} name;
};
Person birth();
{
const std::string &first_name = birth().name.first_name;
// do something with first_name.
} // first_name out of scope. The referred Person went to grave here.
</pre>
<h2>Gotchas</h2>
What makes this feature interesting is all the natural-looking cases where it does not work. <a href="https://abseil.io/tips/107">Abseil tip #107</a> mentions a few of them. For readability, I'm gonna mention them briefly here.
<ol>
<li>Any access to the nested state via a function (member or free) disables lifetime extension of the parent. For example <code>Person().GetName().first_name</code> would no longer trigger lifetime extension of the temporary <code>Person</code>.</li>
<li>As a corollary, any conversion member functions, chained member functions do not extend the lifetime of the original temporary.</li>
</ol>
<h2>Chained Functions Break Lifetime Extension</h2>
Chaining of function is a common pattern where the state of the same object is modified by successively calling different member functions. It's known by different names including the "builder" pattern (not GoF) and <a href="https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Named_Parameter">Named Parameter Idiom</a>. It would look something like this for class <code>Person</code> and class <code>Address</code>.
<pre class="brush:cpp">
class Address {
public:
Address &Line1(std::string l1) { ... return *this; }
Address &Line2(std::string l2) { ... return *this; }
Address &State(std::string state) { ... return *this; }
Address &Zip(int zip) { ... return *this; }
};
class Person {
public:
Person &FirstName(std::string first) { ... return *this; }
Person &LastName(std::string first) { ... return *this; }
Person &MailingAddress(Address addr) { ... return *this; }
};
</pre>
Such a chainable class could be used to create a person in place.
<pre class="brush:cpp">
Person p = Person().FirstName("C").LastName("Z").MailingAddress(Address().Line1("...").Line2("...").State("CA").Zip(12345));
</pre>
As the line is too long, one might attempt a straight-forward refactoring---only to be chastised after.
<pre class="brush:cpp">
auto &addr = Address().Line1("...").Line2("...").State("CA").Zip(12345);
Person p = Person().FirstName("C").LastName("Z").MailingAddress(std::move(addr));
</pre>
This refactoring is incorrect. If you are lucky the code will barf at runtime soon. No guarantees though. It's UB land.
<br/><br/>
By the time the <code>MailingAddress</code> function is called, the <code>addr</code> has become a dangling reference. The <code>Address</code> object is already created and destroyed. The reason is that the lifetime of the temporary <code>Address</code> object is no longer extended due to the chain of member functions.
<br/><br/>
Clang address sanitizer did not catch it either. It looks like a case of <a href="https://github.com/google/sanitizers/wiki/AddressSanitizerExampleUseAfterFree">UseAfterFree</a> but there's no <code>malloc/free</code> in sight.
<h2>Restoring Extended Lifetime</h2>
There're a couple of ways to restore lifetime extension.
<br/>
<ol>
<li>Return the container class (<code>Person, Address</code>) by-value from each member function. This option is either very
expensive or 2x verbose.</li>
<li>Add a dedicated chain termination function that returns <code>*this</code> by-value.</li>
</ol>
Lets consider option #1. Returning <code>*this</code> by-value from each function is expensive. Compiler makes a copy of <code>*this</code> to construct the returned object. Move semantics don't kick in because a member function that returns <code>*this</code> by-value cannot automatically decide to move from <code>*this</code>. There could be a legitimate lvalue pointing to <code>*this</code>.
<br/><br/>
So, the following is NOT a good solution.
<pre class="brush:cpp">
class Address { // Each chained function makes a copy
public:
Address Line1(std::string l1) { ... return *this; }
Address Line2(std::string l2) { ... return *this; }
Address State(std::string state) { ... return *this; }
Address Zip(int zip) { ... return *this; }
};
</pre>
<h2>Rvalue Reference Qualified Functions?</h2>
rvalue reference qualified functions could be used to avoid a copy. Note the difference in return types and reference qualifications.
<pre class="brush:cpp">
class Address { // No longer makes a copy when *this is an rvalue.
public:
Address & Line1(std::string l1) & { ... return *this; }
Address Line1(std::string l1) && { ... return std::move(*this); }
Address & Line2(std::string l2) & { ... return *this; }
Address Line2(std::string l2) && { ... return std::move(*this); }
Address & State(std::string state) & { ... return *this; }
Address State(std::string state) && { ... return std::move(*this); }
Address & Zip(int zip) & { ... return *this; }
Address Zip(int zip) && { ... return std::move(*this); }
};
</pre>
The above 2x verbose <code>Address</code> class is one solution to the lifetime extension problem. An lvalue <code>Address</code> remains an lvalue throughout chaining. An rvalue <code>Address</code> remains an rvalue throughout chaining. The rvalue qualified member functions don't make a copy either. They move. Hopefully, the <code>Address</code> class has fast move-semantics. Not all classes do.
<br/><br/>
Would you really accept it as a solution? .... It's too verbose!
<br/>
<h2>Dedicated Lifetime Extending Function</h2>
Second option is to add a function that terminates the chain and extends the lifetime of the original object.
<pre class="brush:cpp">
class Address { // Each chained function makes a copy
public:
Address & Line1(std::string l1) { ... return *this; }
Address & Line2(std::string l2) { ... return *this; }
Address & State(std::string state) { ... return *this; }
Address & Zip(int zip) { ... return *this; }
Address ExtendLifetime() & { return std::move(*this); }
};
</pre>
There's <code>ExtendLifetime</code> function that allows us to opt into lvalue to rvalue conversion with a single move at the end of the chain. Safe code now looks like
<pre class="brush:cpp">
const auto &addr = Address().Line1("...").State("CA").Zip(12345).ExtendLifetime();
Person p = Person().FirstName("C").LastName("Z").MailingAddress(addr);
</pre>
The catch is that one has to remember to call the <code>ExtendLifetime</code> function when refactoring. It is easy to miss.
<h2>Copy/Move?</h2>
Trickiness of the issue perhaps suggests to create a copy but that may not be always possible/desirable.
<pre class="brush:cpp">
auto addr = Address().Line1("...").State("CA").Zip(12345); // makes a copy
Person p = Person().FirstName("C").LastName("Z").MailingAddress(addr);
</pre>
For instance, the above approach does not work if <code>Address</code> is move-only (e.g., contains a <code>unique_ptr</code>). Of course, one could use a move.
<pre class="brush:cpp">
auto addr = std::move(Address().Line1("...").State("CA").Zip(12345));
Person p = Person().FirstName("C").LastName("Z").MailingAddress(std::move(addr));
</pre>
Mechanics wise, this is not a whole lot different from <code>.ExtendLifetime()</code>. <code>std::move</code> is well understood. However, it kills the flow of chained functions.
<h2>Conclusion</h2>
So no solution appears to be perfect. The first one is massively verbose but it's correct post refactoring. The second one is also correct but the gotcha remains. Using a copy is preferred by redditors <a href="https://www.reddit.com/r/cpp/comments/9qms4n/chained_functions_break_reference_lifetime/">here</a>. Some real-life libraries that may be subject to this issue are mentioned in <a href="https://www.reddit.com/r/cpp/comments/bmydl8/chained_functions_break_reference_lifetime/">another reddit discussion</a>.
<br/><br/>
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-72812594728022239922018-09-23T15:14:00.000-07:002018-10-13T08:54:56.010-07:00Convenient deduction guides for std::function<div dir="ltr" style="text-align: left;" trbidi="on">
The objective is to allow the following to be valid C++.
<pre class="brush:cpp">
#include <functional>
struct Test {
void func(int) {}
};
void test() {
std::function deduced = &Test::func; // compiler error
std::function<void (Test *, int)> ex = &Test::func; // OK
}
</pre>
With <a href="https://en.cppreference.com/w/cpp/language/class_template_argument_deduction">class template argument deduction</a> in C++17, type arguments for <code>std::function</code> above should have been deduced. The first line in function <code>test</code> <a href="https://godbolt.org/z/dX7HC2">fails to compile</a> as of this writing because <code>std::function</code> does not appear to have <a href="https://en.cppreference.com/w/cpp/utility/functional/function/deduction_guides">deduction guides</a> for conversion from pointer to member functions. On the other hand, explicitly specifying the template arguments makes the compiler happy.
<br/><br/>
The following deduction guide seems to fix the issue.
<pre class="brush:cpp">
namespace std { // warning: undefined behavior
template<class R, class C, class... ArgTypes>
function(R(C::*)(ArgTypes...)) -> function<R(C*, ArgTypes...)>;
}
void test() {
std::function deduced = &Test::func; // Now, OK
std::function<void (Test *, int)> ex = &Test::func;
Test test;
deduced(&test, 10); // Calls test.func(10)
ex(&test, 10); // Calls test.func(10)
}
</pre>
However, the above code is technically <a href="https://www.reddit.com/r/cpp/comments/9igyvk/convenient_deduction_guides_for_stdfunction/">undefined behavior</a> because a user-defined deduction guide for a standard library type is added in <code>std</code> namespace. Clang does not like it either. Gcc may start rejecting this code in (near) future.
<br/><br/>
Weirdly, deduction guides must be defined in the same scope where the primary template is defined. That means, writing custom deduction guides for standard library types is out of question. Not sure how I feel about that.
<h2>Arbitrary Choice</h2>
There's another problem. In the deduction guide above, I made an arbitrary choice that the deduced <code>std::function</code> is callable with a pointer to <code>Test</code>. That's arbitrary. What about <code>Test&</code>?
<h2><code>PtrCallable</code> and <code>RefCallable</code></h2>
I added two types that specify how the function will be called. This time in my own namespace.
<pre class="brush:cpp">
namespace callable {
template <class... Args>
struct PtrCallable : std::function<Args...> {
using std::function<Args...>::function; // inherited constructors
};
template <class... Args>
struct RefCallable : std::function<Args...> {
using std::function<Args...>::function; // inherited constructors
};
// Deduction guides for the newly introduced types
template<class R, class C, class... ArgTypes>
PtrCallable(R(C::*)(ArgTypes...)) -> PtrCallable<R(C*, ArgTypes...)>;
template<class R, class C, class... ArgTypes>
RefCallable(R(C::*)(ArgTypes...)) -> RefCallable<R(C&, ArgTypes...)>;
} // namespace callable
</pre>
Now the choice is not arbitrary. User can pick one.
<pre class="brush:cpp">
using namespace callable;
void test() {
RefCallable deduced1 = &Test::func;
PtrCallable deduced2 = &Test::func;
Test test;
deduced1(test, 10); // Calls test.func(10)
deduced2(&test, 10); // Calls (&test)->func(10)
}
</pre>
<h2>More deduction guides for <code>const</code> and <code>volatile</code></h2>
More deduction guides are needed to support other varieties of member functions. Let's add them.
<pre class="brush:cpp">
namespace callable {
template<class R, class C, class... ArgTypes>
PtrCallable(R(C::*)(ArgTypes...) const) -> PtrCallable<R(const C*, ArgTypes...)>;
template<class R, class C, class... ArgTypes>
RefCallable(R(C::*)(ArgTypes...) const) -> RefCallable<R(const C&, ArgTypes...)>;
// ditto for volatile and const volatile
} // namespace callable
</pre>
<h2>Deduction guides for rvalue-ref qualified member functions</h2>
Even more deduction guides are needed for rvalue-ref qualified member functions
<pre class="brush:cpp">
namespace callable {
template<class R, class C, class... ArgTypes>
RefCallable(R(C::*)(ArgTypes...) &&) -> RefCallable<R(C&&, ArgTypes...)>;
template<class R, class C, class... ArgTypes>
RefCallable(R(C::*)(ArgTypes...) const &&) -> RefCallable<R(const C&&, ArgTypes...)>;
// ditto for volatile and const volatile
} // namespace callable
</pre>
<h2>Conclusion</h2>
With a dozen or so new deduction guides all the following cases work. Runnable code is shared on <a href="https://wandbox.org/permlink/e7SQTtiMT6peBto1">Wandbox</a>.
<pre class="brush:cpp">
const Test getConstTest() {
return {};
}
void test_function() {
std::function<void(Test*, int)> f1 = &Test::Nonconst;
std::function<void(const Test*, int)> f2 = &Test::Const;
Test a;
const Test c;
f1(&a, 1);
f2(&c, 1.0);
}
void test_refcallable() {
using namespace callable;
Test a;
const Test c;
RefCallable f1 = &Test::Nonconst;
f1(a, 1);
RefCallable f2 = &Test::Const;
f2(a, 1);
f2(c, 1);
RefCallable f3 = &Test::rvalue;
f3(Test{}, 10);
RefCallable f4 = &Test::rvalue_const;
f4(getConstTest(), 10);
}
void test_ptrcallable() {
using namespace callable;
Test a;
const Test c;
PtrCallable f1 = &Test::Nonconst;
f1(&a, 1);
PtrCallable f2 = &Test::Const;
f2(&a, 1);
f2(&c, 1);
}</pre>
<br /></div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-51010656309822332352018-02-19T19:57:00.000-08:002018-02-21T10:13:45.146-08:00Inheritance vs std::variant<div dir="ltr" style="text-align: left;" trbidi="on">
C++17 added std::variant and std::visit in its repertoire. They are worth a close examination. I've been wondering about whether they are <i>always</i> better than inheritance for modeling sum-types (fancy name for discriminated unions) and if not, under what circumstances they are not. We'll compare the two approaches in this blog post. So here it goes.<br />
<br />
<table>
<tbody style="border-collapse: separate; border-spacing: 4px; border: 2px solid black; display: block; text-align: center;">
<tr bgcolor="#888888" style="color: white;"><th>Inheritance</th><th>std::variant</th></tr>
<tr bgcolor="#CCCCCC"><td>Need not know all the derived types upfront (open-world assumption)</td><td>Must know all the cases upfront (closed-world assumption)</td></tr>
<tr bgcolor="#EEEEEE"><td>Dynamic Allocation (usually)</td><td>No dynamic allocation</td></tr>
<tr bgcolor="#CCCCCC"><td>Intrusive (must inherit from the base class)</td><td>Non-intrusive (third-party classes can participate)</td></tr>
<tr bgcolor="#EEEEEE"><td>Reference semantics (think how you copy a vector of pointers to base class?)</td><td>Value semantics (copying is trivial)</td></tr>
<tr bgcolor="#CCCCCC"><td>Algorithm scattered into classes</td><td>Algorithm in one place</td></tr>
<tr bgcolor="#EEEEEE"><td>Language supported (Clear errors if pure-virtual is not implemented)</td><td>Library supported (poor error messages)</td></tr>
<tr bgcolor="#CCCCCC"><td>Creates a first-class abstraction</td><td>It’s just a container</td></tr>
<tr bgcolor="#EEEEEE"><td>Keeps fluent interfaces</td><td>Disables fluent interfaces. Repeated std::visit</td></tr>
<tr bgcolor="#CCCCCC"><td>Supports recursive types (Composite)</td><td>Must use recursive_wrapper and dynamic allocation. Not in the C++17 standard.</td></tr>
<tr bgcolor="#CCCCCC"><td>Adding a new operation (generally) boils down to implementing a polymorphic method in all the classes</td><td>Adding a new operation simply requires writing a new free function</td></tr>
<tr bgcolor="#CCCCCC"><td>Use the Visitor design pattern to get some of the benefits of the right hand side</td><td></td></tr>
</tbody></table>
<br />
std::variant and std::visit idiom resembles closely to pattern matching in functional languages. However, functional languages are leaps and bounds ahead of the current capabilities of the pattern matching idiom.<br />
<ol style="text-align: left;">
<li>Generally, pattern matching makes it easy to dissect a variant type (or even a structured type) by the "shape" of the type and its content. I.e., a more powerful pattern matching in C++ would use <a href="http://en.cppreference.com/w/cpp/language/structured_binding" target="_blank">structured bindings</a> in some way. </li>
<li>Conditional structured bindings would match only if the condition is satisfied. </li>
<li>Matching on the dynamic type of the variable would be really nice but without paying excessive performance cost.</li>
</ol>
For all these reasons, I think this is best done as a language feature as opposed to a library supported capability. At the moment, it's great to have some basic pattern matching capabilities in C++ that allows you to use both of the styles depending on the problem you're trying to solve.<br />
<div>
<br /></div>
<div>
See a detailed example on slideshare.<br />
<br /></div>
<iframe allowfullscreen="" frameborder="0" height="485" marginheight="0" marginwidth="0" scrolling="no" src="//www.slideshare.net/slideshow/embed_code/key/jT0C8yaZZsl02J?startSlide=4" style="border-width: 1px; border: 1px solid #ccc; margin-bottom: 5px; max-width: 100%;" width="595"> </iframe> <br />
<div style="margin-bottom: 5px;">
<strong> <a href="https://www.slideshare.net/SumantTambe/new-tools-for-a-more-functional-c-80294483" target="_blank" title="New Tools for a More Functional C++">New Tools for a More Functional C++</a> </strong> from <strong><a href="https://www.slideshare.net/SumantTambe" target="_blank">Sumant Tambe</a></strong> </div>
<div>
</div>
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com2tag:blogger.com,1999:blog-13960885.post-61457446220302585382017-12-17T12:46:00.001-08:002017-12-17T12:54:54.466-08:00Ground Up Functional API Design in C++<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
There are plenty of reasons why functional APIs look and feel different than more common object-oriented APIs. A tell-tale sign of a functional APIs is existence of <b>a core abstraction</b> and a set of methods with <b>algebraic</b> properties. The abstraction part is of course about being able to talk about just the necessary details and nothing more. The algebraic part is about being able to take one or more instances of the same abstraction and being able to create a new one <b>following some laws</b>. I.e., <i>Lawfully</i> composing smaller parts into a bigger thing that is an instance of the same abstraction the original instances were.<br />
<br />
Composition by itself is nothing new to OO programmers. Composite, Decorator design patterns are all about putting together smaller pieces into something bigger. However, they miss out on the lawful part. Functional paradigm gives you extra guard rails so that you can bake in some well-understood mathematical properties into the abstraction.<br />
<br />
I think most people with even basic OO experience "get" the abstraction part. But the algebraic part, however, needs some thinking, some training, and most importantly some well-made, simple to understand examples.<br />
<br />
Speaking of examples, C++ has already adopted the ranges library as a technical specification (TS). At its core there are lawful algebraic properties. Understanding the functional principles from an industrial implementation is possible but harder. RxCpp is another example. Both libraries use operator overloading, which I think is a convenience and not a core part of the design. My focus today is understandability. So, here's my attempt to demystify the art of <b>lawful algebraic api design</b> with a simple example of data generators. See <a href="https://github.com/sutambe/cpp-generators" target="_blank">cpp-generators</a> on <span id="goog_848078807"></span>github.<br />
<br />
<iframe allowfullscreen="" frameborder="0" height="360" mozallowfullscreen="" src="https://player.vimeo.com/video/247642986" webkitallowfullscreen="" width="640"></iframe>
<br />
This talk presents two classic techniques from the functional domain — composable data generators and property-based testing — implemented in C++14 for testing a generic serialization and deserialization library (RefleX). It presents a systematic technique of constructing data generators from a mere random number generator and random type generation using compile-time meta-programming. The talk describes the laws of monoids, functors, applicative, and monads and how they are implemented in a simple to understand abstraction of data generators.<br />
<br />
Check out <a href="https://www.slideshare.net/SumantTambe/systematic-generation-data-and-types-in-c" target="_blank">Slides</a>. Transcripts below for a quick read.<br />
<br />
<b>2:30</b><br />
This is an attempt to demystify algebraic api design and buzz words like functor, monoid, and monads.<br />
<br />
<b>4:05</b><br />
I wish the book Functional Programming in C++ by Manning had a chapter on algebraic api design like the material covered in this talk.<br />
<br />
<b>7:30</b><br />
Property-based testing---the motivation behind data generators. Testing a serialization and deserialization library (Reflex)<br />
<br />
<b>12:00</b><br />
The <a href="http://rticommunity.github.io/rticonnextdds-reflex/" target="_blank">RefleX</a> library---Compile-time reflection in C++ for DDS-XTypes<br />
<br />
<b>14:30</b><br />
How to test RefleX? What types and data should be used to test RefleX? We'll use property-based testing.<br />
<br />
<b>17:50</b><br />
A code and type generator machinery that hammers the code with unthinkable tests. It is developer's nightmare but also the best friend.<br />
<br />
Progression of the data generator abstraction...<br />
<br />
<b>20:00</b><br />
A simple random number generator---a built-in library function<br />
<br />
<b>22:00 </b><br />
A bool generator, an uppercase character generator---a custom function on top of the library function.<br />
<br />
<b>23:00</b><br />
A generator of random numbers within a range---a function with some state (a closure)<br />
<br />
<b>26:00</b><br />
A <span style="font-family: "courier new" , "courier" , monospace;">oneof</span> generator from an <span style="font-family: "courier new" , "courier" , monospace;">std::initializer_list<t>.</span></div>
</div>
</div>
<br />
<b>28:00</b><br />
A <span style="font-family: "courier new" , "courier" , monospace;">Gen<t></span> template with a <span style="font-family: "courier new" , "courier" , monospace;">generate</span> function. A named type for the function object. It's structurally same as a closure. So it's not more powerful.<br />
<br />
<b>29:00</b><br />
Is a function object (think closures) a sufficient abstraction for all kinds of generators we might need? No.<br />
<div>
<br /></div>
<b>31:30</b><br />
Now a much farther jump into abstraction level---a composable generator---an algebraic generator with methods such as <span style="font-family: "courier new" , "courier" , monospace;">map, concat, reduce, zip, where</span>.<br />
<br />
<b>33:00</b><br />
Composition is not going to be arbitrary. It will be governed by some well-known rules (laws). These are guard rails.<br />
<br />
<b>34:45</b><br />
Mapping over a generator. Composition of a primitive generator and a mapping function gives another generator.<br />
<br />
<b>36:48</b><br />
An excellent question from the audience. Why is the while loop infinite? The reason is that we've not seen termination as a requirement for the generators. It later become important to make sure the generator abstraction is a well-behaved monoid. To satisfy the monoid laws, especially the identity law, we've to have an empty generator and a way to convey that a generator ended. Hence we introduce termination in the core abstraction. Guard rails and all...<br />
<br />
<b>37:30</b><br />
Introducing Functor---you can map over it. Functor laws. Composition law and the identity law.<br />
<br />
<b>40:30</b><br />
Implementing the map function for generator<br />
<br />
<b>42:30</b><br />
Overloading lvalue and rvalue reference qualified function (e.g., map) for fluent api. Algebraic APIs commonly implemented using the <a href="https://en.wikipedia.org/wiki/Fluent_interface" target="_blank">Fluent Interface</a> technique generates a number of temporary objects. The overhead of temporary objects can be eliminated using move semantics. You can overload functions specifically for temporary objects (rvalues) using rvalue reference qualification.<br />
<br />
<b>44:00</b><br />
Introducing Monoid---The fundamental ability to combine smaller generators to create a bigger generator. Identity law---appending an empty generator gives back the original generator. Without an empty generator it's not a monoid because identity law is not satisfied yet. A notion of termination must be introduced. We do that by just throwing an exception <span style="font-family: "courier new" , "courier" , monospace;">std::out_of_range</span>.<br />
<br />
<b>50:00</b><br />
Associative law of Monoid. Grouping does not matter.<br />
<br />
<b>53:00</b><br />
Introducing Applicatives: Zipping generators. Implementation of zip_with. Generator is an applicative.<br />
<br />
<b>56:30</b><br />
Introducing Monad to handle dependent generators. Generator of generators come up often. <span style="font-family: "courier new" , "courier" , monospace;">concat_map</span> flattens nested generators. Monad laws.<br />
<br />
<b>1:03:00</b><br />
Recapping algebraic api design based on mathematical abstractions. Algebra = a first-class lawful abstraction + compositional api.<br />
<br />
<b>1:06:00</b><br />
Catagory theoretic <i>intuition</i> is much a deeper thing. I'm not sure I get it. For example, intuitively understanding "Monad is just a monoid in the category of endofunctors".<br />
<br />
<b>1:08:00</b><br />
We can generate random types at compile-time if we can generate random numbers at compile-time.<br />
<br />
<b>1:10:00</b><br />
Generating random numbers at compile-time. A 16-bit <a href="https://en.wikipedia.org/wiki/Linear-feedback_shift_register" target="_blank">Linear Feedback Shift Register</a> (LFSR) constexpr function.<br />
<br />
<pre class="brush:cpp">constexpr int LFSR_bit(int prev) {
return (((prev >> 0) ^ (prev >> 2) ^
(prev >> 3) ^ (prev >> 5)) & 1);
}
constexpr int LFSR(int prev) {
return ((prev >> 1) | (LFSR_bit(prev) << 15));
}
</pre>
<br />
<b>1:13:30</b><br />
Random type generation at compile-time using a recursive TypeMap and an LFSR. See <a href="https://github.com/sutambe/cpp-generators/blob/master/include/type_generator.h" target="_blank">type_generator</a>.<span id="goog_848078831"></span><br />
<br />
<b>1:20:00</b><br />
Generating a random 51 levels deep nested tuple or worse a tuple of static size 2.7 MB. Test your generic library with monster types.</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com2tag:blogger.com,1999:blog-13960885.post-38027285223016127732017-12-10T00:14:00.000-08:002017-12-10T09:03:47.032-08:00The video of New Tools for a More Functional C++<div dir="ltr" style="text-align: left;" trbidi="on">
My previous talk on <a href="http://cpptruths.blogspot.com/2017/09/new-tools-for-more-functional-c.html" target="_blank">New Tools for a More Functional C++</a> ran into some audio issue during the <a href="https://www.meetup.com/ACCU-Bay-Area/events/242787015/" target="_blank">meetup</a>. I did not upload the video back then because it had no audio what-so-ever. I finally got around to record the audio track for the talk and I mixed it with the video. So here is the final video. Have fun with FP in C++!<br />
<br />
If you don't have 35 minutes, checkout the partial video transcripts below.<br />
<br />
<iframe allowfullscreen="" frameborder="0" height="360" mozallowfullscreen="" src="https://player.vimeo.com/video/246623471" webkitallowfullscreen="" width="640"></iframe>
<a href="https://vimeo.com/246623471">Functional Programming Tools in C++</a> from <a href="https://vimeo.com/user29254745">Sumant Tambe</a> on <a href="https://vimeo.com/">Vimeo</a>.<br />
<br />
<h3 style="text-align: left;">
Video Transcripts</h3>
<b>00:16</b><br />
<div class="MsoNormal">
<o:p></o:p></div>
<div class="MsoNormal">
We’re going to talk about functional [programming] tools in
C++ and what new capabilities exist in modern C++. <o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>2:00</b></div>
<div class="MsoNormal">
<o:p></o:p></div>
<div class="MsoNormal">
I'm reviewing <a href="https://www.manning.com/books/functional-programming-in-cplusplus">Functional
Programming in C++ book</a> by Manning---a good book for C++ programmers to acquire beginner to
intermediate level knowledge of FP in C++.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>2:30</b><o:p></o:p></div>
<div class="MsoNormal">
Sum types and (pseudo) pattern matching in C++<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>5:00</b><o:p></o:p></div>
<div class="MsoNormal">
Modeling a game of Tennis using <span style="font-family: "courier" , serif;">std::variant<normalscore advantagescore="" deucescore="" gamecompletescore=""></normalscore></span><o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-size: 12pt;"><b>7:30</b></span></div>
<div class="MsoNormal">
<b><o:p></o:p></b></div>
<div class="MsoNormal">
<span style="font-family: "courier" , serif;">std::visit</span>
spews blood when you miss a case in the visitor. See an example. Therefore, language-supported
pattern matching is much more preferable than library support for the same.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>9:00<o:p></o:p></b></div>
<div class="MsoNormal">
Passing overloaded lambdas to <span style="font-family: "courier new" , "courier" , monospace;">std::visit</span>---the fancy way to
create a visitor. User-defined deduction guides for overloading from lambdas.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>13:00<o:p></o:p></b></div>
<div class="MsoNormal">
Algorithms implemented using pattern matching style tend to
concentrate the entire algorithm in a function as opposed to object-oriented
programming style where the algorithm is spread in multiple classes and
potentially multiple files.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>15:00<o:p></o:p></b></div>
<div class="MsoNormal">
Sharing state become much easier with inheritance as opposed
to <span style="font-family: "courier new" , "courier" , monospace;">std::variant</span> based decomposition.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>18:05<o:p></o:p></b></div>
<div class="MsoNormal">
Too much ceremony in std::variant approach as you have to
call <span style="font-family: "courier new" , "courier" , monospace;">std::visit </span>and pass a visitor to it. In object-oriented style, it is just
a call to a function and hence it’s very succinct. <o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>19:00 <o:p></o:p></b></div>
<div class="MsoNormal">
Recursive <span style="font-family: "courier new" , "courier" , monospace;">std::variant </span>is not possible without recursive_variant.<span style="font-family: "courier new" , "courier" , monospace;">
<b>std::variant</b></span><b> is a container not an abstraction.</b> <span style="font-family: "courier new" , "courier" , monospace;">std::variant </span>alone isn’t
sufficient to implement algebraic data types or the Composite design pattern.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>21:00</b><o:p></o:p></div>
<div class="MsoNormal">
<span style="font-family: "courier new" , "courier" , monospace;">std::variant</span> disables fluent interfaces.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>22:00<o:p></o:p></b></div>
<div class="MsoNormal">
A summary of differences between inheritance and
std::variant –based modeling alternatives in C++.<o:p></o:p></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://3.bp.blogspot.com/-Isk1cEoB9nk/WizpWYIOO1I/AAAAAAAACeM/nUz_On1QDPMBw0GysKHLdVkOLmYmlNJAQCLcBGAs/s1600/Screen%2BShot%2B2017-12-09%2Bat%2B11.24.38%2BPM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="941" data-original-width="1600" height="376" src="https://3.bp.blogspot.com/-Isk1cEoB9nk/WizpWYIOO1I/AAAAAAAACeM/nUz_On1QDPMBw0GysKHLdVkOLmYmlNJAQCLcBGAs/s640/Screen%2BShot%2B2017-12-09%2Bat%2B11.24.38%2BPM.png" width="640" /></a></div>
<div align="center" class="MsoNormal" style="text-align: center;">
<span style="mso-no-proof: yes;"><!--[if gte vml 1]><v:shape id="Picture_x0020_2"
o:spid="_x0000_i1025" type="#_x0000_t75" style='width:406pt;height:239pt;
visibility:visible;mso-wrap-style:square'>
<v:imagedata src="file:////Users/sutambe/Library/Group%20Containers/UBF8T346G9.Office/msoclip1/01/clip_image003.png"
o:title=""/>
</v:shape><![endif]--><!--[if !vml]--><!--[endif]--></span><o:p></o:p></div>
<div align="center" class="MsoNormal" style="text-align: center;">
<br /></div>
<div class="MsoNormal">
<b>23:00<o:p></o:p></b></div>
<div class="MsoNormal">
Deep Immutability in C++. C++ const is shallow. A raw pointer does not forward
const-ness, <span style="font-family: "courier new" , "courier" , monospace;">propagate_const </span>does. You can now implement deep Immutability in C++
using propagate_const<t>. <o:p></o:p></t></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>26:00<o:p></o:p></b></div>
<div class="MsoNormal">
A class containing propagate_const is not copy-assignable. This
is consistent with basic C++ rule that a pointer to const can’t be assigned to
pointer to non-const. <o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>27:30<o:p></o:p></b></div>
<div class="MsoNormal">
Mutable temporaries in C++. Yes, temporaries can be
modified. Modern C++ provides ways to control this. See why you may need <span style="font-family: "courier" , serif;">std::move(*this);</span>.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>29:00<o:p></o:p></b></div>
<div class="MsoNormal">
The Named Parameter Idiom---an example of fluent interface
in C++. <o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>31:00<o:p></o:p></b></div>
<div class="MsoNormal">
Avoid constructing unnecessary temporary objects when fluent
interfaces are used with immutable objects. <o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>33:45</b></div>
<div class="MsoNormal">
How to disambiguate between r-value reference qualified
functions and l-value reference qualified functions. *this in a r-value
qualified function is a l-value. The trick is to return a r-value reference to
*<span style="mso-bidi-font-weight: bold;">this. Hence <span style="font-family: "courier new" , "courier" , monospace;">std::move(*</span></span><span style="font-family: "courier new" , "courier" , monospace;">this)</span>,
which is a simply a cast.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>35:00</b></div>
<div class="MsoNormal">
Thank you!</div>
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com1tag:blogger.com,1999:blog-13960885.post-20632646041521867042017-09-29T09:10:00.002-07:002017-09-29T09:10:32.576-07:00New Tools for a More Functional C++<div dir="ltr" style="text-align: left;" trbidi="on">
I presented the following slide deck at the ACCU meetup yesterday.<br />
<br />
<iframe src="//www.slideshare.net/slideshow/embed_code/key/jT0C8yaZZsl02J" width="595" height="485" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> <div style="margin-bottom:5px"> <strong> <a href="//www.slideshare.net/SumantTambe/new-tools-for-a-more-functional-c-80294483" title="New Tools for a More Functional C++" target="_blank">New Tools for a More Functional C++</a> </strong> from <strong><a href="https://www.slideshare.net/SumantTambe" target="_blank">Sumant Tambe</a></strong> </div>
<br />
Abstract: Variants have been around in C++ for a long time and C++17 now has std::variant. We will compare inheritance and std::variant for their ability to model sum-types (a fancy name for tagged unions). We will visit std::visit and discuss how it helps us model the pattern matching idiom. Immutability is one of the core pillars of Functional Programming (FP). C++ now allows you to model deep immutability; we'll see a way to do that using the standard library. We'll explore if `return std::move(*this)` makes any sense in C++. Immutability may be a reason for that. </div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com3tag:blogger.com,1999:blog-13960885.post-18560012817639063772017-08-13T09:09:00.000-07:002017-08-13T09:09:29.431-07:00Binding std::function to member functions <div dir="ltr" style="text-align: left;" trbidi="on">
I realized that std::function can be bound to member functions without requiring the *this object. Consider the following examples.
<pre class="brush:cpp">
// std::string::empty is a const function. All variables from e1 to e5 are fine.
std::function<bool(std::string)> e1 = &std::string::empty;
std::function<bool(std::string &)> e2 = &std::string::empty;
std::function<bool(const std::string &)> e3 = &std::string::empty;
std::function<bool(std::string *)> e4 = &std::string::empty;
std::function<bool(const std::string *)> e5 = &std::string::empty;
// std::string::push_back is not a const function. p4 and p5 don't compile.
std::function<void(std::string, char)> p1 = &std::string::push_back;
std::function<void(std::string &, char)> p2 = &std::string::push_back;
std::function<void(std::string *, char)> p3 = &std::string::push_back;
// These two don't compile because push_back is a non-const function
std::function<void(const std::string &, char)> p4 = &std::string::push_back;
std::function<void(const std::string *, char)> p5 = &std::string::push_back;
</pre>
I thought I knew how to do that but this time I found that the syntax is a little different than what I had in mind.
<br/><br/>
I used tho think (incorrectly) that just like function types for free-standing functions, one would create a member-function type. While, it's straight-forward to create function types for free-standing functions, I think it's not possible to create member function types. Don't get me wrong. One can create pointer-to-member-function type just like pointer-to-a-function type. Here's what I mean.
<pre class="brush:cpp">
using F = int(const char *); // a function type of a free standing function.
F f = std::atoi; // error because a there are no instances of a function type.
F* fnew = new F(); //error because new can't be applied to a function type.
F* fptr = &std::atoi; // OK. A pointer to a function type is initialized.
// However, there's no function type for member functions
using GPTR = bool (std::string::*)() const; // OK. This is a pointer-to-member-function-type.
GPTR gptr = &std::string::empty; // OK. This is a pointer to a member function.
string s;
std::cout << (s.*gptr)(); // OK. prints 1
using H = decltype(*gptr); // error. It makes no sense without a std:string object. Illformed.
bool (*x)(const std::string &) = gptr; // error. Incompatible types.
std::function<bool (const std::string &)> fobj = gptr; // OK! Neat!
</pre>
Therefore, std::function uses the syntax of free-standing function types to bind to pointer to member functions. That's neat.
<br /></div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com1tag:blogger.com,1999:blog-13960885.post-39822247746522021802017-08-06T09:36:00.001-07:002017-08-09T09:45:03.433-07:00Avoiding intermediate copies in std::accumulate<div dir="ltr" style="text-align: left;" trbidi="on">
std::accumulate makes a ton of copies internally. In fact it's 2x the size of the number of elements in the iterator range. To fix, use std::ref and std::reference_wrapper for the initial state. std::shared_ptr is also a possibility if the accumulated state must be dynamically allocated for some reason. Live code on <a href="https://wandbox.org/permlink/a6DcJEJ7t0Yc7gk4">wandbox</a>.
<br/><br/>
Update: Please see alternative solutions in the comments section.
<br/><br/>
<pre class="brush:cpp">
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <functional>
struct Vector : public std::vector<int> {
Vector(std::initializer_list<int> il) : std::vector<int>(il){
std::cout << "Vector(std::initializer_list)\n";
}
Vector() {
std::cout << "Vector()\n";
}
Vector(const Vector &v) : std::vector<int>(v) {
std::cout << "Vector(const Vector &)\n";
}
Vector & operator = (const Vector &v) {
if (this != &v) {
std::vector<int>::operator=(v);
std::cout << "Vector& Vector::operator=(const Vector &)\n";
}
return *this;
}
Vector & operator = (Vector && v) {
if (this != &v) {
std::vector<int>::operator=(std::move(v));
std::cout << "Vector& Vector::operator=(Vector&&)\n";
}
return *this;
}
Vector(Vector&& v) : std::vector<int>(std::move(v)) {
std::cout << "Vector(Vector&&)\n";
}
};
void copy_accumulate(Vector &v) {
Vector v2 = std::accumulate(v.begin(), v.end(), Vector(),
[](Vector & v, int i) {
v.push_back(i);
return v;
});
std::cout << "size of v2 = " << v2.size() << "\n";
}
void nocopy_accumulate(Vector &v) {
Vector init;
Vector v2 = std::accumulate(v.begin(), v.end(), std::ref(init),
[](std::reference_wrapper<Vector> v, int i) {
v.get().push_back(i);
return v;
});
std::cout << "size of v2 = " << v2.size() << "\n";
}
int main()
{
Vector v { 1, 2, 3, 4 };
copy_accumulate(v);
std::cout << "=============\n";
nocopy_accumulate(v);
}
</pre>
<br /></div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com4tag:blogger.com,1999:blog-13960885.post-47659123868324912832017-07-09T16:21:00.001-07:002017-07-09T16:42:58.118-07:00Playing with C++ Coroutines<div dir="ltr" style="text-align: left;" trbidi="on">
While looking for some old photos, I stumbled upon my own presentation on C++ coroutines, which I never posted online to a broader audience. I presented this material in <a href="https://www.meetup.com/ACCU-Bay-Area/events/225772179/">SF Bay ACCU meetup</a> and at the <a href="https://www.meetup.com/Joy-of-Programming-DC/events/228620830/">DC Polyglot meetup</a> in early 2016! Yeah, it's been a while. It's based on much longer blogpost about <a href="https://blogs.rti.com/2015/12/08/modern-asynchronous-requestreply-with-dds-rpc/">Asynchronous RPC using modern C++</a>. So without further ado.</div>
<br/><br/>
<div style="text-align: center;">
<iframe src="//www.slideshare.net/slideshow/embed_code/key/Cy1k7747Pz8Ib5" width="595" height="485" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> <div style="margin-bottom:5px"> <strong> <a href="//www.slideshare.net/SumantTambe/c-coroutines" title="C++ Coroutines" target="_blank">C++ Coroutines</a> </strong> from <strong><a target="_blank" href="https://www.slideshare.net/SumantTambe">Sumant Tambe</a></strong> </div></div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-10003674227043335712017-01-06T06:21:00.000-08:002017-01-06T06:21:00.448-08:00Folding Monadic Functions<div dir="ltr" style="text-align: left;" trbidi="on">
In the previous two blog posts (<a href="http://cpptruths.blogspot.in/2016/12/understanding-fold-expressions.html">Understanding Fold Expressions</a> and <a href="http://cpptruths.blogspot.in/2016/12/folding-functions.html">Folding Functions</a>) we looked at the basic usage of C++17 fold expressions and how simple functions can be folded to create a composite one. We’ll continue our stride and see how "embellished" functions may be composed in fold expressions.
<br/><br/>
First, let me define what I mean by embellished functions. Instead of just returning a simple value, these functions are going to return a generic container of the desired value. The choice of container is very broad but not arbitrary. There are some constraints on the container and once you select a generic container, all functions must return values of the same container. Let's begin with std::vector.
<br/>
<pre class="brush:cpp">
// Hide the allocator template argument of std::vector.
// It causes problems and is irrelevant here.
template <class T>
struct Vector : std::vector<T> {};
struct Continent { };
struct Country { };
struct State { };
struct City { };
auto get_countries = [](Continent& c) -> Vector<Country> { return ... } ;
auto get_states = [](Country& c) -> Vector<State> { return ... };
auto get_cities = [](State& s) -> Vector<City> { return ... };
</pre>
The focus of this post is folding functions like get_countries, get_states, and get_cities. As you may have noted, these functions are different from what we saw in the previous post. They don’t readily compose. The return types and argument types don’t line up. But I bet you know how to get to the cities given a Continent. Don’t you? Hold on to that intuition. It will come in handy later. In essence, my attempt is going to formalize that intuition of yours while generalizing it by leaps and bounds. Possibly, beyond recognition.
<br/><br/>
Our target here is to enable folding (a.k.a. composition) of these embellished functions similar to the compose function we saw in the previous post. We’ll call it composeM though.
<br/>
<pre class="brush:cpp">
Continent c;
auto cities_from_continent = composeM(get_countries, get_states, get_cities);
Vector<City> cities = cities_from_continent(c);
</pre>
Let’s begin by implementing composeM using a unary left fold. Let’s use the >>= operator because we can. Of course, we’ll also need to overload >>= for our embellished functions.
<pre class="brush:cpp">
template <class... Args>
auto composeM(Args&&... args)
{
return (... >>= args);
}
template <class F, class G>
auto operator >>= (F&& f, G&& g)
{
using FArg = arg_type_t<F>;
using GResult = result_type_t<G>;
return [f,g] (FArg a) -> GResult {
using FResult = result_type_t<F>;
GResult finalvec;
FResult const & fvec = f(a);
for(const auto& o: fvec) {
const GResult& gvec = g(o);
finalvec.insert(finalvec.end(), gvec.begin(), gvec.end());
}
return finalvec;
};
}
</pre>
What a nasty function is that!?
<br/><br/>
Now would be a good time to recall the intuition you had about going from a Continent to it's cities. Your intuition about implementing cities_from_continent is probably as follows. This algorithm goes all three levels in one function (with three nested loops).
<ol>
<li>Get a Continent from somewhere. Initialize an empty vector of cities.</li>
<li>Call get_countries (level 1)</li>
<li>Call get_states for each country (level 2)</li>
<li>Call get_cities for each state (level 3) and push_back in the vector of cities</li>
<li>Return the vector of cities</li>
</ol>
On the other hand, the overloaded >>= function implements the same intuition with only two levels at a time (as it accepts only two functions as parameters). Going three levels requires operator >>= to be called twice. C++ compiler will do that for us because we're using the fold expression in composeM. Every time compiler calls operator >>= it returns a function that's <i>just like</i> it received as arguments. Specifically, the returned closure is not a generic. We find out the argument type of F (FArg) and result type of G (GResult) and use them in the definition of the lambda. The returned closure is a composite because it accepts F's argument type and returns G's result type. It glues F and G together. All that ceremony is kinda important.
<br/><br/>
When operator >>= is called the first time, F is of type Continent→Vector<Countries> (i.e., get_countries) and G is of type Country→Vector<State> (i.e., get_states). The first time around, the signature of the closure is going to be Continent→Vector<State>. It's just "like" the other two. Naturally, when this closure is composed with get_cities, operator >>= works smoothly and returns a closure of type Continent→Vector<City>, which is exactly the same as cities_from_continent you intuitively had in mind.
<br/><br/>
An important difference between the direct function and the function that's the result of composition is that the composed version materializes (creates) a temporary vector every time operator >>= is called. That's an overhead. There are ways to avoid that but we may have to consider something other than std::vector. I won't discuss that here. See Range-v3.
<br/><br/>
<span style="font-size: large;"><b>Another Example: boost::future</b></span>
<br/><br/>
So far we've looked at composition of embellished functions that accept an argument and return a vector of some type. At the beginning of the article, I suggested that there is broad set of generic containers we can choose from. Now would be a good time to select another one. How a about boost::future? We'll go through a similar exercise of compositing function that return boost::future. We'll see if there's anything common in the composition of functions that return vectors and functions that return futures.
<br/><br/>
Let's imagine there's a database that contains information about the largest countries, states, and cities in the world. As database operations are i/o bound, using futures to communicate the possibility of long execution times is a good idea. So our function look like as follows.
<pre class="brush: cpp">
auto get_largest_country = [](Continent const &) -> boost::future<Country> { ... };
auto get_largest_state = [](Country const &) -> boost::future<State> { ... };
auto get_largest_city = [](State const &) -> boost::future<City> { ... }
</pre>
If we need the largest city in the largest state of the largest country of a given continent we'll need all the three functions. As before, you have an intuition behind how to do that. May be it's something like below.
<ol>
<li>Get a Continent from somewhere.</li>
<li>Call get_largest_country (level 1). Wait to retrieve the result because db ops could take long.</li>
<li>Call get_largest_state for that country (level 2). Wait again.</li>
<li>Call get_largest_city for that state (level 3). Wait again.</li>
<li>Return the city</li>
</ol>
The actual code is pretty short.
<pre class="brush: cpp">
auto get_largest_city_from_continent = [](Continent const &c) {
return get_largest_city(get_largest_state(get_largest_country(c).get()).get()).get();
};
</pre>
This implementation is fully synchronous and isn't optimized to use nice properties of boost::future (yet). It may remind you of function composition we saw in the <a href="http://cpptruths.blogspot.com/2016/12/folding-functions.html">previous</a> post. However, the .get() calls in between completely mess things for us. We can't use simple function composition because it does not call .get().
<br/><br/>
Let's rewrite operator >>= that would work with functions that return boost::future. We want to compare it with that of the Vector type.
<pre class="brush: cpp">
template <class F, class G>
auto operator >>= (F&& f, G&& g)
{
using FArg = arg_type_t<F>;
using GResult = result_type_t<G>;
return [f,g] (FArg a) -> GResult {
return g(f(a).get());
};
}
</pre>
Just like before, this function operates only two levels at a time because we pass only two functions to it. The implementation is much simpler than before because the argument functions return a boost::future and it may contain at most one value. We retrieve it using .get() and pass it on to function g.
<br/><br/>
Needless to say this implementation of >>= does not look much like the earlier (Vector) implementation of operator >>=. Is there anything common/reusable at all? Can we refactor these two functions into something reusable? Let's observe them closely under a special microscope--generic programming microscope.
<br/><br/>
<span style="font-size: large;"><b>Refactoring To a Generic operator >>=</b></span>
<br/><br/>
Disclaimer: This section may appear a little too abstract and hand-wavy. As I already know how the refactoring is going to look like, I may skip ahead too fast and may be too hasty about some generalizations. Let me know what you think. Here we go.
<br/><br/>
Here's what I see in the implementations of operator >>=
<ol>
<li>Both functions are higher-order. I.e. they take functions as arguments and return a new composite function.</li>
<li>The type of the composite function depends on the types of the arguments. Specifically, the composite function is "just like" the argument functions. </li>
<li>In both cases, the argument type of the composite function is the same as that of F and the return type is the same as that of G.</li>
<li>Function f and g accept an argument of a simple type and return a value "wrapped" in a generic container. The notable difference is of the container type (Vector and boost:future, respectively). Hmm, template template parameter? </li>
<li>There's a dependency between f and g. f is invoked before g. Always. That's generic. This is key.</li>
<li>The argument passed to the composite function is passed to f (i.e., f(a)). As the return value of f is a generic container, the contained value(s) are somehow extracted and passed to g. In the case of Vector we use a for loop and in the case of boost::future, we use .get(). The specific way to get to the guts of the container is dependent on the container type. The composite function "collapses" two nested levels into one. In the case of Vector, two nested loops. In the case of boost::future, two calls to the database appear as one from outside. These things are very very specific to the container. There's no hope to generalize it. This is key too and the most hand-wavy observation.</li>
</ol>
What in the world all this means? And how we might express these observations in C++ in a reusable manner? Not all is reusable as we observed. Items #1 to #5 appear something like we can write reusable code for. #6 does not as the details depend on the container type---a template (as opposed to an instantiation of it).
<br/><br/>
Sounds like we need a template template parameter. Fine. But a template template parameter of what?
<br/><br/>
<span style="font-size: large;"><b>The Genius of Monad</b></span>
<br/><br/>
So what we are looking for is known as a monad. That's the name it gets because mathematicians reached here first--long before we programmers existed. Let's just accept the name and move on.
<br/><br/>
Based on the commonalities listed above, we need something with nearly the same capabilities except for #6. It should allow to plug an implementation that is dependent on the container type. We are in pursuit of a monad-aware implementation of operator >>=. As #1 through #5 are reusable pieces of code, let's just copy-paste them.
<pre class="brush: cpp">
template <class F, class G>
auto operator >>= (F&& f, G&& g)
{
using FArg = arg_type_t<F>;
using GResult = result_type_t<G>;
return [f,g] (FArg a) -> GResult {
return get_monad<GResult>::bind(f(a), std::move(g));
};
}
</pre>
Hopefully, it does not look too unexpected.
<br/><br/>
As you can see, this implementation has the same shape but with more flexibility. It's higher-order. Returns a closure that accepts argument of the same type as F and returns the type as G. It invokes f(a). From this point on things look different. The pluggable "interface" we use is called bind. The result of f(a) is passed to bind which is dependent on type GResult. Further function g is also passed to bind because a generic implementation won't know how to peek into the value of f(a) and invoke g on it. That's the job of bind. So there must be specializations of bind for each container template. But first, we need to identify the container template. We use a template template parameter.
<br/><br/>
Here's how get_monad looks like.
<br/>
<pre class="brush: cpp">
template <class T>
struct get_monad;
template <template <typename> class M, class T>
struct get_monad<M<T>> : monad<M> {};
</pre>
It is a simple wrapper over the real deal: monad. The job of get_monad is to pattern-match on GResult and extract the template-name and template arguments out. It simply forwards the template-name to the monad template. I.e., In case of get_monad<Vector<City>>, monad is instantiated with just Vector as in monad<Vector>. Similarly, for the function returning boost::future, monad<boost::future> is instantiated.
<br/><br/>
That brings us to the monad template, which accepts a template template parameter.
<pre class="brush: cpp">
template<template <typename> class M>
struct monad
{
template <class T, class Func>
static auto bind(M<T>& m, Func&& func) -> result_type_t<Func>;
};
</pre>
This definition only serves as an "interface" and does no work. It's completely optional. Note the signature of bind though. It accepts an argument of type M<T>, whatever M is. We'll look at two examples shortly. It also accepts a function, which must also return M<T>. Bind calls one embellished function at a time. At this point, what we really need are the specializations of this template. Here's a monad specialization for Vector.
<pre class="brush: cpp">
template<>
struct monad<Vector>
{
template <class T, class Func>
static auto bind(const Vector<T>& vec, Func&& func) -> result_type_t<Func>
{
// Alternatively,
// using Outer = decltype(func(std::declval<T>()));
using Outer = result_type_t<Func>;
Outer outer;
for(const T& o: vec) {
const Outer& inner = func(o);
outer.insert(outer.end(), inner.begin(), inner.end());
}
return outer;
}
};
</pre>
The bind function accepts a Vector object and a function as arguments. The job of bind is to unwrap the Vector, get the values, and pass them to the function. That's just half the story. The function itself returns a Vector for every call. bind can return only one Vector. Therefore, bind needs to combine/flatten all the Vectors into one. The outer Vector is that flat Vector, which contains all the elements from the individual Vectors received from func. Note that if if the input vector is empty, the resulting vector is also empty. Likewise, if the function func returns empty Vectors every-time, the resulting Vector is also empty. This behavior is exactly same as commonly discussed list monad.
<br/><br/>
And here's a possible implementation using boost::future.
<pre class="brush: cpp">
template<>
struct monad<boost::future>
{
template <class T, class Func>
static auto bind(boost::future<T> fut, Func&& func) -> result_type_t<Func> {
return func(fut.get());
}
};
</pre>
Like the Vector version, future version also accepts an object of future type (i.e., the container type) and a function. The bind function extracts the value out from the future by calling get. Only bind would know how to do that. It passes it on to the function. The function itself returns a future. We simply return it. This version is fully synchronous and wait for the result of the first function to arrive before calling the next function. Recall that fut is the result of calling f(a) in operator >>=.
<br/><br/>
The bind function is not unique and it may be implemented in multiple ways. A better alternative with boost::future is to chain the result one future to a subsequent function. In fact, that's what we've been doing all along. boost::future provides a nice api called .then to chain embellished functions that return futures. Therefore, an alternative implementation of monad<boost::future>::bind could be as follows.
<pre class="brush: cpp">
#define BOOST_THREAD_PROVIDES_FUTURE_CONTINUATION
#define BOOST_THREAD_PROVIDES_FUTURE_UNWRAP
#define BOOST_THREAD_PROVIDES_FUTURE
#include <boost/thread/future.hpp>
template<>
struct monad<boost::future>
{
template <class T, class Func>
static auto bind(boost::future<T> fut, Func&& func) -> result_type_t<Func> {
return fut.then([func](boost::future<T> f) mutable {
return func(f.get()); // calling .get here does not block.
}).unwrap();
}
};
</pre>
The boost::future::then function is very similar to bind. The main difference is that the argument lambda to .then accepts a boost::future object as opposed the value in it. This complication is to support the possibility of futures that complete with an exception. If the first method (f) returns a future that resolves into an error, we may need to know about it. If a future resolves to an error, .get() rethrows the exception skipping all the subsequent chained functions. That's exactly what we want.
<br/><br/>
There's one more wrinkle that isn't clear in the code. .then wraps the return type of the lambda in a future. In our case the lambda returns a future itself. (e.g., future<State>). Therefore, the resulting type of .then is future<future<T>>. That does not match with that of bind, which is just future<T>. There're two ways out provided by boost::future. Either you can call .unwrap on future<future<T>> or rely on the unwrapping constructor of boost::future that auto converts future<future<T>> to future<T>. I opted for the former for clarity.
<br/><br/>
<span style="font-size: large;"><b>Putting It All Together</b></span>
<br/><br/>
With this refactoring in place, our composeM function that does a left fold of embellished functions works just fine.
<pre class="brush: cpp">
void test()
{
auto get_cities_from_continent = composeM(get_countries, get_states, get_cities);
auto get_largest_city_from_continent = composeM(get_largest_country, get_largest_state, get_largest_city);
Continent c;
auto cities = get_cities_from_continent(c);
auto largest_city = get_largest_city_from_continent(c).get();
std::cout << cities << "\n" << largest_city << "\n";
}
</pre>
That's pretty neat. The type of the container does not matter. We successfully abstracted the details of the container type in to it's respective bind functions. For new generic containers, all we need to do is to implement a specialization of bind. Bind is the function that allows us to compose (a.k.a. chain) a set of embellished functions belonging to the same container type (monad). As long as an implementation of bind satisfying the signature exists for a container, we can use it in fold expressions. Clearly, C++ fold expressions are quite versatile. As an exercise, try implementing bind for std::optional. It's fun! Find out what monad that is.
<br/><br/>
<span style="font-size: large;"><b>Something's Amiss?</b></span>
<br/><br/>
If you are familiar with the concept of a monad from Haskell or other languages, you know already that the monad abstraction presented above is not complete. It's missing a function called return (Haskell lingo), that accepts a unwrapped value and puts it into the chosen generic container (monad). Obviously, it is highly specific to the container used. Putting a value in a future differs significantly from putting a value in a Vector.
<br/><br/>
I'm unsure if we really need a function like return because we just have constructors in C++ to do the job. For the sake of completeness, however, I will include it.
<pre class="brush:cpp">
template<>
struct monad<Vector>
{
template <class T>
static Vector<std::decay_t<T>> return_(T&& t) {
Vector<std::decay_t<T>> vec;
vec.push_back(std::forward<T>(t));
return vec;
// return { t }; // gcc hates this line.
}
....
};
template<>
struct monad<boost::future>
{
template <class T>
static boost::future<std::decay_t<T>> return_(T&& t) {
return boost::make_ready_future(std::forward<T>(t));
}
....
};
</pre>
Note that the type of return_ matches with that of our embellished functions. As return_ does not do anything but "put a value into the monad", we can use it as the identity for monadic function composition. Let's use a binary left fold as a demonstration.
<pre class="brush:cpp">
template <class Head, class... Tail>
struct head {
using type = Head;
};
template <class... Args>
auto composeM(Args&&... args)
{
static_assert(sizeof...(Args) > 0);
using Func = typename head<Args...>::type;
using FArg = arg_type_t<Func>;
auto identity = [](FArg a) {
return get_monad<result_type_t<Func>>::return_(a);
};
return (identity >>= ... >>= args);
}
</pre>
This implementation of composeM works as long as there's at least one function is passed to it. That's because composeM won't know which monad you are talking about without looking at at least one of them in the return type of the passed function. identity simply forwards its argument to the return_ function. It cheats a little in the process. It finds out the argument_type of Func (FArg). That's not strictly necessary---especially if we use generic lambdas and simply forward the argument to bind. If we do that, we need a few tweaks in operator >>=.
<br/><br/>
On a closer examination, it's clear that operator >>= does not depend on the argument type at all. It only needs to figure out the container type---the template template parameter to use to pull-in the right monad. So, GResult is all we need.
<br/><br/>
Here's the final revised version of operator >>= for folding monadic functions.
<pre class="brush:cpp">
template <class F, class G>
auto operator >>= (F&& f, G&& g)
{
//using FArg = arg_type_t<F>; not needed
using GResult = result_type_t<G>;
return [f=std::forward<F>(f),
g=std::forward<G>(g)] (auto&& a) mutable -> GResult {
return get_monad<GResult>::bind(f(std::forward<decltype(a)>(a)), std::forward<G>(g));
};
}
</pre>
Oh, I almost forgot. The choice of operator >>= is not an accident. In Haskell >>= works the same way as our bind function. On the other hand, operator >>= is like Haskell's fish operators (>=> for right fish and <=< for left fish).
<br/><br/>
That's it! If you are still here, thank you for reading. Here's <a href="http://melpon.org/wandbox/permlink/GwNGPIdKNEGnoWLE">live code</a> if you take it for a spin. This concludes the three part series on C++17 Fold Expressions. See previous posts: #<a href="http://cpptruths.blogspot.in/2016/12/understanding-fold-expressions.html">1</a> and #<a href="http://cpptruths.blogspot.in/2016/12/folding-functions.html">2</a>.
<br/><br/>
<span style="font-size: large;"><b>Appendix</b></span>
<br/><br/>
Here're the templates to extract argument and result types of lambdas. They don't work with generic lambdas though.
<pre class="brush:cpp">
namespace detail {
template <typename Func>
struct function_traits {
using arg_type = typename function_traits<decltype(&Func::operator())>::arg_type;
using result_type = typename function_traits<decltype(&Func::operator())>::result_type;
};
template <typename Func>
struct function_traits<Func &> {
using arg_type = typename function_traits<decltype(&Func::operator())>::arg_type;
using result_type = typename function_traits<decltype(&Func::operator())>::result_type;
};
template <typename R, typename C, typename A>
struct function_traits<R (C::*)(A)> {
using result_type = R;
using arg_type = A;
};
template <typename R, typename C, typename A>
struct function_traits<R (C::*)(A) const> {
using result_type = R;
using arg_type = A;
};
template <typename R, typename A>
struct function_traits<R (*)(A)> {
using result_type = R;
using arg_type = A;
};
template <class T>
using result_type_t = typename function_traits<T>::result_type;
template <class T>
using arg_type_t = typename function_traits<T>::arg_type;
}
</pre>
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com6tag:blogger.com,1999:blog-13960885.post-77071656548828341602016-12-27T06:06:00.001-08:002017-01-05T21:10:32.233-08:00Folding Functions<div dir="ltr" style="text-align: left;" trbidi="on">
In the last post we looked at basic usage of C++17 Fold Expressions. I found that many posts on this topic discuss simple types and ignore how folds may be applicable to more complex types as well. [Edit: Please see the comments section for some examples elsewhere in the blogosphere.] In this post I'm going to describe folding over functions.<br /><br/>
<span style="font-size: large;"><b>Composing Functions</b></span><br />
<br />
Function composition is a powerful way of creating complex functions from simple ones. Functions that accept a single argument and return a value are easily composable. Consider the following example to compose two std::functions.
<pre class="brush:cpp">
template <class A, class B, class C>
std::function<C(A)> compose(std::function<B(A)> f, std::function<C(B)> g)
{
return [=](A a) -> C { return g(f(a)); };
}
int main(void)
{
std::function<int(std::string)> to_num = [](std::string s) { return atoi(s.c_str()); };
std::function<bool(int)> is_even = [](int i) { return i%2==0; };
auto is_str_even_num = compose(to_num, is_even);
std::cout << std::boolalpha << is_str_even_num("1234"); // prints true
}
</pre>
Function compose accepts two std::function arguments and returns another one. The types of these std::function arguments are important. f is a function from A->B where as g is a function from B->C. Therefore, it makes sense that compose can generate another function of type A->C. The output f goes to the input of g. The implementation of the lambda confirms that.
<br/><br/>
As std::function is kind of verbose and not very idiomatic in C++ when you want to pass functions around. I'll try to use C++11 lambdas initially. I want to stay away from generic lambdas because argument and return types are kinda important. In generic lambdas, however, it's impossible to find their argument and return types without knowing an actual argument or its type. Note that in compose function we have access to functions only and no arguments.
<br/><br/>
Lets rewrite compose to accepts lambdas.
<pre class="brush:cpp">
template <class F, class G>
auto compose(F&& f, G&& g)
{
using ArgType = detail::arg_type_t<F>;
using ResultType = detail::result_type_t<G>;
return [f,g](ArgType a) -> ResultType { return g(f(a)); };
}
</pre>
F and G are generic arguments, which we expect to be non-generic lambdas. We extract the argument type of F and result type of G and return a composition of two lambdas satisfying the type signature.
<br/><br/>
This implementation is not very idiomatic. Extracting the argument and return types of functions in this style is falling out of favor. std::function::argument_type and std::function::result_type have been deprecated in C++17. A more idiomatic way would have been to return a generic lambda without bothering the argument type. C++ clearly wants to favor duck-typing at compile-time. Until we've concepts in the language, of course.
<br/><br/>
I'll skip the implementation of the detail namespace. It's in the same vein as <a href="http://stackoverflow.com/questions/2562320/specializing-a-template-on-a-lambda-in-c0x/2565037#2565037">this</a> stackoverflow answer.
<br/><br/>
<span style="font-size: large;"><b>Folding Functions</b></span><br />
<br />
Folding functions is a generalization of function composition applied to fold expressions. First, we need to pick up an operator to use fold expressions with. I like >> as it's quite intuitive. Here's the earlier function implemented as an overloaded operator.
<pre class="brush:cpp">
template <class F, class G>
auto operator >>(F&& f, G&& g)
{
using ArgType = detail::arg_type_t<F>;
using ResultType = detail::result_type_t<G>;
return [f,g](ArgType a) -> ResultType { return g(f(a)); };
}
</pre>
We'll now write a new compose function that uses a fold expression over function types. Of course, it's going to use the overloaded >> operator.
<pre class="brush:cpp">
template <class... Funcs>
auto compose(Funcs... funcs)
{
return (... >> funcs);
}
</pre>
The earlier main program will work just fine with this new implementation of compose. It works with lambdas too.
<pre class="brush:cpp">
auto to_num = [](std::string s) { return atoi(s.c_str()); };
auto is_even = [](int i) { return i%2==0; };
auto is_str_even_num = compose(to_num, is_even);
std::cout << std::boolalpha << is_str_even_num("1234") << "\n"; // prints true
</pre>
Interestingly, this compose function works fine with a single argument as it simply returns the argument as discussed in the <a href="http://cpptruths.blogspot.com/2016/12/understanding-fold-expressions.html">previous</a> post. It does not work with empty parameter pack however. What could we return when we get an empty parameter pack? In other words what would be the identity for the function type? Well, it's just a function that returns its argument. Let's see it in action using a binary fold.
<pre class="brush:cpp">
struct Identity
{
template <class T>
T operator()(T&& t) { return std::forward<T>(t); }
};
template <class... Funcs>
auto compose(Funcs... funcs)
{
return (Identity() >> ... >> funcs);
}
</pre>
Only problem, however, is that it does not compile. Not that anything is wrong with binary folds but the overloaded >> for generic functions cannot digest Identity. Identity has a generic function call operator. There's no way to get it's argument_type and result_type without knowing the type of the argument. The compose function does not have it.
<br/><br/>
We're therefore forced to use a generic implementation of operator >>.
<pre class="brush:cpp">
template <class F, class G>
auto operator >>(F&& f, G&& g)
{
return [f,g](auto a) { return g(f(a)); };
}
</pre>
With this final variation, functions can be folded over in a binary fold expression.
<br/><br/>
I will conclude this blog post with a bit of monoid theory.
<br/></br/>
You might wanna ask yourself if function composition is another monoid? As it turns out, it is. It makes sense intuitively. Composition of two functions give rise to another function. The composition is also associative. It does not matter if we call compose(f, compose(g,h)) or compose(compose(f,g),h). The end result is the same. Squint a little and you will realize that they are just left and right folds. Finally, there's also an identity function, which when combined with any other function makes no observable difference. Therefore, we can say that function form a monoid under composition.
<br/><br/>
Next time we'll look at even more interesting functions---those return values wrapped a generic "container".
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com9tag:blogger.com,1999:blog-13960885.post-47509463598750254852016-12-26T19:52:00.000-08:002016-12-26T19:52:09.487-08:00Understanding Fold Expressions<div dir="ltr" style="text-align: left;" trbidi="on">
C++17 has an interesting new feature called <a href="http://en.cppreference.com/w/cpp/language/fold">fold expressions</a>. Fold expressions offer a compact syntax to apply a binary operation to the elements of a parameter pack. Here’s an example.
<pre class="brush: cpp">
template <typename... Args>
auto addall(Args... args)
{
return (... + args);
}
addall(1,2,3,4,5); // returns 15.
</pre>
This particular example is a <i>unary left fold</i>. It's equivalent to ((((1+2)+3)+4)+5). It reduces/folds the parameter pack of integers into a single integer by applying the binary operator successively. It's unary because it does not explicitly specify an init (a.k.a. identity) argument. So, let add it.
<pre class="brush: cpp">
template <typename... Args>
auto addall(Args... args)
{
return (0 + ... + args);
}
addall(1,2,3,4,5); // returns 15.
</pre>
This version of addall is a <i>binary left fold</i>. The init argument is 0 and it's redundant (in this case). That's because this fold expression is equivalent to (((((0+1)+2)+3)+4)+5). Explicit identity elements will come in handy a little later---when we have empty parameter packs or if we use user-defined types in fold expressions.
<br/><br/>
Fold expressions can be defined over a number of operators. 32 to be precise. They are + - * / % ^ & | = < > << >> += -= *= /= %= ^= &= |= <<= >>= == != <= >= && || , .* ->*.
<br/><br/>
In this post you will see an example of each and see how each one behaves. So here's the whole enchilada.
<pre class="brush: cpp">
#include <iostream>
#include <iomanip>
#define UNARY_LEFT_FOLD(NAME, OP) \
template<typename... Args> \
auto NAME(Args&&... args) { \
return (... OP args); \
}
UNARY_LEFT_FOLD(add,+);
UNARY_LEFT_FOLD(sub,-);
UNARY_LEFT_FOLD(mul,*);
UNARY_LEFT_FOLD(divide,/);
UNARY_LEFT_FOLD(mod,%);
UNARY_LEFT_FOLD(bxor,^);
UNARY_LEFT_FOLD(band,&);
UNARY_LEFT_FOLD(bor,|);
UNARY_LEFT_FOLD(assign,=);
UNARY_LEFT_FOLD(lt,<);
#ifndef __clang__
UNARY_LEFT_FOLD(gt,>);
UNARY_LEFT_FOLD(rshift,>>);
#endif
UNARY_LEFT_FOLD(lshift,<<);
UNARY_LEFT_FOLD(addassign,+=);
UNARY_LEFT_FOLD(subassign,-=);
UNARY_LEFT_FOLD(mulassign,*=);
UNARY_LEFT_FOLD(divassign,/=);
UNARY_LEFT_FOLD(modassign,%=);
UNARY_LEFT_FOLD(bxorassign,^=);
UNARY_LEFT_FOLD(bandassign,&=);
UNARY_LEFT_FOLD(borassign,|=);
UNARY_LEFT_FOLD(lshiftassign,<<=);
UNARY_LEFT_FOLD(rshiftassign,>>=);
UNARY_LEFT_FOLD(equals,==);
UNARY_LEFT_FOLD(nequals,!=);
UNARY_LEFT_FOLD(lte,<=);
UNARY_LEFT_FOLD(gte,>=);
UNARY_LEFT_FOLD(land,&&);
UNARY_LEFT_FOLD(lor,||);
UNARY_LEFT_FOLD(objptrmem,.*);
UNARY_LEFT_FOLD(ptrptrmem,->*);
template<typename... Args>
auto comma(Args&&... args) {
return (... , args);
}
struct Phone { int ext; };
struct Person { Phone phone; };
int main(void)
{
std::cout << std::boolalpha;
std::cout << "add " << add(1) << " " << add(1,2,3) << "\n";// 1
std::cout << "sub " << sub(1) << " " << sub(1,2,3) << "\n";
std::cout << "mul " << mul(1) << " " << mul(1,2,3) << "\n";
std::cout << "divide " << divide(1) << " " << divide(18,2,3) << "\n";
std::cout << "mod " << mod(1) << " " << mod(23, 3,2) << "\n";
std::cout << "bxor " << bxor(1) << " " << bxor(1,2,4) << "\n";
std::cout << "band " << band(1) << " " << band(1,3,7) << "\n";
std::cout << "assign " << assign(1) << " " << assign(1,2,4) << "\n";
auto a = 99;
std::cout << "assign-a " << assign(a);
std::cout << " " << assign(a,2,4);
std::cout << " " << a << "\n";
#ifndef __clang__
std::cout << "gt " << gt(1) << " " << gt(3,2,0) << "\n";
std::cout << "rshift " << rshift(1) << " " << rshift(32,2,2) << "\n";
#endif
std::cout << "lt " << lt(1) << " " << lt(1,2,-1) << "\n";
std::cout << "lshift " << lshift(1) << " " << lshift(1,2,3) << "\n";
std::cout << "addassign " << addassign(1) << " " << addassign(2,3,2) << "\n";
std::cout << "subassign " << subassign(1) << " " << subassign(7,2) << "\n";
std::cout << "mulassign " << mulassign(1) << " " << mulassign(2,3,2) << "\n";
std::cout << "divassign " << divassign(1) << " " << divassign(7,2) << "\n";
std::cout << "modassign " << modassign(1) << " " << modassign(23,3,2) << "\n";
std::cout << "bxorassign " << bxorassign(1) << " " << bxorassign(7,2) << "\n";
std::cout << "bandassign " << bandassign(1) << " " << bandassign(7,6) << "\n";
std::cout << "borassign " << borassign(1) << " " << borassign(1,2,4,8) << "\n";
std::cout << "lshiftassign " << lshiftassign(1) << " " << lshiftassign(8,2) << "\n";
std::cout << "rshiftassign " << rshiftassign(1) << " " << rshiftassign(16,1,2) << "\n";
std::cout << "equals " << equals(1) << " " << equals(8,3,2) << "\n";
std::cout << "nequals " << nequals(1) << " " << nequals(7,2,0) << "\n";
std::cout << "lte " << lte(1) << " " << lte(7,2,0) << "\n";
std::cout << "gte " << gte(1) << " " << gte(7,3,1) << "\n";
std::cout << "land " << land() << " " << land(7,2) << "\n";
std::cout << "lor " << lor() << " " << lor(7,2) << "\n";
std::cout << "comma " << comma(1) << " " << comma(8,3,2) << "\n";
auto phoneptr = &Person::phone;
auto extptr = &Phone::ext;
Person p { { 999 } };
Person * pptr = &p;
std::cout << "objptrmem " << objptrmem(p,phoneptr,extptr) << "\n";
std::cout << "p.*phoneptr.*extptr " << p.*phoneptr.*extptr << "\n";
std::cout << "ptrptrmem(&p,phoneptr).ext " << ptrptrmem(&p,phoneptr).ext << "\n";
std::cout << "&(pptr->*phoneptr)->*extptr " << (&(pptr->*phoneptr))->*extptr << "\n";
}
</pre>
The output looks something like the following.
<pre class="brush: cpp">
add 1 6
sub 1 -4
mul 1 6
divide 1 3
mod 1 0
bxor 1 7
band 1 1
assign 1 4
assign-a 99 4 4
gt 1 true
rshift 1 2
lt 1 false
lshift 1 32
addassign 1 7
subassign 1 5
mulassign 1 12
divassign 1 3
modassign 1 0
bxorassign 1 5
bandassign 1 6
borassign 1 15
lshiftassign 1 32
rshiftassign 1 2
equals 1 false
nequals 1 true
lte 1 true
gte 1 true
land true true
lor false true
comma 1 2
objptrmem 999
p.*phoneptr.*extptr 999
ptrptrmem(&p,phoneptr).ext 999
&(pptr->*phoneptr)->*extptr 999
</pre>
There're a number of observations.
<ol>
<li>Clang does not like > and >> operators for some reason. GCC is fine. </li>
<li>Unary fold expressions do not like empty parameter packs except for && || and comma operators. In fact, the <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0036r0.pdf">P0036</a> document describes what happens when empty parameter packs are used with these operators and why it's illegal for other operators. In short, empty parameter packs result into true, false, and void() respectively. In that sense, binary folds appear significantly superior because you can specify the identity element for fundamental and user-defined types and for all the operators. </li>
<li>Single element parameter packs result into the value of the element type. This may be ok for some types and operators but it's very confusing for operators such as > < == != <= >= && ||. These operators return boolean result in general but not when the parameter pack has only one element. The <i>type</i> of the expression changes when the size of the parameter pack is greater than 1. For example, lte(1) returns a int but lte(1,3) return a boolean. That's bizarre. </li>
<li>Multiple element parameter packs work as expected with a twist. Consider gt example on line #73. gt(3,2,0) expands to (3>2)>0, which is true>0, which is true. Similarly, lt(1,0,-1) is (1<0)<-1, which is false<-1, which is false. However, for such operators (that return a boolean result), compiler spits out copious amount of warnings saying that "comparisons like 'X<=Y<=Z' do not have their mathematical meaning". That makes sense.</li>
<li>The assign function is curious too. Assigning to a variable makes sense. For example, assign(a,2,4) expands to (a=2)=4, which assigns 2 to a and later 4 to a. So there're two assignments. The result type is int&. The funny thing is that if you replace a with an rvalue, it still works. I don't know what the compiler is thinking at that point.</li>
<li>Operator associativity has no consequence. For example, <<= and >>= are right-associative operators but left folds still fold from left to right. I.e., Nominally, a <<= b <<= c is equivalent to a <<= (b <<= c). With left unary fold you get (a <<= b) <<= c. If you want the former, use a unary right fold. </li>
<li>Finally, consider the folds expressions containing pointer to members. Line #103 and below. A single, initialized pointer to member just a decays to true in a boolean context (like any other pointer). The weird thing though is that, there's no way to make sense of two or more pointers to members. I can't think of a way where they fold (a.k.a. compose) and return something meaningful. An object (of the same class as that of the member pointer) is required as the left most element in the parameter pack to deference a list of member pointers. For example, objptrmem(p,phoneptr,extptr) is the same as p.*phoneptr.*extptr. Without p, just phoneptr and extptr make no sense together.</li>
</ol>
<br />
<br />
<span style="font-size: large;"><b>Binary Folds</b></span><br />
<br />
This example uses a user-defined Int type in a left binary fold. We'll also specify our own identity for our Int-based binary folds.
<pre class="brush:cpp">
#include <iostream>
#include <iomanip>
struct Int {
int value;
explicit Int(int v=0) : value(v) {}
explicit operator int() const { return value; }
};
std::ostream& operator << (std::ostream& o, const Int& i) {
o << i.value;
return o;
}
Int operator + (Int const &i, Int const &j) {
std::cout << "Adding " << i << " " << j << "\n";
return Int(i.value + j.value);
};
Int operator * (Int const &i, Int const &j) {
std::cout << "Multiplying " << i << " " << j << "\n";
return Int(i.value * j.value);
};
template<typename... Args>
auto addInts(Args&&... args)
{
return (Int{0} + ... + args);
}
template<typename... Args>
auto mulInts(Args&&... args)
{
return (Int{1} * ... * args);
}
int main(void)
{
std::cout << addInts(Int{1}, Int{2}, Int{3}) << "\n"; // prints 6
std::cout << addInts() << "\n"; // prints 0
std::cout << mulInts(Int{1}, Int{2}, Int{3}) << "\n"; // prints 6
std::cout << mulInts() << "\n"; // prints 1
}
</pre>
Things are very much as expected in this example. For user-defined types, the operator you wish to use fold expression with must be overloaded. Int overloads binary + and *. addInts uses Int{0} as the identity element whereas mulInts uses Int{1}. Identity element is special. It's special because in case of Int addition, adding with identity element make no difference. Similarly, in Integer multiplication, multiplying with the identity element makes no difference.
<br/><br/>
I'll wrap with a quick theory about monoids.
<br/><br/>
Formally, (Int,+) is monoid with Int{0} as identity and (Int,*) is also a (different) monoid with Int{1} as identity. Two instances of the same monoid can be <i>combined</i> to produce a third one. In fact, Monoids can be combined arbitrarily to produce other instances of the same monoid. Left and right folds provide just 2 possible ways in which any monoid may be combined.
<br/><br/>
In the following posts, we'll create more interesting monoids and see how well fold expressions can exploit their properties.
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com1tag:blogger.com,1999:blog-13960885.post-54296401274907480142016-11-05T12:21:00.001-07:002016-11-12T12:19:52.786-08:00Dependently-typed Curried printf in C++<div dir="ltr" style="text-align: left;" trbidi="on">
Just a few days ago I came across an intriguing <a href="http://icfp2016.mirage.io/SVs/zesen_qian.md" target="_blank">blog-post</a> about type-safe <code>printf</code> using dependent typing. The blog-post has since become inaccessible and therefore, I've copied an excerpt here. I want to thank Zesen Qian for publishing this blog-post.<br />
<br />
<blockquote class="tr_bq">
<code>.... printf</code> originated from the C programming language and has been a headache since then because a proper call of <code>printf</code> requires the number and types of arguments to match the format string; otherwise, it may visit a wild memory or a wrong register. In recent versions of GCC this issue is addressed by type checks hard coded into the compiler itself, which is ugly because the compiler should not be caring about the safety of applications of a specific function....
<br />
<br />
The key issue here is that, considering the curried version, the type of the returned function of applying the format string to <code>printf</code>, actually depends on the value of that format string. That is to say, <code>printf "%s" : String -> String</code>, and <code>printf "%d%s%d" : Int -> String -> Int -> String</code>, and so on. This is where dependent type comes in: in dependently typed language, the type of returned values of functions can be dependent on value of the arguments; .... ---- Zesen Qian (ICFP'2106)</blockquote>
I thought it might be possible to achieve the same effect in C++.
.
<br />
<br />
<span style="font-size: large;"><b>Currying</b></span><br />
<br />
Currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions, each with a single argument. I've talked about currying from very basics in a <a href="http://cpptruths.blogspot.com/2014/03/fun-with-lambdas-c14-style-part-1.html" target="_blank">previous post</a>. I'll jump straight to an example this time.<br />
<br />
<pre class="brush: cpp">int multiply(int i, int j) { return i*j; }
auto curry = [](auto binary) {
return [=](int i) {
return [=](int j) {
return binary(i, j);
};
};
};
auto mul = curry(multiply);
auto a = mul(10);
auto b = a(20);
std:: cout << b << std::endl; // prints 200
</pre>
<br />
Function <code>multiple</code> takes both arguments at the <i>same time</i>. Function <code>mul</code>, which is a curried version, takes one argument at a time. Intermediate results, such as <code>a</code>, are themselves functions that take one of the remaining arguments. When all arguments are available, the original function evaluates producing a result.
<br />
<br />
<span style="font-size: large;"><b>Currying printf--dependently</b></span><br />
<br />
Currying <code>printf</code> poses an extra challenge because (1) printf accepts a variable number of arguments and (2) the order of the types of the arguments is not fixed (past the first argument). More accurately, the order of the types of the arguments is determined by the format string. The format string of printf is a value---usually, a literal string. We want to make the types of the rest of the arguments <i>dependent</i> on the <i>value</i> of the first argument. That's pretty intriguing, imo. In effect, we need a way to codify the format string literal into a <i>type</i> and that's where the dependent-typing comes into play.
<br />
<br />
To codify a string literal into a type, we are going to use the C++ language feature proposed in <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3599.html">N3599</a>. This proposal includes an example of dependently-typed printf that accepts all arguments at once. We're going to twist it a little bit to accept one argument at a time.
<br />
<br />
The magic lies in the <code>operator ""</code> that converts a string literal into a type. Here's the code without further ado. Both clang and gcc support this extension. Perhaps it will be in C++17 standard soon or it already is.
<br />
<br />
<pre class="brush: cpp">#include <utility>
template <char... chars>
using CharSeq = std::integer_sequence<char, chars...>;
template <typename T, T... chars>
constexpr CharSeq<chars...> operator""_lift() { return { }; }
</pre>
The <code>CharSeq</code> type is a synonym for <code>std::integer_sequence<char, ...></code>. <code>_lift</code> is a function that uses C++11 user-defined literals syntax convert a string literal to an equivalent <code>CharSeq</code> at compile-time. For example, <code>"cpptruths"_lift</code> returns <code>std::integer_sequence<char,'c','p','p','t','r','u','t','h','s'></code>. Check this code out.
<br />
<pre class="brush: cpp">#include <boost/core/demangle.hpp>
auto cpptruths = "cpptruths"_lift;
std::cout << boost::core::demangle(typeid(decltype(cpptruths)).name()) << "\n";
</pre>
Once a string is encoded as a type, a lot of things begin to fall into place using some additional template meta-programming. First, we need to codify the type-level <code>CharSeq</code> into a tuple of types that directly specify the types expected by printf. For instance, <code>"%d"</code> expects an <code>int</code> and <code>"%s"</code> expects and <code>const char *</code> etc.
We implement a meta-function called <code>StringToTuple</code>.
<br />
<pre class="brush: cpp">template <class Head, class Tuple>
struct Append;
template <class Head, class... Args>
struct Append<Head, std::tuple<Args...>>
{
using type = std::tuple<Head, Args...>;
};
template <class CharSeq>
struct StringToTuple;
template <>
struct StringToTuple<CharSeq<>>
{
using type = std::tuple<>;
};
template <char Any, char... chars>
struct StringToTuple<CharSeq<Any, chars...>>
{
using type = typename StringToTuple<CharSeq<chars...>>::type;
};
template <char... chars>
struct StringToTuple<CharSeq<'%', 's', chars...>>
{
using tail = typename StringToTuple<CharSeq<chars...>>::type;
using type = typename Append<const char *, tail>::type;
};
template <char... chars>
struct StringToTuple<CharSeq<'%', 'd', chars...>>
{
using tail = typename StringToTuple<CharSeq<chars...>>::type;
using type = typename Append<int, tail>::type;
};
template <char... chars>
struct StringToTuple<CharSeq<'%', 'f', chars...>>
{
using tail = typename StringToTuple<CharSeq<chars...>>::type;
using type = typename Append<double, tail>::type;
};
template <char... chars>
struct StringToTuple<CharSeq<'%', 'u', chars...>>
{
using tail = typename StringToTuple<CharSeq<chars...>>::type;
using type = typename Append<unsigned int, tail>::type;
};
auto format = "%s%d"_lift;
StringToTuple<decltype(format)>::type FormatTuple; // std::tuple<const char *, int>
</pre>
<code>StringToTuple</code> meta-function uses a pattern-matching. Consider the %s specialization. When the beginning of the <code>CharSeq</code> is '%' followed by 's', the specialization matches recursively computes the type of the tail, which is tuple<int> in this case. The <code>Append</code> meta-function simply concatenates the types in a tuple at the head.
<br />
<br />
If the beginning of the <code>CharSeq</code> is not a '%', the first most generic version with <code>char Any</code> matches, which simply ignores the leading character.
<br />
<br />
Fun does not end here though. We still need to curry printf. All we have at this stage is a sequence of types and that's big leap forward.
<br />
<br />
Let's assume you have a function <code>curried_printf_impl</code> that accepts a format string and a <code>CharSeq</code> as follows.
<br />
<pre class="brush: cpp">template <class CharSeq>
auto curried_printf_impl(const char * fmt, CharSeq)
{
using FormatType = typename StringToTuple<CharSeq>::type;
std::cout << boost::core::demangle(typeid(FormatType).name()) << "\n";
return curry<FormatType>::apply(fmt);
}
#define curried_printf(X) curried_printf_impl(X, X##_lift)
</pre>
We've not talked about the <code>curry</code> template yet. Of course, it's going to use the <code>FormatType</code> tuple and turn it into a sequence of curried functions. The <code>curried_printf</code> macro helps us cleanly separate the string literal from the compile-time character sequence into two separate arguments. ## is token-pasting operator in the C preprocessor.
<br />
<br />
The target really feels within reach now. The <code>curry</code> template is relatively straight forward.
<br />
<pre class="brush: cpp">template <class Tuple>
struct curry;
template <class Head, class... Tail>
struct curry<std::tuple<Head, Tail...>>
{
template<class... Args>
static auto apply(Args&&... args)
{
return [args...](Head h) {
return curry<std::tuple<Tail...>>::apply(args..., h);
};
}
};
template <class Head>
struct curry<std::tuple<Head>>
{
template <class... Args>
static auto apply(Args&&... args) {
return [args...](Head h) {
return printf(args..., h);
};
}
};
template <>
struct curry<std::tuple<>>
{
static auto apply(const char * fmt) {
return printf(fmt);
}
};
</pre>
The general case of the <code>curry</code> template has an <code>apply</code> function that accepts arbitrary number of arguments and returns a closure that captures all those arguments (from apply) and takes exactly one more argument of <code>Head</code> type. As soon as it has the Head argument, it forwards it with all previous arguments to the subsequent <code>curry<Tail...>::apply</code> to accept and retain remaining arguments one by one. The single argument <code>curry</code> (the one with just Head), terminates the recursion and returns a lambda that upon receiving the last argument calls printf. Note that the format string literal is always at the beginning of <code>args...</code> as <code>curried_printf_impl</code> passes it along. If format string is the only argument, curry::apply calls printf right-away in the last no-argument specialization.
<br />
<br />
Here's the main driver program. Also on <a href="https://github.com/sutambe/cpptruths/blob/master/cpp0x/compile_string_parse.cpp">github</a>.
<br />
<pre class="brush: cpp">int main(void)
{
curried_printf("C++ Rocks%s %d %f\n")("!!")(10)(20.30);
curried_printf("C++ Rocks!!\n");
return 0;
}
</pre>
If you mess up with the argument types, the error is short and relatively direct.
<br /><br />
<span style="font-size: large;"><b>Avoiding Copying Arguments</b></span><br />
<br />
The previous example makes a massive assumption that all arguments are fundamental types. That they are cheap to copy. The lambda inside the apply function captures the arguments by value and passes them on by value. The arguments are copied O(N*N) times approximately. That's gonna hurt for large types that are expensive to copy.
<br/><br/>
The Remedy is to <code>std::move</code> the arguments as much as possible. However, forwarding variadic arguments requires us to take some library help: <code>std::tuple</code>.
<br /><br />
<pre class="brush: cpp">
template <class Head, class... Tail>
struct curry<std::tuple<Head, Tail...>>
{
template<class... Args>
static auto apply(Args&&... args)
{
return [t=std::make_tuple(std::move(args)...)](Head h) {
// Move each element of t and h to curry<std::tuple<Tail...>>::apply somehow.
};
}
};
</pre>
It got complicated real fast. For each argument, we'll have to wrap them in a tuple and unwrap them before passing to <code>curry::apply</code>. Wrapping is easy. There's the code. Unwrapping is rather complicated because all arguments are not together in a tuple. <code>Head</code> comes separately. <code>std::apply</code> and <code>std::invoke</code> did not appear particularly useful in this case. We perhaps need a direct syntax to expand tuple into function arguments. Secondly, there's at least one copy of each <code>Head</code> argument anyway because the function should be type-safe and accept only <code>Head</code> type argument in the lambda. I thought this is more trouble than it's worth.
<br/><br/>
<span style="font-size: large;"><b>Currying Arbitrary Functions</b></span><br />
<br />
To work around this problem I'm simply going to use a dynamically allocated tuple that will store the arguments as they come in. As curried function may be copied multiple times, this scheme should work out quite efficiently in such cases.
<br />
<pre class="brush: cpp">
// In C++17, std::experimental::apply can replace the following execute function.
template <size_t... Indices, class Tuple, class Func>
auto execute(std::integer_sequence<size_t, Indices...>,
Tuple&& tuple,
Func&& func)
{
return func(std::get<Indices>(std::forward<Tuple>(tuple))...);
}
template <int I, class AllArgs, class Tuple>
struct dyn_curry;
template <int I, class AllArgs, class Head, class... Tail>
struct dyn_curry<I, AllArgs, std::tuple<Head, Tail...>>
{
enum { Index = std::tuple_size<AllArgs>::value - I };
template <class Func>
static auto apply(std::shared_ptr<AllArgs> shptr, Func&& func)
{
return [shptr, func=std::move(func)](const Head &h) mutable {
std::get<Index>(*shptr) = h;
return dyn_curry<I-1, AllArgs, std::tuple<Tail...>>::apply(shptr, std::move(func));
};
}
};
template <class AllArgs, class Head>
struct dyn_curry<1, AllArgs, std::tuple<Head>>
{
enum { Index = std::tuple_size<AllArgs>::value - 1 };
using IntSeq = std::make_index_sequence<std::tuple_size<AllArgs>::value>;
template <class Func>
static auto apply(std::shared_ptr<AllArgs> shptr, Func&& func)
{
return [shptr, func=std::move(func)](const Head &h) mutable {
std::get<Index>(*shptr) = h;
return execute(IntSeq(), sd::move(*shptr), std::move(func));
};
}
};
template <class Ret, class... Args>
auto arb_curry(Ret (&func) (Args...))
{
using AllArgs = std::tuple<std::decay_t<Args>...>;
std::cout << boost::core::demangle(typeid(AllArgs).name()) << "\n";
std::shared_ptr<AllArgs> shptr(new AllArgs);
return dyn_curry<std::tuple_size<AllArgs>::value, AllArgs, AllArgs>::apply(shptr, func);
}
template <class Ret>
Ret arb_curry(Ret (&func) ()) { return func(); }
int print_add(std::string &msg, int &j, int k) { std::cout << msg; return j+k; }
int identity(int i) { return i; }
int foo() { return printf("foo\n"); }
int main(void)
{
arb_curry(foo);
std::cout << arb_curry(identity)(99) << std::endl;
auto a = arb_curry(print_add);
auto b = a("Adding two integers: ");
auto c = b(20);
auto d = c(30);
std::cout << d << std::endl; //prints 60.
return 0;
}
</pre>
There are three main differences in this more general implementation than the previous example.<br />
<ol style="text-align: left;">
<li>This implementation uses an explicit compile-time index to copy arguments in to the right slot in the tuple of arguments. </li>
<li>There's more type related noise here because each call to apply passes the <code>shared_ptr</code> of the tuple type to the inner lambda. </li>
<li>The final dispatch to the function is implemented in the <code>execute</code> function that expands all the arguments in the tuple as function arguments. In C++17, <code>std::experimental::apply</code> can replace the execute function.</li>
</ol>
Here's <a href="http://melpon.org/wandbox/permlink/9ztVSoExIWb8ZesA">live code</a> and also on <a href="https://github.com/sutambe/cpptruths/blob/master/cpp0x/curry.cpp">github</a>. <br/>
<br/>
<span style="font-size: large;"><b>Conclusion</b></span><br />
<br/>
While currying C++ functions is fun, lifting C++ string literals to type-level opens up a whole new level of meta-programming in C++. constexpr functions can operate on string literals and compute integral results at compile-time. See <a href="http://cpptruths.blogspot.com/2011/07/compile-time-regex-matcher-using.html">this</a> for an example. With constexpr function, however, we can't construct new types at compile-time depending upon the argument value. <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3599.html">N3599</a> allows us to cross the string-to-type barrier at compile-time. That's pretty neat. I can already think of some intriguing applications of N3599 in serialization/deserialization of user-defined types.
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-46246285261702783782015-11-14T10:56:00.001-08:002015-11-28T10:33:51.693-08:00Covariance and Contravariance in C++ Standard Library<div dir="ltr" style="text-align: left;" trbidi="on">
<a href="https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)">Covariance and Contravariance</a> are concepts that come up often as you go deeper into generic programming. While designing a language that supports parametric polymorphism (e.g., templates in C++, generics in Java, C#), the language designer has a choice between Invariance, Covariance, and Contravariance when dealing with generic types. C++'s choice is "invariance". Let's look at an example. <br />
<pre class="brush: cpp">
struct Vehicle {};
struct Car : Vehicle {};
std::vector<Vehicle *> vehicles;
std::vector<Car *> cars;
vehicles = cars; // Does not compile
</pre>
The above program does not compile because C++ templates are invariant. Of course, each time a C++ template is instantiated, the compiler creates a brand new type that uniquely represents that instantiation. Any other type to the same template creates another unique type that has nothing to do with the earlier one. Any two unrelated user-defined types in C++ can't be assigned to each-other by default. You have to provide a copy-constructor or an assignment operator.
<br/>
<br/>
However, the fun starts when you realize that it's just a choice and there are other valid choices. In fact, C++ makes a different choice for pointers and references. For example, it's common knowledge that pointer of type Car is assignable to pointer of type Vehicle. That's because Car is a subtype of Vehicle. More accurately, the Car struct inherits from the Vehicle struct and the compiler allows us to use Car pointers in places where Vehicle pointer is expected. I.e., subtyping is activated through inheritance. Later in the post we will use subtyping without using inheritance.
<br/><br/>
If you think about pointers as a shortcut for the Pointer template below, it becomes apparent that the language has some special rules for them. Don't let the special * syntax confuse you. It is just a shortcut to avoid the ceremony below.
<pre class="brush: cpp">
template <class T>
using Pointer = T *;
Pointer<Vehicle> vehicle;
Pointer<Car> car;
vehicle = car; // Works!
</pre>
So what choices are available? The question we want to ask ourselves is, <u>"What relationship do I expect between instantiations of a template with two different types that happen to have a subtype relationship?"</u>
<ul>
<li>The first choice is <strong>no relationship</strong>. I.e., the template instantiations completely ignore the relationship between parameter types. This is C++ default. It's called invariance. (a.k.a. C++ templates are invariant)</li>
<li>The second choice is <strong>covariant</strong>. I.e., the template instantiations have the same subtype relationship as the parameter types. This is seen in C++ pointers and also in std::shared_ptr, std::unique_ptr because they want to behave as much like pointers as possible. You have write special code to enable that because the language does not give it to you by default.</li>
<li>The third choice is <strong>contravariance</strong>. I.e., the template instantiations have the opposite subtype relationship to that of the parameter types. I.e., TEMPLATE<base> is subtype of TEMPLATE<derived>. We'll come back to contravariance in much more detail later in the post.</li>
</ul>
All C++ standard library containers are invariant (even if they contain pointers).
<h2>Covariance</h2>
As said earlier, with covariance, the templated type maintains the relationship between argument types. I.e., if argument types are unrelated, the templated types shall be unrelated. If <i>derived</i> is a sub-type of <i>base</i> (expressed as inheritance) then TEMPLATE<derived> shall be sub-type of TEMPLATE<base>. I.e., any place where TEMPLATE<base> is expected, TEMPLATE<derived> can be substituted and everything will work just fine. The other way around is not allowed.
<br/><br/>
There are some common examples of covariance in C++ standard library.
<pre class="brush: cpp">
std::shared_ptr<Vehicle> shptr_vehicle;
std::shared_ptr<Car> shptr_car;
shptr_vehicle = shptr_car; // Works
shptr_car = shptr_vehicle' // Does not work.
std::unique_ptr<Vehicle> unique_vehicle;
std::unique_ptr<Car> unique_car;
unique_vehicle = std::move(unique_car); // Works
unique_car = std::move(unique_vehicle); // Does not work
</pre>
One (formal) way to think about covariance is that "the type is allowed to get <strong>bigger</strong> upon assignment". I.e., Vehicle is broader/bigger type than Car.
Here's a quick rundown of some of the commonly used C++ standard library types and their covariance/contravariance properties.
<br/><br/>
<table width="80%" border="1">
<tr>
<th>Type</th><th>Covariant</th><th>Contravariant</th>
</tr>
<tr><td>STL containers</td><td>No</td><td>No</td></tr>
<tr><td>std::initializer_list<T *></td><td>No</td><td>No</td></tr>
<tr><td>std::future<T></td><td>No</td><td>No</td></tr>
<tr><td>boost::optional<T></td><td>No (see note below)</td><td>No</td></tr>
<tr><td>std::shared_ptr<T></td><td>Yes</td><td>No</td></tr>
<tr><td>std::unique_ptr<T></td><td>Yes</td><td>No</td></tr>
<tr><td>std::pair<T *, U *></td><td>Yes</td><td>No</td></tr>
<tr><td>std::tuple<T *, U *></td><td>Yes</td><td>No</td></tr>
<tr><td>std::atomic<T *></td><td>Yes</td><td>No</td></tr>
<tr><td>std::function<R *(T *)></td><td>Yes (in return)</td><td>Yes (in arguments)</td></tr>
</table>
<br/>
The boost::optional<T> appears to be covariant but it really isn't because it slices the object underneath. The same thing happens with std::pair and std::tuple. Therefore, they behave covariantly correctly only when the parameter type itself behaves covariantly.
<br/><br/>
Finally, Combining one covariant type with another (e.g., std::shared_ptr<std::tuple<T *>>) does not necessarily preserve covariance because it is not built into the language. It is often implemented as a <strong>single-level</strong> direct convertibility. I.e., std::tuple<Car *> * is not directly convertible to std::tuple<Vehicle *> *. It would have been if the language itself enforced subtyping between std::tuple<Car*> and std::tuple<Vehicle *> but it does not. On the other hand, std::tuple<std::shared_ptr<T>> behaves covariantly.
<br/><br/>
By "single-level direct convertibility", I mean the following conversion of U* to T*. Convertibility is poor man's test for subtyping in C++.
<br/><br/>
A covariant SmartPointer might be implemented as follows. <br/><br/>
<pre class="brush: cpp">
template <class T>
class SmartPointer
{
public:
template <typename U>
SmartPointer(U* p) : p_(p) {}
template <typename U>
SmartPointer(const SmartPointer<U>& sp,
typename std::enable_if<std::is_convertible<U*, T*>::value, void>::type * = 0)
: p_(sp.p_) {}
template <typename U>
typename std::enable_if<std::is_convertible<U*, T*>::value, SmartPointer<T>&>::type
operator=(const SmartPointer<U> & sp)
{
p_ = sp.p_;
return *this;
}
T* p_;
};
</pre>
<h2>Contravariance</h2>
Contravariance, as it turns out, is quite counter-intuitive and messes up with your brain. But it is a very valid choice when it comes to selecting how generic types behave. Before we deal with contravariance, lets quickly revisit a very old C++ feature: covariant return types.
<br/><br/>
Consider the following class hierarchy.
<br/>
<pre class="brush: cpp">
class VehicleFactory {
public:
virtual Vehicle * create() const { return new Vehicle(); }
virtual ~VehicleFactory() {}
};
class CarFactory : public VehicleFactory {
public:
virtual Car * create() const override { return new Car(); }
};
</pre>
Note that the return value of VehicleFactory::create function is Vehicle * where as CarFactory::create is Car *. This is allowed. The CarFactory::create function overrides its parent's virtual function. This feature is called overriding with covariant return types.
<br/><br/>
What happens when you change the raw pointers to std::shared_ptr? Is it still a valid program?....
<br/><br/>
As it turns out, it's not. std::shared_ptr (or any simulated covariant type for that matter) can't fool the compiler into believing that the two functions have covariant return types. The compiler rejects the code because as far as it knows, only the pointer types (and references too) have built-in covariance and nothing else.
<br/><br/>
Lets look a these two factories from the substitutability perspective. The client of VehicleFactory (which has no knowledge of CarFactory) can use VehicleFactory safely even if the create function gets dispatched to CarFactory at run-time. After all, the create function return something that can be treated like a vehicle. No concrete details about Car are necessary for the client to work correctly. That's just classic Object-oriented programming.
<br/><br/>
Covariance appears to work fine for return types of overridden functions. How about the argument? Is there some sort of variance possible? Does C++ support it? Does it make sense outside C++? <br/><br/>
Let's change the create function to accept Iron * as raw material. Obviously, the CarFactory::create must also accept an argument of type Iron *. It is supposed to work and it does. That's old hat.
<br/><br/>
What if CarFactory is so advanced that it takes any Metal and creates a Car? Consider the following.
<pre class="brush: cpp">
struct Vehicle {};
struct Car : Vehicle {};
struct Metal {};
struct Iron : Metal {};
class VehicleFactory {
public:
virtual Vehicle * create(Iron *) const { return new Vehicle(); }
virtual ~VehicleFactory() {}
};
class CarFactory : public VehicleFactory {
public:
virtual Car * create(Metal *) const override { return new Car(); }
};
</pre>
The above program is illegal C++. The CarFactory::create does not override anything in its base class and therefore due to the override keyword compiler rejects the code. Without override, the program compiles but you are looking at two completely separate functions marked virtual but really they won't do what you expect.
<br/></br/>
More interesting question is whether it makes sense to override a function in a way that the argument in the derived function is broader/larger than that of the bases's?...
<br/><br/>
<strong>Welcome to Contravariance...</strong><br/><br/>
It totally does make sense and this language feature is called <strong>contravariant argument types</strong>. From the perspective of the client of VehicleFactory, the client needs to provide some Iron. The CarFactory not only accepts Iron but any Metal to make a Car. So the Client works just fine.
<br/><br/>
Note the reversed relationship in the argument types. The derived create function accepts the broader type because it must do at least as much as the base's function is able to do. This reverse relationship is the crux of contravariance.
<br/><br/>
C++ does not have built-in support for contravariant argument types. So that's how it ends for C++? Of course not!
<a name="function_contravariance"></a>
<h2>Covariant Return Types and Contravariant Argument Types in std::function</h2>
OK, the heading gives it away so lets get right down to an example.
<pre class="brush: cpp">
template <class T>
using Sink = std::function<void (T *)>;
Sink<Vehicle> vehicle_sink = [](Vehicle *){ std::cout << "Got some vehicle\n"; };
Sink<Car> car_sink = vehicle_sink; // Works!
car_sink(new Car());
vehicle_sink = car_sink; // Fails to compile
</pre>
Sink is a function type that accepts any pointer of type T and return nothing. car_sink is a function that accepts only cars and vehicle_sink is a function that accepts any vehicle. Intuitively, it makes sense that if the client needs a car_sink, a vehicle_sink will work just fine because it is more general. Therefore, substitutability works in the reverse direction of parameter types. As a result, Sink is contravariant in its argument type.
<br/><br/>
std::function is covariant in return type too.
<pre class="brush: cpp">
std::function<Car * (Metal *)> car_factory =
[](Metal *){ std::cout << "Got some Metal\n"; return new Car(); };
std::function<Vehicle * (Iron *)> vehicle_factory = car_factory;
Vehicle * some_vehicle = vehicle_factory(new Iron()); // Works
</pre>
Covariance and Contravariance of std::function works with smart pointers too. I.e., std::function taking a shared_ptr of base type is convertible to std::function taking a shared_ptr of derived type.
<pre class="brush: cpp">
std::cout << std::is_convertible<std::function<void (std::shared_ptr<Vehicle>)>,
std::function<void (std::shared_ptr<Car>)>>::value
<< "\n"; // prints 1.
</pre>
<br/>
<strong>Sink of a Sink is a Source!</strong><br/><br/>
I hope the examples so far have helped build an intuition behind covariance and contravariance. So far it looks like types that appear in argument position should behave contravariantly and types that appear in return position, should behave covariantly. It's a good intuition only until it breaks!
<pre class="brush: cpp">
template <class T>
using Source = std::function<void (Sink<T>)>;
Source<Car> source_car = [](Sink<Car> sink_car){ sink_car(new Car()); };
source_car([](Car *){ std::cout << "Got a Car!!\n"; });
Source<Vehicle> source_vehicle = source_car; // covariance!
</pre>
Type T occurs at argument position in Source. So is Source contravariant in T?...
<br/><br/>
It's not! It's still covariant in T.
<br/><br/>
However, Source<T> is contravriant in Sink<T> though.... Afterall, Source is a <strong>Sink of a Sink<T></strong>!
<br/><br/>
OK, still with me?
<br/><br/>
Let's get this *&%$# straight!
<br/><br/>
Source<Car> does not really take Car as an argument. It takes Sink<Car> as an argument. The only thing you can really do with it is sink/pass a car into it. Therefore, the lambda passes a new car pointer to sink_car. Again on the next line, calling source_car you have to pass a Sink<Car>. That of course is a lambda that accepts Car pointer as input and simply prints a happy message.
<br/><br/>
Source<Car> indeed works like a factory of Cars. It does not "return" it. It uses a callback to give you your new car. It's equivalent to returning a new Car. After all, the direction of dataflow is outward. From Callee to the Caller. As the data is flowing outwards, it's covariant.
<br/><br/>
More formally, type of Source is (T->())->(). A function that takes a callback as an input and returns nothing (i.e., read () as void). As T appears on the left hand side of even number of arrows, it's covariant with respect to the entire type. As simple as that!
<br/><br/>
<h2>Generalizing with Multiple Arguments and Currying</h2>
The covariance and contravariance of std::function works seamlessly with multiple argument functions as well as when they are <a href="http://cpptruths.blogspot.com/2014/03/fun-with-lambdas-c14-style-part-1.html">curried</a>.
<pre class="brush: cpp">
struct Metal {};
struct Iron : Metal {};
struct Copper : Metal {};
// multiple contravariant position arguments
std::function<Vehicle * (Iron *, Copper *)> vehicle_ic;
std::function<Car * (Metal *, Metal *)> car_mm = [](Metal *, Metal *) { return new Car(); };
vehicle_ic = car_mm;
vehicle_ic(new Iron(), new Copper());
// Curried versions
std::function<std::function<Vehicle * (Copper *)> (Iron *)> curried_vehicle;
std::function<std::function<Car * (Metal *)> (Metal *)> curried_car;
curried_car = [](Metal *m) {
return std::function<Car * (Metal *)>([m](Metal *) { return new Car(); });
};
curried_vehicle = curried_car;
curried_vehicle(new Iron())(new Copper());
</pre>
The car_mm function can be substituted where vehicle_ic is expected because it accepts wider types and returns narrower types (subtypes). The difference is that these are two argument functions. Each argument type must be at least the same as what's expected by the client or broader.
<br/><br/>
As every multi-argument function can be represented in curried form, we don't want to throw way our nice co-/contra-variant capabilities of the function-type while currying. Of course, it does not as can be seen from the next example.
<br/><br/>
The curried_vehicle function accepts a single argument and returns a std::function. curried_car is a subtype of curried_vehicle only if it accepts equal-or-broader type and returns equal-or-narrower type. Clearly, curried_car accepts Metal*, which is broader than Iron*. On the return side, it must return a function-type that is a subtype of the return type of curried_vehicle. Applying the rules of function subtyping again, we see that the returned function type is also a proper subtype. Hence currying is oblivious to co-/contra-variance of argument/return types.
<br/><br/>
So that's it for now on co-/contra-variance. CIAO until next time!
<br/><br/>
<a href="http://melpon.org/wandbox/permlink/N88zRhrGxpxz040b">Live code</a> tested on latest gcc, clang, and vs2015.
<br/><br/>
For comments see <a href="https://www.reddit.com/r/cpp/comments/3styua/covariance_and_contravariance_in_c_standard/">reddit/r/cpp</a> and <a href="https://news.ycombinator.com/item?id=10567180">Hacker News</a>.
<br /></div>Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com14tag:blogger.com,1999:blog-13960885.post-54134423687839410752015-11-08T11:29:00.000-08:002015-12-29T12:17:16.857-08:00CppCon'15 and Silicon Valley Code Camp Presentations<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
In last couple of months I did a couple of presentations about my recent projects in C++. Session videos, slides, and code for all the presentations are now available online. Both projects have functional programming at their heart. I've found exploring functional programming in modern C++ quite a fun ride. Without further ado, here's the content<br />
<br />
<b><span style="font-size: large;">CppCon'15: Reactive Stream Processing in Industrial IoT using DDS and RxCpp</span></b><br />
<b><br /></b>
<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/G96QYlsfy_o" width="560"></iframe><b>
</b></div>
<b><br /></b>
<b>Topic:</b> 50 billion devices will be connected to the Internet by 2020. Many of them will belong to national critical infrastructure (smart power grids, smart roads, smart hospitals, smart cities) – forming the Industrial Internet of Things (IIoT). These devices will generate data streams that will need to be correlated, merged, filtered, and analyzed in real-time at the edge. This talk will explore an elegant solution to this problem that is productive, composable, concurrency-friendly, and scales well. We utilize OMG’s Data Distribution Service for Real-Time Systems (DDS) standard for connectivity, and Reactive Extensions (Rx) for functional-style composable asynchronous data processing in modern C++.<br />
<br />
Rx is a generalization of futures and can be thought of as the async equivalent of C++ ranges. It helps create asynchronous data processing pipelines by chaining reusable higher-order functions (map, filter, flatmap, zip etc.) that rely on a common abstraction called an Observable (a continuation monad). RxCpp makes wonderful use of functional programming features in modern C++ including generic lambdas, type inference, variadic templates, and more. Rx is one of the best libraries that truly highlights the power of functional design principles applied in a (primarily) object-oriented programming languages.<br />
<br />
DDS and Rx work great together because they are both reactive, use the publish-subscribe paradigm, and facilitate loose coupling between components. This presentation will discuss <a href="http://bit.ly/cppcon-rx4dds">Rx4DDS</a>, which is a research library that integrates Rx with RTI Connext DDS. Rx4DDS enables a clean, distributed, asynchronous dataflow architecture for stream processing and is available in C#, C++, and JavaScript.<br />
<br />
<b><span style="font-size: large;">Slides</span></b><br />
<b><span style="font-size: large;"><br /></span></b>
<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="355" marginheight="0" marginwidth="0" scrolling="no" src="//www.slideshare.net/slideshow/embed_code/key/ZKeYppf5BVRj5" style="border: 1px solid rgb(204, 204, 204); margin-bottom: 5px; max-width: 100%;" width="425"></iframe></div>
<br />
<div style="margin-bottom: 5px;">
<div style="text-align: center;">
<strong> <a href="https://www.slideshare.net/SumantTambe/reactive-stream-processing-in-industrial-iot-using-dds-and-rx" target="_blank" title="Reactive Stream Processing in Industrial IoT using DDS and Rx">Reactive Stream Processing in Industrial IoT using DDS and Rx</a> </strong> from <strong><a href="https://www.slideshare.net/SumantTambe" target="_blank">Sumant Tambe</a></strong> </div>
</div>
<br />
More reading<br />
<br />
<ul style="text-align: left;">
<li><span style="font-size: large;"><a href="http://blogs.rti.com/2015/10/26/data-centric-stream-processing-in-the-fog/">Data-Centric Stream Processing in the Fog</a></span> is an RTI blog post with detailed description of one of the demonstrations and code I showed at CppCon'15. If you know what I mean by <i><span style="font-family: "georgia" , "times new roman" , serif;">"The finalization actions are baked into each data pipeline at the time of creation"</span></i> you can skip right ahead.</li>
<br />
<li><a href="http://rticommunity.github.io/rticonnextdds-reactive/"><span style="font-size: large;">Rx4DDS home page</span></a> includes all the demonstrations and code I showed at CppCon. The description is somewhat sparse and assumes that you have seen the earlier resources listed here.</li>
</ul>
<hr />
<div>
<b><span style="font-size: large;"><br /></span></b>
<b><span style="font-size: large;">Silicon Valley Code Camp: Composable Generators and Property-based Testing in C++14 </span> </b></div>
<div>
<br /></div>
<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="282" mozallowfullscreen="" src="https://player.vimeo.com/video/141328500" webkitallowfullscreen="" width="500"></iframe>
</div>
<div>
<br />
<b>Topic:</b> C++14 has an enviable collection of functional programming features such as generic lambdas, type inference, variadic templates, function types with co-/contra-variance and so on. With mature compiler support, designing and implementing performant functional-style libraries has become very pleasant in modern C++. Tools and techniques (e.g., property-based testing) enjoyed by the programmers in only elite functional languages (Haskell, Scala) now appear to be within C++'s reach.<br />
<br />
This presentation will discuss two classic techniques from the functional domain -- composable data generators and property-based testing -- implemented in C++14 for testing a generic serialization and deserialization library (<a href="http://rticommunity.github.io/rticonnextdds-reflex/">RefleX</a>). We will look at techniques of constructing complex generators using a random number generator and a tolerable dose of monoids, functors, and of course, monads. We won't stop there though! We will look at automatic type generators using C++ TMP. Equipped with data and type generators, we'll take property-based testing to a whole new level where lazy programmers don't have to do anything to test their programs beyond just compilation and running the test over and over.<br />
<br />
<span style="font-size: large;"><b>Code on github:</b></span> <a href="https://github.com/sutambe/generators">generators</a><br />
<br />
<span style="font-size: large;"><b>Slides </b></span><br />
<br />
<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="355" marginheight="0" marginwidth="0" scrolling="no" src="//www.slideshare.net/slideshow/embed_code/key/rJSSXfkT6ucInl" style="border-width: 1px; border: 1px solid #CCC; margin-bottom: 5px; max-width: 100%;" width="425"> </iframe> </div>
<div style="margin-bottom: 5px;">
<div style="text-align: center;">
<strong> <a href="https://www.slideshare.net/SumantTambe/c-generators-and-propertybased-testing" target="_blank" title="C++ Generators and Property-based Testing">C++ Generators and Property-based Testing</a> </strong> from <strong><a href="https://www.slideshare.net/SumantTambe" target="_blank">Sumant Tambe</a></strong> </div>
</div>
<br />
<br /></div>
</div>
<hr />
<span style="font-size: large;"><b>Bonus Content: Channel9 Interview at CppCon'15</b></span><br />
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Here's my really short interview recorded at CppCon'15 by Channel9. Yes, it's about functional programming! Skip ahead to 45m36s into the video to checkout my segment. Alternatively, <a href="https://channel9.msdn.com/Shows/C9-GoingNative/GoingNative-43-Talks-and-Tips-from-the-Experts-at-CppCon-2015/player?#time=45m36s" target="_">click here</a>.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://channel9.msdn.com/Shows/C9-GoingNative/GoingNative-43-Talks-and-Tips-from-the-Experts-at-CppCon-2015/player?#time=45m36s" target="_"><img border="0" height="360" src="http://4.bp.blogspot.com/-aAJfsbakP7o/VoLo_qAkc2I/AAAAAAAACOA/WFSIURTMp_c/s640/cpp-interview-video-play.png" width="640" /></a><span id="goog_723396494"></span><span id="goog_723396495"></span><a href="https://www.blogger.com/"></a></div>
<br /></div>
</div>
Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com0tag:blogger.com,1999:blog-13960885.post-67200329766698296172015-06-28T11:36:00.000-07:002015-06-29T11:39:27.211-07:00Fun with Lambdas: C++14 Style (part 4)<div dir="ltr" style="text-align: left;" trbidi="on">
This is part 4 in the series of <b>Fun with Lambdas: C++14 Style</b>. The previous posts are <a href="http://cpptruths.blogspot.com/2014/08/fun-with-lambdas-c14-style-part-3.html">part 3</a>, <a href="http://cpptruths.blogspot.com/2014/05/fun-with-lambdas-c14-style-part-2.html">part 2</a>, and <a href="http://cpptruths.blogspot.com/2014/03/fun-with-lambdas-c14-style-part-1.html">part 1</a>.
<br/><br/>
C++14 has a number of features that support functional-style design. By "functional-style" I mean heavy use of higher-order functions (functions that take other functions as arguments). Quite often arguments to the higher-order functions are lambdas (closures, to be precise). With automatic return type deduction for normal functions, writing higher-order function becomes very easy and seamless in C++14.<br />
<br />
This time, I have chosen a "text-book" example to show you the power of C++14: <b>Composable Data Generators</b><br />
<b><br /></b><b><span style="font-size: large;">What is a Generator?</span></b><br /><br />
A <span style="font-family: courier new,monospace; font-size: large">Generator<T></span> produces values of type <span style="font-family: courier new,monospace; font-size: large">T</span> randomly. There is already a random number generator defined in the C library: <span style="font-family: courier new,monospace; font-size: large">random()</span>. It produces long ints.</t><br />
<br />
We can use this basic generator to create higher-level generators, such as bool, character, floating point numbers, etc. Even random sequence and structure generators are possible.<br />
<br />
But first, lets add some structure around the C library function so that we can compose generators.<br />
<br /><pre class="brush: cpp">
#include <cstdlib>
struct RootRandomGen
{
long int operator () () const
{
return random();
}
};
</pre><br/>
<span style="font-family: courier new,monospace; font-size: large">RootRandomGen</span> is a very simple function-object that when called produces a random number between 0 and <span style="font-family: courier new,monospace; font-size: large">RAND_MAX</span>.
<br/><br/>
Let's create a Generator template from which we can create other generators.
<br /><pre class="brush: cpp">
template <class T, class GenFunc>
class Gen
{
GenFunc genfunc;
public:
explicit Gen(GenFunc func)
: genfunc(std::move(func))
{ }
T generate()
{
return genfunc();
}
};
</pre><br/>
The Gen class template allows us to pass any function-object or closure and a make a "generator" out of it. Of course, the function must not take any arguments and must produce a value.
<br/><br/>
To simplify creation of Generators from just lambdas, we create a helper factory function. This is where the power of C++14 starts becoming apparent.
<br /><pre class="brush: cpp">
template <class GenFunc>
auto make_gen_from(GenFunc&& func)
{
return Gen<decltype(func()), GenFunc>(std::forward<GenFunc>(func));
}
</pre><br/>
<span style="font-family: courier new,monospace; font-size: large">make_gen_from</span> is a higher-order function that takes a closure as an argument and creates a <span style="font-family: courier new,monospace; font-size: large">Gen<T></span> object. GenFunc is the type of the closure. The type T is deduced using <span style="font-family: courier new,monospace; font-size: large">decltype(func())</span>, which is C++14 syntax to say whatever the type of the return value of func is. Rest of it is perfect-forwarding of the func argument to the <span style="font-family: courier new,monospace; font-size: large">Gen<T></span> object.
<br/><br/>
To create many more generators, such as for bool, char, string, etc, a function like <span style="font-family: courier new,monospace; font-size: large">make_gen<T></span> might be quite useful. So, let's add one.
<br /><pre class="brush: cpp">
template <class T>
auto make_gen();
template <>
auto make_gen<long int>()
{
return make_gen_from(RootRandomGen());
//return make_gen_from([]() { return random(); });
}
</pre><br/>
The long int generator simply uses the "Root" generator. Alternatively, <span style="font-family: courier new,monospace; font-size: large">RootRandomGen</span> can be defined in-place using a lambda as shown above. I.e., RootRandomGen is superfluous.
<br/><br/>
Let's test what we've so far.
<br /><pre class="brush: cpp">
void init_random()
{
time_t t;
time(&t);
srandom(t);
}
int main(void)
{
init_random();
auto gen = make_gen<long int>();
std::cout << gen.generate(); // expect a random value.
}
</pre><br/>
We can create many more generators by explicitly specializing make_gen for a number of types. But before we do that let's observe the core properties of <span style="font-family: courier new,monospace; font-size: large">Gen<T></span>.
<br /><br />
<b><span style="font-size: large">The Generator<T> Functor</span></b>
<br/><br/>
In functional programming literature, <span style="font-family: courier new,monospace; font-size: large">Gen<T></span> is a <a href="https://en.wikipedia.org/wiki/Functor">functor</a>, which means you can "map over it". I.e., you can write a function named map that takes a generator and a function and returns another generator that applies the function to the values generated by the argument generator. It's much easier to look at code.
<br /><pre class="brush: cpp">
template <class Gen, class Func>
auto map (Gen gt, Func func)
{
return make_gen_from([gt, func]() {
return func(gt.generate());
});
}
</pre><br/>
First, the lambda captures gt and func by value. When called, it first generates a value from gt and passes it to the function and simply returns the value produced by the function. We've already seen that make_gen_from converts any lambda (with right signature) to a generator. So we now have a very general-purpose facility to create arbitrarily many generators simply by passing functions to map.
<br/><br/>
Let's look at an example.
<br /><pre class="brush: cpp">
int main(void)
{
init_random();
auto gen = make_gen<long int>();
auto boolgen = map(gen, [](long int i) { return bool(i % 2); });
std::cout << std::boolalpha << boolgen.generate(); // expect a random boolean.
}
</pre>
<br />
The only problem, however, is that it does not work.
<br/><br/>
The problem is that <span style="font-family: courier new,monospace; font-size: large">Gen<T></span> is designed to support stateful generators that might mutate state between two successive calls to generate. That's why the generate function is not const. But the lambda in the map function is by default const. Therefore, gt is also const, which prevents us from calling <span style="font-family: courier new,monospace; font-size: large">gt.generate()</span> as <span style="font-family: courier new,monospace; font-size: large">Gen<T>::generate()</span> is a non-const function.
<br/><br/>
The solution is to make the lambda in map function mutable. With that, the program compiles but there are more things that can be improved about map.
<br/><br/>
First, gt and func arguments are passed by value and the lambda captures them by value. That may be potentially quite wasteful. We can improve efficiency by using perfect forwarding. Adding perfect forwarding, however, adds a lot of noise to the otherwise simple map function. This noise has become my pet peeve regarding functional-style programming in C++14.
<br /><pre class="brush: cpp">
template <class Gen, class Func>
auto map (Gen&& gt, Func&& func)
{
return make_gen_from([gt=std::forward<Gen>(gt),
func=std::forward<Func>(func)]() mutable {
return func(gt.generate());
});
}
</pre><br/>
I think this map function is a well-behaved citizen of the C++14 world. It's using the generalized lambda capture syntax and perfect-forwarding in combination.
<br/><br/>
Using this map function is slightly awkward because it's a free function. To support more <a href="https://en.wikipedia.org/wiki/Fluent_interface">fluent</a> style of API, I would like to "upgrade" the map function to the <span style="font-family: courier new,monospace; font-size: large">Gen<T></span> class. As I said before, <b>every</b> generator supports mapping. So here's the new Get<T> template.
<br /><pre class="brush: cpp">
template <class T, class GenFunc>
class Gen
{
GenFunc genfunc;
public:
explicit Gen(GenFunc func)
: genfunc(std::move(func))
{ }
T generate()
{
return genfunc();
}
template <class Func>
auto map (Func&& func)
{
return make_gen_from([gt=*this,
func=std::forward<Func>(func)]() mutable {
return func(gt.generate());
});
}
};
</pre><br />
Note that map makes a full copy of this in the lambda so that every generator becomes self-sufficient.
<br/><br/>
We can create a number of other generators using the built-in map function. For instance, an consider Gen<int> below.
<br /><pre class="brush: cpp">
template <>
auto make_gen<int>()
{
return make_gen<long int>().map([](long int i) { return static_cast<int>(i); });
}
</pre><br />
A range generator that produces a random value in the specified range may be created as follows. Like in the iterator semantics, hi is one past the desirable range.
<br /><pre class="brush: cpp">
template <class Integer>
auto make_range_gen(Integer lo, Integer hi)
{
return make_gen<long int>().map(
[lo, hi](long int x) { return static_cast<Integer>(lo + x % (hi - lo)); });
}
</pre><br />
Using the range generator, a generator for uppercase characters is quite simple.
<br /><pre class="brush: cpp">
auto uppercase_gen = make_range_gen('A', 'Z'+1);
std::cout << uppercase_gen.generate(); // expect a random uppercase character.
</pre><br />
<b><span style="font-size: large;">Combinators</span></b>
<br/><br/>
Many more helper functions can be added to the <span style="font-family: courier new,monospace; font-size: large">Gen<T></span> class that produce new generators from argument generators. In functional literature they are called <a href="http://stackoverflow.com/questions/7533837/explanation-of-combinators-for-the-working-man">combinators</a>.
<br/><br/>
Here's the <span style="font-family: courier new,monospace; font-size: large">zip2</span> combinator: Zip works just like a zipper. It takes 2 generators and produces another generator that combines the values generated by the argument generators. To combine the values, it needs a function that accepts two arguments and return a value. The user must provide the function.
<br/>
<br /><pre class="brush: cpp">
template <class T, class GenFunc>
class Gen
{
// ....
template <class UGen, class Zipper2>
auto zip2(UGen&& ugen, Zipper2&& func)
{
return this->map(
[ugen=std::forward<UGen>(ugen),
func=std::forward<Zipper2>(func)](auto&& t) mutable {
return func(std::forward<decltype(t)>(t), ugen.generate());
});
}
};
auto uppergen = make_range_gen<char>('A', 'Z'+1);
auto lowergen = make_range_gen<char>('a', 'z'+1);
auto pairgen =
uppergen.zip2(lowergen,
[](char up, char low) { return std::make_pair(up, low); });
</pre><br />
The example above shows how a pair of random characters can be produced by zipping an uppercase generator with a lowercase generator. The zipper function simply constructs the pair from two characters. Alternatively, <span style="font-family: courier new,monospace; font-size: large">&std::make_pair<char, char></span> would have been sufficient.
<br/><br/>
The zip2 function looks significantly more verbose than a comparable implementation in most other languages that support lambdas. A lot of code is devoted to perfect-forwarding of arguments, which is quite necessary for highly composable libraries such as this one. We'll see later that C++ compilers are smart enough to inline the call-chain completely.
<br/><br/>
Another example of zip is string generator. A string generator zips a bool generator and int generator where the bool value indicates whether string is empty or not and int generator determines the length of the string. Of course, string generator also needs a char generator to populate the string. Here's one way of doing it.
<br /><pre class="brush: cpp">
template <>
auto make_gen<std::string>()
{
auto char_gen = make_range_gen(32, 127); // printable characters.
auto length_gen = make_range_gen(1, 256);
return make_gen<bool>().zip2(
length_gen,
[char_gen](bool empty, int length) mutable {
std::string str;
if(!empty)
{
str.reserve(length);
for(int i = 0; i < length; ++i)
str.push_back(char_gen.generate());
}
return str;
});
}
</pre><br/>
There are many more combinators. The <span style="font-family: courier new,monospace; font-size: large">single</span> generator would always produce the same value. The <span style="font-family: courier new,monospace; font-size: large">oneOf</span> generator selects one of the elements from a given array non-deterministically. Finally, the <i>amb</i> combinator will use of the two input combinators to produce value. Here's a couple of them.
<br /><pre class="brush: cpp">
template <class T>
auto make_single_gen(T&& t)
{
return make_gen_from([t=std::forward<T>(t)]() { return t; });
}
template <class T>
auto make_oneof_gen(std::initializer_list<T> list)
{
return make_range_gen(0ul, list.size()).map([list](int idx) { return *(list.begin()+idx); });
}
</pre><br/>
<b><span style="font-size: large;">Stateful Generators</span> </b> <br/><br/>
The examples we've seen so far are stateless generators. I.e., between two successive calls to generate, no state is updated. Let's look at a stateful generator: <span style="font-family: courier new,monospace; font-size: large">fibonacciGen</span>. This generator must maintain at least two integers (a and b) for its computation.
<br /><pre class="brush: cpp">
auto fiboGen()
{
int a = 0;
int b = 1;
return make_gen_from([a, b]() mutable {
int c = a;
a = b;
b = c+b;
return c;
});
}
</pre><br/>
<b><span style="font-size: large;">The Cost of Functional Design</span></b><br/>
<br/>
It is quite interesting how complex generators can be created from simple generators. But is there a cost to this high level of abstraction? Is the code as fast as it can be?
<br/><br/>
Here are two different algorithmically identical implementations of bool generator. The reason I chose this algorithm because I wanted make use of zip2, which in turn uses map. I wanted to include multiple levels of indirection.
<br /><pre class="brush: cpp">
extern "C" bool random_bool1()
{
return (random()-random()) > 0;
}
extern "C" bool random_bool2()
{
auto boolgen =
make_gen<long int>()
.zip2(make_gen<long int>(),
[](long int i, long int j) { return (i-j) > 0; });
return boolgen.generate();
}
</pre><br/>
The screenshot below shows the compiler's assembly output for both the functions. The amazing fact is that it is exactly identical! The compiler is able to see through the layers and layers of indirections (invocations of lambdas) and is able to produce optimal code for the random_bool functions. That's quite a remarkable feat achieved by g++ 5.1 in this case. Perhaps it is the same with other major C++ compilers.
<br/>
<div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-oADT-UHAm9I/VY-dfQwUfhI/AAAAAAAACHo/ji59HZsuHZI/s1600/random_bool.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-oADT-UHAm9I/VY-dfQwUfhI/AAAAAAAACHo/ji59HZsuHZI/s400/random_bool.png" /></a></div>
<br/>
<b><span style="font-size: large;">Generator size</span></size></b>
<br/><br/>
The performance story does not end here though. Note that producing a random boolean does not need any state. I.e., it is just a function. However, RootRandomGen take one byte because it's a class. Every object in C++ must have a unique identity. To ensure that's the case, C++ compiler gives minimal possible size to each object. As we compose higher-level generators from smaller generators, we are clearly creating objects, which have non-zero sizes. But how much memory do they need exactly? What is the size of boolgen in random_bool2?
<br/><br/>
The size of boolgen is 3 bytes on my machine. The reason for the state is lambda captures. Both map and zip combinators use lambdas with one or more captures. As higher-level generators are built from lower level generators, the state adds up. The problem is that in most generators we've seen so far, there is no real reason to maintain state between two successive calls to the generate function. I.e, the next value is completely unrelated to the previous values. In fact, as we saw before, the compiler did not refer to any state in the implementation of <span style="font-family: courier new,monospace; font-size: large">random_bool2</span>. Of course, for truly stateful generators such as the the fibonacci generator, maintaining state from the prior computation is necessary.
<br/><br/>
The build-up of unnecessary state is quite fast though. For instance, the size of the string generator is whopping 28 bytes! The compiler maintains 28 bytes of state and does not serve any obvious purpose to the user! A generator of printable strings implemented as a simple function would require no persistent state at all. As the size of the generators get larger and larger, pretty soon they won't fit in the cache line and will start to degrade performance, especially if truly stateful generators are mixed with only <i>accidently</i> stateful generators. I hope compiler writers will figure something out about this problem.
<br/><br/>
This concludes the part 4 in the series of Fun with Lambdas: C++14 Style. I hope you enjoyed it. See <a href="http://coliru.stacked-crooked.com/a/505b92499309415a">Live Example</a>.
<br /></div>Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com15tag:blogger.com,1999:blog-13960885.post-85966535263704764142014-09-28T23:35:00.003-07:002014-12-29T11:49:28.374-08:00Fun with C++14 Lambdas at Silicon Valley Code Camp<div dir="ltr" style="text-align: left;" trbidi="on">
Believe it or not, but the 9th <a href="http://www.siliconvalley-codecamp.com/">Silicon Valley Code Camp</a> is less than 2 weeks away and I can't wait to be at the largest software technology conference setup by developers for developers---and here is the best part---at no cost to the attendees. So far, there are 234 registered sessions, 7 technical <a href="http://www.siliconvalley-codecamp.com/Track">tracks</a>, and over 3100 registrations. So mark your calendar--it's October 11th and 12th, Saturday and Sunday, as always.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.siliconvalley-codecamp.com"><img border="0" src="http://cache.siliconvalley-codecamp.com/Images/silicon-valley-code-camp.png" height="100" width="640" /></a></div>
<br />
<br />
C++ is hot again at SVCC and third year in a row there is a dedicated track for modern C++. There are <a href="http://www.siliconvalley-codecamp.com/Track/2014/c-is-hot">11 sessions</a> covering a wide variety of topics related to modern C++ programming.<br />
<br />
I wanna thank SVCC organizers who generously allowed me to present two sessions: The first one is titled: <a href="http://www.slideshare.net/SumantTambe/fun-with-lambdas-c14-style">Fun with Lambdas: C++14 Style</a>[<a href="https://vimeo.com/108763723">video</a>]. You may be following the Fun with Lambdas series on this blog and hopefully having some fun too! I'll present a sampling of the content discussed here with new insights. Check out <a href="http://cpptruths.blogspot.com/2014/03/fun-with-lambdas-c14-style-part-1.html">part 1</a>, <a href="http://cpptruths.blogspot.com/2014/05/fun-with-lambdas-c14-style-part-2.html">part 2</a>, and <a href="http://cpptruths.blogspot.com/2014/08/fun-with-lambdas-c14-style-part-3.html">part 3</a> if you haven't already. Come see how functional programming techniques are going to change the face of C++ programming beyond recognition.<br />
<iframe src="//player.vimeo.com/video/108763723" width="500" height="281" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen></iframe> <p><a href="http://vimeo.com/108763723">Fun with Lambdas: C++14 Style</a> from <a href="http://vimeo.com/user29254745">Sumant Tambe</a> on <a href="https://vimeo.com">Vimeo</a>.</p>
<br />
The second sessions is about <a href="http://www.slideshare.net/SumantTambe/reactive-stream-processing-using-dds-and-rx">Reactive Programming with DDS and Rx</a>[<a href="https://vimeo.com/108753792">video</a>]. It's about functional programming again but this time it's going to be C#. <a href="http://msdn.microsoft.com/en-us/data/gg577609.aspx">Reactive Extensions</a> (Rx) is a fascinating new technique to compose asynchronous and event-based programs using observables and LINQ-style query operators. It fits extremely well with DDS--a data distribution technology for networked real-time systems. I'll demo commonly used Rx operators with real data coming off of a toy DDS example. More on that <a href="http://blogs.rti.com/2014/04/09/reactive-programming-using-rx4dds/">here</a>.<br />
<br />
<iframe src="//player.vimeo.com/video/108753792" width="500" height="281" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen></iframe> <p><a href="http://vimeo.com/108753792">Reactive Stream Processing Using DDS and Rx</a> from <a href="http://vimeo.com/user29254745">Sumant Tambe</a> on <a href="https://vimeo.com">Vimeo</a>.</p>
All in all, I'm anticipating the SVCC'14 to be a pretty busy weekend once again with a lot of learning and sharing. If you are in the area and decide to attend, stop by and say hi!</div>Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com4tag:blogger.com,1999:blog-13960885.post-64460327310601059722014-09-20T12:56:00.000-07:002014-09-21T16:43:25.038-07:00Short-circuiting overloaded && and || using expression templates<div dir="ltr" style="text-align: left;" trbidi="on">
This blog post is just a quick note that C++ offers (at least) two distinct ways to represent lazy computation that is lexically in the same scope but may execute lazily at a later time. In doing so, the computation must capture the local context (i.e., variables) so that it can be used later when needed. Clearly, lambda expressions are a direct language supported mechanism for that. Closures that come out of a lambda expression often capture the context and of course some behavior to be run later. The second mechanism is about 20 years old (as of this writing): <a href="https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Expression-template">Expression Templates</a>.
<br/><br/>
Lets take an example of <b>short-circuiting</b> overloaded && and || operators. Regular overloaded && and || do not short circuit in C++. The reason is that before calling the overloaded operator &&, both the left-hand-side and the right-hand-side arguments of the overloaded function are evaluated. A function call is a sequence-point and therefore all the computations and the side-effects are complete before making the function call. This is eager strategy.
<br/><br/>
Expression Templates is a library-only approach to defer computation at a later time while keeping the context of the original expression around. Sounds a lot like lambda expressions.
<br/><br/>
Consider the struct S below. I would like to implement short-circuiting && and || for this type.
<br/><br/>
<pre class="brush: cpp">
struct S
{
bool val;
explicit S(bool b) : val(b) {}
bool is_true () const
{
return val;
}
};
S operator && (const S & s1, const S & s2)
{
return s1.is_true()? S{s1.val && s2.val} : s1;
}
int main(void)
{
S s1{false}, s2{true}, s3{true};
S s4 = s1 && s2 && s3; // false
}
</pre>
There is hardly any optimization at all. The overloaded && operator is called twice no matter what. Although the result of the expression s1 && s2 && s3 is known just by looking at s1. An opportunity for optimization is wasted (if you ever wanted to optimize that way!).
<br/><br/>
So let's use expression templates. The trick is to convert the expression into a tree of recursively nested instantiations of the Expr template. The tree is evaluated separately after construction.
<br/><br/>
The following code implements short-circuited && and || operators for S as long as it provides logical_and and logical_or free functions and it is convertible to bool. The code is in C++14 but the idea is applicable in C++98 also.
<br/><br/>
<pre class="brush: cpp">
#include <iostream>
struct S
{
bool val;
explicit S(int i) : val(i) {}
explicit S(bool b) : val(b) {}
template <class Expr>
S (const Expr & expr)
: val(evaluate(expr).val)
{ }
template <class Expr>
S & operator = (const Expr & expr)
{
val = evaluate(expr).val;
return *this;
}
bool is_true () const
{
return val;
}
};
S logical_and (const S & lhs, const S & rhs)
{
std::cout << "&& ";
return S{lhs.val && rhs.val};
}
S logical_or (const S & lhs, const S & rhs)
{
std::cout << "|| ";
return S{lhs.val || rhs.val};
}
const S & evaluate(const S &s)
{
return s;
}
template <class Expr>
S evaluate(const Expr & expr)
{
return expr.eval();
}
struct LazyAnd
{
template <class LExpr, class RExpr>
auto operator ()(const LExpr & l, const RExpr & r) const
{
const auto & temp = evaluate(l);
return temp.is_true()? logical_and(temp, evaluate(r)) : temp;
}
};
struct LazyOr
{
template <class LExpr, class RExpr>
auto operator ()(const LExpr & l, const RExpr & r) const
{
const auto & temp = evaluate(l);
return temp.is_true()? temp : logical_or(temp, evaluate(r));
}
};
template <class Op, class LExpr, class RExpr>
struct Expr
{
Op op;
const LExpr &lhs;
const RExpr &rhs;
Expr(const LExpr& l, const RExpr & r)
: lhs(l),
rhs(r)
{}
auto eval() const
{
return op(lhs, rhs);
}
};
template <class LExpr>
auto operator && (const LExpr & lhs, const S & rhs)
{
return Expr<LazyAnd, LExpr, S> (lhs, rhs);
}
template <class LExpr, class Op, class L, class R>
auto operator && (const LExpr & lhs, const Expr<Op,L,R> & rhs)
{
return Expr<LazyAnd, LExpr, Expr<Op,L,R>> (lhs, rhs);
}
template <class LExpr>
auto operator || (const LExpr & lhs, const S & rhs)
{
return Expr<LazyOr, LExpr, S> (lhs, rhs);
}
template <class LExpr, class Op, class L, class R>
auto operator || (const LExpr & lhs, const Expr<Op,L,R> & rhs)
{
return Expr<LazyOr, LExpr, Expr<Op,L,R>> (lhs, rhs);
}
std::ostream & operator << (std::ostream & o, const S & s)
{
o << s.val;
return o;
}
S and_result(S s1, S s2, S s3)
{
return s1 && s2 && s3;
}
S or_result(S s1, S s2, S s3)
{
return s1 || s2 || s3;
}
int main(void)
{
for(int i=0; i<= 1; ++i)
for(int j=0; j<= 1; ++j)
for(int k=0; k<= 1; ++k)
std::cout << i << j << k << " " << and_result(S{i}, S{j}, S{k}) << std::endl;
for(int i=0; i<= 1; ++i)
for(int j=0; j<= 1; ++j)
for(int k=0; k<= 1; ++k)
std::cout << i << j << k << " " << or_result(S{i}, S{j}, S{k}) << std::endl;
return 0;
}</pre>
Let's break it apart piece by piece.
<br/><br/>
Type S has new conversion and assignment operators that convert a generic Expr argument that is convertible to S. The expression is not evaluated until it is actually assigned to another S. We just call evaluate on the expression to begin execution of the computation wrapped inside Expr. logical_and and logical_or are free functions that perform the non-short-circuiting logical operations because we're going to hijack the overloaded && and || for short-circuiting.
<br/><br/>
The evaluate free functions take care of the trivial base case when Expr happens to just another S and all other cases when Expr is a compound expression.
<br/><br/>
struct LazyAnd and LazyOr are the short-circuiting && and ||. They always evaluate the left-hand-side but may not evaluate the right-hand-side if it is not required.
<br/><br/>
Expr template enables construction of so called expression templates. It is meant to be instantiated recursively. for example, an expression template for (s1 && s2) looks like Expr<LazyAnd, S, S> whereas for (s1 && s2 && s3) it is Expr<LazyAnd, Expr<LazyAnd, S , S>, S>. One last example: (s1 && (s2 && s3)) becomes Expr<LazyAnd, S, Expr<LazyAnd, S , S>>.
<br/></br/>
Of course, creating the nested Expr instantiations manually is berserk. So we use overloaded && and || operators that instead of computing the result eagerly, produce and expression that we can evaluate later. I've avoided writing overly generic && and || operator by using the second argument that is either S or and Expr. So the operator does not match with types outside those. Take a look at the examples above. It is fairly straightforward
to see how an expressions turns into a tree. Note that construction of tree does not involve calling logical_and and logical_or functions
<br/><br/>
Finally, the assignment operator and copy-ctor of S take care of executing the expression. LazyAnd and LazyOr do the least possible work while ensuring that left-hand-side is always evaluated. Here is the output of the program. Checkout the live example <a href="http://coliru.stacked-crooked.com/a/e20acff2047b1645">here</a>.
<pre class="brush: cpp">
000 0
001 0
010 0
011 0
100 && 0
101 && 0
110 && && 0
111 && && 1
000 || || 0
001 || || 1
010 || 1
011 || 1
100 1
101 1
110 1
111 1
</pre>
Bottom line: Expression templates and lambdas are both suitable for passing lazy computations to functions. They both can capture local context (variables) and don't extend the life-cycle of the captured argument. Their type is not meant to be observed (it is often unpronounceable). Expression templates, however, are very specific because they appear only in the context of overloaded operators and as a result they may be lot more expressive.
<br/><br/>
This blog post is motivate by <a href="http://stackoverflow.com/questions/25913237/is-there-actually-a-reason-why-overloaded-and-dont-short-circuit">this</a> question on Stackoverflow. Also see comments on <a href="http://www.reddit.com/r/cpp/comments/2gzvtg/shortcircuiting_overloaded_and_using_expression/">reddit/r/cpp</a>.
<br /></div>Sumanthttp://www.blogger.com/profile/11957855386259543653noreply@blogger.com4