PROGRAMMING LANGUAGE
DESIGN CONCEPTS
PROGRAMMING LANGUAGE
DESIGN CONCEPTS
David A. Watt, University of Glasgow
with contributions by
William Findlay, University of Glasgow
John Wiley & Sons, Ltd
Copyright O 2034
John Wiley & Sons Ltd, The Attium, Southern Gate, Chichester.
West Sussex PO19 SSQ, England
Telephone (+44) 1243 779777
Email (for orders andcustomer service enquiries): cs~books@wiley.co.uk
Visit our Home Page on wu?u.wileyeurope.com orwu?u.wiley.com
All Rights Reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in
any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except under
the terms of the Copyright, Designs and Patents Act 1988 or under the t e r m of a licence issued by the Copyright
Licensing Agency Ltd, 90Tottenham Court Road, London WlT4LP, UK, without the permission in writing of the
Publisher, with the exception of any material suppliedspecifically for the purposeof being entered and executed
on a computer system for exclusive use by the purchase of the publication. Requests to the Publisher should be
addressed to the Permissions Department, John Wiley & Sons Ltd, The Atrium Southern Gate, Chichester, West
Sussex PO19 SSQ, England, or emailed to permreq@wiley.co.uk, or faxed to (+44) 1243 770620.
This publication is designed to provide accurate and authoritative information in regard to thesubject matter
covered. It is sold on the understanding that the Publisher is not engaged in rendering professional services. If
professional advice or other expert assistance is required, theservices of a competent professional should be sought.
ADA is a registered trademark of the US Government Ada Joint ProgramOffice.
JAVA is a registered trademark of Sun Microsystems Inc.
OCCAM is a registered trademark of the NMOS Group of Companies.
m x is a registered trademark of AT&T Bell Laboratoties.
Other Wiley Editorial Ofices
John Wiley & Sons Inc, 111 River Street, Hoboken, NJ 07030, USA
Jossey~Bass, 989 Market Street, San Francisco, CA 941031741, USA
Wiley~VCH Verlag GmbH, Boschstr. 12, D~69469 Weinheim Germany
John Wiley & Sons Australia Ltd, 33 Park Road, Milton, Queensland 4064, Australia
John Wiley & Sons (Asia) Pte Ltd, 2 Clementi Loop #02~01, Jin Xing Distripark, Singapore 129809
John Wiley & Sons Canada Ltd, 22 Worcester Road, Etobicoke, Ontatio, Canada M9W 1L1
Wiley also publishes its books in a variety of electronic formats. Somecontent that appears
in print may not be available in electronic books.
Librnry of Congress Cataloging-in-Publication Data
Watt, David A . (David Anthony)
Programming language design concepts I David A . Watt; with
contributions by WilliamFindlay.
p. cm.
Includes bibliographical references and index.
ISBN 0~47045320~4
l.Programminglanguages(Electroniccomputers)I.Findlay, William,
1947 I 1 Title.
(pbk. : alk. paper)
BritishLibrnry Cat?loguing in Publication Dat?
Acatalogue record for this book is available from the Btitish Library
ISBN 0~470~85320~4
Typeset in 10112pt TimesTen by Laserwords Private Limited, Chennai, India
Printed and bound in Great Britain bv Biddles Ltd. Kine's Lvnn
This book is printed on acid~free paper responsibly manufactured from sustainable forestry
in which at least huo trees are plantedfor each one usedfor paper production.
, " ,
To Carol
Con tents
Preface
Part I: Introduction
1 Programming languages
1.1
Programming linguistics
1.1.1 Concepts and paradigms
1.1.2
1.1.3 Language processors
Syntax, semantics, and pragmatics
1.2 Historical development
Summary
Further reading
Exercises
Part 11: Basic Concepts
2 Values and types
2.1 Types
2.2
Primitive types
2.2.1 Built-in primitive types
2.2.2 Defined primitive types
2.2.3 Discrete primitive types
2.3 Composite types
2.3.1 Cartesian products, structures, and records
2.3.2 Mappings, arrays, and functions
2.3.3 Disjoint unions, discriminated records, and objects
2.4 Recursive types
2.4.1 Lists
2.4.2 Strings
2.4.3 Recursive types in general
2.5 Type systems
2.5.1 Static vs dynamic typing
2.5.2 Type equivalence
2.5.3 The Type Completeness Principle
2.6 Expressions
2.6.1 Literals
2.6.2 Constructions
2.6.3
Function calls
2.6.4 Conditional expressions
2.6.5
2.6.6 Constant and variable accesses
Iterative expressions