Digest of C++ posts

Contents

  1. Subclassing problems and solutions, predicate classes, and assignment-free programming in C++ [a separate set of documents]
  2. Genuine Lambda-abstractions in C++
  3. Functional Style in C++: Closures, Late Binding, and Lambda Abstractions [in a separate document]
  4. C++ compiler as a type term rewriting engine
     
  5. Universally polymorphic lists in ANSI C without casts [in a separate document]
  6. Can software development be elevated from the Microsoft style?
  7. A solution to a Fragile Base-Class Problem
  8. Programming in a Finite Automaton style
  9. A simple implementation of <iostream>
     
  10. Why C++ is not very fit for GUI programming
  11. Keyword arguments of C++ functions
  12. Pointers as closures
  13. scheming with the C preprocessor: a computable #include
  14. Chess tournament scheduling: tough but possible
     
  15. Speaking in Iostreams-ese, C/C++ Users Journal, v.15, No. 5, May 1997, pp. 47-55
  16. Transparent incorporation of MacOS data structures into C++
  17. Opaque bases/variables in a class: kludges, suggestions, and dreams
  18. Pointers to class methods: taking, storing, using [Hack]
  19. Cool way of iterating in a local context; nested functions in C++
    • Local procedures and natural iterators in C++ [absurd example]
  20. Virtual circling around in clouds (w/ C++ source)
  21. C++ is good for writing OS kernels. Here's an example.
  22. Advanced Finite Automaton as a simple HTML formatter

[Announcements and descriptions of various software packages: refer to an appropriate document describing the package]

  1. c++advio - portable handling and compression of binary data
  2. grayimage_classlib
  3. Async relaying of TCP packets by a Finite Automaton [small example]
  4. (lazy) SVD promising a matrix in extended LinAlg.shar


 

Can software development be elevated from the Microsoft style?

  A paper and a talk presented at MacHack'96, The 11th Annual Conference for Leading Edge Developers.

Summary
 composing safe, fast, and beautiful code in C++ and C. With an unusual slant on safety and performance, the paper discusses serial (vs. random) access to a collection, pointers vs. references, function classes, incorporation, transient object and classes.
The paper introduces a number of efficient and powerful (yet obscure) patterns that make code safe and neat: precision-targeted pointers, nested functions, lazy objects, stealing of a body, natural iterators. A few good and bad code snippets show off the benefits of well-crafted code.

Keywords
  style, C++, iterator, lazy object, patterns
References
 

the paper [.ps.gz, 64K]

The talk itself
complements the paper while not repeating it

A collection of the HTML pages that make up the talk [.tar.gz, 15K]

 

A solution to a Fragile-Base Class Problem

When a base class of a class hierarchy is extended with new data members, overridden virtual methods, or even with new virtual functions, it is nevertheless possible to avoid rebuilding of the entire hierarchy. One can bypass recompilation for a rather long limb of a class derivation tree.

This technique requires some discipline in building a hierarchy, but in return guarantees that only the top-most class needs to be recompiled to take into account modifications made to a base class. The rest of the hierarchy (which may have been compiled to a set of separate libraries) may be used as it is.

See it for yourself, by building, "upgrading", and not recompiling sample "libraries" and targets in FBCSolution.tar.gz. Check out the README file for more details.
June 27, 1997


 

Genuine Lambda-abstractions in C++

  The following code snippet speaks for itself. It is not a toy: the snippet is taken from an actual working code, a part of LinAlg, a Linear Algebra and Optimization classlib. This code is to verify that my implementation of the Brent root finder really works:
   main(void)
   {
     printf("\n\n\t\tTesting Brent's root finder\n\n");
     MakeTestFunction("cos(x)-x",
         Lambda((const double x),double,return cos(x)-x)) fcos;
     fcos.run(-1.0,3.0,0.739085133);

     MakeTestFunction("x^3 - 2*x - 5, from the Forsythe book",
         Lambda((const double x),double,
             return (sqr(x)-2)*x - 5))().run(2.0,3.0,2.0945514815);
   }
This code is C++ standard-compliant. It compiles with gcc 2.8.1 and Visual C++ 5.0, and runs successfully.

The last three lines of the code constitute a single expression, which creates a few "anonymous" objects, uses them and destroys afterwards. The first argument of the MakeTestFunction() is the title of a test case; the second argument is a test's body itself, specified as an anonymous function: a genuine lambda abstraction. The whole MakeTestFunction clause has the obvious meaning of defining a test case datatype, which is subsequently instantiated and run.

The Lambda() macro really makes a "body" (functor) without a name; the name may be attached -- "bound to" -- later.

Compare the above C++ code with an equivalent Scheme
   (define fcos (make-test "cos(x)-x" (lambda (x) (- (cos x) x))))

or e-lisp code
   (defun fcos (lwb upb expected-result) "testing cos(x)-x"
    (do-test lwb upb expected-result (lambda (x) (- (cos x) x))))

 

References
 

The original source code [.cc, 2K]
which reveals what Lambda's actually are

Basic Linear Algebra and Optimization classlib
the above code is a part of. You need the package (a few files of it, actually) to compile and run the example.

Functional Style in C++: Closures, Late Binding, and Lambda Abstractions
A poster presentation at ICFP'98, which shows a few more elements of a functional-style programming in C++.

Lambda abstractions in C++ vs. Scheme
Four more examples of lambda-expressions, closures, and currying in C++

 

Pointers as closures

 

There is a deep connection between C pointers on one hand, and Scheme closures that respond to the messages ref and set on the other hand. We can therefore precisely emulate the semantics of & in Scheme. We can also say that C has a limited form of closures.

The article referenced below demonstrates the connection by re-writing -- almost verbatim -- two C code fragments into Scheme. The C samples rely on pointers to let invoked functions share and mutate the variables local to the caller. For example, the following C fragment

     void modify(int ** p, int * py)
     {
       **p = *py * *py;
       *p = py;
     }
becomes in Scheme
     (define (modify p py)
       ((*= (* p)) (* (* py) (* py)))
       ((*= p) py)
     )
The technique can easily be generalized to permit pointer arithmetics as well.
 
References
 

A USENET article C pointer <-> Scheme closure: how to emulate & in Scheme [plain text file]
The article was posted on a newsgroup comp.lang.scheme on Tue, 26 Feb 2002 15:01:31 -0800

A Usenet discussion Why can't mutation be expressed mathematically??
A sub-thread between October 1 and October 5, 2001.

 

A simple implementation of <iostream>

Metrowerk's C++ development environment under BeOS PR1 makes it difficult to use C++ iostream facility: even a simple { cout << "Hello, world" << endl; } code builds to a 64K+ executable.

This "iostream.h" remedies the situation: this single file implements the bulk of the commonly used iostream functionality: That is, your code may contain something like

     int d; double f;
     cout << "Enter two numbers" << endl; cin >> d >> f;
     cout << "The numbers are " << d << " and " << f << endl;
and it will compile and work (with this iostream.h included), without any changes in your code whatsoever.
Made at a Be Dev kitchen on Dec 13, 1996 (in 5 minutes)

In much more detail, and in a much broader context, this code is described in the article Speaking in Iostreams-ese, published in C/C++ Users Journal, v.15, No. 5, May 1997, pp. 47-55.


 

Keyword arguments of C++ functions

  The article which is referred to below talks about implementing keyword function arguments in several languages, including C++. A "dictionary" of C++ function's arguments can be constructed and searched either at run time, or at compile time. The first solution is rather straightforward, and is mentioned rather briefly. The article then gives a complete example, which shows how construction of this "argument environment" and variable lookups can be done entirely at compile time (see the middle of the article).
 
References
 

A USENET article explaining the technique [plain text file]
which tries to talk about keyword and default arguments in a rather general way, with examples in Scheme, C++, Perl and a bit of Haskell

Advanced i/o and Arithmetic Compression classlib
Besides i/o and compression code, this package provides vocabularies, (poly/homo)morphic dictionaries with a dynamic "inheritance" path. These vocabularies give one implementation of a run-time variable lookup. The package is capable of greater things: a hierarchical lookup of arguments using defaults of different scope and generality.

Database as-a (OO)P language
Variable lookup as an instance of a database query over function's environment
 

From other archives
 
comp.lang.dylan, comp.lang.clos, comp.lang.scheme, comp.functional newsgroups
an article Implementing keyword and default arguments, function's resource database posted on Tue, 27 Oct 1998 20:55:50 GMT

 

Why C++ is not very fit for GUI programming

  With no intent of starting a holy war, this paper lists several annoying C++ snags seem inherent in GUI C++ programming. I encountered these problems while wrapping XVT's platform-independent graphical toolkit in a C++ class library. It appears that the pitfalls and workaround kludges are fairly common, to many event- and callback-based systems.
 
References
 

Paper and the presentation
at MacHack'95, The Tenth Annual Technical Conference for Leading Edge Developers, Southfield, MI, June 22-24, 1995.

MacHack'95 brochure: Proc. MacHack'95, Expotech Inc., Grosse Pointe Park, MI, 1995, p.68-70.

 

C++ compiler as an expressive type inference engine

 

This article will show that any standard C++ compiler can deal with algebraic data types, perform term comprehension, and do type arithmetic. C++ compiler acts as a term-rewriting engine -- an interpreter of an untyped lambda-calculus over type identifiers. It is the compiler that finds an attempt to divide by zero and aborts the compilation -- before an executable is built, let alone run. We rely extensively on a partial template instantiations. It is a standard C++ feature that offers term comprehension and resolution of polymorphic types. The code in this article compiled with egcs-2.91.66 and g++ 2.95.2 compilers, on FreeBSD and Linux.

This term re-writing engine is somewhat similar to expression templates. There are however important differences. Expression templates deal with terms that represent C++ expressions, e.g., a=b+2*c where a, b and c are matrices. An expression template will rewrite this into a (sequence) of other expressions to explicitly iterate over all elements of matrices a, b, and c. Expression templates therefore manipulate variables whose type -- Matrix in the case above -- is already known.The term-rewriting engine in this article deals with types and type identifiers. The engine re-writes type constructors rather than program variables. The result of the engine is an inferred type of an expression.

Of course term-rewriting is not unique to C++. Some may argue that other languages like Prolog, ML, or Erlang are more suitable to this task. One has to keep in mind however that it is a C++ compiler that does term-rewriting, of type expressions. Prolog and Scheme are (dynamically-typed) languages with latent types; they do not apply in the present context of static type inference. ML and Haskell do sophisticated type inference; yet their type systems are decidable. The ultimately static typing illustrated in this article requires a more expressive type system. Beside C++, Cayenne and other languages with dependent types can accomplish this task. Yet among major contemporary programming languages only C++ appears to be able to implement this ultimately static type system, and perform a very general term rewriting of types at compile-time.
 

Version
 The current version is 2.5, Aug 26, 2000.
References
 

A self-contained source code [.cc, 10K]
which contains inference rules of the type-rewriting system, and shows how they work.

Type Arithmetics: Computation based on the theory of types
The article itself.

Functional Style in C++: Closures, Late Binding, and Lambda Abstractions
 

 

scheming with the C preprocessor: a computable #include

This is the extended abstract of an article submitted to the Dr. Dobb's Journal
The problem:
How to get the C preprocessor to #include different .h files depending on a user-#defined symbol, whose all possible values are generally unknown at the time the code is written.
In other words, how to get the preprocessor to substitute Foo for Bar inside
       #include "Foo.h"
Note, the preprocessor does not normally substitute #defined symbols inside C strings (let alone parts of C strings, let alone #include strings)
Solutions:
In the extended abstract


 

Chess tournament scheduling: tough but possible

...as shown in the article Scheduling Algorithms and NP-Complete Problems, Dr. Dobb's Journal, #262, February 1997, pp.107-109.

tournament-sched.c is the complete code mentioned in the article. This code -- running on a lowly PDP-11 clone -- had actually scheduled several tournaments, in real time.

Phil Troy has kindly pointed out that the scheduling problem is actually that of minimum-weight perfect matching in a general graph, for which efficient exact solutions are known. These solutions are the variations and improvements of Edmond's maximum-weight matching (aka blossom) algorithm. A good description can be found in Computing Minimum-Weight Perfect Matchings by William Cook, Andre' Rohe in INFORMS Journal on Computing, as well as in many books on combinatorial optimization.


 

Advanced Finite Automaton as a simple HTML formatter

  This is a simple self-contained C code for a primitive lynx-like formatting of HTML documents. The notable feature of the code is an extensive use of a Finite State Machine with byte-compiled actions and an option to call a new state instead of just move to it, with an opportunity to return to the caller-state. The code is commented, even excessively so at the beginning.
Version
 The current version is 1.1, May 1995.
References
 

The README file [plain text file]

Complete source code [.shar.gz, 7K]

Advanced Finite Automaton as a simple HTML formatter [Crazy Example]
An article posted on the newsgroups comp.lang.c, comp.lang.c.moderated, comp.infosystems.www.misc on Tue May 9 09:25:21 CDT 1995.

 

Programming in a Finite Automaton style

  An illustration that such an abstract thing as a Finite State Machine can actually be used for mundane programming tasks.

This C code is a simple filter that prints out words from the input stream one by one, ignoring C-style comments. This sounds immensely trivial, until you actually try to write the code. Keep in mind that it should be able to handle empty lines, leading and trailing spaces, and such catches as

    e*/**// /* aaa
      /*   ****a/ //// *
    /   */  */
If you wrote the code in a traditional style, you may want to compare it with the FSM one below.
Version
 The current version is 1.2, Oct 25, 2002.
References
 

Complete source code archive off this site [.c, 3K]

 
Transparent incorporation of MacOS data structures into C++

 
Keywords: Pascal strings, Rectangle, C++, class library
 
Date: Tue May 31 09:30:42 CDT 1994
 
Newsgroups: comp.sys.mac.programmer
Magical conversion from a (char *) to a Pascal string in C++. Plus a few other tricks how to encapsulate some QuickDraw data structures into classes and get native QuickDraw functions to take the embellished objects as their own (that's the magic)

 
Opaque bases/variables in a class: kludges, suggestions, and dreams

 
Summary: Emulating opaque private variables / base classes
 
Keywords: opaque class variables, opaque base classes, kludges/emulation
 
Date: Tue Jun 14 11:00:22 CDT 1994
 
Newsgroups: comp.lang.c++

 
Pointers to class methods: taking, storing, using [Hack]

 
Summary: Non-prescribed but more traditional use of method pointers
 
Keywords: class method pointers, function pointers, call dispatching
 
Date: Tue Aug 9 10:43:35 CDT 1994
 
Newsgroups: comp.lang.c++

 
Cool way of iterating in a local context; nested functions in C++

 
Summary: foreach() iterators that use an action function in its local context
 
Keywords: nested functions, local environments, local classes, iterators
 
Date: Tue Dec 6 08:49:28 CST 1994
 
Newsgroups: comp.lang.c++
In a nutshell, this post is about one method of writing very general foreach()-type iterators that call an iteratee function within its own (and local) environment, without casting to (void *) and fro, without causing name conflicts, and without exposing private parts.

Local procedures and natural iterators in C++ [absurd example]

 
Summary: Snippet from grayimage_classlib showing off "nested" C++ functions (and lots of them)
 
Keywords: nested functions, iterators, closures, C++, offscreen image
 
Date: Thu Sep 7 10:27:59 CDT 1995
 
Newsgroups: comp.sys.mac.programmer.tools, comp.sys.mac.programmer.misc
A complete code snippet with bizarre nesting of C++ function several levels deep. There is something LISP-ish in this C++ code.

 
Virtual circling around in clouds (w/ C++ source)

 
Summary: announcement of upload of a simple VR appl with C++ source
 
Keywords: voxel 3D rendering, visualization, animation, elevation map, panning
 
Date: Fri Dec 8 09:44:19 CST 1995
 
Newsgroups: rec.games.programmer, comp.lang.c++, comp.sys.mac.programmer.games
The old (Jul 20, 1994) article "Simple virtual reality thing - flight thru clouds (w/ C++ source)" describing the previous version of the flight is still relevant.

 
C++ is good for writing OS kernels. Here's an example.

 
Summary: Announcement of the toy_OS written in full C++
 
Keywords: OS kernel, systems programming, threads, multiprocessing
 
Date: Tue Sep 13 09:43:22 CDT 1994
 
Newsgroups: comp.lang.c++



Last updated January 1, 2007

This site's top page is http://okmij.org/ftp/

oleg-at-pobox.com or oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!