E-Book Content
Advances in COMPUTERS VOLUME 15 Contributors to This Volume ALANW. BIERMANN DONALD BITZER DAVIDJ. KUCK LARRYH. REEKER JOHNR. RICE Advances in COMPUTERS EDITED BY MORRIS RUBINOFF Moore School of Electrical Engineering University of Pennsylvania and Pennsylvania Research Associates, Inc. Philadelphia, Pennsylvania AND MARSHALL C. YOVITS Department of Computer and Information Science Ohio State University Columbus, Ohio VOLUME 15 ACADEMIC PRESS rn New YO& rn Son Francisco rn Lgdon-1976 A Subsidiary of Hsrcourf Braace Jovanovich, Publishers COPYRIGHT 0 1976,BY ACADEMIC PRESS, INC. ALL RIQHTS RESERVED. NO PART O F THIS PUBLICATION MAY BE REPRODUCED OR TRANSMITTED IN A N Y FORM OR BY A N Y MEANS, ELECTRONIC OR MECHANICAL, INCLUDING PHOTOCOPY, RECORDING, OR A N Y INFORMATION STORAGE AND RETRIEVAL SYSTEM, WITHOUT PERMISSION IN WRITING FROM THE PUBLISHER. ACADEMIC PRESS, INC. 111 Fifth Avenue, New York, New York 10003 United Kingdom Edition published by ACADEMIC PRESS, INC. (LONDON) LTD. 24/28 Oval Road. London NWl L m w w OF CONGRESS CATALOG CARD NUMBER:59-15761 ISBN 0-12-012115-8 PRINTED IN THE UNITED STATES O F AMERICA Contents CONTRIBUTORS . PBEFACE . . i x . x i Approaches to Automatic Programming Alan W. Biermann 1 3 16 29 40 46 1. Introduction 2. Extensions to Traditional Automatic Programming Methods 3. Program Synthesis from Examples . 4. Synthesis from Formal Input-Output Specifications . 5. Translation of Natural Language Commands . 6. Heuristic Knowledge-Based Algorithm Synthesis 7. Comments . References . . 58 59 The Algorithm Selection Problem John R. Rice 1. Introduction 2. Abstract Models . 3. Concrete Application-The Selection of Quadrature Algorithms 4. Concrete Application-The Selection of Operating Syatem Schedulers . 5. Discussion of the Two Concrete Applications . 6. Approximation Theory Machinery . References . V . 65 67 77 82 90 91 117 CONTENTS vi Parallel Processing of Ordinary Programs David J. Kuck 1. Introduction 2. 3. 4. 5. . . . . . . . Theoretical Fundamentals Program Andysis . Machine Considerations Conclusions . References . 119 127 141 158 174 176 The Computational Study of language Acquisition Larry H. Reeker 1. 2. 3. 4. 5. The Problem. . Modeling Language Acquisition The Problem-SolVing Theory . Conclusion . Appendix : Grammar Representation References . . . . . . . . 181 191 196 223 224 235 The Wide World of ComputerBased Education Donald Bitzer 1. Introduction 2. The PLAT0 System . 3. System Configuration . 4. Teaching Strategies . 5. Computational Applications 6. A Word about TUTOR . 7. Evaluation . . . . . . . . . 239 243 254 256 266 269 272 CONTENTS 8. Cost of Services 9. Conclusion . References . . AUTHORINDEX SUBJECT INDEX CONTENTSOF Pmvrons VOLUMES . vii . . . 276 281 281 . . 285 289 297 . This Page Intentionally Left Blank Contributors to Volume 15 Numbers in parentheses indicate the pages on which the authors' contributions begin. Axm W. BIERMANN, Department of Computer Science, Duke University, Durham, North Carolina ( 1 ) DONALD BITZER, Computer-Based Education Research Laboratory, University of IUinoiS at Urbana-Champaign, Urhna, IUinois (939) DAVID J. KUCK,Department of Computer Science, University of Illinois at Urbana-champaign, Urbana, Illinois ( 119) LaRRy H. REEKER, Departm