The trivia.balland2006 Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The trivia.balland2006 Reference Manual

This is the trivia.balland2006 Reference Manual, version 0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:40:54 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction


* Trivia.Balland2006

[[https://travis-ci.org/guicho271828/trivia.balland2006][https://travis-ci.org/guicho271828/trivia.balland2006.svg?branch=master]]

This is an optimizer implementation based on (Balland et.al. 2006).

c.f.

#+BEGIN_QUOTE
Le Fessant, Fabrice, and Luc Maranget. Optimizing pattern matching.
ACM SIGPLAN Notices. Vol. 36. No. 10. ACM, 2001.

Emilie Balland, Pierre-Etienne Moreau. Optimizing pattern matching compilation by program
transformation. [Technical Report] 2006, pp.19. 
#+END_QUOTE

** Usage & Dependencies

After loading Trivia, use =(ql:quickload :trivia.balland2006.enabled)= to activate the optimizer.

It depends on the following libraries:

+ [[https://github.com/guicho271828/trivia][Trivia by Me]] :: NON-Optimized Pattern Matching Library

+ [[https://github.com/guicho271828/type-i][Type-i]] by Me :: Type inference utility for fundamentally 1-arg predicates

+ alexandria ::
    Alexandria is a collection of portable public domain utilities.

+ iterate ::
    Jonathan Amsterdam's iterator/gatherer/accumulator facility

* Optimizer Details

In (Emillie 2006), their optimization rule reduces the number of
assignments (let) and tests (if).  However, since current state-of-the-art
common lisp implementations (namely, sbcl and ccl) eliminates unnecessary
assignments by default, so we do not focus on the assignments in our compiler.
Thus, Assignment optimization in Section
3.1, e.g., Constant Propagation, Dead Variable Elimination, Inlining,
Let-Fusion are not considered.

The main focus is on reducing the number of conditional check, which may
involve a function call and is costly.  We implement Section 3.2 Reducing
the number of tests, which describes: Fusion, Interleaving, Ifswapping.

** Patterns Transformation Rules

The compatibility of test-forms of guard1 pattern is determined in
form-to-form basis, and the types are detected from the predicate form.
We used =:type-i= package for this purpose. After the types are detected,
one of the following translation rules are applied iteratively.

*** Fusion

Consider the following match:

#+BEGIN_SRC lisp
(match1 what
  ((guard1 it (consp it)
           (car it) (guard1 x (= 1 x))
           (cdr it) (guard1 y (null y))) body1)
  ((guard1 it (consp it)
           (car it) (guard1 x (stringp x))
           (cdr it) (guard1 y (null y))) body2))
#+END_SRC

body1 has an environment where

: it <-- (consp it) <-- can be infered as type `cons'
: car <-- (= 1 car) <-- not inferred right now: an anonymous type e.g. #:ANON0
: cdr <-- (null y)  <-- type `null'

body2 has an environment where

: it <-- (consp it) <-- can be infered as type `cons'
: car <-- (stringp x) <-- can be infered as type `string'
: cdr <-- (null y)  <-- type `null'

Since the two checks have type `cons' in common, the first check can be
merged. In the above case, the original code is compiled into:


#+BEGIN_SRC lisp
(match what
  ((guard1 it (consp it) (car it) #:car (cdr it) #:cdr)
   (match* (#:car #:cdr)
     (((guard x (= 1 x))     (guard y (null y))) body1)
     (((guard x (stringp x)) (guard y (null y))) body2))))
#+END_SRC

*** Interleaving

Consider the following match is done under the environment in which `what' is known to be of type `list'.

#+BEGIN_SRC lisp
(match1 what
  ((guard1 it (consp it)) body1)
  ((guard1 it (null  it)) body2))
#+END_SRC

Since `cons' and `null' are the exhaustive partition of type `list', this can be optimized into

#+BEGIN_SRC lisp
(match1 what
  ((guard1 it (consp it)) body1)
  (_                      body2))
#+END_SRC

to avoid checks.

Note: in (Emillie 2006), 2 variations of interleaving rule is proposed, one
general case, and the other specialized case if i'_1 and i'_2 being nop.
As a good news, in trivia's context, i'_1 and i'_2 are always nop, and
exactly 1 clause should match at a time.

Note: In order to calculate the applicability of this rule, information about
the environment is essential.  however, we try not to use cltl2
environment as of now, since it is out of scope of trivia: Conditional
expression may be removed using the outside environment, but we focus on
the removal of the tests inside trivia.

Quoting (Emillie 2006):

#+BEGIN_QUOTE
IfInterleaving:

: if(c1,i1,i'1); if(c2,i2,nop) → if(c1,i1,i'1;if(c2,i2,nop)) IF c1⊥c2
: if(c1,i1,nop);if(c2,i2,i'2)  → if(c2,i2,if(c1,i1,nop);i'2) IF c1⊥c2

These two rules reduce the number of tests at run time because one of the tests is
moved into the “else” branch of the other. The second rule can be instantiated and used
to swap blocks. When i'1 and i'2 are reduced to the instruction nop, the second rule can be
simplified into:

: if(c1,i1,nop);if(c2,i2,nop)→if(c2,i2,if(c1,i1,nop)) IF c1⊥c2
#+END_QUOTE

*** Swapping

Above interleaving rule only applies when the two checks are
adjacsent. Therefore, we swap the order of patterns.

Quoting (Emillie 2006):
 
#+BEGIN_QUOTE
After all, we obtain the following rule corresponding to the swapping of two conditional
adjacent blocks. This rule does not optimize the number of tests but is useful to join blocks
subject to be merged thanks to a smart strategy.

IfSwapping: if(c1,i1,nop);if(c2,i2,nop)→if(c2,i2,nop);if(c1,i1,nop) IF c1⊥c2
#+END_QUOTE

** Transformation Strategy

The quality of the resulting code is affected by the strategy for selecting
which rule to apply in what order. We again followed the simple strategy in
(Emillie 2006).

#+BEGIN_QUOTE
Using basic strategy operators such as Innermost(s) (which applies s as many times as
possible, starting from the leaves), s1 | s2 (which applies s1 or s2 indifferently), repeat(s)
(which applies s as many times as possible, returning the last unfailing result), and r1 ; r2
(which applies s1, and then s2 if s1 did not failed), we can easily define a strategy which
describes how the rewrite system OptSys should be applied to normalize a PIL program:
#+END_QUOTE

: Innermost( repeat(ConstProp | DeadVarElim | Inlining | LetFusion | IfFusion | IfSwapping) ;
:            repeat(IfInterleaving))

Now in our implementation this is simplified as follows:

: Innermost( repeat( Fusion | Swapping) ; repeat(Interleaving))




* Author & Copyright

Copyright (c) 2015 Masataro Asai (guicho2.71828@gmail.com)

Licensed under the LLGPL.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 trivia.balland2006

Author

Masataro Asai

Contact

guicho2.71828@gmail.com

License

LLGPL

Description

Optimizer for Trivia based on (Balland 2006)

Version

0.1

Dependencies
Source

trivia.balland2006.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 trivia.balland2006.asd

Location

/home/quickref/quicklisp/dists/quicklisp/software/trivia.balland2006-20170124-git/trivia.balland2006.asd

Systems

trivia.balland2006 (system)

Packages

trivia.balland2006-asd


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 trivia.balland2006/package.lisp

Parent

trivia.balland2006 (system)

Location

package.lisp

Packages

trivia.balland2006


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.3 trivia.balland2006/optimizer.lisp

Dependency

package.lisp (file)

Parent

trivia.balland2006 (system)

Location

optimizer.lisp

Exported Definitions
Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

3.1.4 trivia.balland2006/column-swapping.lisp

Dependency

optimizer.lisp (file)

Parent

trivia.balland2006 (system)

Location

column-swapping.lisp

Exported Definitions
Internal Definitions

find-tree (function)


Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

4.1 trivia.balland2006-asd

Source

/home/quickref/quicklisp/dists/quicklisp/software/trivia.balland2006-20170124-git/trivia.balland2006.asd

Use List

Previous: , Up: Packages   [Contents][Index]

4.2 trivia.balland2006

Source

package.lisp (file)

Use List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Functions

Function: apply-fusion CLAUSES TYPES
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: apply-interleaving CLAUSES TYPES &aux UNDER
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: apply-swapping CLAUSES TYPES &aux UNDER
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: fuse CLAUSES TYPES
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: fusiblep C1 C2 &optional UNDER
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: interleave C1 C2 TYPES &aux UNDER
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: pattern-dependencies PATTERNS
Package

trivia.balland2006

Source

column-swapping.lisp (file)

Function: pattern-dependent P1 P2

return true if p2 depends on p1

Package

trivia.balland2006

Source

column-swapping.lisp (file)

Function: swappable C1 C2 &optional UNDER
Package

trivia.balland2006

Source

optimizer.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Functions

Function: apply-or-grounding CLAUSES
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: balland2006 CLAUSES TYPES
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: divide-clauses CLAUSES TYPES &aux UNDER
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: find-tree OBJ TREE &key TEST
Package

trivia.balland2006

Source

column-swapping.lisp (file)

Function: gen-union &optional X Y
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: gensym* NAME
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: ground-or CLAUSE
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: swappable-rec PATTERNS1 PATTERNS2 UNDER
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: type-disjointp T1 T2 &optional UNDER
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: type-equal T1 T2 &optional UNDER
Package

trivia.balland2006

Source

optimizer.lisp (file)

Function: type-exhaustivep T1 T2 &optional UNDER

Returns true for types under, t1, t2, if under = t1 + t2 and nothing more

Package

trivia.balland2006

Source

optimizer.lisp (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   T  
Index Entry  Section

F
File, Lisp, trivia.balland2006.asd: The trivia<dot>balland2006<dot>asd file
File, Lisp, trivia.balland2006/column-swapping.lisp: The trivia<dot>balland2006/column-swapping<dot>lisp file
File, Lisp, trivia.balland2006/optimizer.lisp: The trivia<dot>balland2006/optimizer<dot>lisp file
File, Lisp, trivia.balland2006/package.lisp: The trivia<dot>balland2006/package<dot>lisp file

L
Lisp File, trivia.balland2006.asd: The trivia<dot>balland2006<dot>asd file
Lisp File, trivia.balland2006/column-swapping.lisp: The trivia<dot>balland2006/column-swapping<dot>lisp file
Lisp File, trivia.balland2006/optimizer.lisp: The trivia<dot>balland2006/optimizer<dot>lisp file
Lisp File, trivia.balland2006/package.lisp: The trivia<dot>balland2006/package<dot>lisp file

T
trivia.balland2006.asd: The trivia<dot>balland2006<dot>asd file
trivia.balland2006/column-swapping.lisp: The trivia<dot>balland2006/column-swapping<dot>lisp file
trivia.balland2006/optimizer.lisp: The trivia<dot>balland2006/optimizer<dot>lisp file
trivia.balland2006/package.lisp: The trivia<dot>balland2006/package<dot>lisp file

Jump to:   F   L   T  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   A   B   D   F   G   I   P   S   T  
Index Entry  Section

A
apply-fusion: Exported functions
apply-interleaving: Exported functions
apply-or-grounding: Internal functions
apply-swapping: Exported functions

B
balland2006: Internal functions

D
divide-clauses: Internal functions

F
find-tree: Internal functions
Function, apply-fusion: Exported functions
Function, apply-interleaving: Exported functions
Function, apply-or-grounding: Internal functions
Function, apply-swapping: Exported functions
Function, balland2006: Internal functions
Function, divide-clauses: Internal functions
Function, find-tree: Internal functions
Function, fuse: Exported functions
Function, fusiblep: Exported functions
Function, gen-union: Internal functions
Function, gensym*: Internal functions
Function, ground-or: Internal functions
Function, interleave: Exported functions
Function, pattern-dependencies: Exported functions
Function, pattern-dependent: Exported functions
Function, swappable: Exported functions
Function, swappable-rec: Internal functions
Function, type-disjointp: Internal functions
Function, type-equal: Internal functions
Function, type-exhaustivep: Internal functions
fuse: Exported functions
fusiblep: Exported functions

G
gen-union: Internal functions
gensym*: Internal functions
ground-or: Internal functions

I
interleave: Exported functions

P
pattern-dependencies: Exported functions
pattern-dependent: Exported functions

S
swappable: Exported functions
swappable-rec: Internal functions

T
type-disjointp: Internal functions
type-equal: Internal functions
type-exhaustivep: Internal functions

Jump to:   A   B   D   F   G   I   P   S   T  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables


Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   P   S   T  
Index Entry  Section

P
Package, trivia.balland2006: The trivia<dot>balland2006 package
Package, trivia.balland2006-asd: The trivia<dot>balland2006-asd package

S
System, trivia.balland2006: The trivia<dot>balland2006 system

T
trivia.balland2006: The trivia<dot>balland2006 system
trivia.balland2006: The trivia<dot>balland2006 package
trivia.balland2006-asd: The trivia<dot>balland2006-asd package

Jump to:   P   S   T