Polynomial-Time Optimal Pretty-Printing Combinators with Choice

Anton Podkopaev, Dmitri Boulytchev

Research output

Abstract

We describe pretty-printing combinators with choice which provide optimal document layout in polynomial time. Bottom-up tree rewriting and dynamic programming (BURS) is used to calculate a set of possible layouts for a given output width. We also present the results of suggested approach evaluation and discuss its application for the implementation of pretty-printers.
Original languageEnglish
Pages (from-to)257-265
JournalLecture Notes in Computer Science
Volume8974
DOIs
Publication statusPublished - 2015

Fingerprint

Dynamic programming
Printing
Layout
Polynomial time
Polynomials
Rewriting
Bottom-up
Dynamic Programming
Calculate
Output
Evaluation

Cite this

@article{236a4c2a5cb2430a8993779b70b8c0b2,
title = "Polynomial-Time Optimal Pretty-Printing Combinators with Choice",
abstract = "We describe pretty-printing combinators with choice which provide optimal document layout in polynomial time. Bottom-up tree rewriting and dynamic programming (BURS) is used to calculate a set of possible layouts for a given output width. We also present the results of suggested approach evaluation and discuss its application for the implementation of pretty-printers.",
keywords = "Pretty-printing, Combinators, Bottom-up rewriting systems",
author = "Anton Podkopaev and Dmitri Boulytchev",
year = "2015",
doi = "10.1007/978-3-662-46823-4_21",
language = "English",
volume = "8974",
pages = "257--265",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer",

}

TY - JOUR

T1 - Polynomial-Time Optimal Pretty-Printing Combinators with Choice

AU - Podkopaev, Anton

AU - Boulytchev, Dmitri

PY - 2015

Y1 - 2015

N2 - We describe pretty-printing combinators with choice which provide optimal document layout in polynomial time. Bottom-up tree rewriting and dynamic programming (BURS) is used to calculate a set of possible layouts for a given output width. We also present the results of suggested approach evaluation and discuss its application for the implementation of pretty-printers.

AB - We describe pretty-printing combinators with choice which provide optimal document layout in polynomial time. Bottom-up tree rewriting and dynamic programming (BURS) is used to calculate a set of possible layouts for a given output width. We also present the results of suggested approach evaluation and discuss its application for the implementation of pretty-printers.

KW - Pretty-printing

KW - Combinators

KW - Bottom-up rewriting systems

U2 - 10.1007/978-3-662-46823-4_21

DO - 10.1007/978-3-662-46823-4_21

M3 - Article

VL - 8974

SP - 257

EP - 265

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -