-
Notifications
You must be signed in to change notification settings - Fork 104
Stepper
The stepper is a tool that allows for a better understanding of the substitution model by displaying the program’s evaluation steps.
To use the stepper in a REPL, you can run the repl with subst as its last command line argument:
cd js-slang
yarn build && node dist/repl/repl.js 1 substThe stepper’s “main” function, getEvaluationSteps takes in a parsed program along with its context, and returns an array that shows the detailed evaluation of the program. The structure of the steps array is as follows:
- First step - Start of evaluation
- Even-numbered steps - shows the program before the next evaluation is executed, with a path leading to the part of the program that will be evaluated next
- Odd-numbered steps - shows the program after evaluation has been executed, with path(s) leading to the part(s) of the program that have been evaluated
- Last step - Evaluation complete
Each element of the step contains:
- The current state of the program at this particular step of the evaluation
- An array of path(s) leading to the part(s) of the program that will be evaluated next (even-numbered steps) / has been evaluated (odd-numbered steps)
- A string that explains the evaluation taking place
How getEvaluationSteps works:
- Initialises array to store the steps generated
- Replaces all predefined constants (such as math_PI) in the program with their corresponding value via substPredefinedConstants
- Substitute all predefined functions in the program via substPredefinedFns
- Initialises array containing the first step (original program)
- Runs reduceMain repeatedly on the program (which basically means doing repeated one step evaluations) and generates the subsequent steps
- If steps count hits 999, push in “Maximum number of steps exceeded” as the 1000th step If error occurred, terminate and return the steps array early
- Once program has completed evaluation (length of program reaches 0), set string of last step to be “Evaluation complete” and returns the steps array
Calls generate on the node after treeifying it. Called mainly in test suites and in other stepper helper functions. Can consider replacing it with redexify completely as future work.
Calls generate on the program and redex after pathifying it. Called in the js-slang index runInContext function to convert every element of the steps array generated from getEvaluationSteps into an array containing two strings. This array of array of strings is then sent to the frontend stepper component.
Takes in a substituterNode, and paths to the redex. Returns the redex as an AST. exported to src/index.ts and used in runInContext function.
Exported to src/index.ts and used in runInContext function. Takes in output from getRedex and checks if it the redex is a CallExpression, returning the CallExpression’s callee if it is or undefined otherwise. Used to pass the functions of steps that reduce CallExpressions to the frontend for use in the jumping feature.
substPredefinedConstants uses an array, mathConstants, that contains all predefined mathematical constants. Each entry of this array is of the form [name, value] - where "name" is the name of the constant (e.g. math_PI) & "value" is the corresponding value (e.g. 3.141592653589793). The method takes in a parsed program, loops through all elements of mathConstants and replaces all occurrences of the name in the program with the associated value via substituteMain.
substPredefinedFns takes in a parsed program as well as the program context, then substitutes all predefined functions in the given context (e.g. append, map in Source 2) into the program. It does so by parsing the list of prelude programs from the context, concatenating it to the original program, then running reduceMain repeatedly on this combined program until its length is equal to that of the original program (that is, all of the predefined functions have been substituted).
substituteMain(name: es.Identifier, replacement: irreducibleNodes, target: substituterNodes, paths: string[][]): [substituterNodes, string[][]]
This function replaces all occurrences of a declared constant or function with its value/body. It is called directly in substPredefinedConstants and apply, indirectly in substPredefinedFns (through reduceMain), and in reduceMain when function or constant declarations are evaluated.
It takes in 4 parameters:
- Name: the identifier we are looking to replace (e.g. math_PI)
- Replacement: the expression we would like to replace the identifier with (e.g. 3.14). Note that the replacement needs to be of the type irreducibleNodes. We therefore can't replace something with an arbitrary expression.
- Target: the part of the program where we want to do the replacement; it can be a program or a function
- Paths: the path to the target node
substituteMain serves as a wrapper function for the substitute function to recurse down the target node and replace all occurrences of the name with its replacement. It houses the substituters array containing functions which are responsible for the recursion and substitution, and also contains a map seenBefore which is re-initialized every time substituteMain is called (therefore, it only keeps track of the targets seen within each call of substituteMain). Due to the potential of creating infinite loops from calling substitute recursively, seenBefore is used to keep track of what targets have been seen before and therefore ensures that every node is only evaluated once.
Additionally, substituteMain keeps track of all of the paths to every node of the target, and returns every path leading to the substitution (there can be more than one substitution in the target node). The substituters, while recursing down the target, are also in charge of branching out the paths by calling the branch helper function, and building the paths. Once the identifier has been found, an end marker is pushed into the path array to signify that the particular path is one leading to the identifier. Once the whole node has been traversed, substituteMain will return the paths with the end markers along with the substituted program.
Finds the appropriate substituter function corresponding to the target’s type, and calls it on the provided target.
apply(callee: es.FunctionExpression | es.ArrowFunctionExpression, args: irreducibleNodes[]): BlockExpression | es.Expression
This function is called in reduceMain when a call expression is evaluated. It replaces the call expression with the body of the callee (a function expression), and the body will have its parameters substituted with the supplied arguments.
reduceMain(node: substituterNodes, context: Context): [substituterNodes, Context, string[][], string]
reduceMain takes in a parsed program along with its context, and performs a one-step evaluation to it. Repeated application of this function will therefore cause the program to fully evaluate. At the same time, it also returns the path(s) leading to the part(s) of the program that has been reduced, along with a string that explains the reduction. If substitution is not involved, only one path will be returned; if substitution is involved, the first path in the array points to the constant/function declaration that is evaluated, and subsequent path(s) point to parts of the remaining program that were substituted post-evaluation.
Like substituteMain, reduceMain serves as a wrapper function to allow the reduce function to recurse down the given program and perform the reduction. It houses the reducer array of functions that are in charge of the recursion and reduction, as well as the bodify and explain functions that are in charge of generating the explanation string. The reducers are also in charge of building the path(s) leading to the reduction, and returning said path(s); once the reduction is found, explain is called on the corresponding node to generate the explanation string.
reduce(node: substituterNodes, context: Context, paths: string[][]): [substituterNodes, Context, string[][], string]
Finds the appropriate reducer function corresponding to the node’s type, and calls it on the provided node.
Generates the appropriate explanation string based on the target’s type, calling bodify if necessary.
Converts any parts of the code referenced in the explanation of the reduction into a string. A boolean verbose is introduced to shorten arrow function expressions that are more than two levels deep, in order to keep the explanation string short.
Combs through the given parsed program (which is in the form of an abstract syntax tree, or AST) and trims it so that it can later be converted into a string using the astring module’s generate function. Like the other Main functions, it stores an array of treeifiers that is called by treeify to recurse down the AST.
The core of treeifyMain lies in the treeifiers for the types FunctionExpression and ArrowFunctionExpression. Due to the potential for the AST to contain cycles after substitution (e.g. in the event of two arrow functions each calling the other), calling generate directly may result in infinite text generation. Hence, the two treeifiers are in charge of stopping this infinite text generation by substituting the function body with “...” after 5 iterations (this count is stored in treeifyMain as verboseCount).
Finds the appropriate treeifier function corresponding to the target’s type, and calls it on the provided target.
Uses the given path(s) to trace down the given program, find the point of reduction (the redex), and extract it from the program, leaving a position marker in its place. treeifyMain is called on all other parts of the program that are not on the path. The modified program and the redex are then returned separately. Structure similar to treeifyMain.
Finds the appropriate pathifier function corresponding to the target’s type, and calls it on the provided target. If more than one path is given, pathify is run more than once, each tracing a different path.
findMain(target: es.FunctionExpression | es.ArrowFunctionExpression | es.BlockStatement | es.FunctionDeclaration| BlockExpression ) : string[]
findMain finds and returns the free names in the target passed in. It is used internally and called in substituteMain, specifically in the FunctionDeclaration, FunctionExpression, BlockStatement, BlockExpression and ArrowFunctionExpression substituters. Like other Main functions, it houses an array of finders which recurse through the target to find the free names. Also like substituteMain, it has a seenBefore map which reinitialises each time findMain is called to ensure that each node is only searched once.
getFreshName(paramName: string, counter: number, freeTarget: string[], freeReplacement: string[], boundTarget: es.Identifier[], boundUpperScope: string[], boundReplacement: es.Identifier[]): string
getFreshName is used internally and called in FunctionDeclaration, FunctionExpression, BlockStatement, BlockExpression and ArrowFunctionExpression substituters, when substitution results in variable capture. It renames the variable that would capture it to a fresh name, meaning that the name does not occur in the target or replacement, be it as a free or bound name.
Renaming occurs by renaming paramName to paramName + “_” + counter. If there are any name clashes, counter would be incremented.
getFreshName takes in 7 parameters
- paramName: the name of the parameter to be renamed
- counter: the number appended to the paramName
- freeTarget: free names in the target, as an array of strings
- freeReplacement: free names in the replacement, as an array of strings
- boundTarget: bound names in the target, as an array of es.Identifiers
- boundUpperScope: bound names in the upper scope, eg in nested functions, as an array of strings
- boundReplacement: bound names in the replacement, as an array of es.Identifiers
getFreshName checks the free names in the target, replacement, bound names in the target, replacement, and upper scope, in a while loop, until no more renaming occurs. Without the while loop, the variable may be renamed to a non-fresh name. Eg. the variable x does not have the same name as any of the names in the target, but has the same name as a bound name in the replacement. Then x would be renamed to x_1. But if the name x_1 occurs in the target, then x_1 would be a non-fresh name. Without the while loop, the names in the target would not be checked again, renaming x to a non-fresh name.
scanOutBoundNames is used internally and is called in FunctionDeclaration, FunctionExpression, and ArrowFunctionExpression substituters to find and return the all bound names in functions, which include names of constants or variables, parameter names, and nested function names as an es.Identifier array.
scanOutDeclarations is used internally and called in BlockStatement and BlockExpression substituters. Similar to scanOutBoundNames, it finds and returns all declarations, which are names of variables, and names of functions declared within the node’s body. However unlike scanOutBoundNames, it does not find and return parameters of functions declared within the node’s body.
Zhao Jingjing @zhaojj2209
Niklas Forsström @NiklasOPF
Zachary Chua @Zacchua
Peter Jung @petermonky