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 viasubstPredefinedConstants - Substitute all predefined functions in the program via
substPredefinedFns - Initialises array containing the first step (original program)
- Runs
reduceMainrepeatedly 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 skipping feature.
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.
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[][]]
Replaces all occurrences of a declared constant or function with their value or body, respectively. It is called directly in substPredefinedConstants and apply, indirectly in substPredefinedFns (through reduceMain), and in reduceMain when functions or constant declarations are evaluated.
substituteMain takes in 4 parameters:
-
name: the identifier that is to be replaced (e.g.math_PI) -
replacement: the expression that is to replace the identifier (e.g. 3.141592653589793); the replacement must be of typeirreducibleNodesand thus can't encapsulate an arbitrary expression. -
target: the part of the program in which the replacement takes place; it can be a program or a function -
paths: the path to the target node
substituteMain serves as a wrapper function for substitute to recurse down the target node and replace all occurrences of a name with its replacement. It houses the substituters array containing functions that are responsible for the recursion and substitution, as well as a mapper seenBefore which is re-initialized every time substituteMain is called (therefore, it only keeps track of the targets recorded 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 thus 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
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 reduce to recurse down the given program and perform the reduction. It houses the reducer array that contains functions which are in charge of the recursion and reduction, as well as the bodify and explain functions that are responsible for 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[]
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 the finders array that contains finders which recurse through the target to find free names. Also like substituteMain, it has a mapper seenBefore 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
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 theparamName -
freeTarget: free names in thetarget, as an array of strings -
freeReplacement: free names in thereplacement, as an array of strings -
boundTarget: bound names in thetarget, as an array ofes.Identifiers -
boundUpperScope: bound names in the upper scope, eg in nested functions, as an array of strings -
boundReplacement: bound names in thereplacement, as an array ofes.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 as to ensure that the new name is fresh. Without the while loop, the variable may be renamed to a non-fresh name; e.g. 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.
Used internally and is called in FunctionDeclaration, FunctionExpression, BlockStatement, BlockExpression and ArrowFunctionExpression substituters to find and return all bound names in functions, which include names of constants or variables, parameter names, and nested function names as an es.Identifier array.
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.
Takes in a parsed program and recursively removes all instances of debugger statements. It does so by repeatedly calling the internal helper function remove to detect and filter out statements of type DebuggerStatement in the programme. The operation terminates once all debugger statements are removed, returning the then filtered programme.
In order to visualize the desired content, console.log(itemYouWantToSee); can be added to the code. Then use Inspect elements in your browser to see the content. (The content should show up after you click Run in the local source academy.)
Common things you may want to observe are: reduction steps (added in function getEvaluationSteps), AST of Program (added in reduceMain), markers (for checking if the execution reaches that certain branch)
You may want to add console.log("somecontent") in the code during debugging to help you better visualize how the stepper runs.
The following figures are some basic examples.
We add the line console.log("Block statement encountered!") to see whether the program have block statement.
We can see that the log message is shown on the right, meaning that this line is executed when running the stepper program. This means the block statement written in source academy is detected by the stepper during reduction.
-
ast.blockExpression([reduced as es.Statement,...(otherStatements as es.Statement[])])You need to put the statement array as the argument, hence type casting to es.Statement and es.Statement[] is necessary in this case. The result is the joining of those two parts together as a new block expression. -
ast.program([ast.expressionStatement(ast.identifier('undefined'))])ast.programfunction takes in an array of statements as an argument;ast.expressionStatementfunction takes in the actual content of the statement. Hence, this example refers to"undefined;"as a program string.
- ES Tree
- AST Tree
(These two extra materials are strongly recommended since crafting a valid piece of program requires a deep understanding of them.)
Zhao Jingjing @zhaojj2209
Niklas Forsström @NiklasOPF
Zachary Chua @Zacchua
Peter Jung @petermonky
Feng Yilong @FYL2003
Hans Delano @hanscau