# Introduction to programming

Computer Science is no more about computers
than astronomy is about telescopes.
    — Edsger Dijkstra 我记得面对我的第一个编程任务（1980 年的 BASIC！），我完全没做出来。我甚至不知道如何开始解决这个问题。我很难过，尽管编码对我来说很快就会变得非常自然。我最初的困难的原因现在显而易见：教师完全没有提供将问题转换为正在运行的程序的技术或策略。我必须自己解决这个问题。 在介绍性课程中关注编程语言语法的方法是可以理解的。 解决问题不是一种精确，定义好的技能。 它更像是一种通过练习磨练的整体能力。 因此，教学和评分是具有挑战性的。 立即跳转到一些简单的编程语言语句的语法，要容易得多。 这种方法具体，原则上易于理解，但完全忽略了我们什么时候以及为什么需要这些语句。 可以在这种环境中作为学生而生存的教授，在教其他程序员时通常会继续使用孤注一掷的方法。 在本课程中，我想通过专注于解决问题和学习编写复杂的 Python 代码来纠正这一问题。要做到这一点，我们将遵循一个整体的问题解决策略，包括设计“工作计划”或“算法”，无论是纸上还是头脑中（当你获得更多经验时）。在我们进入编码阶段很久之前，该计划就帮助我们思考问题。计划的一部分是确定一个解决我们问题的合适操作顺序。这是一个棘手的问题，因此我们将通过以下方式缩小解决方案空间的范围：（1）将自己限制在一组通用的操作和数据结构中，（2）应用成熟的方法，我们称之为“向后工作”和“简化为一个已知的解决方案“，最后，（3）利用这个入门课程的主题特性，采用一个适用于大多数数据科学问题的程序大纲。当我们最终进入 Python 编程时，我们将自己局限于该语言的有用子集。目标是教你编程，而不是教你完整的 Python 语言。 请允许我首先区分**编程**（问题解决）和**编码**（用特定编程语言表达我们的解决方案）。 ## 编程是什么？ 当我们考虑编程时，我们会立即考虑编程语言，因为我们使用特定的语言语法表达自己。 但是，这就像向物理学家询问他们讨论物理学的语言。 **编程**主要是将“单词问题”（项目描述）转换为执行计划。 当然，**编码**（输入代码）的最终行为是必需的，但学习在精神上解决编程问题是最困难的过程，也是最重要的过程。 自然语言也是如此。 学习证明数学定理比学习用某种自然语言编写证明更难。 实际上，大多数数学语法在自然语言中都是相同的，就像编程语言一样。 像在数据科学计划中一样，用 Python 或 R 表达您的想法是编程过程中最简单的部分。 也就是说，编写正确的代码通常是该过程中最令人沮丧和耗时的部分，即使对于有经验的程序员也是如此。 编程更多是要表达*什么*而不是*如何*表达。 用计算机解决问题意味着识别一系列操作，每个操作都解决了整个问题的一部分。 每个操作本身可能是一系列子操作。 用 Python 或 R 表达这些操作并不困难。 确定哪些操作及其相对顺序是困难的部分。 让我们从解决编程问题的整体策略入手。 ## 解决问题的策略 无论我们尝试编写什么软件，我们都可以遵循解决问题的整体策略。 **在任何问题解决的情况下，第一步**是充分理解问题并清楚地确定目标。 这可能听起来很明显，但是我们对这个问题的理解中的任何模糊性都可能使我们走错方向。 在数据科学环境中，目标通常是我们试图回答的问题，例如“*哪个销售区域的同比增长最快？*”（摘要统计量），“*哪些交易是欺诈性的？*”（分类器）或“*未来某个日期股票价格是多少？*”（预测器）。 我们应该能够使用英语单词精确地表达目标和预期输出。 如果我们不能这样做，那么 Python 或 R 中没有任何编码的专业知识可以解决问题。 我们很快就会看到一些例子。 **问题解决过程的第二步**（或可能是第一步的一部分）是手动写出一些输入 - 输出对。 这样做有助于我们了解程序需要做什么以及如何执行。 我们将要看到，这种技术不仅适用于整体输入和输出，而且适用于设计[函数](functions.ipynb)（可重用的代码段）。 **如果我们无法手动识别和执行操作，我们无法使用代码自动执行操作。**此外，列出一堆案例通常会突出特殊情况，例如“当输入为负时，输出应为空”。 换句话说，程序不应该以负数作为输入而崩溃。 程序员称之为*测试驱动设计*。 在求职面试设置中，此步骤意味着立即尝试绘制问题的几个实例。 例如，如果要求以某种方式处理数字列表，首先将三个或四个数字放在板上或纸上。 这自然会带来一些面试官期待你提出的重要问题，比如数据的来源以及它是否适合内存等...... **第三步**是弄清楚我们实现目标所需的数据或输入，即我们的原材料。 没有正确的数据，我们无法解决问题。 例如，我曾指导过一个学生实习团队，其目标是确定某个网站的哪些客户会升级到专业帐户。 学生只有已升级的用户数据，没有拒绝升级的用户数据。哎呀！ 如果您只有苹果的数据，则无法构建苹果与橙子分类器。 如果您没有所需的所有数据，那么将此要求确定为问题解决过程的一部分非常重要。 数据采集通常需要编程，我们将回顾下面的主题，作为我们通用计划大纲的一部分。 在这一点上，我们实际上已经设定了解决问题所需的阶段，我们根本没有考虑过代码。 我们从最终结果开始，然后确定了我们需要的数据。 输入 - 输出对巧妙地包含了我们需要执行的计算。 一开始，我们有已知的数据，最后，我们有预期的输出或作品。 好的，进入编程步骤。 **第四步**是确定计算预期结果的操作顺序。 有时这被称为*算法*并且涉及规划输入数据上的特定操作和子操作，逐渐将其转换为预期输出。 前四个步骤是所谓的[费曼技巧](https://www.google.com/search?q=feynman+technique)的关键部分，其中包括写下已分配任务或问题的完整说明，就像你对非专家解释它那样。直到你可以简单地写下来，而不会混淆语言或术语，你自己不明白这个问题。在你完成这个阶段之前，没有必要继续下去。（教师经常开玩笑，学习新主题的最佳方法是教授关于该主题的课程！） 在**第五步**中，我们将计划中的操作转换为实际的可执行代码。 这一步需要整本书，但这里总结了我的建议。 从最简单的子操作开始，确保它们先工作。 然后编写使用这些子操作的较大操作。 如果出现问题，您就会知道新代码中的子操作可能没有经过测试。 在这个阶段，我们通常会发现第四步中的设计问题，因此我们通常会重复四五次。 测试功能和修复错误称为*调试*。 最后，**第六步**是检查我们的整体结果的正确性。 最明显的检查是比较程序的输出与步骤 3 中的已知输入-输出对。 然后，最重要的是，在第 3 步到第 5 步中使用未考虑的输入来测试程序。 这是对程序通用性的重要测试。 如果程序输出错误，则返回第 4 步来查看错误。 而现在，出于现实因素。世界是一个非常混乱的地方，因为我们开始知道最少的问题，所以我们通常需要通过一些或所有这些步骤重复或反弹。 例如，假设我们正在构建一个苹果与橙子分类器，上面的过程使程序不能很好地区分这两个水果。 也许我们只有大小和形状的数据。 我们可能会认为分类器需要颜色数据，所以它回到第二步（可能是第三步），然后是第六步再次检查结果。 ### 制定计划和程序 程序是一系列操作，用于转换数据或执行计算，它最终产生预期输出。*编程*是设计程序的行为：识别操作及其适当的顺序。 换句话说，编程就是为计算机提出一个工作计划，我们经常用半精确的英文描述，叫做*伪代码*。这是上一节中的**第四步**。 *Coding*, on the other hand, is the act of translating such high-level pseudocode to programming language syntax. As you gain more experience, it'll become easier and easier to go from a work plan in your head straight to code, without the pseudocode step. When first learning to program, it helps to use established patterns, templates, strategies, and common data transformation operations as a crutch. For example, in the next section will look at a template for a data science program that will work in most cases throughout this program! In [programming patterns in Python](https://github.com/parrt/msan501/blob/master/notes/python-patterns.ipynb), we'll see lots of patterns you can piece together to create programs. As mentioned above, there are also two strategies or general guidelines you can use to approach the program design process: * *Start with the end result and work your way backwards, asking what the prerequisites are for each step*. In other words, the processing step or steps preceding step *i* compute the data or values needed by step *i*. For example, we cannot print the average of some numbers before we compute that average. We can't compute the average until we sum those numbers. We can't sum until we load those numbers into memory etc... * *Reduce or simplify a new problem to a variation of an existing problem with a known solution.* To apply this new approach, ask what the difference is between the problem you're trying to solve and other problems for which you have a solution. Both techniques are well known in architecture, engineering, and mathematics. For example, imagine you want to erect a heavy statue 10 feet off the ground. A structural engineer might decide that the heavy statute needs a flat metal base directly underneath it. Then, to support all of that weight, four 10 foot steel beams should support the metal base. The beams should have deep concrete footings in the ground, and so on. That's working backwards from the end result. As an example of reuse, engineers building a new suspension bridge do not proceed as if such a thing has never been built before. It's likely they will take an existing design and tweak it to suit the new situation. As an aside, plan reuse is often used to poke fun at other disciplines. For example, from [a collection of physicist jokes](https://www.astro.umd.edu/~avondale/extra/Humor/ScienceHumor/PhysicistJokes.html), here is a one variation: > A Physicist and a mathematician are sitting in a faculty lounge. Suddenly, the coffee machine catches on fire. The physicist grabs a bucket and leap towards the sink, fills the bucket with water and puts out the fire. Second day, the same two sit in the same lounge. Again, the coffee machine catches on fire. This time, the mathematician stands up, gets a bucket, hands the bucket to the physicist, thus *reducing the problem to a previously solved one*. **Exercise**: Given a string containing the digits of a number, such as `s = "501"`, print out the sum of the individual digits. In this case, the output should be `6 = 5 + 0 + 1`. Hint: `int('9')` yields value 9. Work backwards from the desired result, the sum, to figure out what you need. For example, the result is the sum of the digits. That means we need the digits. To get the digits, we can either iterate through the characters of a string or we can convert the string to a list of characters and iterate that. As we iterate, we can just sum up the digit values. To sum things up, we need to initialize a temporary result variable, perhaps called `n`. **Exercise**: Given a list of numbers in `A`, reverse the numbers *inline* (meaning w/o a separate copy of `A` and w/o creating a new list to return). Start by writing an example on the board. This exercise is useful for flipping images in your [images project](../projects/images.md). If you get stuck, or just to check your answers, you can check [my solutions](https://github.com/parrt/msan501/blob/master/notes/code/problem_solving.py). Now that we have an overall strategy for problem solving, let's look at a program outline that'll help us get started with just about any data science program you need to build. ## Data science program template Experienced programmers draw from a collection of generic mental templates as starting points. There are templates for desktop GUI apps, machine learning classifiers, web servers, etc.... A template provides an overall structure for the program and the programmer just has to tailor it to a specific problem. Relying on mental or even physical templates is very common, not just in programming. Lawyers have generic templates for contracts and screenwriters have generic scripts for the various movie genres. For example, most action movies go like this: Meet the bad guy. Meet the hero/heroine. Chase scene. Hero/heroine overcomes great difficulties to defeat the bad guy and his minions. Programming is most similar to writing legal documents because of the required precision. A missing word or punctuation can crash a program or bankrupt a contract signatory. (e.g., see [The Typo that Destroyed a NASA Rocket](https://priceonomics.com/the-typo-that-destroyed-a-space-shuttle)). Gaining experience as a programmer means recognizing patterns in your code and creating generic templates in your mind for future use. While you're getting started, you can rely on the experience of other programmers by reusing existing libraries of code and by using relevant templates. This leads us to the following generic data science program template that is suitable for most of the problems you're likely to run into: 1. Acquire data, which means finding a suitable file or collecting data from the web and storing in a file or database 2. Load data from disk or database and place into memory, organized into data structures 2. Normalize, filter, clean, or otherwise prepare data 3. Process the data, which can mean training a machine learning model, transforming the data, computing summary statistics, or optimizing a cost function 4. Emit results, which can be anything from simply printing an answer to saving data to the disk to generating a fancy visualization Writing a program for a specific problem means figuring out what each of those steps are, though not all programs will use every step. **Acknowledgements**. Conversations with [Kathi Fisler](http://cs.brown.edu/~kfisler/) provided a lot of inspiration for the disciplined, planned approach to programming summarized here. For more on design recipes, see [Transferring Skills at Solving Word Problems from Computing to Algebra Through Bootstrap](https://cs.brown.edu/~sk/Publications/Papers/Published/sfkf-trans-word-prob-comp-alg-bs/paper.pdf).