Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Unfolding of Programs with Nondeterminism
Number of Authors: 1
1994 (English)Report (Refereed)
Abstract [en]

In LIsper: "Total Unfolding: Theory and Applications" some results were proved regarding properties of unfolding of purely functional programs. Especially, a theorem was shown that relates the termination of symbolic evaluation of a "less instantiated" term relative to the termination of a "more instantiated" term. An application is partial evaluation, where unfolding of function definitions is frequently performed to enable further simplifications of the resulting specialized program. The unfolding must then be kept under control to ensure that the partial evaluation terminates. In this paper, we extend the termination result from purely functional programs programs with nondeterministic operations. We give an operational semantics where the behaviour of operators is defined through rewrite rules: nondeterminism then occurs when the resulting term rewriting system is nonconfluent. For the confluent part, the previous termination results carry over. It is, however, not guaranteed in general that the resulting unfolded program has the same semantics as the original program. We give conditions on the rewrite rules that guarantee that both versions have the same semantics, and we show that they apply to a nontrivial class of nondeterministic languages.

Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 1994, 1.
Series
SICS Research Report, ISSN 0283-3638 ; R94:02
Keyword [en]
nondeterminism, unfolding, recursive programs, term rewriting
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-21376OAI: oai:DiVA.org:ri-21376DiVA: diva2:1041412
Available from: 2016-10-31 Created: 2016-10-31Bibliographically approved

Open Access in DiVA

No full text

Other links

fulltext
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.26.0