type inference

33 results back to index

Programming TypeScript by Boris Cherny

billion-dollar mistake, bitcoin, business logic, database schema, don't repeat yourself, duck typing, Firefox, functional programming, Internet of things, pull request, source of truth, SQL injection, type inference, web application

You should keep your data structures immutable with spreads (...) most of the time.1 You should make sure everything has a type, inferred when possible. Be careful not to abuse explicit types; this will help keep your code clear and terse, and improve safety by surfacing incorrect types rather than bandaiding over them. You should keep your code reusable and generic. Polymorphism (see “Polymorphism”) is your best friend. Of course, these ideas are hardly new. But TypeScript works especially well when you stick to them. TypeScript’s built-in downlevel compiler, support for read-only types, powerful type inference, deep support for polymorphism, and completely structural type system encourage good coding style, while the language remains incredibly expressive and true to the underlying JavaScript.

…

Now when we call call, TypeScript will know exactly what the return type is, and it will complain when we pass the wrong number of arguments: let a = call(fill, 10, 'a') // string[] let b = call(fill, 10) // Error TS2554: Expected 3 arguments; got 2. let c = call(fill, 10, 'a', 'z') // Error TS2554: Expected 3 arguments; got 4. We use a similar technique to take advantage of the way TypeScript infers tuple types for rest parameters to improve type inference for tuples in “Improving Type Inference for Tuples”. Generic Type Defaults Just like you can give function parameters default values, you can give generic type parameters default types. For example, let’s revisit the MyEvent type from “Generic Type Aliases”. As a reminder, we used the type to model DOM events, and it looks like this: type MyEvent<T> = { target: T type: string } To create a new event, we have to explicitly bind a generic type to MyEvent, representing the type of HTML element that the event was dispatched on: let buttonEvent: MyEvent<HTMLButtonElement> = { target: myButton, type: string } As a convenience for when we don’t know the specific element type that MyEvent will be bound to beforehand, we can add a default for MyEvent’s generic: type MyEvent<T = HTMLElement> = { target: T type: string } We can also use this opportunity to apply what we learned in the last few sections and add a bound to T, to make sure that T is an HTML element: type MyEvent<T extends HTMLElement = HTMLElement> = { target: T type: string } Now, we can easily create an event that’s not specific to a particular HTML element type, and we don’t have to manually bind MyEvents T to HTMLElement when we create the event: let myEvent: MyEvent = { target: myElement, type: string } Note that like optional parameters in functions, generic types with defaults have to appear after generic types without defaults: // Good type MyEvent2< Type extends string, Target extends HTMLElement = HTMLElement, > = { target: Target type: Type } // Bad type MyEvent3< Target extends HTMLElement = HTMLElement, Type extends string // Error TS2706: Required type parameters may > = { // not follow optional type parameters. target: Target type: Type } Type-Driven Development With a powerful type system comes great power.

…

(question mark)for optional elements in tuples, Tuples for optional function parameters, Optional and Default Parameters for optional properties in objects, Objects @ts-check comment, Step 2a: Enable Typechecking for JavaScript (Optional) @ts-ignore comment, JavaScript That Doesn’t Have Type Declarations on DefinitelyTyped @ts-nocheck comment, Step 2a: Enable Typechecking for JavaScript (Optional) [] (square brackets)index signature syntax, Objects keying-in operator, The infer Keyword retrieving enum values, Enums in tuple declarations, Tuples {} (curly braces), defining object literal types with, Objects | (pipe symbol), for union types, Union and intersection types, Type Operators for Object Types, In the Browser: With Web Workers – (minus) type operator, Mapped Types … (ellipsis) in variadic function parameters list, Rest Parameters A abstract classes, Classes and Inheritance, Classes and Inheritanceextending versus implementing interfaces, Implementing Interfaces Versus Extending Abstract Classes abstract syntax tree (AST), The Compiler actual parameters (see arguments) Ahead-of-Time (AoT) compiler (Angular), Angular 6/7, Services aliases (type) (see type aliases) allowJs TSC flag, Step 1: Add TSC ambient module declarations, Ambient Module Declarationscreating for third-party JavaScript, JavaScript That Doesn’t Have Type Declarations on DefinitelyTyped wildcard, Ambient Module Declarations ambient type declarations, Ambient Type Declarationsdefining TODO as type alias for any, Step 3: Rename Your Files to .ts ambient variable declarations, Ambient Variable Declarations AMD module standard, A Brief History of JavaScript Modulesconsuming JavaScript module that uses, Using CommonJS and AMD Code amd-module directive, The amd-module Directive Angular 6/7, Angular 6/7-Servicescomponents, Components initializing a project, Scaffolding installing CLI, Scaffolding services, Services angularCompilerOptions, Components any type, anyas overloaded function parameter type, Overloaded Function Types inferred for empty array elements, Arrays JavaScript types inferred as, Step 2a: Enable Typechecking for JavaScript (Optional) object versus, Objects TODO ambient type declaration as type alias for, Step 3: Rename Your Files to .ts type assertions as, Type Assertions widening of variables initialized as null or undefined to, Type Widening APIsapplication interacting with databases, Backend Frameworks typesafe, for use with frameworks and TypeScript, Typesafe APIs-Typesafe APIs apply function, call, apply, and bind argumentsdefined, Declaring and Invoking Functions passing in function calls, Declaring and Invoking Functions variable or fixed number of, Rest Parameters aritymodeling using bounded polymorphism, Using bounded polymorphism to model arity variadic versus fixed-arity functons, Rest Parameters arrays, Arrays-Read-only arrays and tuplesArray type, extending safely, Safely Extending the Prototype Array.prototype.includes (ES2016), lib covariance in array members, Shape and array variance filtering, Polymorphism generic functions on Array type, Where Can You Declare Generics?

Tackling TypeScript by Dr. Axel Rauschmayer

functional programming, lateral thinking, type inference

Values that have this type can’t be used for instanceof checks (as right-hand-side operands). 19 Typing Arrays * * * 19.1 Roles of Arrays 19.2 Ways of typing Arrays 19.2.1 Array role “list”: Array type literals vs. interface type Array 19.2.2 Array role “tuple”: tuple type literals 19.2.3 Objects that are also Array-ish: interfaces with index signatures 19.3 Pitfall: type inference doesn’t always get Array types right 19.3.1 Inferring types of Arrays is difficult 19.3.2 Type inference for non-empty Array literals 19.3.3 Type inference for empty Array literals 19.3.4 const assertions for Arrays and type inference 19.4 Pitfall: TypeScript assumes indices are never out of bounds * * * In this chapter, we examine how Arrays can be typed in TypeScript. 19.1 Roles of Arrays Arrays can play the following roles in JavaScript (either one or a mix of them): Lists: All elements have the same type.

…

If, for example the parameter num of a function toString(num) has the static type number, then the function call toString('abc') is illegal, because the argument 'abc' has the wrong static type. 7.4 Type annotations function toString(num: number): string { return String(num); } There are two type annotations in the previous function declaration: Parameter num: colon followed by number Result of toString(): colon followed by string Both number and string are type expressions that specify the types of storage locations. 7.5 Type inference Often, TypeScript can infer a static type if there is no type annotation. For example, if we omit the return type of f(), TypeScript infers that it is string: // %inferred-type: (num: number) => string function toString(num: number) { return String(num); } Type inference is not guesswork: It follows clear rules (similar to arithmetic) for deriving types where they haven’t been specified explicitly. In this case, the return statement applies a function String() that maps arbitrary values to strings, to a value num of type number and returns the result.

…

For example: const myMap: Map<boolean,string> = new Map([ [false, 'no'], [true, 'yes'], ]); Thanks to type inference (based on the argument of new Map()), we can omit the type parameters: // %inferred-type: Map<boolean, string> const myMap = new Map([ [false, 'no'], [true, 'yes'], ]); 7.15.2 Type variables for functions Functions (and methods) can introduce type variables, too: function id<T>(x: T): T { return x; } We use this function as follows. // %inferred-type: number const num1 = id<number>(123); Due to type inference, we can once again omit the type parameter: // %inferred-type: 123 const num2 = id(123); Note that TypeScript inferred the type 123, which is a set with one number and more specific than the type number. 7.15.3 A more complicated function example // %inferred-type: <T>(len: number, elem: T) => T[] function fillArray<T>(len: number, elem: T) { return new Array<T>(len).fill(elem); } The type variable T appears three times in this code: It is introduced via fillArray<T>.

Programming Scala: tackle multicore complexity on the JVM by Venkat Subramaniam

augmented reality, business logic, continuous integration, domain-specific language, don't repeat yourself, functional programming, higher-order functions, loose coupling, semantic web, type inference, web application

Download at Boykma.Com Prepared exclusively for sam kaplan C OLLECTIONS AND T YPE I NFERENCE expectations.2 Second, it helps you to express the expectations on your API in a compiler-verifiable format. In this chapter, you’ll learn about Scala’s sensible static typing and type inference. You’ll also look at three special types in Scala: Any, Nothing, and Option. 5.1 Collections and Type Inference Scala will provide type inference and type safety for the Java Generics collections as well. The following is an example that uses an ArrayList. The first declaration uses explicit, but redundant, typing. The second declaration takes advantage of type inference. As an aside, note that the underscore in the import statement is equivalent to the asterisks in Java. So when we type java.util._, we are importing all classes in the java.util package.

…

. 1.6 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 11 14 19 22 24 24 Getting Started 2.1 Downloading Scala . . . . . . . 2.2 Installing Scala . . . . . . . . . 2.3 Take Scala for a Ride . . . . . . 2.4 Scala on the Command Line . . 2.5 Running Scala Code as a Script 2.6 Scala from an IDE . . . . . . . . 2.7 Compiling Scala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 26 27 28 30 31 32 32 Getting Up to Speed in Scala 3.1 Scala as Concise Java . . . . . . . 3.2 Scala Classes for Java Primitives . 3.3 Tuples and Multiple Assignments . 3.4 Strings and Multiline Raw Strings 3.5 Sensible Defaults . . . . . . . . . . 3.6 Operator Overloading . . . . . . . . 3.7 Scala Surprises for the Java Eyes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 34 37 38 40 41 43 45 Classes in Scala 4.1 Creating Classes . . . . . . . . . . . . . . . . . 4.2 Defining Fields, Methods, and Constructors 4.3 Extending a Class . . . . . . . . . . . . . . . . 4.4 Singleton Object . . . . . . . . . . . . . . . . . 4.5 Stand-Alone and Companion Objects . . . . 4.6 static in Scala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 53 54 57 58 60 61 Prepared exclusively for sam kaplan . . . . . . . . . . . . . . . . . . Download at Boykma.Com CONTENTS 5 6 7 8 9 Sensible Typing 5.1 Collections and Type Inference . . . . 5.2 The Any Type . . . . . . . . . . . . . . 5.3 More About Nothing . . . . . . . . . . . 5.4 Option Type . . . . . . . . . . . . . . . 5.5 Method Return Type Inference . . . . 5.6 Passing Variable Arguments (Varargs) 5.7 Variance of Parameterized Type . . . . . . . . . . . . . . . . . . 63 64 66 67 68 69 70 71 . . . . . . . . . 75 75 76 78 80 81 83 84 87 88 . . . . . 91 91 94 95 97 99 . . . . . . . . . . 103 103 104 106 108 113 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

…

In other words, while AnyRef directly maps to Object, Any and AnyVal are type erased to Object much like type erasure of Generics parameterized types in Java. 5.3 More About Nothing You can see why you’d need Any, but what is the purpose of Nothing? Scala’s type inference works hard to determine the type of expressions and functions. If the type inferred is too broad, it will not help type verification. At the same time, how do you infer the type of an expression or function if one branch returns, say, an Int and another branch throws an exception? In this case, it is more useful to infer the type as Int rather than a general Any.

Types and Programming Languages by Benjamin C. Pierce

Albert Einstein, combinatorial explosion, experimental subject, finite state, functional programming, Henri Poincaré, higher-order functions, Perl 6, power law, Russell's paradox, sorting algorithm, Turing complete, Turing machine, type inference, Y Combinator

A pragmatic approach to partial type reconstruction for systems involving both subtyping and impredicative polymorphism, called local type inference (or local type reconstruction), was proposed by Pierce and Turner (1998; also see Pierce and Turner, 1997; Hosoya and Pierce, 1999). Local type inference has appeared in several recent language designs, including GJ (Bracha, Odersky, Stoutamire, and Wadler, 1998) and Funnel (Odersky and Zenger, 2001), the latter introducing a more powerful form called colored local type inference (Odersky, Zenger, and Zenger, 2001). A simpler but less predictable greedy type inference algorithm was proposed by Cardelli (1993); similar algorithms have also been used in proof-checkers for dependent type theories, such as NuPrl (Howe, 1988) and Lego (Pollack, 1990).

…

Finding the source of type errors. 13th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL), pages 38–43, 1986. Wand, Mitchell. Complete type inference for simple objects. In Proceedings of the IEEE Symposium on Logic in Computer Science, Ithaca, NY, June 1987. Wand, Mitchell. Corrigendum: Complete type inference for simple objects. In Proceedings of the IEEE Symposium on Logic in Computer Science, 1988. Wand, Mitchell. Type inference for objects with instance variables and inheritance. Technical Report NU-CCS-89-2, College of Computer Science, Northeastern University,February 1989a.

…

., 461 factorial, 52 fail, 16 failure vs. undefinedness, 16 families (of terms, types), 462 Featherweight Java, 247–264 fields, see instance variables; records finalizers, 515 finding type errors, 545 finite tree type, 285 finite-state generating function, 294 first-class polymorphism, 340 fixed point, 142–145 combinator, 65 of a generating function, 282 theorem (Tarski-Knaster), 283 typing, using recursive types, 273 FJ, see Featherweight Java flattened data structures, 341 Float type, 117 fold function, 63 fomsub implementation, 467–473 formal methods, lightweight, 1 Forsythe, 11, 199 Fortran, 8, 11 fragments of System F, 358–359 fragments of System Fω, 461 free variable, 55, 69 fresh variable, 120 full abstraction, 143 full beta-reduction, 56 full F<:, 391 fullequirec implementation, 267–280 fullerror implementation, 171–178 fullfomsub implementation, 389–409, 467–473 fullfsub implementation, 389–409, 417–436 fullfsubref implementation, 411–416 fullisorec implementation, 275–278 fullomega implementation, 439–466 fullpoly implementation, 339–379 fullrecon implementation, 317–338 fullref implementation, 153–170, 225–245 fullsimple implementation, 99–111, 117–146 fullsub implementation, 181–208 fulluntyped implementation, 51–73 fullupdate implementation, 475–489 <fun>, 118 function types, 99–100 functional languages, mostly, 153 functions, 16 higher-order, 58 multi-argument, 58 on types, see type operators Funnel, 409 FX, 11 * * * * * * Index G garbage collection, 45, 158–165, 514–515 tag free, 341 general recursion, 142–145 generating function, 282 generating set, 290 generation lemma, see inversion lemma generators, classes as, 229 generics, 341 gfp algorithm, 292, 295–298 GJ, 195, 248, 409 grammar, 24 graph reduction, 57 greatest fixed point of a generating function, 283 greatest lower bound, see joins and meets greedy type inference, 355 * * * * * * Index H hash consing, 222 Haskell, 6, 45 heap, 153 hidden representation type, 364 higher-order bounded quantifiers, 468 higher-order functions, 58 higher-order polymorphism, 449–466 history of type systems, 10 hungry functions, 270 hybrid object models, 377 * * * * * * Index I identity, object, 245 identity function, 55 imperative objects, see objects, imperative implementations allsome, 381–387 arith, 23–49 bot, 220 equirec, 281–313 fomsub, 467–473 fullequirec, 267–280 fullerror, 171–178 fullfomsub, 389–409, 467–473 fullfsub, 389–409, 417–436 fullfsubref, 411–416 fullisorec, 275–278 fullomega, 439–466 fullpoly, 339–379 fullrecon, 317–338 fullref, 153–170, 225–245 fullsimple, 99–111, 117–146 fullsub, 181–208 fulluntyped, 51–73 fullupdate, 475–489 joinexercise, 223 joinsub, 218–220 purefsub, 417–436 rcdsub, 181–224 recon, 317–338 reconbase, 330 simplebool, 113–116 tyarith, 91–98 untyped, 83–88 implicit type annotations, 330–331 implicitly typed languages, 101 impredicative polymorphism, 340, 360–361 impure language features, 153 induction, 19 lexicographic, 19 logical relations proof technique, 150 mathematical foundations, 282–284 on derivations, 37 on natural numbers, 19 on terms, 29–32 inductive definitions, 23–29 inference, see type reconstruction inference rules, 26 mathematical foundations, 283 infinite types, 284–286 inheritance, 227 overrated, 245 injection into a sum type, 133 instance of an inference rule, 36 instance variables, 228, 230, 233–234 instanceof, 341 instantiation of a polymorphic function, 317–320, 342 intensional polymorphism, 340 interface, 226 interface types, 479 interfaces (in Java), 261 interference, syntactic control of, 170 intermediate language, 161 intermediate languages, typed, 11 internal language, 53, 120 internet, see web intersection types, 11, 206–207, 359, 489 and bounded quantification, 400, 409 and normal forms, 206 introduction rule, 108 invariant, 33 inversion lemma subtyping, 188 typing, 94, 104, 188, 457 iso-recursive types, 275, 280 subtyping, 311–312 * * * * * * Index J Java, 6, 8–10, 45, 119, 137, 154, 174, 177, 178, 193, 195, 196, 198–199, 226, 232, 247–264, 341, 444 exception handling in, 174 parametric polymorphism, 195 reflection, 196 JINI, 9 joinexercise implementation, 223 joins and meets, 17 algorithms for calculating, 218–220 in System F<:, 432–435 joinsub implementation, 218–220 judgment, 36 * * * * * * Index K KEA, 226 kernel F<:, 391 kinding, 439–447, 459 kinds dependent, 445 power, 445 row, 445 singleton, 445 Knaster-Tarski fixed point theorem, 283 * * * * * * Index L λ-calculus, see lambda-calculus λNB, 63-66 λ→, see simply typed lambda-calculus λω, see System λω λ<:, see simply typed lambda-calculus with subtyping label, 129 lambda cube, 465 lambda-& calculus, 226, 340 lambda-calculi, typed, 2 lambda-calculus, 51, 52 enriched, 63-68 simply typed, see simply typed lambda-calculus untyped, see untyped lambda-calculus lambda-term, 53 language definition, defined, 7 language design and type systems, 9-10 language features, pure, 153 late binding, see objects, open recursion latent type system, 2 lazy evaluation, 57 least fixed point of a generating function, 283 least upper bound, see joins and meets left-associativity of application, 54 let bindings, 124-125 let-polymorphism, 331-336, 340 exponential behavior, 334 levels, de Bruijn, 81 lexical analysis, 53 lexicographic induction, 19 lexicographic order, 19 LF, 11, 465 lfp algorithm, 294 lightweight formal methods, 1 linear logic and type systems, 11, 109 linking, 367 lists, 146 Church encoding, 350-353, 500 defined using recursive types, 267-270 polymorphic functions for, 345-347 subtyping, 197 local type inference, 355 location, 159 logic and type systems, 108 origins, 11 type systems in, 2 logical framework, 465 logical relations, 149 * * * * * * Index M μ, see least fixed point μ notation for recursive types, 299–304 marshaling, 252, 341 Martin-Löf type theory, see constructive type theory match function, 131 matching, pattern-, 130–131 matching relation on object types, 480 mathematics, formalization of, 11 meaning of terms, 32–34 meet, see joins and meets membership checking for (co-)inductively defined sets, 290–298 Mercury, 338 message, 226 meta-mathematics, 24 metalanguage, 24 metatheory, 24 metavariables, 24 naming conventions, 565 method, 226, 228 invocation, 226 multi-, see multi-method override, 233, 264 Milner-Mycroft Calculus, 338 minimal types, 218, 418–420 minimal typing theorem, 419 mini-ML, 337 ML, 6, 8, 9, 11, 174, 177 exception handling in, 174 history, 336–338 module system, 379 parametric datatypes, 445 polymorphism, 331–336 ML implementations evaluation, 87 simply typed lambda-calculus, 113–116 subtyping, 221–224 System F, 381–387 untyped arithmetic expressions, 45–49 untyped lambda-calculus, 83–88 ML-style polymorphism, 340 modal logics, 109 model checking, 1, 284 Modula-3, 7 modularity, 3 module systems, 364, 379, 465 monads, 153 monitoring, run-time, 1 monotone function, 282 monotype, 359 most general unifier, 327 mostly functional languages, 153 multi-argument functions, 58 multi-method, 226, 340 multiple inheritance, 489 multiple representations (of object types), 226 multi-step evaluation, 39 mutually recursive functions, 144 types, 253 v, see greatest fixed point nameless form, see de Bruijn indices naming context, 77 naming conventions for metavariables and rules, 565–566 narrowing lemmas, 401, 425 National Science Foundation, xx natural deduction, 26 natural semantics, 32, 34, 43 natural-number induction, 19 nested induction, 19 NextGen, 196 nominal type systems, 251–254, 312 normal forms, 38 and intersection types, 206 uniqueness of, 39 normal order, 56 normalization, 149–152 by evaluation, 152 strong, 152 normalization theorem, 39, 152, 353 numeric values, 40 NuPRL, 11 * * * * * * Index O object calculus, 11, 51, 184, 248, 251 object language, 24 Objective Caml see OCaml, xvii objects, 228, 368 as recursive records, 272 bounded quantification and, 411–416 encodings vs. primitive objects, 262–263 existential, 372–377, 475–489 hybrid object models, 377 identity, 245 imperative, 157, 225–245, 411–416 interface types, 479 Java-style, 247–264 matching relation on object types, 480 object-oriented programming, defined, 225–227 open recursion, 227, 235–244 purely functional, 372–377, 475–489 vs. abstract data types, 374–377 OCaml, xvii, 7, 45, 208, 231, 489 OCaml implementations, see ML implementations occur check, 327, 338 omega, 65 open recursion, see objects, open recursion operational semantics, 32, see also evaluation big-step, 43 small-step, 42 operator associativity, 53 operator precedence, 53 Option type, 137–138 order, well-founded, 18 ordered sets, basic definitions, 16–18 ordinary induction, 19 overloading, 340 finitary, 206 overriding of method definitions, 233 * * * * * * Index P P(S) powerset of S, 15 package, existential, 364 pairs, 126–127 Church encodings, see Church encodings, pairs parallel reduction, 454 parametric abbreviation, 439 data type, 142, 444 polymorphism, 319, 340 parametricity, 359–360 parentheses and abstract syntax, 25, 52 parsing, 53 partial evaluation, 109 partial function, 16 partial order, 17 partially abstract types, 406 Pascal, 11 pattern matching, 130–131 PCF, 143 Pebble, 465 Penn translation, 204 Perl, 6 permutation, 18 permutation lemma, 106 permutation rule for record subtyping, 184 performance issues, 201–202 pi-calculus, 51 Pict, 200, 356, 409 Pizza, 195 pointer, 154, see references arithmetic, 159 pointwise subtyping of type operators, 468 polarity, 473 PolyJ, 195 polymorphic functions for lists, 345–347 identity function, 342 recursion, 338 update, 482–485 polymorphism, 331 ad hoc, 340 data abstraction, 368–377 existential, see existential types existential types, 363–379 exponential behavior of ML-style, 334 F-bounded, 393, 408 higher-order, 449–466 impredicativity and predicativity, 360–361 intensional, 340 ML-style, 331–336 parametric, 339–361 parametricity, 359–360 predicative, 360 prenex, 359 rank-2, 359 safety problems with references, 335–336 stratified, 360 subtype, see subtyping universal, see universal types varieties of, 340–341 polytype, 359 portability, types and, 7 positive subtyping, 489 Postscript, 6 power types, 445, 472 precedence of operators, 53 predecessor for Church numerals, 62 predicate, 15 predicative polymorphism, 360–361 prenex polymorphism, 359 preorder, 17 preservation of a predicate by a relation, 16 preservation of shapes under type reduction, 456 preservation of types during evaluation, 95–98, 107, 168, 173, 189, 261, 353, 404, 457 preservation of typing under type substitution, 318 principal type, 317, 329–330 types theorem, 329 typing, 337 unifier, 327 principal solution, 329 principle of safe substitution, 182 product type, 126–127 programming languages Abel, 409 Algol-60, 11 Algol-68, 11 Amber, 311 C, 6, 45 C#, 7 C++, 6, 226 Cecil, 226, 340 Clean, 338 CLOS, 226, 340 CLU, 11, 408 Dylan, 226 Featherweight Java, 247–264 Forsythe, 11, 199 Fortran, 8, 11 Funnel, 409 FX, 11 GJ, 195, 248, 409 Haskell, 6, 45 Java, 6, 8–10, 45, 119, 137, 154, 174, 177, 178, 193, 195, 196, 198–199, 226, 232, 247–264, 341, 444 KEA, 226 Mercury, 338 ML, 6, 8, 9, 11, 174, 177, see also OCaml, Standard ML Modula-3, 7 NextGen, 196 Objective Caml, see OCaml OCaml, xvii, 7, 208, 231, 489 Pascal, 11 Pebble, 465 Perl, 6 Pict, 200, 356, 409 Pizza, 195 PolyJ, 195 Postscript, 6 Quest, 11, 409 Scheme, 2, 6, 8, 45 Simula, 11, 207 Smalltalk, 226 Standard ML, xvii, 7, 45 Titanium, 8 XML, 9, 207, 313 progress theorem, 38, 95–98, 105, 169, 173, 190, 262, 353, 405, 458 projection (from pairs, tuples, records), 126–131 promotion, 418 proof, defined, 20 proof-carrying code, 9 proof theory, 2 proper types, 442 propositions as types, 109 pure λ→, 102 pure lambda-calculus, 51 pure language features, 153 pure type systems, xiv, 2, 444, 466 purefsub implementation, 417–436 * * * * * * Index Q qualified types, 338 quantification, see polymorphism Quest, 11, 409 * * * * * * Index R ramified theory of types, 2 range of a relation, 16 rank-2 polymorphism, 359 raw type, 248 rcdsub implementation, 181–224 reachableF, 294 recon implementation, 317–338 reconbase implementation, 330 reconstruction, see type reconstruction record kinds, 445 records, 129–131 Cardelli-Mitchell calculus, 207 Church encoding, 396–400 concatenation, 207 row variables, 208, 337 recursion, 65–66, 142–145 fixed-point combinator, 65 polymorphic, 338 recursive types, 253, 267–280 Amadio-Cardelli algorithm, 309–311 and subtyping, 279 equi-recursive vs. iso-recursive, 275 history, 279–280 in ML, 277–278 in nominal systems, 253 metatheory, 281–313 μ notation, 299–304 subtyping, 281–290, 298–313 type reconstruction, 313, 338 recursive values from recursive types, 273 redex, 56 reduce function, 63 reducibility candidates, 150 reduction vs. evaluation (terminology), 34 references, 153–170 allocation, 154 and subtyping, 199–200 assignment, 154 dereferencing, 154 subtyping, 198 type safety problems, 158 type safety problems with polymorphism, 335–336 refinement types, 207 reflection, 196, 252 and casting, 196 reflexive closure, 17 reflexive relation, 16 reflexivity of subtyping, 182 region inference, 8 regular trees, 298–299 relation, 15 logical, see logical relations removenames, 78 representation independence, 371 representation of numbers by Church numerals, 67 representation type (of an object), 230 restorenames, 78 row kinds, 445 row variables, 11, 208, 337, 489 rule computation, 35, 72 congruence, 35, 72 naming conventions, 565 schema, 27 rule, inference, 27 rule schema, 27 rules B-IFFALSE, 43 B-IFTRUE, 43 B-ISZEROSUCC, 43 B-ISZEROZERO, 43 B-PREDSUCC, 43 B-PREDZERO, 43 B-SUCC, 43 B-VALUE, 43 CT-ABS, 322, 542 CT-ABSINF, 330 CT-APP, 322, 542 CT-FALSE, 322 CT-FIX, 543 CT-IF, 322 CT-ISZERO, 322 CT-LETPOLY, 332 CT-PRED, 322 CT-PROJ, 545 CT-SUCC, 322 CT-TRUE, 322 CT-VAR, 322, 542 CT-ZERO, 322 E-ABS, 502 E-APP1, 72, 103, 160, 166, 186, 343, 392, 446, 450, 470, 502, 503 E-APP2, 72, 103, 160, 166, 186, 343, 392, 446, 450, 470, 502 E-APPABS, 72, 81, 103, 160, 166, 186, 342, 343, 392, 446, 450, 470, 502, 503 E-APPERR1, 172 E-APPERR2, 172 E-APPRAISE1, 175 E-APPRAISE2, 175 E-ASCRIBE, 122, 194 E-ASCRIBE1, 122 E-ASCRIBEEAGER, 123 E-ASSIGN, 161, 166 E-ASSIGN1, 161, 166 E-ASSIGN2, 161, 166 E-CASE, 132, 136 E-CASEINL, 132, 135 E-CASEINR, 132, 135 E-CASEVARIANT, 136 E-CAST, 258 E-CASTNEW, 258 E-CONS1, 147 E-CONS2, 147 E-DEREF, 161, 166 E-DEREFLOC, 161, 166 E-DOWNCAST, 195 E-FIELD, 258 E-FIX, 144 E-FIXBETA, 144 E-FLD, 276 E-FUNNY1, 40 E-FUNNY2, 40 E-GC, 514 E-HEAD, 147 E-HEADCONS, 147 E-IF, 34 E-IF-WRONG, 42 E-IFFALSE, 34 E-IFTRUE, 34 E-INL, 132, 135 E-INR, 132, 135 E-INVK-ARG, 258 E-INVK-RECV, 258 E-INVKNEW, 258 E-ISNIL, 147 E-ISNILCONS, 147 E-ISNILNIL, 147 E-ISZERO, 41 E-ISZERO-WRONG, 42 E-ISZEROSUCC, 41 E-ISZEROZERO, 41 E-LET, 124, 131, 335 E-LETV, 124, 131, 332 E-NEW-ARG, 258 E-PACK, 366, 452 E-PAIR1, 126 E-PAIR2, 126 E-PAIRBETA1, 126 E-PAIRBETA2, 126 E-PRED, 41 E-PRED-WRONG, 42 E-PREDSUCC, 41, 48 E-PREDZERO, 41 E-PROJ, 128, 129, 187 E-PROJ1, 126 E-PROJ2, 126 E-PROJNEW, 258 E-PROJRCD, 129, 187, 201, 484 E-PROJTUPLE, 128 E-RAISE, 175 E-RAISERAISE, 175 E-RCD, 129, 187, 484 E-REF, 162, 166 E-REFV, 162, 166 E-SEQ, 120 E-SEQNEXT, 120 E-SUCC, 41 E-SUCC-WRONG, 42 E-TAIL, 147 E-TAILCONS, 147 E-TAPP, 343, 392, 450, 470 E-TAPPTABS, 342, 343, 385, 392, 450, 470 E-TRY, 174, 175 E-TRYERROR, 174 E-TRYRAISE, 175 E-TRYV, 174, 175 E-TUPLE, 128 E-TYPETEST1, 195 E-TYPETEST2, 195 E-UNFLD, 276 E-UNFLDFLD, 276 E-UNPACK, 366 E-UNPACKPACK, 366, 367, 452 E-UPDATEV, 484 E-VARIANT, 136 E-WILDCARD, 507 K-ABS, 446, 450, 470 K-ALL, 450, 470 K-APP, 446, 450, 470 K-ARROW, 446, 450, 470 K-SOME, 452 K-TOP, 470 K-TVAR, 446, 450, 470 M-RCD, 131 M-VAR, 131 P-RCD, 509 P-RCD', 509 P-VAR, 509 Q-ABS, 446, 451, 471 Q-ALL, 451, 471 Q-APP, 446, 451, 471 Q-APPABS, 441, 446, 451, 471 Q-ARROW, 446, 451, 471 Q-REFL, 446, 451, 471 Q-SOME, 452 Q-SYMM, 446, 451, 471 Q-TRANS, 446, 451, 471 QR-ABS, 454 QR-ALL, 454 QR-APP, 454 QR-APPABS, 454 QR-ARROW, 454 QR-REFL, 454 S-ABS, 468, 471 S-ALL, 392, 394, 395, 427, 471 S-AMBER, 311 S-APP, 468, 471 S-ARRAY, 198 S-ARRAYJAVA, 198 S-ARROW, 184, 186, 211, 392, 471 S-ASSUMPTION, 311 S-BOT, 192 S-EQ, 468, 471 S-INTER1, 206 S-INTER2, 206 S-INTER3, 206 S-INTER4, 206 S-LIST, 197 S-PRODDEPTH, 187 S-PRODWIDTH, 187 S-RCD, 211 S-RCDDEPTH, 183, 187, 484 S-RCDPERM, 184, 187 S-RCDVARIANCE, 484 S-RCDWIDTH, 183, 187, 484 S-REF, 198 S-REFL, 182, 186, 211, 392 S-REFSINK, 199 S-REFSOURCE, 199 S-SINK, 199 S-SOME, 406, 476, 556 S-SOURCE, 199 S-TOP, 185, 186, 211, 392, 471 S-TRANS, 183, 186, 209, 211, 392, 471 S-TVAR, 392, 394, 471 S-VARIANTDEPTH, 197 S-VARIANTPERM, 197 S-VARIANTWIDTH, 197 SA-ALL, 422, 424 SA-ARROW, 212, 422, 424 SA-BOT, 220 SA-RCD, 212 SA-REFL-TVAR, 422, 424 SA-TOP, 212, 422, 424 SA-TRANS-TVAR, 422, 424 T-ABS, 101, 103, 167, 186, 343, 392, 447, 451, 471 T-APP, 102, 103, 167, 181, 186, 343, 392, 447, 451, 471 T-ASCRIBE, 122, 194 T-ASSIGN, 159, 165, 167, 199 T-CASE, 132, 136 T-CAST, 530 T-CONS, 147 T-DCAST, 259 T-DEREF, 159, 165, 167, 199 T-DOWNCAST, 194 T-EQ, 441, 447, 451 T-ERROR, 172 T-EXN, 175 T-FALSE, 93 T-FIELD, 259 T-FIX, 144 T-FLD, 276 T-HEAD, 147 T-IF, 93, 102, 218 T-INL, 132, 135 T-INR, 132, 135 T-INVK, 259 T-ISNIL, 147 T-ISZERO, 93 T-LET, 124, 332, 509 T-LETPOLY, 332, 333 T-LOC, 164, 167 T-NEW, 259 T-NIL, 147 T-PACK, 365, 366, 406, 452 T-PAIR, 126 T-PRED, 93 T-PROJ, 128, 129, 187, 484 T-PROJ1, 126 T-PROJ2, 126 T-RCD, 129, 187, 484 T-REF, 159, 165, 167 T-SCAST, 259 T-SEQ, 120 T-SUB, 182, 186, 209, 392, 471 T-SUCC, 93 T-TABS, 342, 343, 392, 395, 451, 471 T-TAIL, 147 T-TAPP, 342, 343, 392, 395, 451, 471 T-TRUE, 93 T-TRY, 174, 175 T-TUPLE, 128 T-TYPETEST, 195 T-UCAST, 259 T-UNFLD, 276 T-UNIT, 119, 167 T-UNPACK, 366, 406, 435, 452 T-UPDATE, 484 T-VAR, 101, 103, 167, 186, 259, 343, 392, 447, 451, 471 T-VARIANT, 136, 197 T-WILDCARD, 507 T-ZERO, 93 TA-ABS, 217, 419 TA-APP, 217, 419 TA-APPBOT, 220 TA-IF, 220, 526 TA-PROJ, 217 TA-PROJBOT, 220 TA-RCD, 217 TA-TABS, 419 TA-TAPP, 419 TA-UNPACK, 436 TA-VAR, 217, 419 XA-OTHER, 418 XA-PROMOTE, 418 run-time code generation, 109 run-time error, 42 trapped vs. untrapped, 7 run-time monitoring, 1 * * * * * * Index S safety, 3, 6-8, 95-98 problems with references, 158 problems with references and polymorphism, 335-336 satisfaction of a constraint set by a substitution, 321 saturated sets, 150 Scheme, 2, 6, 8, 45 units, 368 scope, 55 scoping of type variables, 393-394 second-order lambda-calculus, 341, 461 security, type systems and, 9 self, 227, 234-244, 486-488 semantics alternative styles, 32-34 axiomatic, 33 denotational, 33 operational, 32 semi-unification, 338 semistructured databases, 207 sequences, basic notations, 18 sequencing notation, 119-121 and references, 155 sets, basic operations on, 15 sharing, 445, 465 shifting (of nameless terms), 78-80 ML implementation, 85-87 side effects, 153 simple theory of types, 2 simple types, 100 simplebool implementation, 113-116 simply typed lambda-calculus, 2, 11, 99-111 extensions, 117-146 ML implementation, 113-116 pure, 102 with type operators, 445 Simula, 11, 207 single-field variant, 138-140 singleton kinds, 441, 445, 465 size of a term, 29 small-step operational semantics, 32, 42 Smalltalk, 226 soundness, see safety soundness and completeness, 212 of algorithmic subtyping, 423 of constraint typing, 325 Source and Sink constructors, 199 spurious subsumption, 253 Standard ML, xvii, 7, 45 statement, 36 static distance, 76 static vs. dynamic typing, 2 store, 153 store typing, 162-165 stratified polymorphism, 360 streams, 270-271 strict vs. non-strict evaluation, 57 String type, 117 strong binary operations, 376 strong normalization, 152, 353 structural operational semantics, 32, 34 structural unfolding, 489 structural vs. nominal type systems, 251-254 stuck term, 41 stupid cast, 259-260 subclass, 227, 232 subexpressions of μ-types, 304-309 subject expansion, 98, 108 subject reduction, see preservation subscripting conventions, 566 subset semantics of subtyping, 182, 201-202 substitution, 69-72, 75-81, 83-88 capture-avoiding, 70 ML implementation, 85-87 type-, 317 substitution lemma, 106, 168, 189, 453 substitution on types, 342 ML implementation, 382 subsumption, 181-182 postponement of, 214 subtraction of Church numerals, 62 subtype polymorphism, see subtyping subtyping, 181-224, see also bounded quantification Top and Bot types, 191-193 algorithm, 209-213, 417-436 algorithmic, in nominal systems, 253 and ascription, 193-196 and base types, 200 and channel types, 200 and objects, 227 and references, 199-200 and type reconstruction, 338, 355 and variant types, 196-197 arrays, 198-199 coercion semantics, 200-206 depth, 183 higher-order, 11, 467-473 intersection types, 206-207 iso-recursive types, 311-312 joins and meets in System F<:, 432-435 lists, 197 ML implementation, 221-224 objects, 229-230 positive, 489 power types, 472 record permutation, 184 recursive types, 279, 281-290, 298-313 references, 198 reflexivity, 182 subset semantics, 182, 201-202 subtype relation, 182-187 transitivity, 183 type operators, 467-473 undecidability of System F<:, 427-431 union types, 206-207 vs. other forms of polymorphism, 341 width, 183 sum types, 132-135 super, 234 supertype, 182 support, 290 surface syntax, 53 syllabi for courses, xvii symmetric relation, 16 syntactic control of interference, 170 syntactic sugar, 121 syntax, 26-29, 52-55, 69 ML implementation, 46-47, 383-385 syntax-directedness, 209 System F, 11, 339-361 fragments, 358-359 history, 341 ML implementation, 381-387 System Fω, 449-466 and higher-order logic, 109 fragments, 461 System , 467-473 System F<:, 389-409 kernel and full variants, 391 System λω, 445-447 * * * * * * Index T T, see terms tag, type-, 2 tag-free garbage collection, 341 tagged representation of atomic values, 201 tagging creating new types by, 133 tail recursion, 296 TAL, 11 Tarski-Knaster fixed point theorem, 283 termination measure, 39 terminology, reduction vs. evaluation, 34 terms, 24, 26 and expressions (terminology), 24 closed, 55 depth, 29 induction on, 29–32 inductive definition of (nameless form), 77 ML implementation, 46, 83–85 nameless form, see de Bruijn indices size, 29 stuck, 41 theorem proving, types in, 9, 464 this, see self thunk, 239 TinkerType, xx Titanium, 8 Top type, 185, 191–193 top-down subexpressions of a recursive type, 304 Top[K], 468 total function, 16 total order, 17 transitive closure, 17, 289 transitive relation, 16 transitivity and coinduction, 288–290 transitivity of subtyping, 183 translucent types, 11 trapped vs. untrapped errors, 7 tree, 538 abstract syntax, 25 derivation, 36 regular, 298–299 type, 285 treeof, 300 tuples, 126–129 two-counter machines, 430 tyarith implementation, 91–98 typability, 93, 109–110, 354–357 type abstraction, 342 type annotations, 3, 10, 111 type application, 342 type classes, 337, 338 type constructors, see type operators type destructors, 489 type environment, 101 type equivalence, 447, 453–456 type erasure, 110, 354 type errors, 3 finding, 545 type exposure, 417–418 type inference, see type reconstruction type names, 251 type operators, 100, 439–447 bounded, 473 co- and contravariant, 473 definition equivalence, 441 in nominal systems, 254 quantification over, 449–466 subtyping, 467–473 type reconstruction, 317–338, 354–357 colored local type inference, 355 greedy, 355 history, 336–338 local type inference, 355 recursive types, 313, 338 subtyping, 338, 355 type safety, see safety type scheme, 359 type substitution, 317 ML implementation, 382 type systems and efficiency, 8 and portability, 7 and security, 9 and theorem provers, 9, 464 applications, 8–9 as formal methods, 1 category theory and, 12 defined, 1–4 history, 10 in mathematics and logic, 2 language design and, 9–10 role in computer science, 1–4 type tags, 2, 196, 252 type theory, see type systems constructive, 2 type variables, 319–320 type-assignment systems, 101 type-directed partial evaluation, 152 type-erasure semantics, 357 type-passing semantics, 357 typecase, 341 typed arithmetic expressions, 91–98 typed assembly language, 11 typed intermediate languages, 11 typed lambda-calculi, 2 types, 92 typing context, 101 typing derivations, 94 desugaring of, 125 semantics defined on, 111, 200–206 typing relation, 92–95, 100–103 algorithm, 213–218 ML implementation, 113–116 properties, 104–108 * * * * * * Index U undecidability of full type reconstruction for System F, 354 of partial type reconstruction for System F, 354 of subtyping for System F<:, 427–431 undefinedness vs. failure, 16 unification, 321, 326–329 union types, 142, 206–207 disjoint, 142 uniqueness of normal forms, 39 uniqueness of types, 94, 104, 511 and annotations, 135, 141 and sums, 134–135 Unit type, 118–119 unit value, 118–119 units (in Scheme), 368 universal domain, 273 universal set, 282 universal types, 339–361 unsafe declarations, 7 untyped implementation, 83–88 untyped arithmetic expressions, 23–44 untyped lambda-calculus, 11, 51–73 representation using recursive types, 273–275 up-cast, see casting update, polymorphic, 482–485 * * * * * * Index V value, 34, 57 numeric, 40 value restriction, 336, 358 variable capture, 70 variables bound, 55, 69-72 free, 55 variant types, 132-142 and subtyping, 196-197 extensible, 177 single-field, 138-140 vs. datatypes, 140-142 * * * * * * Index W weak binary operations, 375 weak head reduction, 460 weak pointers, 515 weak type variable, 336 weakening lemma, 106 web resources, xx well-formed context, 459 well-founded order, 18 set, 18 well-typed term, 93 width subtyping, 183 wildcard bindings, 119-121 witness type, 364 wrong, 42, 73 * * * * * * Index X XML, 9, 207, 313 * * * * * * Index Y Y combinator, 65 Year 2000 problem, 9 * * * * * * Index Z Z combinator, 65 * * * * * * List of Figures Preface Figure P-1: Chapter Dependencies Figure P-2: Sample Syllabus for an Advanced Graduate Course Chapter 1: Introduction Figure 1-1: Capsule History of Types in Computer Science and Logic Chapter 3: Untyped Arithmetic Expressions Figure 3-1: Booleans (B) Figure 3-2: Arithmetic Expressions (NB) Chapter 5: The Untyped Lambda-Calculus Figure 5-1: The Predecessor Function's "Inner Loop" Figure 5-2: Evaluation of factorial c3 Figure 5-3: Untyped Lambda-Calculus (λ) Chapter 8: Typed Arithmetic Expressions Figure 8-1: Typing Rules for Booleans (B) Figure 8-2: Typing Rules for Numbers (NB) Chapter 9: Simply Typed Lambda-Calculus Figure 9-1: Pure Simply Typed Lambda-Calculus (λ→) Chapter 11: Simple Extensions Figure 11-1: Uninterpreted Base Types Figure 11-2: Unit Type Figure 11-3: Ascription Figure 11-4: Let Binding Figure 11-5: Pairs Figure 11-6: Tuples Figure 11-7: Records Figure 11-8: (Untyped) Record Patterns Figure 11-9: Sums Figure 11-10: Sums (With Unique Typing) Figure 11-11: Variants Figure 11-12: General Recursion Figure 11-13: Lists Chapter 13: References Figure 13-1: References Chapter 14: Exceptions Figure 14-1: Errors Figure 14-2: Error Handling Figure 14-3: Exceptions Carrying Values Chapter 15: Subtyping Figure 15-1: Simply Typed Lambda-Calculus with Subtyping (λ<:) Figure 15-2: Records (Same as Figure 11-7) Figure 15-3: Records and Subtyping Figure 15-4: Bottom Type Figure 15-5: Variants and Subtyping Chapter 16: Metatheory of Subtyping Figure 16-1: Subtype Relation with Records (Compact Version) Figure 16-2: Algorithmic Subtyping Figure 16-3: Algorithmic Typing Chapter 19: Case Study: Featherweight Java Figure 19-1: Featherweight Java (Syntax and Subtyping) Figure 19-2: Featherweight Java (Auxiliary Definitions) Figure 19-3: Featherweight Java (Evaluation) Figure 19-4: Featherweight Java (Typing) Chapter 20: Recursive Types Figure 20-1: Iso-Recursive Types (λμ) Chapter 21: Metatheory of Recursive Types Figure 21-1: Sample Tree Types.

Software Design for Flexibility by Chris Hanson, Gerald Sussman

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, connected car, domain-specific language, Donald Knuth, en.wikipedia.org, functional programming, Guido van Rossum, higher-order functions, interchangeable parts, loose coupling, Magellanic Cloud, phenotype, premature optimization, Richard Stallman, stem cell, the scientific method, Turing machine, type inference

How many failures are needed to solve the problem with the propagator diagram that you compiled into? If it takes more than about 200 failures you compiled into very bad code! Exercise 7.7: Card game puzzle revisited Redo exercise 5.17 using propagators. Exercise 7.8: Type inference In section 4.4.2 we built a type-inference engine as an example of the application of unification matching. In this exercise (which is really a substantial project) we implement type inference taking advantage of propagation. a. Given a Scheme program, construct a propagation network with a cell for every locus that is useful to type. Each such cell will be the repository of the type information that will be accumulated about the type information at that locus in the program.

…

But a system of match procedures is potentially more efficient, because it avoids the syntactic analysis of the patterns while matching. Can the unification matcher be broken up in a similar way? If not, why not? Is it a good idea to do so? If not, why not? If so, do it! (This is hard!) 4.4.2 Application: Type inference One classic application of unification matching is type inference: given a program and some type information about parts of the program, deduce type information about other parts of the program. For example, if we know that < is a procedure that takes two numerical arguments and produces a boolean value, then if we analyze the expression (g (< x (f y))), we can deduce that f and g are unary procedures; g accepts a boolean argument; f returns a numerical value; and x has a numerical value.

…

(declare-type iter (type:procedure ((numeric-type) (numeric-type)) (numeric-type))) Also, the type of each internal variable has been determined, and an appropriate declaration has been posted: (declare-type n (numeric-type)) (declare-type product (numeric-type)) (declare-type counter (numeric-type)) 4.4.3 How type inference works The process of type inference has four phases. 1. The given program is annotated with type variables for all subexpressions of the program. 2. Constraints on the type variables are formulated based on the semantic structure of the program. 3. The constraints are unified to eliminate as many of the variables as possible. 4.

Scala in Depth by Tom Kleenex, Joshua Suereth

discrete time, domain-specific language, duck typing, fault tolerance, functional programming, higher-order functions, MVC pattern, sorting algorithm, type inference

Scala defines three variable types on the left-hand side, like var, val, and lazy val. These leave the type of the variable clean. In all instances, the type of the name x is Int. In addition to separating the concerns of how a variable behaves from the variable type, the placement of types on the right allows type inference to determine the type of the variables. 1.2.2. Type inference Scala performs type inference wherever possible. Type inference is when the compiler determines what the type annotation should be, rather than forcing the user to specify one. The user can always provide a type annotation, but has the option to let the compiler do the work. val x: Int = 5 val y = 5 This feature can drastically reduce the clutter found in some other typed languages.

…

SeqLike captures the original fully typed collection in its second type parameter. This allows the type system to carry the most specific type through a generic method so that it can be used in the return value. Deferring Type Inference of Parent-Class Type Parameters The need to defer the type inference for a type parameter Foo <: Seq[T] is necessary for supporting the Scala 2.8.x series. As of the Scala 2.9.x, the type inference algorithm was improved such that the implicit <:< parameter is no longer necessary. The next type parameter in the sort method is the cbf : CanBuildFrom[Coll, T, Coll]. The CanBuildFrom trait, when looked up implicitly, determines how to build new collections of a given type.

…

Sometimes it can help the type inferencer automatically determine types for a method call. One of the neat aspects of the type inferencing algorithm is that implicits can defer the resolution of types until later in the algorithm. Scala’s type inferencer works in a left-to-right fashion across parameter lists. This allows the types inferred from one parameter list to affect the types inferred in the next parameter list. A great example of this left-to-right inference is with anonymous functions using collections. Let’s take a look: scala> def foo[A](col: List[A])(f: A => Boolean) = null foo: [A](col: List[A])(f: (A) => Boolean)Null scala> foo(List("String"))(_.isEmpty) res1: Null = null The foo method defines two parameter lists with one type parameter: one that takes a list of the unknown parameter and another that takes a function using the unknown parameter.

Programming Scala by Unknown

billion-dollar mistake, business logic, domain-specific language, duck typing, en.wikipedia.org, fault tolerance, functional programming, general-purpose programming language, higher-order functions, information security, loose coupling, type inference, web application

If you are coming from a dynamically typed language, you may find that your test suites are a little smaller as a result, but not that much smaller. Many developers who find static languages too verbose often blame static typing for the verbosity when the real problem is a lack of type inference. In type inference, the compiler infers the types of values based on the context. For example, the compiler will recognize that x = 1 + 3 means that x must be an integer. Type inference reduces verbosity significantly, making the code feel more like code written in a dynamic language. We have worked with both static and dynamic languages, at various times. We find both kinds of languages compelling for different reasons.

…

The compiler automatically makes intToStringMap2 a HashMap[Integer,String]. Type inference is used for methods, too. In most cases, the return type of the method can be inferred, so the : and return type can be omitted. However, type annotations are required for all method parameters. Pure functional languages like Haskell (see, e.g., [O’Sullivan2009]) use type inference algorithms like Hindley-Milner (see [Spiewak2008] for an easily digested explanation). Code written in these languages require type annotations less often than in Scala, because Scala’s type inference algorithm has to support object-oriented typing as well as functional typing.

…

[SleepingBarberProblem] Sleeping barber problem, http://en.wikipedia.org/wiki/Sleep ing_barber_problem. [SMRa] David Hall, A Scalable Language, and a Scalable Framework, http://scala-blogs .org/2008/09/scalable-language-and-scalable.html. [SMRb] Scala Map Reduce, http://github.com/dlwh/smr/. [Smith2009a] Eishay Smith, Beware of Scala’s Type Inference, http://www.eishay.com/ 2009/05/beware-of-scalas-type-inference.html. [Smith2009b] Eishay Smith, Unexpected repeated execution in Scala, http://www.eishay .com/2009/06/unexpected-repeated-execution-in-scala.html. [Spiewak2008] Daniel Spiewak, What is Hindley-Milner? (and why is it cool?), http:// www.codecommit.com/blog/scala/what-is-hindley-milner-and-why-is-it-cool.

Essential TypeScript 4: From Beginner to Pro by Adam Freeman

en.wikipedia.org, Google Chrome, node package manager, revision control, type inference, web application

The first is creating an inaccurate test that doesn’t reliably differentiate between types, such as this test:dataItems.forEach(item => { if ("id" in item && "name" in item) { console.log(`Person: ${item.name}: ${item.city}`); } else { console.log(`Product: ${item.name}: ${item.price}`); } }); This test checks for id and name properties, but these are defined by both the Person and Product types, and the test doesn’t give the compiler enough information to infer a type. The type inferred in the if block is the Product | Person union, which means the use of the city property will generate an error. The type inferred in the else block is never, since all the possible types have already been inferred, and the compiler will generate errors for the use of the name and price properties. A related problem is testing for an optional property, like this:dataItems.forEach(item => { if ("price" in item) { console.log(`Product: ${item.name}: ${item.price}`); } else { console.log(`Person: ${item.name}: ${item.city}`); } }); The test will match objects that define a price property, which means that the type inferred in the if block will be Product, as intended (notice that the statements in the code blocks are reversed in this example).

…

A related problem is testing for an optional property, like this:dataItems.forEach(item => { if ("price" in item) { console.log(`Product: ${item.name}: ${item.price}`); } else { console.log(`Person: ${item.name}: ${item.city}`); } }); The test will match objects that define a price property, which means that the type inferred in the if block will be Product, as intended (notice that the statements in the code blocks are reversed in this example). The problem is that objects can still match the Product shape if they don’t have a price property, which means the type inferred in the else block is Product | Person and the compiler will report an error for the use of the city property. Writing effective tests for types can require careful thought and thorough testing, although the process becomes easier with experience.

…

== undefined) { results.push({ ...match, ...item }); } }); return results; } } export let peopleData = new DataCollection(people); export let collatedData = peopleData.collate(cities, "city", "name"); collatedData.forEach(c => console.log(`${c.name}, ${c.city}, ${c.population}`)); export let empData = peopleData.collate(employees, "name", "name"); empData.forEach(c => console.log(`${c.name}, ${c.city}, ${c.role}`)); Listing 12-13.Using Generic Type Inference in the index.ts File in the src Folder The compiler is able to infer the type arguments based on the argument passed to the DataCollection<T> constructor and the first argument passed to the collate method. To check the types inferred by the complier, examine the index.d.ts file in the dist folder, which is created when the declaration option is enabled. Tip In a project that uses modules, the files created through the declaration option contain only those types that are exported outside a module, which is why I added the export keyword in Listing 12-13.

The TypeScript Workshop: A Practical Guide to Confident, Effective TypeScript Programming by Ben Grynhaus, Jordan Hudgens, Rayon Hunte, Matthew Thomas Morgan, Wekoslav Stefanovski

Ada Lovelace, Albert Einstein, business logic, Charles Babbage, create, read, update, delete, don't repeat yourself, Donald Knuth, fault tolerance, Firefox, full stack developer, functional programming, Google Chrome, Hacker News, higher-order functions, inventory management, Kickstarter, loose coupling, node package manager, performance metric, QR code, Ruby on Rails, SQL injection, type inference, web application, WebSocket

In other words, we're missing out on one of TypeScript's most powerful features: type inference. Type inference is the ability for TypeScript to know what the type of something should be without having to be told. A very simple example of type inference would be the following: const hello = "hello"; No type is specified. This is because TypeScript understands that the variable hello is being assigned a string and cannot be reassigned. If we try to pass this variable as an argument to a function that expects another type, we will get a compilation error, even though we never specified the type. Let's apply type inference to promises. First, let's look at the type definition for the Promise object: new <T>(executor: (resolve: (value?

…

The magic is called type inference, and that means that TypeScript will try to guess the type of the variable based on the value provided. Let's define a variable and initialize it with a value, like this: let variable = 3; Now, if we try to assign a string to that variable, TypeScript will issue an error: Figure 1.2: Error message from assigning an incorrect type From the error message, we can see the type that TypeScript correctly inferred for the variable – number. Actually, in most cases, we won't even need to add type annotations, as TypeScript's powerful type inference engine will correctly infer the type of the variable.

…

This has implications when it comes to using the this (see below) and new (see Chapter 4, Classes and Objects) keywords. Type Inference Let's consider the following code: const myFunction = (name: string): string => `Hello ${name}!`; const numbers = [1, 3, 2]; const filtered = numbers.filter((val) => val < 3); console.log(filtered); The output is as follows: [1, 2] Notice that in the preceding code, we aren't specifying a type for the numbers constant. But wait, isn't this a book on TypeScript? Yes, and now we come to one of the best features of TypeScript: type inference. TypeScript has the ability to assign types to variables when we omit them.

Scala in Action by Nilanjan Raychaudhuri

business logic, continuous integration, create, read, update, delete, database schema, domain-specific language, don't repeat yourself, duck typing, en.wikipedia.org, failed state, fault tolerance, functional programming, general-purpose programming language, higher-order functions, index card, Kanban, MVC pattern, type inference, web application

Scala type inference will figure out the type of parameters when you invoke the function but not during the function declaration.[4],[5] 4 “Type inference,” Wikipedia, http://mng.bz/32jw. 5 Daniel Spiewak, posted at Code Commit, “What is Hindley-Milner? (and why is it cool?),” undated, http://mng.bz/H4ip. Type inference If you have a background in Haskell, OCaml, or any other type of inferred programming language, the way Scala parameters are defined could feel a bit weird. The reason is that Scala doesn’t use the Hindley-Milner algorithm to infer type; instead Scala’s type inference is based on declaration-local information, also known as local type inference.

…

But having constraints is useful when building a large application because they allow you to enforce a certain set of rules across the codebase. Scala, being a type-inferred language, takes care of most of the boilerplate code for the programmer (that’s what compilers are good for, right?) and takes you close to a dynamically typed language, but with all the benefits of a statically typed language. Definition Type inference is a technique by which the compiler determines the type of a variable or function without the help of a programmer. The compiler can deduce that the variable s in s="Hello" will have the type string because "hello" is a string. The type inference ensures the absence of any runtime type errors without putting a declaration burden on the programmer.

…

The reason is that Scala doesn’t use the Hindley-Milner algorithm to infer type; instead Scala’s type inference is based on declaration-local information, also known as local type inference. Type inference is out of the scope of this book, but if you’re interested you can read about the Hindley-Milner type inference algorithm and why it’s useful. Sometimes it becomes necessary to create a function that will take an input and create a List from it. But the problem is you can’t determine the type of input yet. Someone could use your function to create a List of Int, and another person could use it to create a List of String. In cases like this you create a function in Scala by parameterized type. The parameter type will be decided when you invoke the function: scala> def toList[A](value:A) = List(value) toList: [A](value: A)List[A] scala> toList(1) res16: List[Int] = List(1) scala> toList("Scala rocks") res15: List[java.lang.String] = List(Scala rocks) When declaring the function, you denote the unknown parameterized type as A.

Programming in Scala by Martin Odersky, Lex Spoon, Bill Venners

domain-specific language, functional programming, Guido van Rossum, higher-order functions, Larry Wall, off-by-one error, Silicon Valley, sorting algorithm, the Cathedral and the Bazaar, type inference, web application

On the other hand, even if that rule were relaxed, the inferencer still could not come up with a type for op because its parameter types are not given. Hence, there is a Catch-22 situation which can only be resolved by an explicit type annotation from the programmer. This example highlights some limitations of the local, flow-based type inference scheme of Scala. It is not present in the more global HindleyMilner style of type inference used in functional languages such as ML or Haskell. However, Scala’s local type inference deals much more gracefully with object-oriented subtyping than the Hindley-Milner style does. Fortunately, the limitations show up only in some corner cases, and are usually easily fixed by adding an explicit type annotation.

…

On the other hand, at least one of the two annotations in the following example is annoying: val x: HashMap[Int, String] = new HashMap[Int, String]() Clearly, it should be enough to say just once that x is a HashMap with Ints as keys and Strings as values; there’s no need to repeat the same phrase twice. Scala has a very sophisticated type inference system that lets you omit almost all type information that’s usually considered annoying. In the previous example, the following two less annoying alternatives would work just as well: val x = new HashMap[Int, String]() val x: Map[Int, String] = new HashMap() Type inference in Scala can go quite far. In fact, it’s not uncommon for user code to have no explicit types at all. Therefore, Scala programs often look a bit like programs written in a dynamically typeddynamic!

…

Scala’s postfix type syntax resembles Pascal, Modula-2, or Eiffel. The main reason for this deviation has to do with type inference, which often lets you omit the type of a variable or the return type of a method. Using the “variable: Type” syntax this is easy—just leave out the colon and the type. But in C-style “Type variable” syntax you cannot simply leave off the type—there would be no marker to start the definition anymore. You’d need some alternative keyword to be a placeholder for a missing type (C# 3.0, which does some type inference, uses var for this purpose). Such an alternative keyword feels more ad-hoc and less regular than Scala’s approach. 16 Landin, “The Next 700 Programming Languages.”

Programming in Haskell by Graham Hutton

Eratosthenes, functional programming, higher-order functions, John Conway, Simon Singh, type inference

On the other hand, the expression ¬ 3 does not have a type under the above rule for function application, because this would require that 3 :: Bool , which is not valid because 3 is not a logical value. Expressions such as ¬ 3 that do not have a type are said to contain a type error, and are deemed to be invalid expressions. Because type inference precedes evaluation, Haskell programs are type safe, in the sense that type errors can never occur during evaluation. In practice, type inference detects a very large class of program errors, and is one of the most useful features of Haskell. Note, however, that the use of type inference does not eliminate the possibility that other kinds of error may occur during evaluation. For example, the expression 1 ‘div ‘ 0 is free from type errors, but produces an error when evaluated because division by zero is undefined.

…

Although it is difficult to make an objective comparison, Haskell programs are often between two and ten times shorter than programs written in other current languages. r Powerful type system (chapters 3 and 10) Most modern programming languages include some form of type system to detect incompatibility errors, such as attempting to add a number and a character. Haskell has a type system that requires little type information from the programmer, but allows a large class of incompatibility errors in programs to be automatically detected prior to their execution, using a sophisticated process called type inference. The Haskell type system is also more powerful than most current languages, by allowing functions to be “polymorphic” and “overloaded”. r List comprehensions (chapter 5) One of the most common ways to structure and manipulate data in computing is using lists. To this end, Haskell provides lists as a basic concept in the language, together with a simple but powerful comprehension notation that constructs new lists by selecting and filtering elements from one or more existing lists.

…

Lisp had some influences from the lambda calculus, but still adopted variable assignments as a central feature of the language. r In the 1960s, Peter Landin developed ISWIM (“If you See What I Mean”), the first pure functional programming language, based strongly on the lambda calculus and having no variable assignments. r In the 1970s, John Backus developed FP (“Functional Programming”), a functional programming language that particularly emphasised the idea of higher-order functions and reasoning about programs. r Also in the 1970s, Robin Milner and others developed ML (“MetaLanguage”), the first of the modern functional programming languages, which introduced the idea of polymorphic types and type inference. r In the 1970s and 1980s, David Turner developed a number of lazy functional programming languages, culminating in the commercially produced language Miranda (meaning “admirable”). r In 1987, an international committee of researchers initiated the development of Haskell (named after the logician Haskell Curry), a standard lazy functional programming language. r In 2003, the committee published the Haskell Report, which defines a longawaited stable version of Haskell, and is the culmination of fifteen years of work on the language by its designers.

Learning TypeScript: Enhance Your Web Development Skills Using Type-Safe JavaScript by Josh Goldberg

billion-dollar mistake, type inference

In this example, TypeScript knows that the ternary expression always results in a string, so the bestSong value is a string: let bestSong = Math.random() > 0.5 ? "Chain of Fools" : "Respect"; Type Inferences in Detail At its core, TypeScript’s type system works by: Reading in your code and understanding all the types and values in existence For each object, seeing what type its initial declaration indicates it may contain For each object, seeing all ways it’s used later on Complaining to the user if an object’s usage doesn’t match with its type Let’s walk through that type inference system in detail. Take the following snippet, in which TypeScript is emitting a type error about a member variable being erroneously called as a function: let firstName = "Cleopatra"; firstName.length(); // ~~~~~~ // This expression is not callable. // Type 'Number' has no call signatures TypeScript came to that complaint by, in order: Reading in the code and understanding there to be one object: firstName Concluding that firstName is of type string its initial value is a string, "Cleopatra" Seeing that the code is trying to access a .length member of firstName and call it like a function Complaining that the .length member of a string is a number, not a function (it can’t be called like a function) Understanding TypeScript’s type inference is an important skill for understanding TypeScript code.

…

. // Type 'Number' has no call signatures TypeScript came to that complaint by, in order: Reading in the code and understanding there to be one object: firstName Concluding that firstName is of type string its initial value is a string, "Cleopatra" Seeing that the code is trying to access a .length member of firstName and call it like a function Complaining that the .length member of a string is a number, not a function (it can’t be called like a function) Understanding TypeScript’s type inference is an important skill for understanding TypeScript code. Code snippets in this chapter and through the rest of this book will display more and more complex types that TypeScript will be able to infer from code. Kinds of Errors While writing TypeScript, the two kinds of “errors” you’ll come across most frequently are: Syntax: blocking TypeScript from being converted to JavaScript.

…

TypeScript in Action Freedom Through Restriction Precise Documentation Stronger Developer Tooling What TypeScript Is Not Getting Started in the TypeScript Playground Compiling Syntax Getting Started Locally Running Locally Editor Features Summary 2. The Type System What’s in a Type? Type Inferences in Detail Kinds of Errors Assignability Type Annotations Unnecessary Type Annotations Type Shapes Summary 3. Unions and Narrowing Union Types Declaring Union Types Union Properties Narrowing Assignment Narrowing Conditional Checks Summary 4. Literals Literal Types Literal Assignability Strict Null Checking The Billion Dollar Mistake Truthiness Narrowing Implicit Union Type Truthiness Summary

Practical OCaml by Joshua B. Smith

cellular automata, Debian, domain-specific language, duck typing, Free Software Foundation, functional programming, general-purpose programming language, Grace Hopper, higher-order functions, hiring and firing, John Conway, Paul Graham, slashdot, SpamAssassin, text mining, Turing complete, type inference, web application, Y2K

However, you probably want to interact with more than the OCaml type inference engine. WHAT IS TYPE INFERENCE? Type inference is the process by which the OCaml compiler figures out type information from your code. The compiler does this for two reasons: so that the programmer does not have to specify type information, and so that the types are used correctly. These compile-time type checks are what prevent you from using a function with the wrong type. In a language such as Python, these errors would show up only during runtime. Type inference is part of the polymorphic type checker found in ML dialects.

…

OCaml is not a dead language; it is constantly updated and worked on by a small group of fulltime researchers and the community at large. The small but active community develops the language and the standard library. INRIA is the core of OCaml development, but OCaml is used inside academic projects the world over. The language is also being improved, with a lot of work going into the type inference engine and tools such as Camlp4. Why This Book? Apress is committed to publishing the books that programmers need, and this book is one of the few English language books available on OCaml. Now is a good time for OCaml because the focus on security and correctness of programs will only become greater.

…

This chapter covers types—the concept of types is one of the most important in OCaml. It also covers variables and discusses the ramifications of the fact that OCaml is a constant language (meaning that data values are not really variable). Types in OCaml are important because they are the foundation upon which many of the compile-time checks are built. The type inference engine makes sure that the function return and input types are correct, eliminating a certain class of error. The OCaml type system is very flexible and enables the programmer to define types easily. An example of a class of error that can be eliminated by using types occurs in distance calculation.

Programming in Haskell by Graham Hutton

domain-specific language, Eratosthenes, first-past-the-post, functional programming, higher-order functions, type inference

On the other hand, the expression not 3 does not have a type under the above rule, because this would require that 3 :: Bool, which is not valid because 3 is not a logical value. Expressions such as not 3 that do not have a type are said to contain a type error, and are deemed to be invalid expressions. Because type inference precedes evaluation, Haskell programs are type safe, in the sense that type errors can never occur during evaluation. In practice, type inference detects a very large class of program errors, and is one of the most useful features of Haskell. Note, however, that the use of type inference does not eliminate the possibility that other kinds of error may occur during evaluation. For example, the expression 1 ‘div‘ 0 is well-typed, but produces an error when evaluated because the result of division by zero is undefined.

…

Powerful type system (chapters 3 and chapters 8) Most modern programming languages include some form of type system to detect incompatibility errors, such as erroneously attempting to add a number and a character. Haskell has a type system that usually requires little type information from the programmer, but allows a large class of incompatibility errors in programs to be automatically detected prior to their execution, using a sophisticated process called type inference. The Haskell type system is also more powerful than most languages, supporting very general forms of polymorphism and overloading, and providing a wide range of special purpose features concerning types. List comprehensions (chapter 5) One of the most common ways to structure and manipulate data in computing is using lists of values.

…

In the 1970s, John Backus developed FP (“Functional Programming”), a functional programming language that particularly emphasised the idea of higher-order functions and reasoning about programs. Also in the 1970s, Robin Milner and others developed ML (“Meta-Language”), the first of the modern functional programming languages, which introduced the idea of polymorphic types and type inference. In the 1970s and 1980s, David Turner developed a number of lazy functional programming languages, culminating in the commercially produced language Miranda (meaning “admirable”). In 1987, an international committee of programming language researchers initiated the development of Haskell (named after the logician Haskell Curry), a standard lazy functional programming language.

Haskell Programming: From First Principles by Christopher Allen, Julie Moronuki

book value, c2.com, en.wikipedia.org, fail fast, fizzbuzz, functional programming, heat death of the universe, higher-order functions, natural language processing, spaced repetition, tiling window manager, Turing complete, Turing machine, type inference, web application, Y Combinator

Here’s what the type signature looks like: Prelude> :type fromIntegral fromIntegral :: (Num b, Integral a) => a -> b So, it takes a value, 𝑎, of an Integral type and returns it as a value, 𝑏, of any Num type. Let’s see how that works with our fractional division problem: Prelude> 6 / fromIntegral (length [1, 2, 3]) 2.0 And now all is right with the world once again. 5.7 Type inference Haskell does not obligate us to assert a type for every expression or value in our programs because it has type inference. Type inference is an algorithm for determining the types of expressions. Haskell’s type inference is built on an extended version of the Damas-HindleyMilner type system. Haskell will infer the most generally applicable (polymorphic) type that is still correct. Essentially, the compiler starts from the values whose types it knows and then works out the types of the other values.

…

Working with a good type system can eliminate those tests that only check that you’re passing the right sort of data around, which can help tremendously. Haskell’s type system allows for a nifty feature known as type inference. We can declare our types when we write our programs, but the compiler will infer the types for expressions that have no declared type. It is better to have explicit type declarations in any nontrivial CHAPTER 5. TYPES 139 program, but type inference can be helpful as you’re learning and experimenting with writing new programs. An example of a type is Bool, which we remember from the last chapter. The Bool type is a set with two inhabitants, True and False.

…

Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 91 91 92 97 99 101 103 107 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 109 109 111 116 123 125 126 130 131 Types . . . . . . . . . . . . . . . . . . . . What are types? . . . . . . . . . . . . . . Querying and Reading Types . . . . Typeclass constrained type variables Currying . . . . . . . . . . . . . . . . . . Polymorphism . . . . . . . . . . . . . . Type inference . . . . . . . . . . . . . . Asserting types for declarations . . . Chapter Exercises . . . . . . . . . . . . Definitions . . . . . . . . . . . . . . . . . Follow-up resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 136 136 139 141 144 153 158 161 163 171 173 4 Basic datatypes 4.1 Basic Datatypes . . . . . . . . . . 4.2 Anatomy of a data declaration 4.3 Numeric types . . . . . . . . . . 4.4 Comparing values . . . . . . . . 4.5 Tuples . . . . . . . . . . . . . . . . 4.6 Lists . . . . . . . . . . . . . . . . . 4.7 Chapter Exercises . . . . . . . . 4.8 Definitions . . . . . . . . . . . . . 4.9 Answers . . . . . . . . . . . . . . . 5 Types 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 3 . . . . . . . . . . . . . . . . . . 6 Typeclasses 174 6.1 Typeclasses . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 CONTENTS 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11 6.12 6.13 6.14 6.15 6.16 6.17 7 4 What are typeclasses?

Functional Programming in Scala by Paul Chiusano, Rúnar Bjarnason

domain-specific language, functional programming, higher-order functions, iterative process, loose coupling, off-by-one error, type inference, web application

EXERCISE 4: Implement dropWhile,10 which removes elements from the List prefix as long as they match a predicate. Again, notice these functions take time proportional only to the number of elements being dropped—we do not need to make a copy of the entire List. Footnote 10mdropWhile has two argument lists to improve type inference. See sidebar. www.it-ebooks.info 41 def drop[A](l: List[A], n: Int): List[A] def dropWhile[A](l: List[A])(f: A => Boolean): List[A] SIDEBAR Type inference in Scala When writing functions like dropWhile, we will often place the List in the first argument group, and any functions, f that receive elements of the List in a later argument group. We can call this function with two sets of parentheses, like dropWhile(xs)(f), or we can partially apply it by supplying only the first argument dropWhile(xs).

…

Putting this all together for this case, our function will take as arguments the value to return in the case of the empty list, and the function to add an element to the result in the case of a nonempty list:12 Footnote 12mIn the Scala standard library, foldRight is a method on List and its arguments are curried similarly for better type inference. Listing 3.3 Right folds and simple uses def foldRight[A,B](l: List[A], z: B)(f: (A, B) => B): B = l match { case Nil => z case Cons(x, xs) => f(x, foldRight(xs, z)(f)) } def sum2(l: List[Int]) = foldRight(l, 0.0)(_ + _) def product2(l: List[Double]) = foldRight(l, 1.0)(_ * _) Again, placing f in its own argument group after l and z lets type inference determine the input types to f. See earlier sidebar. foldRight is not specific to any one type of element, and the value that is returned doesn't have to be of the same type as the elements either.

…

These concerns about variance are not very important for the present discussion and are more of an artifact of how Scala encodes data constructors via subtyping, so don't worry if this is not completely clear right now.3 Footnote 3mIt is certainly possible to write code without using variance annotations at all, and function signatures are sometimes simpler (while type inference often gets worse). Unless otherwise noted, we will be using variance annotations throughout this book, but you should feel free to experiment with both approaches. 3.2.1 Pattern matching Let's look in detail at the functions sum and product, which we place in the object List, sometimes called the companion object to List (see sidebar).

Real World Haskell by Bryan O'Sullivan, John Goerzen, Donald Stewart, Donald Bruce Stewart

bash_history, database schema, Debian, distributed revision control, domain-specific language, duck typing, en.wikipedia.org, Firefox, functional programming, general-purpose programming language, Guido van Rossum, higher-order functions, job automation, Larry Wall, lateral thinking, level 1 cache, machine readable, p-value, panic early, plutocrats, revision control, sorting algorithm, SQL injection, transfer pricing, type inference, web application, Yochai Benkler

In a dynamically typed language, all the pieces are 1×1 squares and always fit, so you have to constantly examine the resulting picture and check (through testing) whether it’s correct. Type Inference Finally, a Haskell compiler can automatically deduce the types of almost[3] all expressions in a program. This process is known as type inference. Haskell allows us to explicitly declare the type of any value, but the presence of type inference means that this is almost always optional, not something we are required to do. What to Expect from the Type System Our exploration of the major capabilities and benefits of Haskell’s type system will span a number of chapters.

…

showHex function, Pretty Printing a String side effects, Function Types and Purity, Be Careful of Side Effects blending C with Haskell, Be Careful of Side Effects signatures, The Type of a Function of More Than One Argument sin function, Numeric Types single quotes ('), Writing Character and String Literals single-character escape codes, Single-Character Escape Codes snd function, Functions over Lists and Tuples sockets, Basic Networking–TCP Syslog Client solution maps, Solving for Check Digits in Parallel sort function, Sequential Sorting source files, Haskell Source Files, and Writing Simple Functions–Understanding Evaluation by Example space leaks, Left Folds, Laziness, and Space Leaks, Space Leaks and Strict Evaluation–Learning to Use seq, Space Profiling spines for maps, A Brief Introduction to Maps split function, Text I/O, Supplying Random Numbers supplying random numbers, Supplying Random Numbers split-base Cabal flag, Dealing with Different Build Setups splitAt function, Working with Sublists SQL (Structured Query Language), Overview of HDBC SqlError type, Error Handling SqlValues type, SqlValue sqrt function, Numeric Types square brackets ([ ]), Lists, Useful Composite Data Types: Lists and Tuples, Exhaustive Patterns and Wild Cards, Recursive Types, Filename Matching character classes, Filename Matching exhaustive patterns, as a constructor, Exhaustive Patterns and Wild Cards lists, using, Lists recursive types and, Recursive Types type variables and, Useful Composite Data Types: Lists and Tuples -sstderr RTS option, Tuning for Performance, Collecting Runtime Statistics ST (state thread) monad, The ST Monad stack, Stacking Multiple Monad Transformers–Understanding Monad Transformers by Building One, Stacking Multiple Monad Transformers–Moving Down the Stack monad transformers, Stacking Multiple Monad Transformers–Moving Down the Stack standard module, Getting Started with ghci, the Interpreter starvation, Starvation state monads, The State Monad–Monads and Functors, Using the State Monad: Generating Random Values, Running the State Monad, Motivation: Boilerplate Avoidance, A Tiny Parsing Framework random values, generating, Using the State Monad: Generating Random Values running, Running the State Monad StateT monad transformer, Stacking Multiple Monad Transformers, Transformer Stacking Order Is Important transformer stacking order and, Transformer Stacking Order Is Important static types, Static Types stderr function, Standard Input, Output, and Error stdin function, Standard Input, Output, and Error stdout function, Standard Input, Output, and Error STM (software transactional memory), Software Transactional Memory–Using Invariants, STM and Safety I/O (input/output), STM and Safety strict evaluation, Lazy Evaluation, Space Leaks and Strict Evaluation–Learning to Use seq strict types, Efficient File Processing strictness, Strictness and Tail Recursion–Understanding Core string function, Pretty Printing a String string literals, Writing Character and String Literals String type, First Steps with Types, hGetContents, Efficient File Processing, Mixing and Matching String Types file processing and, Efficient File Processing hGetContents function and, hGetContents regular expressions, Mixing and Matching String Types strings, Strings and Characters, Passing String Data Between Haskell and C–Matching on Strings, Matching on Strings, Multiline String Literals multiline literals, Multiline String Literals passing data between C and Haskell, Passing String Data Between Haskell and C–Matching on Strings, Matching on Strings matching on, Matching on Strings strong types, Strong Types struct keyword (C/C++), The structure structural recursion, Explicit Recursion Structured Query Language (SQL), Overview of HDBC structures, Defining a New Data Type, The structure, Association Lists (see also data structures) stub versions of types/functions, Developing Haskell Code Without Going Nuts subtraction (-) option, Numeric Types subtype polymorphism, Polymorphism in Haskell suffixes function, Code Reuse Through Composition sum types, Generating Test Data synchronizing variable, Simple Communication Between Threads synonyms (types), Type Synonyms syntactic sugar, Desugaring of do Blocks syslog, Basic Networking System.Cmd module, Running External Programs System.Directory library, Deleting and Renaming Files System.Directory module, Making Use of Our Pattern Matcher, Directory and File Information, File Modification Times System.Environment module, Runtime Options System.Exit module, Program Termination System.FilePath module, Making Use of Our Pattern Matcher, A Naive Finding Function System.IO library, Working with Files and Handles, Standard Input, Output, and Error, Sizing a File Safely errors, Standard Input, Output, and Error files, sizing safely, Sizing a File Safely System.IO.Error module, I/O Exceptions System.Posix module, Predicates: From Poverty to Riches, While Remaining Pure System.Posix.Files module, File Modification Times System.Random module, Using the State Monad: Generating Random Values, Supplying Random Numbers supplying random numbers, Supplying Random Numbers System.Time module, ClockTime and CalendarTime System.Win32 module, Predicates: From Poverty to Riches, While Remaining Pure systems programming, Systems Programming in Haskell–Final Words on Pipes, Dates and Times–Extended Example: Piping dates and times, Dates and Times–Extended Example: Piping T \t (tab) character, Strings and Characters, A Note About Tabs Versus Spaces vs. spaces, A Note About Tabs Versus Spaces tab (\t) character, Strings and Characters, A Note About Tabs Versus Spaces vs. spaces, A Note About Tabs Versus Spaces tables (hash), Life Without Arrays or Hash Tables, Maps, Hashing Values, Turning Two Hashes into Many maps and, Maps turning two into many, Turning Two Hashes into Many tail function, Useful Composite Data Types: Lists and Tuples, Functions over Lists and Tuples, Recursion, Basic List Manipulation tail recursion, Strictness and Tail Recursion tails function, As-patterns, Code Reuse Through Composition suffixes function and, Code Reuse Through Composition take function, Functions over Lists and Tuples takeWhile function, Working with Sublists tan function, Numeric Types TCP, communicating with, Communicating with TCP–TCP Syslog Client templates (C++), Parameterized Types temporary files, Temporary Files Ternary type, Generating Test Data testing, Testing and Quality Assurance (see quality assurance) text, Warming Up: Portably Splitting Lines of Text–Infix Functions, Text I/O–Filename Matching, Escaping Text escaping, Escaping Text I/O (input/output), Text I/O–Filename Matching splitting lines of, Warming Up: Portably Splitting Lines of Text–Infix Functions text I/O, Text I/O–Filename Matching “text mode”, reading files, Warming Up: Portably Splitting Lines of Text Text.Regex.Posix module, Regular Expressions in Haskell then and else branches, Conditional Evaluation thread maps, The Main Thread and Waiting for Other Threads -threaded compiler option, Using Multiple Cores with GHC threaded runtime, Using Multiple Cores with GHC threads, Concurrent Programming with Threads, Simple Communication Between Threads, The Main Thread and Waiting for Other Threads–Communicating over Channels, Finding the Status of a Thread, Communication Between Threads communication between, Simple Communication Between Threads, Communication Between Threads finding status of, Finding the Status of a Thread waiting for other threads, The Main Thread and Waiting for Other Threads–Communicating over Channels throw function, Throwing Exceptions thunks, Lazy Evaluation TimeDiff type, TimeDiff for ClockTime times, Dates and Times–Extended Example: Piping, File Modification Times file modifications and, File Modification Times .tix files, Measuring Test Coverage with HPC toCalendarTime function, Using CalendarTime toInteger function, Numeric Types top level names, Introducing Local Variables toRational function, Numeric Types total functions, Partial and Total Functions toUpper function, Transforming Every Piece of Input toUTCTime function, Using CalendarTime transactions (database), Transactions transformer stacking, Transformer Stacking Order Is Important traverse function, Controlling Traversal, Density, Readability, and the Learning Process, Another Way of Looking at Traversal readability of, Density, Readability, and the Learning Process triple (3-tuple), Useful Composite Data Types: Lists and Tuples True Boolean value, Boolean Logic, Operators, and Value Comparisons truncate function, Representing JSON Data in Haskell, Numeric Types try keyword, Lookahead, First Steps with Exceptions, I/O Exceptions exceptions and, First Steps with Exceptions, I/O Exceptions I/O (input/output), I/O Exceptions tuples, Useful Composite Data Types: Lists and Tuples–Functions over Lists and Tuples, Functions over Lists and Tuples, Tuples, Algebraic Data Types, and When to Use Each algebraic data types and, Tuples, Algebraic Data Types, and When to Use Each functions for, Functions over Lists and Tuples two-dimensional arrays, Folding over Arrays two-dimensional vectors, Tuples, Algebraic Data Types, and When to Use Each :type command, First Steps with Types, Defining a New Data Type type constructors, Defining a New Data Type, Looking for Shared Patterns, Almost a State Monad Monads and, Looking for Shared Patterns, Almost a State Monad type inference, Type Inference, Type Inference Is a Double-Edged Sword–A More General Look at Rendering type keyword, Type Synonyms type signatures, Some Common Basic Types type variables, Useful Composite Data Types: Lists and Tuples, Polymorphism in Haskell polymorphism and, Polymorphism in Haskell type-based testing, QuickCheck: Type-Based Testing Typeable typeclass, Dynamic Exceptions typeclasses, Static Types, Using Typeclasses–Conclusion, Declaring Typeclass Instances, Important Built-in Typeclasses–Automatic Derivation, Automatic Derivation, Living in an Open World–How to Give a Type a New Identity, Relaxing Some Restrictions on Typeclasses, The Dreaded Monomorphism Restriction–Conclusion, Using Typeclasses, More Typeclass Instances automatic derivation, Automatic Derivation built-in, Important Built-in Typeclasses–Automatic Derivation declaring instances, Declaring Typeclass Instances instances, More Typeclass Instances monomorphism restriction, The Dreaded Monomorphism Restriction–Conclusion open world assumptions, Living in an Open World–How to Give a Type a New Identity restrictions, relaxing, Relaxing Some Restrictions on Typeclasses using, Using Typeclasses typed pointers, Typed Pointers types, First Steps with Types–A Simple Program, Why Care About Types?

…

Several Haskell compression libraries exist, all of which have simple interfaces: a compression function accepts an uncompressed string and returns a compressed string. We can use function composition to render JSON data to a string, and then compress to another string, postponing any decision on how to actually display or transmit the data. Type Inference Is a Double-Edged Sword A Haskell compiler’s ability to infer types is powerful and valuable. Early on, you’ll probably face a strong temptation to take advantage of type inference by omitting as many type declarations as possible. Let’s simply make the compiler figure the whole lot out! Skimping on explicit type information has a downside, one that disproportionately affects new Haskell programmers.

Programming Rust: Fast, Safe Systems Development by Jim Blandy, Jason Orendorff

bioinformatics, bitcoin, Donald Knuth, duck typing, Elon Musk, Firefox, fizzbuzz, functional programming, mandelbrot fractal, Morris worm, MVC pattern, natural language processing, reproducible builds, side project, sorting algorithm, speech recognition, Turing test, type inference, WebSocket

Given the function’s return type, it’s obvious that v must be a Vec<i16>, a vector of 16-bit signed integers; no other type would work. And from that it follows that each element of the vector must be an i16. This is exactly the sort of reasoning Rust’s type inference applies, allowing you to instead write: fn build_vector() -> Vec<i16> { let mut v = Vec::new(); v.push(10); v.push(20); v } These two definitions are exactly equivalent; Rust will generate the same machine code either way. Type inference gives back much of the legibility of dynamically typed languages, while still catching type errors at compile time. Functions can be generic: when a function’s purpose and implementation are general enough, you can define it to work on any set of types that meet the necessary criteria.

…

Other types can take similar steps: for example, HashSet and HashMap also use Iterator::size_hint to choose an appropriate initial size for their hash table. One note about type inference: at the top of this section, it’s a bit strange to see the same call, std::env::args().collect(), produce four different kinds of collections depending on its context. The return type of collect is its type parameter, so the first two calls are equivalent to the following: let args = std::env::args().collect::<String>(); let args = std::env::args().collect::<HashSet<String>>(); But as long as there’s only one type that could possibly work as collect’s argument, Rust’s type inference will supply it for you. When you spell out the type of args, you ensure this is the case.

…

The fractional part may consist of a lone decimal point, so 5. is a valid floating-point constant. If a floating-point literal lacks a type suffix, Rust infers whether it is an f32 or f64 from the context, defaulting to f64 if both would be possible. (Similarly, C, C++, and Java all treat unsuffixed floating-point literals as double values.) For the purposes of type inference, Rust treats integer literals and floating-point literals as distinct classes: it will never infer a floating-point type for an integer literal, or vice versa. Some examples of floating-point literals: Literal Type Mathematical value –1.5625 Inferred −(1 9⁄16) 2.

Rust Programming by Example by Guillaume Gomez, Antoni Boucher

Debian, MVC pattern, type inference, web application

A great example of this power is the Servo web engine, also developed by Mozilla. Rust is multi-paradigm: it can be used in an imperative or functional way and you can even write concurrent applications safely. It is statically typed, meaning that every type must be known at compile time, but since it uses type inference, we can omit the type for most local variables. It is also strongly typed, which means that its type system prevents the programmer from some kinds of errors, such as using the wrong type for a function parameter. And Rust is very good at writing concurrent software because it prevents data races, which is concurrent access to a variable where one is a write; this is an undefined behavior in other languages.

…

This macro prints the text between parentheses, followed by a new line. We'll see what is a macro in the Macros section. Variables We'll now change the previous program to add a variable: fn main() { let name = "world"; println!("Hello, {}!", name); } The {} part in the string literal is replaced by the content of the name variable. Here, we see the type inference in action—we don't have to specify the type of the name variable and the compiler will infer it for us. We could have also written the type ourselves: let name: &str = "world"; (From now on, I'll omit the main function, but this code should be written inside the function.) In Rust, variables are immutable by default.

…

For instance, a number of the u8 type can be between 0 and 255, inclusive. And a number of the i16 type can be between -32768 and 32767, inclusive. The size variants are the pointer-sized integer types: usize and isize are 64-bit on a 64-bit CPU. The default integer type is i32, which means that this type will be used by the type inference when it cannot choose a more specific type. Floating-point types There are two floating-point types: f32 and f64, the latter being the default. The number following f represents the number of bits for the type. An example value is 0.31415e1. Boolean type The bool type admits two values: true and false.

The Rust Programming Language by Steve Klabnik, Carol Nichols

anti-pattern, billion-dollar mistake, bioinformatics, business logic, business process, cryptocurrency, data science, DevOps, duck typing, Firefox, functional programming, Internet of things, iterative process, pull request, reproducible builds, Ruby on Rails, type inference

Macros Adding Custom Failure Messages Checking for Panics with should_panic Controlling How Tests Are Run Running Tests in Parallel or Consecutively Showing Function Output Running a Subset of Tests by Name Ignoring Some Tests Unless Specifically Requested Test Organization Unit Tests Integration Tests Summary 12 AN I/O PROJECT: BUILDING A COMMAND LINE PROGRAM Accepting Command Line Arguments Reading the Argument Values Saving the Argument Values in Variables Reading a File Refactoring to Improve Modularity and Error Handling Separation of Concerns for Binary Projects Fixing the Error Handling Extracting Logic from main Splitting Code into a Library Crate Developing the Library’s Functionality with Test-Driven Development Writing a Failing Test Writing Code to Pass the Test Working with Environment Variables Writing a Failing Test for the Case-Insensitive search Function Implementing the search_case_insensitive Function Writing Error Messages to Standard Error Instead of Standard Output Checking Where Errors Are Written Printing Errors to Standard Error Summary 13 FUNCTIONAL LANGUAGE FEATURES: ITERATORS AND CLOSURES Closures: Anonymous Functions That Can Capture Their Environment Creating an Abstraction of Behavior with Closures Closure Type Inference and Annotation Storing Closures Using Generic Parameters and the Fn Traits Limitations of the Cacher Implementation Capturing the Environment with Closures Processing a Series of Items with Iterators The Iterator Trait and the next Method Methods That Consume the Iterator Methods That Produce Other Iterators Using Closures That Capture Their Environment Creating Our Own Iterators with the Iterator Trait Improving Our I/O Project Removing a clone Using an Iterator Making Code Clearer with Iterator Adaptors Comparing Performance: Loops vs.

…

Syntax Destructuring to Break Apart Values Ignoring Values in a Pattern Creating References in Patterns with ref and ref mut Extra Conditionals with Match Guards @ Bindings Summary 19 ADVANCED FEATURES Unsafe Rust Unsafe Superpowers Dereferencing a Raw Pointer Calling an Unsafe Function or Method Accessing or Modifying a Mutable Static Variable Implementing an Unsafe Trait When to Use Unsafe Code Advanced Lifetimes Ensuring One Lifetime Outlives Another with Lifetime Subtyping Lifetime Bounds on References to Generic Types Inference of Trait Object Lifetimes Advanced Traits Specifying Placeholder Types in Trait Definitions with Associated Types Default Generic Type Parameters and Operator Overloading Fully Qualified Syntax for Disambiguation: Calling Methods with the Same Name Using Supertraits to Require One Trait’s Functionality Within Another Trait Using the Newtype Pattern to Implement External Traits on External Types Advanced Types Using the Newtype Pattern for Type Safety and Abstraction Creating Type Synonyms with Type Aliases The Never Type That Never Returns Dynamically Sized Types and the Sized Trait Advanced Functions and Closures Function Pointers Returning Closures Summary 20 FINAL PROJECT: BUILDING A MULTITHREADED WEB SERVER Building a Single-Threaded Web Server Listening to the TCP Connection Reading the Request A Closer Look at an HTTP Request Writing a Response Returning Real HTML Validating the Request and Selectively Responding A Touch of Refactoring Turning Our Single-Threaded Server into a Multithreaded Server Simulating a Slow Request in the Current Server Implementation Improving Throughput with a Thread Pool Graceful Shutdown and Cleanup Implementing the Drop Trait on ThreadPool Signaling to the Threads to Stop Listening for Jobs Summary A KEYWORDS Keywords Currently in Use Keywords Reserved for Future Use B OPERATORS AND SYMBOLS Operators Non-operator Symbols C DERIVABLE TRAITS Debug for Programmer Output PartialEq and Eq for Equality Comparisons PartialOrd and Ord for Ordering Comparisons Clone and Copy for Duplicating Values Hash for Mapping a Value to a Value of Fixed Size Default for Default Values D MACROS The Difference Between Macros and Functions Declarative Macros with macro_rules!

…

Let’s try it: $ cargo build Compiling guessing_game v0.1.0 (file:///projects/guessing_game) error[E0308]: mismatched types --> src/main.rs:23:21 | 23 | match guess.cmp(&secret_number) { | ^^^^^^^^^^^^^^ expected struct `std::string::String`, found integral variable | = note: expected type `&std::string::String` = note: found type `&{integer}` error: aborting due to previous error Could not compile `guessing_game`. The core of the error states that there are mismatched types. Rust has a strong, static type system. However, it also has type inference. When we wrote let guess = String::new(), Rust was able to infer that guess should be a String and didn’t make us write the type. The secret_number, on the other hand, is a number type. A few number types can have a value between 1 and 100: i32, a 32-bit number; u32, an unsigned 32-bit number; i64, a 64-bit number; as well as others.

Coders at Work by Peter Seibel

Ada Lovelace, Bill Atkinson, bioinformatics, Bletchley Park, Charles Babbage, cloud computing, Compatible Time-Sharing System, Conway's Game of Life, Dennis Ritchie, domain-specific language, don't repeat yourself, Donald Knuth, fallacies of distributed computing, fault tolerance, Fermat's Last Theorem, Firefox, Free Software Foundation, functional programming, George Gilder, glass ceiling, Guido van Rossum, history of Unix, HyperCard, industrial research laboratory, information retrieval, Ken Thompson, L Peter Deutsch, Larry Wall, loose coupling, Marc Andreessen, Menlo Park, Metcalfe's law, Multics, no silver bullet, Perl 6, premature optimization, publish or perish, random walk, revision control, Richard Stallman, rolodex, Ruby on Rails, Saturday Night Live, side project, slashdot, speech recognition, systems thinking, the scientific method, Therac-25, Turing complete, Turing machine, Turing test, type inference, Valgrind, web application

In the original source, lots of type inference is going on and the source language is carefully crafted so that type inference is possible. In the intermediate language, the type system is much more general, much more expressive because it's more explicit: every function argument is decorated with its type. There's no type inference, there's just type checking for the intermediate language. So it's an explicitly typed language whereas the source language is implicitly typed. Type inference is based on a carefully chosen set of rules that make sure that it just fits within what the type inference engine can figure out.

…

Type inference is based on a carefully chosen set of rules that make sure that it just fits within what the type inference engine can figure out. If you transform the program by a source-to-source transformation, maybe you've now moved outside that boundary. Type inference can't reach it any more. So that's bad for an optimization. You don't want optimizations to have to worry about whether you might have just gone out of the boundaries of type inference. Seibel: So that points out that there are programs that are correct, because you're assuming a legitimate source-to-source transformation, which, if you had written it by hand, the compiler would have said, “I'm sorry; I can't type this.” Peyton Jones: Right. That's the nature of static type systems—and why dynamic languages are still interesting and important.

…

You see crazy, idiotic statements about how dynamic language are going to totally unseat Java and static languages, which is nonsense. But the academics are out there convinced static type systems are the ultimate end and they're researching particular kinds of static type systems like the ML, Hindley-Milner type inferences and it's completely divorced from industry. Seibel: Why is that? Because it's not solving any real problems or because it's only a partial solution? Eich: We did some work with SML New Jersey to self-host the reference implementation of JavaScript, fourth edition, which is now defunct. We were trying to make a definitional interpreter.

Erlang Programming by Francesco Cesarini

cloud computing, fault tolerance, finite state, functional programming, higher-order functions, loose coupling, revision control, RFC: Request For Comment, social bookmarking, sorting algorithm, Turing test, type inference, web application

Trace BIFs, the dbg Tracer, and Match Specifications . . . . . . . . . . . . . . . . . . . . . . . . 355 Introduction The Trace BIFs Process Trace Flags Inheritance Flags Garbage Collection and Timestamps Tracing Calls with the trace_pattern BIF The dbg Tracer Getting Started with dbg Tracing and Profiling Functions Tracing Local and Global Function Calls Distributed Environments Redirecting the Output Match Specifications: The fun Syntax Generating Specifications Using fun2ms Difference Between ets and dbg Match Specifications Match Specifications: The Nuts and Bolts 355 357 358 360 361 362 365 366 369 369 371 371 374 375 382 383 Table of Contents | ix The Head Conditions The Specification Body Saving Match Specifications Further Reading Exercises 383 384 387 390 391 392 18. Types and Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 Types in Erlang An Example: Records with Typed Fields Erlang Type Notation TypEr: Success Types and Type Inference Dialyzer: A DIscrepancy AnaLYZer for ERlang Programs Documentation with EDoc Documenting usr_db.erl Running EDoc Types in EDoc Going Further with EDoc Exercises 395 395 396 399 401 402 403 405 407 408 410 19. EUnit and Test-Driven Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 Test-Driven Development EUnit How to Use EUnit Functional Testing, an Example: Tree Serialization The EUnit Infrastructure Assert Macros Test-Generating Functions EUnit Test Representation Testing State-Based Systems Fixtures: Setup and Cleanup Testing Concurrent Programs in Erlang Exercises 411 412 413 413 416 416 416 417 418 418 419 420 20.

…

.‖ Types are determined at runtime, as is the viability of the operation you ‡ Variables can also begin with an underscore; these play a role in pattern matching and are discussed in the section “Pattern Matching” on page 33. § We cover side effects and destructive operations later in the book. ‖ Other languages can avoid variable declarations for other reasons. Haskell, for instance, uses a type inference algorithm to deduce types of variables. 30 | Chapter 2: Basic Erlang are trying to execute on the variable. The following code attempting to multiply an atom by an integer will compile (with compiler warnings), but will result in a runtime error when you try to execute it: Var = one, Double = Var * 2 At first, using variables that start with capital letters might feel counterintuitive, but you’ll get used to it quickly.

…

However, including the parameter name—assuming it is chosen to reflect its purpose— improves the documentation.* * The EDoc system described later in the chapter will automatically include parameter names in its generated type documentation even if they do not appear in the –spec statement. 398 | Chapter 18: Types and Documentation TypEr: Success Types and Type Inference The TypEr system, built by Tobias Lindahl and Kostis Sagonas,† is used to check the validity of –spec annotations, as well as to infer the types of functions in modules without type annotations. You use TypEr from the command line. You can see the full range of options by typing: typer --help Taking the example of the mobile user database from Chapter 10, the following command: typer --show usr.erl usr_db.erl gives the following output (shortened for brevity): Unknown functions: [{ets,safefixtable,2}] %% File: "usr.erl" %% ---------------spec start() -> 'ok' | {'error','starting'}.

Learn You a Haskell for Great Good!: A Beginner's Guide by Miran Lipovaca

fault tolerance, functional programming, higher-order functions, loose coupling, type inference

Static typing means that a lot of possible errors can be caught at compile time. If you try to add together a number and a string, for example, the compiler will whine at you. Haskell uses a very good type system that has type inference. This means that you don’t need to explicitly label every piece of code with a type, because Haskell’s type system can intelligently figure it out. For example, if you say a = 5 + 4, you don’t need to tell Haskell that a is a number—it can figure that out by itself. Type inference makes it easier for you to write code that’s more general. If you write a function that takes two parameters and adds them together, but you don’t explicitly state their type, the function will work on any two parameters that act like numbers.

…

If you write a program that tries to divide a Boolean type with a number, it won’t compile. This is good because it’s better to catch those kinds of errors at compile time, rather than having your program crash later on. Everything in Haskell has a type, so the compiler can reason quite a lot about your program before compiling it. Unlike Java or Pascal, Haskell has type inference. If we write a number, for example, we don’t need to tell Haskell it’s a number, because it can infer that on its own. So far, we’ve covered some of the basics of Haskell with only a very superficial glance at types, but understanding the type system is a very important part of learning Haskell.

…

In order for this to be a real type that a value can be part of, it must have all its type parameters filled up. So if we pass Char as the type parameter to Maybe, we get a type of Maybe Char. The value Just 'a' has a type of Maybe Char, for example. Most of the time, we don’t pass types as parameters to type constructors explicitly. That’s because Haskell has type inference. So when we make a value Just 'a', for example, Haskell figures out that it’s a Maybe Char. If we want to explicitly pass a type as a type parameter, we must do it in the type part of Haskell, which is usually after the :: symbol. This can come in handy if, for example, we want a value of Just 3 to have the type Maybe Int.

Python for Data Analysis: Data Wrangling with Pandas, NumPy, and IPython by Wes McKinney

Bear Stearns, business process, data science, Debian, duck typing, Firefox, general-purpose programming language, Google Chrome, Guido van Rossum, index card, p-value, quantitative trading / quantitative finance, random walk, recommendation engine, sentiment analysis, side project, sorting algorithm, statistical model, Two Sigma, type inference

., no delimiters) read_clipboard Version of read_table that reads data from the clipboard; useful for converting tables from web pages read_excel Read tabular data from an Excel XLS or XLSX file read_hdf Read HDF5 files written by pandas read_html Read all tables found in the given HTML document read_json Read data from a JSON (JavaScript Object Notation) string representation read_msgpack Read pandas data encoded using the MessagePack binary format read_pickle Read an arbitrary object stored in Python pickle format read_sas Read a SAS dataset stored in one of the SAS system’s custom storage formats read_sql Read the results of a SQL query (using SQLAlchemy) as a pandas DataFrame read_stata Read a dataset from Stata file format read_feather Read the Feather binary file format I’ll give an overview of the mechanics of these functions, which are meant to convert text data into a DataFrame. The optional arguments for these functions may fall into a few categories: Indexing Can treat one or more columns as the returned DataFrame, and whether to get column names from the file, the user, or not at all. Type inference and data conversion This includes the user-defined value conversions and custom list of missing value markers. Datetime parsing Includes combining capability, including combining date and time information spread over multiple columns into a single column in the result. Iterating Support for iterating over chunks of very large files.

…

It’s normal to feel overwhelmed by the number of different parameters (read_csv has over 50 as of this writing). The online pandas documentation has many examples about how each of them works, so if you’re struggling to read a particular file, there might be a similar enough example to help you find the right parameters. Some of these functions, like pandas.read_csv, perform type inference, because the column data types are not part of the data format. That means you don’t necessarily have to specify which columns are numeric, integer, boolean, or string. Other data formats, like HDF5, Feather, and msgpack, have the data types stored in the format. Handling dates and other custom types can require extra effort.

…

frompyfunc function, Writing New ufuncs in Python from_codes method, Categorical Type in pandas full function, Creating ndarrays full_like function, Creating ndarrays functions, Functions(see also universal functions) about, Functions accessing variables, Namespaces, Scope, and Local Functions anonymous, Anonymous (Lambda) Functions as objects, Functions Are Objects-Functions Are Objects currying, Currying: Partial Argument Application errors and exception handling, Errors and Exception Handling exponentially-weighted, Exponentially Weighted Functions generators and, Generators-Exceptions in IPython grouping with, Grouping with Functions in Python, Function and object method calls lambda, Anonymous (Lambda) Functions magic, About Magic Commands-About Magic Commands namespaces and, Namespaces, Scope, and Local Functions object introspection, Introspection partial argument application, Currying: Partial Argument Application profiling line by line, Profiling a Function Line by Line-Profiling a Function Line by Line returning multiple values, Returning Multiple Values sequence, Built-in Sequence Functions-reversed transforming data using, Transforming Data Using a Function or Mapping type inference in, Reading and Writing Data in Text Format writing fast NumPy functions with Numba, Writing Fast NumPy Functions with Numba-Creating Custom numpy.ufunc Objects with Numba functools module, Currying: Partial Argument Application G gamma function, Pseudorandom Number Generation generatorsabout, Generators generator expressions for, Generator expresssions itertools module and, itertools module get method, Default values, Vectorized String Functions in pandas GET request (HTTP), Interacting with Web APIs getattr function, Attributes and methods getroot method, Parsing XML with lxml.objectify get_chunk method, Reading Text Files in Pieces get_dummies function, Computing Indicator/Dummy Variables, Creating dummy variables for modeling, Interfacing Between pandas and Model Code get_indexer method, Unique Values, Value Counts, and Membership get_value method, Selection with loc and iloc GIL (global interpreter lock), Why Not Python?

Clojure Programming by Chas Emerick, Brian Carper, Christophe Grand

Amazon Web Services, Benoit Mandelbrot, cloud computing, cognitive load, continuous integration, database schema, domain-specific language, don't repeat yourself, drop ship, duck typing, en.wikipedia.org, failed state, finite state, Firefox, functional programming, game design, general-purpose programming language, Guido van Rossum, higher-order functions, Larry Wall, mandelbrot fractal, no silver bullet, Paul Graham, platform as a service, premature optimization, random walk, Ruby on Rails, Schrödinger's Cat, semantic web, software as a service, sorting algorithm, SQL injection, Turing complete, type inference, web application

*warn-on-reflection* true) ;= true (defn first-char-of-either [a b] (.substring ^String (or a b) 0 1)) ; Reflection warning, NO_SOURCE_PATH:2 - call to substring can't be resolved. ;= #'user/first-char-of-either Note Such cases are rarely found in the wild, because type hints are usually put upstream of interop calls, resulting in the type of the macro form being determined through type inference: (defn first-char-of-either [^String a ^String b] (.substring (or a b) 0 1)) ;= #'user/first-char-of-either We can verify that the hint metadata on the or expression is lost; here, the expression, with metadata: (binding [*print-meta* true] (prn '^String (or a b))) ; ^{:tag String, :line 1} (or a b) But if we macroexpand the same expression, that metadata is gone: (binding [*print-meta* true] (prn (macroexpand '^String (or a b)))) ; (let* [or__3548__auto__ a] ; (if or__3548__auto__ or__3548__auto__ (clojure.core/or b))) However, there’s no reason why the type hint on the or expression can’t be preserved; doing so simply requires using &form effectively in its macro definition.

…

We cover primitive type declarations in Declare Functions to Take and Return Primitives. Avoiding reflective interop calls is key to ensuring maximal performance in code that is CPU-bound. In practice, little type-hinting is required in order to avoid reflection entirely, since the Clojure compiler provides for type inference based on the known types of literals, constructor calls, and method return types. To illustrate this, let’s add a type hint to some code in order to optimize it. Here’s a function that returns a provided String, capitalized: Example 9-12. An unhinted capitalization function (defn capitalize [s] (-> s (.charAt 0) Character/toUpperCase (str (.substring s 1)))) This implementation works, but we’d probably like to speed it up a little bit: Example 9-13.

…

We can address this by adding a single type hint (notice the ^String addition): (defn fast-capitalize [^String s] (-> s (.charAt 0) Character/toUpperCase (str (.substring s 1)))) This will eliminate all three reflective calls. How can just one type hint impact all three reflective calls? This is where the Clojure compiler’s type inference comes into play: The let-bound name s is explicitly type-hinted to be a String. Therefore… …the .charAt call can be compiled down to a direct call to String.charAt. The compiler knows that this method returns a char, so… …it can properly select the char variant of Character.toUpperCase (rather than its int override).

Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14 by Scott Meyers

premature optimization, type inference

But bear in mind that C++ breaks no new ground in adopting what is generally known in the programming languages world as type inference. Other statically typed procedural languages (e.g., C#, D, Scala, Visual Basic) have a more or less equivalent feature, to say nothing of a variety of statically typed functional languages (e.g., ML, Haskell, OCaml, F#, etc.). In part, this is due to the success of dynamically typed languages such as Perl, Python, and Ruby, where variables are rarely explicitly typed. The software development community has extensive experience with type inference, and it has demonstrated that there is nothing contradictory about such technology and the creation and maintenance of large, industrial-strength code bases.

…

type deduction, Deducing Types-Item 3: Understand decltype.(see also template, type deduction) for auto, Function Arguments-Item 2: Understand auto type deduction. emplace_back and, Item 24: Distinguish universal references from rvalue references. universal references and, Item 24: Distinguish universal references from rvalue references. type inference (see type deduction) type traits, Item 9: Prefer alias declarations to typedefs.-Item 9: Prefer alias declarations to typedefs. type transformations, Item 9: Prefer alias declarations to typedefs. typedefs, reference collapsing and, Item 28: Understand reference collapsing. typeid and viewing deduced types, Runtime Output-Runtime Output typenamedependent type and, Item 9: Prefer alias declarations to typedefs.

Reactive Messaging Patterns With the Actor Model: Applications and Integration in Scala and Akka by Vaughn Vernon

A Pattern Language, business intelligence, business logic, business process, cloud computing, cognitive dissonance, domain-specific language, en.wikipedia.org, fault tolerance, finite state, functional programming, Internet of things, Kickstarter, loose coupling, remote working, type inference, web application

Click here to view code image * * * var shoppingCart = new ShoppingCart val differentCart = new ShoppingCart shoppingCart = differentCart // valid expression * * * Note also that in both shoppingCart declarations, the code doesn’t provide a type, just a named reference. That’s because you can use Scala’s type inference as a shorthand. Type inference means that the Scala compiler can analyze the code and detect the type that is implied. It actually works out the same as declaring the type explicitly. Click here to view code image val shoppingCart: ShoppingCart = new ShoppingCart Now, let’s get back to constructors. Here’s how you make the ShoppingCart require one constructor parameter, or what Scala calls a class argument: Click here to view code image * * * class ShoppingCart(val maximumItems:Int) extends ItemContainer { ... } * * * Now a client of ShoppingCart must pass an Int parameter as it creates each instance.

…

The numbers that pass the if (...) filter will be yielded as part of the result. The result is referenced by evenNumbers, which is the Vector of the numbers 2, 4, 6, 8, and 10. Because the source of the iteration is a Vector of Int, the comprehension knows to yield the result into a Vector of Int. Thus, Scala type inference ensures that evenNumbers references a Vector of Int, even though there is no type specified with the declaration of evenNumbers. Here’s a different way to achieve the same result, which is more elegant Scala code: * * * val evenNumbers = for { number <- numbers if number % 2 == 0 } yield number * * * If you did decide to declare the evenNumbers reference fully, it would look like this: Click here to view code image val evenNumbers: Vector[Int] = ...

Purely Functional Data Structures by Chris Okasaki

Donald Knuth, Ford Model T, functional programming, higher-order functions, reversible computing, Turing machine, type inference

Brodal and Okasaki simplify this implementation in [BO96], using skew binomial heaps (Section 9.3.2) and structural abstraction (Section 10.2.2). Polymorphic Recursion Several attempts have been made to extend Standard ML with polymorphic recursion, such as [Myc84, Hen93, KTU93]. One complication is that type inference is undecidable in the presence of polymorphic recursion [Hen93, KTU93], even though it is tractable in practice. Haskell sidesteps this problem by allowing polymorphic recursion whenever the programmer provides an explicit type signature. 11 Implicit Recursive Slowdown In Section 9.2.3, we saw how lazy redundant binary numbers support both increment and decrement functions in 0(1) amortized time.

…

A dichromatic framework for balanced trees. In IEEE Symposium on Foundations of Computer Science, pages 8-21, October 1978. (pp. 24,29, 99) [GT86] Hania Gajewska and Robert E. Tarjan. Deques with heap order. Information Processing Letters, 22(4): 197-200, April 1986. (p. 113) [Hen93] Fritz Henglein. Type inference with polymorphic recursion. ACM Transactions on Programming Languages and Systems, 15(2):253-289, April 1993. (p. 170) [HJ94] Paul Hudak and Mark P. Jones. Haskell vs. Ada vs. C++ vs An experiment in software prototyping productivity, 1994. (p. 1) [HM76] Peter Henderson and James H. Morris, Jr.

Python for Data Analysis by Wes McKinney

Alignment Problem, backtesting, Bear Stearns, cognitive dissonance, crowdsourcing, data science, Debian, duck typing, Firefox, functional programming, Google Chrome, Guido van Rossum, index card, machine readable, random walk, recommendation engine, revision control, sentiment analysis, Sharpe ratio, side project, sorting algorithm, statistical model, type inference

The options for these functions fall into a few categories: Indexing: can treat one or more columns as the returned DataFrame, and whether to get column names from the file, the user, or not at all. Type inference and data conversion: this includes the user-defined value conversions and custom list of missing value markers. Datetime parsing: includes combining capability, including combining date and time information spread over multiple columns into a single column in the result. Iterating: support for iterating over chunks of very large files. Unclean data issues: skipping rows or a footer, comments, or other minor things like numeric data with thousands separated by commas. Type inference is one of the more important features of these functions; that means you don’t have to specify which columns are numeric, integer, boolean, or string.

…

.: return x + y In [135]: add_them = np.frompyfunc(add_elements, 2, 1) In [136]: add_them(np.arange(8), np.arange(8)) Out[136]: array([0, 2, 4, 6, 8, 10, 12, 14], dtype=object) Functions created using frompyfunc always return arrays of Python objects which isn’t very convenient. Fortunately, there is an alternate, but slightly less featureful function numpy.vectorize that is a bit more intelligent about type inference: In [137]: add_them = np.vectorize(add_elements, otypes=[np.float64]) In [138]: add_them(np.arange(8), np.arange(8)) Out[138]: array([ 0., 2., 4., 6., 8., 10., 12., 14.]) These functions provide a way to create ufunc-like functions, but they are very slow because they require a Python function call to compute each element, which is a lot slower than NumPy’s C-based ufunc loops: In [139]: arr = randn(10000) In [140]: %timeit add_them(arr, arr) 100 loops, best of 3: 2.12 ms per loop In [141]: %timeit np.add(arr, arr) 100000 loops, best of 3: 11.6 us per loop There are a number of projects under way in the scientific Python community to make it easier to define new ufuncs whose performance is closer to that of the built-in ones.

Smart and Gets Things Done: Joel Spolsky's Concise Guide to Finding the Best Technical Talent by Joel Spolsky

AOL-Time Warner, Build a better mousetrap, David Heinemeier Hansson, functional programming, knowledge worker, linear programming, no silver bullet, nuclear winter, off-by-one error, Ruby on Rails, Sand Hill Road, Silicon Valley, sorting algorithm, Superbowl ad, the scientific method, type inference, unpaid internship

And while everyone else their age was running around playing “soccer” (this is a game many kids who can’t program computers play that involves kicking a spherical object called a “ball” with their feet (I know, it sounds weird)), they were in their dad’s home office trying to get the Linux kernel to compile. Instead of chasing girls in the playground, they were getting into flamewars on Usenet about the utter depravity of programming languages that don’t implement Haskell-style type inference. Instead of starting a band in their garage, they were implementing a cool hack so that when their neighbor stole bandwidth over their openaccess Wi-Fi point, all the images on the web appeared upside-down. BWA HA HA HA HA! So, unlike, say, the fields of law or medicine, over here in software development, by the time these kids are in their second or third year in college, they are pretty darn good programmers.

Concepts, Techniques, and Models of Computer Programming by Peter Van-Roy, Seif Haridi

computer age, Debian, discrete time, Donald Knuth, Eratosthenes, fault tolerance, functional programming, G4S, general-purpose programming language, George Santayana, John von Neumann, Lao Tzu, Menlo Park, natural language processing, NP-complete, Paul Graham, premature optimization, sorting algorithm, the Cathedral and the Bazaar, Therac-25, Turing complete, Turing machine, type inference

There is an important lesson to be learned here. Defining a recursive type should be done before writing the recursive function that uses it. Otherwise it is easy to be misled by an apparently simple function that is incorrect. This is true even in functional languages that do type inference, such as Standard ML and Haskell. Type inference can verify that a recursive type is used correctly, but the design of a recursive type remains the programmer’s responsibility. 3.4.2.7 Sorting with mergesort We define a function that takes a list of numbers or atoms and returns a new list sorted in ascending order. It uses the comparison operator <, so all elements have to be of the same type (all integers, all floats, or all atoms).

…

This means we would like to compile a component separately, i.e., without knowing about other components. We would also like the final program, in which all components are assembled, to be as efficient and compact as possible. This means we would like to do compile-time analysis, e.g., type checking, Haskell-style type inference, or global optimization. There is a strong tension between these two desires. If the compilation is truly separate, then analysis cannot cross component boundaries. To do a truly global analysis, the compiler must in general be able to look at the whole program at once. This means that for many statically typed languages, compiling large programs (more than, say, a million lines of source code) requires much time and memory.

…

. , see parameter passing pattern matching case statement, 6, 67 function (in Erlang), 388 Haskell, 309 receive expression (in Erlang), 391 reduction rule semantics, 784 PDA (procedural data abstraction), 420 pencil, xviii Pentium III processor, 201, 471 performance cluster computing, 711 competitive concurrency, 254 constraint programming, 758 Cray-1 supercomputer, 175 declarative programming, 313 dictionary, 201 distributed stream, 724 lazy language, 289, 342 measuring, 167 memoization, 25, 315 mobile object, 724 monitor, 597 Mozart Programming System, 201, 379 personal computer, 175 price of concurrency, 339 record field access, 438 role of optimization, 177, 265, 302 role of parallelism, 237, 322 transitive closure, 471 word-of-mouth simulation, 486 permanent failure, 739 permutations, 2 persistence data structure, 149, 297 database, 654 Erlang, 387 transaction, 600 personal computer, 3, 252, 254, 289, 304 low-cost, 74, 175 pessimistic scheduling, 603 Phidani Software, 642 π calculus, xvii, 41, 54, 805 pipeline, 259 pixel, 556 placeholder dataflow variable, 86 future (in Multilisp), 336 GUI design, 686, 703 planning flight, 671 WARPLAN, 621 Plotkin, Gordon, 779 point resting, 338 synchronization, 333 two-dimensional space, 554 pointer, 76 content edge, 733 888 Index dependency, 459 dynamic typing, 106 garbage collection, 76 memory block, 480 resource, 480 state, 733 POLA (Principle of Least Authority), 209 polymorphism, 18, 106, 425, 462, 493 active objects, 429 ad-hoc, 429 apportioning responsibility, 425 example, 530 Haskell, 312 object-oriented programming, 490 port objects, 429 stream objects, 429 universal, 429 Ponsard, Christophe, 545 port (explicit state), 349, 719, 848 communication from inside encapsulated search, 673 distributed semantics, 383 Port.sendRecv operation, 673 portal, 476 postcondition, 441, 521 potential function, 175 precondition, 441, 521 predicate calculus, 633 preemption, 252 preprocessor, 318 DCG (in Prolog), 649 design patterns, 536 extended DCG (in Prolog), 140 fallacy of, 318 presentation model (in GUI), 695 principle abstraction, 410 avoid changing interfaces, 458 avoid premature optimization, 177, 452 balance planning and refactoring, 452 centralized first, distributed later, 745 class is final by default, 492 compartmentalize responsibility, 425, 451 concentrate explicit state, 412 creative extension, xiv, 844 decisions at right level, 460 declarative concurrency, 242, 281 document component interfaces, 451 documented violations, 460 eager default, lazy declared, 330 encapsulate design decisions, 458 enriching control (in logic programming), 640 error confinement, 90 “everything should be an object”, 542 exploit data abstraction uniformity, 543 form mirrors content, 544 freely exchange knowledge, 451 function structure follows type structure, 135 functional abstraction, 4 last call optimization, 72 layered language design, 850 least authority (POLA), 209 least expressiveness, 323 least privilege, 209 minimize dependencies, 387, 459 minimize indirections, 459 model independence, 457 more is not better or worse, just different, xx Mozart design rules, xxvi natural selection, 451, 462 need to know, 209 objects over ADTs, 490 pay only on use, 620 predictable dependencies, 460 run time is all there is, 504, 690 separation of concerns, 567 stateful component with declara- Index 889 tive behavior, 417 substitution property, 518, 521, 523 syntax stability, 643 system decomposition, 210 type first, 137 use data abstraction everywhere, 489, 543 working software keeps working, 59, 459, 722 private scope, 507, 508 C++ and Java sense, 508 Smalltalk and Oz sense, 507 probability exponential distribution, 475 Gaussian distribution, 476 normal distribution, 476 uniform distribution, 474 unique name generation, 207 problem cryptarithmetic, 755, 776 digital logic satisfiability, 176 Flavius Josephus, 558–561 flight planning, 671 grocery puzzle, 774 halting, 209, 681 Hamming, 293, 342 intractable, 176 library scheduler, 672 making change, 775 n-queens, 629 NP-complete, 176 palindrome product, 628, 757 Send-More-Money, 755, 776 undecidable, 209 zebra puzzle, 774 proc statement, 65, 792 procedure as component, 412 basic operations, 55 external reference, 65 importance, 54 order, 177 tail-recursive, 72 procedure value (closure), 65, 178, 792 anonymous, 53 common limitation, 179, 552 distributed lexical scoping, 722 encoding as an object, 540 higher-order programming, 177 relation to inner class, 552 process concurrent calculus, 54 concurrent program design, 364 CSP, 619 distributed system, 707 Erlang, 350, 386, 389 large program design, 450 operating system, 255 producer and consumer, 724 run-time error, 96 small program design, 218 processor, 237 cluster computing, 711 dataflow machine, 337, 469 parallel functional programming, 331 shared-memory multiprocessor, 710 producer, 257 profiling, 177, 452 program design, see software development program point, 444, 606 programming, xv, 1 accumulator, 139 component-based, 412 concurrent, 573 constraint, 44, 274, 577, 663 data-centered, 576 declarative, 29, 406 descriptive, 115 need for algorithms, 116 programmable, 115 Erlang, 388 flow-based, 257 functional, 406 890 Index future developments, 461 good style, xxi Haskell, 309 higher-order, 113, 123, 177–194 introduction, 13 relation to object-oriented, 538 imperative, 29, 406 Java, 552, 615 kernel language approach, xvi logic, 44, 101, 142, 406, 632 multi-agent, 412, 576 multiparadigm, xiv, xxvi event manager, 566 nonalgorithmic, 622 object-based, 19, 538 object-oriented (OOP), 19, 413, 489 open, 105, 202 paradigm, xiii, xvi, 29, see computation model Prolog, 663 real-time, 304 relational, 621 stateful, 29 stateless, 29 synchronous, 266 programming model, xiii, 29 Prolog, 660–671 Aquarius, 140, 661 Parma, 661 SICStus, 190, 663 state threads package, 190 proof engineering, 117 proof rule, 444 propagate-and-search, 629, 750 propagator, 752, 760 property liveness, 602 object, 497 safety, 602 propositional logic, 632 protected scope, 508 C++ sense, 509 Java sense, 567 protection boundary, 202 protector, 325 protocol, 353 by-need, 282 communication, 715 consistency, 712 DHCP (Dynamic Host Connection Protocol), 207 distributed binding, 733 distributed unification, 733 eager copy, 734 eager immediate copy, 734 interaction (in GUI), 682 invalidation, 733 IP (Internet Protocol), 206 lazy copy, 733 meta-object, 516 mobile state, 733 negotiation, 376 short-circuit, 559 stationary state, 733 TCP (Transmission Control Protocol), 712, 740 timer, 368 Prototyper tool, 689 pseudorandom numbers, 473 Psion Series 3 palmtop computer, 378 public scope, 507 pure object-oriented language, 543 QTk, 213, 680, 729 interactive use, 214, 684 Prototyper, 689 use in application, 225 quadratic equation, 179 quantifier, 441, 445, 633, 645 existential (in Prolog), 671 quantum (in thread scheduling), 252 query database, 655 logic programming, 634 queue, 145 amortized ephemeral, 147 amortized persistent, 298 Index 891 breadth-first traversal, 156 concurrent, 379, 583 nonblocking delete, 598 priority, 605, 614 worst-case ephemeral, 147 worst-case persistent, 299 race condition, 20, 234 raise statement, 93, 801 random number generation, 472 rational tree, 760 Raymond, Eric, 462 reachable memory, 74 ReadOnly operation, 799 real-time computing garbage collection, 76 hard, 174, 253, 254, 304 soft, 304 reasoning algebraic, 111, 116, 323 atomic action, 581 causal, 353, 575 lift control system, 375 logical, xix, 111, 632 message-passing concurrent model, 352 shared-shate concurrent model, 324 stateful model, 324, 440 receive asynchronous, 332 nonblocking, 333 synchronous, 332 receive expression (in Erlang), 391 recomputation, 761, 776 record, 19, 52, 825 adjoin, 827 basic operations, 54, 826 dynamic creation, 165, 549, 695 importance, 53 type, 438 usage trade-offs, 438 recurrence equation, 167 recursion, 3, 113, 124 direct, 113 indirect, 113 mutual, 110 polymorphic, 309 programming with, 127 Prototyper tool, 690 tail recursion optimization, 72 red cut (in Prolog), 670 Red Hat Corporation, xxvi, 201, 471 reduction order, 330–332 applicative, 330 normal, 330 reduction rule, 784 reengineering, 522 refactoring, 452 reference, 714 referential transparency, 113 reflection, 515 region (in OPI), 815 register abstract machine, 56 forwarding, 621 memory management, 74 registration action procedures (in GUI), 683 display refresh (FlexClock), 700 distributed binding, 737 finalization, 481 relation, 655 relative error, 120 reliability, 711 rendezvous, 619 replicator, 326 research project, xxiv resolution deadlock, 605 logic programming, 635, 640, 662 SLDNF, 662 video display, 321 resource distributed component, 746 distributed system, 729 external, 77, 480 file descriptor, 293 892 Index localized, 709 producer/consumer pipeline, 261 use of laziness, 289 responsibility atomicity and consistency (in transaction), 600 compartmentalize (in a team), 451 coroutine (avoiding starvation), 275 design by contract, 521 distributed memory management, 738 dynamic typing, 493 failure confinement, 245 memory management, 76 role of polymorphism, 425 type inference, 137 resting point, 338 restriction (environment), 62 retract/1 operation (in Prolog), 662 return (in for loop), 190 Reuter, Andreas, 582, 600 Reynolds, John C., 419 right, see name Rinard, Martin C., 338 RISC (Reduced Instruction Set Computer) microprocessor, 621 RMI (remote method invocation), 354, 709, 724, 725 root variable, 763 Round operation, 822 RPC (remote procedure call), 354, 709 rubber band, 251 runic inscription, 779 Runnable interface (in Java), 616 s-expression, 650 Sacks, Oliver, 405 safety, 602 Saint-Exupéry, Antoine de, 111 Santayana, George, 694 Saraswat, Vijay A., 338, 662, 808 scalability compilation, 458 multiprocessor, 710 program development, 105 weighted reference counting, 737 scalar product (constraint), 775 scheduler Delay operation, 304 deterministic, 253 lift control system, 366 nondeterministic, 253 randomness, 473 resource allocation, 672 round-robin, 252, 256 thread, 239, 252 transaction, 603 Schulte, Christian, xxvi science, xv, xviii scientific method, xvii scope, 56, 507 attribute, 510 dynamic, 59 lexical, 57, 59, 64, 508, 539 absence in Prolog, 661 distributed, 722 hiding, 221, 411, 423, 442, 483, 495, 549 substitution, 803 private, 507, 508 protected, 508 public, 507 static, see lexical user-defined, 508 search aggregate, 670 all-solutions, 626 binary, 151 branch-and-bound, 772 breadth-first, 644 communication from inside encapsulated search, 673 constraint programming, 274 contribution of AKL, 809 danger, 639 Index 893 database query, 657 depth-first, 622, 644 deterministic, 621 encapsulated, 625 generate-and-test, 629, 758 iterative deepening, 644 linear, 197 logic programming, 661 n-queens problem, 629 one-solution, 626 overuse, xxi propagate-and-search, 629, 750 pruning, 662 relational computation model, 623 relational programming, 621 saturation, 772 search space, 622 search strategy, 761 search tree, 624 security abstract data type, 201–210 application, 744 atom vs. name, 508 capability, 208 data abstraction, 419–435 distributed resources, 731 distributed system, 743 engineering, 744 hardware, 744 human society, 208 implementation, 744 kernel language concepts, 847 language, 208, 744 linguistic abstraction, 39 mechanism, 208 open distribution, 711 policy, 208 right, 791, 847 static typing, 106 threat model, 744 self clone, 517 delegation, 511 dynamic binding, 505 forwarding, 511 Java, 553 this notation, 551 self (in Erlang), 390 semantic stack, 62 runnable, 62 suspended, 62 terminated, 62 semantics, 31 abstract machine, 56–78, 92–94, 239–241, 282–283, 348–349, 416–417 axiomatic, 38, 440–450, 632 by-need trigger, 282 cell, 416 common abstractions, 808 denotational, 38 exceptions, 92 interleaving, 780 kernel language, see abstract machine kernel language approach, 38 logical, 38, 631–641 monitor (in Java), 592 operational, 38, 60, 635, 779–811 port, 348, 383 secure types, 203 semantic statement, 61 SOS (structural operational semantics), 779 thread, 239 Send operation, 349 slot-reserving semantics, 384 send asynchronous, 332 latency, 263 nonblocking, 333 synchronous, 332 Send-More-Money problem, 755, 776 separation of concerns, 567 sequential logic, 269 serializability, 600 serialization, 709 894 Index serializer, 325 set comprehension, 301 setof/3 operation (in Prolog), 626, 666, 670 Shakespeare, William, 815 shared-state concurrency, see atomic action, see lock, see monitor, see transaction sharing, 418 Browser tool, 102, 829 distributed state, 720 distributed value, 716 thread, 378 short-circuit concurrent composition, 277 Flavius Josephus problem, 559 transitive closure, 464 Show operation, 340 side effect, 411 declarative, 288 signal operation (in monitor), 592 signature (of procedure), 129 simulation components, 412 digital logic, 266–272 inadequacy of declarative model, 173 Internet, 412 multi-agent, 412 slow network, 578 small world, 486 word-of-mouth, 476 Simurgh, 707 single-assignment store, 42–49, 60, 781 importance, 43 singularity, 176 sink (consumer), 259 64-bit address, 78 64-bit word, 74, 175, 820 skip statement, 62, 785 SLDNF resolution, 662 small world graph, 461 simulation, 486 Smolka, Gert, xxvi snapshot (of state), 437, 718 software design, see design methodology, see language design software development, 218, 450 bottom-up, 451 compositional, 453 concurrent components, 362 distributed programming, 745 evolutionary, 451 extreme programming, 452 framework, 492 IID (Iterative and Incremental), 451 importance of names, 508 in the large, 450 in the small, 218 incremental, 451 interactive interface, 87 iterative, 451 middle-out, 451 stepwise refinement, 465, 604 test-driven, 452 top-down, 8, 451 software engineering, 450 component as unit of deployment, 221 concurrency, 233 distributed lexical scoping, 722 further reading, 462 informatics curriculum, xxii lexical scoping, 59 software rot, 459 Solaris operating system, xxvi, xxix Solve operation, 626, 773 SolveAll operation, 626 SolveOne operation, 626 Sort operation, 670, 829 SOS (structural operational semantics), 779 source (producer), 259 source code, 221 interactive, 815 Index 895 million line, xvi, 36, 387, 457, 458 nonexistent, 492 preprocessor input, 318 reengineering, 522 set of functors, 285 textual scope, 64 variable name, 44 space, see computation space, see memory space leak, see memory leak specification, 410 component, 461 specification language, 116 speculative execution (in nonstrict language), 331 stack declarative object, 423 depth-first traversal, 156 memory management, 74 open declarative, 195, 421 proving it correct, 442 secure declarative bundled, 423 secure declarative unbundled, 205, 422 secure stateful bundled, 424 secure stateful unbundled, 424 semantic, 61 stateful concurrent, 578 standalone application, 222 declare not allowed, 87 Java, 555 uncaught exception, 93 starvation, 275 wait set implementation, 597 state cell (mutable variable), 414 declarative, 408 explicit, 16, 409 implicit, 408 interaction with call by name, 485 lazy execution, 481 lazy language, 331 memory management, 77 modularity property, 315 nonstrict language, 331 port (communication channel), 347 reasoning with, 38, 440 revocable capability, 434 threading, 139 transformation, 133 state transition diagram, 353, 368 component design, 364 floor component, 369 lift component, 371 lift controller component, 369 transaction, 607 stateless (declarative programming), 111 statement case, 67, 790 catch (clause in try), 94 choice, 623, 772 conc, 278 declare, 2, 87 fail, 623 finally (clause in try), 94 for, 188 fun, 84 functor, 223 gate, 272 if, 66, 790 local, 56, 63, 786 lock, 22, 583 proc, 65, 792 raise, 93, 801 skip, 62, 785 thread, 241, 785 try, 92, 799 break, 486 compound, 117 compound (in Java), 552 declarative kernel language, 49 interactive, 87 procedure application, 66 sequential composition, 63, 785 suspendable, 65 896 Index value creation, 63 variable-variable binding, 63 static binding, 506 linking, 222 scope, see scope, lexical typing, 51, 104–106 stdin (standard input), 229, 553 stdout (standard output), 553 Steiner, Jennifer G., 334 Stirling’s formula for factorial, 618 storage manager, 325 store, 781 equivalence, 785 mutable (for cells), 416 mutable (for ports), 348 need, 780, 795 predicate, 781 read-only, 206, 798 single-assignment, 42–49, 60, 99, 235, 781 trigger, 282, 795 value, 43 stream, 795 deterministic, 257 Java, 553 merger, 395 producer/consumer, 257 usage trade-offs, 439 strict . . . , see eager . . . strict two-phase locking, 604 strictness analysis, 289, 310, 342 string, 53, 830 virtual, 211, 831 StringToAtom operation, 824 structure compiler, 162 compositional, 461 difference, 141 distribution, 255 effect of concurrency, 252 grammar, 32 hierarchical, 453 interpreter, 653 noncompositional, 461 program, 219, 220 structure equality, 103, 418, 723 substitution, 126, 803 substitution property, 518, 521, 523 subtype basic types, 52 class hierarchy, 518 Sun Microsystems, xxvi, 462 superclass, 503, 513, 556 supercomputer, 175 supply-driven execution, see eager execution suspension Delay operation, 305 due to program error, 48, 89 thread, 239, 276 Sussman, Gerald Jay, 42 Sussman, Julie, 42 Symbian Ltd., 378 symbolic link, 459 synchronization, 333–337 clock, 308 dataflow, 790 synchronized keyword, 593, 616 synchronous communication, 332 active object variant, 562 component interaction, 456 CSP, 619 dependency, 387 error reporting, 360 failure detection, 400, 739 fault confinement, 745 receive, 332 send, 332 synchronous programming, 266 syntactic sugar, 40, 79–84 dynamic record creation, 165 local statement, 40 state transition diagram, 369 syntax, 31 convention for examples, xxix language, 31 nestable constructs (in Oz), 833 Index 897 nestable declarations (in Oz), 833 Oz language, 833 Oz lexical, 839 Prolog, 663 term (in Oz), 833 synthesized argument, 161 system exception, 96 Szyperski, Clemens, 462 tail call optimization, 72 Tanenbaum, Andrew S., 334 task (in concurrency), 780 tautology, 632 TCP (Transmission Control Protocol), 712, 740 technology, xv dangers of concurrency, 21 history of computing, 176 magic, 314 molecular computing, 176 Prolog implementation, 661 reengineering, 522 singularity, 176 software component, 462 synchronous digital, 267 transition to 64-bit, 78 Tel, Gerard, 353 tell operation, 782, 787 temporal logic, 603 temporary failure, 739 term Erlang, 391 Oz, 833 Prolog, 664 termination detection, 276, 382 ping-pong example, 305 failure in declarative program, 245 partial, 243, 338, 804 proof, 449 total, 804 test-driven development, 452 testing declarative programs, 111, 407 dynamic typing, 105 programming in the small, 219 stateful programs, 407 text file, 210 Thalys high-speed train, 382 theorem binomial, 4 Church-Rosser, 331 Gödel’s completeness, 634 Gödel’s incompleteness, 634 halting problem, 681 theorem prover, 117, 634, 662 Therac-25 scandal, 21 thinking machine, 621 third-party independence, 335 32-bit address, 78 32-bit word, 74, 174 this, see self Thompson, D’Arcy Wentworth, 405 thread, 846 declarative model, 233 hanging, 399 interactive interface, 89 introduction, 15 Java, 615 monotonicity property, 239, 781, 782 priority, 253 ready, 239 runnable, 239 suspended, 239 synchronization, 333 thread statement, 241, 785 Thread class (in Java), 616 throughput, 263 thunk, 432 ticket, 480, 714 Connection module, 715 ticking, 307 time complexity, 11 time slice, 252–254 duration, 254 898 Index time-lease mechanism, 480, 734, 738 time-out, 740 Erlang, 391–394 system design, 460 timer protocol, 368 timestamp, 207, 602 timing measurement active object, 379 memory consumption, 173 palindrome product (constraint version), 758 palindrome product (naive version), 629 transitive closure, 471 word frequency, 201 token equality, 418, 714, 723 token passing, 579, 588, 591, 721 token syntax (of Oz), 833 tokenizer, 32, 162 top-down software development, 8, 451 total termination, 804 trade-off asynchronous communication vs. fault confinement, 745 compilation time vs. execution efficiency, 457 compositional vs. noncompositional design, 461 dynamic vs. static scoping, 58 dynamic vs. static typing, 104 explicit state vs. implicit state, 315, 409 expressiveness vs. execution efficiency, 116 expressiveness vs. manipulability, 681 functional decomposition vs. type decomposition, 542 helper procedure placement, 120 indexed collections, 435 inheritance vs. component composition, 462, 492 kernel language design, 844 language design, 811 lazy vs. eager execution, 329 memory use vs. execution speed, 177 names vs. atoms, 510 nonstrictness vs. explicit state, 331, 344 objects vs.

Monadic Design Patterns for the Web by L.G. Meredith

barriers to entry, domain-specific language, don't repeat yourself, finite state, functional programming, Georg Cantor, ghettoisation, higher-order functions, John von Neumann, Kickstarter, semantic web, seminal paper, social graph, type inference, web application, WebSocket

A subtype should correctly implement the contracts of its supertypes, so that the Liskov Substitution Principle applies, but the compiler only verifies this property at the level of type checking. superclass A class’s superclasses include its direct superclass, its direct superclass’s direct superclass, and so on, all the way up to Any. supertrait A class’s or trait’s supertraits, if any, include all traits directly mixed into the class or trait or any of its superclasses, plus any supertraits of those traits. supertype A type is a supertype of all of its subtypes. synthetic class A synthetic class is generated automatically by the compiler rather than being written by hand by the programmer. Download from Wow! eBook <www.wowebook.com> tail recursive A function is tail recursive if the only place the function calls itself is the last operation of the function. target typing Target typing is a form of type inference that takes into account the type that’s expected. In nums.filter((x) => x > 0), for example, the Scala compiler infers type of x to be the element type of nums, because the filter method invokes the function on each element of nums. template A template is the body of a class, trait, or singleton object definition.

Masterminds of Programming: Conversations With the Creators of Major Programming Languages by Federico Biancuzzi, Shane Warden

Benevolent Dictator For Life (BDFL), business intelligence, business logic, business process, cellular automata, cloud computing, cognitive load, commoditize, complexity theory, conceptual framework, continuous integration, data acquisition, Dennis Ritchie, domain-specific language, Douglas Hofstadter, Fellow of the Royal Society, finite state, Firefox, follow your passion, Frank Gehry, functional programming, general-purpose programming language, Guido van Rossum, higher-order functions, history of Unix, HyperCard, industrial research laboratory, information retrieval, information security, iterative process, Ivan Sutherland, John von Neumann, Ken Thompson, Larry Ellison, Larry Wall, linear programming, loose coupling, machine readable, machine translation, Mars Rover, millennium bug, Multics, NP-complete, Paul Graham, performance metric, Perl 6, QWERTY keyboard, RAND corporation, randomized controlled trial, Renaissance Technologies, Ruby on Rails, Sapir-Whorf hypothesis, seminal paper, Silicon Valley, slashdot, software as a service, software patent, sorting algorithm, SQL injection, Steve Jobs, traveling salesman, Turing complete, type inference, Valgrind, Von Neumann architecture, web application

If you break down the work we did with LINQ, it’s actually about six or seven language features like extension methods and lambdas and type inference and so forth. You can then put them together and create a new kind of API. In particular, you can create these query engines implemented as APIs if you will, but the language features themselves are quite useful for all sorts of other things. People are using extension methods for all sorts of other interesting stuff. Local variable type inference is a very nice feature to have, and so forth. We could’ve probably shipped something like LINQ much quicker if we said, “Let’s just jam SQL in there or something that is totally SQL Server-specific, and we’ll just talk to a database and then we’ll have it,” but it’s not general enough to merit existence in a general-purpose programming language.

…

ML ML is a general-purpose functional language developed by Robin Milner and the team he led at the University of Edinburgh in the 1970s. It grew from a metalanguage project designed to describe mathematical proofs. ML’s most valuable contribution to language design may be the Hindley-Milner type inference algorithm used in many static, latent type systems. The language inspired Standard ML, Caml, Haskell, and F#, among others. The Soundness of Theorems You created LCF, one of the first tools for automated theorem proving, and the programming language ML to run the proving. How did it work?

The Productive Programmer by Neal Ford

anti-pattern, business process, c2.com, continuous integration, database schema, domain-specific language, don't repeat yourself, Firefox, general-purpose programming language, knowledge worker, Larry Wall, Paradox of Choice, Ruby on Rails, side project, type inference, web application, William of Occam

Expressive DSLs on top of powerful languages will become the new standard. Frameworks will be written using DSLs, not on top of statically typed languages with restrictive syntax and unnecessary ceremony. Note that this isn’t necessarily a dynamic language or even a Ruby tirade: a strong potential exists for statically typed type-inference languages that have a suitable syntax to also take advantage of this style of programming. For an example of this, check out Jaskell* and, in particular, the build DSL written on top of it called Neptune.† Neptune performs the same basic tasks as Ant, but it is written as a domain-specific language atop Jaskell.

Programming Clojure by Stuart Halloway, Aaron Bedra

continuous integration, duck typing, en.wikipedia.org, functional programming, general-purpose programming language, Gödel, Escher, Bach, higher-order functions, Neal Stephenson, Paul Graham, Ruby on Rails, type inference, web application

Using dotimes, you can collect five timings of sum-to as follows: ​(dotimes [_ 5] (time (sum-to 10000)))​ ​| "Elapsed time: 0.149 msecs"​ ​| "Elapsed time: 0.126 msecs"​ ​| "Elapsed time: 0.194 msecs"​ ​| "Elapsed time: 0.279 msecs"​ ​-> "Elapsed time: 0.212 msecs"​ To speed things up, you can hint the argument and return type as long. Clojure’s type inference will flow this hint to all the internal operations and function calls inside the function. ​(defn ^long integer-sum-to [^long n]​ ​ (loop [i 1 sum 0]​ ​ (if (< = i n)​ ​ (recur (inc i) (+ i sum))​ ​ sum)))​ The integer-sum-to is indeed faster: ​(dotimes [_ 5] (time (integer-sum-to 10000)))​ ​| "Elapsed time: 0.044 msecs"​ ​| "Elapsed time: 0.023 msecs"​ ​| "Elapsed time: 0.025 msecs"​ ​| "Elapsed time: 0.023 msecs"​ ​-> "Elapsed time: 0.02 msecs"​ Clojure’s primitive math is still correct, in that it will check for overflow and throw an exception.

More Joel on Software by Joel Spolsky

a long time ago in a galaxy far, far away, AOL-Time Warner, barriers to entry, Black Swan, Build a better mousetrap, business process, call centre, Danny Hillis, David Heinemeier Hansson, Dennis Ritchie, failed state, Firefox, fixed income, functional programming, George Gilder, Larry Ellison, Larry Wall, lolcat, low cost airline, Mars Rover, Network effects, Paradox of Choice, Paul Graham, performance metric, place-making, price discrimination, prisoner's dilemma, Ray Oldenburg, Ruby on Rails, Salesforce, Sand Hill Road, Silicon Valley, slashdot, social software, Steve Ballmer, Steve Jobs, Superbowl ad, The Great Good Place, The Soul of a New Machine, Tragedy of the Commons, type inference, unpaid internship, wage slave, web application, Y Combinator

And while everyone else their age was running around playing soccer (this is a game many kids who can’t program computers play that involves kicking a spherical object called a ball with their feet—I know, it sounds weird), they were in their dad’s home office trying to get the Linux kernel to compile. Instead of chasing girls in the playground, they were getting into flamewars on Usenet about the utter depravity of programming languages that don’t implement Haskell-style type inference. Instead of starting a band in their garage, they were implementing a cool hack so that when their neighbor stole bandwidth over their open-access Wi-Fi point, all the images on the Web appeared upside-down. BWA HA HA HA HA! So, unlike, say, the fields of law or medicine, over here in software development, by the time these kids are in their second or third year in college they are pretty darn good programmers.

Learn Algorithmic Trading by Sebastien Donadio

active measures, algorithmic trading, automated trading system, backtesting, Bayesian statistics, behavioural economics, buy and hold, buy low sell high, cryptocurrency, data science, deep learning, DevOps, en.wikipedia.org, fixed income, Flash crash, Guido van Rossum, latency arbitrage, locking in a profit, market fundamentalism, market microstructure, martingale, natural language processing, OpenAI, p-value, paper trading, performance metric, prediction markets, proprietary trading, quantitative trading / quantitative finance, random walk, risk tolerance, risk-adjusted returns, Sharpe ratio, short selling, sorting algorithm, statistical arbitrage, statistical model, stochastic process, survivorship bias, transaction costs, type inference, WebSocket, zero-sum game

Finally, we explain practical issues faced in setting up and calibrating a backtester, their impact on an algorithmic trading strategy, and what approaches best minimize damage caused due to inaccurate backtesting. Why Python? Python is the most widely used programming language in the world (one-third of new software development uses this language): This language is very simple to learn. Python is an interpreted, high-level programming language with type inference. Unlike C/C++, where you need to focus on memory management and the hardware features of the machine you are using to code, Python takes care of the internal implementation, such as memory management. As a result, this type of language will ease the focus on coding trading algorithms. Python is versatile; it can be used in any domain for any application development.

Beautiful Architecture: Leading Thinkers Reveal the Hidden Beauty in Software Design by Diomidis Spinellis, Georgios Gousios

Albert Einstein, barriers to entry, business intelligence, business logic, business process, call centre, continuous integration, corporate governance, database schema, Debian, domain-specific language, don't repeat yourself, Donald Knuth, duck typing, en.wikipedia.org, fail fast, fault tolerance, financial engineering, Firefox, Free Software Foundation, functional programming, general-purpose programming language, higher-order functions, iterative process, linked data, locality of reference, loose coupling, meta-analysis, MVC pattern, Neal Stephenson, no silver bullet, peer-to-peer, premature optimization, recommendation engine, Richard Stallman, Ruby on Rails, semantic web, smart cities, social graph, social web, SPARQL, Steve Jobs, Stewart Brand, Strategic Defense Initiative, systems thinking, the Cathedral and the Bazaar, traveling salesman, Turing complete, type inference, web application, zero-coupon bond

Several qualifications limit this advantage: In considering design issues, as in the present discussion, the notational issue is less critical. One could, for example, use a functional approach for design and then target an imperative language. Many modern functional languages such as Haskell and OCaml are strongly typed, implying the notation will be a little more verbose; for example, unless the designer wants to rely on type inference (not a good idea at the design stage), within needs the type declaration Double → [Double] → Double. Not everyone may be comfortable with the common practice of replacing multiargument functions by functions returning functions (known in the medical literature as RCS, for “Rabid Currying Syndrome,” and illustrated by such signatures as (a → b → c) → Obs a → Obs b → Obs c in the financial article).