用于声明性数据脚本语言的类型系统的制作方法

专利名称：：用于声明性数据脚本语言的类型系统的制作方法
技术领域：
：本主题公开内容一般地涉及用于声明性数据脚本语言的有表现力的、紧凑的且灵活的类型系统。背景作为一般的背景，脚本语言是控制软件系统、应用程序和程序的编程语言。脚本常常被不同于“程序”对待，它独立于其他应用程序而执行。另外，脚本可以不同于应用程序的“核心代码”，它可以用不同的语言来写成。脚本可以由开发者或其他程序以源格式或目标格式来编写，它覆盖了在人类友好或机器友好或均不友好的方面的全部范围。当最终用户可访问时，脚本允许应用程序的行为适应用户的需要。还可以从源代码解释脚本，或被“半编译”成字节码或被解释的另一机器友好的格式。脚本语言还可以被嵌入在它们与之关联的应用程序中。对于进一步的背景，类型系统定义编程语言如何将值和表达式分类成类型、它可以如何操纵那些类型和它们如何交互。类型将值或一组值标识为具有成特定的含义或目的，尽管诸如抽象类型和函数类型等的一些类型可以不被表示成执行的程序中的值。类型系统在各语言之间显著地不同，例如，连同其他种类的差异一起，类型系统可以随它们的编译时语法和运行时操作实现而不同。对于如何使用各类型的示例，编译器可以使用静态类型的值来优化存储以及用于对该值的操作的算法选择。在许多C编译器中，例如，根据单精度浮点数的公认的标准，以32位来表示标称(nominal)类型化的“浮点”数据类型。C因而对那些值使用浮点专用的操作，例如，浮点加、乘等等。另外，类型约束条件的深度以及它们的评估的方式可以影响语言的类型化。在一些情况中，开发者即人类创建定义源代码的文本，编译器将该语言翻译成一种或多种机器友好的格式以供给定的平台执行目标代码。在其他情况中，应用程序或机器本身可以生成代码以供跨越数据存储执行，在代码生成时不涉及人类。在任一种情况中，期望保持语言紧凑但也高度有表现力的和合乎逻辑的高效的、合乎逻辑的且有表现力的类型系统，以使得可以连同高效的存储表示一起生成高效的和结构紧凑的数据密集的应用程序。然而，常规的编程语言的类型系统对于大规模数据处理和消费的复杂性来说不是足够通用和足够灵活的。简而言之，当涉及大量的数据时，类型系统的任何复杂性或灵活性的缺乏以及所关联的低效率会按指数或不成比例地放大。因此，当大量的数据被存储在数据库中时，例如当一组服务器计算机在长时间段内收集大量数据的记录或事务时，开发者、其他计算机、其他应用程序等等可能希望经由一个或多个脚本访问数据或数据的有针对性的子集。编程类型构造这样的脚本的效率和所得到的数据结构的可被表示的得到的简单性变成重要的目标，尤其是在这样的脚本针对巨量的数据而操作时。举例来说，可能希望经由一个或多个方法、脚本或程序查询一些数据的某个子集、读取或写入数据、更新数据或对数据应用任何其他处理。给定计算领域中的数据值的多样性，丰富地和高效地表达类型的能力可以显著地改善数据密集的应用程序和程序的所得到的性能。因而存在对带有解决用于大规模数据处理系统的当前类型系统的这些和其他不足的类型系统的编程语言的长期需求。上面所描述的编程语言的当前类型系统的背景信息和不足仅仅旨在提供常规系统的背景信息和问题中的一些的一般概览，且不旨在是详尽的。常规系统的其他问题和在此描述的各种非限制性实施例的相应益处可以在查看下列描述后变得进一步明显。概述在此提供简化的概述以便帮助允许对在更详细的描述和附图中出现的示例性的、非限制性的实施例的各种方面的基本理解或一般理解。然而，本
发明内容不旨在作为广泛概览或详尽概览。相反，本
发明内容的唯一目的是作为后续各个实施例的更详细的描述的序言而以简化形式呈现与一些示例性非限制性实施例相关的一些概念。提供高效的、合乎逻辑的且有表现力的类型系统的各个实施例，以便用于灵活地定义声明性编程语言的类型，使得可以生成高效的且结构上紧凑的数据密集的应用程序。在一个非限制性方面中，该类型系统支持精化(refinement)类型和类型成员表达式的组合。连同其他非限制性的方面一起，与包括所有有效值作为成员的顶端类型(toptype)组合，各类型可以被表示成其他类型的交和/或并。因而，可以为在真实世界数据的大规模集合中存在的全部数据类型高效地表示类型。下面更详细地描述这些和其他实施例。附图简述参考附图进一步描述各种非限制性的实施例，附图中图1是用于声明性编程语言和相关结构的编译过程链的框图；图2是阐释在此描述的一个或多个实施例中的类型系统的示例性方面的第一框图；图3是阐释在此描述的一个或多个实施例中的类型系统的示例性方面的第二框图；图4是阐释在此描述的一个或多个实施例中的类型系统的示例性方面的第三框图；图5是阐释能够实现两个或更多个类型的交的类型系统的框图；图6是阐释能够联结两个或更多类型或执行两个或更多类型的并操作的类型系统的框图；图7是阐释具有对空类型来说可否定(negatable)的顶端类型的类型系统的框图；图8是阐释按照一实施例用于根据包括支持类型精化和类型成员的类型系统的声明性编程模型来定义声明性代码的过程的流程图；图9是根据一实施例用于根据具有复杂类型系统的声明性编程模型来执行声明性代码的计算系统的框图；图10是阐释根据一实施例用于由计算设备的至少一个处理器执行声明性代码的过程的流程图；图11是用于由实施例封装的声明性模型的示例性过程链；图12是与面向记录的执行模型相关联的类型系统的阐释；图13是按照一实施例与基于约束的执行模型相关联的类型系统的非限制性阐释；图14是根据经排序的执行模型的数据存储的阐释；图15是根据次序无关的执行模型的数据存储的非限制性的阐释；图16是表示其中可以实现在此描述的各个实施例的示例性非限制性网络化环境的框图；以及图17是表示其中可以实现在此描述的各个实施例的一个或多个方面的示例性非限制性的计算系统或操作环境的框图。详细描述概览如背景中所讨论，常规类型系统具有限制所得到的程序的可表达性且限制所得到的存储结构和算法处理的效率的某些复杂性和不灵活性等。当大规模执行例如结合大规模数据存储和处理系统执行时，尤其感受到常规系统的这样的不足。D是由微软设计的编程语言，它很适合于编写数据密集的程序。D的类型化系统支持允许语言可表达性的协作的唯一特征的组合，语言可表达性包括但不限于表达程序的两个或更多个不同类型的并和/或交的能力。举例来说，在一个实施例中，该类型系统支持精化类型和类型成员表达式的组合。该类型系统还包括包含所有有效值作为成员的顶端类型。作为用于在此相对于声明性编程模型和语言的上述类型系统陈述的各个实施例的上下文而提供D编程语言。然而，应明白，在此描述的各个实施例可以被应用到关于其编程构件和其他定义特性具有与D相同的或相似的能力的任何声明性编程语言。在这一点上，常常希望用声明性编程语言编写源代码，声明性编程语言常常被认为是命令性编程语言的对应物。不像命令性编程语言，声明性编程语言允许用户写下他们想要从他们的数据得到什么且不必指定针对给定的技术或平台如何满足那些希望。因而，在此预期一个或多个实施例中陈述的包括类型系统的任何声明性语言，而不只是以D编程语言为基础的各实施例，尽管D是示例性伪代码和概念阐释的合适的源。在这一点上，在下面给出关于D编程语言的更多细节，D编程语言是很适合于紧凑的且人类可理解的表示的声明性编程语言，且有利地包括用于创建和修改数据密集的应用程序的有效构件，而独立于无论是闪存、关系数据库、RAM、外部驱动器、网络驱动器等等的底层存储机制，“D”有时还被称为“M”编程语言，尽管出于一致性，在此不使用对M的引用。D包括用于编写声明性源代码的高效的和紧凑的语法，包括具有准许将该语言用于例如数据密集的应用程序的性能的类型系统。更具体地，在此所描述的类型系统允许使用有表现力的类型系统来静态地验证数据密集的应用程序。在这一点上，在一个实施例中，将“顶端”类型(在D中写成Any(任何))、精化类型(其中类型可以由任意的布尔表达式限定)组合起来，并将类型测试表达式包括在精化表达式语言中。用于数据脚本语言的类型系统下面陈述关于用于数据脚本语言的类型系统的各实施例的另外的细节，但是首先在图1中阐释关于根据D编译链可表示和使用D程序的不同方式的某种上下文。举例来说，源代码100可以直接由开发者或机器撰写。源代码100可以由D编译器110编译，D编译器Iio包括例如用于分析源代码100的D语法分析程序120和用于形成D句法树的D句法树组件130，然后可以分析D句法树并将其变换成D图结构140。D图结构140可以由开发者直接生成，且还可由应用程序生成，并以紧凑方式表示。D图结构140可以被解开成树130并回退到源代码100，且根据诸如SQL数据库查询、企业数据管理(EDM)、电子表格应用程序、图形应用程序等的各种域专用的使用150(即可以存储和分析数据的任何地方)，D图结构140可以被编译或半编译成与数据密集的应用程序结合的目标代码。诸如D编程语言等的类型化语言是指该语言的变量可以假设的值域是有界的概念。这样的值域的上界被称为类型。类型系统是记住变量的类型且一般地记住程序中的所有表达式的类型的类型化语言的组件。可以在“D”中指定和检查的各类型不被常规系统所允许，且下面更详细地描述这样的类型。如所提到的，在各种非限制性的实施例中，本发明提供用于数据脚本语言的类型系统，该类型系统组合精化类型和精化语言的类型测试表达式，以便允许简单但丰富的类型语言。在一个实施例中，支持顶端类型，顶端类型与精化类型和精化语言的类型测试表达式的组合得到该类型语言的进一步的表达性。使用此有表现力的类型系统，可以静态地验证数据密集的应用程序。如图2的框图中所示出，在一个实施例中，诸如D编程语言等的声明性编程语言包括形成程序的部分的各种编程构件200。系统、应用程序、服务可以指定这样的构件200或针对(诸)数据存储260作为D程序而执行它们，以便取得数据密集的结果。在一个非限制性的方面中，编程构件200下的编程模型的类型系统250包括对各精化类型210的组合和在精化类型210的表达式内的类型成员评估220的支持。在这一点上，各精化类型的组合和对在精化类型表达式内的类型成员评估的支持不受常规系统支持。如图3的框图中所示出，除了类型系统250的能力之外，类型系统350还可以包括包含所有有效值330的顶端类型。换句话说，顶端类型是在具有顶端类型的编程模型中出现的任何类型中最少受约束的类型。如图4的框图中所示出，可选地，除了其他能力之外，类型系统450还可以包括对作为类型的值420以及作为值的类型410的支持。“D”中的类型包括诸如整数、文本和逻辑等的典型原始类型、以及被写成f(意指类型T的值的集合)的集合类型、以及被写成{11:T1，...，1η:Τη}(意指带有分别为类型Tl，...，Tn的字段11，...，In的实体)的实体或记录类型。在上面所描述的用于数据脚本语言的类型系统的一种实现中，类型系统支持被写成Any的“顶端”类型。所有有效的D值是此“最少受约束”类型的值。另外，支持精化类型，精化类型可以被写成{值TIe}，其中值是标识符，T是类型且e是布尔值表达式，例如，用于精化类型的“D”语法简单地是“Twheree(当e为真时的Τ)”。这样的类型的值是其布尔表达式e等于真的类型T的有效“D”值。例如，值42是类型{χ=Integer(整数)|x>41}的成员，这是因为值42是类型整数且由于42确实大于41而满足测试χ>41。对于其它示例，值43也是此类型的成员，但40不是。另外，类型系统支持精化的布尔值表达式。支持“与”、“或”、“非”、“暗示”的布尔表达式形式，且另外该类型系统包括写成“einT(Τ中e)”的表达式的类型成员测试或类型测试。该类型测试表达式的操作行为是对表达式e求值并判断所得到的值是否在类型T的值的集中。在这一点上，将类型系统的上面的特征组合在一起得到用于定义类型的一些强大的和优雅的表达式。例如，图5阐释第一非限制性益处，该益处是可以以单个紧凑的表达式定义类型520，该表达式是两者均由基于约束的或结构类型化定义的第一类型500和第二类型510的交。类型S和T的交类型可以被表达为如下{x:Any|xinT&&xinS(χ任何|Τ中的χ与S中的χ的交)}图6阐释另一非限制性益处，即，类型620可以以单个紧凑的表达式来定义，该表达式是两者均由基于约束的或结构类型化定义的第一类型500和第二类型510的并。类型S和T的并类型可以被表达为如下{x=Any|xinT||xinS(χ任何|T中的χ与S中的χ的并)}带有顶端类型或顶级类型的类型系统的另一非限制性益处是空类型还可以被表达，如图7中所示。通过否定顶端类型“Any”，可以表达是没有有效类型的集合的空类型720。在D中，空类型可以被表达为如下{x=Any|false(χ任何|假)}为进一步理解，可以使用判断的集合来在数学上描述类型系统。判断是下列形式ΓΚ7其中J是某种断言，其自由变量在Γ中声明。上下文Γ是形式为0,xl:Tl，...，Χη:Τη的不同变量及其类型的经排序列表。(空上下文0有时消失。)类型系统的主判断形式是断言在上下文Γ中表达式e具有类型T的类型化判断，例如，在Γ中定义e的自由变量。这可以被声明为如下Γ卜eT断言e:T(即表达式e具有类型T的断言)是关系。换句话说，给定的表达式可以被说成是具有许多类型。如果存在类型T使得ΓμeT，则表达式e被说成是在上下文r被适当类型化。可以通过给出基于被假定为有效的其他判断来定义某些判断的有效性的一组类型规则来指定(正式的)类型系统。另一判断形式是断言类型S是另一类型T的子类型的子类型化判断，且其被写成如下。Γ卜S<:T“D”编程语言的类型系统可以通过给出定义这样的判断的一组类型规则来正式指定。例如，判断类型测试表达式是否适当类型化是由下列类型规则定义的。Γl·e··S厂卜eInT·Logical换句话说，如果表达式是某种类型S，则在上下文Γ中表达式einT被适当类型化(且是类型Logical(逻辑))。另一规则允许引入子类型化。权利要求1.一种用于根据包括支持类型精化和类型成员的类型系统的声明性编程模型定义声明性代码的方法，包括接收800声明性编程语言的至少一个编程构件的规定，包括接收810通过指定对于其来说布尔表达式为真的值来定义至少一个类型的类型精化构件的规定，以及在所述类型精化构件内接收判断求值表达式所得到的一个或多个值是否所指示的类型的成员的类型成员测试构件的规定；以及基于所述至少一个编程构件的所述规定生成830代码的机器可读的表示。2.如权利要求1所述的方法，其特征在于，所述编程构件的所述规定的接收800包括接收在所述类型精化构件中指定的至少两个类型的交的规定。3.如权利要求1所述的方法，其特征在于，所述编程构件的所述规定的接收800包括接收所述类型精化构件中指定的至少两个类型的并的规定。4.如权利要求1所述的方法，其特征在于，所述编程构件的所述规定的接收800包括接收所述类型精化构件中指定的至少两个类型的并和至少两个类型的交的规定。5.如权利要求1所述的方法，其特征在于，所述至少一个编程构件的所述规定的接收800包括接收820顶端类型的规定，所有类型满足所述顶端类型的条件。6.如权利要求1所述的方法，其特征在于，所述接收800包括接收具有句法“Any”820的编程构件。7.如权利要求1所述的方法，其特征在于，所述至少一个编程构件的所述规定的接收800包括接收空类型的规定，没有表达式满足所述空类型的条件。8.如权利要求1所述的方法，其特征在于，所述空类型的所述规定的接收800包括接收顶端类型在逻辑上被否定的规定，所述顶端类型是所有表达式所属于的类型。9.一个计算机系统，包括至少一个计算机可读模块930，包括表示根据实现支持基于约束的类型精化和类型成员的类型系统的声明性编程模型的声明性代码的计算机可执行指令，所述至少一个计算机可读模块包括编程构件，所述编程构件包括通过相对于表示所有类型的不受限顶级类型形成类型来定义所述类型的所述类型系统的精化类型，且其中所述编程构件的所述精化类型包括类型测试构件，所述类型测试构件针对所指示的类型的成员测试表达式的求值；以及包括数据的至少一个数据存储950，关于所述数据至少一个计算机可执行指令执行以便基于所述声明性代码的所述编程构件执行所述数据的访问、修改、过滤、变换、版本化或处理中的至少之一。10.如权利要求9所述的系统，类型检查模块940对所述至少一个计算机可读模块的至少一个类型求值，以便基于定义所述编程构件的类型化的有效性的至少一个规则判断错误。11.如权利要求9所述的系统，其特征在于，所述类型检查模块940通过增加所述声明性代码的所述表示来输出被包括在所述至少一个计算机可读模块中的类型检查信息。12.如权利要求9所述的系统，其特征在于，各类型具有值，且各值具有类型。13.如权利要求9所述的系统，其特征在于，所述编程构件包括所述类型精化构件中指定的至少两个类型的交的规定。14.如权利要求9所述的系统，其特征在于，所述编程构件包括所述类型精化构件中指定的至少两个类型的并的规定。15.如权利要求9所述的系统，其特征在于，所述编程构件包括所述类型精化构件中指定的至少两个类型的并和至少两个类型的交的规定。16.如权利要求9所述的系统，其特征在于，所述编程构件包括顶级类型的规定，对于所述顶级类型，所有有效类型是成员。17.一种用于由计算设备的至少一个处理器执行声明性代码的方法，包括对于所述计算设备的执行，接收1000根据类型化系统指定的声明性程序，所述类型化系统在所述声明性程序的编程构件内支持通过精化的类型化、类型成员的求值和所述声明性程序的所有有效值是其成员的顶端类型；以及根据与所述类型化系统相关联的一组类型化规则以及判断来对所述声明性程序中表示的所述类型进行类型检查1020。18.如权利要求17所述的方法，其特征在于，所述接收1000所述声明性程序包括接收根据支持具有值的类型和具有类型的值的类型化系统的声明性程序。19.如权利要求17所述的方法，其特征在于，所述接收1000所述声明性程序包括接收作为表示所述声明性程序的至少两个类型的交的交类型的类型的定义。20.如权利要求17所述的方法，其特征在于，所述接收1000所述声明性程序包括接收作为表示所述声明性程序的至少两个类型的并的并类型的类型的定义。全文摘要提供用于灵活地定义声明性编程语言的各类型的高效的、合乎逻辑的和有表现力的类型系统，以使得可以生成高效的且结构上紧凑的数据密集的应用程序。该类型系统支持精化类型和类型成员表达式的组合，并支持包含所有有效值作为成员的顶端类型。借助于该类型系统，各类型可以被表达成其他类型的交和/或并。因而，可以为真实世界数据存储中存在的全部数据类型高效地表示类型。文档编号G06F17/00GK102171681SQ200980140409公开日2011年8月31日申请日期2009年9月30日优先权日2008年10月3日发明者A·D·高登,B·H·洛夫林,D·E·兰沃西,D·F·伯克斯,G·柏曼,J·C·施利梅尔,J·D·多蒂申请人:微软公司