An implementation of syntax directed functional programming on nested-stack machines View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1992-07

AUTHORS

Heinz Fassbender, Heiko Vogler

ABSTRACT

This paper contributes to the field of functional programming languages. We investigate the call-by-name and call-by-need implementation of a restricted type of functional programming, calledsyntax directed functional programming; the target of this implementation is an abstract machine that is based on nested stacks. In fact, the technical kernel of this paper is a refinement of an automata theoretical result that, roughly speaking, investigates the well-known relationship “recursion = iteration + stack” in the framework of tree transducers. More precisely, in the underlying result the class of functions computed by total deterministic macro tree-to-string transducers with the call-by-name computation strategy is characterized by total deterministic checking-tree nested-stack transducers. Note that total deterministic macro tree-to-string transducers are term rewriting systems by means of which the reduction semantics of syntax directed functional programming languages can be described. More... »

PAGES

341-375

References to SciGraph publications

  • 1975-06. Bottom-up and top-down tree transformations— a comparison in THEORY OF COMPUTING SYSTEMS
  • 1982. The SRDL specification experiment in PROGRAM SPECIFICATION
  • 1990. Graph-based implementation of a functional logic language in ESOP '90
  • 1990. Parallele Implementierung funktionaler Programmiersprachen in NONE
  • <error retrieving object. in <ERROR RETRIEVING OBJECT
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01211311

    DOI

    http://dx.doi.org/10.1007/bf01211311

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1021650925


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Lehrstuhl f\u00fcr Informatik II, RWTH Aachen, Aachen, Germany", 
              "id": "http://www.grid.ac/institutes/grid.1957.a", 
              "name": [
                "Lehrstuhl f\u00fcr Informatik II, RWTH Aachen, Aachen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fassbender", 
            "givenName": "Heinz", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Lehrstuhl f\u00fcr Informatik II, RWTH Aachen, Aachen, Germany", 
              "id": "http://www.grid.ac/institutes/grid.1957.a", 
              "name": [
                "Lehrstuhl f\u00fcr Informatik II, RWTH Aachen, Aachen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vogler", 
            "givenName": "Heiko", 
            "id": "sg:person.014562633673.93", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-52592-0_69", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034083248", 
              "https://doi.org/10.1007/3-540-52592-0_69"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-75332-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045461842", 
              "https://doi.org/10.1007/978-3-642-75332-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-11490-4_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028249143", 
              "https://doi.org/10.1007/3-540-11490-4_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01704020", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006876172", 
              "https://doi.org/10.1007/bf01704020"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1992-07", 
        "datePublishedReg": "1992-07-01", 
        "description": "This paper contributes to the field of functional programming languages. We investigate the call-by-name and call-by-need implementation of a restricted type of functional programming, calledsyntax directed functional programming; the target of this implementation is an abstract machine that is based on nested stacks. In fact, the technical kernel of this paper is a refinement of an automata theoretical result that, roughly speaking, investigates the well-known relationship \u201crecursion = iteration + stack\u201d in the framework of tree transducers. More precisely, in the underlying result the class of functions computed by total deterministic macro tree-to-string transducers with the call-by-name computation strategy is characterized by total deterministic checking-tree nested-stack transducers. Note that total deterministic macro tree-to-string transducers are term rewriting systems by means of which the reduction semantics of syntax directed functional programming languages can be described.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01211311", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136737", 
            "issn": [
              "0934-5043", 
              "1433-299X"
            ], 
            "name": "Formal Aspects of Computing", 
            "publisher": "Association for Computing Machinery (ACM)", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "4"
          }
        ], 
        "keywords": [
          "functional programming language", 
          "functional programming", 
          "programming language", 
          "abstract machine", 
          "need implementation", 
          "computation strategy", 
          "reduction semantics", 
          "implementation", 
          "programming", 
          "machine", 
          "language", 
          "restricted type", 
          "syntax", 
          "tree transducers", 
          "string transducers", 
          "semantics", 
          "calls", 
          "stack", 
          "kernel", 
          "recursion", 
          "iteration", 
          "framework", 
          "trees", 
          "theoretical results", 
          "class of functions", 
          "system", 
          "refinement", 
          "results", 
          "field", 
          "name", 
          "class", 
          "strategies", 
          "terms", 
          "means", 
          "types", 
          "fact", 
          "function", 
          "target", 
          "relationship", 
          "transducer", 
          "paper"
        ], 
        "name": "An implementation of syntax directed functional programming on nested-stack machines", 
        "pagination": "341-375", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1021650925"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01211311"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01211311", 
          "https://app.dimensions.ai/details/publication/pub.1021650925"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:19", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_257.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01211311"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01211311'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01211311'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01211311'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01211311'


     

    This table displays all metadata directly associated to this object as RDF triples.

    125 TRIPLES      22 PREDICATES      72 URIs      59 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01211311 schema:about anzsrc-for:08
    2 anzsrc-for:0803
    3 schema:author Nb99adba1081041be8b447b9ac0f8dc3e
    4 schema:citation sg:pub.10.1007/3-540-11490-4_19
    5 sg:pub.10.1007/3-540-52592-0_69
    6 sg:pub.10.1007/978-3-642-75332-9
    7 sg:pub.10.1007/bf01695769
    8 sg:pub.10.1007/bf01704020
    9 schema:datePublished 1992-07
    10 schema:datePublishedReg 1992-07-01
    11 schema:description This paper contributes to the field of functional programming languages. We investigate the call-by-name and call-by-need implementation of a restricted type of functional programming, calledsyntax directed functional programming; the target of this implementation is an abstract machine that is based on nested stacks. In fact, the technical kernel of this paper is a refinement of an automata theoretical result that, roughly speaking, investigates the well-known relationship “recursion = iteration + stack” in the framework of tree transducers. More precisely, in the underlying result the class of functions computed by total deterministic macro tree-to-string transducers with the call-by-name computation strategy is characterized by total deterministic checking-tree nested-stack transducers. Note that total deterministic macro tree-to-string transducers are term rewriting systems by means of which the reduction semantics of syntax directed functional programming languages can be described.
    12 schema:genre article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N0b2706df0c2e440a97645d30ef02a787
    16 N1c4047ca80ad40c19e0ea1f1b1a02583
    17 sg:journal.1136737
    18 schema:keywords abstract machine
    19 calls
    20 class
    21 class of functions
    22 computation strategy
    23 fact
    24 field
    25 framework
    26 function
    27 functional programming
    28 functional programming language
    29 implementation
    30 iteration
    31 kernel
    32 language
    33 machine
    34 means
    35 name
    36 need implementation
    37 paper
    38 programming
    39 programming language
    40 recursion
    41 reduction semantics
    42 refinement
    43 relationship
    44 restricted type
    45 results
    46 semantics
    47 stack
    48 strategies
    49 string transducers
    50 syntax
    51 system
    52 target
    53 terms
    54 theoretical results
    55 transducer
    56 tree transducers
    57 trees
    58 types
    59 schema:name An implementation of syntax directed functional programming on nested-stack machines
    60 schema:pagination 341-375
    61 schema:productId N2361e55cb9ab4e24adb721e71d183a45
    62 N330201148bc947908060d857aa5cbb76
    63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021650925
    64 https://doi.org/10.1007/bf01211311
    65 schema:sdDatePublished 2022-05-20T07:19
    66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    67 schema:sdPublisher Nf677b838cd2f46999128742364f9ea38
    68 schema:url https://doi.org/10.1007/bf01211311
    69 sgo:license sg:explorer/license/
    70 sgo:sdDataset articles
    71 rdf:type schema:ScholarlyArticle
    72 N0b2706df0c2e440a97645d30ef02a787 schema:issueNumber 4
    73 rdf:type schema:PublicationIssue
    74 N1c4047ca80ad40c19e0ea1f1b1a02583 schema:volumeNumber 4
    75 rdf:type schema:PublicationVolume
    76 N2361e55cb9ab4e24adb721e71d183a45 schema:name doi
    77 schema:value 10.1007/bf01211311
    78 rdf:type schema:PropertyValue
    79 N330201148bc947908060d857aa5cbb76 schema:name dimensions_id
    80 schema:value pub.1021650925
    81 rdf:type schema:PropertyValue
    82 N718568d1a69446fbac93db22e9e2770a schema:affiliation grid-institutes:grid.1957.a
    83 schema:familyName Fassbender
    84 schema:givenName Heinz
    85 rdf:type schema:Person
    86 Nb99adba1081041be8b447b9ac0f8dc3e rdf:first N718568d1a69446fbac93db22e9e2770a
    87 rdf:rest Ne79a5758ef1a4f99a33a1a9f29b14c5c
    88 Ne79a5758ef1a4f99a33a1a9f29b14c5c rdf:first sg:person.014562633673.93
    89 rdf:rest rdf:nil
    90 Nf677b838cd2f46999128742364f9ea38 schema:name Springer Nature - SN SciGraph project
    91 rdf:type schema:Organization
    92 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Information and Computing Sciences
    94 rdf:type schema:DefinedTerm
    95 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Computer Software
    97 rdf:type schema:DefinedTerm
    98 sg:journal.1136737 schema:issn 0934-5043
    99 1433-299X
    100 schema:name Formal Aspects of Computing
    101 schema:publisher Association for Computing Machinery (ACM)
    102 rdf:type schema:Periodical
    103 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.1957.a
    104 schema:familyName Vogler
    105 schema:givenName Heiko
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
    107 rdf:type schema:Person
    108 sg:pub.10.1007/3-540-11490-4_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028249143
    109 https://doi.org/10.1007/3-540-11490-4_19
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/3-540-52592-0_69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034083248
    112 https://doi.org/10.1007/3-540-52592-0_69
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-3-642-75332-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045461842
    115 https://doi.org/10.1007/978-3-642-75332-9
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/bf01695769 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033919759
    118 https://doi.org/10.1007/bf01695769
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/bf01704020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006876172
    121 https://doi.org/10.1007/bf01704020
    122 rdf:type schema:CreativeWork
    123 grid-institutes:grid.1957.a schema:alternateName Lehrstuhl für Informatik II, RWTH Aachen, Aachen, Germany
    124 schema:name Lehrstuhl für Informatik II, RWTH Aachen, Aachen, Germany
    125 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...