Lambda Calculus
Check-in [15bb3f246c]
Not logged in

Overview
Comment: changes to support Lazp family | ancestors | descendants | both | trunk files | file ages | folders 15bb3f246c7d5d2cfb58e52a6496b63ab532ff50 bill 2012-03-15 15:06:24
Context
 2012-03-16 14:40 fixed lc.js and lcvm.js so they would load in stricter browsers check-in: cba31deacb user: bill tags: trunk 2012-03-15 15:06 changes to support Lazp check-in: 15bb3f246c user: bill tags: trunk 03:13 changed to support node.js modules check-in: a29ab74885 user: bill tags: trunk
Changes

     > > > > > > > > > >  1 2 3 4 5 6 7 8 9 10  (function(){ var LC=require('./lc.js') var VM=require('./lcvm.js') exports.hereDoc = function(f) { return f.toString(). replace(/^[^\/]+\/\*!?/, ''). replace(/\*\/[^\/]+\$/, ''); } })() 
     > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >  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 55 56 57 58 59 60 61 62 63 64 65 66  @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. ## Standard Functions _lit v -- AST literal value _ref v -- AST variable reference _apply[ func, arg, arg, arg] -- AST function application (uses , and ] for varargs) _lambda var body -- AST lambda binding _macro var body -- AST macro binding _prim name -- AST primitive call cons head tail nil head tail -- normally, this is curried as just “nil” string head tail -- a string int head tail -- identify an int value The AST functions serve as an embedded DSL. ## Values function macro unbound variable primitive value ## 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 54 55 56 57 58 59 60 61  (function(){ var LC=require('./lc.js') var LAZP=require('./lazp.js') function run() { console.log('hello') LC.loadDefs(DEFS) } var DEFS = LAZP.hereDoc(function() {/* true = \x y . x false = \x y . y # Y combinator Y = \g . (\x . g (x x)) \x . g (x x) rec = \f . f (Y f) # rec = \f . f f # lists # using false as "nil" in lists, so you use a list like this: # DUMMY can be anything, but it needs to be there # here's how you use a list: # aList (\h t DUMMY . {list-case}) {empty-case} # If the list is not empty, h and t are the head and tail of the list and it returns list-case. DUMMY is not used, but needs to be there # If the list is empty, it returns empty-case # these defs are required by the pretty-printer: cons, nil, head, tail cons = \a b f . f a b nil = \x y . y head = \l . l \h t . h tail = \l . l \h t . t null = \l . l (\h t D . false) true last = rec \last l . l (\h t D . null t h (last t)) nil append = rec \append l1 l2 . l1 (\h t D . cons h (append t l2)) l2 reverse = \l . (rec \rev l res . l (\h t D . rev t (cons h res)) res) l nil # list constructor: list 1 , 2 , 3 end # first attempt, using recursive 'list' definition # #list = (rec \list rest item if-continue . if-continue (list (cons item rest)) (reverse (cons item rest))) nil #, = true #end = false # # second attempt, using "post-processing" with reverse #[ =(]= \item f . f (cons item nil) #, =.= \l item f . f (cons item l) #] =)= reverse # # current constructor # no post processing # also allows [1, 2, 3 | REST ] (like Prolog) [ =(]= \item c . c \rest . cons item rest , =.= \f item c . c \rest . f (cons item rest) ] =)= \f . f nil | =.= \f rest g . f rest ident = \x . x */}) run() })()