Demand-Driven Higher-Order Fixpoint Iteration

    Publikation: Working paperForskning

    Resumé

    Our aim is to show that techniques from higher-order strictness analysis may be used as a general algorithmic principle in a functional programming language. Certain problems may be expressed as the search for the least solution that satisfy certain given properties. This is often done using some kind of fixpoint iteration. We will present a fixpoint operation that can be used for second-order functions and extend this to higher-order functions. The technique is based on using partial function graphs to represent higher-order objects. The main problem in finding fixpoints for higher-order functions is to establish a notion of {\em neededness} so as to restrict the iteration to those parts of the function that may influence the result. This is here done through a uniform extension of the domain of values with need information. The result is an iteration strategy which will terminate if base domains are finite.
    OriginalsprogEngelsk
    Udgivelses stedRoskilde
    UdgiverRoskilde Universitet
    Antal sider15
    StatusUdgivet - 2005

    Citer dette

    Rosendahl, M. (2005). Demand-Driven Higher-Order Fixpoint Iteration. Roskilde: Roskilde Universitet.
    Rosendahl, Mads. / Demand-Driven Higher-Order Fixpoint Iteration. Roskilde : Roskilde Universitet, 2005.
    @techreport{144a293052be11dba4bc000ea68e967b,
    title = "Demand-Driven Higher-Order Fixpoint Iteration",
    abstract = "Our aim is to show that techniques from higher-order strictness analysis may be used as a general algorithmic principle in a functional programming language. Certain problems may be expressed as the search for the least solution that satisfy certain given properties. This is often done using some kind of fixpoint iteration. We will present a fixpoint operation that can be used for second-order functions and extend this to higher-order functions. The technique is based on using partial function graphs to represent higher-order objects. The main problem in finding fixpoints for higher-order functions is to establish a notion of {\em neededness} so as to restrict the iteration to those parts of the function that may influence the result. This is here done through a uniform extension of the domain of values with need information. The result is an iteration strategy which will terminate if base domains are finite.",
    author = "Mads Rosendahl",
    year = "2005",
    language = "English",
    publisher = "Roskilde Universitet",
    type = "WorkingPaper",
    institution = "Roskilde Universitet",

    }

    Rosendahl, M 2005 'Demand-Driven Higher-Order Fixpoint Iteration' Roskilde Universitet, Roskilde.

    Demand-Driven Higher-Order Fixpoint Iteration. / Rosendahl, Mads.

    Roskilde : Roskilde Universitet, 2005.

    Publikation: Working paperForskning

    TY - UNPB

    T1 - Demand-Driven Higher-Order Fixpoint Iteration

    AU - Rosendahl, Mads

    PY - 2005

    Y1 - 2005

    N2 - Our aim is to show that techniques from higher-order strictness analysis may be used as a general algorithmic principle in a functional programming language. Certain problems may be expressed as the search for the least solution that satisfy certain given properties. This is often done using some kind of fixpoint iteration. We will present a fixpoint operation that can be used for second-order functions and extend this to higher-order functions. The technique is based on using partial function graphs to represent higher-order objects. The main problem in finding fixpoints for higher-order functions is to establish a notion of {\em neededness} so as to restrict the iteration to those parts of the function that may influence the result. This is here done through a uniform extension of the domain of values with need information. The result is an iteration strategy which will terminate if base domains are finite.

    AB - Our aim is to show that techniques from higher-order strictness analysis may be used as a general algorithmic principle in a functional programming language. Certain problems may be expressed as the search for the least solution that satisfy certain given properties. This is often done using some kind of fixpoint iteration. We will present a fixpoint operation that can be used for second-order functions and extend this to higher-order functions. The technique is based on using partial function graphs to represent higher-order objects. The main problem in finding fixpoints for higher-order functions is to establish a notion of {\em neededness} so as to restrict the iteration to those parts of the function that may influence the result. This is here done through a uniform extension of the domain of values with need information. The result is an iteration strategy which will terminate if base domains are finite.

    M3 - Working paper

    BT - Demand-Driven Higher-Order Fixpoint Iteration

    PB - Roskilde Universitet

    CY - Roskilde

    ER -

    Rosendahl M. Demand-Driven Higher-Order Fixpoint Iteration. Roskilde: Roskilde Universitet. 2005.