Lambda Calculus
Check-in [f0dacdf977]
Not logged in

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:doc changes
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:f0dacdf977eb70147160b37d9679616c4339b2c2
User & Date: bill 2012-03-20 15:44:30
Context
2012-03-20
15:52
doc changes check-in: 391380a0ba user: bill tags: trunk
15:44
doc changes check-in: f0dacdf977 user: bill tags: trunk
05:17
fixes check-in: f5c87e831e user: bill tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to lazp.wiki.

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))