View in EDS

Typing termination in a higher-order concurrent imperative language

Saved in:
Bibliographic Details
Title: Typing termination in a higher-order concurrent imperative language
Authors: Boudol, Gérard1 gbo@sophia.inria.fr
Source: Information & Computation. Jun2010, Vol. 208 Issue 6, p716-736. 21p.
Subjects: Imperative programming, Concurrent Aggregates (Computer program language), Computer software termination, ML (Computer program language), Recursion theory, Mathematical analysis
Abstract: Abstract: We propose means to predict termination in a higher-order imperative and concurrent language à la ML. We follow and adapt the classical method for proving termination in typed formalisms, namely the realizability technique. There is a specific difficulty with higher-order state, which is that one cannot define a realizability interpretation simply by induction on types, because applying a function may have side-effects at types not smaller than the type of the function. Moreover, such higher-order side-effects may give rise to computations that diverge without resorting to explicit recursion. We overcome these difficulties by introducing a type and effect system for our language that enforces a stratification of the memory. The stratification prevents the circularities in the memory that may cause divergence, and allows us to define a realizability interpretation of the types and effects, which we then use to establish that typable sequential programs in our system are guaranteed to terminate, unless they use explicit recursion in a divergent way. We actually prove a more general fairness property, that is, any typable thread yields the scheduler after some finite computation. Our realizability interpretation also copes with dynamic thread creation. [Copyright &y& Elsevier]
Copyright of Information & Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 50734146
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Typing termination in a higher-order concurrent imperative language
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Boudol%2C+Gérard%22">Boudol, Gérard</searchLink><relatesTo>1</relatesTo><i> gbo@sophia.inria.fr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Information+%26+Computation%22">Information & Computation</searchLink>. Jun2010, Vol. 208 Issue 6, p716-736. 21p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Imperative+programming%22">Imperative programming</searchLink><br /><searchLink fieldCode="DE" term="%22Concurrent+Aggregates+%28Computer+program+language%29%22">Concurrent Aggregates (Computer program language)</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software+termination%22">Computer software termination</searchLink><br /><searchLink fieldCode="DE" term="%22ML+%28Computer+program+language%29%22">ML (Computer program language)</searchLink><br /><searchLink fieldCode="DE" term="%22Recursion+theory%22">Recursion theory</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+analysis%22">Mathematical analysis</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Abstract: We propose means to predict termination in a higher-order imperative and concurrent language à la ML. We follow and adapt the classical method for proving termination in typed formalisms, namely the realizability technique. There is a specific difficulty with higher-order state, which is that one cannot define a realizability interpretation simply by induction on types, because applying a function may have side-effects at types not smaller than the type of the function. Moreover, such higher-order side-effects may give rise to computations that diverge without resorting to explicit recursion. We overcome these difficulties by introducing a type and effect system for our language that enforces a stratification of the memory. The stratification prevents the circularities in the memory that may cause divergence, and allows us to define a realizability interpretation of the types and effects, which we then use to establish that typable sequential programs in our system are guaranteed to terminate, unless they use explicit recursion in a divergent way. We actually prove a more general fairness property, that is, any typable thread yields the scheduler after some finite computation. Our realizability interpretation also copes with dynamic thread creation. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Information & Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=50734146
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.ic.2009.06.007
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 21
        StartPage: 716
    Subjects:
      – SubjectFull: Imperative programming
        Type: general
      – SubjectFull: Concurrent Aggregates (Computer program language)
        Type: general
      – SubjectFull: Computer software termination
        Type: general
      – SubjectFull: ML (Computer program language)
        Type: general
      – SubjectFull: Recursion theory
        Type: general
      – SubjectFull: Mathematical analysis
        Type: general
    Titles:
      – TitleFull: Typing termination in a higher-order concurrent imperative language
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Boudol, Gérard
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 06
              Text: Jun2010
              Type: published
              Y: 2010
          Identifiers:
            – Type: issn-print
              Value: 08905401
          Numbering:
            – Type: volume
              Value: 208
            – Type: issue
              Value: 6
          Titles:
            – TitleFull: Information & Computation
              Type: main
ResultId 1