image

A++

The Smallest Programming Language in the World

Georg P. Loczewski

Image

A++

The Smallest Programming Language in the World

An Educational Programming Language

Including an Introduction to the Lambda Calculus

Image

IMPRESSUM

Copyright © 2018 Georg P. Loczewski

The book was set by the author using the LATEX typesetting system and was printed and bound in the Federal Republic of Germany.

1st. Edition 2005

S.Toeche-Mittler Verlag, Darmstadt

2nd. augmented Edition 2018

tredition GmbH, Hamburg

ISBN

978-3-7469-3021-3 (Paperback)

978-3-7469-3022-0 (Hardcover)

978-3-7469-3023-7 (e-Book)

See also A++ Die kleinste Programmiersprache der Welt[28]

The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with the use of these programs.

All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher and the author.

The book was set by the author using the LATEX typesetting system and was printed and bound in the Federal Republic of Germany.

To my wife Ursula and my sons Thomas and Johannes dedicated in love.

Image

Preface

Origin of A++

A++ was developed in the year 2002 in the context of writing the book ‘Programmierung pur’ which has been published in April 2003 under the ISBN 3-87820-108-7.

The roots of A++ lie back many years however, when I discovered Scheme which was in 1995 or to be more precise a little bit after when I read the book ‘Scheme and the Art of Programming’ by George Springer and Daniel P. Friedmann [32]. It was not this book that inspired me to launch the ARS or A++ project a couple of years later, it were a few statements by Guy L. Steele Jr., one of the creators of the Scheme programming language, which he made in the foreword of that book.

Describing the origin of Scheme he gives homage to the Lambda Calculus, invented by Alonzo Church in the late 1930’s. He talks about the importance of the principle of abstraction and makes the following statement in this context on page XV:

Abstraction consists in treating something complex as if it were simpler, throwing away detail. In the extreme case, one treats the complex quantity as atomic, unanalyzed, primitive. The lambda calculus carries this to a pure, unadulterated extreme. It provides exactly three operations, plus a principle of startling generality.

The emphasis of the selected sentence in this quotation does not appear in the original text.

Following these words which have been quoted here, Guy L. Steele describes the three basic operations of the lambda calculus. He continues to describe the ingenuity of the lambda calculus coming up with another remarkable statement:

Abstraction is all there is to talk about: it is both the object and the means of discussion.

Guy L. Steele’s praise of the lambda calculus fascinated me, impressed me a lot and never let me loose.

There was one thing however, which bothered me: The definition of ‘abstraction’ as ‘give something a name’ and the operation of abstraction in the lambda calculus do not match, at least according to my understanding. The operation of abstraction in the lambda calculus does not include a ‘name giving’ feature. Lambda abstractions in the lambda calculus are ‘per se’ anonymous. They are assigned a name only indirectly if they are passed as arguments to another lambda abstraction in the synthesis operation.

I am grateful to Guy L. Steele for letting me discover the beauty of ARS, which he describes in the mentioned text, in which he also outlines the origin of Scheme. Scheme is a programming language which has inherited a lot of the beauty and power of the lambda calculus that Guy L. Steele is talking about.

Glenn L. Vanderburg has used the following words to describe Scheme in his advanced text book about Java [34] on page 593:

Scheme might be considered the queen of programming languages: It is small, pure, and beautiful.

Now there is another thing that bothered me though: it has to do with how Scheme is defined in the official document, the R5RS-Report [23]. The formal syntax definition starting on page 38 in that document does not show at all the three basic operations of the lambda calculus to be the root or the core of the scheme programming language.

The fascination of ARS, shared with Guy L. Steele, and the two things that bothered me led finally to the development of A++ and even ARS++. ARS++ extends A++ into Scheme and beyond without giving up ARS as root and core of the language, showing up ‘unadulterated’ in its definition1.

Scheme is small, A++ is even smaller. It was a challenge for me to see how far one could go just using ARS, without creating a programming language with all kinds of whistles and bells definitely tempting a student in the process of being initiated to programming to focus his or her attention on things that are not essential to programming at all.

To develop A++ and extending it to ARS++ and to define an interface to C, C++ and Java called ARSAPI, was a great adventure and learning experience for me,2 which I would like to share with many other people being engaged in teaching or studying the art of programming. This book covers the first part. All parts together are presented in ‘Programmierung pur’ (‘Undiluted Programming’).

Acknowledgements

My thanks go out to many people who through their excellent work made it possible and interesting for me to get involved with programming languages in general and Scheme, the Lambda Calculus and ARS specificallly. This includes Guy L. Steele and Gerald J. Sussman, Alonzo Church, Jacques Chazarain [3], Peter Norvig [29], Samuel N. Kamin [22], Brent Benson (‘libscheme’), Richard Stallman (‘gcc’), Hans J. Boehm (‘garbage collector’) and many others.

At this point it is also appropriate to express thanks to all those people who make their software products available to all who have a need for it, software products like Linux, all GNU-licensed programs, Java, all Scheme implementations, the excellent typesetting software LATEX with all the macro packages and again many others.

Without these people, i.e. without their books and their software, the idea to write a book on A++ and ARS++ would have never been born and the project would have never been realized.

My special thanks I want to express to my publisher Mr. Jens Toeche-Mittler, who supported the idea behind these books from the very beginning and to my family who put up with me thinking, programming and writing at times, when other tasks may have seemed and may have been more important.

Georg P. Loczewski Gross-Zimmern, September 2004

After 6 years of programming in perl following the publication of the first edition and the discovery of an exciting lambda language, JavaScript, I thought it was time to work a little bit on A++. Douglas Crockford convincingly shows in his book ’JavaScript – The Good Parts’ ([11]) that JavaScript is a beautifiul and powerful language despite a few ’bad parts’. Unfortunately it didn’t make in the competition with Java, back in history, because of political management decisions.

A good part of JavaScript is without any question JSON, the JavaScript Object Notation, becoming more popular now as a replacement of XML. The simplicity and expressiveness of JSON make it a good candidate as a generic vehicle for data interchange. I thought it might be interesting to merge the simplicity of A++ in respect to the internal architecture of programs with the simplicity of JSON in regard to the handling of data.

On the other hand it is always worthwhile to think about possibilities to improve something that is 5 years old. These are the reasons, A++ - The Smallest Programming Language in World, appears in its second edition.

Georg P. Loczewski Gross-Zimmern, July 2010

1The name ARS++ is derived form ARS + Scheme + Extensions. This means that the primitive operations of Scheme and some more have been made available to A++ in the form of predefined values and abstractions.

2-unfortunately a little bit late though after having been working in the field of programming for over 30 years-

Contents

Preface

I A++ – The Language

1 Educational Programming Languages

1.1 Introduction

1.2 Pascal

1.3 Scheme

1.4 Logo

1.5 A++

2 Introduction to A++

2.1 Purpose of A++ and Origin

2.1.1 Purpose
2.1.2 Origin
2.1.3 ARS — Generalization of the Lambda-Calculus
2.1.4 Name of the language

2.2 Motivations for the development of A++

2.2.1 To support an alternate method of teaching the principles of programming
2.2.2 To provide a learning tool for exploring the fundamentals of programming
2.2.3 To support a method teaching powerful programming patterns applicable to most languages
2.2.4 To open a new view of programming for many programmers:

2.3 Features of A++

2.3.1 Programming paradigms supported:
2.3.2 Constitutive Principles of A++
2.3.3 Closure
2.3.4 Basic abstractions derived from ARS
2.3.5 Development of Applications with A++

2.4 Internal Architecture of A++

2.4.1 Overview
2.4.2 Internal Structure Overview (commented version)
2.4.3 Syntax of ARS (A++)
2.4.4 Definition of A++ in the form of a Tree Diagram
2.4.5 Commenting the definition:
2.4.6 Examples of A++ - Syntax

3 Linking Logic with the Physical World

3.1 Introduction

3.2 Internal Structure of A++ Including Minimal Set of Primitives

3.2.1 Overview
3.2.2 Internal Structure Overview (commented version)
3.2.3 Syntax of A++ with Minimal Set of Primitives

3.3 Examples using pre-defined primitives of A++

3.3.1 Pre-defined primitive abstractions in A++
3.3.2 A++ including pre-defined primitives
3.3.3 A++ Overview

4 Program Simplicity plus Data Structure Simplicity

4.1 Introducing JSON

4.1.1 Practical data types or data constructs
4.1.2 Syntax of JSON

4.2 Integrating JSON into A++

4.2.1 Structure of A++ including JSON (Overview)
4.2.2 Structure of A++ including JSON (commented version)
4.2.3 Syntax of A++ merged with JSON Architecture

5 General Programming Patterns and A++

5.1 Closure Pattern

5.2 CLAM Pattern

5.3 List Pattern

5.4 Dictionary Pattern

5.5 Set Pattern

5.6 Recursion Pattern

5.7 Higher Order Function Pattern

5.8 Message Passing Pattern

5.8.1 Classes of objects
5.8.2 Instance of a class
5.8.3 Constructors
5.8.4 Creating instances of a class
5.8.5 Sending messages
5.8.6 Executing methods
5.8.7 Essential features of object oriented programming
5.8.8 Relation between classes

5.9 Meta Object Protocol Pattern

6 Discovering the Power of A++

6.1 Basic Abstractions

6.1.1 The IF- Abstraction
6.1.2 Extended Logical Abstractions
6.1.3 Application of extended logical abstractions

6.2 Numeric Abstractions

6.2.1 Natural Numbers
6.2.2 Arithmetic Operations
6.2.3 Application of numeric abstractions

6.3 Collections of Data

6.3.1 Basic abstractions for pairs
6.3.2 Basic utility abstractions for lists

6.4 Extended Numerical Abstractions

6.4.1 Abstraction ‘zeropair’
6.4.2 Decrementing a number: ‘pred’
6.4.3 Subtracting a number: ‘sub’

6.5 Relational Abstractions

6.5.1 Comparing two numbers: ‘equaln’
6.5.2 Comparing two numbers: ‘gtp’
6.5.3 Comparing two numbers: ‘ltp’
6.5.4 Comparing two numbers: ‘gep’

6.6 Examples for recursion

6.6.1 Calculating the faculty of a number
6.6.2 Calculating the sum of elements of a list
6.6.3 Insertion Sort

6.7 Higher Order Functions

6.7.1 Creating a new function by composition: ‘compose’
6.7.2 Changing the arity of a function:‘curry’
6.7.3 Converting all elements in a list: ‘map’
6.7.4 Converting the ‘map’ function: ‘mapc’
6.7.5 Selecting elements from a given list: ‘filter’
6.7.6 Searching for an element in a given list: ‘locate’
6.7.7 Iterating through all elements of a list: ‘for-each’

6.8 Set Operations

6.8.1 Checking for a member in a set: ‘memberp’
6.8.2 Adding an element to a set: ‘addelt’
6.8.3 Combining two sets: ‘union’

6.9 Associative Lists in A++

6.9.1 Abstractions for associative lists
6.9.2 Application of associative lists

6.10 Miscellaneous abstractions

6.10.1 Testing the basic abstractions

6.11 Object Oriented Programming in A++

6.11.1 First example of object oriented programming in A++
6.11.2 Second example of object oriented programming in A++
6.11.3 Third example of object oriented programming in A++

6.12 Imperative Programming in A++

7 Computer Resources for A++

7.1 Support Functions

7.1.1 Abstraction for displaying a number
7.1.2 Abstraction for displaying a boolean value
7.1.3 Abstraction for displaying lists

7.2 A++ Interpreters

7.2.1 A++ Interpreter written in Perl
7.2.2 A++ Interpreter written in C

7.3 Initializing the A++ Interpreter

7.3.1 Initializing the A++ Interpreter part 1
7.3.2 Initializing the A++ Interpreter part 2
7.3.3 Initializing the A++ Interpreter part 3