44e26d6972
- CLAUDE.md 생성 (볼트 운영 규칙, Karpathy LLM Wiki 10가지 규칙) - 나의 핵심 맥락.md 생성 (아키텍트 프로필, 세컨드 브레인 목적, 핵심 소스) - raw/ 구조 정립 (book/기존 설계원칙 보존, articles/repos/notes/ 추가) - wiki/ 초기화 (index.md, log.md, concepts/sources/patterns/ 폴더) - output/ 초기화 - LLMWiki/ 기존 프롬프트 패턴 파일 보존 Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
1429 lines
86 KiB
Markdown
1429 lines
86 KiB
Markdown
# **Domain-Specific Languages**
|
||
|
||
One powerful strategy for building flexibility into a programming project is to create a *domain-specific language* that captures the conceptual structure of the subject matter of the programs to be developed. A domain-specific language is an abstraction in which the nouns and verbs of the language are directly related to the problem domain. Such a language allows an application program to be written directly in terms of the domain. By its nature, a domainspecific language implements a fairly complete model of the domain, in excess of what is needed for a particular application. [1](#page-53-0) Although this may seem like extra work that is not essential to the particular problem at hand, it is often less work than writing a monolithic program, and the resulting program is much easier to modify, debug, and extend.
|
||
|
||
<span id="page-0-0"></span>So a domain-specific language layer is built to support more than just the development of a particular program. It provides a general framework for the construction of a variety of related programs that share the domain of discourse. It simplifies the process of extending an existing application in that domain. And it provides a substrate that allows related applications to cooperate.
|
||
|
||
In this chapter we first introduce systems of combinators, a powerful organizational strategy for the erection of domain-specific language layers. We will demonstrate the effectiveness of this strategy by showing how to reformulate the ugly mess of regular expressions for string matching into a pretty combinator-based domain-specific language embedded in Scheme. But sometimes we have components that do not easily fit into a clean systemsometimes we need a system of adapters. We illustrate this with a domain-specific language for making unit-conversion wrappers for procedures, allowing procedures written assuming one unit system to be used with a different unit system. Finally, we consider the broad domain of board games. We see how it is possible to abstract the details of the domain by building an interpreter for the rules of the game.
|
||
|
||
## **2.1 Combinators**
|
||
|
||
Biological systems achieve much of their adaptability through the use of very general parts (cells) that are dynamically configured and consequently able to adjust as their environment changes. Computational systems usually do not use this strategy, instead relying on a hierarchy of custom parts and combinations. In recent years, large libraries of well-specified higher-level parts have raised the abstraction level of this activity. But the means of combination are rarely abstracted or shared, other than as "patterns." [2](#page-53-1)
|
||
|
||
<span id="page-1-0"></span>In some situations we can improve on this practice by simple strategies that promote the use of shared combination mechanisms. If the systems we build are made up from members of a family of "mix-and-match" components that combine to make new members of the family, perturbations of the requirements can sometimes be addressed by rearrangement of components.
|
||
|
||
A *system of combinators* is a set of primitive parts and a set of means of combining parts such that the interface specifications of the combinations are the same as those of the primitives. This enables construction without accidental interactions between the parts. A classic example of a combinator-like system is TTL [123], which is a historic library of standard parts and combinations for building complex digital systems.
|
||
|
||
Combinator systems provide a design strategy for domainspecific languages. The elements of the system are words in the language, and the combinators are used to combine them into
|
||
|
||
phrases. Combinator systems have the significant advantage that they are easy to build and to reason about, but they have limitations, which we will discuss in section 3.1.5. When they fit the domain, they are an excellent strategic choice.
|
||
|
||
But how do we arrange to build our systems by combining elements of a family of mix-and-match components? We must identify a set of primitive components and a set of *combinators* that combine components so as to make compound components with the same interface as the primitive components. Such sets of combinators are sometimes explicit, but more often implicit, in mathematical notation.
|
||
|
||
### **2.1.1 Function combinators**
|
||
|
||
The use of functional notation in mathematics is a combinator discipline. A function has a domain, from which its arguments are selected, and a range (or codomain) of its possible values. There are combinators that produce new functions as combinations of others. For example, the composition *f ○ g* of functions *f* and *g* is a new function that takes arguments in the domain of *g* and produces values in the codomain of *f*. If two functions have the same domain and codomain, and if arithmetic is defined on their common codomain, then we can define the sum (or product) of the functions as the function that when given an argument in their common domain, is the sum (or product) of the values of the two functions at that argument. Languages that allow first-class procedures provide a mechanism to support this means of combination, but what really matters is a good family of pieces.
|
||
|
||
Organizing a system around combinators has several advantages. The parts that are made can be arbitrarily mixed and matched. Any combination yields a legal program, whose behavior transparently depends only on the behaviors of the parts and the ways that they are combined. The context in which a part appears does not change the behavior of the part: it is always acceptable to pick up a compound part to use it in a new context, without worry about its behavior in that context. Thus such programs are easy to write, easy
|
||
|
||
to read, and easy to verify. A program built on combinators is extensible, because introduction of new parts or new combinators does not affect the behavior of existing programs.
|
||
|
||
We can think of function combinators as implementing wiring diagrams that specify how a function is built by combining its parts. For example, functional composition represents a box made of two subboxes so that the output of the first feeds the input of the second, as shown in [figure](#page-3-0) 2.1. A program that implements this idea is straightforward:
|
||
|
||
```
|
||
(define (compose f g)
|
||
(lambda args
|
||
(f (apply g args))))
|
||
```
|
||
|
||
<span id="page-3-0"></span>
|
||
|
||
**[Figure](#page-3-1) 2.1** The composition *f ◦ g* of functions *f* and *g* is a new function that is defined by this "wiring diagram." The input to *f ◦ g* is given to *g*. The output of *g* is then passed to *f* , and it produces the output of *f ◦ g*.
|
||
|
||
(It gets more exciting if we want to check that the arities match: that the function represented by procedure f takes only one argument, to match the output of g. It gets even more fun if g can return multiple values and f must take those arguments. We may also want to check that the arguments passed to the composition are the right number for g. But these are fine points that we will deal with later.)
|
||
|
||
We can demonstrate composition with a simple example:
|
||
|
||
```
|
||
((compose (lambda (x) (list 'foo x))
|
||
(lambda (x) (list 'bar x)))
|
||
```
|
||
|
||
```
|
||
'z)
|
||
(foo (bar z))
|
||
```
|
||
|
||
It is sometimes nicer to name the procedure that is being returned by a combinator. For example, we could write compose as
|
||
|
||
```
|
||
(define (compose f g)
|
||
(define (the-composition . args)
|
||
(f (apply g args)))
|
||
the-composition)
|
||
```
|
||
|
||
The name the-composition is not defined outside of the scope of the definition of compose, so there is no obvious advantage to this way of writing the compose procedure. We often use anonymous procedures defined by lambda expressions in our programs, as in the first version of compose above. So the choice of how to write the program is mostly a matter of style. [3](#page-53-2)
|
||
|
||
<span id="page-4-0"></span>Even with just this compose combinator we can write some rather elegant code. Consider the problem of computing the *n*th iterate of a function *f*(*x*) = *f*(*f <sup>−</sup>*1(*x*)). We can write this elegantly as a program:
|
||
|
||
```
|
||
(define ((iterate n) f)
|
||
(if (= n 0)
|
||
identity
|
||
(compose f ((iterate (- n 1)) f))))
|
||
(define (identity x) x)
|
||
```
|
||
|
||
The result of ((iterate n) f) is a new function, of the same type as f. It can be used wherever f can be used. So (iterate n) is itself a function combinator. Now we can use this to determine the result of repeatedly squaring a number:
|
||
|
||
```
|
||
(((iterate 3) square) 5)
|
||
390625
|
||
```
|
||
|
||
Notice the analogy: function composition is like multiplication, so function iteration is like exponentiation.
|
||
|
||
There are many simple combinators that are generally useful in programming. We will present just a few here to give a feeling for
|
||
|
||
<span id="page-5-1"></span>the range of possibilities.
|
||
|
||
We can arrange to use two functions in parallel, then combine their results with a specified combiner function (see [figure](#page-5-0) 2.2). This parallel combination is implemented with the procedure
|
||
|
||
<span id="page-5-0"></span>
|
||
|
||
**[Figure](#page-5-1) 2.2** In parallel-combine the functions *f* and *g* take the same number of arguments. The input to the "parallel combination" is passed to both of them. Their outputs are then combined by the function *h*, of two arguments.
|
||
|
||
```
|
||
(define (parallel-combine h f g)
|
||
(define (the-combination . args)
|
||
(h (apply f args) (apply g args)))
|
||
the-combination)
|
||
((parallel-combine list
|
||
(lambda (x y z) (list 'foo x y z))
|
||
(lambda (u v w) (list 'bar u v w)))
|
||
'a 'b 'c)
|
||
((foo a b c) (bar a b c))
|
||
```
|
||
|
||
The parallel-combine combinator can be useful in organizing a complex process. For example, suppose we have a source of images of pieces of vegetable. We may have one procedure that given the image can estimate the color of the vegetable, and another that can
|
||
|
||
give a description of the shape (leaf, root, stalk, ...). We may have a third procedure that can combine these descriptions to identify the vegetable. These can be neatly composed with parallel-combine.
|
||
|
||
### **Arity**
|
||
|
||
<span id="page-6-0"></span>There are entire families of combinators that we can use in programming that we don't normally think of. Many of these appear in common mathematical contexts. For example, tensors are an extension of linear algebra to linear operators with multiple arguments. But the idea is more general than that: the "tensor combination" of two procedures is just a new procedure that takes a data structure combining arguments for the two procedures. It distributes those arguments to the two procedures, producing a data structure that combines the values of the two procedures. The need to unbundle a data structure, operate on the parts separately, and rebundle the results is ubiquitous in programming. The wiring diagram in [figure](#page-7-0) 2.3 shows spread-combine. It is a generalization of the tensor product in multilinear algebra. In the mathematical tensor product, *f* and *g* are linear functions of their inputs, and *h* is a trace over some shared indices; but tensors are just the special case that inspired this combinator.
|
||
|
||
<span id="page-7-0"></span>
|
||
|
||
**[Figure](#page-6-0) 2.3** In spread-combine the *n* +*m* arguments are split between the functions *f* and *g*. The first *n* arguments go to *f* and the *m* other arguments go to *g*. The resulting outputs are then combined by the function *h*, of two arguments.
|
||
|
||
The program to implement spread-combine is a bit more complicated than parallel-combine, because it must distribute the correct arguments to f and g. Here is a first draft of that code:
|
||
|
||
```
|
||
(define (spread-combine h f g)
|
||
(let ((n (get-arity f)))
|
||
(define (the-combination . args)
|
||
(h (apply f (list-head args n))
|
||
(apply g (list-tail args n))))
|
||
the-combination))
|
||
```
|
||
|
||
This code requires a way of determining how many arguments a procedure takes (its *arity*), because it has to pick out the arguments for f and then pass the rest to g.
|
||
|
||
This version of spread-combine is not very good. The most egregious problem is that the-combination takes any number of arguments, so it does not have a well-defined numerical arity, and thus it cannot be passed to another combinator that needs its arity. For example, the result of a spread-combine cannot be passed as the second argument f to another spread-combine. So, somehow,
|
||
|
||
we have to decorate the-combination with an appropriate arity. Here is a second draft:
|
||
|
||
```
|
||
(define (spread-combine h f g)
|
||
(let ((n (get-arity f)) (m (get-arity g)))
|
||
(let ((t (+ n m)))
|
||
(define (the-combination . args)
|
||
(h (apply f (list-head args n))
|
||
(apply g (list-tail args n))))
|
||
(restrict-arity the-combination t))))
|
||
```
|
||
|
||
Here, the procedure the-combination that is returned has its arity specified, so it can be the input to some other combinator that requires an arity. The restrict-arity procedure takes a procedure, annotates it so that its arity can be obtained by getarity, and returns the annotated procedure.
|
||
|
||
This is pretty good, but the best programs are written by paranoids! We want to catch errors as early as possible, before they become hard to locate or cause serious trouble. So let's annotate this code with an *assertion* in *Paranoid Programming Style*, to check that we have the right number of arguments to our combination.
|
||
|
||
```
|
||
(define (spread-combine h f g)
|
||
(let ((n (get-arity f)) (m (get-arity g)))
|
||
(let ((t (+ n m)))
|
||
(define (the-combination . args)
|
||
(assert (= (length args) t))
|
||
(h (apply f (list-head args n))
|
||
(apply g (list-tail args n))))
|
||
(restrict-arity the-combination t))))
|
||
((spread-combine list
|
||
(lambda (x y) (list 'foo x y))
|
||
(lambda (u v w) (list 'bar u v w)))
|
||
'a 'b 'c 'd 'e)
|
||
((foo a b) (bar c d e))
|
||
```
|
||
|
||
The special form assert is just a convenient way to signal an error if its argument does not have a true value.
|
||
|
||
One way to write restrict-arity and get-arity is as follows:
|
||
|
||
```
|
||
(define (restrict-arity proc nargs)
|
||
(hash-table-set! arity-table proc nargs)
|
||
proc)
|
||
(define (get-arity proc)
|
||
(or (hash-table-ref/default arity-table proc #f)
|
||
(let ((a (procedure-arity proc))) ;arity not in table
|
||
(assert (eqv? (procedure-arity-min a)
|
||
(procedure-arity-max a)))
|
||
(procedure-arity-min a))))
|
||
(define arity-table (make-key-weak-eqv-hash-table))
|
||
```
|
||
|
||
<span id="page-9-0"></span>Here we are using a hash table to attach a "sticky note" to the procedure. [4](#page-53-3) This is a simple trick for adding information to an existing object, but it depends on the uniqueness of the object being annotated, so it should be used carefully.
|
||
|
||
If the procedure get-arity is unable to find an explicit value in arity-table, it computes one using primitives from the underlying MIT/GNU Scheme system. This involves some hair, because those primitives support a more general idea of arity: that a procedure requires a minimum number of arguments, and may have an optional maximum number of arguments. Our arity code expects an arity to be a fixed number of arguments, and so get-arity cannot work with any other kind of procedure. Unfortunately, this excludes procedures like + that take any number of arguments. Changing the arity code to use a more general notion of arity would complicate it, and our goal here is to have a clear exposition rather than a general solution (see exercise 2.2).
|
||
|
||
# **Exercise 2.1: Arity repair**
|
||
|
||
The procedures compose and parallel-combine that we have introduced do not obey the requirement that they advertise the arity of the combination. Thus they would not be good citizens of our family of combinators. Fix the implementations of compose and parallel-combine shown above, so that
|
||
|
||
- they check their components to make sure that the arities are compatible;
|
||
- the combination they construct checks that it is given the correct number of arguments when it is called;
|
||
- the combination advertises its arity correctly for get-arity.
|
||
|
||
# **Exercise 2.2: Arity extension**
|
||
|
||
Our exposition of useful combinators is flawed in that the arity mechanism we displayed cannot handle the more general arity mechanism used by MIT/GNU Scheme. For example, the addition procedure, which is the value of +, can take any number of arguments:
|
||
|
||
```
|
||
(procedure-arity-min (procedure-arity +)) = 0
|
||
(procedure-arity-max (procedure-arity +)) = #f
|
||
```
|
||
|
||
and the arctangent procedure can take either 1 or 2 arguments:
|
||
|
||
```
|
||
(procedure-arity-min (procedure-arity atan)) = 1
|
||
(procedure-arity-max (procedure-arity atan)) = 2
|
||
```
|
||
|
||
It is useful to extend the handling of arities so that combinators can work with these more complex situations.
|
||
|
||
- **a.** Sketch a plan for how to extend the combinators to use the more general arities. Note that you may not always be able to use arithmetic on the arities. What choices will you have to make in reformulating spread-combine? For example, what kinds of restrictions will be needed on the procedures f, g, and h in spread-combine?
|
||
- **b.** Apply your plan and make it all work!
|
||
|
||
For any language there are primitives, means of combination, and means of abstraction. A *combinator language* defines primitives and means of combination, inheriting its means of
|
||
|
||
abstraction from the underlying programming language. In our example, the primitives are functions, and the means of combination are the combinators compose, parallel-combine, spread-combine, and others we may introduce.
|
||
|
||
### **Multiple values**
|
||
|
||
Notice that parallel-combine and spread-combine are similar in that each is the application of a combiner h to the results of f and g. But we did not use compose to construct these combinators. To abstract this pattern we need to be able to return multiple values from the combination of f and g and then use those multiple values as arguments for h. We could do this by returning a compound data structure, but a better way is to use the Scheme multiple-value return mechanism. Given multiple values we can define spreadcombine as a composition of two parts, h and this combination of f and g: [5](#page-53-4)
|
||
|
||
```
|
||
(define (spread-apply f g)
|
||
(let ((n (get-arity f)) (m (get-arity g)))
|
||
(let ((t (+ n m)))
|
||
(define (the-combination . args)
|
||
(assert (= (length args) t))
|
||
(values (apply f (list-head args n))
|
||
(apply g (list-tail args n))))
|
||
(restrict-arity the-combination t))))
|
||
```
|
||
|
||
<span id="page-12-1"></span>
|
||
|
||
**[Figure](#page-12-0) 2.4** The combinator spread-combine is really a composition of two parts. The first part, spread-apply, is the combination of the functions *f* and *g* with the correct arguments routed to them. The second part is the combiner *h*, which is just composed with the first part. This decomposition is enabled by use of the multiple-values mechanism of Scheme.
|
||
|
||
<span id="page-12-2"></span>The Scheme procedure values returns the results of applying both f and g. [6](#page-53-5)
|
||
|
||
<span id="page-12-0"></span>Below we will generalize compose so that we can directly implement the abstraction shown in [figure](#page-12-1) 2.4 as follows:
|
||
|
||
```
|
||
(define (spread-combine h f g)
|
||
(compose h (spread-apply f g)))
|
||
```
|
||
|
||
This has the same behavior as our original version:
|
||
|
||
```
|
||
((spread-combine list
|
||
(lambda (x y) (list 'foo x y))
|
||
(lambda (u v w) (list 'bar u v w)))
|
||
'a 'b 'c 'd 'e)
|
||
((foo a b) (bar c d e))
|
||
```
|
||
|
||
To make this work, we generalize compose to allow multiple values to pass between the composed procedures:
|
||
|
||
```
|
||
(define (compose f g)
|
||
(define (the-composition . args)
|
||
(call-with-values (lambda () (apply g args))
|
||
```
|
||
|
||
```
|
||
f))
|
||
(restrict-arity the-composition (get-arity g)))
|
||
```
|
||
|
||
Here the second argument to compose returns two values:
|
||
|
||
```
|
||
((compose (lambda (a b)
|
||
(list 'foo a b))
|
||
(lambda (x)
|
||
(values (list 'bar x)
|
||
(list 'baz x))))
|
||
'z)
|
||
(foo (bar z) (baz z))
|
||
```
|
||
|
||
Now we can generalize even further. We can allow all of the functions we are combining to return multiple values. If f and g both return multiple values we can combine those values into multiple values that the-combination can return:
|
||
|
||
```
|
||
(define (spread-apply f g)
|
||
(let ((n (get-arity f)) (m (get-arity g)))
|
||
(let ((t (+ n m)))
|
||
(define (the-combination . args)
|
||
(assert (= (length args) t))
|
||
(let-values ((fv (apply f (list-head args n)))
|
||
(gv (apply g (list-tail args n))))
|
||
(apply values (append fv gv))))
|
||
(restrict-arity the-combination t))))
|
||
((spread-combine list
|
||
(lambda (x y) (values x y))
|
||
(lambda (u v w) (values w v u)))
|
||
'a 'b 'c 'd 'e)
|
||
(a b e d c)
|
||
```
|
||
|
||
The only restriction is that the total number of values returned must be appropriate for the arity of h.
|
||
|
||
# **Exercise 2.3: A quickie**
|
||
|
||
Reformulate parallel-combine to be a composition of two parts and to allow the parts to return multiple values.
|
||
|
||
### **A small library**
|
||
|
||
Many common patterns of usage can be captured as combinators, and very pretty programs are often constructed using such techniques. It is to our advantage to expose and abstract such common patterns. Here are a few more to think about.
|
||
|
||
Often we have an interface that is more general than necessary in a particular situation. In such a case we may want to preserve the interface, but call some more specialized procedure that does not need all of the parameters we can supply in the general case; so we choose to make a version of our specialized procedure that ignores some arguments.
|
||
|
||
The procedure discard-argument takes the index, i, of the argument to be discarded and returns a combinator. The combinator takes a function, f, of *n* arguments and returns a new function thecombination of *n* + 1 arguments that applies f to the *n* arguments resulting from deleting the *i*th argument from the *n* + 1 given arguments. [Figure](#page-14-0) 2.5 illustrates this idea. The code for this combinator is:
|
||
|
||
<span id="page-14-1"></span><span id="page-14-0"></span>
|
||
|
||
**[Figure](#page-14-1) 2.5** The combinator (discard-argument 2) takes a three-argument function *f* and makes a new function of four arguments that ignores its third argument (i=2) and passes the remaining arguments to *f*.
|
||
|
||
```
|
||
(define (discard-argument i)
|
||
(assert (exact-nonnegative-integer? i))
|
||
(lambda (f)
|
||
(let ((m (+ (get-arity f) 1)))
|
||
(define (the-combination . args)
|
||
```
|
||
|
||
```
|
||
(assert (= (length args) m))
|
||
(apply f (list-remove args i)))
|
||
(assert (< i m))
|
||
(restrict-arity the-combination m))))
|
||
(define (list-remove lst index)
|
||
(let lp ((lst lst) (index index))
|
||
(if (= index 0)
|
||
(cdr lst)
|
||
(cons (car lst) (lp (cdr lst) (- index 1))))))
|
||
(((discard-argument 2)
|
||
(lambda (x y z) (list 'foo x y z)))
|
||
'a 'b 'c 'd)
|
||
(foo a b d)
|
||
```
|
||
|
||
<span id="page-15-1"></span>One can generalize this combinator to discard multiple arguments. The opposite of the situation of discard-argument also commonly occurs. In [figure](#page-15-0) 2.6 we see a wiring diagram for specializing a procedure by specifying all but one argument in advance, leaving one to be passed in the call. This is traditionally called *currying* in honor of the logician Haskell Curry, who was an early investigator of combinatory logic. [7](#page-53-6)
|
||
|
||
<span id="page-15-2"></span><span id="page-15-0"></span>
|
||
|
||
**[Figure](#page-15-1) 2.6** The combinator ((curry-argument 2) 'a 'b 'c) specifies three of the arguments to the four-argument function *f* , leaving the third argument (i=2) to be supplied in the call to the resulting one-argument function.
|
||
|
||
The code for curry-argument poses no surprises:
|
||
|
||
```
|
||
(define ((curry-argument i) . args)
|
||
(lambda (f)
|
||
(assert (= (length args) (- (get-arity f) 1)))
|
||
```
|
||
|
||
```
|
||
(lambda (x)
|
||
(apply f (list-insert args i x)))))
|
||
(define (list-insert lst index value)
|
||
(let lp ((lst lst) (index index))
|
||
(if (= index 0)
|
||
(cons value lst)
|
||
(cons (car lst) (lp (cdr lst) (- index 1))))))
|
||
((((curry-argument 2) 'a 'b 'c)
|
||
(lambda (x y z w) (list 'foo x y z w)))
|
||
'd)
|
||
(foo a b d c)
|
||
```
|
||
|
||
<span id="page-16-1"></span>Note that here we do not need to use restrict-arity because the returned procedure has exactly one argument. [8](#page-53-7) In exercise 2.5 we generalize this combinator for currying, to leave multiple arguments to be supplied.
|
||
|
||
<span id="page-16-0"></span>Sometimes we want to use a library procedure that has a different order of arguments than the standard that we are using in the current application. Rather than make a special interface for that procedure, we can use a general permutation procedure to rearrange things, as in [figure](#page-17-0) 2.7. This program is also simple, but notice that the procedure the-combination that is returned from the combinator and actually runs on args does not have to interpret the permutation specification—this is done once in the let surrounding the-combination and referred to within. In general, writing code this way allows some deep optimizations by early computation, even in the light of very late binding!
|
||
|
||
<span id="page-17-0"></span>
|
||
|
||
**[Figure](#page-16-0) 2.7** The combinator (permute-arguments 1 2 0 3) takes a function *f* of four arguments and produces a new function of four arguments that permutes its arguments according to the supplied permutation before passing them to *f*.
|
||
|
||
```
|
||
(define (permute-arguments . permspec)
|
||
(let ((permute (make-permutation permspec)))
|
||
(lambda (f)
|
||
(define (the-combination . args)
|
||
(apply f (permute args)))
|
||
(let ((n (get-arity f)))
|
||
(assert (= n (length permspec)))
|
||
(restrict-arity the-combination n)))))
|
||
(((permute-arguments 1 2 0 3)
|
||
(lambda (x y z w) (list 'foo x y z w)))
|
||
'a 'b 'c 'd)
|
||
(foo b c a d)
|
||
```
|
||
|
||
The procedure make-permutation is simple, but it is not efficient:
|
||
|
||
```
|
||
(define (make-permutation permspec)
|
||
(define (the-permuter lst)
|
||
(map (lambda (p) (list-ref lst p))
|
||
permspec))
|
||
the-permuter)
|
||
```
|
||
|
||
### **2.1.2 Combinators and body plans**
|
||
|
||
A moral of this story is that a structure composed of combinations of combinators is a body plan, much like the body plans of animals or engineering patterns like the superheterodyne radio receiver (figure 1.1 on page 10). Consider the compose combinator. It provides an arrangement of locales, the procedures f and g. The locales are connected by a standard interconnect, but that is all that
|
||
|
||
is required of f and g. Indeed, these components may be anything that can take the right number of arguments and can return the right number of values. So the combinators are organizing principles, like Hox genes: they specify locales and their relationship without mandating what happens inside each locale.
|
||
|
||
# **Exercise 2.4: As compositions?**
|
||
|
||
You may have noticed that the combinators made by discardargument, curry-argument, and permute-arguments can each be thought of as a composition of an argument manipulation and a procedure. Rebuild these combinators as compositions using the multiple-value return mechanism.
|
||
|
||
# **Exercise 2.5: Useful combinators**
|
||
|
||
It is time to fill out this small library a bit more.
|
||
|
||
- **a.** The combinators discard-argument and curry-argument could be generalized to allow ignoring or prespecializing on more than one argument. The method of specifying the permutation for permute-arguments seems to be a pretty general way to specify arguments by their order in a call (zero-based). Build generalized versions of these procedures that have such an interface. Name them discard-arguments and curryarguments. Make your code compatible with the code in the text: your (curry-arguments 2) should do exactly what (curry-argument 2) does.
|
||
- **b.** What other combinators would you find useful? Make up a list, with appropriate use cases that you might encounter in actual code. Write implementations of them for your library.
|
||
- **c.** Further generalize compose so that it can take any number of functional aguments. The expression (compose f g h) is
|
||
|
||
equivalent to (compose f (compose g h)). Note that it should also be equivalent to (compose (compose f g) h). Be careful: what is the composition of zero arguments?
|
||
|
||
# **2.2 Regular expressions**
|
||
|
||
Regular expressions are widely used for string matching. Although regular-expression systems are derived from a perfectly good mathematical formalism, the particular choices made by implementers to expand the formalism into useful software systems are often disastrous: the quotation conventions adopted are highly irregular; the egregious misuse of parentheses, both for grouping and for backward reference, is a miracle to behold. In addition, attempts to increase the expressive power and address shortcomings of earlier designs have led to a proliferation of incompatible derivative languages.
|
||
|
||
On the surface, regular expressions look like a combinator language, because expression fragments can be combined to make more complex expressions. But the meaning of a fragment is highly dependent on the expression it is embedded in. For example, if we want a caret, ∧, in a bracket expression, [...], the caret must not be in the first character position, because if the caret appears after the first character it is just an ordinary character, but if it appears as the first character it negates the meaning of the bracket expression. Thus a bracket expression may not contain just a caret.
|
||
|
||
So the syntax of the regular-expression language is awful; there are various incompatible forms of the language; and the quotation conventions are *baroquen* [sic]. While regular expression languages are domain-specific languages, they are bad ones. Part of the value of examining regular expressions is to experience how bad things can be.
|
||
|
||
Nevertheless, there is a great deal of useful software, for example grep, that uses regular expressions to specify the desired behavior. We will invent a better domain-specific combinator language for
|
||
|
||
specifying regular expressions and a means of translating this language to conventional regular-expression syntax. We will use the POSIX Basic Regular Expression (BRE) syntax as a target for our translator [96], since it is a subset of most other regular-expression syntaxes. POSIX also defines a more powerful Extended Regular Expression (ERE) syntax, which we will consider in an exercise.
|
||
|
||
With this machinery we will be able to use the capabilities of systems like grep from inside the Scheme environment. We will have all the advantages of a combinator language. It will have a clean, modular description while retaining the ability to use existing tools. Users of this language will have nothing to *grep* about, unless they value concise expression over readability.
|
||
|
||
As with any language there are primitives, means of combination, and means of abstraction. Our language allows the construction of patterns that utilities like grep can match against character-string data. Because this language is embedded in Scheme, we inherit Scheme's power: we can use Scheme constructs to combine patterns and use Scheme procedures to abstract them.
|
||
|
||
### **2.2.1 A regular expression combinator language**
|
||
|
||
Patterns are built out of these primitive patterns:
|
||
|
||
```
|
||
(r:dot) matches any character except newline
|
||
(r:bol) matches only the beginning of a line
|
||
(r:eol) matches only the end of a line
|
||
(r:quote string) matches the string
|
||
(r:char-from string) matches one character that is in the string
|
||
(r:char-not-from string) matches one character that is not in
|
||
the string
|
||
```
|
||
|
||
Patterns can be combined to make compound patterns:
|
||
|
||
```
|
||
(r:seq pattern ...)
|
||
```
|
||
|
||
This pattern matches each argument *pattern* in sequence, from left to right.
|
||
|
||
```
|
||
(r:alt pattern ...)
|
||
```
|
||
|
||
This pattern tries each argument *pattern* from left to right, until one of these alternatives matches. If none matches then this pattern does not match.
|
||
|
||
```
|
||
(r:repeat min max pattern)
|
||
```
|
||
|
||
This pattern tries to match the argument *pattern* a minimum of *min* times but no more than a maximum of *max* times. If *max* is given as #f then no maximum is specified. If *max* equals *min* the given pattern must be matched exactly that many times.
|
||
|
||
Here are some example patterns:
|
||
|
||
```
|
||
(r:seq (r:quote "a") (r:dot) (r:quote "c"))
|
||
matches any three-character string beginning with a and ending
|
||
with c. For example, it will match abc and aac and acc.
|
||
```
|
||
|
||
```
|
||
(r:alt (r:quote "foo") (r:quote "bar") (r:quote "baz"))
|
||
matches either foo, bar, or baz.
|
||
```
|
||
|
||
```
|
||
(r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
|
||
matches catdogcat and catcatdogdog and dogdogcatdogdog but
|
||
not catcatcatdogdogdog.
|
||
```
|
||
|
||
We will implement patterns as Scheme expressions. Thus we can freely mix them with any Scheme code, giving us all the power of the programming language.
|
||
|
||
# **2.2.2 Implementation of the translator**
|
||
|
||
Let's look at how this language is implemented. Regular expressions will be represented as strings in the POSIX Basic Regular Expression syntax.
|
||
|
||
```
|
||
(define (r:dot) ".")
|
||
(define (r:bol) "∧")
|
||
(define (r:eol) "$")
|
||
```
|
||
|
||
These directly correspond to regular-expression syntax.
|
||
|
||
Next, r:seq implements a way to treat a given set of regularexpression fragments as a self-contained element:
|
||
|
||
```
|
||
(define (r:seq . exprs)
|
||
(string-append "\\(" (apply string-append exprs) "\\)"))
|
||
```
|
||
|
||
The use of parentheses in the result isolates the content of the given expression fragments from the surrounding context. Unfortunately, the use of \ in the translated output is necessary. In basic regular expressions, the parenthesis characters are treated as self-quoting characters. Here we need them to act as grouping operations, which is done by preceding each with a backslash. Adding insult to injury, when this regular expression is put into a Scheme string, it is necessary to quote each backslash character with *another backslash*. So our example (r:seq (r:quote "a") (r:dot) (r:quote "c")) translates to \(\(a\).\(c\)\), or as a Scheme string "\\(\\(a\\).\\(c\\)\\)". Ugh.
|
||
|
||
The implementation of r:quote is a bit harder. In a regular expression, most characters are self-quoting. However, some characters are regular-expression operators and must be explicitly quoted. We wrap the result using r:seq to guarantee that the quoted string is self-contained.
|
||
|
||
```
|
||
(define (r:quote string)
|
||
(r:seq
|
||
(list->string
|
||
(append-map (lambda (char)
|
||
(if (memv char chars-needing-quoting)
|
||
(list #\\ char)
|
||
(list char)))
|
||
(string->list string)))))
|
||
(define chars-needing-quoting
|
||
'(#\. #\[ #\\ #\∧ #\$ #\*))
|
||
```
|
||
|
||
To implement alternative subexpressions, we interpolate a vertical bar between subexpressions and wrap the result using r:seq:
|
||
|
||
```
|
||
(define (r:alt . exprs)
|
||
(if (pair? exprs)
|
||
(apply r:seq
|
||
(cons (car exprs)
|
||
(append-map (lambda (expr)
|
||
(list "\\|" expr))
|
||
(cdr exprs))))
|
||
(r:seq)))
|
||
```
|
||
|
||
(r:alt (r:quote "foo") (r:quote "bar") (r:quote "baz")) translates to \(\(foo\)\|\(bar\)\|\(baz\)\). In addition to quoting the parenthesis characters, we must also quote the vertical bar character, which is otherwise a self-quoting character in this syntax. Note that alternative expressions, unlike the rest of the regular expressions supported here, are not supported by BRE syntax: they are an extension defined by GNU grep that is supported by many implementations. (Alternatives *are* supported by ERE syntax.)
|
||
|
||
It is straightforward to implement repetition by using copies of the given regular expression:
|
||
|
||
```
|
||
(define (r:repeat min max expr)
|
||
(apply r:seq
|
||
(append (make-list min expr)
|
||
(cond ((not max) (list expr "*"))
|
||
((= max min) '())
|
||
(else
|
||
(make-list (- max min)
|
||
(r:alt expr "")))))))
|
||
```
|
||
|
||
<span id="page-23-0"></span>This makes min copies of expr, followed by (- max min) optional copies, where each optional copy is an alternative of the expression and an empty expression. If there is no maximum, [9](#page-54-0) the expression is followed by an asterisk to match any number of times. So (r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog"))) translates to something large that might cause seizures in the reader.
|
||
|
||
The implementation of r:char-from and r:char-not-from is complicated by the need for baroque quotation. This is best organized in two parts, the first to handle the differences between them, and the second for the quotation handling that they have in common:
|
||
|
||
```
|
||
(define (r:char-from string)
|
||
(case (string-length string)
|
||
((0) (r:seq))
|
||
((1) (r:quote string))
|
||
(else
|
||
(bracket string
|
||
(lambda (members)
|
||
(if (lset= eqv? '(#\- #\∧) members)
|
||
'(#\- #\∧)
|
||
(quote-bracketed-contents members)))))))
|
||
(define (r:char-not-from string)
|
||
(bracket string
|
||
(lambda (members)
|
||
(cons #\∧ (quote-bracketed-contents members)))))
|
||
(define (bracket string procedure)
|
||
(list->string
|
||
(append '(#\[)
|
||
(procedure (string->list string))
|
||
'(#\]))))
|
||
```
|
||
|
||
The special cases for r:char-from handle empty and singleton sets of characters specially, which simplifies the general case. There is also a special case for a set containing only caret and hyphen. But r:char-not-from has no such special cases.
|
||
|
||
The general case handles the quotation of the three characters that have special meaning inside a bracket by placing them in positions where they are not operators. (We told you this was ugly!)
|
||
|
||
```
|
||
(define (quote-bracketed-contents members)
|
||
(define (optional char)
|
||
(if (memv char members) (list char) '()))
|
||
(append (optional #\])
|
||
(remove
|
||
(lambda (c)
|
||
(memv c chars-needing-quoting-in-brackets))
|
||
members)
|
||
```
|
||
|
||
```
|
||
(optional #\∧)
|
||
(optional #\-)))
|
||
(define chars-needing-quoting-in-brackets
|
||
'(#\] #\∧ #\-))
|
||
```
|
||
|
||
In order to test this code, we can print the corresponding grep command and use cut and paste to run it in a shell. Because different shells use different quoting conventions, we need to not only quote the regular expression, but also choose which shell to use. The Bourne shell is ubiquitous, and has a relatively simple quoting convention.
|
||
|
||
```
|
||
(define (write-bourne-shell-grep-command expr filename)
|
||
(display (bourne-shell-grep-command-string expr filename)))
|
||
(define (bourne-shell-grep-command-string expr filename)
|
||
(string-append "grep -e "
|
||
(bourne-shell-quote-string expr)
|
||
" "
|
||
filename))
|
||
```
|
||
|
||
The Bourne quoting convention uses single-quote characters surrounding a string, which quotes anything in the string other than a single-quote, which ends the quoted string. So, to quote a singlequote character, we must end the string, quote the single quote explicitly using backslash, and then start another quoted string. The shell interprets this concatenation as a single token. (Are we having fun yet?)
|
||
|
||
```
|
||
(define (bourne-shell-quote-string string)
|
||
(list->string
|
||
(append (list #\')
|
||
(append-map (lambda (char)
|
||
(if (char=? char #\')
|
||
(list #\' #\\ char #\')
|
||
(list char)))
|
||
(string->list string))
|
||
(list #\'))))
|
||
```
|
||
|
||
### **The moral of this story**
|
||
|
||
Our translator is very complicated because most regular expressions are not composable to make larger regular expressions unless extreme measures are taken to isolate the parts. Our translator does this work, but consequently the regular expressions that it generates have much unnecessary boilerplate. Humans don't write regular expressions this way, because they use boilerplate only where necessary—but they often miss instances where it is necessary, causing hard-to-find bugs.
|
||
|
||
The moral of this story is that regular expressions are a beautiful example of how *not* to build a system. Using composable parts and combinators to make new parts by combining others leads to simpler and more robust implementations.
|
||
|
||
# **Exercise 2.6: Adding \* and + to regular expressions**
|
||
|
||
In the traditional regular expression language the asterisk (\*) operator following a subpattern means zero or more copies of the subpattern. A common extension to the language adds the plus-sign (+) operator. A plus sign following a subpattern means one or more copies of the subpattern.
|
||
|
||
Define Scheme procedures r:\* and r:+ to take a pattern and iterate it as necessary. This can be done in terms of r:repeat.
|
||
|
||
Demonstrate your procedures on real data in complex patterns.
|
||
|
||
# **Exercise 2.7: A bug, one bad joke, two tweaks, and a revelation**
|
||
|
||
Ben Bitdiddle has noticed a problem with our implementation of (r:repeat *min max expr*).
|
||
|
||
The use of (r:alt expr "") at the end of the r:repeat procedure is a bit dodgy. This code fragment translates to \(*expr*\|\), where *expr* is the value of expr. This relies on the fact that alternation with something and nothing is the equivalent of saying "one or none." (We will omit the required but confusing backslashes
|
||
|
||
in the rest of this explanation.) That is: (*expr*|) denotes one or no instances of *expr*. Unfortunately, this depends on an undocumented GNU extension to the formal POSIX standard for REs.
|
||
|
||
<span id="page-27-0"></span>Specifically, section 9.4.3 of the POSIX standard [10](#page-54-1) states that a vertical line appearing immediately before a close parenthesis (or immediately after an open parenthesis) produces undefined behavior. In essence, an RE must not be a null sequence.
|
||
|
||
GNU grep just happens to "do the right thing" when presented with (*x*|). Not all grep implementations are as tolerant.
|
||
|
||
Therefore, Ben asks his team of three code hackers (Louis, Alyssa, and Eva) to propose alternative workarounds. Ultimately, he proposes his own patch, which you will implement.
|
||
|
||
- Louis Reasoner suggests that a simple, elegant fix would be to replace the code fragment (r:alt expr "") with a straightforward call to (r:repeat 0 1 expr).
|
||
- Alyssa P. Hacker proposes to rewrite the else clause of r:repeat to translate (r:repeat 3 5 *x*) into the equivalent of (*xxx*|*xxxx*|*xxxxx*) instead of the naughty *xxx*(*x*|)(*x*|) non-POSIXcompliant undefined regular expression that our code produces. She refers to section 9.4.7 of the POSIX regular expression documentation. [11](#page-54-2)
|
||
- <span id="page-27-2"></span><span id="page-27-1"></span>Eva Lu Ator points to the question mark (?) operator in section 9.4.6.4 [12](#page-54-3) and proposes that a better fix would be to implement an r:? operator and replace (r:alt expr "") with (r:? expr).
|
||
- Meanwhile, Ben looks closely at the RE spec and has a revelation. He proposes that r:repeat be reimplemented to emit Interval Expressions. See section 9.3.6.5 of the POSIX documentation. [13](#page-54-4)
|
||
|
||
<span id="page-27-3"></span>Please try not to get sick.
|
||
|
||
Let's consider each proposal:
|
||
|
||
**a.** Everyone giggles at Louis's silly joke. What's so funny about it? That is, what's wrong with this idea?
|
||
|
||
A one-sentence punchline will do.
|
||
|
||
**b.** What advantages does Eva's proposal have over Alyssa's in terms of both code and data?
|
||
|
||
A concise yet convincing few sentences suffice.
|
||
|
||
**c.** What advantage does Ben's proposal have over all the others? Specifically, ponder which section of the POSIX document he cites versus which sections the others cite, then take a quick peek at exercise 2.10 below and consider the implications. Also, consider the size of the output strings in this new code as well as the overall clarity of the code.
|
||
|
||
Again, a brief sentence or two is sufficient.
|
||
|
||
**d.** Following Ben's proposal, reimplement r:repeat to emit Interval Expressions. Hint: Scheme's number->string procedure should be handy. Caveat: Beware the backslashes.
|
||
|
||
Show the output generated by r:repeat on a few well-chosen sample inputs. Demonstrate your procedure on real data in some complex patterns.
|
||
|
||
## Exercise 2.8: Too much nesting
|
||
|
||
Our program produces excessively nested regular expressions: it makes groups even when they are not necessary. For example, the following simple pattern leads to an overly complex regular expression:
|
||
|
||
```
|
||
(display (r:seq (r:quote "a") (r:dot) (r:quote "c"))) ((a).(c))
|
||
```
|
||
|
||
<span id="page-28-0"></span>Another problem is that BREs may involve back-references. (See section 9.3.6.3 of the POSIX regular expression documentation.<sup>14</sup>) A back-reference refers to a preceding parenthesized subexpression. So it is important that the parenthesized subexpressions be ones explicitly placed by the author of the pattern. (Aargh! This is one of
|
||
|
||
the worst ideas we have ever heard of—grouping, which is necessary for iteration, was confused with naming for later reference!)
|
||
|
||
**To do:** Edit our program to eliminate as much of the unnecessary nesting as you can. Caution: There are subtle cases here that you have to watch out for. What is such a case? Demonstrate your better version of our program and show how it handles the subtleties.
|
||
|
||
Hint: Our program uses strings as its intermediate representation as well as its result. You might consider using a different intermediate representation.
|
||
|
||
## **Exercise 2.9: Back-references**
|
||
|
||
Add a procedure for constructing back-references. (See exercise 2.8.) Have fun getting confused about BREs.
|
||
|
||
## **Exercise 2.10: Standards?**
|
||
|
||
The best thing about standards is that there are so many to choose from.
|
||
|
||
Andrew S. Tannenbaum
|
||
|
||
In addition to Basic Regular Expressions (BREs), there are Extended Regular Expressions (EREs) defined in the POSIX regular expression documentation [96]. Some software, such as egrep, uses this version of regular expressions. Unfortunately EREs are not a conservative extension of BREs: ERE syntax is actually inconsistent with BRE syntax! It is an interesting project to extend our Scheme pattern language so that the target can be either BREs or EREs.
|
||
|
||
**a.** What are the significant differences between BREs and EREs that make this a pain? List the differences that must be addressed.
|
||
|
||
- **b.** How can our translator be factored so that our language can translate into either kind of regular expression, depending on what is needed? How can we maintain the abstract layer that is independent of the target regular expression language? Explain your strategy.
|
||
- **c.** Implement the strategy you devised in part **b**. Demonstrate your work by making sure that you can run egrep as well as grep, with equivalent results in cases that test the differences you found in part **a**.
|
||
|
||
# **2.3 Wrappers**
|
||
|
||
Sometimes we can repurpose an existing program by wrapping it rather than rewriting it. Consider the problem of computing how the radius of a sphere of gas varies with the temperature, keeping the pressure constant. The ideal gas law is
|
||
|
||
$$PV = nRT, (2.1)$$
|
||
|
||
where *P* is the pressure, *V* is the volume, *n* is the amount of the gas, *R* is the gas constant, and *T* is the temperature. So the volume is computed by
|
||
|
||
```
|
||
(define (gas-law-volume pressure temperature amount)
|
||
(/ (* amount gas-constant temperature) pressure))
|
||
(define gas-constant 8.3144621) ;J/(K*mol)
|
||
```
|
||
|
||
and the radius of a sphere is computed by
|
||
|
||
```
|
||
(define (sphere-radius volume)
|
||
(expt (/ volume (* 4/3 pi)) 1/3))
|
||
(define pi (* 4 (atan 1 1)))
|
||
```
|
||
|
||
(Note: 4/3 and 1/3 are rational constants—the slash is not an infix division operator.) The choice of gas constant makes this program use SI units, so the pressure is in newtons per square meter, the temperature is in kelvins, the amount is in moles, the volume is in cubic meters, and the radius is in meters.
|
||
|
||
This looks straightforward, but use of other units can make things complicated. Suppose we want to measure the temperature in degrees Fahrenheit, the pressure in pounds per square inch, and the radius in inches. Determining the correct formula is more complicated than computing the numerical answer. We could modify the simple formula to account for the units, but this obscures the idea of the program and specializes it to the particular problem. Alternatively, we could arrange to have a modular way to convert the units.
|
||
|
||
A unit conversion is a procedure that is linked to its inverse. We can write temperature conversions between conventional units, such as Fahrenheit and Celsius temperatures, and between SI and conventional units.
|
||
|
||
```
|
||
(define fahrenheit-to-celsius
|
||
(make-unit-conversion (lambda (f) (* 5/9 (- f 32)))
|
||
(lambda (c) (+ (* c 9/5) 32))))
|
||
(define celsius-to-kelvin
|
||
(let ((zero-celsius 273.15)) ;kelvins
|
||
(make-unit-conversion (lambda (c) (+ c zero-celsius))
|
||
(lambda (k) (- k zero-celsius)))))
|
||
```
|
||
|
||
We can access the inverse procedure using unit:invert. For example,
|
||
|
||
```
|
||
(fahrenheit-to-celsius -40)
|
||
-40
|
||
(fahrenheit-to-celsius 32)
|
||
0
|
||
((unit:invert fahrenheit-to-celsius) 20)
|
||
68
|
||
```
|
||
|
||
We can compose unit conversions:
|
||
|
||
```
|
||
((compose celsius-to-kelvin fahrenheit-to-celsius) 80)
|
||
299.81666666666666
|
||
```
|
||
|
||
And we can define compound unit conversions. For example, pressure can be expressed in in pounds per square inch or newtons per square meter. [15](#page-54-6)
|
||
|
||
```
|
||
(define psi-to-nsm
|
||
(compose pound-to-newton
|
||
(unit:invert inch-to-meter)
|
||
(unit:invert inch-to-meter)))
|
||
```
|
||
|
||
So now we can compute, in inches, the radius of a sphere occupied by 1 mole of an ideal gas at 68 *◦*F and 14.7 psi.
|
||
|
||
```
|
||
((unit:invert inch-to-meter)
|
||
(sphere-radius
|
||
(gas-law-volume
|
||
(psi-to-nsm 14.7)
|
||
((compose celsius-to-kelvin fahrenheit-to-celsius) 68)
|
||
1)))
|
||
7.049624635839811
|
||
```
|
||
|
||
This is a mess! This implementation of unit conversions, while simple to program, is hard to read and hard to use. On the other hand, it nicely separates several concerns. The physics of the gas law is separated from the geometry of the sphere and the units of measurement. The physical and geometric descriptions are uncluttered and each is easy to read.
|
||
|
||
We can do better. We can build a small domain-specific language, where the domain is units. This will simplify the job of constructing new converters, and make the resulting converters more readable.
|
||
|
||
### **2.3.1 Specialization wrappers**
|
||
|
||
One way to proceed is to make a general family of wrappers that can take a procedure like gas-law-volume and produce a version of that procedure specialized by unit conversions for its output and inputs. Although we will show how to do this for unit conversions, the code will be general enough to build wrappers for arbitrary transformations of data.
|
||
|
||
For the problem at hand we can construct a specializer for the gas-law-volume procedure that knows its native units (SI). The specializer is defined by a simple language that is compiled into the appropriate combinations of primitive unit conversions. This is somewhat like a combinator system except that the combinators are generated by the compiler according to a high-level specification. We will see this technique again in chapter 4, where we use it to compile combinations of pattern-matching procedures from patterns.
|
||
|
||
```
|
||
(define make-specialized-gas-law-volume
|
||
(unit-specializer
|
||
gas-law-volume
|
||
'(expt meter 3) ; output (volume)
|
||
'(/ newton (expt meter 2)) ; pressure
|
||
'kelvin ; temperature
|
||
'mole)) ; amount
|
||
```
|
||
|
||
To make a version of the gas-law-volume procedure that uses other units we supply the units that we want to use:
|
||
|
||
```
|
||
(define conventional-gas-law-volume
|
||
(make-specialized-gas-law-volume
|
||
'(expt inch 3) ; output (volume)
|
||
'(/ pound (expt inch 2)) ; pressure
|
||
'fahrenheit ; temperature
|
||
'mole)) ; amount
|
||
```
|
||
|
||
This procedure can then be used to produce the volume in cubic inches, and therefore we can get the radius in inches.
|
||
|
||
```
|
||
(sphere-radius (conventional-gas-law-volume 14.7 68 1))
|
||
7.04962463583981
|
||
```
|
||
|
||
### **2.3.2 Implementing specializers**
|
||
|
||
How can we make this work? There are two parts: a procedure unit-specializer that wraps a given procedure with the necessary unit conversions, and a means of translating the given unit expressions into the appropriate unit conversion. The first part is
|
||
|
||
```
|
||
(define (unit-specializer procedure implicit-output-unit
|
||
. implicit-input-units)
|
||
(define (specializer specific-output-unit
|
||
. specific-input-units)
|
||
(let ((output-converter
|
||
(make-converter implicit-output-unit
|
||
specific-output-unit))
|
||
(input-converters
|
||
(map make-converter
|
||
specific-input-units
|
||
implicit-input-units)))
|
||
(define (specialized-procedure . arguments)
|
||
(output-converter
|
||
(apply procedure
|
||
(map (lambda (converter argument)
|
||
(converter argument))
|
||
input-converters
|
||
arguments))))
|
||
specialized-procedure))
|
||
specializer)
|
||
```
|
||
|
||
The procedure unit-specializer takes a procedure to be specialized and its implicit native units, and returns a specializer that takes specific units and creates a specialized version of the given procedure. The only tricky part is making sure that unit expressions are passed to make-converter in the correct order.
|
||
|
||
The second part of the solution is make-converter, which takes two unit expressions, and returns a converter procedure that converts data in the first unit to the second unit. For this problem, we will make a version of make-converter that's really dumb: it treats the unit expressions as literal constants that can be compared with equal?. With that simplification, make-converter can use a table lookup to find the appropriate converter, which means we have to explicitly provide every necessary conversion rather than deriving them from primitive unit conversions. Here's an example of how the table is created:
|
||
|
||
```
|
||
(register-unit-conversion 'fahrenheit 'celsius
|
||
fahrenheit-to-celsius)
|
||
(register-unit-conversion 'celsius 'kelvin
|
||
celsius-to-kelvin)
|
||
```
|
||
|
||
This registers the conversions we defined earlier. Once these conversions are registered, we can look up either conversion direction by the order of arguments passed to make-converter.
|
||
|
||
However, what we need isn't either of these conversions, but instead the conversion from fahrenheit to kelvin. Since we don't want to infer this from the existing definitions—an interesting but much more complex implementation—we will have to build compound conversions from the existing ones. To make that easy, we will introduce an "algebra" of unit conversions, as follows:
|
||
|
||
```
|
||
(define (unit:* u1 u2)
|
||
(make-unit-conversion (compose u2 u1)
|
||
(compose (unit:invert u1)
|
||
(unit:invert u2))))
|
||
```
|
||
|
||
The procedure unit:\*, combined with unit:invert, provides us with a general ability to combine unit conversions. For convenience, we will add the following, which are easily derived from unit:\* and unit:invert:
|
||
|
||
```
|
||
(unit:/ u1 u2)
|
||
(unit:expt u n)
|
||
```
|
||
|
||
With this algebra, we can write the conversions we want:
|
||
|
||
```
|
||
(register-unit-conversion 'fahrenheit 'kelvin
|
||
(unit:* fahrenheit-to-celsius celsius-to-kelvin))
|
||
(register-unit-conversion '(/ pound (expt inch 2))
|
||
'(/ newton (expt meter 2))
|
||
(unit:/ pound-to-newton
|
||
(unit:expt inch-to-meter 2)))
|
||
(register-unit-conversion '(expt inch 3) '(expt meter 3)
|
||
(unit:expt inch-to-meter 3))
|
||
```
|
||
|
||
### **2.3.2 Adapters**
|
||
|
||
What we have shown here is one possible technique for taking an existing program and broadening its applicability without changing the original program. The resulting "adapter" mechanism is itself
|
||
|
||
extensible and can be used to generalize many other kinds of programs.
|
||
|
||
This is an important principle: rather than rewriting a program to adapt it to a new purpose, it's preferable to start with a simple and general base program and wrap it to specialize it for a particular purpose. The program doesn't know anything about the wrappers, and the wrappers make few assumptions about the underlying program. And the unit-specializer procedure knows very little about either. Because these parts are so loosely coupled, they can each be generalized for many purposes, including those we aren't thinking about here. This is a kind of layering strategy, which we will expand upon in chapter 6.
|
||
|
||
# **Exercise 2.11: Implementing unit conversions**
|
||
|
||
Here we ask you to fill in the details that make this system work.
|
||
|
||
- **a.** As a warmup, write the procedures register-unitconversion, and make-converter.
|
||
- **b.** Write the procedures unit:/ and unit:expt.
|
||
- **c.** Fill out a library of conversions for conventional units to SI units. This requires conversions for mass and length. (Time is in seconds in both systems. However, you may be interested in minutes, hours, days, weeks, years, etc. Don't get stuck trying to make this universal.)
|
||
- **d.** Make some useful compounds, like velocity and acceleration.
|
||
- **e.** For a real project, extend this specializer system for some other data conversion of some other program, having nothing to do with units.
|
||
- **f.** Another big extension is to build make-converter so that it can derive compound conversions, as required, from previously registered conversions. This will require a graph search.
|
||
|
||
## **2.4 Abstracting a domain**
|
||
|
||
Let's look at how a domain-specific language layer can be created as a basis for software about board games. There are many common features of board games; each game combines some of those features. A *domain model* can be built that captures the common structure of a class of board games, in terms of the abstract concepts that describe board games, such as pieces, potential locations, and primitive behaviors such as moving and capturing.
|
||
|
||
A particular board game program may be constructed entirely in terms of the domain model. If the domain model is sufficiently general, it will support future variation without change to the model itself.
|
||
|
||
Let's consider board games such as chess and checkers. They are both two-person games played on a board that is a rectangular grid. The players have pieces that are arrayed on the board. There is never more than one piece at any position on the board. The players alternate moves. On each move a player chooses a piece and moves it to some other location on the board. Sometimes an opponent's piece is captured. This is an informal description of a domain model for a class of board games.
|
||
|
||
Based on this kind of domain model we will construct a *referee* for checkers that will compute all legal moves for a player at a given state of play. The domain model's implementation is fairly complex, providing implementations of pieces, coordinates, and the board. In order to simplify our presentation we will restrict ourselves to just what is needed by the referee.
|
||
|
||
The general organization of the referee is that it will generate all the legal moves for each piece separately and then aggregate them. In order to do this, it's helpful to have an abstraction that keeps track of the effects of moving a piece. For example, one effect might change a piece's position, another might change its type (e.g., "kinging" in checkers), and yet another might capture an opponent's
|
||
|
||
piece. Each legal move consists of a sequence of such changes applied to the initial state of the move.
|
||
|
||
A good program must be written many times. This is true of the programs we show. The first draft may not clearly separate out the concerns, but by making that draft the programmer learns the structure of the problem. We will show two different implementations, which will reveal the evolution of the program as we identify shortcomings in our draft.
|
||
|
||
### **2.4.1 A monolithic implementation**
|
||
|
||
Let's start with a simple version of the referee that one might write to understand what really has to be done.
|
||
|
||
### **A checkers domain model**
|
||
|
||
The first implementation will be built on a domain model that is specific to checkers and fairly simple. In the later implementation we will abstract away the checkers-specific parts and hide many of the details of the domain model. The final domain model will support other similar board games, and perhaps other domains.
|
||
|
||
The domain model we will use has three abstract types. A *board* tracks the live pieces and the color of the player to move next (the *current* player). It can be asked what piece, if any, is in a particular position. A *piece* has a color, a position, and whether it is a king. A *position* is specified by *coordinates* that are relative to the player to move. Here are the operations on boards:
|
||
|
||
```
|
||
(current-pieces board)
|
||
gets a list of the pieces belonging to the current player.
|
||
```
|
||
|
||
```
|
||
(is-position-on-board? coords board)
|
||
```
|
||
|
||
tests whether the given *coords* specify a position on *board*. Coordinates that do not satisfy this predicate will cause errors when used with other operations.
|
||
|
||
```
|
||
(board-get coords board)
|
||
```
|
||
|
||
gets the piece that is at the position specified by *coords*. If there is no piece in that position it returns #f.
|
||
|
||
```
|
||
(position-info coords board)
|
||
```
|
||
|
||
describes what occupies the position *coords* in *board*. If the position is empty the value is unoccupied; if it contains one of the current player's pieces the value is occupied-by-self; if it contains an opponent's piece the value is occupied-by-opponent.
|
||
|
||
```
|
||
(is-position-unoccupied? coords board)
|
||
is equivalent to position-info returning unoccupied.
|
||
```
|
||
|
||
```
|
||
(is-position-occupied-by-self? coords board)
|
||
is equivalent to position-info returning occupied-by-self.
|
||
```
|
||
|
||
```
|
||
(is-position-occupied-by-opponent? coords board)
|
||
is equivalent to position-info returning occupied-by-opponent.
|
||
```
|
||
|
||
There is a similarly small set of operations on pieces:
|
||
|
||
```
|
||
(piece-coords piece)
|
||
gets the coordinates of piece.
|
||
```
|
||
|
||
```
|
||
(should-be-crowned? piece)
|
||
```
|
||
|
||
tests whether *piece* should be crowned—specifically, if it is not already a king and is on the opponent's home row.
|
||
|
||
```
|
||
(crown-piece piece)
|
||
```
|
||
|
||
gets a new piece identical to *piece* except that it is a king.
|
||
|
||
```
|
||
(possible-directions piece)
|
||
```
|
||
|
||
gets a list of directions that *piece* may consider for a move. This does not take into account whether moving in that direction is permissible.
|
||
|
||
The coordinate system is simple: just row and column integers. When we refer to *coordinates* or *coords*, we mean absolute
|
||
|
||
coordinates on the board. We use the term *offset* for relative coordinates. An offset can be added to some coordinates to produce new coordinates, or inversely two coordinates can be subtracted to produce an offset. A *direction* is an offset in which the row and column are 0, 1, or −1; For checkers, the possible directions are the two forward diagonals, with the row 1 and the column either −1 or 1. Once a piece becomes a king, it can additionally use the backward diagonals, with row −1. In chess, the possible moves use additional directions, depending on the piece, while a knight move needs a more complex definition. We won't define the procedures for manipulating coordinates; they should be self-explanatory.
|
||
|
||
### **A checkers referee**
|
||
|
||
(step-to *step*)
|
||
|
||
We need a data structure to represent each move. Since any given move may require changing a piece's position multiple times, we will use a list of *step* objects, each of which specifies the piece prior to the step, the piece after the step, the board after the step, and whether the step is a jump. Such a list, which we will call a *path*, is ordered from newest step to oldest. This ordering facilitates sharing of common subpaths that may occur when a move can be continued in multiple ways.
|
||
|
||
```
|
||
gets the piece after step is taken.
|
||
(step-board step)
|
||
gets the board after step is taken.
|
||
(make-simple-move new-coords piece board)
|
||
gets a step that moves piece to new-coords on board.
|
||
```
|
||
|
||
(make-jump *new-coords jumped-coords piece board*) gets a step that moves *piece* to *new-coords* on *board* and removes the opponent's piece at *jumped-coords*.
|
||
|
||
(replace-piece *new-piece old-piece board*) gets a step that replaces *old-piece* with *new-piece* on *board*.
|
||
|
||
```
|
||
(path-contains-jumps? path)
|
||
tests whether any of the steps in path are jumps.
|
||
```
|
||
|
||
Let's build our referee. We will start by describing what simple steps are possible from a given starting point in a given direction. The try-step procedure identifies a potential next step, augmenting the given path. If there is no such step, it returns #f.
|
||
|
||
```
|
||
(define (try-step piece board direction path)
|
||
(let ((new-coords
|
||
(coords+ (piece-coords piece) direction)))
|
||
(and (is-position-on-board? new-coords board)
|
||
(case (position-info new-coords board)
|
||
((unoccupied)
|
||
(and (not (path-contains-jumps? path))
|
||
(cons (make-simple-move new-coords
|
||
piece
|
||
board)
|
||
path)))
|
||
((occupied-by-opponent)
|
||
(let ((landing (coords+ new-coords direction)))
|
||
(and (is-position-on-board? landing board)
|
||
(is-position-unoccupied? landing board)
|
||
(cons (make-jump landing
|
||
new-coords
|
||
piece
|
||
board)
|
||
path))))
|
||
((occupied-by-self) #f)
|
||
(else (error "Unknown position info"))))))
|
||
```
|
||
|
||
The procedure looks at the position one step along the given direction; if it's unoccupied, then it's possible to move there. (We explicitly test whether this is a continuation of a jump, as that is not allowed in checkers.) If the position is occupied by one of the player's pieces, no move is possible. But if the position is occupied by an opponent's piece, and the next position in that direction is unoccupied, then we can jump over the opponent's piece and capture it.
|
||
|
||
We must try each possible direction for the piece. The procedure compute-next-steps returns a list of possible next paths by augmenting an existing path by one step.
|
||
|
||
```
|
||
(define (compute-next-steps piece board path)
|
||
;; filter-map drops false values
|
||
(filter-map (lambda (direction)
|
||
(try-step piece board direction path))
|
||
(possible-directions piece)))
|
||
```
|
||
|
||
The rules of checkers mandate choosing a jump when one or more is possible:
|
||
|
||
```
|
||
(define (evolve-paths piece board)
|
||
(let ((paths (compute-next-steps piece board '())))
|
||
(let ((jumps (filter path-contains-jumps? paths)))
|
||
(if (null? jumps)
|
||
paths
|
||
(evolve-jumps jumps)))))
|
||
```
|
||
|
||
And after an initial jump, we must test for other possible jumps:
|
||
|
||
```
|
||
(define (evolve-jumps paths)
|
||
(append-map (lambda (path)
|
||
(let ((paths
|
||
(let ((step (car path)))
|
||
(compute-next-steps (step-to step)
|
||
(step-board
|
||
step)
|
||
path))))
|
||
(if (null? paths)
|
||
(list path)
|
||
;; continue jumping if possible
|
||
(evolve-jumps paths))))
|
||
paths))
|
||
```
|
||
|
||
That is the logic for generating the moves for a single piece. The referee must do this for every piece and aggregate the results:
|
||
|
||
```
|
||
(define (generate-moves board)
|
||
(crown-kings
|
||
(mandate-jumps
|
||
(append-map (lambda (piece)
|
||
(evolve-paths piece board))
|
||
(current-pieces board)))))
|
||
```
|
||
|
||
This procedure does two things in addition to generating the moves. First, the aggregated moves may contain jumps for some pieces and ordinary moves for others, in which case only the jumps are legal moves.
|
||
|
||
```
|
||
(define (mandate-jumps paths)
|
||
(let ((jumps (filter path-contains-jumps? paths)))
|
||
(if (null? jumps)
|
||
paths
|
||
jumps)))
|
||
```
|
||
|
||
Second, if any piece reaches the opponent's home row, it must be made a king.
|
||
|
||
```
|
||
(define (crown-kings paths)
|
||
(map (lambda (path)
|
||
(let ((piece (step-to (car path))))
|
||
(if (should-be-crowned? piece)
|
||
(cons (replace-piece (crown-piece piece)
|
||
piece
|
||
(step-board (car path)))
|
||
path)
|
||
path)))
|
||
paths))
|
||
```
|
||
|
||
### **Critique**
|
||
|
||
This code is quite nice; it is surprisingly compact, and it is written in terms of the domain model. However, the rules of checkers are distributed throughout the code. The availability of a jump is discovered in the procedure try-step, but the fact that jumps may chain is in evolve-jumps. Also, the rule that if a jump is available a jump must be taken is split between the procedures evolve-paths and mandate-jumps. A more subtle problem is that the control structure of the referee is interwoven with the rules. For example, the accumulation of changes (steps in the path) is built into the control structure, as is chaining of a multiple jump. The reason why the logic for mandating jumps is in two places is that it is required by the distribution of the control structure.
|
||
|
||
### **2.4.2 Factoring out the domain**
|
||
|
||
Let's try to ameliorate the problems noted in the previous implementation. Can we separate the domain model and control structure from the rules of checkers?
|
||
|
||
### **A domain model**
|
||
|
||
We can reuse the coordinates, pieces, and board from our monolithic implementation, since they are largely unchanged. However, we will eliminate the specific idea of king and non-king pieces, instead using a symbolic type. This introduces two new operations:
|
||
|
||
```
|
||
(piece-type piece)
|
||
gets the type of piece.
|
||
```
|
||
|
||
```
|
||
(piece-new-type piece type)
|
||
```
|
||
|
||
gets a new piece identical to *piece* except that it has the given *type*.
|
||
|
||
We redefine should-be-crowned? and crown-piece to use the piece type, so they behave the same as before, but they are no longer part of the core domain model.
|
||
|
||
Although the procedure possible-directions is specific to checkers, we will use it here, but only when defining the rules of checkers. It is not part of the new domain model.
|
||
|
||
The step data structure is also specific to checkers, because it specifies whether a step is a jump. We will replace it with a more general structure called a *change*:
|
||
|
||
```
|
||
(make-change board piece flags)
|
||
```
|
||
|
||
creates a new change object. The *flags* argument is a list of symbols that we can use to indicate changes of state such as capture of a piece. The selectors get-board, get-piece, and get-flags can be used to get the corresponding parts of a change.
|
||
|
||
Like the piece type, the change flags provide a way to add gamespecific features to the domain model without baking them in.
|
||
|
||
We will replace the path idea with a more abstract notion called a *partial move*. A partial move consists of an initial board and piece, together with zero or more changes. Our code uses the identifier pmove for a partial move.
|
||
|
||
```
|
||
(initial-pmove board piece)
|
||
creates a pmove with no changes and no flags.
|
||
```
|
||
|
||
```
|
||
(is-pmove-empty? pmove)
|
||
tests whether pmove is empty: in other words, if it has no changes.
|
||
```
|
||
|
||
```
|
||
(is-pmove-finished? pmove)
|
||
tests whether pmove has been flagged as finished.
|
||
```
|
||
|
||
```
|
||
(current-board pmove)
|
||
```
|
||
|
||
returns the board from the most recent change in *pmove*; if there are no changes, it returns the board passed as an argument to initial-pmove.
|
||
|
||
```
|
||
(current-piece pmove)
|
||
```
|
||
|
||
returns the piece from the most recent change in the *pmove*; if there are no changes, it returns the piece passed as an argument to initial-pmove.
|
||
|
||
The next operations extend a pmove in different ways. When we say "extends *pmove* by *foo*" we mean "extends *pmove* by adding a change object that does *foo*."
|
||
|
||
```
|
||
(new-piece-position coords pmove)
|
||
extends pmove by moving its piece to coords.
|
||
```
|
||
|
||
```
|
||
(update-piece procedure pmove)
|
||
```
|
||
|
||
extends *pmove* by replacing its piece with the result of calling *procedure* on its piece.
|
||
|
||
```
|
||
(finish-move pmove)
|
||
```
|
||
|
||
extends *pmove* by adding a change object with a flag that specifies that the move is complete. The result always satisfies the predicate is-pmove-finished?.
|
||
|
||
In the implementation of section 2.4.1, we used the terms *jumping* and *capturing* interchangeably. But capturing is a more general idea: for example, in chess, capturing is done by displacing a piece rather than jumping over it. We use a change flag to encode the act of capturing a piece, and the following procedures to manage that flag:
|
||
|
||
```
|
||
(captures-pieces? pmove)
|
||
tests whether any pieces are captured by pmove.
|
||
```
|
||
|
||
```
|
||
(capture-piece-at coords pmove)
|
||
```
|
||
|
||
extends *pmove* by removing the piece at *coords*. The position specified by *coords* must contain an opponent's piece. The operation also sets a flag in the new change object saying that a piece was captured; the resulting pmove always satisfies captures-pieces?.
|
||
|
||
### **An executive**
|
||
|
||
To help separate the control structure from the rules of checkers we build a rule executive that captures the control structure without incorporating the specific content of the rules. In this kind of game there are two kinds of rule. One kind, which we will call an *evolution rule*, augments a pmove, possibly returning multiple derived pmoves. The other kind, an *aggregate rule*, acts on a set of pmoves, eliminating some that are not allowed or extending some to incorporate changes, such as crowning a king.
|
||
|
||
Here is an executive that starts with some empty pmoves, one for each of the player's pieces, and evolves these into a collection of pmoves that represent finished moves. It then applies the aggregate rules to the collection of finished pmoves, ultimately returning a collection of the legal moves.
|
||
|
||
An evolution rule is implemented as a procedure that transforms a given pmove into a collection of new pmoves, some of which may be finished (satisfy is-pmove-finished?). The executive recursively applies all of the evolution rules to the collection of pmoves until all of them are finished.
|
||
|
||
An aggregate rule is implemented as a procedure that accepts a collection of finished pmoves and produces a new collection. Each aggregate rule is applied once, and there are no ordering constraints between aggregate rules, so the executive can compose them together into a single procedure that is the composite aggregate rule. If there are no aggregate rules, then the composite simply returns its argument.
|
||
|
||
```
|
||
(define (execute-rules initial-pmoves evolution-rules
|
||
aggregate-rules)
|
||
((reduce compose (lambda (x) x) aggregate-rules)
|
||
(append-map (lambda (pmove)
|
||
(evolve-pmove pmove evolution-rules))
|
||
initial-pmoves)))
|
||
(define (evolve-pmove pmove evolution-rules)
|
||
(append-map (lambda (new-pmove)
|
||
(if (is-pmove-finished? new-pmove)
|
||
(list new-pmove)
|
||
(evolve-pmove new-pmove evolution-
|
||
rules)))
|
||
(append-map (lambda (evolution-rule)
|
||
(evolution-rule pmove))
|
||
evolution-rules)))
|
||
```
|
||
|
||
An evolution rule is registered for use in the executive by the procedure define-evolution-rule and an aggregate rule is registered by the procedure define-aggregate-rule. Each rule has a name, the game that it is registered in, and a procedure implementing its behavior.
|
||
|
||
### **Rules of checkers**
|
||
|
||
Here is a rule for simple moves. This looks for any unoccupied adjacent position in a possible direction, and extends the pmove to
|
||
|
||
include a move to that position. After such a move, it is not legal to continue moving, so we mark that pmove as finished.
|
||
|
||
```
|
||
(define-evolution-rule 'simple-move checkers
|
||
(lambda (pmove)
|
||
(if (is-pmove-empty? pmove)
|
||
(get-simple-moves pmove)
|
||
'())))
|
||
(define (get-simple-moves pmove)
|
||
(filter-map
|
||
(lambda (direction)
|
||
(let ((landing (compute-new-position direction 1 pmove))
|
||
(board (current-board pmove)))
|
||
(and (is-position-on-board? landing board)
|
||
(is-position-unoccupied? landing board)
|
||
(finish-move (new-piece-position landing
|
||
pmove)))))
|
||
(possible-directions (current-piece pmove))))
|
||
```
|
||
|
||
In get-simple-moves, the procedure compute-new-position gets the proposed landing site of the piece possibly being moved, given the direction and distance for the move. The procedure offset\* multiplies an offset and a number to get a new offset scaled by the number.
|
||
|
||
```
|
||
(define (compute-new-position direction distance pmove)
|
||
(coords+ (piece-coords (current-piece pmove))
|
||
(offset* direction distance)))
|
||
```
|
||
|
||
The rule for jumps is similar, except that it must look for an occupied position followed by an unoccupied position in a given direction. When no jumps are possible, a pmove is finished.
|
||
|
||
```
|
||
(define-evolution-rule 'jump checkers
|
||
(lambda (pmove)
|
||
(let ((jumps (get-jumps pmove)))
|
||
(cond ((not (null? jumps))
|
||
jumps)
|
||
((is-pmove-empty? pmove)
|
||
'()) ; abandon this pmove
|
||
(else
|
||
(list (finish-move pmove)))))))
|
||
(define (get-jumps pmove)
|
||
```
|
||
|
||
```
|
||
(filter-map
|
||
(lambda (direction)
|
||
(let ((possible-jump
|
||
(compute-new-position direction 1 pmove))
|
||
(landing (compute-new-position direction 2 pmove))
|
||
(board (current-board pmove)))
|
||
(and (is-position-on-board? landing board)
|
||
(is-position-unoccupied? landing board)
|
||
(is-position-occupied-by-opponent? possible-jump
|
||
board)
|
||
(capture-piece-at possible-jump
|
||
(new-piece-position landing
|
||
pmove)))))
|
||
(possible-directions (current-piece pmove))))
|
||
```
|
||
|
||
Making kings is independent of other rules: just look at all the completed moves and crown any non-king that is on the opponent's home row.
|
||
|
||
```
|
||
(define-aggregate-rule 'coronation checkers
|
||
(lambda (pmoves)
|
||
(map (lambda (pmove)
|
||
(let ((piece (current-piece pmove)))
|
||
(if (should-be-crowned? piece)
|
||
(update-piece crown-piece pmove)
|
||
pmove)))
|
||
pmoves)))
|
||
```
|
||
|
||
And finally, the rule mandating that a jump be taken when one or more is available is done at the end by detecting that case and throwing away all the non-jump moves.
|
||
|
||
```
|
||
(define-aggregate-rule 'require-jumps checkers
|
||
(lambda (pmoves)
|
||
(let ((jumps (filter captures-pieces? pmoves)))
|
||
(if (null? jumps)
|
||
pmoves
|
||
jumps))))
|
||
```
|
||
|
||
### **Critique**
|
||
|
||
The rule-based implementation of our referee solves the problems we identified earlier. It removes the control structure from our program and localizes it in the executive. As a consequence, the
|
||
|
||
rules are specific: each checkers rule is expressed by a single procedural rule. The rules are not diffused as they were in the earlier implementation.
|
||
|
||
<span id="page-50-0"></span>However, this comes at a cost: we must add applicability conditions to each rule to prevent it being applied to pmoves for which it is inappropriate. [16](#page-54-7) For example, the simple-move rule must exclude any nonempty pmoves that it is given, because a nonempty pmove might include one or more jumps, which cannot be continued with a simple move. This is a general mis-feature of rule-based systems: every rule must be able to accept the output of any rule; this is normally handled by encoding the control state in the data the rules are applied to.
|
||
|
||
## **Exercise 2.12: A bit of chess**
|
||
|
||
Using the same domain model we used for checkers, it is possible to capture the rules of chess. There are several important differences, besides the fact that chess involves many types of pieces. One difference is that the range of motion of rooks, bishops, and queens is limited only by obstruction. Another difference is that capture is by displacement rather than jump. In this exercise we will consider only rooks and knights; the remaining pieces are addressed in exercise 2.13.
|
||
|
||
- **a.** Construct an analogous referee to generate the legal moves for a rook. Don't try to implement the castling rule.
|
||
- **b.** Augment your referee to model the behavior of a knight.
|
||
|
||
# **Exercise 2.13: More chess**
|
||
|
||
Make a full implementation of the rules of chess.
|
||
|
||
# **Exercise 2.14: An advanced project**
|
||
|
||
Choose some other domain, not a board game, and build an implementation of the rules of some process using the rule executive and a domain model of your design. This is not easy.
|
||
|
||
# **2.5 Summary**
|
||
|
||
The techniques displayed and elaborated on in this chapter can be helpful in the design and development of every large-scale system. It is almost always to our advantage to build our systems using mixand-match interchangeable parts with well-defined interfaces.
|
||
|
||
In languages with higher-order procedures and lexical scoping, like Scheme or Java, it is easy to make systems of combinators standard means of combination, such as compose—for a library of interchangeable parts. And it is convenient to make parametric parts that share a common interface specification. For example, if our interface specification is procedures that take one argument and return one value, then
|
||
|
||
```
|
||
(define (make-incrementer dx)
|
||
(lambda (x) (+ x dx)))
|
||
```
|
||
|
||
defines a set of interchangeable incrementers. It is much harder to make systems of combinators and libraries of combinable parts with languages like C that do not have lexically scoped higher-order procedures. But with careful planning and some effort it can be done.
|
||
|
||
When we are confronted with a system based on parts that do not compose cleanly, such as regular expressions, it is often possible to ameliorate the difficulties by metaprogramming. In that case we built a new combinator-based language that we compiled to the regular expression language, making a pleasant but longwinded alternative. Our regular-expressions combinator language is a fine
|
||
|
||
domain-specific intermediate language for programs that need to match strings, but it is not so nice as a scripting language for a user to type. For that purpose we would want to design a clean and more concise syntax for matching strings that can be compiled to a combinator-based intermediate language. [17](#page-54-8)
|
||
|
||
<span id="page-52-0"></span>Wrappers are a common strategy for making old code useful in a new context. We showed how programs that assumed a particular unit system could be used with other unit systems, by building a system of wrappers that automatically did the necessary unit conversions. To do this we made a small domain-specific language for expressing unit conversions that compiled into the appropriate wrapper.
|
||
|
||
But wrappers can be used for more than just adapters for old code. We can wrap a procedure with a wrapper that checks input arguments for reasonableness and checks that the output is a plausible result given the inputs. If such checks fail, the wrapper can raise an error signal. This "paranoid programming style" is a very powerful tool for protecting a system from misuse and for debugging.
|
||
|
||
As illustrated with regular expressions and with unit conversions, often the best way to attack a class of problems is to invent a domain-specific language in which the solutions are easy to express. To explore this strategy we divided the problem of generating the legal moves for a board game into three individually extensible pieces: a domain model, a control-structure executive, and the specific rules of the game. The domain model provides a set of primitives that are combined to make the rules, giving us a language for expressing the rules. The application of the rules is sequenced by the control-structure executive. This combination forms the essence of a domain-specific language for expressing the rules of checkerslike board games.
|
||
|
||
Every good language has primitives, means of combination of those primitives, and means of abstraction for the combinations. The examples shown in this chapter are embedded in Scheme, and thus are able to use Scheme's powerful means of combination and
|
||
|
||
abstraction. But this is only the start. In chapter 5 we will transcend this embedding strategy, using the powerful idea of metalinguistic abstraction.
|
||
|
||
- <span id="page-53-0"></span>[1](#page-0-0) The generality of the domain model is an example of "Postel's law"—see page 3.
|
||
- <span id="page-53-1"></span>[2](#page-1-0) There are some notable exceptions: the functional programming extensions introduced by Java 8 directly capture useful combinations. Functional programming languages, such as Lisp and Haskell, have libraries of useful combination mechanisms.
|
||
- <span id="page-53-2"></span>[3](#page-4-0) Here things are simple, but in complex programs with many internal procedures, descriptive names can make things easier to read and understand. In MIT/GNU Scheme there is a minor advantage to naming the procedure being returned here, because the debugger can show this name for a procedure that would otherwise be anonymous.
|
||
- <span id="page-53-3"></span>[4](#page-9-0) Documentation of hash table procedures in MIT/GNU Scheme can be found in [51].
|
||
- <span id="page-53-4"></span>[5](#page-11-0) We thank Guy L. Steele Jr. for suggesting that we show this decomposition.
|
||
- <span id="page-53-5"></span>[6](#page-12-2) Documentation of values, call-with-values, and let-values can be found in [51] and [109].
|
||
- <span id="page-53-6"></span>[7](#page-15-2) Combinatory logic was invented by Moses Schönfinkel [108] and developed by Haskell Curry [26] in the early 20 th century. Their goal had nothing to do with computation, but rather to simplify the foundations of mathematics by eliminating the need for quantified variables.
|
||
- <span id="page-53-7"></span>[8](#page-16-1) The MIT/GNU Scheme procedure-arity, used in get-arity, will produce a numerical arity for the procedure returned, so we
|
||
|
||
- do not need to put a sticky note on it.
|
||
- <span id="page-54-0"></span>[9](#page-23-0) We indicate that there is no maximum by calling r:repeat with #f for max.
|
||
- <span id="page-54-1"></span>[10](#page-27-0) ERE Special Characters, [96] #tag 09 04 03
|
||
- <span id="page-54-2"></span>[11](#page-27-1) ERE Alternation, [96] #tag 09 04 07
|
||
- <span id="page-54-3"></span>[12](#page-27-2) EREs Matching Multiple Characters, [96] #tag 09 04 06
|
||
- <span id="page-54-4"></span>[13](#page-27-3) BREs Matching Multiple Characters, [96] #tag 09 03 06
|
||
- <span id="page-54-5"></span>[14](#page-28-0) BREs Matching Multiple Characters, [96] #tag 09 03 06
|
||
- <span id="page-54-6"></span>[15](#page-32-0) Note that the composition of two instances of meter-to-inch is a sensible way to convert square meters to square inches. There are unit conversions for which this is not true. For example, taking the square of a kelvin-to-Celsius conversion doesn't make sense, even though the numerical computation produces consistent results. This is a consequence of the fact that Celsius temperature has an offset from the physically meaningful kelvin temperature. Indeed, the square of a Celsius temperature has no physical meaning.
|
||
- <span id="page-54-7"></span>[16](#page-50-0) However, because the rule executive explicitly handles finished pmoves, we don't need to test for those in the rules.
|
||
- <span id="page-54-8"></span>[17](#page-52-0) SRFI 115 [110] is an interesting example. |