Unimperative Programming Language - Teaser

The following is from my latest project which is a foray into functional programming. Any comments or suggestions?

The Unimperative Programming Language

by Christopher Diggins

Introduction

Unimperative is a simple programming language, which supports a mix of procedural programming and functional programming. In Unimperative the primary data type is a function. The sequence of evaluation in Unimperative matters somewhat, and function parameters are evaluated left to right.

Unimperative has a surprise twist, which I will save for the end

Comparing to Scheme

Unimperative is quite similar to Scheme. In Scheme we can write a factorial function as:

  (define factorial
    (lambda (n)
      (if (zero? n)
          1
          (* n (fact (- n 1))))))

In Unimperative we can write the equivalent function as:

  Function factorial =
    (IfZero, _1,
      1,
      (Mult, _1, (Self, (Dec, _1))));

Basic Usage

In many language we call functions by writing:

  MyFxn(x, y)

In the Unimperative programming language we instead write:

  (MyFxn, x, y)

The first element following an open paranthesis, and followed by a comma, is always treated as a function which will be evaluated. The elements which follow are passed as arguments to the function.

Other functions after the first one in a list are not evaluate:

  (MyFxn, OtherFxn)

This evaluates the function MyFxn and passes the OtherFxn as a parameter without evaluating it.

A function must be followed by at least one argument in order to be evaluated. The evaluation operator is the combination of paranthesis and comma:

  (xxx,

The following code does not evaluate MyFxn:

  (MyFxn)

If we wanted to evaluate MyFxn we would have to write:

  (MyFxn, nil)

Alternatively we could also write:

  (Eval, MyFxn)

Defining Functions

To define a function in Unimperative we do so as follows:

  Function MyFxn = (Add, _1, _2);

The _1 and _2 are place holders which refer to the first and second argument respectively.

An Interesting Twist

The Unimperative programming language has a surpise: it is completely legal C++, and doesn't use any macros! An Unimperative library will be available soon as part of the next OOTL ( Object Oriented Template Library ) release from http://www.ootl.org

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Looks interesting...

As a big user of boost::lambda, and FC++, this looks really interesting. Will you be publishing an article about this on "The C++ Source" when it's ready?

Thanks for the encouragement.

Thanks for the encouragement. I will probably be writing an article on the Unimperative language for CodeProject.com and for the C++ Users Journal (or Doctor Dobbs Journal).

Nice!

This does look interesting, as a kind of nicer "surface syntax" for functional programming in C++ a la FC++, boost::lambda, or boost::spirit::phoenix.

Here are some more code examples:

Thanks again for the encouragement. Good news, I got the prototype working tonight. Unfortunately the code is part of the OOTL, and I want to make sure everything in the OOTL is in top shape before I release it. For the time begin here are some of the Test Cases, I have been using for the library:

  void FpTest4() {
    Function f1 = (Add, 20, 1);
    Function f2 = (Add, (f1, nil), (f1, nil));
    Function f3 = (Output, (f2, nil));
    f3.Evaluate(empty);
  }

  void FpTest5() {
    Function f1 = (Add, 20, 1);
    Function f2 = (Add, (Eval, f1), (Eval, f1));
    Function f3 = (Output, (Eval, f2));
    f3.Evaluate(empty);
  }

  void FpTest9() {
    Function Factorial = (If, (Eq, _1, 0), 1, (Mult, _1, (Eval, self, (Dec, _1))));
    Function f = (Output, (Sub, (Factorial, 5), 78));
    f.Evaluate(empty);
  }

  void FpTest10() {
    Function f =
      (Procedure,
        (Add, 1, 2),
        (Add, 2, 3),
        (Output, 42),
       End);
    f.Evaluate(empty);
  }

  void FpTest11() {
    Function f = (If, true, (Output, 42), (Output, 14));
    f.Evaluate(empty);
  }

  void FpTest16() {
    Function f1 = (Mult, (Add, 3, 3), (Add, 2, (Add, 3, 2)));
    Function f2 = (Output, (Add, (Eval, f1), 0));
    f2.Evaluate(empty);
  }

  void FpTestRecurse2() {
    Function CountList;
    CountList =
      (If,
        (IsNil, (Car, _1)),
        0,
        (Add, 1, (Eval, self, (Cdr, _1)))
      );
    Function f1 = (CountList, (Cons, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
    Function f2 = (Output, (Add, (Eval, f1), 32));
    f2.Evaluate(empty);
  }

Let me play the devils advocate...

and ask the obvious question:

How is this of any usefulness to making robust applications?

Although what you did is impressive, the only thing it succeeds in doing is increase my admiration for C++.

But does it have any benefits in real life? in everyday projects?

Why should I write

Function MyFxn = (Add, _1, _2);

instead of

template  T add(T a, T b) {
    return a + b;
}
??? P.S: it's offtopic, but how come using interfaces in C++ is faster than virtual functions, as said in the BIL library documentation? and how is it more memory-efficient than using base abstract types? for every 4 bytes gained from not using vtables, another 4 bytes is lost for the interface reference types. If I have N objects that I want to call from an interface reference, I must have N interface references, too.

Some reasons why:

Hi Axilmar,

The MyFxn version can be used as a variable which can be used interchangeably with other Functions. The template add can not. MyFxn can also accept variable number of arguments, and it can return variable number of arguments.

A better comparison might be:

  boost::any add(boost::any a, boost::any b) {
    return any_cast&ltint>(a) + any_cast<int>(b);
  }

Which is quite similar to what Function does. In fact closer still would be:

  boost::any add(std::vector<boost::any> args) {
    return any_cast&ltint>(args.at(0)) + any_cast<int>(args.at(1));
  }

There you have the basis for Unimperative.

The more general question I think is why program functionally as opposed to imperatively. Certain algorithms are more easily expressed in terms of functional programming just as others are more easily expressed with imperative programming.

I would prefer to discuss BIL interfaces elsewhere (i.e. my blog, or a new forum topic) but here goes:

If I have N objects that I want to call from an interface reference, I must have N interface references, too.

That is not true. You might have N interface references, but that is not neccessary. Abstract base types require an extra pointer in every object. Whether or not you use them polymorphically. You only pay for references when you use them.

The MyFxn version can be used

The MyFxn version can be used as a variable which can be used interchangeably with other Functions. The template add can not. MyFxn can also accept variable number of arguments, and it can return variable number of arguments.

Thanks for the reply. We have talked in the Heron forums...I was one of the few (as I recall, the second one) guys that have posted in the sourceforge Heron forums, a few moons ago.

My question was not about the theoritical benefits of Unimperative(i.e. functional). I know about them; yes, carrying is one of them. Easier to write, well, maybe (if you can get your head around functional programming, that is).

My question was from a project point of view: is there any project that actually requires such a functionality?

For example, let's say that I may want to store a series of randomly chosen functions (yeap, extreme case, I know) in a list to call them later. Let's say I do it with a functional style, i.e. by using Unimperative or FC++ or boost::lambda. Wouldn't I need to store the function type alongside? So I would have to do something like:

switch (fn.function_type) {
    case ADD:
        x = fn(1, 2);

    case DIV:
        y = fn(1, 2, mod);

    etc
}

I could do it in an object-oriented style, but that would be like doing the work twice: my objects could be functors anyway, instead of Function placeholders.

So, what's the need? what's the necessity? is there any practical/actual need for this certainly very clever stuff? that's what I was asking.

That is not true. You might have N interface references, but that is not neccessary.

(link to your blog? -I am lazy, I know) Of course its true...if I want to have, let's say, 40 objects at the same time, I need 40 interface references. The only time that it might be beneficial to use interface references is when I use objects on the stack, just like in the examples...which is a trivial and non-interesting case, in my opinion. When objects are polymorphic, it is because I want them to be around for a long time, and therefore allocated on the heap. If I was to use objects in the stack only, I might as well do the algorithm as a template (so the interface constraint becomes implicit).

My point is again, that I don't find any real necessity for this.

Hi again Achilleas, Unimp

Hi again Achilleas,

Unimperative is entirely dynamically typed. It is quite different than FC++. In Unimperative you can pick an arbitrary function from a list as follows:

  
  Function FxnFromFxnList = (NthItem, _1, _2);
  Function FxnList = (MakeList, Add, Sub, Output)
  Function F1 = (Eval, (FxnFromFxnList, 0, FxnList), 7, 4 // evaluates to 11 (CD: my mistake sorry
  Function F2 = (Eval, (FxnFromFxnList, 1, FxnList), 7, 4 // evaluates to 3
  Function F3 = (Eval, (FxnFromFxnList, 2, FxnList), 7, 4 // evaluates to nil, but outputs 7 and then 4 to standard output

I am going to quell the interfaces discussion, sorry. I don't have the time nor energy to debate that particular topic.

With respect to the general q

With respect to the general question "Why is functional programming in C++ helpful," I would refer you to Smaragdakis and McNamara 2002, "FC++: Functional Tools for Object-Oriented Tasks:"

"In this paper, we show how FC++ can be used in common OO programming tasks. We demonstrate FC++ implementations of several common design patterns (Adapter, Builder, Command, and more). Compared to conventional C++ implementations of these patterns, our implementations are either simpler (in that fewer classes/dependencies are needed), more efficient, or more type-safe (thanks to parametric polymorphism and type-inference)."

But your question might be "why the syntax?" I obviously can't speak for cdiggins, but the value that I see to it is essentially uniformity and concision: I can create a named functor (in C++ terminology, that is, rather than ML terminology) without the syntactic overhead of declaring a class, defining operator() for it, etc. and can store that in a variable of the appropriate type, pass it as a parameter, return it as a value, etc. Obviously you can do the same thing without the syntactic support, but why, for the love of C++ verbosity? Functional programming in C++ is incredibly useful; the primary downside to it seems to be that it exhibits the worst aspects of C++'s tendency to illegibility. A little syntactic sugar helps the medicine go down.*

*"Syntactic sugar causes cancer of the semicolon." — Alan Perlis

Learning Functional C++ only

Would it be possible to learn and use C++ only utilizing the sort of functional aspects as talked about here. Including the ability to use existing libraries of various kinds and create libraries that could be used by others in a standard way.

If this is possible are there any suggestions on how to get started learning C++ in this light.

The only book I've seen that stresses the STL when teaching C++ is Accelerated C++ by Koenig and Moo. But it doesn't seem to stress these functional aspects. Then there is the turorials on the FC++ page and the documentation on ootl page. Any other suggestions.

What's the goal?

C++ isn't very good at entirely abstracting away from the underlying details of the language, i.e. you need to have a pretty good grasp of basic C++ to reliably be able to do the more sophisticated, high-level things. The high-level things usually depend on a mixture of features, like templates and operator overloading, while other issues like the memory allocation model can't usually be entirely ignored either, despite the ability to hide behavior inside smart pointers and so forth.

In support of my point, very few books teach you how to use e.g. STL or the more advanced template techniques (like Alexandrescu's) as a beginner, without requiring that you already have a good grasp of C++. I think that foundation is necessary.

So, my advice to someone wanting to learn C++ would be first to make sure you have good reasons for wanting to learn it — because some commitment will be required to do it properly — and then go about it the old-fashioned way: learn the basic language first, and then learn the higher-level stuff.