Fun2

Fun2

Fun2 is an esoteric dialect of JavaScript, and a successor to Fun. Like Fun, a Fun2 program consists entirely of function calls. Fun2 extends Fun by adding a two-layer architecture: an S-expression layer for constructing Lisp data structures, and a Lisp interpreter layer that evaluates them. The result is a language that is genuinely Lisp, expressed in Fun's function-call syntax.

Fun2 was created by Andrew Bayly.

Background: Fun and its limitations

Fun is an esoteric dialect of JavaScript in which every construct is a function call. It is Turing-complete and has a small standard library. However, experience with Fun revealed several design tensions.

The FUNCTION/CALL split. Fun requires the programmer to wrap any expression passed as a deferred computation in FUNCTION(...), and to invoke it later with CALL(...). This split exists because Fun's standard library functions use JavaScript's Function.bind to return suspended computations, and FUNCTION is needed to prevent a body from being unwrapped one level too early. While the underlying wrap mechanism is elegant, the FUNCTION/CALL split is a leaky abstraction — it exposes an implementation detail rather than expressing a clean language concept.

Indexed parameters. User-defined functions in Fun access their arguments via READ_PARAM(D0()), READ_PARAM(D1()), and so on. This is hostile to readability and composition, and has no precedent in functional languages.

Limited variable names. Fun provides only five global variable slots: A through E. This is sufficient for small programs but becomes a significant constraint as programs grow.

Imperative control structures. Fun's primary looping construct is WHILE, and its variable model is based on mutable global and local slots. While recursion is possible, it is awkward, and the overall feel of the language is imperative rather than functional.

Design of Fun2

Fun2 addresses these issues by introducing a two-layer architecture.

The S-expression layer

The S-expression layer provides primitives for constructing Lisp data as plain JavaScript values — numbers, strings (used as symbols), and arrays (used as lists). It has no semantics of its own: it knows nothing about what any symbol means. All meaning is provided by the interpreter layer.

Because the S-expression layer constructs data eagerly using ordinary JavaScript evaluation, there is no need for any equivalent of Fun's wrap mechanism or FUNCTION/CALL split. Function bodies are just arrays — data — until the interpreter chooses to evaluate them.

The interpreter layer

The interpreter layer is a tree-walking Lisp interpreter, implemented as a JavaScript library. It evaluates S-expressions constructed by the S-expression layer. RUN is the bridge between the two layers: it takes one or more S-expressions and evaluates each in turn.

User-defined functions are lists of the form (argnames body), where argnames is a list of parameter name strings and body is an unevaluated S-expression. This is precisely the tinylisp representation, and the interpreter follows tinylisp semantics throughout.

Relationship to tinylisp

The Fun2 interpreter implements a close variant of tinylisp, with the following changes:

• Built-in names are upper-case, to fit the Fun aesthetic and avoid collisions with S-expression layer tokens.
• MUL, DIV, MOD, GT, NOT, and NULL are added as built-ins, beyond tinylisp's minimal set.
• disp is renamed DISP.
• String, character, type, and file-loading primitives are omitted.
• Macros are not supported. The built-in special forms IF, DEF, and QUOTE cover the essential cases where unevaluated arguments are needed. QUOTE combined with EVAL can substitute for macros in many situations, at the cost of some verbosity.

S-expression layer

Digits

D0() through D9() return the integers 0 through 9. For multi-digit numbers, NUM(d1, d2, ... dN) concatenates its arguments as decimal digits and returns the result as a number. For example, NUM(D1(), D0()) returns 10.

Letters

A() through Z() return the single-character strings 'A' through 'Z'. These are used as symbol names in Lisp expressions. For multi-character symbols, TOK(l1, l2, ... lN) concatenates its arguments and returns the result as a string. For example, TOK(M(),A(),P()) returns 'MAP'.

In practice, programmers are encouraged to use single-letter names for frequently referenced symbols, as this is considerably more concise. Multi-letter names via TOK are available when expressiveness is more important than brevity.

Lists

LIST(a1, a2, ... aN) returns a JavaScript array of its arguments. This is the fundamental list constructor. The shorthand _ is provided as an alias, since list construction is extremely common. For example, _(ADD(), D1(), D2()) constructs the S-expression (ADD 1 2). The empty list is constructed as _().

The explicit use of _ to construct lists is intentional — it provides a clear visual signal that a new list is beginning, analogous to the opening parenthesis in conventional Lisp syntax.

Predefined tokens

The following functions return the string of their name, for use as Lisp operator symbols:

Function	Returns
CONS()	'CONS'
HEAD()	'HEAD'
TAIL()	'TAIL'
ADD()	'ADD'
SUB()	'SUB'
MUL()	'MUL'
DIV()	'DIV'
MOD()	'MOD'
EQ()	'EQ'
LT()	'LT'
GT()	'GT'
NOT()	'NOT'
NULL()	'NULL'
IF()	'IF'
DEF()	'DEF'
QUOTE()	'QUOTE'
DISP()	'DISP'

Interpreter layer

The interpreter evaluates S-expressions according to the following rules:

• A number evaluates to itself.
• A string is treated as a symbol and looked up in the current environment.
• An empty list evaluates to itself (representing nil/false).
• A non-empty list is evaluated as a function call: the first element is evaluated to obtain a callable, and the remaining elements are the arguments.

The environment is a stack of scopes. Symbol lookup searches from the innermost scope outward to the global scope.

Built-in functions

These evaluate all their arguments before applying the operation.

Name	Parameters	Description
CONS	item, list	Prepends item to list, returning a new list
HEAD	list	Returns the first element of list, or () if empty
TAIL	list	Returns list without its first element, or () if empty
ADD	a, b	Returns a + b
SUB	a, b	Returns a - b
MUL	a, b	Returns a * b
DIV	a, b	Returns floor(a / b)
MOD	a, b	Returns a mod b
EQ	a, b	Returns 1 if a equals b, else 0
LT	a, b	Returns 1 if a < b, else 0
GT	a, b	Returns 1 if a > b, else 0
NOT	x	Returns 1 if x is falsy (0 or empty list), else 0
NULL	list	Returns 1 if list is the empty list, else 0
EVAL	expr	Evaluates expr, then evaluates the result
DISP	value	Prints value and returns the empty list

Special forms

These do not evaluate all their arguments unconditionally.

Name	Parameters	Description
QUOTE	expr	Returns expr unevaluated
IF	cond, then, else	Evaluates cond; if truthy evaluates and returns then, otherwise else
DEF	name, value	Defines name in the global environment; name must not already be defined

Falsy values are 0 and the empty list (). All other values are truthy.

User-defined functions

A user-defined function is a list of the form (argnames body), where argnames is a list of parameter name strings. Functions are defined using DEF and called by placing them as the first element of a list.

RUN

RUN(expr1, expr2, ... exprN) evaluates each of its arguments as a Lisp S-expression in turn. It is the entry point from the Fun2 S-expression layer into the interpreter layer.

Example programs

Print a number

RUN(
  _(DISP(), D5())
)

Factorial

RUN(
  _(DEF(), F(),
    _(_(N()),
      _(IF(), _(EQ(), N(), D0()),
        D1(),
        _(MUL(), N(), _(F(), _(SUB(), N(), D1())))
      )
    )
  ),
  _(DISP(), _(F(), D5()))
)

Output: 120

Fibonacci

RUN(
  _(DEF(), F(),
    _(_(N()),
      _(IF(), _(LT(), N(), D2()),
        N(),
        _(ADD(),
          _(F(), _(SUB(), N(), D1())),
          _(F(), _(SUB(), N(), D2()))
        )
      )
    )
  ),
  _(DISP(), _(F(), NUM(D1(),D0())))
)

Output: 55

Fold

Defines a fold function R and uses it to sum and then multiply a list, passing ADD and MUL as first-class values.

RUN(
  _(DEF(), R(),
    _(_(F(), A(), L()),
      _(IF(), _(NULL(), L()),
        A(),
        _(R(),
          F(),
          _(F(), A(), _(HEAD(), L())),
          _(TAIL(), L())
        )
      )
    )
  ),
  _(DISP(), _(R(), ADD(), D0(), _(QUOTE(), _(D1(), D2(), D3(), D4(), D5())))),
  _(DISP(), _(R(), MUL(), D1(), _(QUOTE(), _(D1(), D2(), D3(), D4(), D5()))))
)

Output:

15
120

Map

Defines a double function D and a map function M, then maps double over a list.

RUN(
  _(DEF(), D(),
    _(_(N()),
      _(MUL(), N(), D2())
    )
  ),
  _(DEF(), M(),
    _(_(F(), L()),
      _(IF(), _(NULL(), L()),
        _(QUOTE(), _()),
        _(CONS(),
          _(F(), _(HEAD(), L())),
          _(M(), F(), _(TAIL(), L()))
        )
      )
    )
  ),
  _(DISP(), _(M(), D(), _(QUOTE(), _(D1(), D2(), D3(), D4(), D5()))))
)

Output: (2 4 6 8 10)

Turing completeness

Fun2 is Turing-complete. This follows directly from the fact that the interpreter layer implements a variant of tinylisp, which is itself Turing-complete. Unlike Fun, no explicit Brainfuck translation is needed to establish this.

Implementation

The Fun2 interpreter is implemented as two JavaScript files: the S-expression layer and the interpreter layer. Both are plain JavaScript libraries with no dependencies. A Fun2 program is a JavaScript file that includes both libraries and calls RUN(...).

An interactive implementation is available at andrewbayly.github.io/esolangs/Fun2/.

See also

• Fun — the predecessor language
• tinylisp — the Lisp dialect implemented by the Fun2 interpreter layer