--[[ Kamin Chapter 2 Lisp Interpreter in Lua
     KILT: Kamin Interpreter in Lua Toolset
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

This implements the Lisp language and interpreter defined in Chapter 2
(Lisp) of the textbook:

     Samuel N. Kamin. Programming Languages: An Interpreter-
     Based Approach, Addison Wesley, 1990.

Developed for CSci 658, Software Language Engineering, Fall 2013

1234567890123456789012345678901234567890123456789012345678901234567890

2013-07-22: Initiated from Kamin Chapter 1 base
2013-07-27: Prototyped parser and symbol tables
2013-07-30: Prototyped evaluator [#0.1]
2013-08-11: Incorporated corrections from Core into Lisp
              (environments, evaluator, Name parsing, etc.)
            Changed S-expressions to use linked lists 
            Improved internal documentation [#0.2]
2013-08-13: Added metatable to evaluation table to trap bad opcodes
            Changed integer division to give integer result
            Added pcalls to REPL to catch errors without crashing
2013-08-17: Separated REPL into module (migrated from Core)
            Separated Lisp Opcodes into module of global constants
2013-08-24: Reconstructed modularized main chunk for Lisp from 
            Scheme main chunk and previous Lisp code (Note 1)
2013-08-29: Added requires of the Factory modules

Note 1: Several changes were made to the shared functionality during
the process of modularizing the Scheme interpreter.  These changes
were made in the commented-out Lisp or Core code but were not
reinserted into the previous Lisp files.

1234567890123456789012345678901234567890123456789012345678901234567890

This is an experiment in the use of Lua and the LPEG (Lua Parsing
Expression Grammar) library.  

I developed this interpreter using Lua 5.1.5 and LPEG 0.12-1 on an
Apple Macintosh executing OS X 10.8 (Mountain Lion).  Lua and Luarocks
2.0.13 were installed using Homebrew in July 2013. LPEG was installed
with Luarocks.

This program, and the other Kamin interpreters constructed, should be
modularized to share and reuse design and code across the family. The
program also needs to be tested more thoroughly!


SYNTAX

The syntax follows that of the Chapter 2 Lisp language in the Kamin
textbook.

In the following BNF grammar, all words beginning with capital letters
are nonterminals.  The BNF metasymbols are ::= to show derivation
rules for nonterminals, | for alternatives, ^* for zero or more
repetitions, and ^+ for one or more repetitions.  All other words
(e.g., "define") and symbols (e.g., the left and right parentheses 
and the operator like +) are literals.

Script   ::= Input^+
Input    ::= Expr | FunDef
FunDef   ::= (define Function ArgList Expr)
ArgList  ::= ( Variable^* )
Expr     ::= Value | Variable 
           | ( if Expr Expr Expr )
           | ( while Expr Expr )
           | ( set Variable Expr )
           | ( begin Expr^+ )
           | ( Operator Expr^* )
Operator ::= Function | ValueOp
Value    ::= Integer | QuotedC
QuotedC  ::= 'SExpr
SExpr    ::= Integer | Symbol | ( SExpr^* )
Symbol   ::= Name 
Function ::= Name
Variable ::= Name
ValueOp  ::= + | - | * | / | = | < | > | cons | car | cdr 
           | number? | symbol? | list? | null? | print
Integer  ::= sequence of decimal digits with optional unary -
Name     ::= any sequence of characters that is not an Integer, 
             not a keyword (literals as shown above), 
             not a left or right parenthesis or semicolon, and 
             not white space

In the REPL interface, command "quit" typed to the prompt terminates
the program and, thus, it cannot be used as a variable name.  A
semicolon ";" causes the rest of that line to be ignored by the parser
(i.e., is an end-of-line comment).

This grammar corresponds to that in Kamin Chapter 2 except Kamin does
not have the Script level. (It starts with Input).

Note: The program below also removes single quotes from the characters
allowed in Names and allows Names used for Symbols to include the
control operators such as "if" and "while".  (The latter is to allow
Lisp code to be quoted in S-expressions.) There is some inconsistency
in the Kamin book between what is said in the chapters about the
syntax and what is implemented and/or shown in examples.

This grammar is encoded in LPEG notation for this program.  That 
representation is factored slightly differently than above.


SEMANTICS

The semantics follows that of the Chapter 2 Lisp language in the Kamin
textbook.

The value space consists of S-expressions, which may be integers,
symbols, the nil list, and non-nil lists. In this semantics
description, "nil" means the empty list S-expression in Kamin Lisp,
not the Lua nil value.

The interpreter represents Boolean value "false" by the nil list and
"true" by non-nil S-expressions, canonically by the symbol "T".

Integer ==> Return the S-expression holding the number value. 

Variable ==> Return the S-expression value associated with that
variable name in the current environment. If the variable does not
occur in the current environment, then its value is undefined.

Note: The Kamin Chapter 1 Core and Chapter 2 Lisp languages only have
global variables and formal parameters to function calls.  They do not
have local variables within functions.

(define f (p1 ... pn) e) ==> Define the user-defined function "f" with
"n" formal parameters (where n may be 0) "p1" through "pn" and body
expression "e" and return the name of the function. Expression e may
reference both parameters and global variables. If a formal parameter
and a global variable have the same name, then the value of the
argument corresponding to the parameter is used in evaluation.

(if e1 e2 e3) ==> If test expression "e1" evaluates to false, then
evaluate expression "e3" and return its value; otherwise, evaluate and
return the value of expression "e2.

(while e1 e2) ==> Evaluate test expression "e1".  If it evaluates to
false, then return nil.  Otherwise evaluate body expression "e2", then
reevaluate "e1". Repeat this until "e1" evaluates to false.  A "while"
always returns nil, but "e2" usually includes side effecting
subexpressions such as "set" or "print".

(set v e) ==> Evaluate "e1". Then assign its value to variable "v" and
return this value.

(begin e1 ...en) => Evaluate each of "e1" through "en" in that order
and return the value of "en".

(f e1 ... en) ==> Evaluate each of "e1" through "en" and apply
function "f" to those values as its actual arguments. "f" may be a
user-defined function (given in a "define") or one of the builtin
value operators (i.e., a ValueOp). The number of argument expressions
supplied must match the number of formal parameters expected by the
function definition or operands expected by the builtin operator.

(car s) => Return the first element of nonempty list "s"; otherwise,
its use is an error.

(cdr s) ==> Return the list "s" with its first element removed;
otherwise, its use is an error.

(cons h t) ==> Given S-expression "h" and list "t", return a new list
whose "car" is "h" and "cdr" is "t"; otherwise, its use is an error.

(= s1 s2) ==> Return symbol T (i.e., true) if "s1" and "s2" are the
same number, the same symbol, or both nil; otherwise, return nil
(i.e., false).

(number? s) ==> Return symbol T if "s" is a number; otherwise,
return nil.

(symbol? s) ==> Return symbol T if "s" is a symbol; otherwise,
return nil.

(null? s) ==> Return symbol T if "s" is a nil; otherwise, return
nil.

(list? s) ==> Return symbol T if s is a nonempty list; otherwise, 
return nil.

(+ e1 e2) ==> Return e1 + e2 as an S-expression if both "e1" and "e2"
are number S-expressions; otherwise, return nil. 

Similarly for -, *, and /.

(< e1 e2) ==> Return symbol T if both "e1" and "e2" are numbers and e1
< e2; otherwise, return nil. Similarly for >.

(print e) ==> Prints the S-expression value e and returns this value.

--]]

-- MODULE INCLUSION

-- KILT language selector (global constant)
KILT_LANGUAGE = "lisp"

-- KILT tree utilities library
local util = require "utilities"
local treeConcat, printTree = util.treeConcat, util.printTree

-- KILT Environment Module
local environment = require "environment"
local globalEnv = environment.globalEnv
local assign    = environment.getVal

-- KILT Values Module
local values = require "values"

-- KILT Parser Module
local parser = require "parser"

-- KILT Evaluator Module
local evaluator = require "evaluator"

-- KILT REPL Module
local repl = require("repl")

-- Wire REPL module dependencies
repl.setGlobalEnv(environment.globalEnv)
repl.setParse(parser.parse)
repl.setTrimSpaces(parser.trimSpaces)
repl.setTrimComment(parser.trimComment)
repl.setGetCommand(parser.getCommand)
repl.setEvalScript(evaluator.evalScript)
repl.setValToString(values.valToString)

-- Interactive session begins here

print "Entering Kamin Chapter 2 Lisp Interpreter"
repl.readEvalPrint()
print "Exiting Kamin Lisp Interpreter"