Mills - Theoretical Introduction to Programming.pdf

(1692 KB) Pobierz
654217911 UNPDF
Theoretical Introduction to Programming
654217911.001.png
Bruce Mills
Theoretical
Introduction to
Programming
With 29 Figures
654217911.002.png
Bruce Mills, BEng, BSc, PhD
British Library Cataloguing in Publication Data
A catalogue record for this book is available from the British Library
Library of Congress Control Number: 2005926335
ISBN-10: 1-84628-021-4
Printed on acid-free paper
ISBN-13: 978-1-84628-021-4
© Springer-Verlag London Limited 2006
Apart from any fair dealing for the purposes of research or private study, or criticism or review,
as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be
reproduced, stored or transmitted, in any form or by any means, with the prior permission in
writing of the publishers, or in the case of reprographic reproduction in accordance with the
terms of licences issued by the Copyright Licensing Agency. Enquiries concerning reproduction
outside those terms should be sent to the publishers.
The use of registered names, trademarks, etc. in this publication does not imply, even in the
absence of a specific statement, that such names are exempt from the relevant laws and regula-
tions and therefore free for general use.
The publisher makes no representation, express or implied, with regard to the accuracy of the
information contained in this book and cannot accept any legal responsibility or liability for any
errors or omissions that may be made.
Printed in the United States of America (SPI/SBA)
987654321
Business Media
springeronline.com
+
Springer Science
654217911.003.png
v
Preface
This book is organised into a large number of brief, self-contained entries.
Admittedly, there is no such thing as a self-contained entry . For exam-
ple, you need some knowledge of English to understand this paragraph.
But, the principle is that each entry, of one or two pages, is a conceptual
whole as well as a part of a greater whole (see note 20) in the same way
that a car has four whole wheels, and not eight half wheels.
Some entries are intended to demonstrate a technique, or introduce an
historically contingent fact such as the actual syntax of a contemporary
language, or in this case, a specific issue regarding this book. Others
are intended to illustrate a more eternal truth. They may be about a
contemporary language, but stress a philosophical position or broadly
based attitude. Both of these I have called notions . Finally, there are
entries that are intended to cause the reader to do something other than
just nodding their head as a sign of either agreement or an incipient
dormant state. These are the exercises.
The distinction can only be arbitrary; the classification is merely a guide
to suggest the sense in which the pages are intended.
In many cases, entries that are not specifically labelled as exercises in-
volve generic opportunities for self-study. As this is a book on computer
programming, it is natural and strongly advised that the reader try im-
plementing each concept of interest as it arises. With this in mind, I
have tried hard not to leave out pragmatic details whose omission would
leave the reader with nothing but the illusion of understanding. Nev-
ertheless, actually cutting practice code makes a big difference in the
ability of the programmer to use the concepts when the need arises.
At the end of the book are the notes explaining short and simple issues
or (paradoxically) issues that are too complex to explain in this book.
If a note became too lengthy while being written it was converted into
a notion or an exercise.
vii
Contents
Preface ..........................................................v
Chapter 1. The Abstract Rational Outlook ................ 1
Abstract Computation.........................................2
Rational Thought..............................................4
Human Psychology............................................6
Mythological Language........................................8
Literate Programming........................................10
Hand-Crafted Software.......................................12
Technical Programming.......................................14
Chapter 2. A Grab Bag of Computational Models .......17
Abstract and Virtual Machines...............................18
State Machines...............................................20
State Machines in Action.....................................22
Turing Machine .............................................. 26
Non-Deterministic Machines..................................30
Von Neumann Machine.......................................34
Stack Machine................................................36
Register Machine.............................................38
Analogue Machine............................................39
Cellular Automata............................................40
Unorthodox Models .......................................... 41
The Game of Life.............................................42
The Modern Desktop Computer..............................44
Aspects of Virtual Machines..................................46
Aspects of Programming......................................48
Register Indirection .......................................... 50
Pure Expression Substitution .................................52
Lists Pure and Linked........................................54
Pure String Substitution. .....................................56
The Face Value of Numerals..................................58
Solving Equations............................................62
Pure Unification..............................................64
Equality of Expressions.......................................66
Equational Reasoning ........................................ 68

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin