Difference between revisions of "Publications/newton.18.els"
From LRDE
(Created page with "{{Publication | published = true | date = 2017-04-05 | authors = Jim Newton, Didier Verna | title = Approaches in Typecase Optimization | booktitle = European Lisp Symposium |...") |
|||
(3 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
{{Publication |
{{Publication |
||
| published = true |
| published = true |
||
− | | date = |
+ | | date = 2018-04-05 |
| authors = Jim Newton, Didier Verna |
| authors = Jim Newton, Didier Verna |
||
| title = Approaches in Typecase Optimization |
| title = Approaches in Typecase Optimization |
||
| booktitle = European Lisp Symposium |
| booktitle = European Lisp Symposium |
||
| lrdekeywords = typechecking, Boolean functions, Binary decision diagrams |
| lrdekeywords = typechecking, Boolean functions, Binary decision diagrams |
||
− | | lrdenewsdate = |
+ | | lrdenewsdate = 2018-04-05 |
+ | | lrdepaper = http://www.lrde.epita.fr/dload/papers/newton.18.els.pdf |
||
− | | lrdestatus = accepted |
||
| lrdeprojects = Climb |
| lrdeprojects = Climb |
||
| address = Marbella, Spain |
| address = Marbella, Spain |
||
− | | abstract = We contrast two approaches to optimizing the Common Lisp typecase macro expansion. The first approach is based on heuristics intended to estimate run time performance of certain type checks involving Common Lisp type specifiers. The technique may, depending on code |
+ | | abstract = We contrast two approaches to optimizing the Common Lisp typecase macro expansion. The first approach is based on heuristics intended to estimate run time performance of certain type checks involving Common Lisp type specifiers. The technique may, depending on code size, exhaustively search the space of permutations of the type checks, intent on finding the optimal order. With the second technique, we represent a typecase form as a type specifierencapsulating the side-effecting non-Boolean parts so as to appear compatible with the Common Lisp type algebra operators. The encapsulated expressions are specially handled so that the Common Lisp type algebra functions preserve them, and we can unwrap them after a process of Boolean reduction into efficient Common Lisp codemaintaining the appropriate side effects but eliminating unnecessary type checks. Both approaches allow us to identify unreachable code, test for exhaustiveness of the clauses and eliminate type checks which are calculated to be redundant. |
− | | note = accepted |
||
| type = inproceedings |
| type = inproceedings |
||
| id = newton.18.els |
| id = newton.18.els |
||
Line 20: | Line 19: | ||
booktitle = <nowiki>{</nowiki>European Lisp Symposium<nowiki>}</nowiki>, |
booktitle = <nowiki>{</nowiki>European Lisp Symposium<nowiki>}</nowiki>, |
||
year = 2018, |
year = 2018, |
||
− | lrdestatus = accepted, |
||
address = <nowiki>{</nowiki>Marbella, Spain<nowiki>}</nowiki>, |
address = <nowiki>{</nowiki>Marbella, Spain<nowiki>}</nowiki>, |
||
month = apr, |
month = apr, |
||
Line 41: | Line 39: | ||
identify unreachable code, test for exhaustiveness of the |
identify unreachable code, test for exhaustiveness of the |
||
clauses and eliminate type checks which are calculated to |
clauses and eliminate type checks which are calculated to |
||
− | be redundant. |
+ | be redundant.<nowiki>}</nowiki> |
− | note = <nowiki>{</nowiki>accepted<nowiki>}</nowiki> |
||
<nowiki>}</nowiki> |
<nowiki>}</nowiki> |
||
Latest revision as of 19:08, 7 April 2023
- Authors
- Jim Newton, Didier Verna
- Where
- European Lisp Symposium
- Place
- Marbella, Spain
- Type
- inproceedings
- Projects
- Climb
- Keywords
- typechecking, Boolean functions, Binary decision diagrams
- Date
- 2018-04-05
Abstract
We contrast two approaches to optimizing the Common Lisp typecase macro expansion. The first approach is based on heuristics intended to estimate run time performance of certain type checks involving Common Lisp type specifiers. The technique may, depending on code size, exhaustively search the space of permutations of the type checks, intent on finding the optimal order. With the second technique, we represent a typecase form as a type specifierencapsulating the side-effecting non-Boolean parts so as to appear compatible with the Common Lisp type algebra operators. The encapsulated expressions are specially handled so that the Common Lisp type algebra functions preserve them, and we can unwrap them after a process of Boolean reduction into efficient Common Lisp codemaintaining the appropriate side effects but eliminating unnecessary type checks. Both approaches allow us to identify unreachable code, test for exhaustiveness of the clauses and eliminate type checks which are calculated to be redundant.
Documents
Bibtex (lrde.bib)
@InProceedings{ newton.18.els, author = {Jim Newton and Didier Verna}, title = {Approaches in Typecase Optimization}, booktitle = {European Lisp Symposium}, year = 2018, address = {Marbella, Spain}, month = apr, abstract = {We contrast two approaches to optimizing the Common Lisp typecase macro expansion. The first approach is based on heuristics intended to estimate run time performance of certain type checks involving Common Lisp type specifiers. The technique may, depending on code size, exhaustively search the space of permutations of the type checks, intent on finding the optimal order. With the second technique, we represent a typecase form as a type specifier, encapsulating the side-effecting non-Boolean parts so as to appear compatible with the Common Lisp type algebra operators. The encapsulated expressions are specially handled so that the Common Lisp type algebra functions preserve them, and we can unwrap them after a process of Boolean reduction into efficient Common Lisp code, maintaining the appropriate side effects but eliminating unnecessary type checks. Both approaches allow us to identify unreachable code, test for exhaustiveness of the clauses and eliminate type checks which are calculated to be redundant.} }