[[TracNav]] [[PageOutline]] = Guide to the Interpreter Source Code = The Fortress interpreter is written in Java. It can be run from ant, from the command line, or as junit tests. The plan is to, as much as possible, allow Fortress programs to run as if they were interpreted (without explicit compile, link, and run steps that a user can do wrong), and perform compiler-like operations "behind the curtain". This will change over time as the implementation acquires platform-specific and application-specific optimizations -- the caches will become more like the "Fortresses" in the original language plan, and will acquire operations more interesting than just get, put, and is-up-to-date. ''Explain in more detail'' == AST nodes == The Fortress AST nodes are automatically generated by the [http://sourceforge.net/projects/astgen ASTGen] tool from the [source:trunk/ProjectFortress/astgen/Fortress.ast AST node hierarchy description]. Among other language constructs, Fortress expressions are represented as subclasses of the abstract class {{{Expr}}}. The {{{Expr}}} node hierarchy is particularly interesting because most of the Fortress type checking deals with the subclasses of {{{Expr}}}. Some of the nodes are created internally and some of the nodes are desugared away after a particular phase. Detailed information about [wiki:ExprNodeHierarchy the Expr node hierarchy] is available. == Phase structure == === Preparing to run === The main entry point of the interpreter is [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/drivers/Shell.java Shell]. This is normally invoked from a shell script [source:trunk/ProjectFortress/fortress fortress] ( [source:trunk/ProjectFortress/fortress.bat fortress.bat]) that chooses sensible defaults for classpaths and VM options. The front-end uses repository-like caches to avoid the cost of reparsing, re-syntax-expanding, and re-checking source files over and over again. The caches themselves manage rebuilding, as needed. Once all components and APIs are discovered and up to date, the Shell invokes [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/drivers/Driver.java Driver] to manage the various phases of the interpreter. Directories full of Fortress programs can be compiled for testing purposes. Wrappers (see [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/drivers/SystemJUTests.java SystemJUTests] or [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/drivers/DemoTests.java DemoTests]) invoke [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/drivers/FileTests.java FileTests] to accomplish this. When {{{FileTests}}} runs a Fortress program, success is defined as the absence of Java exceptions from the interpreter, and the absence of "FAIL" in the program output, unless the name of the test begins with "XXX" in which case failure and success are swapped (that is, "XXXFoo.fss" is expected to fail in some way.). It is a convention within the ant script {{{build.xml}}} that any class whose name ends in {{{JUTest}}} or {{{JUTests}}} is run as a target of "{{{ant test}}}"; therefore the {{{SystemJUTests}}} are part of a normal test run, but the {{{DemoTests}}} are not. === Syntax Expansion === Syntax expansion can be applied to components, and depends on syntax definitions found in APIs. The syntax expansion package is called to obtain component ASTs. It performs a partial parse of the source to determine the imports, and then consults the imports (which are expected to contain checked and disambiguated AST) for any applicable syntax expansions. If there are any, then it generates a modified grammar, runs Rats, compiles the resulting parser, and then loads the new parsing classes for the full parse of the source code. '' more here'' === Parsing === The interpreter uses a packrat parser generator called [http://cs.nyu.edu/~rgrimm/xtc/rats.html Rats!] developed by [http://cs.nyu.edu/~rgrimm Robert Grimm]. Although Rats! provides AST utilities, we are not using those, and are instead using our own. All AST nodes include line+column begin and end locations, and we try hard to preserve those and use them appropriately when reporting errors. We chose a packrat parser generator because it works better than all the others that we tried, which included LL(k) (JavaCC), LALR(1) (Javacup), hand-written recursive descent, and GLR(1) (Elkhound). Elkhound was capable of expressing the Fortress language, but sometimes was very slow. The [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/parser Fortress grammar implemented in Rats] is very close to the [http://research.sun.com/projects/plrg/fortress.pdf Fortress grammar described in the Fortress language specification]. === Checking and disambiguation === We are moving more and more semantics checks into a static pass, aiming for an organization more like what would be found in a conventional compiler. The static analysis also performs a first disambiguating rewrite of the input AST, determining which instances of {{{a.b.c}}} are API member references, and which are object member references. At the moment, our current progress on the type-checker is described on the TypeCheckerProgress page. The expanded, parsed, checked, disambiguated version of the AST is what is written into the cache. === AST rewriting === Before the interpreter can run, each component's AST is processed ([DisambiguationRewrite "desugared"]) into a simpler form, the component's initial environment is populated with names, and those things that the component exports are copied into the environments of the exported APIs. Desugaring is important because it rewrites some AST nodes into simpler forms, and also makes name references across object scopes more explicit. === Initializing top-level environments === Top-level (component and API) environments are initialized in "four and a half" passes. 1. The first pass populates the environment with bindings from names to uninitialized things (values, mutables, types, and functions). The entities bound to types and functions require further initialization in later passes; immutable cells are initialized with lazy thunks; mutable cells are initialized with empty references.[[BR]] The first-and-a-half-pass gathers names form imported APIs and injects them into the importing component's environment. 2. The second pass initializes types. 3. The third pass initializes functions, which refer to types. 4. The fourth pass ensures that all mutable and immutable variables are initialized. Immutable cells' thunks are forced and their link is snapped; mutable cells have their initial values computed in order. All components' environments run pass N before any environment runs pass N+1. Once an environment is populated, no more names may be added to it (this is not yet enforced because of legacy bugs from an older design, but that is the plan), but the environment may be copied and extended. Environments are implemented with applicative trees, so that copying is a cheap constant-time operation, and environment extension is a log(number-of-names) operation. This data structure was chosen because (1) it supports scalable unsynchronized reading, and (2) when benchmarked on a uniprocessor (where locking is cheap) it was faster than an obvious implementation build from stacks of hash tables. It would be possible to avoid this strict structuring into four passes if the various Fortress entities were initialized-on-demand, but we plan to eventually write a compiler, and think that this will help us understand the compiler better. We think it also helps with error reporting, but this might not really be so. === Evaluation === Driver looks up the specified main entry point in the initialized environment of the main component, and invokes it. == Run time entities == These are roughly divided into types and values. Values in turn comprise objects and functions. Functions and types may be generic, though generic types are not exactly types and generic functions are not exactly functions. This distinction is muddied somewhat by the lack of type inference, which forces us to sometimes treat generic functions as if they were values. === The "Fcn" hierarchy === * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/Fcn.java Fcn] -- any function at all * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/OverloadedFunction.java OverloadedFunction] -- an overloaded function; a collection of !SingleFcns * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/OverloadedMethod.java OverloadedMethod] -- the method version of an overloaded function; a collection of ??? * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/SingleFcn.java SingleFcn] -- a function defined at one place; it has a location * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/FGenericFunction.java FGenericFunction] -- a generic function defined at one place * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/Simple_fcn.java Simple_fcn] -- a non-generic function defined at one place * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/Dummy_fcn.java Dummy_fcn] -- ''need to track this down'' * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/NonPrimitive.java NonPrimitive] -- Something that can actually be called; a constructor or closure. * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/AnonymousConstructor.java AnonymousConstructor] * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/Constructor.java Constructor] * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/glue/GenericFlatStorageMaker.java GenericFlatStorageMaker] * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/Closure.java Closure] -- Code + environment * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/ClosureInstance.java ClosureInstance] -- The instantiation of a FGenericFunction. * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/FunctionalMethod.java FunctionalMethod] -- The top-level representative of a functional method; usually a member of an overloaded function. * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/MethodClosure.java MethodClosure] -- object methods become method closures. Object and trait methods differ in whether they import the lexical environment of the constructor upon application; this is an issue for objects because of object expressions; otherwise, non-expression object methods and trait methods see a top-level lexical environment. * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/GenericMethod.java GenericMethod] -- generic method, from trait or object. A flag determines which. * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/MethodClosureInstance.java MethodClosureInstance] -- an instance of an object's generic method. Like a method closure, but knows what generic generated it. * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/PartiallyDefinedMethod.java PartiallyDefinedMethod] -- a trait method * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/PartiallyDefinedMethodInstance.java PartiallyDefinedMethodInstance] -- instantiation of a trait's generic method. Like a trait method closure, but knows what generic generated it. * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/NativeMethod.java NativeMethod] * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/GetterMethod.java GetterMethod] * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/values/SetterMethod.java SetterMethod] ''Suggested change: rename !PartiallyDefinedMethod to !TraitMethod'' === Other values === === Environment builders === * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/BuildEnvironments.java BuildEnvironments] -- top-level environment builder * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/EvalVarsEnvironments.java EvalVarsEnvironments] -- a builder that only evaluates variables. * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/BuildTraitEnvironment.java BuildTraitEnvironment] -- within-trait environment builder[[BR]] Overrides {{{newClosure}}}, {{{newGenericClosure}}}, {{{putValue}}}, {{{forFnDecl3}}} * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/BuildObjectEnvironment.java BuildObjectEnvironment] -- within-object environment builder[[BR]] Overrides {{{newClosure}}}, {{{newGenericClosure}}} (again). * [source:trunk/ProjectFortress/src/com/sun/fortress/interpreter/evaluator/BuildLetEnvironments.java BuildLetEnvironments] -- let (local) environment builder === Types === The types are somewhat in flux, as more and more of the "primitive" types are replaced by instances of traits, except where the constraints of practical implementation forbid it. For example, {{{FTypeArray}}} will eventually vanish because arrays are implemented in libraries. == TO DO == There's no discussion of the evaluator visitor at all. There's no discussion of structure of phases as visitors over ASTs. We need a description of each package and what's contained in it, as well as other important directories. ''Separate page'' We should discuss the various Ant targets. ''Probably on a separate page'' There's no discussion of parallel execution and how we do it. There's no discussion of what libraries we rely on (dstm2, etc.) We should mention !FortressLibrary.fss and how it hooks in (as well as other libraries). We could add some discussion of how to create your own visitor. If there are abstract facilities in place for transforming ASTs, we should mention them.