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