Elements of Programming provides a different understanding of programming than is presented elsewhere. Its major premise is that practical programming, like other areas of science and engineering, must be based on a solid mathematical foundation. The book shows that algorithms implemented in a real programming language, such as C++, can operate in the most general mathematical ...
Elements of Programming provides a different understanding of programming than is presented elsewhere. Its major premise is that practical programming, like other areas of science and engineering, must be based on a solid mathematical foundation. The book shows that algorithms implemented in a real programming language, such as C++, can operate in the most general mathematical setting. For example, the fast exponentiation algorithm is defined to work with any associative operation. Using abstract algorithms leads to efficient, reliable, secure, and economical software.
This is not an easy book. Nor is it a compilation of tips and tricks for incremental improvements in your programming skills. The book’s value is more fundamental and, ultimately, more critical for insight into programming. To benefit fully, you will need to work through it from beginning to end, reading the code, proving the lemmas, doing the exercises. When finished, you will see how the application of the deductive method to your programs assures that your system’s software components will work together and behave as they must.
Following key definitions, the book describes a number of algorithms and requirements for types on which they are defined that exemplify its abstract mathematical approach. The code for these descriptions—also available on the Web—is written in a small subset of C++ meant to be accessible to any experienced programmer. This subset is defined in a special language appendix coauthored by Sean Parent and Bjarne Stroustrup.
Whether you are a software developer, or any other professional for whom programming is an important activity, or a committed student, you will come to understand what the book’s experienced authors have been teaching and demonstrating for years—that mathematics is good for programming, that theory is good for practice.
作者简介
· · · · · ·
Alexander Stepanov studied mathematics at Moscow State University from 1967 to 1972. He has been programming since 1972: first in the Soviet Union and, after emigrating in 1977, in the United States. He has programmed operating systems, programming tools, compilers, and libraries. His work on foundations of programming has been supported by GE, Brooklyn Polytechnic, AT&T,HP, SG...
Alexander Stepanov studied mathematics at Moscow State University from 1967 to 1972. He has been programming since 1972: first in the Soviet Union and, after emigrating in 1977, in the United States. He has programmed operating systems, programming tools, compilers, and libraries. His work on foundations of programming has been supported by GE, Brooklyn Polytechnic, AT&T,HP, SGI, and, since 2002, Adobe. In 1995 he received the Dr. Dobb’s Journal Excellence in Programming Award for the design of the C++ Standard Template Library.
Paul McJones studied engineering mathematics at the University of California, Berkeley, from 1967 to 1971. He has been programming since 1967 in the areas of operating systems, programming environments, transaction processing systems, and enterprise and consumer applications. He has been employed by the University of California, IBM, Xerox, Tandem, DEC, and, since 2003, Adobe. In 1982 he and his coauthors received the ACM Programming Systems and Languages Paper Award for their paper “The Recovery Manager of the System R Database Manager.”
Examples of values are integers represented in 32-bit two's complement big-endian format and rational numbers represented as a concatenation of two 32-bit sequences, interpreted as integer numerator and denominator, represented as two's complement big-endian values. (查看原文)
##Chapter 1 Foundations == Structure == Chapter 1 作为全书的领头羊,具有画龙点睛之功效。 也是我人为这本书,值得一度的根本原因。 本章内容是其他内容的最高抽象,也就是其余内容都是作为第一章的延伸。你可以理解为金字塔的塔尖。 Categories of ideas and it's incarnation. == Understand == Catefories of ideas =========== Entity: 物质可灭,精神永存 抽象存在:不可变,永恒的。 具体存在:会生,会灭。 attribut...
2013-08-14 09:34:34
##Chapter 1 Foundations
== Structure ==
Chapter 1 作为全书的领头羊,具有画龙点睛之功效。 也是我人为这本书,值得一度的根本原因。 本章内容是其他内容的最高抽象,也就是其余内容都是作为第一章的延伸。你可以理解为金字塔的塔尖。
Categories of ideas and it's incarnation.
== Understand ==
Catefories of ideas
===========
Entity: 物质可灭,精神永存
抽象存在:不可变,永恒的。
具体存在:会生,会灭。
attribute:具体与抽象之间对应,或者说共享、共同存在的内容。只有通过attribute抽象的存在才能以具体存在,特定的等价联系。来自具体存在。
Identity:指存在的根本内容,作者没有给出具体定义。
Species:类别
An abstract species describes common properties of essentially equivalent abstract entities.抽象属性集合
A concrete species describes the set of attributes of essentially equivalent concrete entities. 具体属性集合
Genus:类属
An abstract genus describes different abstract species that are similar in some respect.
A concrete genus describes different concrete species similar in some respect.
entity属于一个类别,类别提供了entity,产生,存在的规则。
entity可以属于多个类属,每个类属描述一些属性。
Objects and values属于entities,types属于species, concepts是Genus。
计算机处理的都是抽象内容。
Incarnation
=======
Function: is a rule that associates one or more abstract entities, called arguments, from corresponding species with an abstract entity, called the result, from another species.函数是抽象存在到抽象存在的转化的规则,就是小学学到的函数定义。
Values:
A datum is a finite sequence of 0s and 1s.计算机数据就是0 1 的序列。
A datum corresponding to a particular entity is called a representation of the entity; the entity is called the interpretation of the datum.
数据是作为entity,如object,value的(原始)表示,长什么样,一个鼻子俩个眼。
而entity是作为数据的一种解释,好看呀还是俊俏。
We refer to a datum together with its interpretation as a value.
那么value包括两方面:entity和datum。
我们可以形成这样非严格的逻辑关系:
datum -> entity(value, object) ->species->genura
101 -> 5 -> int -> number
这有点 类似高中课本上那条咬住自己尾巴的snake。
A value type is a correspondence between a species and a set of datums.
那么vlaue type是datum和species联系的纽带。表示这种关系的一个实例!所以说value type本质上是代表一个二元关系,而不是某个实体。 这很重要,可以说是颠覆式的。二元关系,在算术中是大小,几何中是相似,集合中是包含。而value type 这种二元关系涉及到的两个主题就是value 和entity。
A value type is properly partial if its values represent a proper subset of the abstract entities in the corresponding species; otherwise it is total. For example, the type int is properly partial, while the type bool is total.
很自然,我们就会对关系加以分类。上面这段话理解很费劲。我理解成boundary!
整型值无法被完全表述entities,只能partial。可以把boudary理解为genus。
A value type is uniquely represented if and only if at most one value corresponds to each abstract entity.
Two values of a value type are equal if and only if they represent the same abstract entity. They are representationally equal if and only if their datums are identical sequences of 0s and 1s.相同值表述不一定相同,如负数的补码和普通形式。
If a value type is uniquely represented, equality implies representational equality.在同一种表述格式的前提下,当然值也相同。
Object
An object is a representation of a concrete entity as a value in memory.
object 对应具体存在在内存的值形态。
An object type is a pattern for storing and modifying values in memory.
Values and objects play complementary roles.
Describing the states of objects in terms of values allows us to abstract
from the particular implementations of the objects when discussing equality.
Functional programming deals with values; imperative programming deals with objects.
Since values are unchanging, they can represent abstract entities. Sequences of values can also represent sequences of snapshots of concrete entities.
Objects hold values representing entities. Since objects are changeable, they can represent concrete entities by taking on a new value to represent a change in the entity. Objects can also represent abstract entities: staying constant or taking on different approximations to the abstract.
讨论抽象具体entities与其表述方式value object的关系。
We use objects in the computer for the following three reasons.
1. Objects model changeable concrete entities, such as employee records in a payroll application.
2. Objects provide a powerful way to implement functions on values, such as a procedure implementing the square root of a floating-point number using an iterative algorithm.迭代过程改变object的值, 理解对吗?
3. Computers with memory constitute the only available realization of a universal computational device
2、3 理解不能。
Some properties of value types carry through to object types.
Since concrete entities have identities, objects representing them need a corresponding notion of identity.
Procedures
A procedure is a sequence of instructions that modifies the state of some objects; it may also construct or destroy objects.
##Chapter 2. Transformations and Their Orbits
##Chapter 1 Foundations == Structure == Chapter 1 作为全书的领头羊,具有画龙点睛之功效。 也是我人为这本书,值得一度的根本原因。 本章内容是其他内容的最高抽象,也就是其余内容都是作为第一章的延伸。你可以理解为金字塔的塔尖。 Categories of ideas and it's incarnation. == Understand == Catefories of ideas =========== Entity: 物质可灭,精神永存 抽象存在:不可变,永恒的。 具体存在:会生,会灭。 attribut...
2013-08-14 09:34:34
##Chapter 1 Foundations
== Structure ==
Chapter 1 作为全书的领头羊,具有画龙点睛之功效。 也是我人为这本书,值得一度的根本原因。 本章内容是其他内容的最高抽象,也就是其余内容都是作为第一章的延伸。你可以理解为金字塔的塔尖。
Categories of ideas and it's incarnation.
== Understand ==
Catefories of ideas
===========
Entity: 物质可灭,精神永存
抽象存在:不可变,永恒的。
具体存在:会生,会灭。
attribute:具体与抽象之间对应,或者说共享、共同存在的内容。只有通过attribute抽象的存在才能以具体存在,特定的等价联系。来自具体存在。
Identity:指存在的根本内容,作者没有给出具体定义。
Species:类别
An abstract species describes common properties of essentially equivalent abstract entities.抽象属性集合
A concrete species describes the set of attributes of essentially equivalent concrete entities. 具体属性集合
Genus:类属
An abstract genus describes different abstract species that are similar in some respect.
A concrete genus describes different concrete species similar in some respect.
entity属于一个类别,类别提供了entity,产生,存在的规则。
entity可以属于多个类属,每个类属描述一些属性。
Objects and values属于entities,types属于species, concepts是Genus。
计算机处理的都是抽象内容。
Incarnation
=======
Function: is a rule that associates one or more abstract entities, called arguments, from corresponding species with an abstract entity, called the result, from another species.函数是抽象存在到抽象存在的转化的规则,就是小学学到的函数定义。
Values:
A datum is a finite sequence of 0s and 1s.计算机数据就是0 1 的序列。
A datum corresponding to a particular entity is called a representation of the entity; the entity is called the interpretation of the datum.
数据是作为entity,如object,value的(原始)表示,长什么样,一个鼻子俩个眼。
而entity是作为数据的一种解释,好看呀还是俊俏。
We refer to a datum together with its interpretation as a value.
那么value包括两方面:entity和datum。
我们可以形成这样非严格的逻辑关系:
datum -> entity(value, object) ->species->genura
101 -> 5 -> int -> number
这有点 类似高中课本上那条咬住自己尾巴的snake。
A value type is a correspondence between a species and a set of datums.
那么vlaue type是datum和species联系的纽带。表示这种关系的一个实例!所以说value type本质上是代表一个二元关系,而不是某个实体。 这很重要,可以说是颠覆式的。二元关系,在算术中是大小,几何中是相似,集合中是包含。而value type 这种二元关系涉及到的两个主题就是value 和entity。
A value type is properly partial if its values represent a proper subset of the abstract entities in the corresponding species; otherwise it is total. For example, the type int is properly partial, while the type bool is total.
很自然,我们就会对关系加以分类。上面这段话理解很费劲。我理解成boundary!
整型值无法被完全表述entities,只能partial。可以把boudary理解为genus。
A value type is uniquely represented if and only if at most one value corresponds to each abstract entity.
Two values of a value type are equal if and only if they represent the same abstract entity. They are representationally equal if and only if their datums are identical sequences of 0s and 1s.相同值表述不一定相同,如负数的补码和普通形式。
If a value type is uniquely represented, equality implies representational equality.在同一种表述格式的前提下,当然值也相同。
Object
An object is a representation of a concrete entity as a value in memory.
object 对应具体存在在内存的值形态。
An object type is a pattern for storing and modifying values in memory.
Values and objects play complementary roles.
Describing the states of objects in terms of values allows us to abstract
from the particular implementations of the objects when discussing equality.
Functional programming deals with values; imperative programming deals with objects.
Since values are unchanging, they can represent abstract entities. Sequences of values can also represent sequences of snapshots of concrete entities.
Objects hold values representing entities. Since objects are changeable, they can represent concrete entities by taking on a new value to represent a change in the entity. Objects can also represent abstract entities: staying constant or taking on different approximations to the abstract.
讨论抽象具体entities与其表述方式value object的关系。
We use objects in the computer for the following three reasons.
1. Objects model changeable concrete entities, such as employee records in a payroll application.
2. Objects provide a powerful way to implement functions on values, such as a procedure implementing the square root of a floating-point number using an iterative algorithm.迭代过程改变object的值, 理解对吗?
3. Computers with memory constitute the only available realization of a universal computational device
2、3 理解不能。
Some properties of value types carry through to object types.
Since concrete entities have identities, objects representing them need a corresponding notion of identity.
Procedures
A procedure is a sequence of instructions that modifies the state of some objects; it may also construct or destroy objects.
##Chapter 2. Transformations and Their Orbits
##Chapter 1 Foundations == Structure == Chapter 1 作为全书的领头羊,具有画龙点睛之功效。 也是我人为这本书,值得一度的根本原因。 本章内容是其他内容的最高抽象,也就是其余内容都是作为第一章的延伸。你可以理解为金字塔的塔尖。 Categories of ideas and it's incarnation. == Understand == Catefories of ideas =========== Entity: 物质可灭,精神永存 抽象存在:不可变,永恒的。 具体存在:会生,会灭。 attribut...
2013-08-14 09:34:34
##Chapter 1 Foundations
== Structure ==
Chapter 1 作为全书的领头羊,具有画龙点睛之功效。 也是我人为这本书,值得一度的根本原因。 本章内容是其他内容的最高抽象,也就是其余内容都是作为第一章的延伸。你可以理解为金字塔的塔尖。
Categories of ideas and it's incarnation.
== Understand ==
Catefories of ideas
===========
Entity: 物质可灭,精神永存
抽象存在:不可变,永恒的。
具体存在:会生,会灭。
attribute:具体与抽象之间对应,或者说共享、共同存在的内容。只有通过attribute抽象的存在才能以具体存在,特定的等价联系。来自具体存在。
Identity:指存在的根本内容,作者没有给出具体定义。
Species:类别
An abstract species describes common properties of essentially equivalent abstract entities.抽象属性集合
A concrete species describes the set of attributes of essentially equivalent concrete entities. 具体属性集合
Genus:类属
An abstract genus describes different abstract species that are similar in some respect.
A concrete genus describes different concrete species similar in some respect.
entity属于一个类别,类别提供了entity,产生,存在的规则。
entity可以属于多个类属,每个类属描述一些属性。
Objects and values属于entities,types属于species, concepts是Genus。
计算机处理的都是抽象内容。
Incarnation
=======
Function: is a rule that associates one or more abstract entities, called arguments, from corresponding species with an abstract entity, called the result, from another species.函数是抽象存在到抽象存在的转化的规则,就是小学学到的函数定义。
Values:
A datum is a finite sequence of 0s and 1s.计算机数据就是0 1 的序列。
A datum corresponding to a particular entity is called a representation of the entity; the entity is called the interpretation of the datum.
数据是作为entity,如object,value的(原始)表示,长什么样,一个鼻子俩个眼。
而entity是作为数据的一种解释,好看呀还是俊俏。
We refer to a datum together with its interpretation as a value.
那么value包括两方面:entity和datum。
我们可以形成这样非严格的逻辑关系:
datum -> entity(value, object) ->species->genura
101 -> 5 -> int -> number
这有点 类似高中课本上那条咬住自己尾巴的snake。
A value type is a correspondence between a species and a set of datums.
那么vlaue type是datum和species联系的纽带。表示这种关系的一个实例!所以说value type本质上是代表一个二元关系,而不是某个实体。 这很重要,可以说是颠覆式的。二元关系,在算术中是大小,几何中是相似,集合中是包含。而value type 这种二元关系涉及到的两个主题就是value 和entity。
A value type is properly partial if its values represent a proper subset of the abstract entities in the corresponding species; otherwise it is total. For example, the type int is properly partial, while the type bool is total.
很自然,我们就会对关系加以分类。上面这段话理解很费劲。我理解成boundary!
整型值无法被完全表述entities,只能partial。可以把boudary理解为genus。
A value type is uniquely represented if and only if at most one value corresponds to each abstract entity.
Two values of a value type are equal if and only if they represent the same abstract entity. They are representationally equal if and only if their datums are identical sequences of 0s and 1s.相同值表述不一定相同,如负数的补码和普通形式。
If a value type is uniquely represented, equality implies representational equality.在同一种表述格式的前提下,当然值也相同。
Object
An object is a representation of a concrete entity as a value in memory.
object 对应具体存在在内存的值形态。
An object type is a pattern for storing and modifying values in memory.
Values and objects play complementary roles.
Describing the states of objects in terms of values allows us to abstract
from the particular implementations of the objects when discussing equality.
Functional programming deals with values; imperative programming deals with objects.
Since values are unchanging, they can represent abstract entities. Sequences of values can also represent sequences of snapshots of concrete entities.
Objects hold values representing entities. Since objects are changeable, they can represent concrete entities by taking on a new value to represent a change in the entity. Objects can also represent abstract entities: staying constant or taking on different approximations to the abstract.
讨论抽象具体entities与其表述方式value object的关系。
We use objects in the computer for the following three reasons.
1. Objects model changeable concrete entities, such as employee records in a payroll application.
2. Objects provide a powerful way to implement functions on values, such as a procedure implementing the square root of a floating-point number using an iterative algorithm.迭代过程改变object的值, 理解对吗?
3. Computers with memory constitute the only available realization of a universal computational device
2、3 理解不能。
Some properties of value types carry through to object types.
Since concrete entities have identities, objects representing them need a corresponding notion of identity.
Procedures
A procedure is a sequence of instructions that modifies the state of some objects; it may also construct or destroy objects.
##Chapter 2. Transformations and Their Orbits
3 有用 豆友1314003 2014-09-09 18:26:48
有些很有用的算法,有些很有启发的思想,还有一些纯粹C艹的东西。西加加大法,一天八十八
3 有用 lichray 2015-10-01 04:22:56
中文译名《编程原本》,足见其地位。
0 有用 侃大海 2021-03-20 07:56:16
读了一遍了,至少要多读几遍才能有收获,现在读了第一遍后最大的收获是终于有理由去学代数了,什么群啊,环之类的概念了,有了这些初步视觉上的印象,再去看就能与未能理解的这本书关联起来了,就从抽象到具体了吧
2 有用 doublethink 2012-11-21 11:05:30
过程相当痛苦,而且至今还有一些知识点没有很好的理解。 不敢说全懂,但是还是很认真地做了大部分的习题的,对引理和工程也有所思考。有时,觉得书写错了。错了。。错了。。。真的错了。最后发现还是自己错了。所以,若有读者认书错了。。。再多想一下下吧~! 需重读,再写笔记,时间的话就。。。
0 有用 侃大海 2021-03-20 07:56:16
读了一遍了,至少要多读几遍才能有收获,现在读了第一遍后最大的收获是终于有理由去学代数了,什么群啊,环之类的概念了,有了这些初步视觉上的印象,再去看就能与未能理解的这本书关联起来了,就从抽象到具体了吧
3 有用 lichray 2015-10-01 04:22:56
中文译名《编程原本》,足见其地位。
3 有用 豆友1314003 2014-09-09 18:26:48
有些很有用的算法,有些很有启发的思想,还有一些纯粹C艹的东西。西加加大法,一天八十八
2 有用 doublethink 2012-11-21 11:05:30
过程相当痛苦,而且至今还有一些知识点没有很好的理解。 不敢说全懂,但是还是很认真地做了大部分的习题的,对引理和工程也有所思考。有时,觉得书写错了。错了。。错了。。。真的错了。最后发现还是自己错了。所以,若有读者认书错了。。。再多想一下下吧~! 需重读,再写笔记,时间的话就。。。