Semantics Structures in Computation

A Functional/Imperative Synthesis

By: P.B. Levy

Write A Review

Hardcover | 30 November 2003

At a Glance

Hardcover
398 Pages

Dimensions(cm)
24.13 x 16.51 x 2.54

Hardcover

$279.00

or 4 interest-free payments of $69.75 with

Ships in 5 to 7 business days

Call-by-push-value is a programming language paradigm that, surprisingly, breaks down the call-by-value and call-by-name paradigms into simple primitives. This monograph, written for graduate students and researchers, exposes the call-by-push-value structure underlying a remarkable range of semantics, including operational semantics, domains, possible worlds, continuations and games.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $89.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Computing & I.T.Computer Programming & Software Development Programming & Scripting Languages Computer Science Engineering & Technology Electronics & Communications Engineering Electronics Engineering Electronic Devices & Materials Databases Data Capture & Analysis Mathematics

Algebra Compilers & Interpreters

List of Figures	p. xvii
Preface	p. xxi
Acknowledgments	p. xxv
Introduction	p. xxvii
Computational Effects	p. xxviii
Reconciling CBN and CBV	p. xxix
The Problem Of Two Paradigms	p. xxix
A Single Language	p. xxix
"Hasn't This Been Done By ...?"	p. xxxi
The Case For Call-By-Push-Value	p. xxxii
Conventions	p. xxxii
Notation and Terminology	p. xxxii
Weakening	p. xxxiii
A CBPV Primer	p. xxxiii
Basic Features	p. xxxiii
Example Program	p. xxxiv
CBPV Makes Control Flow Explicit	p. xxxvi
Value Types and Computation Types	p. xxxvi
Structure of Thesis	p. xxxvii
Goals	p. xxxvii
Chapter Outline	p. xxxviii
Chapter Dependence	p. xl
Proofs	p. xl
Language
Call-By-Value and Call-By-Name	p. 3
Introduction	p. 3
The Main Point Of The Chapter	p. 3
A Simply Typed [lambda]-Calculus	p. 4
The Language	p. 4
Product Types	p. 4
Equations	p. 6
Reversible Derivations	p. 7
Adding Effects	p. 8
The Principles Of Call-By-Value and Call-By-Name	p. 8
Call-By-Value	p. 10
Operational Semantics	p. 10
Denotational Semantics for print	p. 11
Scott Semantics	p. 13
The Monad Approach	p. 14
Observational Equivalence	p. 17
Coarse-Grain CBV vs. Fine-Grain CBV	p. 17
Call-By-Name	p. 18
Operational Semantics	p. 18
Observational Equivalence	p. 18
CBN vs. Lazy	p. 20
Denotational Semantics for print	p. 21
Scott Semantics	p. 22
Algebras and Plain Maps	p. 23
Comparing CBV and CBN	p. 25
Call-By-Push-Value: a Subsuming Paradigm	p. 27
Introduction	p. 27
Aims Of Chapter	p. 27
CBV And CBN Lead To CBPV	p. 28
Syntax	p. 28
Operational Semantics Without Effects	p. 30
Big-Step Semantics	p. 30
CK-Machine	p. 32
CK-Machine For Non-Closed Computations	p. 33
Typing the CK-Machine	p. 33
Operations On Stacks	p. 36
Agreement Of Big-Step and CK-Machine Semantics	p. 37
Operational Semantics for print	p. 37
Big-Step Semantics for print	p. 37
CK-Machine For print	p. 38
Observational Equivalence	p. 39
Denotational Semantics	p. 39
Values and Computations	p. 39
Denotational Semantics Of Stacks	p. 41
Monads and Algebras	p. 41
Subsuming CBV and CBN	p. 42
From CBV to CBPV	p. 42
From CBN to CBPV	p. 43
CBPV As A Metalanguage	p. 45
Useful Syntactic Sugar	p. 45
Pattern-Matching	p. 45
Commands	p. 46
Computations Matter Most	p. 47
Complex Values and Equational Theory	p. 49
Introduction	p. 49
Complex Values	p. 50
Equations	p. 51
CK-Machine Illuminates to Equations	p. 52
Adding Complex Values is Computation-Unaffecting	p. 54
The Problem With the CBPV Equational Theory	p. 56
Complex Stacks	p. 57
Equational Theory For CBPV With Stacks	p. 58
Reversible Derivations	p. 60
Example Isomorphisms Of Types	p. 61
Trivialization	p. 61
Recursion and Infinitely Deep CBPV	p. 65
Introduction	p. 65
Divergence and Recursion	p. 66
Divergent and Recursive Terms	p. 66
Type Recursion	p. 68
Denotational Semantics Of Type Recursion	p. 69
Bilimit-Compact Categories	p. 69
Sub-Bilimit-Compact Categories	p. 72
Minimal Invariants	p. 73
Interpreting Recursive Types	p. 75
Infinitely Deep Terms	p. 77
Syntax	p. 77
Partial Terms and Scott Semantics	p. 78
Infinitely Deep Types	p. 79
Syntax	p. 79
Partial Types and Scott Semantics	p. 79
The Inductive/Coinductive Formulation of Infinitely Deep Syntax	p. 80
Relationship Between Recursion and Infinitely Deep Syntax	p. 82
Predomain Semantics For CBPV	p. 83
Domains and Predomains	p. 83
Interpreting Type Recursion In Predomains and Domains	p. 84
Concrete Semantics
Simple Models of CBPV	p. 89
Introduction	p. 89
Semantics of Values	p. 90
Global Store	p. 91
The Language	p. 91
Denotational Semantics	p. 92
Combining Global Store With Other Effects	p. 94
Control Effects	p. 95
letstk and changestk	p. 95
Typing Control Effects	p. 96
Regarding nil As A Free Identifier	p. 98
Observational Equivalence	p. 100
Denotational Semantics	p. 101
Combining Control Effects With Other Effects	p. 105
Erratic Choice	p. 107
The Language	p. 107
Denotational Semantics	p. 107
Finite Choice	p. 109
New Model For May Testing	p. 109
Errors	p. 111
The Language	p. 111
Denotational Semantics	p. 113
Summary	p. 114
Possible World Model for Cell Generation	p. 117
Cell Generation	p. 117
The Language	p. 118
Operational Semantics	p. 119
Worlds	p. 119
Stores	p. 120
Operational Rules	p. 121
Observational Equivalence	p. 122
Cell Types As Atomic Types	p. 122
Excluding Thunk Storage	p. 123
Introduction	p. 124
What Is A Possible World Semantics?	p. 124
Contribution Of Chapter	p. 125
Stores	p. 125
Possible Worlds Via CBPV Decomposition	p. 126
Denotational Semantics	p. 127
Semantics of Values	p. 127
Semantics of Computations	p. 128
A Computation Type Denotes A Contravariant Functor	p. 128
Semantics of Stacks	p. 129
Summary	p. 130
Combining Cell Generation With Other Effects	p. 131
Introduction	p. 131
Cell Generation + Printing	p. 132
Cell Generation + Divergence	p. 133
Related Models and Parametricity	p. 135
Modelling Thunk Storage And Infinitely Deep Types	p. 137
Jump-With-Argument	p. 141
Introduction	p. 141
The Language	p. 142
Jumping	p. 143
Intuitive Reading of Jump-With-Argument	p. 143
Graphical Syntax For JWA	p. 144
Execution	p. 145
The StkPS Transform	p. 148
StkPS Transform As Jumping Implementation	p. 148
Related Transforms	p. 149
C-Machine	p. 151
C-Machine for Effect-Free JWA	p. 151
Adapting the C-Machine for print	p. 153
Relating Operational Semantics	p. 154
Observational Equivalence	p. 155
Equations	p. 155
Equational Theory	p. 155
Example Isomorphisms	p. 156
JWA As A Type Theory For Classical Logic	p. 157
The StkPS Transform Is An Equivalence	p. 160
The Main Result	p. 160
Complex Values	p. 161
Equational Theory For CBPV+Control	p. 162
Representing CBPV+Stacks In CBPV+Control	p. 163
Stacks and Complex Values Are Computation-Unaffecting	p. 164
The StkPS Transform Between Equational Theories	p. 166
Pointer Games	p. 169
Introduction	p. 169
Pointer Games And Their Problems	p. 169
Contribution Of This Chapter	p. 170
More Is Simpler	p. 171
Cells As Objects	p. 171
Related Work On Abstract Machines	p. 173
Structure Of Chapter	p. 174
Arenas In The Literature	p. 174
Player/Opponent Labelling	p. 174
Tokens Of An Arena	p. 174
Arenas Versus Arena Families	p. 175
Forests Versus Graphs	p. 176
Pointer Game Semantics For Infinitary JWA + Storage	p. 176
Types	p. 176
Terms	p. 180
[eta]-Expansion And Copycat Behaviour	p. 188
Semantics Of Terms	p. 189
Categorical Structure	p. 190
Cell Generation	p. 192
Claims	p. 193
Pointer Game For Infinitary CBPV + Control + Storage	p. 194
Pointer Game Via StkPS	p. 194
Introducing Questions and Answers	p. 195
Answer-Move Pointing To Answer-Move	p. 197
Removing Control	p. 198
Categorical Semantics
Semantics in Element Style	p. 207
Countable vs. Finite	p. 207
Introduction	p. 207
Categorical Preliminaries	p. 208
Modules	p. 208
Homset Functors	p. 209
Some Notation	p. 210
Locally Indexed Categories	p. 210
OpGrothendieck Construction And Homset Functors	p. 213
Locally Indexed Modules	p. 215
Locally Indexed Natural Transformations	p. 216
Modelling Effect-Free Languages	p. 216
Cartesian Categories and Substitution Lemma	p. 216
Products, Exponentials and Distributive Coproducts	p. 217
Categorical Structures For Judgements Of JWA And CBPV	p. 220
Introduction	p. 220
Judgement Model of JWA	p. 220
Stacks In CBPV	p. 221
Computations In CBPV	p. 222
Enrichment	p. 223
Connectives	p. 225
Right Adjunctives--Interpreting U	p. 225
Jumpwiths--Interpreting [not sign]	p. 226
Left Adjunctives--Interpreting F	p. 226
Products--Interpreting [Pi]	p. 227
Exponentials--Interpreting to	p. 229
Distributive Coproducts--Interpreting [Sigma]	p. 231
Tying It All Together	p. 234
Adjunctions	p. 235
Examples	p. 236
Trivial Models Of CBPV	p. 236
Eilenberg-Moore Models Of CBPV	p. 236
Between JWA and CBPV	p. 237
Erratic Choice	p. 239
Global Store	p. 240
Possible Worlds: Part 1	p. 241
Families	p. 243
Composite Connectives	p. 243
Families Construction For JWA	p. 246
Families Construction For CBPV	p. 247
All Models are Categorical Models	p. 249
Introduction	p. 249
All Models Of x-Calculus Are Cartesian Categories	p. 249
The Theorem, Vaguely Stated	p. 249
Fixing The Object Structure	p. 250
What Is A Model Of x-Calculus?	p. 251
The Theorem, Precisely Stated	p. 253
All Models Of CBPV Are CBPV Adjunction Models	p. 254
All Models Of JWA Are JWA Module Models	p. 259
Enrichment	p. 260
Representing Objects	p. 261
Introduction	p. 261
Categorical Structures	p. 262
Joint vs. Separate Naturality	p. 262
Context Extension Functors	p. 263
Representable Functors	p. 264
Ordinary Category	p. 264
Locally Indexed Category	p. 266
Cartesian Category	p. 267
Category With Right Modules	p. 269
Cartesian Category With Left Modules	p. 271
Parametrized Representability	p. 273
Possible Worlds: Part 2	p. 277
Adjunctions and Monads	p. 278
Definitions of Adjunction	p. 278
Terminality of Eilenberg-Moore	p. 283
Kleisli and Co-Kleisli Adjunctions	p. 284
CBV Is Kleisli, CBN Is Co-Kleisli	p. 287
Conclusions
Conclusions, Comparisons and Further Work	p. 293
Summary of Achievements and Drawbacks	p. 293
Simplifying Algebra Semantics	p. 294
Advantages Of CBPV Over Monad And Linear Logic Decompositions	p. 294
Beyond Simple Types	p. 296
Dependent Types	p. 296
Polymorphism	p. 297
Further Work	p. 297
Appendices	p. 298
Technical Treatment of CBV and CBN	p. 299
The Jumbo [lambda]-Calculus	p. 300
Introduction	p. 300
Tuple Types	p. 300
Function Types	p. 301
Languages and Translations	p. 302
Call-By-Value	p. 304
Coarse-Grain Call-By-Value	p. 304
Fine-Grain Call-By-Value	p. 305
From CG-CBV To FG-CBV	p. 308
Call-By-Name	p. 311
The Lazy Paradigm	p. 312
Subsuming FG-CBV and CBN	p. 314
From FG-CBV to CBPV	p. 314
From CBPV Back To FG-CBV	p. 314
From CBN to CBPV	p. 319
From CBPV Back To CBN	p. 320
Models In The Style Of Power-Robinson	p. 327
Introduction	p. 328
Actions of Monoidal Categories	p. 328
Freyd Categories	p. 329
Judgement Model	p. 330
Enrichment	p. 331
Connectives	p. 331
Modelling CBPV	p. 332
The Full Reflection	p. 333
Theories	p. 334
Conservativity	p. 336
References	p. 337
Index	p. 345
Table of Contents provided by Rittenhouse. All Rights Reserved.

Semantics Structures in Computation

A Functional/Imperative Synthesis

At a Glance

Hardcover

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Algebra

Algebra Workbook Grades 6-8

Algebra

Linear Algebra

Textbook of Algebra

Fundamentals of Algebra

Basic Math & Pre-Algebra For Dummies Book + Workbook Bundle

For Dummies Math & Science

The Maths Book

Big Ideas Simply Explained

Linear Algebra: A Modern Introduction

4th Edition

Simply Maths

DK Simply

Cartoon Guide to Calculus

Cartoon Guide Series

Essential Calculus

2nd Edition

Algebra II For Dummies

2nd edition

A Mind for Numbers

How to Excel at Math and Science (Even If You Flunked Algebra)

Elementary Linear Algebra

8th Edition - International Metric Edition

Linear Algebra and Its Applications

6th Global Edition

The Cartoon Guide to Algebra

Cartoon Guide Series

The Mending of Broken Bones

A Modern Guide to Classical Algebra

Mechanical Engineering for Makers

A Hands-On Guide to Designing and Making Physical Things

Algebra I For Dummies Book + Workbook Bundle

For Dummies

The Versatility of Integrability

In Memory of Igor Krichever

Blackjack Mathematics for Non-Mathematicians

Conjectures and Results on Modular Representations of $mathrm{GL}_n(K)$ for a $p$-Adic Field $K$

Memoirs of the American Mathematical Society

Blackjack Mathematics for Non-Mathematicians

Fundamentals of Quantum Computing

Solving Problems with Quantum Algorithms and Practical Qiskit Coding

Discrete Mathematics and Its Applications

Subvarieties of the Flag Variety

This product is categorised by