troth

A simple λ-Calculus interpreter

Features

• λ Abstractions
• Expression Aliasing
• Expression Reduction

Syntax

Tokens

ALIAS: [A-Z0-9_$&+,:=?@#|'<>.-^\*%!]+
ID: [a-km-z_]+
OPAREN: \(
CPAREN: \)
DOT: \.
LAMBDA: l
DEFINITION: fn
USE: use "[a-km-z_\\]+"
SEMI: ;

[!NOTE] Comments are denoted by // and run until the end of the line Use statements are one token, just like strings are in other languages

Grammar Rules

definiton: DEFINITION ALIAS expression SEMI
use: USE SEMI
expression: OPAREN (ALIAS | ID | call) CPAREN
call: expression expression
lambda: LAMBDA ID DOT expression

Examples

[!NOTE] This grammar does support numerical and 'special' characters in (and even as the first character of) ALIASes, meaning full high-level languages could be defined with normal arithmatic. However, IDs must be lowercase alphabetic characters and the '_' character.

TODO

• Lexer
• Parser
• Reducer
• Automatic Alpha Converter
• CLI Functionality
• Cross-File Linking (not object files)
  • Basic Static Linking
  • Standard Library for Basic Functions (auto-included)
• Multiple Backend Options
  • Beta Reduction
  • Naive transpilation to λ-calculus with JS syntax

Notes

Transpilation of λ-calculus to higher-level languages is a uniquely difficult task. Nearly all constructs that are built into other languages, such as number literals, are simply encoded in the λ-calculus. This means that while sometimes certain patterns simply act like their analog in a higher-level language, sometimes they serve completely unrelated purposes. Additionally, there are certain quirks of the λ-calculus, which allow these analogs to have a dual form, such as numerical lliterals, which in their Church-encoded form can be used as definite for-loops as well as number literals. Decyphering this seems impossible algorithmically, thus until future revelations, I will not attempt it.

Quirks

• When Troth encounters an ALIAS being invoked, it first runs the alias through a an alpha conversion process, where each id within the aliased expression is appended with an alias-specific postfix to avoid conflation
• Troth performs rudementry static linking by parsing the included file, then copying all entries in the resultant definitions map into the original parser's map
• Currently, Troth immediantly evaluates the expression without displaying intermediate steps