Note: Page numbers followed by f and t indicate figures and tables respectively.

A

abstract data type (ADT), 337, 366

abstract syntax, 356–359

programming exercises for, 364–365

representation in Python, 372–373

abstract-syntax tree, 115

for arguments lists, 401–403

for Camille, 359

parser generator with tree builder, 360–364

programming exercises for, 364–365

TreeNode, 359–360

abstraction, 104

binary search, 151–152

binary tree, 150–151

building blocks as, 174–175

programming exercises for, 152–153

activation record, 201

actual parameters, 131

ad hoc binding, 236–238

ad hoc polymorphism. See overloading;

operator/function

overloading

addcf function, 298

ADT. See abstract data type (ADT)

aggregate data types

arrays, 338

discriminated unions, 343

programming exercises for, 343–344

records, 338–340

undiscriminated unions, 341–343

agile methods, 25

all-or-nothing proposition, 613–614

alphabet, 34

ambiguity, 52

ambiguous grammar, 51

ancestor blocks, 190

antecedent, definition of, 651

ANTLR (ANother Tool for Language Recognition), 81

append, primitive nature of, 675–676

applicative-order evaluation, 493, 512

apply_environment_reference function, 462

arguments. See actual parameters Armstrong, Joe, 178

arrays, 338

assembler, 106

assignment statement, 457–458

conceptual and programming exercises for, 465–467

environment, 462–463

illustration of pass-by-value in Camille, 459–460

reference data type, 460–461

stack object, 463–465

use of nested lets to simulate sequential evaluation, 458–459

associativity, 50

of operators, 57–58

asynchronous callbacks, 620

atom?, list-of-atoms?, and list-of-numbers?, 153–154

atomic proposition, 642

attribute grammar, 66

automobile concepts, 7

B

backtracking, 651

Backus–Naur Form (BNF), 40–41

backward chaining, 659–660

balanced pairs of lexemes, 43

bash script, 404

β-reduction, 492–495

examples of, 495–499

biconditional, 644

binary search tree abstraction, 151–152

binary tree abstraction, 150–151

binary tree example, 667–672

binding and scope

deep, shallow, and ad hoc binding, 233–234

ad hoc binding, 236–238

conceptual exercises for, 239–240

deep binding, 234–235

programming exercises for, 240

shallow binding, 235–236

dynamic scoping, 200–202

vs. static scoping, 202–207

free or bound variables, 196–198

programming exercises for, 198–199

FUNARG problem, 213–214

addressing, 226–228

closures vs. scope, 224–225

conceptual exercises for, 228

downward, 214

programming exercises for, 228–233

upward, 215–224

upward and downward FUNARG problem in single function, 225–226

uses of closures, 225

introduction, 186–187

lexical addressing, 193–194

conceptual exercises for, 194–195

programming exercise for, 195

mixing lexically and

dynamically scoped

variables, 207–211

conceptual and programming exercises for, 211–213

preliminaries

closure, 186

static vis-à-vis dynamic properties, 186

static scoping

conceptual exercises for, 192–193

lexical scoping, 187–192

vs. dynamic scoping, 202–207

bindings times, 6–7

block-structured language, 188

Blub Paradox, 21

BNF. See Backus–Naur Form (BNF)

bootstrapping a language, 540

bottom-up parser, 75, 80–81

bottom-up parsing, 48

bottom-up programming, 15–16, 177, 716–717

bottom-up style of programming, 540

bound variables, 196–198. See also formal parameters

programming exercises for, 198–199

breakpoints, 560–562

built-in functions, in Haskell, 301–307

C

C language, 105–106

call chain, 200

call-with-current-continuation, 550–554

callbacks, 618–620

call/cc, defining, 622–625

call/cc vis-à-vis CPS, 617–618

Camille, 86–89

adding support for

recursion in, 440–441

for user-defined functions to, 423–426

assignment statement in, 457–458

implementing

pass-by-name/need in, 522–526

programming exercises for, 526–527

pass-by-value in, 459–460

properties of new versions of, 465t

sequential execution in, 527–532

programming exercise for, 533

Camille abstract-syntax tree for, 359

data type: TreeNode, 359–360

parser generator with tree builder, 360–364

programming exercises for, 364–365

Camille interpreter, 533–537

conceptual and programming exercises for, 537–539

implementing

pass-by-reference in, 485

programming exercise for, 490–492

reimplementation of

evaluate_operand

function, 487–490

revised implementation of

references, 486–487

candidate sentences, 34

capability to impart control, 701

category theory, 385

choices of representation, 367

Chomsky hierarchy, 41

class constraint, 257

clausal form, 651–653

resolution with propositions in, 657–660

CLIPS programming language, 14, 705

asserting facts and rules, 705–706

conditional facts in rules, 708

programming exercises for, 708–709

templates, 707

variables, 706–707

Clojure, 116

closed-world assumption, 701

closure, 186

non-recursive functions, 426–427

representation

in Python, 371–372

of recursive environment, 442

in Scheme, 367–371

uses of, 225

vs. scope, 224–225

CNF. See conjunctive normal form (CNF)

code indentation, 727

coercion, 249

combining function, 319

Common Lisp, 128

compilation, 106

low-level view of execution by, 110f

compile time, 6

compiler, 194

compiler translates, 104

advantages and disadvantages of, 115t

vs. interpreters, 114–115

complete function application, 286

complete graph, 680

complete recursive-descent parser, 76–79

compound propositions, 642

compound term, 645

concepts, relationship of, 714–715

concrete syntax, 356

representation, 74

concrete2abstract function, 358

conjunctive normal form (CNF), 646–648

cons cells, 135–136

conceptual exercise for, 141

list-box diagrams, 136–140

list representation, 136

consequent, definition of, 651

constant function, 130

constructor, 352

context-free languages and, 42–44

context-sensitive grammar, 64–67

conceptual exercises for, 67

continuation-passing style (CPS)

all-or-nothing proposition, 613–614

call/cc vis-à-vis CPS, 617–618

growing stack or growing continuation, 610–613

introduction, 608–610

trade-off between time and space complexity, 614–617

transformation, 620–622

conceptual exercises for, 625–626

defining call/cc in, 622–625

programming exercises for, 626–635

control abstraction, 585–586

applications of first-class continuations, 589

conceptual exercises for, 591–593

coroutines, 586–589

power of first-class continuations, 590

programming exercises for, 593–594

control and exception handling, 547

callbacks, 618–620

continuation-passing style

all-or-nothing proposition, 613–614

call/cc vis-à-vis CPS, 617–618

growing stack or growing continuation, 610–613

introduction, 608–610

trade-off between time and space complexity, 614–617

transformation, 620–635

control abstraction, 585–586

applications of first-class continuations, 589

conceptual exercises for, 591–593

coroutines, 586–589

power of first-class continuations, 590

programming exercises for, 593–594

first-class continuations

call/cc, 550–554

concept of continuation, 548–549

conceptual exercises for, 554–555

programming exercises for, 555–556

global transfer of control with

breakpoints, 560–562

conceptual exercises for, 564–565

first-class continuations in Ruby, 562–563

nonlocal exits, 556–560

other mechanisms for, 570–579

programming exercises for, 565–570

levels of exception handling in programming languages, 579

dynamically scoped exceptions, 582–583

first-class continuations, 583–584

function calls, 580–581

lexically scoped exceptions, 581

programming exercises for, 584–585

stack unwinding/crawling, 581–582

tail recursion

iterative control behavior, 596–598, 596f

programming exercises for, 606–608

recursive control behavior, 594–595

space complexity and lazy evaluation, 601–606

tail-call optimization, 598–600

coroutines, 586–589

CPS. See continuation-passing style (CPS)

curried form, 292–294

currying

all built-in functions in Haskell are, 301–307

conceptual exercises for, 310–311

curried form, 292–294

flexibility in, 297–301

form through first-class closures, 307–308

ML analogs, 308–310

partial function application, 285–292

programming exercises for, 311–313

and uncurry functions in Haskell, 295–297

and uncurrying, 294–295

D

dangling else problem, 58–60

data abstraction, 337–338

abstract syntax, 356–359

programming exercises for, 364–365

abstract-syntax tree for Camille, 359

Camille abstract-syntax tree data type: TreeNode, 359–360

Camille parser generator with tree builder, 360–364

programming exercises for, 364–365

aggregate data types

arrays, 338

discriminated unions, 343

programming exercises for, 343–344

records, 338–340

undiscriminated unions, 341–343

case study, 366–367

abstract-syntax representation in Python, 372–373

choices of representation, 367

closure representation in Python, 371–372

closure representation in Scheme, 367–371

programming exercises for, 373–382

conception and use of data structure, 366

inductive data types, 344–347

ML and Haskell

analysis, 385

applications, 383–385

comparison of, 383

summaries, 382–383

variant records, 347–348

in Haskell, 348–352

programming exercises for, 354–356

in Scheme, 352–354

decision trees, 710

declaration position, 193

declarative programming, 13–15

deduction theorem, 644

deep binding, 234–235

deferred callback, 620

defined language vis-à-vis defining language, 395

defined programming language, 115, 395

delay function, 504

denotation, 186

denotational construct, 37, 39

denoted value, 345

dereference function, 461, 522

difference lists technique, 144–146

discriminated unions, 343

docstrings, 728

domain-specific language, 15

dot notation, 136

downward FUNARG problem, 214

in single function, 225–226

DrRacket IDE, 352

Dyck language, 43

dynamic binding, 6–7

dynamic scoping, 200–202

advantages and disadvantages of, 203t

vs. static scoping, 202–207

dynamic semantics, 67

dynamic type system, 245

dynamically scoped exceptions, 582–583

E

eager evaluation, 493

EBNF. See Extended

Backus–Naur Form (EBNF)

embedded specific language, 15

empty string, 34

entailment, 643

environment, 366–382, 441–445, 462–463

environment frame. See activation record

Erlang, 178

evaluate-expression

function, 393

evaluate_expr function, 427–430, 445–446

evaluate_operand function, reimplementation of, 487–490

execute_stmt function, 532

expert system, 705

explicit conversion, 252

explicit/implicit typing, 268

expressed values vis-à-vis denoted values, 394–395

Extended Backus–Naur Form (EBNF), 45, 60–61

conceptual exercises for, 61–64

external representation, 356

F

fact, 656

factorial function, 610

fifth-generation languages. See logic programming;

declarative programming

finite-state automaton (FSA), 38–39, 73, 74f

two-dimensional array modeling, 75t

first Camille interpreter

abstract-syntax trees for arguments lists, 401–403

front end for, 396–399

how to run Camille program, 404–405

read-eval-print loop, 403–404

simple interpreter for, 399–401

first-class closures, supporting curried form through, 307–308

first-class continuations

applications of, 589

call/cc, 550–554

concept of continuation, 548–549

conceptual exercises for, 554–555

levels of exception handling in

programming languages, 583–584

power of, 590

programming exercises for, 555–556

in Ruby, 562–563

first-class entity, 11, 126

first-order predicate calculus, 14, 644–645

conjunctive normal form, 646–648

representing knowledge as predicates, 645–646

fixed-format languages, 72

fixed point, 505

fixed-point Y combinator, 714

folding function, 319

folding lists, 319–324

foldl vis-à-vis foldr, 323–324

in Haskell, 319–320

in ML, 320–323

foldl, use of, 606

foldl’, use of, 606

foldr, use of, 606

formal grammar, 40

formal languages, 34–35

formal parameters, 131

formalism gone awry, 660

Fortran, 22

forward chaining, 649, 657, 660

fourth-generation languages, 81

free-format languages, 72

free or bound variables, 196–198

programming exercises for, 198–199

free variables, 196–198

programming exercises for, 198–199

fromRational function, 257

front end, 73

for Camille, 396–399

source code, 394

FSA. See finite-state automaton (FSA)

full FUNARG programming language, 226

FUNARG problem, 213–214

addressing, 226–228

closures vs. scope, 224–225

conceptual exercises for, 228

downward, 214

in single function, 225–226

programming exercises for, 228–233

upward, 215–224

in single function, 225–226

uses of closures, 225

function annotations, 738

function calls, 580–581

function currying, 155

function hiding. See function overriding

function overloading, 738

function overriding, 267–268

functional composition, 315–316

functional mapping, 313–315

functional programming, 11–12

advanced techniques

eliminating expression recomputation, 167

more list functions, 166–167

programming exercises for, 170–174

repassing constant arguments across recursive calls, 167–170

binary search tree abstraction, 151–152

binary tree abstraction, 150–151

concurrency, 177–178

cons cells, 135–136

conceptual exercise for, 141

list-box diagrams, 136–140

list representation, 136

functions on lists

append and reverse, 141–144

difference lists technique, 144–146

list length function, 141

programming exercises for, 146–149

hallmarks of, 126

lambda calculus, 126–127

languages and software engineering, 174

building blocks as abstractions, 174–175

language flexibility supports program modification, 175

malleable program design, 175

prototype to product, 175–176

layers of, 176–177

Lisp

introduction, 128

lists in, 128–129

lists in, 127–128

local binding

conceptual exercises for, 164

let and let* expressions, 156–158

letrec expression, 158

programming exercises for, 164–165

using let and letrec to define, 158–161

other languages supporting, 161–164

programming project for, 178–179

recursive-descent parsers, Scheme predicates as, 153

atom?, list-of-atoms?, and list-of-numbers?, 153–154

list-of pattern, 154–156

programming exercise for, 156

Scheme

conceptual exercise for, 134

homoiconicity, 133–134

interactive and illustrative session with, 129–133

programming exercises for, 134–135

functions, 126

non-recursive functions adding support for user-defined functions to Camille, 423–426

augmenting

evaluate_expr

function, 427–430

closures, 426–427

conceptual exercises for, 431–432

programming exercises for, 432–440

simple stack object, 430–431

recursive functions

adding support for recursion in Camille, 440–441

augmenting

evaluate_expr with new variants, 445–446

conceptual exercises for, 446–447

programming exercises for, 447–450

recursive environment, 441–445

functions on lists

append and reverse, 141–144

difference lists technique, 144–146

list length function, 141

programming exercises for, 146–149

functor, 645

G

generate-filter style of programming, 507

generative construct, 41

global transfer of control

with continuations

breakpoints, 560–562

conceptual exercises for, 564–565

first-class continuations in Ruby, 562–563

nonlocal exits, 556–560

programming exercises for, 565–570

other mechanisms for, 570

conceptual exercises for, 578

goto statement, 570–571

programming exercises for, 578–579

setjmp and longjmp, 571–578

goal. See headless Horn clause

goto statement, 570–571

grammars, 40–41

conceptual exercises for, 61–64

context-free languages and, 42–44

disambiguation

associativity of operators, 57–58

classical dangling else problem, 58–60

operator precedence, 57

generate sentences from, 44–46

language recognition, 46f, 47–48

regular, 41–42

growing continuation, 610–613

growing stack, 610–613

H

handle, 48

hardware description languages, 17

Haskell languages, 162, 258–259

all built-in functions in, 301–307

analysis, 385

applications, 383–385

comparison of, 383

curry and uncurry functions in, 295–297

folding lists in, 319

sections in, 316–319

summaries, 382–383

variant records in, 348–352

headed Horn clause, 653, 656

headless Horn clause, 653, 656, 665

heterogeneous lists, 128

higher-order functions (HOFs), 155, 716

analysis, 334–335

conceptual exercises for, 329–330

crafting cleverly conceived functions with curried, 324–328

folding lists, 319–324

functional composition, 315–316

functional mapping, 313–315

programming exercises for, 330–334

sections in Haskell, 316–319

Hindley–Milner algorithm, 270

HOFs. See higher-order functions (HOFs)

homoiconic language, 133, 540

homoiconicity, 133–134

Horn clauses, 653–654

limited expressivity of, 702

in Prolog syntax, casting, 663

host language, 115

hybrid language

implementations, 109

hybrid systems, 112

hypothesis, 656

I

imperative programming, 10

implication function, 643

implicit conversion, 248–252

implicit currying, 301

implicit typing, 268

implode function, 325–326

independent set, 680

inductive data types, 344–347

instance variables, 216

instantiation, 651

interactive or incremental testing, 146

interactive top-level. See read-eval-print loop

interface polymorphism, 267

interpretation vis-à-vis compilation, 103–109

interpreter, 103

advantages and disadvantages of, 115t

vs. compilers, 114–115

introspection, 703

iterative control behavior, 596–598, 596f

J

JIT. See Just-in-Time (JIT) implementations

join functions, 728

Just-in-Time (JIT)

implementations, 111

K

keyword arguments, 735–737

Kleene closure operator, 34

L

LALR(1) parsers, 90

lambda (λ) calculus, 11, 126–127

abstract syntax, 356–359

scope rule for, 187–188

lambda functions, 738–739

Python primer, 738–739

Language-INtegrated Queries (LINQ), 18

languages

defined, 4

definition time, 6

development, factors

influencing, 21–25

generator, 79–80

implementation time, 6

and software engineering, 174

building blocks as abstractions, 174–175

language flexibility supports program modification, 175

malleable program design, 175

prototype to product, 175–176

themes revisited, 714

late binding. See dynamic binding

LATEX compiler, 106

lazy evaluation, 160

analysis of, 511–512

applications of, 511

β-reduction, 492–495

C macros to demonstrate pass-by-name, 495–499

conceptual exercises for, 513–517

enables list comprehensions, 506–511

implementing, 501–505

introduction, 492

programming exercises for, 517–522

purity and consistency, 512–513

tail recursion, 601–606

two implementations of, 499–501

learning language concepts, through interpreters, 393–394

left-linear grammars, 41

leftmost derivation, 45

length function, 141

let expressions, 156–158

let* expressions, 156–158

letrec expression, 158

lexemes, 40, 72

lexical addressing, 193–194

conceptual exercises for, 194–195

programming exercise for, 195

lexical analysis, 72

lexical closures, 716, 739–740

lexical depth, 193

lexical scoping, 187–192, 425

and dynamically scoped variables, 207–211

exceptions, 581

linear grammar, 41

link time, 6

LINQ. See Language-INtegrated Queries (LINQ)

Lisp, 11, 176

introduction, 128

lists in, 128–129

list-and-symbol representation.

See S-expression

list-box diagrams, 136–140

list-of pattern, 154–156

list-of-vectors representation (LOVR), 379

lists

comprehensions, lazy evaluation, 506–511

in functional programming, 127

functions

append and reverse, 141–144

difference lists technique, 144–146

list length function, 141

programming exercises for, 146–149

in Lisp, 128–129

and pattern matching in, 672–674

predicates in Prolog, 674–675

Python primer, 731–733

representation, 136

literal function, 130

literate programming, 23

load time, 6

local binding

conceptual exercises for, 164

and conditional evaluation

Camille grammar and language, 395–396

checkpoint, 391–393

conditional evaluation in Camille, 410–411

first Camille interpreter, 396–405

interpreter essentials, 394–395

learning language concepts

through interpreters, 393–394

programming exercises for, 417–419

putting it all together, 411–417

syntactic and operational support for local binding, 405–410

let and let* expressions, 156–158

letrec expression, 158

other languages supporting, 161–164

programming exercises for, 164–165

Python primer, 742

using let and letrec to define, 158–161

local block, 190

local reference, 190

logic programming analysis of Prolog

metacircularProlog

interpreter and WAM, 704–705

Prolog vis-à-vis predicate

calculus, 701–703

reflection in, 703–704

applications of decision trees, 710

natural language processing, 709

CLIPS programming language, 705

asserting facts and rules, 705–706

conditional facts in rules, 708

programming exercises for, 708–709

templates, 707

variables, 706–707

first-order predicate calculus, 644–645

conjunctive normal form, 646–648

representing knowledge as predicates, 645–646

imparting more control in, 691–697

conceptual exercises for, 697–698

programming exercises for, 698–701

introduction, 641–642

from predicate calculus to

clausal form, 651–653

conversion examples, 654–656

formalism gone awry, 660

Horn clauses, 653–654

motif of, 656

resolution with propositions in clausal form, 657–660

Prolog programming language, 660–662

analogs between Prolog and RDBMS, 681–685

arithmetic in, 677–678

asserting facts and rules, 662–663

casting Horn clauses in Prolog syntax, 663

conceptual exercises for, 685–686

graphs, 679–681

list predicates in, 674–675

lists and pattern matching in, 672–674

negation as failure in, 678–679

primitive nature of append, 675–676

program control in, 667–672

programming exercises for, 686–691

resolution, unification, and instantiation, 665–667

running and interacting with, 663–665

tracing resolution process, 676–677

propositional calculus, 642–644

resolution

in predicate calculus, 649–651

in propositional calculus, 648–649

logical equivalence, 644

logician Haskell Curry, 292

LOVR. See list-of-vectors

representation (LOVR)

M

macros, 716

operator, 176

malleable program design, 175

manifest typing, 132. See also implicit typing

Match-Resolve-Act cycle, 705

memoized lazy evaluation. See pass-by-need

Mercury programming language, 14

mergesort function, 744–748

metacharacters, 36

metacircular interpreters, 539–540, 704–705

programming exercise for, 540–542

MetaLanguage (ML), 36, 162

analogs, 308–310

analysis, 385

applications, 383–385

comparison of, 383

summaries, 382–383

metaphor, 24

metaprogramming, 716

ML. See MetaLanguage (ML)

modus ponens, 648

monomorphic, 253

multi-line comments, Python, 727

mutual recursion, Python

primer, 744

N

named keyword arguments, 735–737

natural language processing, 709

nested functions, Python primer, 743

nested lets, to simulate sequential evaluation, 458–459

non-recursive functions

adding support for user-defined functions to Camille, 423–426

augmenting evaluate_expr function, 427–430

closures, 426–427

conceptual exercises for, 431–432

programming exercises for, 432–440

simple stack object, 430–431

non-terminal alphabet, 40

nonfunctional requirements, 19

nonlocal exits, 553, 556–560

normal-order evaluation, 493

ntExpressionList variant, 402

O

object-oriented programming in, 12–13, 748–750

occurs-bound?, 197–198

occurs-free?, 197–198

operational semantics, 19

operator precedence, 57

operator/function overloading, 263–267

overloading, 258

P

palindromes, 34

papply function, 288

parameter passing

assignment statement, 457–458

conceptual and programming exercises for, 465–467

environment, 462–463

illustration of pass-by-value in Camille, 459–460

reference data type, 460–461

stack object, 463–465

use of nested lets to simulate sequential evaluation, 458–459

Camille interpreters, 533–537

conceptual and programming exercises for, 537–539

implementing

pass-by-name/need in

Camille, 522–526

programming exercises for, 526–527

implementing

pass-by-reference in Camille

interpreter, 485

programming exercise for, 490–492

reimplementation of

evaluate_operand function, 487–490

revised implementation of references, 486–487

lazy evaluation

analysis of, 511–512

applications of, 511

β-reduction, 492–495

C macros to demonstrate pass-by-name, 495–499

conceptual exercises for, 513–517

enables list comprehensions, 506–511

implementing, 501–505

introduction, 492

programming exercises for, 517–522

purity and consistency, 512–513

two implementations of, 499–501

metacircular interpreters, 539–540

programming exercise for, 540–542

sequential execution in Camille, 527–532

programming exercise for, 533

survey of

conceptual exercises for, 482–484

pass-by-reference, 472–477

pass-by-result, 477–478

pass-by-value, 467–472

pass-by-value-result, 478–480

programming exercises for, 484–485

summary, 481–482

parametric polymorphism, 253–262

parse trees, 51–56

parser, 258

parser generator, 81

parsing, 46f, 47–48, 74–76

bottom-up, shift-reduce, 80–82

complete example in lex and yacc, 82–84

conceptual exercises for, 90

infuse semantics into, 50

programming exercises for, 90–100

Python lex-yacc, 84

Camille scanner and parser generators in, 86–89

complete example in, 84–86

recursive-descent, 76

complete recursive-descent parser, 76–79

language generator, 79–80

top-down vis-à-vis bottom-up, 89–90

partial argument application. See partial function application

partial function application, 285–292

partial function instantiation. See partial function application

pass-by-copy, 144. See also pass-by-value

pass-by-name, 499–500

C macros to demonstrate, 495–499

implementing in Camille, 522–526

programming exercises for, 526–527

pass-by-need, 499–500

implementing in Camille, 522–526

programming exercises for, 526–527

pass-by-reference, 472–477

pass-by-result, 477–478

pass-by-sharing, 471

pass-by-value, 459–460, 467–472

pass-by-value-result, 478–480

pattern-directed invocation, 17

Perl, 207

program demonstrating dynamic scoping, 208

whose run-time call chain depends on its input, 210

+ operator, 36

polymorphic, 144, 253

polysemes, 55, 56t

positional vis-à-vis keyword arguments, 735–738

pow function, 131

powerset function, 327–328

powucf function, 293

precedence, 50

predicate calculus

to logic programming

clausal form, 651–653

conversion examples, 654–656

formalism gone awry, 660

Horn clauses, 653–654

motif of, 656

resolution with propositions in clausal form, 657–660

representing knowledge as, 645–646

resolution in, 649–651

vis-à-vis predicate calculus, 701–703

primitive car, 142

primitive cdr, 142

primitive cons, 142

problem solving, thought process for, 20–21

procedure, 126

program-compile-debug-recompile loop, 175

program, definition of, 4

programming language

bindings, 6–7

concept, 4–5, 7–8

concepts, 7–8

definition of, 4

features of type systems used in, 248t

fundamental questions, 4–6

implementation

influence of language goals on, 116

interpretation vis-à-vis compilation, 103–109

interpreters and compilers, comparison of, 114–115

programming exercises for, 117–121

run-time systems, 109–114

levels of exception handling in, 579

dynamically scoped exceptions, 582–583

first-class continuations, 583–584

function calls, 580–581

lexically scoped exceptions, 581

programming exercises for, 584–585

stack unwinding/crawling, 581–582

recurring themes in, 25–26

scope rules of, 187

programming styles

bottom-up programming, 15–16

functional programming, 11–12

imperative programming, 8–10

language evaluation criteria, 19–20

logic/declarative

programming, 13–15

object-oriented programming, 12–13

synthesis, 16–19

thought process for problem solving, 20–21

Prolog programming language, 14, 660–662

analysis of metacircularProlog interpreter and WAM, 704–705

Prolog vis-à-vis predicate calculus, 701–703

reflection in, 703–704

arithmetic in, 677–678

asserting facts and rules, 662–663

casting Horn clauses in Prolog syntax, 663

conceptual exercises for, 685–686

graphs, 679–681

imparting more control in, 691–697

conceptual exercises for, 697–698

programming exercises for, 698–701

list predicates in, 674–675

lists and pattern matching in, 672–674

negation as failure in, 678–679

primitive nature of append, 675–676

program control in, 667–672

programming exercises for, 686–691

and RDBMS, analogs between, 681–685

resolution, unification, and

instantiation, 665–667

running and interacting with, 663–665

tracing resolution process, 676–677

promise, 501

proof by refutation, 649

propositional calculus, 642–644

resolution in, 648–649

pure interpretation, 112

purity, concept of, 12

pushdown automata, 43

Python, 19

abstract-syntax representation in, 372–373

closure data type in, 426

closure representation in, 371–372

FUNARG problem, 222

lex-yacc, 84

Camille scanner and parser generators in, 86–89

complete example in, 84–86

Python primer

data types, 722–725

essential operators and expressions, 725–731

exception handling, 750–751

introduction, 722

lists, 731–733

object-oriented programming in, 748–750

overview, 721–722

programming exercises for, 751–754

tuples, 733–734

user-defined functions

lambda functions, 738–739

lexical closures, 739–740

local binding and nested functions, 742–743

mergesort, 744–748

more user-defined functions, 740–742

mutual recursion, 744

positional vis-à-vis keyword arguments, 735–738

simple user-defined functions, 734–735

Q

qualified type or constrained type, 257

R

Racket programming language, 128

RDBMS. See relational database management system (RDBMS)

read-eval-print loop (REPL), 130, 175, 394, 403–404

read-only reflection, 703

records, 338–340

recurring themes in study of languages, 25–27

recursive-control behavior, 143, 594–595

recursive-descent parsers

Scheme predicates as, 153

atom?, list-of-atoms?, and list-of-numbers?, 153–154

list-of pattern, 154–156

programming exercise for, 156

recursive-descent parsing, 48, 76

complete recursive-descent parser, 76–79

language generator, 79–80

recursive environment

abstract-syntax representation of, 443–444

list-of-lists representation of, 444–445

recursive functions

adding support for recursion in Camille, 440–441

augmenting evaluate_expr with new variants, 445–446

conceptual exercises for, 446–447

programming exercises for, 447–450

recursive environment, 441–445

reduce-reduce conflict, 51

reducing, 48

reference data type, 460–461

referencing environment, 130, 366

referential transparency, 10

regular expressions, 35–38

conceptual exercises for, 39–40

regular grammars, 41–42

regular language, 39

conceptual exercises for, 39–40

relational database management

system (RDBMS), analogs

between Prolog and, 681–685

REPL. See read-eval-print loop (REPL)

representation

abstract-syntax representation in Python, 372–373

choices of, 367

closure representation in Python, 371–372

closure representation in Scheme, 367–371

resolution, 383

in predicate calculus, 649–651

proof by contradiction, 659

in propositional calculus, 648–649

resumable exceptions, 583

resumable semantics, 583

Rete Algorithm, 705

revised implementation of references, 486–487

ribcage representation, 377

right-linear grammar, 41

rightmost derivation, 46

Ruby

first-class continuations in, 562–563

Scheme implementation of coroutines, 588–589

rule of detachment, 648

run-time complexity, 141–144

run-time systems, 109–114

S

S-expression, 129, 356–357

same-fringe problem, 511

Sapir–Whorf hypothesis, 5

scanning, 72–74

conceptual exercises for, 90

programming exercises for, 90–100

Scheme programming language, 540

closure representation in, 367–371

conceptual exercise for, 134

homoiconicity, 133–134

interactive and illustrative session with, 129–133

programming exercises for, 134–135

variable-length argument lists in, 274–278

variant records in, 352–354

Schönfinkel, Moses, 292

scope, closure vs., 224–225

scripting languages, 17

self-interpreter, 539

semantics, 64–67

conceptual exercises for, 67

consequence, 643

in syntax, modeling some, 49–51

sentence derivations, 44–46

sentence validity, 34

sentential form, 44

sequential execution, in Camille, 527–532

programming exercise for, 533

set-builder notation, 507

set-former, 507

setjmp and longjmp, 571–578

shallow binding, 235–236

shift-reduce conflict, 51

shift-reduce parsers, 81

shift-reduce parsing, 48

short-circuit evaluation, 492

side effect, 7

Sieve of Eratosthenes algorithm, 507

simple interpreter for Camille, 399–401

simple stack object, 430–431

simple user-defined functions, Python primer, 734–735

simulated-pass-by-reference, 475

single-line comments, Python, 727

single list argument, 276

SLLGEN, 354

Smalltalk programming language, 12–13, 225

sortedElem function, 507

space complexity

tail recursion, 601–606

trade-off between time and, 614–617

split functions, 728

SQL query, 14

square function, 499

stack frame. See activation record

stack object, 463–465. See also simple stack object

stack of interpreted software interpreters, 112

stack unwinding/crawling, 581–582

static bindings, 6, 116

static call graph, 200

static scoping

advantages and disadvantages of, 203t

conceptual exercises for, 192–193

lexical scoping, 187–192

vs. dynamic scoping, 202–207

static semantics, 67

static type system, 245

static vis-à-vis dynamic properties, 186, 188t

static/dynamic typing, 268

string, 34

string2int function, 326–327

struct. See records

SWI-Prolog, 663

symbol table, 194

symbolic logic, 642

syntactic ambiguity, 48–49

conceptual exercises for, 61–64

modeling some semantics in, 49–51

parse trees, 51–56

syntactic analysis. See parsing

syntatic sugar, 45

syntax, 34

T

table-driven, top-down parser, 75

tail-call optimization, 598–600

tail recursion

iterative control behavior, 596–598, 596f

programming exercises for, 606–608

recursive control behavior, 594–595

space complexity and lazy evaluation, 601–606

tail-call optimization, 598–600

tautology, 644

terminals, 40

terminating semantics, 582

terms, definition of, 651

throwaway prototype, 22, 176

thunk, 501–505

time and space complexity, trade-off between, 614–617

top-down parser, 75

top-down parsing, 48

top-down vis-à-vis bottom-up parsing, 89–90

traditional compilation, 112

TreeNode, 359–360

tuples, 275, 338

Python primer, 733–734

Turing-complete. See programming language

Turing machine, 5

type cast, 252

type checking, 246–248

type class, 257

type inference, 268–274

type signatures, 310

type systems

conceptual exercises for, 278–280

conversion, coercion, and casting

conversion functions, 252–253

explicit conversion, 252

implicit conversion, 248–252

function overriding, 267–268

inference, 268–274

introduction, 245–246

operator/function overloading, 263–267

parametric polymorphism, 253–262

static/dynamic typing vis-à-vis explicit/implicit typing, 268

type checking, 246–248

variable-length argument lists in Scheme, 274–278

U

undiscriminated unions, 341–343

unification, 651

UNIX shell scripts, 116

unnamed keyword arguments, 735–737

upward FUNARG problem, 215–224

in single function, 225–226

user-defined functions

Python primer

lambda functions, 738–739

lexical closures, 739–740

local binding and nested functions, 742–743

mergesort, 744–748

more user-defined functions, 740–742

mutual recursion, 744

positional vis-à-vis keyword arguments, 735–738

simple user-defined functions, 734–735

V

variable assignment, 458

variable-length argument lists, in Scheme, 274–278

variadic function, 275

variant records, 347–348

in Haskell, 348–352

programming exercises for, 354–356

in Scheme, 352–354

very-high-level languages. See logic programming, declarative programming

virtual machine, 109

von Neumann architecture, 7

W

WAM. See Warren Abstract Machine (WAM)

Warren Abstract Machine (WAM), 705

weakly typed languages, 247

web browsers, 106

web frameworks, 17

well-formed formulas (wffs), 646

wffs. See well-formed formulas (wffs)

Y

Y combinatory, 159

yacc parser generator, 81

shift-reduce, bottom-up parser, 82–84