ANSWERS TO EXERCISES
1.1.
'Joe''s Pizza is "cute"'
"Joe's Pizza is ""cute"""
1.2.
'-'16 0
1.3.
(a) e1 sX sX ; (b) e1 tX e2 tX e3 ; (c) t1 e2 or e1 t2 .
1.4.
(a) tX becomes b ; (b) failure; (c) e6 becomes A(B) , e4 becomes C D ; (d) failure.
1.5.
Add {
(eX) '0' = eX;
(eX) eY's'= <Add (eX) eY>'s'; }
1.6.
Addb {
(eX'0')(eY s1) = <Addb (eX)(eY)> s1;
(eX'1')(eY'0') = <Addb (eX)(eY)>'1';
(eX'1')(eY'1') =
<Addb (<Addb (eX)('1')>)(eY)>'0';
(eX)(eY) = eX eY; }
2.1.
$ENTRY Go { = <Job> }
Job { = <Prout 'Please enter a line'>
<Job1 <Card>>; }
Job1 {
0 = <Prout 'Good-bye!'>;
eX = <Prout 'The translation is:'>
<Prout <Trans-line eX>>
<Job>; }
2.2.
(a) Sum-1 and '#SUM_1 '
(b) Sum'-'1 and '#SUM -#1 '
(c) as above
(d) (9'+'25)'()' and '(#9 +#25 )#(#)'
2.3.
* Conv-xx, conversion of a file typed for Input
* into a file for Xxin.
* Call: refgo conv-xx+reflib file-name
$ENTRY Go { =
<Xxout (<Arg 1>) <Input <Arg 1>>>; }
$EXTERN Input,Xxout;
2.4.
Merge { s1 s2 =
<Implode <Explode s1> <Explode s2>>; }
2.5.
(a)
7 6 8 5 4 9 3 2 10 11 1
eA ( t2 ) ( Sunday ) ( s.Day s.Night )
The variable eA (No.7) is closed.
(b)
1 3 2 4 5 7 9 8 10 6 11
( e.Word ) e1 ( ( e.Word ) e.Transl ) e2
No.3 is closed, No.4 open, No.9 repeated, No.11 closed.
(c)
1 8 9 10 7 6 2 11 12 13 4 5 3
( e1 '+' e2 '+' e3 ) e1 '+' e2 ( e3 )
No.5 is closed, No.6 repeated, No.8 open, No.10 closed, Nos.11 and 13 repeated.
2.6.
(a) ('di'
|
eA)('f'3.1.
The second delete sign will show up in the answer:
#Crocodile
To send the message, insert the sentence:
()'#'e2 = <Prout 'Extra delete signs!'>
<Prout '#'e2>;
between sentences 2 and 3.
3.2.
Cut {
(e1)(e2) = <Cut1 (()e1) (()e2)>; }
Cut1 {
((e.R1) tX e1) ((e.R2) tX e2) =
<Prout (e.R1 tX)(e.R2 tX)>
<Cut1 (()e1) (()e2)>;
((e.R1) tX e1) ((e.R2) tY e2) =
<Cut1 ((e.R1 tX) e1) ((e.R2 tY) e2)>;
eZ = ; }
3.3.
Equal {
(sX e1) (sX e2) = <Equal (e1) (e2)>;
((e.T1)e1) ((e.T2)e2) =
<Equal1 <Equal (e.T1)(e.T2)> (e1)(e2)>;
() () = T;
(e1) (e2) = F; }
Equal1 {
T eA = <Equal eA>;
F eA = F; }
3.4.
F {
sX e1 = <F1 sX()e1>;
= <Prout 'No repeated symbols'>; }
F1 {
sX(e2)sX e1 = sX e2 sX;
sX(e2)sY e1 = <F1 sX(e2 sY) e1>;
sX(e2) = <F e2>; }
3.5.
With implicit recursion:
Isect {
(sX e1)(e2 sX e3) = sX <Isect (e1)(e2 e3)>;
(sX e1)(e2) = <Isect (e1)(e2)>;
()(e2) = ; }
Without implicit recursions:
Isect {
(sX e1) eI (sX e2) = sX <Isect (e1)(eI e2)>;
(sX e1) eI (sY e2) =
<Isect (sX e1) eI sY (e2)>;
(sX e1) eI () = <Isect (e1) (eI)>;
() eI (e2) = ; }
NOTE: We have used the ``closed'' format of Isectwhich provides the space for one more expression, originally empty. If the format were Isect (e1)e2>
, we would have to introduce an auxiliary function.
3.6.
2c + t, where t = 1 if one string is a prefix of the other. With this definition:
* Precedence-conservative
* <Prec eC(e1)(e2)> == T(e1)(e2)
* == F(e1)(e2)
* where eC is the common part of e1 and e2.
Prec {
eC ()(e2) = T(eC)(eC e2);
eC (e1)() = F(eC e1)(eC);
eC (t1eX)(t1eY) = <Prec eC t1 (eX)(eY)>;
eC (t1eX)(t2eY) =
<Addc eC <Pre-term t1 t2>(t1eX)(t2eY)>;}
Addc { eC sT(eX)(eY) = sT(eC eX)(eC eY); }
the time is c + t.
3.7.
String {
e1 s2 = <String e1> s2;
= T;
e1(e2) = F e1(e2); }
Pal { eX = <Pal1 ()eX()>; }
Pal1 {
(eL) s1 e2 s1 (eR) =
<Pal1 (eL s1) e2 (s1 eR)>;
(eL)(eR) = T eL eR;
(eL) eI (eR) = F eL eI eR; }
3.8.
Fact {sN = <Loop F(1) I(1) N(sN)>; }
Loop {
F(sF) I(sN) N(sN) = <* sN sF>;
F(sF) I(sI) N(sN) =
<Loop F(<* sI sF>) I(<+ sI 1>) N(sN)>;
}
3.9.
* Recursive definition
Reverse {
s1 e2 = <Reverse e2> s1;
= ; }
*Iterative definition
Reversei { eX = <Revit ()(eX)>; }
Revit {
(eR)(s1 e2) = <Revit (s1 eR)(e2)>;
(eR)() = eR; }
3.10.
See function Pprout in reflib .
3.11.
* Multibracket Backtracking
Mback {
[e1(e2 ^e3)e4] = <Mback [e1 ^(e2 e3)e4]>;
[.e1 ^e2.] = e1 e2; };
This function achieves the result by moving pointer back to the beginning of the expression. The same can be done by moving the pointer forwards.
3.12.
(a)
* Call: <Tree [. ^sX.]>
* where sX is the root node.
Tree {
*1. A leaf. Jump over.
[e1 ^sX'.'e2] = <Tree [e1 sX'.' ^e2]>;
*2. A node with subtree. Enter it.
[e1 ^sX(eT) e2] = <Tree [e1 sX( ^eT)e2]>;
*3. A 'hanging' node. Generate subtree.
[e1 ^sX e2] = <Tree [e1 ^<Subtree sX> e2]>; *4. Up the tree.
[e1(e2 ^)e3] = <Tree [e1(e2) ^e3]>;
*5. End of work
[.e1 ^.] = e1; }
(b) All those nodes the processing of which has been completed are in the left multibracket and in the format sX(eS) , where eS is the completed subtree for sX
. Those nodes the processing of which has been started but not yet completed are also in the left multibracket, but in the format
sX)(
because the left parenthesis following sX
is represented by an inverted pair of parentheses. Therefore, we modify setnence 3 above as:
*3. A 'hanging' node. See whether repeated.
[e1 ^sX e2] = <Tree1
(<Rep sX[. ^e.ML(e1 ).]> )(sX e2)e.MR>;
The two new funcitons are defined as follows:
* See whether the subtree was already built
Rep {
*1. Repeated node found.
sX [e1 ^sX(eS) e2] =
Yes(eS) <Mback [e1 ^sX(eS) e2]>;
*2. A different symbol.
sX [e1 ^sY e2] = <Rep sX [e1 sY ^e2]>;
*3. Enter a parenthesis
sX [e1 ^(e2)e3] = <Rep sX [e1( ^e2)e3]>;
*4. Exit a parethesis
sX [e1(e2 ^)e3] = <Rep sX [e1(e2) ^e3]>;
*5. End of work.
sX [.e1 ^.] = No e1; }
Tree1 {
*1. Repeated node. Cope subtree.
(Yes(eS)e1)(sX e2)e.MR =
<Tree (e1)(sX(eS) e2)e.MR>;
*2. New node. Compute subtree.
(No e1)(sX e2)e.MR =
<Tree (e1)(<Subtree sX> e2)e.MR>;
}
4.1.
Addop {
e1 s.Op e2, '+-': eX s.Op eY =
(e1) s.Op e2;
e1 = <Prout 'No additive operations'>; }
4.2.
Less {
(e1) e2, <- e1 e2>: '-'eZ = T;
(e1) e2 = F;
eA = <Less <Format eA>>; }
Lesseq {
(e1) e2, <- e2 e1>: '-'eZ = F;
(e1) e2 = T;
eA = <Lesseq <Format eA>>; }
Format {
'-'s1 e2 = ('-'s1) e2;
'+'s1 e2 = (s1) e2;
s1 '-'e2 = (s1) '-'e2;
s1 '+'e2 = (s1) e2;
s1 e2 = (s1) e2; }
4.3.
S123 {
eA 1 e1, e1:
{eB 2 e2, e2: {eC 3 eD = T;
eC = F };
eB = F };
eA = F }
4.4.
Fa {
e1 sX sY e2,
<Less sY sX>: T,
<Less 100 <+ sX sY>>: T = sX sY;
e1 = <Prout 'No such pair'>;
}
Fb {
e1 sX sY e2, <Less sY sX>: T,
<Less 100 <+ sX sY>>:
{T = <Prout 'It is greater'>;
F = <Prout 'It is not greater'>;
};
e1 = <Prout 'No such pair'>;
}
4.5.
* Dictionary is stored as DICT
$ENTRY Go { =
<Br 'dict='<Xxin 'DICT'>>
<Prout 'Type in additions'>
<Addition <Input>> ;
}
Addition {
= <Prout 'No additions. Go ahead.'>
<Job>;
eX = <Prout 'OK. Go ahead.'>
<Xxout ('DICT') eX<Cp 'dict'>>
<Br 'dict='eX<Dg 'dict'>>
<Job>;
}
$EXTRN Input,Xxout,Xxin;
... etc. as before
6.1.
Fun-n {
sN eA = <Mu <Implode 'Fun'<Symb sN>> eA>; }
6.2.
Insert between the third and the fourth sentences:
'*'e1 = <Prout 'Error: no upgrade of 'e1>;
6.3.
(a) '*'((Add) (35)16)
(b) '*'((Up) ('*V'((F) ('*VE'1)'*VE'2)) '*V!'('*E'3))
(c) <Comp 'A*B'>
(d) Impossible. This is equivalent to <Dn 'A*B'> , and no expression becomes active when downgraded. Compare with Exercise 6.4(b).
6.4.
(a) 51
(b) 'A*B'
6.5.
Two functions must be modified:
Check-end {
= <Prout 'End of session'>;
'*'Error = <Job>;
eX = <Out <Ev-met eX>>; }
Out {
0 eX = <Prout 'The result is:'>
<Prout <Up eX>> <Prout> <Job>;
1 eX = <Prout 'Result depends on unknowns'>
<Prout> <Job>;
2 eX = <Prout 'Recognition impossible'>
<Prout 'View field in metacode:'>
<Pprout eX> <Error eX>;
}
$EXTRN Pprout,Error;