Towards a Standard Library
Cry ‘Havoc!’, and let slip the dogs of war William Shakespeare
Standard Library
We define Scheme functions in three places: as special forms like let, in the primitive environment like the + operator, or within the body of an external Scheme program. The standard library is the third of these choices. Its functions are defined using building blocks of both primitive and special forms. If a function does not need a special evaluation strategy, or mapping to an internal operator, it belongs in the library. Successful programming languages will have a collection of functions that provide extensive capability and empower users to complete their tasks. When building a language, the standard library is often the first real “program” written in that language. When we write the library, we are not only providing the user with convenient shortcuts, but proving many features of the language work!
Our Standard Library
We build the standard library, test/stdlib_mod.scm with a multitude of functions. Importantly, we allow recursive functions, like fold and reduce which enable efficient functional programming.
Composing car and cdr into c({ad}^n)r
Our standard library defines functions that are combinations of car and cdr, for example cdar is define cdar (lambda (pair) (cdr (car pair)))). We can see these examples in the first defines of the standard library. For this to work, car and cdr must accept both quoted and unquoted lists. In other words, to chain these functions, they must accept S-Expressions without evaluating the arguments. This makes these functions specials forms.
In Eval.hs we add the special forms:
eval all@(List [Atom "cdr", List [Atom "quote", List (x:xs)]]) =
return $ List xs
eval all@(List [Atom "cdr", arg@(List (x:xs))]) =
case x of
Atom _ -> do val <- eval arg
eval $ List [Atom "cdr", val]
_ -> return $ List xs
eval all@(List [Atom "car", List [Atom "quote", List (x:xs)]]) =
return $ x
eval all@(List [Atom "car", arg@(List (x:xs))]) =
case x of
Atom _ -> do val <- eval arg
eval $ List [Atom "car", val]
_ -> return $ xThis feels like a hack, and if the cadr family of functions wasn’t so essential, we could drop car and cdr as special forms.
Running Standard Library
Eval.hs contains the functions that run text within the context of the standard library. Because the reader monad does not return the input context, we must wrap the expression and the standard library together as LispVals, then evaluate. This is done with the endOfList function.
Define the standard library file.
sTDLIB :: T.Text
sTDLIB = "lib/stdlib.scm" Parse the input function as an S-Expression, then the library file as a list of S-Expressions. Append the parsed input expression to the end of the list.
endOfList :: LispVal -> LispVal -> LispVal
endOfList (List x) expr = List $ x ++ [expr]
endOfList n _ = throw $ TypeMismatch "failure to get variable: " n
parseWithLib :: T.Text -> T.Text -> Either ParseError LispVal
parseWithLib std inp = do
stdlib <- readExprFile std
expr <- readExpr inp
return $ endOfList stdlib expr
getFileContents :: FilePath -> IO T.Text
getFileContents fname = do
exists <- doesFileExist fname
if exists then TIO.readFile fname else return "File does not exist."Final monadic evaluation of both standard library and expression. The key here is the evalBody, which accepts an S-Expression consisting of a series of define statements to be sequentially evaluated. This is the same evaluation strategy used in both let and lambda expressions.
textToEvalForm :: T.Text -> T.Text -> Eval LispVal
textToEvalForm std input = either (throw . PError . show ) evalBody $ parseWithLib std input
evalText :: T.Text -> IO () --REPL
evalText textExpr = do
stdlib <- getFileContents $ T.unpack sTDLIB
res <- runASTinEnv basicEnv $ textToEvalForm stdlib textExprConclusion
The standard library is the third and final place we define capability in our Scheme, after special forms and the primitive environment. The idea behind the standard library is that we have a relatively easy to write collection of utility and helper functions needed to get things done. If you look into the library, functions like reduce, fold and the cadr family are pretty useful.
However the e -> a functionality of ReaderT monadic action limits our approach. We cannot evaluate the file containing the library and get the modified environment back again. This somewhat complicates things, and requires us to take our approach via syntax manipulation. Although its not ideal, its also not very complex and lets us keep the simplistic lexical scoping via reader monad function local we established earlier. Alternatively, we can approach evaluation with StateT to run the monad, and get a modified state.
[ Understanding Check ]
Add a new standard library function to generate the first ‘n’ Fibonacci numberers using a recursive function.
Define a pair of co-recursive functions, even-co and odd-co, that determine if a number is even or odd, in the standard library. test/test_fix2.scm contains a standard library that defines a Y-combinator. However, when we set this as the standard library then run the commented out expression, our expression fails to terminate. Why is this?
Create a new primitive Vector data type. Modify the parser to read Vector as numbers between brackets. In Prim.hs put the basic operations like add, multiply, then in standard library put operation like dot production, l2-distance. Include an auto-quote facility for the Vectorspecial form.