Probably Programming

After my last post on the A++ programming language, there was quite a bit of discussion on reddit about both a mistake I made about the classification of the language (which I corrected in my previous post), and questions about how A++ is different from Scheme.

Because of the relative simplicity of A++ compared to Scheme, rather than talk about how they compare and contrast (that would mostly be like, “Scheme does this, this, this, this, this, and this, whereas A++ does this”), I’m simply going to talk about the main aspects of A++, namely, its simplicity and the fact that it uses lazy evaluation.

The core of A++ is simplicity (and lambda-calculus)

The idea behind A++ is that it is lambda-calculus, with a simplified uniform syntax (using parens all the time, rather than only in certain cases), and with explicit name-binding added to it.

What this means is that everything is a function, with the exception of named constants, which enable a simple form of message-passing to be implemented. The only thing you can do with named constants is check if they are equal, so they add a very small amount of complexity to the language.

There are no data structures (that aren’t made up of nested lambdas), there are no primitive values, and no built-in operators, aside from those which allow the definition, binding, and applying of functions.

A tiny exception is made in instances when printing things out, but the only thing you can do a with a primitive is increment it, decrement it, or print it out, so it can’t be used in a program. Named constants also don’t count, since they essentially don’t have values. Ignoring these two trivial exceptions, there’s one main rule that A++ follows:

In A++, there are (pretty much) only functions.

The only (non-output-related) built-in operations are define, lambda, apply (which is done when the first thing inside some parenstheses isn’t “define”, “lambda”, or “equal”), and equal (which is used for comparing the aforementioned named constants).

To make A++ the powerful enough to write new language constructs within the language itself, it uses lazy evaluation.

Lazy evaluation

Parameter evaluation is done lazily, meaning an operation passed into a function is only applied (called) when you explicitly apply it (by wrapping it in a pair of parentheses).

This is needed in A++, because there are no built-in control structures. While loops aren’t strictly needed because A++ allows recursion, you do need some sort of conditional statement.

In A++, true, false, and if are defined as follows:

(define true   (lambda (x y) 
                 x))
 
(define false  (lambda (x y) 
                 y))
 
(define if (lambda (b t f) (b t f)))

Any predicate or boolean operation evaluates to either true or false, so when passed to if, it makes sense that only one of the two following parameters is evaluated.

If A++ used eager evaluation, both the t and f parameters would be evaluated before being passed into the if function, which, since A++ allows side-effects, could result in unwanted output. Even if A++ was purely functional, allowing no side-effects, it would waste time to evaluate both branches of the if function.

For example, if you were to run the following code:

(if true (ndisp! four) (ndisp! five))

you would get the expected output from A++ of

-->4

but if A++ eagerly-evaluated the parameters to if, you would end up with

-->4
-->5

instead (or possibly in the opposite order, depending on which evaluation order was used by the language).

Lisp offers deferred evaluation via the quote operator, and allows the construction of control structures with macros. Since the goal of A++ is simplicity, it makes sense that it would pick the lazy evaluation scheme, which allows it to fulfill both of those roles without any extra feature being added to the language.

Introduction to A++

Update: Apologies to anyone who’s sensibilities were offended by the claim that A++ is a “purely functional” language. This was a mistake on my part. While the only thing (with the exceptions mentioned below) you can really manipulate with A++ is functions, you could perhaps say that A++ is a “purely function-oriented” language, but since it does offer destructive assignment it is not “purely functional,” but more of a baby-Scheme.

I’m going to go ahead and claim temporary sleep-deprivation-induced insanity, and offer a correction below.

Despite having the same name with just one more plus, A++ is not related in any way to A+. A++ is a truly tiny, purely functional programming language language where (almost) everything is a function, whereas A+ is anything but tiny and is far from being purely functional represents almost everything as arrays.

A++, which is short for Abstraction + reference + synthesis, is an abstraction of the lambda calculus, with a syntax that is even simpler (and thankfully contains only symbols which are on a standard keyboard). This simplicity is due to the fact that it borrows its syntax from Lisp and Scheme, requiring parentheses to surround each expression.

The addition that A++ makes to lambda calculus is the ability to explicitly assign names to objects (functions or values), something which lambda calculus only supports through binding via function calls.

A++ is intended to be a “learning instrument for programming” and thus doesn’t try to add any extensions to the language which would make it too useful for everyday programming.

Due to its simplicity, it is a great language for getting to understand concepts which would normally be overshadowed by all the other stuff in a language.

A++ is a Lisp-1, with a single name space for both functions and data. Indeed, in A++ there is no operator to define a function, one simply defines a symbol to map to a lambda expression.

Since A++ uses lazy-evaluation, control structures such as if statements and while loops can be created with just lambdas, without having to add macros to the language.

There are some primitive functions built into the interpreter to allow for converting church numerals into regular numbers, and for displaying booleans and numbers. There is support for primitive integers, strings, and symbolic constants. However, the support for primitive integers is limited to the minimum needed for converting from a church-encoded integer to a primitive integer, so the primitive integer can be printed, and the support for strings is only in place to allow for loading of external files into the interpreter. This means that in the language, you have to work exclusively with church numerals, and the only really useful primitive (aside from lambdas and define) are the symbolic constants.

All the standard lisp stuff, like car, cdr, map, filter, boolean operators (true and false, once again, defined in church encoding), various predicates (like nullp and zerop), while, and for-each are all built in the A++ language itself, and loaded automatically from a file when the interpreter is started, rather than being built-in functions.

So, when I said this was a purely functional language everything in this language is constructed using functions, I wasn’t kidding. The only difference from what most people would consider a purely functional language, is the fact that you can re-define a new value to the same name. Of course, without the ability to do this, closures would be of limited usefulness.

My First A++ Program

I had a hard time coming up with an idea for a program to implement in A++. Mainly, anything more complex I wanted to do, I couldn’t because of the very limited interaction with the outside world allowed by the A++ interpreter.

I looked at the list of solutions by programming task at Rosetta Code, and decided to implement the Roman Numerals task.

I based my solution off the first C solution for roman numerals. Due to the lazy-evaluation provided by A++, I was able to translate the macros used almost exactly.

While A++ makes possible functional and object-oriented programming, this example is imperative in nature, since it is copied more or less exactly from a C implementation of the same algorithm.

(define roman 
    (lambda(n)
 
      (define iftrue      ; standard if function requires an "else" bit
          (lambda(b t)
            (if b t nil)))
 
      (define digit 
          (lambda(loop num c)
            (loop (gep n num) 
               (lambda()
                 (print c)
                 (define n (sub n num))))))
      (define digits
          (lambda(loop num c1 c2)
            (loop (gep n num)
               (lambda()
                 (print c1)
                 (print c2)
                 (define n (sub n num))))))
 
      (define hundred (mult ten ten))
 
      (digit  while   (mult ten hundred) 'M   )
      (digits iftrue (mult nine hundred) 'C 'M)
      (digit  iftrue (mult five hundred) 'D   )
      (digits iftrue (mult four hundred) 'C 'D)
      (digit  while              hundred 'C   )
      (digits iftrue     (mult nine ten) 'X 'C)
      (digit  iftrue     (mult five ten) 'L   )
      (digits iftrue     (mult four ten) 'X 'L)
      (digit  while                  ten 'X   )
      (digits iftrue                nine 'I 'X)
      (digit  iftrue                five 'V   )
      (digits iftrue                four 'I 'V)
      (digit  while                  one 'I   )))

You can download the A++ roman numeral program if you’d like.

Sadly, A++ offers no way to build up a string for printing or to print multiple items on a single line, so each of the numerals will be printed on its own line.

Also, I chose this particular implementation because A++ doesn’t provide a function to perform division!

continue on to learn more about A++

(more…)