Ooops
October 17, 2021, 11:12:23

Author Topic: [bmx] Lambda Calculus by Yasha [ 1+ years ago ]  (Read 774 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bmx] Lambda Calculus by Yasha [ 1+ years ago ]
« on: June 29, 2017, 00:28:41 »
Title : Lambda Calculus
Author : Yasha
Posted : 1+ years ago

Description : Lambda calculus "is a formal system for function definition, function application and recursion" (<a href="http://en.wikipedia.org/wiki/Lambda_calculus" target="_blank">Wikipedia[/url]).

This little parser/evaluator (hopefully) allows you to define programs in strings, using a fairly simple notation, and then evaluate them for a result. The interpreter is completely untyped, and uses a form of memoised lazy evaluation (so no expression is evaluated until it's actually needed, as opposed to languages like Blitz, where all arguments to a function are always evaluated before the function is applied).

The syntax is pretty straightforward:  (backslash) stands in for the lambda character. Function parameters can have multi-character names, so if you want to define a function with more than one parameter (really, nested one-parameter functions, as is correct), the names must be separated by spaces. Within a body expression, parentheses group values into subexpressions. The parameters are separated from the body of a function definition by a dot.

For the sake of readability, there are also a couple of syntactic extensions:

 - strings (or block literals) can be defined within nested braces: {foo} . I haven't done anything with this but it provides a simple way to define structured data in literal form.
 - numbers, or at least any character sequence starting with a number, are interpreted as value literals. Because this lambda calculus is completely untyped, values are stored in long, double and string formats within Value objects (how you use these is up to you).
 - applying a value to an argument ignores the argument and returns the value, as if using the function x.K . Is this correct? I don't know but it certainly simplifies things, and removes an area where otherwise type could have inadvertently appeared. (EDIT: That is to say, values are treated as functions that discard their argument and return a constant, so the expression (1 2) returns 1 and ignores the 2)
 - local variables can be defined using let-syntax, to make expressions a bit cleaner. A let definition is strictly equivalent to wrapping the expression in a lambda and applying it, but much easier to read. Let-syntax has two forms: you can either make a "let" definition a closed subexpression at the start of the expression where you want the binding to apply, or you can use "in" after the definition to make it slightly clearer.
 - newline ends an expression at the outermost scope, but has no effect within parentheses. Thus "let" definitions in the outermost scope can have their own lines, which looks nice.
 - anything between a semicolon and a newline is a comment.

Here's an example program written three different ways to demonstrate the different let-syntaxes:
Code: [Select]
let t=x y.x    ;let as separate statements
let f=x y.y
let not=p.p f t
not f

(let t=x y.x) (let f=x y.y) (let not=p.p f t) not f   ;Identical but on one line

let t=x y.x in let f=x y.y in let not=p.p f t in not f   ;using "in" to end a definition

;... all three are converted to this after parsing:
( .(f.(
ot.not f) p.p f t) x y.y) x y.x

You can mix and match these and they should have pretty much the same effect (adding or removing parentheses might change the structure very slightly, of course).

Note that 1) let definitions are not recursive and can only refer to those that came before, not themselves or later definitions; and 2) "let" statements may not appear in any expression, including the outermost scope, after any kind of value expression.

Finally, it's also possible to define built-in functions, using the mechanism at the bottom of the file, which can make some things a lot easier - although it's possible to define basic logic and the natural numbers and so on in terms of the lambda calculus (some examples given), it's not very easy to read or efficient. Built-in functions also provide the ability to do I/O, and in the case of the "do" expression, execute command lists like in an imperative (Blitz) programming language. Builtin functions can be eager or lazy, but must have a particular signature.

Several tiny example programs are listed, but they're kinda hard to read on one line using escaped ~n, so here's one to illustrate syntax ("prog.txt"):
Code: [Select]
let Y = G.(g.G(g g))(g.G(g g))    ; Y combinator (allow recursion)

; Fibonacci function and simple printing wrapper
let fib = f.
 i a b.if (eq? i n) a (f n (+ i 1) (+ a b) a)
let showfib =
.print (Y fib n 1 1 0)

; Reverse loop function - repeat f(n) while decrementing n
let loop = l.
 f.if (eq? n 1) (f n) (do (l (- n 1) f) (f n))

; Print the first ten Fibonacci numbers
Y loop 10 showfib

Within an expression, operators and functions are always written prefix (like in Lisp, which was inspired by this). Pretty much anything can be a variable name, as long as it's not "let", "in", "", "=" or ".", which are special syntax. Variable names are case-sensitive.

Apologies for the incredible mess that is the code, but in my defence this is my first BlitzMax program (I just wrote it to take a break from boring stuff, nothing practical). [/i]

Code :
Code: BlitzMax
  1. 'Lazy Lambda Calculus Interpreter
  2.  
  3. Framework brl.StandardIO
  4. Import brl.Retro
  5.  
  6. SuperStrict
  7.  
  8. Local code:String = LoadText("prog.txt")                'Your code here
  9.  
  10. '       Working example programs, increasing complexity:
  11. '"let y = 7 ~n let x = 8 in x y"
  12. '"(x.(y.x y))5 7"
  13. '"if (- 1 1) (* 2 3) (- 9 2)"
  14. '"do (print 1) (print 2) (print 3)"
  15. '"(f.f(f 9))((x.x)(x.x))"
  16. '"let true = x y.x in let false = x y.y in true (false 6(true 1 3)) 8"
  17. '"let true = x y.x~nlet false = x y.y~nlet if = p a b.p a b~nif false (false 1 2) (true 3 4)"
  18. '"let true = x y.x~nlet false = x y.y~nlet and = p q.p q p~nand true false"
  19. '"let t=x y.x~nlet f=x y.y~nlet not=p.p f t~nnot f"
  20. '"let t=x y.x~nlet f=x y.y~nlet or=p q.p p q~nlet and=p q.p q p~nor (and t f) (and t t)"
  21. '"let t=x y.x~nlet f=x y.y~nlet if=p a b.p a b~nlet not=p.p f t~n(p.if p (f p (not p)) p) t"
  22. '"let t=x y.x~nlet f=x y.y~nlet zero=f x.x~nlet succ=
  23.  f x.f(n f x)~nlet is0=
  24. .n(x.f)t~nis0 (succ zero)"
  25. '"let t=x y.x~nlet f=x y.y~nlet if=p a b.p a b~nlet not=p.p f t~nlet Y = G.(g.G(g g))(g.G(g g))~nY (f p.if p (f (not p)) p) t"
  26. '"let Y = G.(g.G(g g))(g.G(g g))~nY (f p.if p (f (- p 1)) p) 2"
  27. '"let Y = G.(g.G(g g))(g.G(g g))~nlet F = f.
  28. . if(eq? n 0) 1 (* n (f(- n 1)))~nY F 10"
  29.  
  30. Print code + "~n"
  31.  
  32. Local e:Expression = Parse(code, Print, GlobalEnv())
  33. If e <> Null
  34.         PrintParseTree e
  35.         Print "~nResult:"
  36.         Print Evaluate(e, DebugLog).ToString()
  37. EndIf
  38.  
  39. Print "~n...done!"
  40.  
  41.  
  42.  
  43. Function Parse:Expression(code:String, errFunc(e:String), gEnv:Variable)                'Parse an input string into a tree
  44.         Local e:Expression = Null
  45.        
  46.         Try
  47.                 Local s:Source, t:Expression, defs:TList = New TList
  48.                 code = Trim(code)
  49.                 If code.Length
  50.                         s = Source.Make(code)   'Appends one ~n, to ensure we can end easily
  51.                         e = Expression.Make(gEnv, False)
  52.                         While s.c < s.code.Length
  53.                                 t = ParseExpression(s, "~n", gEnv, False)       'Note gEnv - updates if vars are defined
  54.                                 If t <> Null    'Ignore null expressions... they're just blank lines
  55.                                         If t.isDef
  56.                                                 If e.body.Count() Then LambdaError.Error "Cannot define variable after expression has begun", s.getLine()
  57.                                                 defs.AddFirst(t) ; gEnv = t.env         'Shuffle the environments back round
  58.                                         Else
  59.                                                 e.AddTerm(t)    'Add as expression term
  60.                                         End If
  61.                                 EndIf
  62.                         Wend
  63.                        
  64.                         If e.body.Count() = 0 Then LambdaError.Error "No expression to evaluate!"
  65.                        
  66.                         For t = EachIn defs             'If any local variables were defined, wrap the expression in their lambda forms
  67.                                 e.env = t.env ; t.env = t.env.env               'We know that e isn't a lambda, here
  68.                                 t.body.AddFirst(e) ; e.ttype = Term.isLAM ; e = t
  69.                         Next
  70.                 EndIf
  71.         Catch err:LambdaError
  72.                 If err.line
  73.                         errFunc "Error on line " + err.line + ": " + err.MSG
  74.                 Else
  75.                         errFunc "Error: " + err.MSG
  76.                 EndIf
  77.                 e = Null
  78.         End Try
  79.        
  80.         Return e
  81.        
  82.         Function ParseExpression:Expression(s:Source, terminator:String, env:Variable, isDef:Int)
  83.                 Local e:Expression, c:String, braceLevel:Int = 0, token:String = "", defs:TList = New TList, d:Expression
  84.                
  85.                 e = Expression.Make(env, isDef)
  86.                 While s.c < s.code.Length
  87.                         c = s.getChr()
  88.                        
  89.                         If braceLevel = 0
  90.                                 Select c
  91.                                         Case ";"        'Comment
  92.                                                 While s.c < s.code.Length
  93.                                                         c = s.getChr() ; If c = "~n" Then s.c:-1; Exit  'Backup, the newline might be important
  94.                                                 Wend
  95.                                         Case terminator
  96.                                                 If token.Length Then e.AddToken(token, s.getLine()) ; token = ""        'Don't forget a token if there was no separator
  97.                                                 If e.body.Count() = 0
  98.                                                         If terminator = "~n" Then Return Null Else LambdaError.Error "Expression must have content", s.getLine()
  99.                                                 Else
  100.                                                         Exit
  101.                                                 EndIf
  102.                                         Case ")"        'If terminator wasn't )
  103.                                                 LambdaError.Error "Mismatched parentheses", s.getLine()
  104.                                         Case "="
  105.                                                 LambdaError.Error "Unexpected character: ~q=~q", s.getLine()
  106.                                         Case "{"
  107.                                                 If token.Length Then e.AddToken(token, s.getLine()) ; token = ""
  108.                                                 braceLevel = 1
  109.                                         Case "}"
  110.                                                 LambdaError.Error "Mismatched braces", s.getLine()
  111.                                         Case "("
  112.                                                 If token.Length Then e.AddToken(token, s.getLine()) ; token = ""
  113.                                                 d = ParseExpression(s, ")", e.env, False)               'e.env not env
  114.                                                 If d.isDef
  115.                                                         If e.body.Count() Then LambdaError.Error "Cannot define local variable after expression has begun", s.getLine()
  116.                                                         defs.AddFirst(d) ; e.env = d.env        'Shuffle the environments back round
  117.                                                 Else
  118.                                                         e.AddTerm(d)    'Add as expression term
  119.                                                 End If
  120.                                         Case ""
  121.                                                 If token.Length Then e.AddToken(token, s.getLine()) ; token = ""
  122.                                                 If e.body.Count()
  123.                                                         e.AddTerm ParseLambda(s, terminator, e.env, isDef)      'e.env not env
  124.                                                 Else
  125.                                                         e = ParseLambda(s, terminator, env, isDef)              'Simplify...
  126.                                                 EndIf
  127.                                                 Exit    'The expression has to end with the end of the lambda - lambda body already ate the terminator
  128.                                         Default
  129.                                                 If c[0] > 32                    'Build token
  130.                                                         token:+c
  131.                                                 ElseIf token.Length             'Whitespace
  132.                                                         If token = "let"                'Name definition
  133.                                                                 If e.body.Count() Then LambdaError.Error "Cannot define variable in middle of expression", s.getLine()
  134.                                                                 d = ParseLet(s, terminator, e.env) ; token = ""         'Note: e.env not env
  135.                                                                 If d.isDef = 2  'If it's applied to this expression only with "in"
  136.                                                                         defs.AddFirst(d) ; e.env = d.env        'Don't exit - doesn't escape
  137.                                                                 Else
  138.                                                                         e = d ; Exit
  139.                                                                 EndIf
  140.                                                         ElseIf token = "in"             'End of name definition
  141.                                                                 If isDef
  142.                                                                         e.isDef = 2     'Mark that we ended on "in"
  143.                                                                         If e.body.Count() = 0 Then LambdaError.Error("Empty definition", s.getLine()) Else Exit
  144.                                                                 Else
  145.                                                                         LambdaError.Error "~qin~q without ~qlet~q", s.getLine()
  146.                                                                 End If
  147.                                                         Else
  148.                                                                 e.AddToken(token, s.getLine())  'Unknown term type - check whether it's a value, a variable, or an error
  149.                                                                 token = ""
  150.                                                         EndIf
  151.                                                 End If
  152.                                 End Select
  153.                         Else
  154.                                 If c = "{" Then braceLevel:+1 Else If c = "}" Then bracelevel:-1
  155.                                 If braceLevel
  156.                                         token:+c                'Don't add the final } if it reached zero
  157.                                 Else
  158.                                         e.AddTerm(Value.Make(token))', e.env))
  159.                                         token = ""
  160.                                 EndIf
  161.                         EndIf
  162.                 Wend
  163.                
  164.                 If s.c >= s.code.Length         'Reached the end of input?
  165.                         If braceLevel Then LambdaError.Error "Mismatched braces: did not close", s.getLine()
  166.                         If terminator[0] > 32 Then LambdaError.Error "Incomplete expression: expecting ~q" + terminator + "~q to close", s.getLine()
  167.                 EndIf
  168.                
  169.                 For d = EachIn defs             'If any local variables were defined, wrap the expression in their lambda forms
  170.                         If e.ttype = Term.isEXP Then e.env = d.env Else e.env.env = d.env               'Lambdas need special treatment
  171.                         d.env = d.env.env
  172.                         d.body.AddFirst(e) ; d.isDef = e.isDef
  173.                         e.ttype = Term.isLAM ; e = d
  174.                 Next
  175.                
  176.                 Return e
  177.         End Function
  178.        
  179.         Function ParseLambda:Expression(s:Source, terminator:String, env:Variable, isDef:Int)
  180.                 Local token:String = "", c:String
  181.                
  182.                 While s.c < s.code.Length
  183.                         c = s.getChr()
  184.                         Select c
  185.                                 Case ";"        'Comment
  186.                                         While s.c < s.code.Length
  187.                                                 c = s.getChr() ; If c = "~n" Then s.c:-1; Exit  'Backup, the newline might be important
  188.                                         Wend
  189.                                 Case "(", ")", terminator, "{", "}", "", "="            'Note that newline is OK if parenthesised
  190.                                         LambdaError.Error "Expecting parameter name; found control character ~q" + c + "~q", s.getLine()
  191.                                 Case "."
  192.                                         If token.Length
  193.                                                 Exit
  194.                                         Else
  195.                                                 LambdaError.Error "Expecting parameter name; found control character ~q" + c + "~q", s.getLine()
  196.                                         EndIf
  197.                                 Default
  198.                                         If c[0] > 32                    'Build token
  199.                                                 token:+c
  200.                                         ElseIf token.Length             'Whitespace
  201.                                                 Exit
  202.                                         End If
  203.                         End Select
  204.                 Wend
  205.                 Local l:Expression = Expression.Make(Variable.Make(token, env), isDef) ; l.ttype = Term.isLAM
  206.                
  207.                 If c <> "."             'If we haven't had the start character yet, skip whitespace
  208.                         While s.c < s.code.Length
  209.                                 c = s.getChr()
  210.                                 If c[0] > 32
  211.                                         If c[0] <> 46 Then s.c:-1               'Backup if not dot - the next character is probably important
  212.                                         Exit
  213.                                 EndIf
  214.                         Wend
  215.                 EndIf
  216.                 If s.c = s.code.Length Then LambdaError.Error "Body of lambda abstraction not found!", s.getLine()
  217.                
  218.                 Local b:Expression
  219.                 If c = "."
  220.                         b = ParseExpression(s, terminator, l.env, isDef)
  221.                         If b.env = l.env                'Only store the whole thing if it's a full lambda
  222.                                 l.body = b.body ; l.isDef = b.isDef
  223.                         Else
  224.                                 l.body.AddFirst(b)
  225.                         EndIf
  226.                 Else            'Listing two or more parameters is literally read the same way as nesting the lambdas
  227.                         b = ParseLambda(s, terminator, l.env, isDef)
  228.                         l.isDef = b.isDef ; l.body.AddFirst b           'Push the lambda as only term
  229.                 EndIf
  230.                 If l.body = Null Then LambdaError.Error "Expecting body for lambda abstraction", s.getLine()
  231.                
  232.                 Return l
  233.         End Function
  234.        
  235.         Function ParseLet:Expression(s:Source, terminator:String, env:Variable)
  236.                 Local token:String = "", c:String
  237.                
  238.                 While s.c < s.code.Length
  239.                         c = s.getChr()
  240.                         Select c
  241.                                 Case ";"        'Comment
  242.                                         While s.c < s.code.Length
  243.                                                 c = s.getChr() ; If c = "~n" Then s.c:-1; Exit  'Backup, the newline might be important
  244.                                         Wend
  245.                                 Case "(", ")", terminator, "{", "}", "", "."
  246.                                         LambdaError.Error "Expecting parameter name; found control character ~q" + c + "~q", s.getLine()
  247.                                 Case "="
  248.                                         If token.Length
  249.                                                 Exit
  250.                                         Else
  251.                                                 LambdaError.Error "Expecting parameter name; found control character ~q" + c + "~q", s.getLine()
  252.                                         EndIf
  253.                                 Default
  254.                                         If c[0] > 32                    'Build token
  255.                                                 token:+c
  256.                                         ElseIf token.Length             'Whitespace
  257.                                                 Exit
  258.                                         End If
  259.                         End Select
  260.                 Wend
  261.                 Local n:Variable = Variable.Make(token, env)
  262.                
  263.                 If c <> "="             'If we haven't had the definition character yet, skip whitespace
  264.                         While s.c < s.code.Length
  265.                                 c = s.getChr()
  266.                                 If c = "=" Then Exit
  267.                         Wend
  268.                 EndIf
  269.                 If s.c = s.code.Length Then LambdaError.Error "Expecting definition for variable ~q" + token + "~q", s.getLine()
  270.                
  271.                 Local d:Expression = ParseExpression(s, terminator, env, True)  'The var definition - note its env is not v
  272.                 If d = Null Then LambdaError.Error "Expecting definition for ~qlet " + n.name + "~q = ..."
  273. '               If isREPL Then n.def = d        'This isn't circular if done right
  274.                 Local l:Expression = Expression.Make(n, d.isDef)
  275.                 If d.ttype = Term.isEXP And d.body.Count() = 1 Then l.body.AddFirst(d.body.First()) Else l.body.AddFirst(d)
  276.                
  277.                 Return l
  278.         End Function
  279. End Function
  280.  
  281. Function PrintParseTree(t:Term, indent:Int = 0, nlev:Int = 0)   'Print a parsed expression tree to output
  282.         Local elem:Term
  283.        
  284.         Select True
  285.                 Case Term.isBIN = t.ttype               'Comes before isVAL and isLAM as it has those flags too
  286.                         rPrint Builtin(t).name, indent
  287.                 Case (Term.isEXP & t.ttype) > 0         'Note that lambdas also have isVal set, so this comes first
  288.                         rPrint t.ttype + ": expr " + Expression(t).id + " (level " + nlev + ", " + Expression(t).env.ToString() + "):", indent
  289.                         For elem = EachIn Expression(t).body
  290.                                 PrintParseTree elem, indent + 4, nlev + 1
  291.                         Next
  292.                         rPrint "(~~expr " + Expression(t).id + " level " + nlev + ")", indent
  293.                 Case (Term.isVAL & t.ttype) > 0
  294.                         rPrint Value(t).sval, indent
  295.                 Case (Term.isVAR & t.ttype) > 0
  296.                         rPrint Variable(t).name, indent
  297.         End Select
  298.        
  299.         Function rPrint(txt:String, indent:Int)
  300.                 Print RSet("", indent) + txt
  301.         End Function
  302. End Function
  303.  
  304. Function Evaluate:Term(t:Term, errFunc(e:String))       'Evaluate a parsed expression tree (non-recursive)
  305.         Try
  306.                 Local eStack:TList = New TList ; eStack.AddFirst(t)             'Use a secondary stack (prevent overflow of call stack)
  307.                
  308.                 While (Term(eStack.Last()).ttype & Term.isVAL) = False  'While the bottom of the stack is a var or expression
  309.                         Local e:Expression
  310.                         t = Term(eStack.RemoveFirst())  'Pop stack
  311.                        
  312.                         If t.ttype & Term.isVAL         'Unapplied lambdas and literal values
  313.                                 e = Expression(eStack.First())
  314.                                 If e = Null Or e.ttype <> Term.isEXP Then LambdaError.Error "Unexpected error - missing expression"
  315.                                 e.body.AddFirst(t)
  316.                                        
  317.                         Else            'Expressions
  318.                                 e = Expression(t) ; If e.mutable = False Then e = e.Copy()      'This one might not fire often
  319.                                
  320.                                 Local fst:Term = Term(e.body.First()), snd:Term
  321.                                 If fst = Null Then LambdaError.Error "Unexpected error - empty expression"
  322.                                
  323.                                 Select fst.ttype
  324.                                         Case Term.isVAL
  325.                                                 eStack.AddFirst(fst)    'If it's a pure value, just return it
  326.                                                
  327.                                         Case Term.isVAR
  328.                                                 LambdaError.Error "Unexpected error - unsubstituted variable ~q" + fst.ToString() + "~q"
  329.                                                
  330.                                         Case Term.isEXP                         'Still arguments to apply?
  331.                                                 If e.body.FirstLink() <> e.body.LastLink() Then e.body.RemoveFirst() ; eStack.AddFirst(e)
  332.                                                 eStack.AddFirst(fst)
  333.                                                
  334.                                         Case Term.isLAM
  335.                                                 Local l:Expression = Expression(fst)
  336.                                                
  337.                                                 If e.body.FirstLink() = e.body.LastLink()       'No arguments, so just return the lambda
  338.                                                         If l.mutable = False Then l = l.Copy()
  339.                                                         eStack.AddFirst(l)
  340.                                                        
  341.                                                 Else    'Apply the lambda to the argument
  342.                                                         e.body.RemoveFirst() ; snd = Term(e.body.RemoveFirst())
  343.                                                         l = l.Apply(snd)        'Application always creates a copy of the function being applied
  344.                                                        
  345.                                                         If e.body.First() <> Null               'If there are any other arguments in this expression
  346.                                                                 eStack.AddFirst(e)      'Put the expression back
  347.                                                         Else
  348.                                                                 e.body.AddFirst(l)
  349.                                                         EndIf
  350.                                                         eStack.AddFirst(l)
  351.                                                 End If
  352.                                        
  353.                                         Case Term.isBIN
  354.                                                 Local b:Builtin = Builtin(fst)
  355.                                                
  356.                                                 If e.body.FirstLink() = e.body.LastLink()       'No arguments, so just return the value
  357.                                                         eStack.AddFirst(b)
  358.                                                        
  359.                                                 Else    'Apply the function to the argument
  360.                                                         e.body.RemoveFirst() ; snd = Term(e.body.RemoveFirst())
  361.                                                         snd = b.Apply(snd)      'Store result in snd, which may be a curried copy of itself
  362.                                                        
  363.                                                         If e.body.First() <> Null               'If there are any other arguments in this expression
  364.                                                                 eStack.AddFirst(e)      'Put the expression back
  365.                                                         Else
  366.                                                                 e.body.AddFirst(snd)
  367.                                                         EndIf
  368.                                                         eStack.AddFirst(snd)
  369.                                                 End If
  370.                                 End Select
  371.                         EndIf
  372.                 Wend
  373.                
  374.                 Return Term(eStack.RemoveLast())        'Eventual expression value
  375.         Catch err:LambdaError
  376.                 If errFunc <> Null Then errFunc "Error: " + err.MSG Else Throw err
  377.         End Try
  378. End Function
  379.  
  380. Type Source
  381.         Field code:String
  382.         Field multiLine:Int
  383.         Field c:Int
  384.        
  385.         Function Make:Source(code:String)
  386.                 Local s:Source = New Source
  387.                 s.c = 0; s.multiLine = code.Contains("~n")      'Don't give line numbers for a single-line expression
  388.                 s.code = code + "~n"
  389.                 Return s
  390.         End Function
  391.        
  392.         Method getChr:String()
  393.                 c:+1
  394.                 Return Chr(code[c - 1])
  395.         End Method
  396.        
  397.         Method getLine:Int()    'Get the line number of the current character
  398.                 Local i:Int, l:Int = 1  'Start on line 1
  399.                 For i = 0 To c - 1
  400.                         If code[i] = 10 Then l:+1       'Count the newline characters before c
  401.                 Next
  402.                 Return l * multiLine
  403.         End Method
  404. End Type
  405.  
  406. Type Term Abstract
  407.         Const isVAL:Int = 1, isVAR:Int = 2, isEXP:Int = 4, isLAM:Int = 1 + 4, isBIN:Int = 1 + 4 + 8
  408.         Field ttype:Int
  409.         Field env:Variable              'Argument, or evaluation context (depending on code)
  410. End Type
  411.  
  412. Type Value Extends Term
  413.         Field sval:String, lval:Long, dval:Double
  414.        
  415.         Function Make:Value(token:String)', env:Variable)       'Make a value literal object
  416.                 Local v:Value = New Value
  417.                 v.ttype = Term.isVAL
  418.                 v.sval = token ; v.lval = token.ToLong() ; v.dval = token.ToDouble()
  419.                 'v.env = env            'Err... does this still do anything? I forget
  420.                 Return v
  421.         End Function
  422.        
  423.         Method ToString:String()
  424.                 Return sval
  425.         End Method
  426. End Type
  427.  
  428. Type Variable Extends Term
  429.         Global uIDCount:Long
  430.         Field name:String, uniqueID:Long, def:Term
  431.        
  432.         Method New()
  433.                 ttype = Value.isVAR
  434.         End Method
  435.        
  436.         Function Make:Variable(name:String, env:Variable)
  437.                 Local v:Variable = New Variable
  438.                 v.name = name
  439.                 v.env = env
  440.                 v.uniqueID = uIDCount           'Do we even need this? Don't think so
  441.                 uIDCount:+1             'Honestly I can't be bothered to come up with a "more permanent" solution than this
  442.                 Return v
  443.         End Function
  444.        
  445.         Method ToString:String()
  446.                 Return "var ~q" + name + "~q[" + String.FromLong(uniqueID) + "]"
  447.         End Method
  448.        
  449.         Function GetByName:Variable(name:String, env:Variable)
  450.                 While env <> Null
  451.                         If env.name = name Then Return env
  452.                         env = env.env
  453.                 Wend
  454.                 Return Null
  455.         End Function
  456.        
  457.         Function GetByUID:Variable(uID:Long, env:Variable)
  458.                 While env <> Null
  459.                         If env.uniqueID = uID Then Return env
  460.                         env = env.env
  461.                 Wend
  462.                 Return Null
  463.         End Function
  464. End Type
  465.  
  466. Type Expression Extends Term
  467.         Field body:TList                'List of terms that makes up the expression
  468.         Field isDef:Int                 '1|2 if this is a var definition (helpful for rearranging things), 2 if it ended on "in"
  469.         Field mutable:Int               'True if this is safe to evaluate in place
  470.         Field inScope:Int               'True if this expression is in its original location and can have substitutions made
  471.        
  472.         Field id:Int            'Debug purposes only - provides a recognisable ID, as all functions are nameless
  473.         Global uniquerefid:Int  'Similarly
  474.        
  475.         Method New()
  476.                 ttype = isEXP
  477.                 body = New TList
  478.                 mutable = False
  479.                 inScope = True
  480.         End Method
  481.        
  482.         Function Make:Expression(env:Variable, isDef:Int)
  483.                 Local e:Expression = New Expression
  484.                 e.env = env
  485.                 e.isDef = isDef
  486.                 uniquerefid:+1 ; e.id = uniquerefid             'DEBUG - safe to remove if not desired
  487.                 Return e
  488.         End Function
  489.        
  490.         Method AddToken(t:String, lNo:Int = 0)  'Undetermined token that may be a variable name, a value, or an error
  491.                 Local v:Variable = Variable.GetByName(t, env)
  492.                 If v = Null
  493.                         If t.ToLong() Or t.ToDouble()   'Nonzero number
  494.                                 AddTerm(Value.Make(t))', env))
  495.                         ElseIf t.Contains("0")  'First char is 0, or is $/%/-/. and then 0
  496.                                 If t[0] = 48 Or ((t[0] = 36 Or t[0] = 37 Or t[0] = 45 Or t[0] = 46) And t[1] = 48)
  497.                                         AddTerm(Value.Make(t))', env))
  498.                                 Else
  499.                                         LambdaError.Error "Unrecognised variable name: ~q" + t + "~q", lNo
  500.                                 EndIf
  501.                         Else
  502.                                 LambdaError.Error "Unrecognised variable name: ~q" + t + "~q", lNo
  503.                         EndIf
  504.                 Else            'Variable, either defined or builtin
  505.                         If v.def <> Null And v.def.ttype = Term.isBIN Then AddTerm(v.def) Else AddTerm(v)
  506.                 End If
  507.         End Method
  508.        
  509.         Method AddTerm(t:Term)
  510.                 body.AddLast(t)
  511.         End Method
  512.        
  513.         Method Copy:Expression()                'Perform a shallow copy of the expression object and term list
  514.                 Local c:Expression = New Expression
  515.                 c.ttype = ttype ; c.mutable = True ; c.inScope = inScope ; c.isDef = isDef
  516.                 c.env = env ; c.body = body.Copy()
  517.                 c.id = id       'Debug line (safe to remove)
  518.                 Return c
  519.         End Method
  520.        
  521.         Method Apply:Expression(arg:Term)               'This is now where substitution happens
  522.                 Local l:Expression
  523.                
  524.                 l = Copy()      'l must always be unique at this step or errors could result
  525.                 If arg.ttype & Term.isEXP And arg.ttype <> Term.isBIN
  526.                         arg = Expression(arg).Copy()    'Make sure it's a copy
  527.                         Expression(arg).inScope = False
  528.                 EndIf
  529.                
  530.                 l.ttype = Term.isEXP
  531.                 l.Subst(l.env, arg)             'Replace all references to l.env with arg within the body and nested expressions
  532.                 Return l
  533.         End Method
  534.        
  535.         Method Subst(v:Variable, t:Term)                'Go through the termlist and replace a variable with an argument
  536.                 Local elem:Term, newBody:TList = New TList
  537.                
  538.                 For elem = EachIn body
  539.                         If elem.ttype = Term.isVAR
  540.                                 If Variable(elem).uniqueID = v.uniqueID Then elem = t
  541.                         ElseIf elem.ttype & Term.isEXP And elem.ttype <> Term.isBIN
  542.                                 Local sub:Expression = Expression(elem).Copy()  'Copy every expression term regardless, for safety
  543.                                 If sub.inScope Then sub.Subst(v, t) ; elem = sub
  544.                         EndIf
  545.                        
  546.                         newBody.AddLast(elem)   'Building a new list is cleaner than editing the old one in-place
  547.                 Next
  548.                
  549.                 body = newBody
  550.         End Method
  551.        
  552.         Method ToString:String()
  553.                 If ttype = Term.isLAM Then Return "Lambda " + id + " (" + env.ToString() + ")"  'This is actually enough to ID a lambda
  554.                 Return "Expression " + id + " (" + env.ToString() + ")" 'For an expr, not so much, but meh
  555.         End Method
  556. End Type
  557.  
  558. Type Builtin Extends Term               'Builtin functionality for extra speed or convenience (or IO, side-effects, etc.)
  559.         Field arity:Int, aCount:Int, name:String        'Note that builtin functions may not have optional parameters
  560.         Field applied:Term[], lazy:Int
  561.         Field func:Term(args:Term[])            'The BlitzMax function to call
  562.        
  563.         Method New()
  564.                 ttype = Term.isBIN
  565.                 aCount = 0
  566.         End Method
  567.        
  568.         Function Make:Builtin(func:Term(args:Term[]), arity:Int, name:String = "", lazy:Int = False)
  569.                 Local b:Builtin = New Builtin
  570.                 b.arity = arity
  571.                 b.func = func
  572.                 b.applied = New Term[arity]
  573.                 b.name = name           'This is only important for printing the parse tree or similar tasks
  574.                 b.lazy = lazy
  575.                 Return b
  576.         End Function
  577.        
  578.         Method Copy:Builtin()
  579.                 Local c:Builtin = New Builtin
  580.                 c.arity = arity ; c.func = func ; c.name = name
  581.                 c.aCount = aCount ; c.lazy = lazy
  582.                 c.applied = applied[..]
  583.                 Return c
  584.         End Method
  585.        
  586.         Method Apply:Term(arg:Term)             'Note that this creates a copy every time it's incompletely applied
  587.                 If arg.ttype & Term.isEXP Then arg = Expression(arg).Copy()
  588.                 If aCount < arity - 1   'Incomplete application
  589.                         Local b:Builtin = Copy()
  590.                         b.applied[aCount] = arg
  591.                         b.aCount:+1
  592.                         Return b
  593.                 Else            'Complete - evaluate instead
  594.                         Local args:Term[] = applied[..], i:Int
  595.                         args[aCount] = arg
  596.                         If lazy = False
  597.                                 For i = 0 To arity - 1
  598.                                         args[i] = Evaluate(args[i], Null)
  599.                                 Next
  600.                         EndIf
  601.                         Return func(args)
  602.                 EndIf
  603.         End Method
  604. End Type
  605.  
  606.  
  607. Type LambdaError
  608.         Field msg:String
  609.         Field line:Int
  610.        
  611.         Function Error(msg:String, line:Int = 0)
  612.                 Local err:LambdaError = New LambdaError
  613.                 err.line = line
  614.                 err.msg = msg
  615.                 Throw err
  616.         End Function
  617. End Type
  618.  
  619.  
  620. Function GlobalEnv:Variable()           'This is the place to add user-defined functions
  621.         Global gEnv:Variable
  622.        
  623.         If gEnv <> Null Then Return gEnv        'Cache this so we don't rebuild the same list every time
  624.        
  625.         gEnv = AddBuiltin("*", Multiply, 2, gEnv)               'Names can be pretty much anything - operators are mostly fine
  626.         gEnv = AddBuiltin("-", Subtract, 2, gEnv)
  627.         gEnv = AddBuiltin("eq?", Equality, 2, gEnv)
  628.         gEnv = AddBuiltin("+", lAdd, 2, gEnv)
  629.         gEnv = AddBuiltin("if", lIf, 3, gEnv, True)
  630.         gEnv = AddBuiltin("print", lPrint, 1, gEnv)             'Build a one-way list on gEnv
  631.         gEnv = AddBuiltin("do", lDo, 1, gEnv)
  632.        
  633.         gEnv = Variable.Make("Global Top Level", gEnv)  'Outermost level
  634.        
  635.         Return gEnv
  636.        
  637.         'Use this to add functions - all must have this signature
  638.         Function AddBuiltin:Variable(name:String, func:Term(args:Term[]), arity:Int, env:Variable, lazy:Int = False)
  639.                 Local v:Variable = Variable.Make(name, env)
  640.                 v.def = Builtin.Make(func, arity, name, lazy)
  641.                 Return v
  642.         End Function
  643.        
  644.         'Some simple ones
  645.         Function Multiply:Term(args:Term[])             'Multiply two integers (for factorial demo)
  646.                 Return Value.Make(String.FromLong(Value(args[0]).lval * Value(args[1]).lval))
  647.         End Function
  648.        
  649.         Function Subtract:Term(args:Term[])             'Difference of two integers (for factorial demo)
  650.                 Return Value.Make(String.FromLong(Value(args[0]).lval - Value(args[1]).lval))
  651.         End Function
  652.        
  653.         Function Equality:Term(args:Term[])             'Compare two integers (for factorial demo)
  654.                 Return Value.Make(String.FromLong(Value(args[0]).lval = Value(args[1]).lval))
  655.         End Function
  656.        
  657.         Function lAdd:Term(args:Term[])                 'Sum of two integers (for fibonacci demo)
  658.                 Return Value.Make(String.FromLong(Value(args[0]).lval + Value(args[1]).lval))
  659.         End Function
  660.        
  661.         Function lIf:Term(args:Term[])                  'A definition of If that accepts and returns an int like in BlitzMax
  662.                 Local pred:Term = Evaluate(args[0], Null)       'Note that If is lazy and therefore evaluates args only now
  663.                 If Value(pred).lval
  664.                         Return Evaluate(args[1], Null)
  665.                 Else
  666.                         Return Evaluate(args[2], Null)
  667.                 EndIf
  668.         End Function
  669.        
  670.         Function lPrint:Term(args:Term[])               'Print a value to output
  671.                 Print Value(args[0]).sval
  672.                 Return args[0]  'Just returns itself
  673.         End Function
  674.        
  675.         Function lDo:Term(args:Term[])          'Execute a a list of expressions imperatively
  676.                 Global this:Term
  677.                 If this = Null Then this = Builtin.Make(lDo, 1)
  678.                 Return this             'Since the argument was already evaluated by Apply, all it has to do is return itself
  679.         End Function            'and it can continue to execute any number of commands
  680. End Function


Comments :


Warpy(Posted 1+ years ago)

 Very good! I will give this a go later. I'm not totally sure what you mean about applying values to arguments, but if you mean variable substitution then I think you're right.


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal