Skip to content

Scala implementation of SIMPLE outlined in "Understanding Computation" by Tom Stuart

Notifications You must be signed in to change notification settings

alephoverflow/SIMPLEScala

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

23 Commits
 
 
 
 
 
 
 
 

Repository files navigation

A Scala implementation of the toy programming language, SIMPLE, outlined in "Understanding Computation" by Tom Stuart.

The implementation does not include a text -> abstract representation parser.

This code includes a Machine that takes a abstract program structure, and executes / "reduces" the program. The program is a tree of SIMPLE constructs, where the nodes are: statements, sequences, if/else, while loop, expressions, each potentially possessing a recursive substructure. The terminal nodes / leaves include (integer and boolean) are primitives, and are not reducible. All other nodes are reducible: their subtree can be recursively reduced, until finally the node itself reduces to a primitive.

Variables reduce to a value defined in the current environment, by looking up the value of the variable.

Statements are impure, expressions are pure. The former potentially modifies the environment.

The reduction should be viewed as being iterative rather than recursive because each Machine Step performs a "small-step" reduction, reducing the innermost non-primitive construct. The alternative is "big-step", where a reduction of a node, will recursively reduce all it's descendents in one Machine step.

About

Scala implementation of SIMPLE outlined in "Understanding Computation" by Tom Stuart

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages