检索结果-内蒙古大学图书馆

Equational programming in lambda-calculus via SL-systems .1.

THEORETICAL COMPUTER SCIENCE 1996年第1-2期160卷 145-184页

作者： Tronci, E Dipartimento di Matematica Pura ed Applicata Università dell'Aquila Via Vetoio Coppito 67100 L'Aquila Italy

A system of equations in the lambda-calculus is a set of formulas of lambda (the equations) together with a finite set of variables of lambda (the unknowns). A system L is said to be beta-solvable (beta eta-solvable) iff there exists a simultaneous substitution with closed lambda-terms for the unknowns that makes the equations of L theorems in the theory beta (beta eta). A system L can be viewed as a set of specifications (the equations) for a finite set of programs (the unknowns) whereas a solution for L yields executable codes for such programs. A class G of systems for which the solvability problem is effectively decidable defines an equational programming language and a system solving algorithm for G defines a compiler for such language. This leads us to consider separation-like systems (SL-systems), i.e. systems with equations having form x (M) over right arrow = z, where x is an unknown and z is a free variable which is not an unknown. We show that the beta (beta eta)-solvability problem for SL-systems is undecidable. On the other hand we are able to define a class of SL-systems (regular SL-systems) for which the beta-solvability problem is decidable in Polynomial Time. Such class yields an equational programming language in which self-application is handled, constraints on executable code to be generated by the compiler can be specified by the user and (properties of) data structures can be described in an abstract way.

关键词： systems of equations in the lambda-calculus lambda-calculus equational programming functional programming automated synthesis of programs

来源：评论

学校读者我要写书评

暂无评论

Equational programming in lambda-calculus via SL-systems .2.

引用

THEORETICAL COMPUTER SCIENCE 1996年第1-2期160卷 185-216页

作者： Tronci, E Dipartimento di Matematica Pura ed Applicata Università dett'Aquila Via Vetoio Coppito 67100 L'Aquila Italy

A system of equations in the lambda-calculus is a set of formulas of lambda (the equations) together with a finite set of variables of lambda (the unknowns), A system L is said to be beta-solvable (beta eta-solvable) iff there exists a simultaneous substitution with closed lambda-terms for the unknowns that makes the equations of L theorems in the theory beta (beta eta). A system L can be viewed as a set of specifications (the equations) for a finite set of programs (the unknowns) whereas a solution for L yields executable codes for such programs. A class G of systems for which the solvability problem is effectively decidable defines an equational programming language and a system solving algorithm for G defines a compiler for such language. This leads us to consider separation-like systems (SL-systems), i.e. systems with equations having form x (M) over right arrow = z, where x is an unknown and z is a free variable which is not an unknown. It is known that the beta (beta eta)-solvability problem for SL-systems is undecidable. Here we show that there is a class of SL-systems (NP-regular SL-systems) for which the beta-solvability problem is NP-complete. Moreover, we show that any SL-system L can be transformed into an NP-regular SL-system L'. This transformation consists of adding abstractions to the LHS occurrences of the RHS variables of L. In this sense NP-regular SL-systems isolate the source of undecidability for SL-systems, namely: a shortage of abstractions on the LHS occurrences of the RHS variables. NP-regular SL-systems yield an equational programming language in which unrestrained self-application is handled, constraints on executable code to be generated by the compiler can be specified by the user and (properties of) data structures can be described in an abstract way. However, existence of executable code satisfying a specification in such language is an NP-complete problem. This is the price we have to pay for allowing unrestrained self-application in

关键词： systems of equations in the lambda-calculus lambda-calculus equational programming functional programming automated synthesis of programs

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：