A++ and the Lambda Calculus E-Book

Georg P. Loczewski

• Herausgeber: tredition
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 41

Veröffentlichungsjahr: 2018

Beschreibung

The book contains an introduction to the Lambda Calculus as the theoretical foundation of all 'Functional Programming' languages. The Lambda Calculus has been created by the American logician Alonzo Church in the 1930's and is documented in his works published in 1941 under the title 'The Calculi of Lambda Conversion'. Alonzo Church wanted to formulate a mathematical logical system and had no intent to create a programming language. The intrinsic relationship of his system to programming was discovered much later in a time in which programming of computers became an issue. The book 'A++ and the Lambda Calculus' also contains a brief introduction to the educational programming language A++, a minimal programming language that has been built with the Lambda Calculus as its foundation. The purpose of A++ is to serve as a learning instrument rather than as a programming language used to solve practical problems. A++ is supposed to be an excellent 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. A++ is presented in greater detail in the books: 'A++ The Smallest Programming Language in the World' (978-3-7469-3021-3) and in 'Programmieren lernen mit A++' (978-3-7469-3199-9).

Leseprobe

A++ and the Lambda Calculus

Georg P. Loczewski

A++ and the Lambda Calculus

Principles of Functional Programming

IMPRESSUM

Copyright ©2018 Georg P. Loczewski

A++ and the Lambda Calculus

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 2018

tredition GmbH, Hamburg

ISBN

978-3-7469-3811-0 (Paperback)

978-3-7469-3809-7 (Hardcover)

978-3-7469-3810-3 (e-Book)

See also A++ The Smallest Programming Language in the World[29]

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.

Contents

I The Lambda Calculus

1 Introduction

1.1 Origin

1.2 Definition

1.3 Literature

1.4 Syntax of Lambda Expressions

2 Basic Rules for Lambda Conversions

2.1 Notation used in Conversion Rules

2.1.1 Notation used to specify conversion of lambda expressions

2.1.2 Notation used to specify substitution

2.2 Alpha Conversion

2.2.1 Rules of Alpha Conversion

2.2.2 Beta Conversion

2.2.3 Rule of β-Conversion

2.2.4β-Reduction

2.2.5β-Abstraction

2.3 Eta Conversion

2.3.1η-Reduction

2.3.2η-Abstraction

2.4 Rules of Associativity

2.4.1 Rule of Associativity for Abstraction

2.4.2 Rule of Associativity for Application

2.4.3 Example for both rules:

2.5 Y-Combinator

2.5.1 Using the Y-Combinator to implement recursion

II A++

1 Introduction to A++

1.1 Purpose of A++ and Origin

1.1.1 Purpose

1.1.2 Origin

1.1.3 ARS — Generalization of the Lambda-Calculus

1.1.4 Name of the language

1.2 Motivations for the development of A++

1.2.1 To support an alternate method of teaching the principles of programming

1.2.2 To provide a learning tool for exploring the fundamentals of programming

1.2.3 To support a method teaching powerful programming patterns applicable to most languages

1.2.4 To open a new view of programming for many programmers:

1.3 Features of A++

1.3.1 Programming paradigms supported:

1.3.2 Constitutive Principles of A++

1.3.3 Closure

1.3.4 Basic abstractions derived from ARS

1.3.5 Development of Applications with A++

1.4 Internal Architecture of A++

1.4.1 Overview

1.4.2 Internal Structure Overview (commented version)

1.4.3 Syntax of ARS (A++)

1.4.4 Definition of A++ in the form of a Tree Diagram

1.4.5 Commenting the definition:

1.4.6 Examples of A++ - Syntax

2 General Programming Patterns and A++

2.1 Closure Pattern

2.2 CLAM Pattern

2.3 List Pattern

2.4 Dictionary Pattern

2.5 Set Pattern

2.6 Recursion Pattern

2.7 Higher Order Function Pattern

2.8 Message Passing Pattern

2.8.1 Classes of objects

2.8.2 Instance of a class

2.8.3 Constructors

2.8.4 Creating instances of a class

2.8.5 Sending messages

2.8.6 Executing methods

2.8.7 Essential features of object oriented programming

2.8.8 Relation between classes

2.9 Meta Object Protocol Pattern

Appendices

Bibliography

Part I

The Lambda Calculus

Chapter 1

Introduction

1.1 Origin

The Lambda Calculus has been created by the American logician Alonzo Church in the 1930’s and is documented in his works published in 1941 under the title ‘The Calculi of Lambda Conversion’.

Alonzo Church wanted to formulate a mathematical logical system and had no intent to create a programming language. The intrinsic relationship of his system to programming was discovered much later in a time in which programming of computers became an issue.

1.2 Definition

DEFINITION 1 (LAMBDA CALCULUS)

The Lambda Calculus defines the laws for the formulation and conversion of lambda expressions.

1.3 Literature

As a mathematical logical system the Lambda Calculus is covered in detail in [2] and less comprehensively but in a more readable form in [34]. A clear account of the historical origins and basic properties of the lambda calculus is presented by Curry and Fey in their book [12]. This view is taken from [21] page 23.

From the programmer’s point of view the Lambda Calculus is adressed in [21], [22], [3].

1.4 Syntax of Lambda Expressions

The syntax of lambda expressions is defined as follows:

The Lambda Calculus therefore includes three diffenrent types of lambda expressions:

•variables (referencing lambda expressions)

•lambda abstractions (defining functions)

•applications (invoking functions)

Remark:

The parentheses in the syntax of an application are not mandatory. This results from the law of associativity for applications introduced below.

Chapter 2

Basic Rules for Lambda Conversions

2.1 Notation used in Conversion Rules