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

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

Overview
Comment:changes to support Lazp
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:15bb3f246c7d5d2cfb58e52a6496b63ab532ff50
User & Date: 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
Hide Diffs Unified Diffs Ignore Whitespace Patch

Added lazp.js.





















>
>
>
>
>
>
>
>
>
>
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(/\*\/[^\/]+$/, '');
}
})()

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

Added testLazp.js.



























































































































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