@appendix Example Compilations
This chapter exemplifies how LM-Prolog's compiler works.  It features
compiled unification, tail recursion optimization, automatic detection
of determinacy, and more.
Examples show how Prolog predicates are compiled into Lisp procedures and
further into Lisp Machine code (CADR system 93).

@section Introduction

@cindex backtracking
@cindex continuation
@cindex success continuation
The basic control strategy of LM-Prolog is called
``success continuations'' [Carlsson 1984].  
A success continuation is a function that is passed
as an extra argument to predicates.  
When a predicate has succeeded in proving its task, 
it invokes the continuation rather than returning.  If the continuation 
returns non-@l[nil], the predicate goes on to find more proofs, 
and so backtracking is achieved.

This scheme is used in compilation in the following way: a body of a clause
with, for example, three predications @l[((p ...) (q ...) (r ...))]
compiles to a structure like

@lisp
(funcall (entrypoint 'p)
         (continuation
           (funcall (entrypoint 'q)
                    (continuation
                      (funcall (entrypoint 'r)
                               original-continuation ...))
                               ...))
         ...)
@end lisp


@noindent
where @l[continuation] is a macro 
that expands its arguments to a function
of zero arguments, and @l[entrypoint] macro-expands to a
cached search for the compiled code of its argument.

An important special case is when the predicate is deterministic,
in which case the compiler often arranges that the continuation is
the function @l[true]. This makes it possible to compile a conjunction
of predications sequentially rather than as a nested construct. If all 
three predicates in the example above were deterministic, the compiled
code would look like

@lisp
(and (funcall (entrypoint 'p) (continuation (true)) ...)
     (funcall (entrypoint 'q) (continuation (true)) ...)
     (funcall (entrypoint 'r) (continuation (true)) ...)
     (invoke original-continuation))
@end lisp


The latter solution clearly consumes less stack space and constructs no
continuations.

The compiler uses argument list declarations and knowledge about previously
defined predicates to compute determinacy of static predicates. 
@c Note that generality rather than
@c maximum efficiency has been the important consideration in many system
@c predicates like @l[append] or @l[member] so they are not deterministic.
@c You may want to write specialized versions of them for 
@c specific argument list patterns, if you have a time-critical application.
To make best use of the determinacy optimization, definitions of
deterministic predicates should precede their uses.  This may not be possible
due to mutual recursion. 

@c You can use the Lisp form @l[declare]
@c to inform the compiler that certain predicates are deterministic.
@c The format is @l[(declare (deterministic p1 p2 ...))]
@c The declaration remains in effect during a @l[Compile Buffer/Region] editor
@c command, or during a @l[qc-file] operation and should of course be given 
@c before the first use of the declared predicates.

We give here a sample compilation of a ``pure'' LM-Prolog program:
the predicate @l[concatenate] which appends two lists,
and the predicate @l[naive-reverse] which reverses a list using
@l[concatenate].  Lisp is used as target language.  The compiled code
contains several macros and microcoded instructions:

@description
@item deffun
Macro that transforms tail recursive calls to iteration.

@item %unify-term-with-template
Instruction to unify a term with a ``template structure''.

@item %unify-term-with-term
Instruction to unify two terms.

@item %cell0
Instruction to allocate a value cell.

@item %prolog-list
Instruction to allocate a list.

@item %prolog-list*
Instruction to allocate a ``dotted list''.

@item %dereference
Instruction to dereference a variable.

@item %reference
Instruction to convert a variable before storing
a reference to it in a list.

@item %invoke
Instruction to invoke a continuation.

@item %current-entrypoint
Instruction that does a cached search for
the current definition of a predicate.

@end description

@section Concatenate
@lisp
(define-predicate concatenate
  (:options (:world :benchmarks) 
            (:execution :compiled) 
            (:argument-list (+ + -)))
  ((concatenate (?first . ?rest) ?back (?first . ?all-but-first))
   (concatenate ?rest ?back ?all-but-first))
  ((concatenate () ?back ?back)))
@end lisp

Mapping of variables:

@lisp
; ?first  (car g0634)
; ?rest  (cdr g0634)
; ?back  ?variable1
; ?all-but-first  ?variable5
@end lisp

Compiled code:

@lisp
(deffun concatenate-in-/:benchmarks-prover
        (.continuation. ?variable0 ?variable1 ?variable2
         &aux ?variable5)
  (let ((g0364 (%dereference ?variable0)))
    (cond ((and (and (consp g0364) t t))
           (and (%unify-term-with-template ?variable2
                                           '(14000002 . 4000000))
                (funcall (entrypoint 'concatenate)
                         (continuation (invoke .continuation.))
                         (cdr g0364)
                         ?variable1
                         ?variable5)))
          ((and (eq g0364 nil))
           (and (unify (%dereference ?variable1)
                       (%dereference ?variable2))
                (invoke .continuation.))))))
@end lisp

which further compiles to

@lisp
20 DEREFERENCE D-PDL ARG|1  ;?VARIABLE0
21 POP LOCAL|1
22 BR-ATOM 36
23 MOVE D-PDL ARG|3       ;?VARIABLE2
24 CAR D-PDL LOCAL|1
25 POP LOCAL|2
26 UNIFY-WITH-TEMPLATE D-PDL FEF|6       ;'(14000002 . 4000000)
27 BR-NIL-POP 34
30 CDR D-PDL LOCAL|1
31 MOVE D-PDL LOCAL|0     ;?VARIABLE5
32 POP ARG|3                  ;?VARIABLE2
33 BR 21
34 MOVE D-RETURN PDL-POP
35 MOVE D-IGNORE LOCAL|1
36 BR-NOT-NIL 46
37 DEREFERENCE D-PDL ARG|2  ;?VARIABLE1
40 DEREFERENCE D-PDL ARG|3  ;?VARIABLE2
41 UNIFY-WITH-TERM D-PDL PDL-POP
42 BR-NIL-POP 45
43 MOVE D-PDL ARG|0       ;.CONTINUATION.
44 (MISC) %INVOKE D-RETURN
45 MOVE D-RETURN PDL-POP
46 (MISC) FALSE D-RETURN
@end lisp

Instruction 26 references the template for @l[(?first . ?all-but-first)].

Tail recursion was transformed to iteration (instructions 30--33). In
performing that transformation, the compiler noted that dereferencing
@l[?variable0] is only needed initially since @l[cdr] 
(instruction 30) subsumes dereferencing.

Note the efficient compilation of the matching of @l[?variable0]
(instructions 22 and 36).

@section Naive-Reverse
@lisp
(define-predicate naive-reverse
  (:options (:world :benchmarks) 
            (:execution :compiled) 
            (:argument-list (+ -)))
  ((naive-reverse (?first . ?rest) ?reverse)
   (naive-reverse ?rest ?rest-reversed)
   (concatenate ?rest-reversed (?first) ?reverse))
  ((naive-reverse () ())))
@end lisp

Mapping of variables:

@lisp
; ?first  (car g0366)
; ?rest  (cdr g0366)
; ?reverse  ?variable1
; ?rest-reversed  ?variable4
@end lisp

Compiled code:

@lisp
(deffun naive-reverse-in-/:benchmarks-prover
        (.continuation. ?variable0 ?variable1 &aux ?variable4)
  (let ((g0366 (%dereference ?variable0)))
    (cond ((and (and (consp g0366) t t))
           (and
            (progn
             (setq ?variable4 (%cell0))
                   (and (funcall (entrypoint 'naive-reverse)
                                 (continuation (true))
                                 (cdr g0366)
                                 ?variable4)
                        (funcall (entrypoint 'concatenate)
                                 (continuation (invoke .continuation.))
                                 ?variable4
                                 (prolog-list (car g0366))
                                 ?variable1)))))
          ((and (eq g0366 nil))
           (and (unify (%dereference ?variable1) nil)
                (invoke .continuation.))))))
@end lisp

which further compiles to:

@lisp
30 DEREFERENCE D-PDL ARG|1  ;?VARIABLE0
31 POP LOCAL|1
32 BR-ATOM 57
33 CELL0 D-PDL
34 POP LOCAL|0            ;?VARIABLE4
35 MOVE D-PDL FEF|11      ;'NAIVE-REVERSE
36 CURRENT-ENTRYPOINT D-PDL FEF|12      ;'#<DTP-LOCATIVE 14304554>
37 CALL D-PDL PDL-POP
40 MOVE D-PDL FEF|8       ;'(TRUE)
41 CDR D-PDL LOCAL|1
42 MOVE D-LAST LOCAL|0    ;?VARIABLE4
43 BR-NIL-POP 55
44 MOVE D-PDL FEF|9       ;'CONCATENATE
45 CURRENT-ENTRYPOINT D-PDL FEF|10      ;'#<DTP-LOCATIVE 14304536>
46 CALL D-RETURN PDL-POP
47 MOVE D-PDL ARG|0       ;.CONTINUATION.
50 MOVE D-PDL LOCAL|0     ;?VARIABLE4
51 CAR D-PDL LOCAL|1
52 REFERENCE D-PDL PDL-POP
53 PROLOG-LIST D-PDL, 1 long
54 MOVE D-LAST ARG|2      ;?VARIABLE1
55 MOVE D-RETURN PDL-POP
56 MOVE D-IGNORE LOCAL|1
57 BR-NOT-NIL 66
60 DEREFERENCE D-PDL ARG|2  ;?VARIABLE1
61 UNIFY-WITH-TERM D-PDL 'NIL
62 BR-NIL-POP 65
63 MOVE D-PDL ARG|0       ;.CONTINUATION.
64 (MISC) %INVOKE D-RETURN
65 MOVE D-RETURN PDL-POP
66 (MISC) FALSE D-RETURN
@end lisp

Aided by the given call-pattern, the compiler noted that @l[concatenate]
is deterministic, and so it compiled a deterministic call from 
@l[naive-reverse] to @l[concatenate]. @l[(continuation (true))]
means there will only be one solution.

Tail recursion optimization is not applicable here.
One variable has to be initialized by an explicitly allocated value cell
(instructions 33--34).
Instructions 35--36 and 44--45 show examples of the @l[current-entrypoint] 
instruction. The locative in instruction 45 is a pointer to the
definitions of @l[concatenate]. The pointer is installed at load time.

In the call to @l[concatenate], a list 1 long is constructed by our
@l[prolog-list] instruction (instructions 51--53).

@section Discussion

The Naive Reverse program reverses a list 30 long in about .043 seconds on a
CADR.

Since continuations are always passed as arguments to predicates,
they could probably be allocated as stack lists.  There could be
problems, however, with stack lists being passed to lazy collections
or problems with tail recursive predicates.  For now, all continuations
are allocated in LM-Prolog's temporary area.

@cindex scope
@cindex lexical scoping
New ZetaLisp versions support lexical scoping of variables. With lexical
scoping, continuations are not represented as lists but as compiled
functions without arguments which refer to variables in lexically
enclosing functions.

