Project 4Due November 14, 200811:59:59pmUpdates• 11/3. Renamed class method to class of, since methods can’t have same name as keywords.IntroductionIn this project, you will write an interpreter for a new language called Rube, which is a simple object-orientedprogramming language with a syntax similar to Ruby. To get started, we’ve supplied you with a parser fortranslating Rube source code into abstract syntax trees. Your job is to write a series of OCaml functions forexecuting programs in AST form.This is a long write-up mostly because we need to describe precisely what Rube programs do, andbecause we explain this both in English and in math (as operational semantics). But the actual amountof code you’ll need to write for the basic interpreter is remarkably small—in fact, if you understand theoperational semantics, they essentially tell you exactly what to write in OCaml for your interpreter.What to SubmitWe’ve left a p4.tar.gz file in the usual place. This time, this directory contains several files:.submit The usual submit fileMakefile A file for building this projectOCamlMakefile A helper for Makefileast.mli A signature describing Rube abstract syntax treeslexer.mll A lexer for tokenizing Rube programsparser.mly A parser for parsing Rube programs (uses the lexer)rube.ml The file you need to editri.ru Some sample Rube programsTo build the project, cd into the directory and type gmake. This will build an executable rube that simplyreads in a Rube program from standard input, parses it into an abstract syntax tree, unparses the AST tostandard output, and then evaluates the program and prints the result. (“Unparsing” is the process of goingfrom an AST to a textual representation.) For example, if you build rube and then type ./rube < r1.rb,you should see% ./rube < r1.ru"Hello, world!\n".print()Evaluates to:Implement me!The only file you need to submit is rube.ml. You may not modify any of the other files; we will overwritethe other files with fresh copies when we grade your projects. For grading purposes, we will not use theparser—we will invoke the functions that you write in rube.ml directly from within OCaml. However,you will most likely find that being able to parse source programs will make it easier for you to test yourinterpreter. Warning: If you thought OCaml’s parser error messages were bad, you haven’t seen anythingyet! The Rube parser is bare bones, and contains no error recovery whatsoever. So if you make a typo ina Rube program, you’ll just get a parse error message. If you get really stuck with this, just build up yourRube programs inside of OCaml, rather than using the parser.1prog ::= expr Rube programexpr ::= n Integers| nil Nil| "str" String| id Local variable| @id Field| if expr then expr else expr end Conditional| expr; expr Sequencing| id = expr Local variable write| @id = expr Field write| expr.id(expr, . . . , expr) Method invocation| class method . . . method end Anonymous classmethod ::= def id(id, . . . , id) expr endFigure 1: Rube syntaxRube SyntaxThe formal syntax for Rube programs is shown in Figure 1. A Rube program prog is made up of a single (butpossibly quite complicated) expression. To execute a program, we evaluate the expression to yield the resultof the program. For example, the program in r1.ru calls the print method of the string Hello, world!\n,which causes the string to be displayed and then returns nil.In Rube, as in Ruby, everything is an object, including integers n, the null value nil, and strings "str".Local variables are identifiers id, which are made up of upper and lower case letters or symbols (including +,-, *, /, , !, and ?). An identifier with an @ in front of it refers to a field. Rube also includes the conditionalform if, which evaluates to the true branch if the guard evaluates anything except nil, and the false branchotherwise. Rube includes sequencing of expressions, assignments to local variables, and method invocationwith the usual syntax.One interesting feature of Rube is that classes are “first class,” meaning they are treated just like anyother object—they can have methods invoked on them (like the new method, which creates new objects), canbe passed as arguments, and can be returned as results. Classes in Rube are anonymous (like anonymousfunctions defined with fun in OCaml). The expressionclass method . . . method endreturns an object representing the defined class. If you want to define a class and then save it for future use,you can assign it to a variable. For example, consider the file r3.ru, reproduced here:C = classdef m(a, b)@x = a.+(b);@xendend;x = C.new();x.m(1, 2)This program defines a class, assigns it to the local variable C, instantiates it by calling C.new(), and then2invokes a method of the resulting object. Note that, unlike in Ruby, identifiers are all treated the sameregardless of capitalization. (In Ruby, capitalized identifiers are constants that cannot be changed.)Pretty neat, huh! The equivalent Ruby code actually does the same thing—when you write class C ...end in Ruby, you’re assigning to C, and you can freely copy that class around the program. For example,if C and D are both assigned to classes, in Rube and Ruby you can write X = if p then C else D; y =X.new to make y an instance of either C or D, depending on the value of p.We can define precisely how a Rube program executes by giving a formal operational semantics for it.Just like in the class lectures, the first thing we need to do to define a semantics is to explain what programsmay reduce to. In our semantics, programs will reduce to values v given by the following grammar:v ::= n | nil | “str” | {method1. . . methodn} | [class = v0; fields = @id1: v1, . . . , @idn: vn]Values include integers n, the null value nil, and strings “str”. We’ve used a slightly different font here toemphasize the difference between program text, such as nil, and what it evaluates to, nil.We represent classes by special class objects {method1. . . methodn}, where the methodiare the methodsdefined in the class. Finally, to represent object values, we write [class = v0; fields = @id1: v1, . . . , @idn: vn],which is an instance of class v0and which has fields @id1through @idn, and field @idihas value vi. Forexample, in the code above, class C evaluates to {def m(a, b) @x = a.+(b); @x end} and x evaluates to[class = vC; fields = ∅] where vCis what C evaluates to and by ∅ we mean the object has no fields
View Full Document
Unlocking...