Aug 29 19:13 2013 Core.lua Page 1 --[[ Kamin Chapter 1 Core Interpreter in Lua KILT: Kamin Interpreter in Lua Toolset H. Conrad Cunningham, Professor Computer and Information Science University of Mississippi This implements the Core language and interpreter defined in Chapter 1 (The Basic Evaluator) 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-17: Initiated project 2013-07-19: Prototyped parser and symbol tables 2013-07-20: Prototyped evaluator 2013-07-22: Prototyped REPL interface [#0.1] 2013-07-30: Made more generic from work on Lisp [#0.2] 2013-08-11: Corrected design of environments and evaluator Corrected parsing of Names Continued refactoring to make more generic & readable Improved internal documentation [#0.3] 2013-08-12: Separated Environment and Function Table into modules 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 Separated Core Opcodes into module of global constants 2013-08-24: Reconstructed modularized main chunk for Kamin Core from Scheme main chunk and previous Core 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! Aug 29 19:13 2013 Core.lua Page 2 SYNTAX The syntax follows that of the Chapter 1 Core 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 operators such as +) 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 Function ::= Name Variable ::= Name ValueOp ::= + | - | * | / | = | < | > | 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 1 except Kamin does not have the Script level. (It starts with Input). 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 1 Core language in the Kamin textbook. The value space consists of integers. (Of course, Lua represents all numbers in double precision floating point.) Aug 29 19:13 2013 Core.lua Page 3 The interpreter represents Boolean value "false" by integer 0 and "true" by nonzero values, canonically by the value 1. Integer ==> Returns the integer value. Variable ==> Return the 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 language only has global variables and formal parameters to function calls. It does 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 0. Otherwise evaluate body expression "e2", then reevaluate "e1". Repeat this until "e1" evaluates to false. A "while" always returns 0, 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. (+ e1 e2) ==> Return the integer value e1 + e2 (i.e., the result of adding integer "e1" and "e2"). The builtin arithmetic operators -, *, and / are the operators for subtraction, multiplication, and division. (Because of Lua's use of double precision floating point for all numbers, division may result in a nonintegral value.) (< e1 e2) ==> Return 1 (true) if e1 < e2 in the usual integer Aug 29 19:13 2013 Core.lua Page 4 ordering; otherwise return 0 (false). Similarly for > and =. (print e) ==> Prints the integer value e and returns this value. --]] -- MODULE INCLUSION -- KILT language selector (global constant) KILT_LANGUAGE = "core" -- 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 1 Core Language Interpreter" repl.readEvalPrint() print "Exiting Kamin Core Interpreter"