DOCSEARCHbyAlgolia
Submit Docs

Standard ML (SML) Documentation

website·Indexed 29 days ago

https://smlhelp.github.io/book/

A comprehensive guide to Standard ML, covering core concepts such as functional programming basics, type safety, and higher-order functions. The documentation includes detailed sections on recursion, induction, lazy evaluation, and the SML/NJ Basis library, as well as technical guides on module systems, functors, and continuation passing style (CPS). It also provides syntax cheatsheets, installation instructions for SML/NJ, and debugging strategies for common errors.

Tokens
30.6K
Snippets
171
Records
228
Agent score
75%

What's inside SML

  1. Overview of Standard ML (SML) Programming Paradigm

    Standard ML (SML) is a functional programming language. Its core philosophy is to avoid side effects and state changes, treating computation as a process of simplification or reduction. This approach allows programs to be reasoned about similarly to mathematical expressions, where computation is viewed as a series of expression evaluations.

  2. Understand SML List types and properties

    Lists in SML are ordered collections of objects of a fixed type (e.g., int list, string list). Unlike arrays, lists do not provide constant-time access to indices; they are persistent (immutable) and accessed primarily via the head (the first element). The list keyword is a type constructor and cannot be used as a standalone type.

  3. Understand the difference between iterative and recursive thinking

    Iterative solutions (common in imperative languages like Python or C) rely on initializing data cells and performing a sequence of mutations (e.g., using a while loop to increment a counter and update a result variable).

    Recursive solutions (essential for functional programming) are used because pure functional languages utilize immutable data. Instead of mutating a variable, a recursive function solves a problem by breaking it down into a base case and a recursive step that operates on a smaller version of the original problem.

  4. Understand SML Strong Typing and Type Safety

    Standard ML (SML) employs a system of strong typing where every expression and function has a specified type. Unlike weakly typed languages that verify types at runtime, SML enforces typing rules at compile-time. This ensures that data types are not haphazardly intermingled (e.g., preventing the addition of a string to an integer), allowing the compiler to catch type errors before the program ever executes. A program is considered 'well-typed' if it passes this compile-time type-checking process.

  5. Use the SML int type for integers

    int is the SML type for whole numbers. In SML, integers are treated as unbounded for mathematical purposes. Every integer acts as its own constant constructor, meaning they can be used directly in pattern matching. The ~ symbol is used to denote negative numbers (e.g., ~1) and also serves as a unary negation function of type int -> int.

  6. Understand SML Type Inference

    SML uses type inference to automatically determine the types of expressions and functions when they are not explicitly provided. The compiler assigns the 'most general type' (the most flexible polymorphic type possible) and then narrows it down based on contextual clues. For example, if a variable is used with the + operator, the compiler infers it must be an int because the operator requires integer inputs to type-check.

  7. Distinguish between parametric and ad hoc polymorphism in SML

    SML employs two different styles of polymorphism:

    1. Parametric Polymorphism: A single, general implementation that works identically for any type (e.g., length for lists). It uses type variables like 'a.
    2. Ad Hoc Polymorphism (Overloading): Multiple different implementations of the same operator for different types. For example, the + operator has different implementations for int and real. The specific implementation is chosen based on the context/type.

  8. Relate mathematical induction to SML recursion

    There is a strong association between mathematical induction and recursion in SML. When proving the correctness of a recursive function, the components of the proof map directly to the structure of the code:

    1. Base Case: Parallels the non-recursive case (the termination condition) of the function.
    2. Inductive Step/Case: Parallels the recursive case of the function.
    3. Inductive Hypothesis: Parallels the recursive call itself. It is the assumption that the function works correctly for a smaller input, which is then used to prove the current step is correct.

  9. Understand the SML real type and its limitations

    real is the SML type for floating-point numbers. Because they use finite machine representations, they cannot represent every real number with perfect precision. Crucially, real is not an equality type: it cannot be compared using the = operator and cannot be used in pattern matching.

  10. Use the Fn module for basic combinators

    The Fn module in the SML/NJ Basis library provides basic combinators and fundamental lambda calculus operations. This includes the composition operator o, which is also available at the top-level scope.

  11. Deconstruct lazy lists using head and tail

    To reason about infinite lazy lists via coinduction, use deconstructors (co-constructors) that observe the current state and transition to the next state.
    fun head (Nil : 'a lazylist) : 'a = raise Fail "Unimplemented"
  | head (Cons (x, _)) = x

fun tail (Nil : 'a lazylist) : 'a lazylist = raise Fail "Unimplemented"
  | tail (Cons (_, xs)) = xs ()

  12. Understand Extensional Equivalence in SML

    Two expressions are extensionally equivalent (denoted as ≅) if they yield congruent results for all possible inputs. This definition focuses on the output values rather than the internal implementation, complexity, or the path taken to reach the result. For example, fn x => x + x and fn x => 2 * x are different literal values (the first is a value in its terminal form and does not simplify to the second), but they are extensionally equivalent because they produce the same integer output for any given input.