% $BI>2A9M;!(B

\chapter{ DKLIC $B=hM}7O$NI>2A$H9M;!(B \Comment{(Evaluation)} }
\label{eval}

$BA0>O$G$O!"(BDKLIC $B=hM}7O$r<BAu$7$?!#(B
%
$BK\>O$G$O!"(BDKLIC $B=hM}7O$K$D$$$FI>2A$H9M;!$r9T$&!#(B


\section{ $B4{B8$N;n:n$+$i$N2~NIE@(B }

DKLIC $B=hM}7O$N4{B8$N;n:n(B \cite{DKLIC}, \cite{SPA2001}, \cite{takayama}
$B$G$OL$Dj5AJQ?tF1;N$ND>7k$r8!=P$9$k$3$H$,$G$-$J$+$C$?!#(B
%
$BK\8&5f$G$OL$Dj5AJQ?tF1;N$ND>7k$r8!=P$9$k$3$H$K$h$C$F!"(B
$BFs=EAw?.$NKI;_!"Cf7Q$NGS=|$r9T$&$3$H$r2DG=$K$7$?!#(B

$B$^$?!"4{B8$N;n:n$G$OJ,;6O@M}JQ?t$N(B ID $B$N:FMxMQ$,9T$o$l$F$$$J$+$C$?!#(B
%
$BK\8&5f$G$O(B ID $B$r:FMxMQ$7$FNI$$%?%$%_%s%0$H!"(B
$B%[%9%H$N(B ID $BMxMQ!&:FMxMQ8"$r9M;!$7$?!#(B
%
$B$^$?!"(BID $B$r@5$7$/:FMxMQ$9$k$?$a$KI,MW$J(B
$B<u?.3NG'%a%C%;!<%8$rF3F~$7$??7$?$JDL?.%W%m%H%3%k(B DKLICP $B$r@_7W$7$?!#(B
%
$B$=$7$F!"(BDKLICP $B$K=>$C$FDL?.$r9T$&(B DKLIC $B=hM}7O$r<BAu$7$?!#(B


\section{ KLIC $BJBNs<BAu$H$NHf3S(B }

KLIC $B=hM}7O$G$O!"%[%9%HKh$KM"=PI=$HM"F~I=$,@8@.$5$l$k!#(B
$B%m!<%+%k%[%9%H$+$iM"=P$5$l$?JQ?t$OM"=PI=$KEPO?$5$l!"(B
$B1s3V%[%9%H$+$iM"F~$5$l$?JQ?t$OM"F~I=$KEPO?$5$l$k!#(B

DKLIC $B=hM}7O$NJQ?tI=$HF1MM!"M"F~I=$KBP$7$F$O(B
KLIC $B$N(B GC $B%U%'%$%:=*N;D>8e$KM"F~I=$N(B GC $B%U%'%$%:$,5/F0$5$l!"(B
$BM"F~JQ?t$NGQ4~$,M"F~85$N%[%9%H$KJs9p$5$l$k!#(B
$B$7$+$7!"M"=PI=$KBP$7$F$O$3$N$h$&$J(B GC $B=hM}$O9T$o$l$J$$!#(B

$BM"=P$5$l$kJQ?t$N(B ID $B$O!"$=$NJQ?t$rM"=P$7$?%[%9%H$H(B
$BM"=PI=$K$*$1$k%$%s%G%/%9$+$i@.$k!#(B
$B=>$C$F!"(B\Opener $B$K$h$k(B ID $B6u4V$NJ,N%$O<+A3$K$J$5$l$F$$$k!#(B
%
KLIC $B=hM}7O$NJBNs<BAu$K$*$$$FA4$F$N%[%9%H$O=g=xIU$1$i$l$F$*$j!"(B
$B$=$N=g=x?t$K$h$C$F%[%9%H$rFCDj$9$k$3$H$,$G$-$k$,!"(B
DKLIC $B=hM}7O$NA0Ds$H$9$kJ,;64D6-$K$*$$$F$O(B
$BJ8;zNs$"$k$$$O(B IP $B%"%I%l%9$K$h$C$F%[%9%H$rFCDj$9$k!#(B
KLIC $B$N(B ID $B3d$jEv$FJ}<0$r$=$N$^$^3HD%$9$k$H!"(B
$BJQ?t<1JL;R$O(B KLIC $B$N@0?t$NHO0O$r1[$($F$7$^$&$G$"$m$&!#(B

DKLIC $B=hM}7O$O%[%9%H4V@\B3$NBPKh$KJQ?tI=$r0lBP(B
$B!J$=$l$>$l%=%1%C%H$NN>C<$K!K@8@.$9$k!#(B
DKLIC $B=hM}7O$O$^$@Nc30=hM}$r<BAu$7$F$$$J$$$,!"(B
$B>-MhNc30=hM}$r<BAu$7$?;~!"(B
$BLdBj$N5/$-$?%=%1%C%H$H0lBP$NJQ?tI=$N$_$r=hM}$7!"(B
$B$=$NB>$N7rA4$J%=%1%C%H$HJQ?tI=$O$=$N$^$^$K$7$F$*$/(B
$B$H$$$&$3$H$,2DG=$G$"$k!#(B
%
$B0lJ}!"(BKLIC $B$N$h$&$K3F%[%9%H$,M"=PI=$HM"F~I=$NAH$r(B
$B$?$@0l$D$7$+;}$?$J$$>l9g!"(B
$B$=$NCf$+$iLdBj$N5/$-$?@\B3$KBP1~$9$kJQ?t72$r(B
$BA*$S=P$5$J$1$l$P$J$i$J$$$G$"$m$&!#(B

\Comment{
eager push vs lazy pull
fflush $B%P%C%U%!%j%s%0(B
$BDjNLE*$J4QB,I>2A$O:#8e$N2]Bj$G$"$k!#(B
%
$BNc$($P!"7HBS>pJsC<Kv(B
TCP/IP $B$KAjEv$9$k?.Mj@-$N$"$k%W%m%H%3%k$,(B
 $BEE;R%a!<%k%7%9%F%`>e$K9=C[$5$l$?>l9g!"(B
$B>e5-$N%P%C%U%!%j%s%0J}<0$OM-8z$G$"$m$&$+!#(B
%
$B%Q%1%C%H?t@aLs(B
$B0lBP0l(B vs $BB?BP0l(B
}


\section{ $BCf7QDL?.$NGS=|(B }

% linear vs non-linear

$B%W%C%7%e7?DL?.$K$*$1$kCf7Q$rGS=|$9$k$?$a$NDL?.%W%m%H%3%k$O!"(B
$BJ88%(B\cite{transit}$B$K$b8+$i$l$k!#(B
$B$?$@$7!"$3$N%W%m%H%3%k$ODL?.O)$,C10lBeF~$G$"$k$3$H$r(B
$BA0Ds$H$7$F$$$J$$$?$a!"(BDKLICP $B$h$j8zN($,0-$$!#(B
$B$^$?!"B?$/$NJQ?t$,@~7A$G$"$k$3$H$r0EL[$K2>Dj$7$F$$$k!#(B

$B%[%9%H(B \A $B$+$i(B \B $B$XDL?.O)(B K$B!"(B
$B%[%9%H(B \B $B$+$i(B \C $B$XDL?.O)(B L $B$,DL$8$F$$$k;~!"(B
$B%[%9%H(B \B $BFb$G(B K=L $B$,<B9T$5$l$?$,!"(B
K=L $B$r;2>H$9$k%W%m%;%9$,%[%9%H(B \B $BFb$K;D$C$F$$$k>l9g!"(B
$BJ88%(B\cite{transit}$B$NJ}<0$G$O(B
$B%[%9%H(B \A $BFb$G$N(B K $B$N6qBN2=%a%C%;!<%8$O(B
$B%[%9%H(B \B $B$rCf7Q$7$F%[%9%H(B \C $B$XFO$/!#(B

$B$3$l$OO@M}E*$K@5$7$$$,!"J,;64D6-$NCY1d;~4V$,L5;k$G$-$J$$$[$I(B
$BBg$-$$$3$H$r9MN8$9$k$HK>$^$7$/$J$$!#(B
%
DKLICP $B$O%[%9%H(B \B $BFb$G(B K=L $B$X$N;2>H$,;D$C$F$$$k$+H]$+$K4X$o$i$:!"(B
$B%[%9%H(B \A--\C $B4V$NDL?.$r%[%9%H(B \B $B$,Cf7Q$9$k$h$&$J>u67$rGS=|$9$k(B
$B$h$&$K@_7W$7$?!#(B

% \( k + l > k' \)


\section{ Oz $B$H$NHf3S(B }

% static vs dynamic

$BJB9T@)Ls8@8l(B Oz $B$O@EE*2r@O$rL\;X$7$F$$$J$$!#(B
$BJ,;64D6-$K$*$$$F$O!"AG@-$NCN$l$J$$%G!<%?$d%b%P%$%k%3!<%I$KBP$7$F(B
$B@EE*2r@O!&8!>Z$r9T$($k$3$H$OHs>o$K=EMW$G$"$m$&!#(B

Oz $B$OB?J,LZ$N40A4$JC10l2=$rL\;X$7$F$$$k$N$KBP$7!"(B
DKLIC $B$OJ,;6JQ?t$rC1$KDL?.O)$H8+$J$7$F$$$k!#(B
%
DKLICP $B$G$O(B out $B%b!<%IF1;N$NJ,;6JQ?t$ND>7k$KBP$7$F(B
$B2?$N=hM}$b9T$o$J$$$,!"%b!<%I$KMj$i$J$$(B Oz $B$O(B
$B$3$N$h$&$JDL?.$N:GE,2=$r9T$&$3$H$,$G$-$J$$!#(B

% $BJ,;6(B GC
% $BB?BPB?(B


\section{ $BDL?.Nc30=hM}(B }

$BDL?.Cf$K1s3V%[%9%H!"DL?.O)!"DL?.Aj<j$N%W%m%;%9$,Mn$A$?>l9g!"(B
$BFI$_9~$_%b!<%I$NJ,;6O@M}JQ?t$K6/@)E*$K(B [] $B$r=q$-9~$`$3$H$K$h$C$F!"(B
$BMn$A$?DL?.Aj<j$+$i$N%a%C%;!<%8$rBT$AB3$1$k%G%C%I%m%C%/$,(B
$B5/$-$J$$$3$H$rJ]>Z$9$k$3$H$,$G$-$k$G$"$m$&!#(B


\section{ $B%9%H%j!<%`$XO"B3$7$?(B ID $B$r3d$jEv$F$FJV;v$r%P%C%U%!$9$k(B }

$B8=:_(B DKLIC $B=hM}7O$OJ,;6JQ?t$X$N(B ID $B$N3d$jEv$F$K4X$7$F!"(B
$B$=$NJQ?t$N7?$r2?$i2>Dj$7$F$$$J$$!#(B

$B$7$+$7!"%9%H%j!<%`$XO"B3$7$?(B ID $B$r3d$jEv$F$l$P!"(B
$B8D!9$N%3%s%9$KBP$7$F<u?.3NG'$rAw?.$;$:!"(B
$B0lDj;~4VKh$K(B\Name{i}$B$+$i(B\Name{j}$B$^$G$N%3%s%9$KBP$9$k(B
$B<u?.3NG'%a%C%;!<%8(B\String{\Name{i}-\Name{j}=Removed}
$B$rAw?.$9$k$3$H$K$h$C$FDL?.%a%C%;!<%8$r%P%C%U%!%j%s%0$9$k$3$H(B
$B$,2DG=$G$"$m$&!#(B
$B$3$l$O(B TCP $B%Q%1%C%H$N<u?.3NG'$,!V;XDj$7$?HV9f$^$G$N%Q%1%C%H72!W(B
$B$KBP$9$k<u?.3NG'$G$"$k$N$KNI$/;w$?J}<0$G$"$k!#(B

$B$^$?!">e5-$NJ}<00J30$K$b(B dklicio $B$NM%@hEY$r2<$2$k$3$H$K$h$C$F!"(B
$B%9%H%j!<%`$,$"$kDxEY=q$-9~$^$l$F$+$i(B
dklicio $B%W%m%;%9$K$h$k6qBN2=%a%C%;!<%8$,Aw?.$5$l$k$h$&$K$7$F(B
$B<+A3$K%P%C%U%!%j%s%0$r9T$&$3$H$b2DG=$G$"$k!#(B
%
$B$3$A$i$NJ}<0$G$O!"$=$b$=$b(B ID $B$N3d$jEv$FIQEY$,Dc$/$J$k(B
$B$H$$$&K>$^$7$$@-<A$,$"$k!#(B

ID $B$N3d$jEv$F$HDL?.%a%C%;!<%8NL$NDjNLI>2A$O:#8e$N2]Bj$G$"$k!#(B


\section{ $B@~7A$GHs(B mobile $B$J%9%H%j!<%`$N(B ID $BB(;~:FMxMQ(B }

% $B$b$A$m$s%b!<%IIU$-$rA0Ds$H$9$k!#(B

$B%9%H%j!<%`$XO"B3$7$?(B ID $B$r3d$jEv$F$k(B
$BA0@a$NJ}<0$r$5$i$K2!$7?J$a$k$H!"(B
\String{\Name{ID}={\tt[T|ID]}}$B$N$h$&$K(B
$B%9%H%j!<%`$N(B cdr $B$K$=$N%9%H%j!<%`$N(B
ID $B$rB(;~:FMxMQ$9$kJ}<0$K$?$I$jCe$/!#(B
%
$B$3$NJ}<0$G$O<u?.3NG'$OITMW$G$"$k!#(B

$B$3$N>l9g!"%9%H%j!<%`$N(B ID $B$O(B
$BJQ?t$G$J$/%9%H%j!<%`$N<1JL;R$G$"$k$3$H$K$J$k!#(B
$B=>$C$F!"$3$N%9%H%j!<%`$OC10lBeF~$G$J$/$J$k!#(B
\begin{verbatim}
append(X, Y, Z) :- X = [] |
  Z = Y.
append(X, Y, Z) :- X = [A | X1] |
  Z = [A | Z1],
  append(X1, Y, Z1).
\end{verbatim}
append/3 $B=R8l$K$*$$$F%9%H%j!<%`(B X, Y, Z $B$,C10lBeF~$G$J$$>l9g!"(B
Z = Y $B$K$h$C$F(B Z $B$H(B Y $B$N$I$N;~E@(B (continuation) $B$rD>7k$9$k$N$+(B
$BH=CG$G$-$J$$!#(B

$B$^$?!"%9%H%j!<%`$,4V@\M"=P$5$l$k>l9g$b!"(B
$B%9%H%j!<%`$N$I$N;~E@$,4V@\M"=P$5$l$F$$$k$N$+H=CG$9$k$3$H$O$G$-$J$$!#(B
$B$I$N$h$&$J>l9g$K!"(B
$B%9%H%j!<%`$N(B cdr $B$K%9%H%j!<%`$N(B ID $B$rB(;~:FMxMQ$7$FNI$$$N$+(B
$B8!>Z$9$k$3$H$O:#8e$N2]Bj$G$"$m$&!#(B


\section{ strictly linear ID allocation }

KL1 $B8@8l$N@EE*2r@O$NBN7O$K$O!"7?!&%b!<%IBN7O$NB>$K;2>H?tBN7O$,$"$k!#(B
$B;2>H?t$,$A$g$&$IFs$D$G$"$k$h$&$JJQ?t$O!"=q$-<j0l?M$KBP$7$FFI$_<j0l?M(B
$B$G$"$k$?$a!"GK2uE*BeF~$,2DG=$G$"$k!#$3$N@-<A$r@~7A@-$H8F$V!#(B

$B@~7A@-$N35G0$r6qBNCM$K$b2!$7?J$a$?(B strict linearity
$B$O!"%W%m%0%i%`$,0z?t$KEO$5$l$?;q8;$N$_$rMxMQ$7$F<B9T$r(B
$B9T$&$3$H$r<($9@-<A$G$"$k(B\cite{strict-linearity}$B!#(B
strictly linear $B$J%W%m%0%i%`$O(B
$BMxMQ$9$k;q8;$,@EE*$KH=L@$9$k$?$a!"(BGC $B$rI,MW$H$7$J$$!#(B

strict linearity $B$N35G0$rJQ?t$X$N(B ID $B3d$jEv$F$K$b(B
$BE,MQ$9$k$H!"<!$N$h$&$J(B stack/2 $B%5!<%P=R8l$O(B
$B2<5-$N(B strict linear $B$J(B stack/3 $B%5!<%P=R8l$K=q$-49$($k$3$H$,$G$-$k!#(B
\begin{verbatim}
stack(S, D) :- S = [] |
  true.
stack(S, D) :- S = [push(X) | S1] |
  stack(S1, [X|D]).
stack(S, D) :- S = [pop(X) | S1], D = [Y|D1] |
  X = Y,
  stack(S1, D1).
\end{verbatim}

\begin{verbatim}
stack(S, ^(R), D) :- S = [](*) |
  R = [](D).
stack(S, ^(R), D) :- S = [push([X|*]) | S1] |
  R = [push(*) | R1],
  stack(S1, R1, [X|D]).
stack(S, ^(R), D) :- S = [pop(^(X)) | S1], D = [Y|D1] |
  X = Y,
  R = [pop([*|*]) | R1],
  stack(S1, ^(R1), D1).
\end{verbatim}
$BA4$F$N%5!<%P$,(B strict linear $B$G$"$k$H2>Dj$9$k$H!"(B
DKLIC $B=hM}7O$O<u?.3NG'$r>JN,$9$k$3$H$,$G$-$k!#(B
$B$7$+$7!"$3$l$O%5!<%P%W%m%0%i%^$,<u?.3NG'$NAw?.$r(B
$BL@<($9$k$3$H$r0UL#$7!"<u?.3NG'$N@UG$$,(B DKLIC $B=hM}7O$+$i(B
$B%5!<%P%W%m%0%i%^$X0\$C$?$@$1$G$"$k$H8@$($k!#(B


\section{ $B:#8e$N2]Bj(B }

$B8=:_(B DKLIC $B=hM}7O$OL$Dj5AJQ?t$NM"=PF~$H(B
$B$=$N6qBN2=!"D>7k!"GQ4~$N$_$r4IM}$7$F$$$k!#(B
%
$B$7$+$7!"5-9f=hM}8@8l(B KL1 $B$K$*$$$F(B
$B5-9f$N8zN(E*$JM"=PF~!"Aw<u?.$KBP$9$kMWK>$b$"$jF@$k$G$"$m$&!#(B

% $BJQ?t(B--$B6qBNCM%P%C%U%!%j%s%0%5!<%P(B

$B$^$?!"4{$K6qBN2=$5$l$?9`$NAw<u?.$r%P%C%U%!%j%s%0$9$k$3$H$O(B
$BDL?.NL$N:o8:$N$?$a$KI,MW$G$"$k!#(B
%
$B$3$N$h$&$J%5!<%P$O%f!<%6Dj5A%5!<%P$H$7$F<BAu$7!"(B
DKLICP $B$N>e0L%W%m%H%3%k$r9=C[$9$k$3$H$,2DG=$G$"$m$&!#(B

DKLIC $B=hM}7O$O07$&%W%m%0%i%`$,%b!<%IIU$-$G$"$k$3$H$r(B
$BA0Ds$H$7$F$$$k$,!"(BKLIC $BK]Lu7O$O%b!<%I2r@O$r9T$o$J$$!#(B
%
DKLIC $B%W%m%0%i%^$O(B KLIC $B$K2C$($F(B Kima $B$rMxMQ$9$k$3$H$K$h$C$F(B
$B%b!<%IIU$-%W%m%0%i%`$r5-=R$9$kI,MW$,$"$k$G$"$m$&!#(B
%
$B$7$+$7!"%W%m%0%i%^$,(B Kima $B$r6/@)$5$l$k$N$O>/!9LLE]$G$"$k!#(B
$B:#8e(B KLIC $B$"$k$$$O$=$l$KBe$o$kK]Lu7O$O(B Kima $B$N$h$&$J(B
$B@EE*2r@O4o$r4^$`$3$H$,K>$^$7$$!#(B

\vspace{1em}

$B0J>e$G!"(BDKLIC $B=hM}7O$NI>2A$H9M;!$r=*$($k!#(B
%
$B<!>O$G$O!"K\O@J8$K$D$$$F$^$H$a$k!#(B
