ISWIM

Last updated
ISWIM
Paradigm Imperative, functional
Designed by Peter Landin
First appeared1966;58 years ago (1966)
Influenced by
ALGOL 60, Lisp
Influenced
SASL, Miranda, ML, Haskell, Clean, Lucid

ISWIM (If You See What I Mean) is an abstract computer programming language (or a family of languages) devised by Peter Landin and first described in his article "The Next 700 Programming Languages", published in the Communications of the ACM in 1966. [1]

Contents

Although not implemented, it has proved very influential in the development of programming languages, especially functional programming languages such as SASL, Miranda, ML, Haskell and their successors, and dataflow programming languages like Lucid.

Design

ISWIM is an imperative programming language with a functional core, consisting of a syntactic sugaring of lambda calculus to which are added mutable variables and assignment and a powerful control mechanism: the program point operator. Being based on lambda calculus, ISWIM has higher-order functions and lexically scoped variables.

The operational semantics of ISWIM are defined using Landin's SECD machine and use call-by-value, that is eager evaluation. [2] A goal of ISWIM was to look more like mathematical notation, so Landin abandoned ALGOL's semicolons between statements and begin ... end blocks and replaced them with the off-side rule and scoping based on indentation.

A notationally distinctive feature of ISWIM is its use of where clauses. An ISWIM program is a single expression qualified by where clauses (auxiliary definitions including equations among variables), conditional expressions and function definitions. Along with CPL, ISWIM was one of the first programming languages to use where clauses.

A notable semantic feature was the ability to define new data types, as a (possibly recursive) sum of products. This was done using a somewhat verbose natural language style description, but apart from notation amounts exactly to the algebraic data types found in modern functional languages. [3] ISWIM variables did not have explicit type declarations and it seems likely (although not explicitly stated in the 1966 paper) that Landin intended the language to be dynamically typed, like LISP and unlike ALGOL; but it is also possible that he intended to develop some form of type inference.

Implementations and derivatives

No direct implementation of ISWIM was attempted but Art Evan's language PAL , [4] and John C. Reynolds' language Gedanken, [5] captured most of Landin's concepts, including powerful transfer-of-control operations. Both of these were typed dynamically. Robin Milner's ML may be considered equivalent to ISWIM without the J operator and with type inference.

Another line of descent from ISWIM is to strip out the imperative features (assignment and the J operator) leaving a purely functional language. [6] It then becomes possible to switch to lazy evaluation. This path led to programming languages SASL, Kent Recursive Calculator (KRC), Hope, Miranda, Haskell, and Clean.

Related Research Articles

In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program.

Lambda calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics.

ML is a functional programming language. It is known for its use of the polymorphic Hindley–Milner type system, which automatically assigns the data types of most expressions without requiring explicit type annotations, and ensures type safety; there is a formal proof that a well-typed ML program does not cause runtime type errors. ML provides pattern matching for function arguments, garbage collection, imperative programming, call-by-value and currying. While a general-purpose programming language, ML is used heavily in programming language research and is one of the few languages to be completely specified and verified using formal semantics. Its types and pattern matching make it well-suited and commonly used to operate on other formal languages, such as in compiler writing, automated theorem proving, and formal verification.

In computer science, syntactic sugar is syntax within a programming language that is designed to make things easier to read or to express. It makes the language "sweeter" for human use: things can be expressed more clearly, more concisely, or in an alternative style that some may prefer. Syntactic sugar is usually a shorthand for a common operation that could also be expressed in an alternate, more verbose, form: The programmer has a choice of whether to use the shorter form or the longer form, but will usually use the shorter form since it is shorter and easier to type and read.

In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.

In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be a match." The patterns generally have the form of either sequences or tree structures. Uses of pattern matching include outputting the locations of a pattern within a token sequence, to output some component of the matched pattern, and to substitute the matching pattern with some other token sequence.

Curry is a declarative programming language, an implementation of the functional logic programming paradigm, and based on the Haskell language. It merges elements of functional and logic programming, including constraint programming integration.

In type theory, a typing rule is an inference rule that describes how a type system assigns a type to a syntactic construction. These rules may be applied by the type system to determine if a program is well-typed and what type expressions have. A prototypical example of the use of typing rules is in defining type inference in the simply typed lambda calculus, which is the internal language of Cartesian closed categories.

<span class="mw-page-title-main">Peter Landin</span> British computer scientist (1930–2009)

Peter John Landin was a British computer scientist. He was one of the first to realise that the lambda calculus could be used to model a programming language, an insight that is essential to the development of both functional programming and denotational semantics.

In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures. Some programming language theorists require support for anonymous functions as well. In languages with first-class functions, the names of functions do not have any special status; they are treated like ordinary variables with a function type. The term was coined by Christopher Strachey in the context of "functions as first-class citizens" in the mid-1960s.

<span class="mw-page-title-main">Programming language theory</span> Branch of computer science

Programming language theory (PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of formal languages known as programming languages. Programming language theory is closely related to other fields including mathematics, software engineering, and linguistics. There are a number of academic conferences and journals in the area.

In computing, a meta-circular evaluator (MCE) or meta-circular interpreter (MCI) is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambda application may be implemented using function application. Meta-circular evaluation is most prominent in the context of Lisp. A self-interpreter is a meta-circular interpreter where the interpreted language is nearly identical to the host language; the two terms are often used synonymously.

In functional programming, a generalized algebraic data type is a generalization of parametric algebraic data types.

In the area of mathematical logic and computer science known as type theory, a type constructor is a feature of a typed formal language that builds new types from old ones. Basic types are considered to be built using nullary type constructors. Some type constructors take another type as an argument, e.g., the constructors for product types, function types, power types and list types. New types can be defined by recursively composing type constructors.

In computer science, polymorphic recursion refers to a recursive parametrically polymorphic function where the type parameter changes with each recursive invocation made, instead of staying constant. Type inference for polymorphic recursion is equivalent to semi-unification and therefore undecidable and requires the use of a semi-algorithm or programmer-supplied type annotations.

This article describes the features in the programming language Haskell.

A Hindley–Milner (HM) type system is a classical type system for the lambda calculus with parametric polymorphism. It is also known as Damas–Milner or Damas–Hindley–Milner. It was first described by J. Roger Hindley and later rediscovered by Robin Milner. Luis Damas contributed a close formal analysis and proof of the method in his PhD thesis.

A CEK Machine is an abstract machine invented by Matthias Felleisen and Daniel P. Friedman that implements left-to-right call by value. It is generally implemented as an interpreter for functional programming languages, but can also be used to implement simple imperative programming languages. A state in a CEK machine includes a control statement, environment and continuation. The control statement is the term being evaluated at that moment, the environment is (usually) a map from variable names to values, and the continuation stores another state, or a special halt case. It is a simplified form of another abstract machine called the SECD machine.

References

  1. Landin, P. J. (March 1966). "The Next 700 Programming Languages" (PDF). Communications of the ACM. Association for Computing Machinery. 9 (3): 157–165. doi:10.1145/365230.365257. S2CID   13409665.
  2. Plotkin, Gordon (1975). Call-by-Name, Call-by Value and the Lambda Calculus (PDF) (Report).
  3. Turner, D. A. (2013), "Some History of Functional Programming Languages", Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 1–20, ISBN   978-3-642-40446-7 , retrieved 2024-01-28, The ISWIM paper also has the first appearance of algebraic type definitions used to define structures. This is done in words, but the sum-of-products idea is clearly there
  4. Evans, Art (1968). "PAL: a language designed for teaching programming linguistics". Proceedings ACM National Conference. ACM National Conference. Association for Computing Machinery.
  5. Reynolds, John C. (September 1969). GEDANKEN: a simple typeless language which permits functional data structures and co-routines (Report). Argonne National Laboratory.
  6. Ivanović, Mirjana; Budimac, Zoran (April 1993). "A definition of an ISWIM-like language via Scheme". ACM SIGPLAN Notices. 28 (4): 29–38. doi: 10.1145/152739.152743 . S2CID   14379260.