A++ The Smallest Programming Language in the World E-Book

Georg P. Loczewski

• Herausgeber: tredition
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch
• Veröffentlichungsjahr: 2018

Seitenzahl: 186

Beschreibung

A++ has been developed in 2002 in the context of 'Programmierung pur' [Undiluted Programming] (ISBN 3-87820-108-7) with the purpose to serve as a learning instrument rather than as a programming language used to solve practical problems. A++ is supposed to be an efficient tool to become familiar with the core of programming and with programming patterns that can be applied in other languages needed to face the real world. This book does not only introduce A++ as a language, but also covers its implementation in Perl and C including an introduction to these languages using A++ itself. The book also contains an introduction to the Lambda-Calculus of Alonzo Church, which represents the theoretical foundation of A++.

Leseprobe

A++

The Smallest Programming Language in the World

Georg P. Loczewski

A++

The Smallest Programming Language in the World

An Educational Programming Language

Including an Introduction to the Lambda Calculus

IMPRESSUM

Copyright©2018GeorgP.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.Edition2005

S.Toeche-MittlerVerlag,Darmstadt

2nd.augmentedEdition2018

treditionGmbH,Hamburg

ISBN

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

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

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

SeealsoA++DiekleinsteProgrammiersprachederWelt[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.

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,2which 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

7.3.4 Initializing the A++ Interpreter part 4

7.3.5 Initializing the A++ Interpreter part 5

7.3.6 Initializing the A++ Interpreter part 6

7.3.7 Initializing the A++ Interpreter part 7

7.4 WWW Links

8 Extending A++

8.1 ARS++

8.2 ARSAPI

II A++ – The Implementation

1 General Introduction

2 ARS and Perl

2.1 Syntax of Perl

2.2 Syntax of ARS

2.2.1 Examples of syntax of abstraction

2.2.2 Examples of syntax of reference

2.2.3 Examples of syntax of synthesis

2.3 Basic Abstractions

2.3.1 The IF- Abstraction

2.3.2 The boolean values ‘true’ and ‘false’

2.3.3 Application of basic logical abstractions

2.3.4 Extended Logical Abstractions

2.3.5 Application of extended logical abstractions

2.4 Numeric Abstractions

2.5 Arithmetic Operations

2.6 Application of numeric abstractions

2.7 Collections of Data

2.7.1 Basic abstractions for pairs

2.7.2 Application of abstractions for pairs

2.8 Basic utility abstractions for lists

2.8.1 Checking for an empty list: ‘nullp’

2.8.2 Displaying the contents of a list: ‘ldisp’

2.8.3 Determining the length of a list: ‘length’

2.8.4 Removing an element from a list: ‘remove’

2.8.5 Retrieving the n-th element from a list: ‘nth’

2.9 Relational Abstractions

2.10 Examples for recursion

2.10.1 Calculating the faculty of a number

2.10.2 Calculating the sum of elements of a list

2.11 Higher Order Functions

2.11.1 Creating a new function by composition: ‘compose’

2.11.2 Changing the arity of a function:‘curry’

2.11.3 Converting all elements in a list: ‘map1’

2.11.4 Converting the ‘map1’ function: ‘mapc’

2.11.5 Selecting elements from a given list: ‘filter’

2.11.6 Iterating through all elements of a list: ‘for-each’

2.12 Set Operations

2.12.1 Checking for a member in a set: ‘memberp’

2.12.2 Adding an element to a set: ‘addelt’

2.12.3 Combining two sets: ‘union’

2.13 Associative lists

2.13.1 Native lists or arrays

2.13.2 Abstractions for associative lists

2.13.3 Application of associative lists

2.14 Object Oriented Programming in Perl

2.14.1 Object Oriented Programming as Introduced in ARS

2.14.2 Modules support object-oriented programming in Perl

2.15 Regular expressions

3 A++ Interpreter in Perl

3.1 Introduction

3.2 A++ Interpreter

3.2.1 Main Program: Command Line Mode

3.2.2 Main Program: WEB-Based Application

3.2.3 Expression Definition Module (EXP)

3.2.4 List Module (PAIR)

3.2.5 Value Module (VALUE)

3.2.6 Name Management Module (NAME)

3.2.7 Environment Module (ENV)

3.2.8 Parser Module (ARSP)

3.2.9 Expression Evaluation Module (EVAL)

4 ARS and C

4.1 Mechanisms for Abstraction

4.1.1 Give something a name

4.1.2 Abstract Data Types (ADT)

4.1.3 Defining Functions

4.2 Operations within functions

4.2.1 Basic operations

4.2.2 Definition of variables

4.2.3 Assignment of values

4.2.4 Defining functions

4.2.5 Invoking functions

4.2.6 Testing values

4.2.7 Repeating operations

4.2.8 Arithmetic operations

4.2.9 Relational operations

4.2.10 Boolean operations

4.2.11 Library functions

4.2.12 Testing the basic operations

4.3 Simple and complex expressions

4.3.1 Atom

4.3.2 Complex expression

4.4 Modularization

4.5 Variables and pointers

4.6 Structures in C

4.6.1 typedef

4.6.2 enum

4.6.3 struct

4.6.4 union

4.7 Special control operations: setjmp/longjmp

5 A++ Interpreter in C

5.1 Introduction

5.2 ADT’s used by the the interpreter

5.2.1 NAME

5.2.2 PRIM

5.2.3 SPEC

5.2.4 VTYPE

5.2.5 EXPTYPE

5.2.6 ABS

5.2.7 SYN

5.2.8 EXP

5.2.9 ELIST

5.2.10 NLIST

5.2.11 VLIST

5.2.12 ENV

5.2.13 LFUN

5.2.14 CLAM

5.2.15 ACL

5.2.16 THUNK

5.2.17 VALUE

5.3 Functions used by the interpreter

5.3.1 Constructors

5.3.2 Name management

5.3.3 Environments

5.3.4 Evaluation of expressions

5.3.5 User input interface

5.3.6 Reading of A++ code by the parser

5.3.7 Main program of the A++ Interpreter

5.4 Source code of the A++ Interpreter

5.4.1 Main ARS-Module Header File: Datatypes and Function-Prototypes

5.4.2 Main ARS-Module Implementation File: arsc.c

5.4.3 Environment Modul ENV: app env.c

5.4.4 A++-Interface for Primitive Functions: app_prim.c

5.4.5 Primitive Functions related to data type boolean: app_bool.c

5.4.6 Primitive Functions related to data type string: app_string.c

5.4.7 Primitive Functions related to data type char: app_char.c

5.4.8 Primitive Functions related to data type integer and double: app_number.c

5.4.9 A++/JSON-Interface: app_jso.c

5.4.10 ARS-Parser Module: arsparser.c

5.4.11 Primitive functions related to I/O ports: Modul: app_port.c

5.4.12 I/O Modul: app_read.c

5.4.13 I/O Modul: app_print.c

5.4.14 Generic Value Modul: app_val.c

5.4.15 Error Modul: app_error.c

5.4.16 Main Program

5.4.17 Script for building the interpreter

6 ARS based programming in C

6.1 The ‘clam’ as a key for ARS based programming in C

6.2 Datatypes

6.2.1 Datatype ‘NAME’

6.2.2 nameTable

6.2.3 Abstract Datatype ‘VALUE’

6.2.4 Datatype ‘INTV’

6.2.5 Datatype ‘SYMV’

6.2.6 Datatype ‘STRV’

6.2.7 Datatype ‘PAIRV’

6.2.8 Datatype ‘NLIST’

6.2.9 Datatype ‘VLIST’

6.2.10 Datatype ‘ENV’

6.2.11 Datatype ‘CLAM’

6.3 Mapping ARS to C

6.3.1 Abstraction

6.3.2 Reference

6.3.3 Synthesis

6.4 Simple example

6.5 Basic demo of ARSAPI for C

6.5.1 Main program

6.5.2 Testing object oriented programming in C

6.5.3 Testing functional programming

6.6 Advanced demo of ARSAPI for C: menu system ‘genfui’

6.6.1 Source code of ‘ARSAPI for C’ demos

6.6.2 Header files for the demo

6.6.3 Library for ARS based programming in C

6.6.4 Basic demo main program

Appendices

A Detailed Discussion of Addition and Multiplication

A.1 Addition of the numbers ‘two’ and ‘three’

A.2 Multiplication of the numbers ‘two’ and ‘three’

B The Lambda Calculus

B.1 Introduction

B.1.1 Origin

B.1.2 Definition

B.1.3 Literature

B.2 Syntax of Lambda Expressions

B.3 Basic Rules for Lambda Conversions

B.3.1 Notation used in Conversion Rules

B.3.2 Alpha Conversion

B.3.3 Beta Conversion

B.3.4 Eta Conversion

B.3.5 Rules of Associativity

B.3.6 Y-Combinator

C Testing the Y-Combinator in A++

C.1 A++ Source code of Y-Combinator test program

C.2 Running the Y-Combinator test program

C.3 Comments on the Y-Combinator test program

D Background of the Author

Part I

A++ – The Language

Chapter 1

Educational Programming Languages

1.1 Introduction

An educational programming language is a programming language that is designed primarily as a learning instrument and not so much as a tool for writing real world application programs.

In this sense A++, Pascal, Scheme and Logo may be considered to belong to this category of programming languages.

1.2 Pascal

Pascal has been traditionally used in many schools, colleges and universities in computer science classes to teach students the fundamentals of programming.

The great success of Pascal in the field of Computer Science Education results from its perfectly structured architecture forcing students to rigorously follow the rules of Structured Programming. In the 1980’s, the time period, in which spaghetti-code and ’GOTO-Statements’ were discovered to be the source of all evil in programming1Pascal was cheerfully received as a medicine against the poison that had infiltrated the programming practices of that time.

1.3 Scheme

More and more computer science teachers today prefer Scheme as the programming language of choice whenever students have to be introduced to the world of computer programming.

They argue that learning Pascal requires students to spend too much brainpower on the syntax of a language than on the essentials of programming .

They want to protect students from losing most of the fun in programming by getting too deeply involved in secondary things like the syntax and rules of a specific programming language.

They also believe that Pascal as a programming language is less expressive than Scheme , imposing on students too many limits thus demanding from them to spend much of their intellectual energy coping with the idiosyncracies of a language instead of letting them concentrate on the solution of a given problem.

The use of Scheme on the contrary will liberate students initially from lower level thinking that is influenced by the implementation of a programming language and will take them up to the heights of thinking in terms of higher levels of abstraction making programming simpler, more comprehensive and more powerful.

1.4 Logo

Logo is a language especially designed to introduce children to programming . A device called ’turtle’ is used to make programming for children very attractive. It is amazing how fast children learn to program the ’turtle’ to draw all kinds of pictures on the screen, starting with simple lines and later the fanciest pictures after having been familiarized with basic programming constructs.

Logo is not a ’dumb’ language however that can only be used to draw lines. It is very similiar to Scheme in its expressiveness and power and can there be used by experienced programmers as well to write complex application programs. Logo is especially suited for applications in the field of symbolic programming and artificial intelligence .

1.5 A++

A++ in particular is a programming language designed to provide a tool for basic training in programmingenforcing a rigorous confrontation with the essentials of programming . Programming in A++ students learn

•that programming problems can be solved using the powerful patterns derived from ARS (Abstraction, Reference and Synthesis)

•and that neither the knowledge of the syntax of a programming language

•nor the familiarity with all the primitive functions of a language implementation makes up the art of programming.

An interpreter is available in Scheme, Java, C, C++ and Python offering an ideal environment for basic training in programming, enforcing a rigorous confrontation with the fundamentals of programming languages.

In none of the programming languages used traditionally in introductory programming classes students are forced as rigorously as in A++ to come to a deep understanding of the essentials of programming.

This rigorous approach has the advantage, that students become thoroughly familiar with powerful programming patterns very fast, enabling them to learn and productively apply the popular programming languages of the real world in a very short time.

1This era began with Prof. Dijkstra’s famous article in the Communications of the ACM with the title ’A GOTO-Statement Considered Harmful’.

Chapter 2

Introduction to A++

2.1 Purpose of A++ and Origin

2.1.1 Purpose

A++ is a minimal programming language that has been built on the Lambda Calculus with the purpose to serve as a learning instrument rather than as a programming language used to solve practical problems.

A++ is introduced as a universal learning tool for programming, confronting students with the essence of programming and helping to master this confrontation.