Lambda Calculus
Check-in [f0dacdf977]
Not logged in

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 ``` ```@pagedown # Lazp: An untyped, lazy Lambda Calculus with Macros and Primitives To facilitate macros, Lazp uses abstract syntax trees, made from LC cons-lists (i.e. like LISP): a b c -> (_apply (_ref a) (_ref b) (_ref c)) πa . b -> (_lambda (a) (_ref b)) πa . b -> (_macro (a) (_ref b)) -- macro: returns an AST which is then evaluated πx y z -> (_prim x (_ref y) (_ref z)) -- call a primitive function x with arguments y and z Template Haskell demonstrates a perceived need for macros, even in a lazy language, like Haskell. Macros expose the Lazp code-generator to developers which helps with creating external DSLs, among other things. Eval, which takes an AST as an argument, is the identity macro and the Lazp compiler can be exposed as a macro. ## AST Function usage _lit v -- literal value _ref v -- variable reference: should be a string _lambda var body -- lambda binding: var should be a string, body is an AST _apply func arg -- function application: func can be any AST function except a _prim _prim arg rest -- primitive call: rest is either a _prim, _lit, or _ref The AST functions serve as an embedded DSL. ## Examples eval x = πx . x apply func arg = π func arg . _apply (_lit func) (_lit arg) compile code-string -- function returning AST ## Parser macros How these work depends on the parser you use, but they run Lazp code at parse-time. Parser macros can implement things like splicing primitive values into the AST and importing libraries, but the most important thing is that they allow developers to extend the parser. Parser macros can be activated using a standard parser macro (of course :) ). ## Implementation Lazp will start as a virtual machine in JavaScript, with the intent to generate LLVM code. Potentially, there could be a C version in between, so that thereβs a native one before the LLVM one is done. The LLVM version could use the VMKitβs garbage collector or the Boehm-Demers-Weiser garbage collector, which performs well with small objects (like function contexts). ## Function IDs Functions and unbound variables will have IDs that act like runtime types ## Parser (the parser should eventually be written in Lazp) \ is equivalent to π \m\ is equivalent to π \p\ is equivalent to π Since \xxx\ is not legal Lazp syntax, itβs a good way to name character macros. ## LISP-like syntax for Lazp (an alternate parser for curmudgeons) (lambda (a) b) -> (_lambda (a) (_ref b)) (a b c) -> (_apply (_ref a) (_ref b) (_ref c)) ``` ``` > > | | | < | | | | | | | | < < < > ``` ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 ``` ```@pagedown # Lazp: An untyped, lazy Lambda Calculus with Macros and Primitives The goal, here, isn't to make something that's super fast; it's to provide a useable untyped, lazy, lambda calculus for people to use. To facilitate macros, Lazp uses abstract syntax trees, made from LC functions (i.e. like LISP): a b c -> _apply (_apply (_ref a) (_ref b)) (_ref c) πa . b -> _lambda a (_ref b) πx y z -> _prim x (_prim (_ref y) (_ref z)) -- call a primitive function x with arguments y and z Template Haskell demonstrates a perceived need for metaprogramming, even in a lazy language, like Haskell. Eval exposes the Lazp code-generator to developers which helps with creating external DSLs, among other things. ## AST Function usage _lit v -- literal value _ref v -- variable reference: v should be a string _lambda var body -- lambda binding: var should be a string or number, body is an AST _apply func arg -- function application: func can be any AST function except a _prim _prim arg rest -- primitive call: rest is either a _lit, a _ref, or another _prim (which allows more args) The AST functions serve as an embedded DSL. ## Examples eval x = πx . x -- evaluates x apply func arg = π func arg . _apply (_lit func) (_lit arg) compile code-string -- function returning AST ## Parser macros How these work depends on the parser you use, but they run Lazp code at parse-time. Parser macros can implement things like splicing primitive values into the AST and importing libraries, but the most important thing is that they allow developers to extend the parser. Parser macros can be activated using a standard parser macro (of course :) ). ## Implementation Lazp will start as a virtual machine in JavaScript, with the intent to generate native code. Native code could be done in C and/or LLVM. An LLVM version could use the VMKitβs garbage collector or the Boehm-Demers-Weiser garbage collector, which performs well with small objects (like function contexts). ## Function IDs Functions and unbound variables will have IDs that act like runtime types ## Parser (the parser should eventually be written in Lazp) \x . y is equivalent to πx . y Since \xxx\ has no meaning in Lazy, it seems like a good way to name character macros, if you don't want to use up "normal" identifiers in the name space. ## LISP-like syntax for Lazp (an alternate parser for curmudgeons) (lambda (a) b) -> (_lambda (a) (_ref b)) (a b c) -> (_apply (_ref a) (_ref b) (_ref c)) ```