A Method for Implementing Functional Programming Languages

一种函数式编程语言的实现方法

基本信息

项目摘要

The purpose of this project is to propose a new method for implementing functional programming languages and to study algorithmic aspects of this method from the complexity viewpoint.In 1979 D.A. Turner applied combinators to a certain practical system for evaluating lambda expressions. His system is not quite efficient in the sense that the space complexity of output is at least quadratic in n, where n is the length of input expressions. In 1985 the author presented a new method for representing combinator graphs in O(n log n) space.In this project another new efficient method called BC-chains is proposed, which requires only linear space in n even in the worst case. Provided the normal order reduction is assumed, this leads to a new reduction algorithm, which can be proved to run as efficiently as the standard normal order reduction algorithm even in the worst case. In fact, in some computing experiment, this algorithm is reported to run at least as fast as the standard one in the average sense as well.For translating input expressions to combinator graphs, a new algorithm is devised, which runs in O(n log n) time in the worst case. The space complexity of this algorithm can be proved to be O(n log n).The report of this project describes the details of all the algorithms mentioned above, which constitute the complete set of basic algorithms for translation as well as for execution. The report also contains some theoretical results on the complexity of related problems.
该项目的目的是提出一种实现函数式编程语言的新方法,并从复杂性的角度研究这种方法的算法方面。1979年,D.A. Turner将组合子应用于某个实际系统,以评估lambda表达式。他的系统不是很有效,因为输出的空间复杂度至少是n的二次方,其中n是输入表达式的长度。1985年,作者提出了一种在O(nlogn)空间中表示组合子图的新方法,本项目提出了另一种称为BC-链的新方法,它即使在最坏的情况下也只需要n中的线性空间。假设正常阶约简,这将导致一个新的约简算法,可以证明即使在最坏的情况下,它也能像标准正常阶约简算法一样有效地运行。实际上,在一些计算实验中,该算法的平均运行速度至少与标准算法一样快。对于将输入表达式转换为组合子图,设计了一种新的算法,在最坏情况下,该算法的运行时间为O(nlog n)。该算法的空间复杂度为O(nlogn),该项目的报告详细描述了上述所有算法,构成了完整的翻译和执行基本算法集。该报告还载有一些关于相关问题复杂性的理论结果。

项目成果

期刊论文数量(11)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
K. Noshita and T. Hikita: "The BC-chain method for representing combinators in linear space" New Generation Computing J.3. 131-144 (1985)
K. Noshita 和 T. Hikita:“在线性空间中表示组合器的 BC 链方法”新一代计算 J.3。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
K.Noshita;T.Hikita: New Generation Computing J.3. 131-144 (1985)
K.Noshita;T.Hikita:新一代计算 J.3。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
K. Noshita and X.-X. He: "A fast algorithm for translating combinator expressions with BC-chains" (1987)
K. Noshita 和 X.-X。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
野下浩平: 情報処理. 27. 111-119 (1986)
Kohei Noshita:信息处理。27。111-119(1986)
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

NOSHITA Kohei其他文献

NOSHITA Kohei的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('NOSHITA Kohei', 18)}}的其他基金

Searching algorithms with transposition tables and their applications
转置表搜索算法及其应用
  • 批准号:
    15500021
  • 财政年份:
    2003
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Application of game-tree searching algorithms to parallel selection
博弈树搜索算法在并行选择中的应用
  • 批准号:
    12680337
  • 财政年份:
    2000
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Design and Evaluation of a Distributed Shared-Hashing Mechanism for Searching Game-Trees in Parallel
并行搜索博弈树的分布式共享哈希机制的设计与评估
  • 批准号:
    10680340
  • 财政年份:
    1998
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)

相似海外基金

Distributed Combinator Reduction (Computer Research)
分布式组合器缩减(计算机研究)
  • 批准号:
    8302018
  • 财政年份:
    1983
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了