Aug 29 19:13 2013 Scheme.lua Page 1 --[[ Kamin Chapter 4 Scheme Interpreter in Lua KILT: Kamin Interpreter in Lua Toolset H. Conrad Cunningham, Professor Computer and Information Science University of Mississippi This implements the Scheme language and interpreter defined in Chapter 4 (Scheme) 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-08-01: Began study and planning 2013-08-09: Began design and programming from Kamin Lisp base 2013-08-14: Completed prototype, including Environment module 2013-08-17: Continued modularizing design. Built Utilities, Opcodes, Values, Parser, Evaluator, and REPL modules from Scheme or common code 2013-08-22: Completed prototype of modularized Scheme interpreter 2013-08-24: Cleaned dependencies and comments 2013-08-29: Added requires of the Factory modules 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 4 Scheme 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., "while") and symbols (e.g., the left and right parentheses and the operator like +) are literals. Aug 29 19:13 2013 Scheme.lua Page 2 Script ::= Input^+ Input ::= Expr Expr ::= Value | Variable | ( if Expr Expr Expr ) | ( while Expr Expr ) | ( set Variable Expr ) | ( begin Expr^+ ) | ( Expr^+ ) Value ::= Integer | QuotedC | ( lambda Arglist Expr ) | ValueOp ArgList ::= ( Variable^* ) QuotedC ::= 'SExpr SExpr ::= Integer | Symbol | ( SExpr^* ) Symbol ::= Name Variable ::= Name ValueOp ::= + | - | * | / | = | < | > | cons | car | cdr | number? | symbol? | list? | null? | | primop? | closure? | 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 4 except Kamin does not have the Script level. (It starts with Input). Note: The program below (following the Lisp interpreter) 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 4 Scheme language in the Kamin textbook. The value space consists of S-expressions, which may be integers, symbols, the nil list, and non-nil lists as in Lisp plus closures and primitive operations. In this semantics description, "nil" means the empty list S-expression in Kamin Lisp, not the Lua nil value. Aug 29 19:13 2013 Scheme.lua Page 3 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. (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". (lambda (p1 ... pn) e) ==> Defines an anonymous user-defined function with "n" formal parameters (where n may be 0) "p1" through "pn" and body expression "e". Evaluation of a lambda expression creates and returns a closure that references the environment existing at the point of the lambda's execution. Expression "e" may reference both parameters of any enclosing scope 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. (e1 ... en) ==> First, evaluate expression "e1", which must be a primitive (builtin ValueOp) operator or a closure. Then evaluate expressions "e2" through "en" (if any) and apply operation "e1" to the values of these actual arguments. The number of argument expressions supplied must match the number of formal parameters expected by the function definition or operands expected by the primitive operator. The meaning of the primitive value operators are as follows. (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 Aug 29 19:13 2013 Scheme.lua Page 4 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. (primop? s) ==> Return symbol T if s is a primitive (value) operator; otherwise, return nil. NOTE: Currently the implementation does not allow control operators (e.g., if, while, begin, and set) to be accepted by this primitive. (closure? s) ==> Return symbol T if s is a closure; 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 = "scheme" -- 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" local controlop, builtin = parser.controlop, parser.builtin Aug 29 19:13 2013 Scheme.lua Page 5 -- 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) -- Initialize the global environment local function initGlobalEnv() globalEnv = {} -- controlops in env not used by Scheme for xt, op in pairs(parser.controlop) do assign(xt, {PRIMSXP,op}, globalEnv) end for xt, op in pairs(parser.builtin) do assign(xt, {PRIMSXP,op}, globalEnv) end return globalEnv end -- Interactive session begins here print "Entering Kamin Chapter 4 Scheme Interpreter" initGlobalEnv() repl.readEvalPrint() print "Exiting Kamin Scheme Interpreter"