Class Expr`Abstract`

A combinatory logic expression.

Applications, variables, lambdas, combinators per se, and other expression subtypes all extend this class.

Expr itself cannot (or at least should not) be instantiated.

Hierarchy (View Summary)

Expr

Index

Constructors

constructor

Properties

arity? context? note? props? size?

Constructors

constructor

new Expr(): Expr
Returns Expr

Properties

`Optional`arity

arity?: number

number of arguments the term is waiting for (if known)

`Optional`context

context?: {
    env?: Record<string, Expr>;
    parser: object;
    scope?: object;
    src?: string;
}

optional context for the term. Is set by the parser with addContext: true

`Optional`note

note?: string

a brief description what the term does

`Optional`props

props?: TermInfo

the properties of the term, typically inferred from its behavior. This is used internally when declaring Native / Alias terms.

`Optional`size

size?: number

An estimated number of nodes in the expression tree. Used to prevent runaway computations.

Methods

`Protected`_braced

_braced(isFirst?: boolean): boolean
Protected
Whether the expression needs to be parenthesized when printed in terse mode. (see format)
Parameters
- OptionalisFirst: boolean
  whether this is the first term in a sequence
Returns boolean
- Defined in expr.ts:773

`Protected`_fold

_fold<T>(
initial: T,
combine: (acc: T, expr: Expr) => TraverseValue<T>,
): TraverseValue<T>
Protected
Internal method for fold(), which performs the actual folding. Should be implemented in subclasses having any internal structure.
Type Parameters
- T
Parameters
- initial: T
- combine: (acc: T, expr: Expr) => TraverseValue<T>
Returns TraverseValue<T>
- Defined in expr.ts:309

`Protected`_traverse_descend

_traverse_descend(
options: TraverseOptions,
change: TraverseCallback,
): TraverseValue<Expr>
Protected
Apply a traverse callback to the subterms of the expression, without changing the expression itself.
Parameters
- options: TraverseOptions
- change: TraverseCallback
Returns TraverseValue<Expr>
- Defined in expr.ts:259

`Protected`_traverse_redo

_traverse_redo(
options: TraverseOptions,
change: TraverseCallback,
): TraverseValue<Expr>
Protected
Parameters
- options: TraverseOptions
- change: TraverseCallback
Returns TraverseValue<Expr>
- Defined in expr.ts:234

`Protected`_unspaced

_unspaced(arg: Expr): boolean
Protected
Whether the expression can be printed without a space when followed by arg.
Parameters
- arg: Expr
Returns boolean
- Defined in expr.ts:783

annotate

annotate(
    options?: {
        arity?: number;
        canonize?: boolean;
        fancy?: string;
        max?: number;
        maxArgs?: number;
        note?: string;
    },
): Expr
Experimental
Add metadata based on user-supplied values and/or the properties of the term itself.

Typically applied to named terms shortly after instantiation.

Experimental. Name and meaning may change in the future.
Parameters
- options: {
      arity?: number;
      canonize?: boolean;
      fancy?: string;
      max?: number;
      maxArgs?: number;
      note?: string;
  } = {}
  - Optionalarity?: number
    number of arguments the term is waiting for (if known)
  - Optionalcanonize?: boolean
    whether to try to infer the properties
  - Optionalfancy?: string
    how to display in html mode, e.g. φ instead of 'f'
  - Optionalmax?: number
    maximum number of steps for inference, if canonize is true
  - OptionalmaxArgs?: number
    maximum number of arguments for inference, if canonize is true
  - Optionalnote?: string
    a brief description what the term does
Returns Expr
- Defined in expr.ts:134

any

any(predicate: (e: Expr) => boolean): boolean
Returns true if predicate() is true for any subterm of the expression, false otherwise.
Parameters
- predicate: (e: Expr) => boolean
Returns boolean
- Defined in expr.ts:269

apply

apply(...args: Expr[]): Expr
apply self to zero or more terms and return the resulting term, without performing any calculations whatsoever
Parameters
- ...args: Expr[]
Returns Expr
- Defined in expr.ts:164

declare

declare(
options?: FormatOptions & { declaration?: [string, string, string] },
): string
Parameters
- options: FormatOptions & { declaration?: [string, string, string] } = {}
Returns string
- Defined in expr.ts:888

diag

diag(indent?: string): string

Returns a string representation of the expression tree, with indentation to show structure.

  Applications are flattened to avoid excessive nesting.
  Variables include ids to distinguish different instances of the same variable name.

  May be useful for debugging.

Parameters

indent: string = ''

Returns string

Example

> console.log(ski.parse('C 5 x (x->x x)').diag())
App:
  Native: C
  Church: 5
  FreeVar: x[53]
  Lambda (x[54]):
    App:
      FreeVar: x[54]
      FreeVar: x[54]

diff

diff(other: Expr, swap?: boolean): string | null

Recursively compare two expressions and return a string describing the first point of difference. Returns null if expressions are identical.

  Aliases are expanded.
  Bound variables in lambda terms are renamed consistently.
  However, no reductions are attempted.

  Members of the FreeVar class are considered different
  even if they have the same name, unless they are the same object.
  To somewhat alleviate confusion, the output will include
  the internal id of the variable in square brackets.

  Do not rely on the exact format of the output as it may change in the future.

Parameters

other: Expr
Optionalswap: boolean = false
If true, the order of expressions is reversed in the output.

Returns string | null

Example

"K(S != I)" is the result of comparing "KS" and "KI"

Example

"S(K([x[13] != x[14]]))K"

equals

equals(other: Expr): boolean
True is the expressions are identical, false otherwise. Aliases are expanded. Bound variables in lambda terms are renamed consistently. However, no reductions are attempted.
```
  E.g. a->b->a == x->y->x is true, but a->b->a == K is false.
```
Parameters
- other: Expr
Returns boolean
Remarks
Final. Current implementation is a frontend to diff.
- Defined in expr.ts:685

expand

expand(): Expr
Replace all aliases in the expression with their definitions, recursively.

Returns Expr
- Defined in expr.ts:176

expect

expect(actual: object | Expr, comment?: string): void
Sealed
Assert expression equality. Can be used in tests.

this is the expected value and the argument is the actual one. Mnemonic: the expected value is always a combinator, the actual one may be anything.

In case of failure, an error is thrown with a message describing the first point of difference and expected and actual properties like in AssertionError. AssertionError is not used directly because browsers don't recognize it.
Parameters
- actual: object | Expr
- comment: string = ''
Returns void
- Defined in expr.ts:736

fold

fold<T>(initial: T, combine: (acc: T, expr: Expr) => TraverseValue<T>): T
Experimental
Fold the expression into a single value by recursively applying combine() to its subterms. Nodes are traversed in leftmost-outermost order, i.e. the same order as reduction steps are taken.

null or undefined return value from combine() means "keep current value and descend further".

SKI.control provides primitives to control the folding flow:
- SKI.control.prune(value) means "use value and don't descend further into this branch";
- SKI.control.stop(value) means "stop folding immediately and return value".
- SKI.control.descend(value) is the default behavior, meaning "use value and descend further".
This method is experimental and may change in the future.
Type Parameters
- T
Parameters
- initial: T
- combine: (acc: T, expr: Expr) => TraverseValue<T>
Returns T
Example
```
// count the number of nodes in the expression tree
expr.fold(0, (acc, e) => acc + 1);

@experimental
```
- Defined in expr.ts:296

foldBottomUp

foldBottomUp<T>(fun: (head: Expr, tail: T[]) => T): T

Experimental

Fold an application tree bottom to top. For each subtree, the function is given the term in the root position and a list of the results of folding its arguments.

   E.g. fold('x y (z t)', f) results in f(x, [f(y, []), f(z, [f(t, [])])])

Type Parameters

Parameters

fun: (head: Expr, tail: T[]) => T

Returns T

Example

expr.foldBottomUp((head, tail) => {
   if (head.arity && head.arity <= tail.length) {
     return '(<span class="redex">'
         + head + ' '
         + tail.slice(0, head.arity).join(' ')
         + '</span>'
         + tail.slice(head.arity).join(' ')
         + ')';
   } else {
      return '(' + head + ' ' + tail.join(' ') + ')';
   }
});

format

format(options?: FormatOptions): string
Sealed
Stringify the expression with fancy formatting options. Said options mostly include wrappers around various constructs in form of ['(', ')'], as well as terse and html flags that fill in appropriate defaults. Format without options is equivalent to toString() and can be parsed back.
Parameters
- Optionaloptions: FormatOptions = {}
  formatting options
  - Optionalaround?: [string, string]
  - Optionalbrackets?: [string, string]
  - Optionalhtml?: boolean
  - Optionalinventory?: Record<string, Named>
  - Optionallambda?: [string, string, string]
  - Optionalredex?: [string, string]
  - Optionalspace?: string
  - Optionalterse?: boolean
  - Optionalvar?: [string, string]
Returns string
Example
```
foo.format() // equivalent to foo.toString()
```
Example
```
foo.format({terse: false}) // spell out all parentheses
```
Example
```
foo.format({html: true}) // use HTML tags and entities
```
Example
```
foo.format({ around: ['(', ')'], brackets: ['', ''], lambda: ['(', '->', ')'] }) // lisp style, still back-parsable
```
Example
```
foo.format({ lambda: ['&lambda;', '.', ''] }) // pretty-print for the math department
```
Example
```
foo.format({ lambda: ['', '=>', ''], terse: false }) // make it javascript
```
Example
```
foo.format({ inventory: { T } }) // use T as a named term, expand all others
```
- Defined in expr.ts:822

`Protected` `Abstract`formatImpl

formatImpl(options: RefinedFormatOptions, nargs: number): string
Protected
Internal method for format(), which performs the actual formatting.
Parameters
- options: RefinedFormatOptions
- nargs: number
Returns string
- Defined in expr.ts:861

infer

infer(options?: { max?: number; maxArgs?: number; maxSize?: number }): TermInfo
Sealed
Try to empirically find an equivalent lambda term for the expression, returning also the term's arity and some other properties.
```
  This is used internally when declaring a Native / Alias term,
  unless {canonize: false} is used.

  As of current it only recognizes terms that have a normal form,
  perhaps after adding some variables. This may change in the future.

  Use toLambda() if you want to get a lambda term in any case.
```
Parameters
- options: { max?: number; maxArgs?: number; maxSize?: number } = {}
Returns TermInfo
- Defined in expr.ts:358

invoke

invoke(arg: Expr): Invocation | null
Apply term reduction rules, if any, to the given argument. A returned value of null means no reduction is possible. A returned value of Expr means the reduction is complete and the application of this and arg can be replaced with the result. A returned value of a function means that further arguments are needed, and can be cached for when they arrive.

This method is between apply() which merely glues terms together, and step() which reduces the whole expression.

foo.invoke(bar) is what happens inside foo.apply(bar).step() before reduction of either foo or bar is attempted.

The name 'invoke' was chosen to avoid confusion with either 'apply' or 'reduce'.
Parameters
- arg: Expr
Returns Invocation | null
- Defined in expr.ts:589

run

run(opt?: Expr | RunOptions, ...args: Expr[]): Run
Sealed
Iteratively apply step to the expression until it's irreducible, or until the provided limits are reached.

Returns { expr: Expr, steps: number, final: boolean }.

If { throw: true } is given and no irreducible form was reached within the limits, an error is thrown.
Parameters
- Optionalopt: Expr | RunOptions = {}
- ...args: Expr[]
Returns Run
- Defined in expr.ts:612

step

step(): Step
iterate one step of a calculation.

Returns Step
- Defined in expr.ts:597

subst

subst(search: Expr, replace: Expr): Expr | null
Replace all instances of search in the expression with replace and return the resulting expression, or null if no changes could be made.

Lambda terms and applications will never match if used as plug as they are impossible to compare without extensive computations.

Typically used on variables but can also be applied to other terms, e.g. aliases. See also Expr.traverse() for more flexible replacement of subterms.
Parameters
- search: Expr
- replace: Expr
Returns Expr | null
- Defined in expr.ts:566

toJSON

toJSON(): string | object
Experimental Sealed
Convert the expression to a JSON-serializable format. Sadly the format is not yet finalized and may change in the future.

Returns string | object
- Defined in expr.ts:910

toLambda

toLambda(
options?: { max?: number; maxArgs?: number },
): Generator<{ expr: Expr; steps: number }, void, unknown>
Sealed
Returns a series of lambda terms equivalent to the given expression, up to the provided computation steps limit.
```
  Unlike infer(), this method will always return something,
  even if the expression has no normal form.

  See also Expr.walk() and Expr.toSKI().
```
Parameters
- options: { max?: number; maxArgs?: number } = {}
Returns Generator<{ expr: Expr; steps: number }, void, unknown>
- Defined in expr.ts:471

toSKI

toSKI(
options?: { max?: number; maxArgs?: number },
): Generator<{ expr: Expr; final: boolean; steps: number }, void, unknown>
Sealed
Rewrite the expression into S, K, and I combinators step by step. Returns an iterator yielding the intermediate expressions, along with the number of steps taken to reach them.
```
See also Expr.walk() and Expr.toLambda().
```
Parameters
- Optionaloptions: { max?: number; maxArgs?: number } = {}
Returns Generator<{ expr: Expr; final: boolean; steps: number }, void, unknown>
- Defined in expr.ts:518

toString

toString(): string
Sealed
Returns string representation of the expression. Same as format() without options.
```
  Use formatImpl() to override in subclasses.
```
Returns string
- Defined in expr.ts:762

traverse

traverse(
options?: TraverseOptions | TraverseCallback,
change?: TraverseCallback,
): Expr | null

Sealed

Traverse the expression tree, applying change() to each node. If change() returns an Expr, the node is replaced with that value. A null/undefined value is interpreted as "descend further if applicable, or leave the node unchanged".

  Returned values may be decorated:

  SKI.control.prune will suppress further descending even if nothing was returned
  SKI.control.stop will terminate further changes.
  SKI.control.redo will apply the callback to the returned subtree, recursively.

  Note that if redo was applied at least once to a subtree, a null return from the same subtree
  will be replaced by the last non-null value returned.

  The traversal order is leftmost-outermost, unless options.order = 'leftmost-innermost' is specified.
  Short aliases 'LO' and 'LI' (case-sensitive) are also accepted.

  Returns null if no changes were made, or the new expression otherwise.

Parameters

Optionaloptions: TraverseOptions | TraverseCallback
Optionalchange: TraverseCallback

Returns Expr | null

unroll

unroll(): Expr[]
Expand an expression into a list of terms that give the initial expression when applied from left to right: ((a, b), (c, d)) => [a, b, (c, d)]

This can be thought of as an opposite of apply: fun.apply(...arg).unroll() is exactly [fun, ...args] (even if ...arg is in fact empty).

Returns Expr[]
- Defined in expr.ts:445

walk

walk(options?: { max?: number; maxSize?: number }): IterableIterator<Run>
Returns an iterator of reduction steps of the expression, up to the provided limits. Each step is an object of { expr, steps, final }, same as in run.

Mnemonics: like run but slower.
Parameters
- options: { max?: number; maxSize?: number } = {}
Returns IterableIterator<Run>
Remarks
This method is final. Do not override, override step instead.
- Defined in expr.ts:650

Class ExprAbstract

Hierarchy (View Summary)

Index

Constructors

Properties

Methods

Constructors

constructor

Returns Expr

Properties

Optionalarity

Optionalcontext

Optionalnote

Optionalprops

Optionalsize

Methods

Protected_braced

Parameters

Returns boolean

Protected_fold

Type Parameters

Parameters

Returns TraverseValue<T>

Protected_traverse_descend

Parameters

Returns TraverseValue<Expr>

Protected_traverse_redo

Parameters

Returns TraverseValue<Expr>

Protected_unspaced

Parameters

Returns boolean

annotate

Parameters

Optionalarity?: number

Optionalcanonize?: boolean

Optionalfancy?: string

Optionalmax?: number

OptionalmaxArgs?: number

Optionalnote?: string

Returns Expr

any

Parameters

Returns boolean

apply

Parameters

Returns Expr

declare

Parameters

Returns string

diag

Parameters

Returns string

Example

diff

Parameters

Returns string | null

Example

Example

equals

Parameters

Returns boolean

Remarks

expand

Returns Expr

expect

Parameters

Returns void

fold

Type Parameters

Parameters

Returns T

Example

foldBottomUp

Type Parameters

Parameters

Returns T

Example

format

Parameters

Class Expr`Abstract`

`Optional`arity

`Optional`context

`Optional`note

`Optional`props

`Optional`size

`Protected`_braced

`Protected`_fold

`Protected`_traverse_descend

`Protected`_traverse_redo

`Protected`_unspaced

`Optional`arity?: number

`Optional`canonize?: boolean

`Optional`fancy?: string

`Optional`max?: number

`Optional`maxArgs?: number

`Optional`note?: string

`Optional`around?: [string, string]

`Optional`brackets?: [string, string]

`Optional`html?: boolean

`Optional`inventory?: Record<string, Named>

`Optional`lambda?: [string, string, string]

`Optional`redex?: [string, string]

`Optional`space?: string

`Optional`terse?: boolean

`Optional`var?: [string, string]

`Protected` `Abstract`formatImpl