Functional, Algebraic, and Interpreted language
Which is abbreviated to FAI (pronounced fī) or FAI lang.
Over the past while, I've been creating my own language, and while it's certainly not complete by any means, it's ready for a showcase and first draft specification.
Many people have said that we need to make CS more ingrained in math education, but people generally haven't provided any seamless solutions. Rather than integrating CS with math, these proposals tend to just teach CS and math side-by-side. That's better than nothing, but it's not good enough. To truly teach them together, you need a language that looks so much like algebra that students can use it intuitively without much thought. That's where FAI comes in. It strives to be a purely functional language with algebraic syntax. While it has features not commonly found in algebra (like string manipulation), the core principle is to provide a high-level language that looks and acts like algebra, just with a heavy emphasis on functions.
It can't solve equations for you. That's not the point. If you want something to solve equations for you, use a calculator. FAI allows you to implement your own derivations as functions, and call them as necessary. For example:
plus_minus(a, b) = (a+b | a-b) quadratic(a, b, c) = plus_minus(-b, sqrt((b^2)-(4*a*c)))/(2*a)
And then insert \(x^2-3x+2=0\)
quadratic(1, -3, 2) > (2 | 1)
And it returns the roots: 2 and 1. Don't worry about the syntax the roots were returned in for now, just know that both 2 and 1 were returned by the quadratic function.
FAI is also purely functional, making it great for teaching the functional programming concepts which are applicable in almost every high-level field. lambda exists in a readable format, and is used as any other function. In fact, all built-in functions are simply lambdas with external definitions that have been attached to a name:
quadratic > lambda(a, b, c: <expression>) sqrt > lambda(a: <external>)
This allows for usage of higher-order functions, like so:
combine_three(a, b, c, func)=func(func(a,b),c) combine_three(1, 2, 3, lambda(a, b: a + b)) > 6
This can also teach about recursion, using a piecewise-like syntax for the conditions:
factorial(x)={x<=1: 1; x * factorial(x-1)} factorial(5) > 120
There exist other more semantically relevant features, but not ones that get in the way of the core purpose of the language, which is to serve as a link between programming and algebra.
Features and WIP Specification
The following is a detailed list of current language features at the time of writing. If you aren't interested in this, scroll down a lot to find information on the future of this language.
Scope in FAI is slightly confusing, though it has been designed to keep the purely functional aspect of the language where a function may only use its own arguments.
The following are both global definitions, but they do very different things:
var_name = 10 func_name() = 10
The first is called an outer argument, while the second is a global function. The scope of an outer argument is restricted to the outermost scope, while the scope of a global function extends to everywhere. For example:
x = 10 f1(a) = a + 1 f1(x) // Using an outer argument in the outer scope works > 11 f2(a) = x + a // Oops! Can't use an outer argument inside a function f2(1) > InvalidName: The name x is neither a named function nor an argument. f3(a) = f1(a) + 1 // Using a global function in a function is okay though f3(10) > 12
This means that these two lines technically act differently:
f(x) = x+1 // Can be used anywhere l = lambda(x: x + 1) // Can only be used in the outer scope
A function may only access its arguments and any globally defined function. All functions also have access to self, which is always defined to be the lambda of the function being called, except in the outer scope. While this would mostly be used for lambda recursion, technically any function has access to its self.
A call is anything directly evaluated by the REPL. However, because expressions have fairly intuitive evaluation, this part will be exclusively focused on non-expression calls.
The syntax for declaring a global function is:
fname(arg1, arg2, arg3, ... argn) = <expression>
The syntax for declaring an outer argument is:
Certain recursive functions can take a long time to execute. For example, the following call can take 5 seconds to execute:
fibo(x) = {x <= 2: 1; fibo(x-1) + fibo(x-2)} fibo(32) // This is REALLY slow > 2178309
However, it can be sped up through a trick called memoization. In many languages you would have to implement this yourself, but FAI will memoize functions for you if you add the keyword memo before the function definition.
memo fibo(x) = {x <= 2: 1; fibo(x-1) + fibo(x-2)} fibo(400) // Lightning fast. If it wasn't memoized, it would longer than the heat death of the universe to finish. > 1.76023680645014E+83
Attempting to redefine a name in the outer scope will throw an error without the update keyword.
x = 10 f(x) = x + 1 f(x) > 11 x = 5 // Can't do this! > DefineFailed: The update keyword is required to change the definition of a function or outer argument. update f(x) = x + 2 // This is okay though. f(x) > 12
Because FAI is lazily evaluated, it can break memoization if a memoized function relied on a now updated function. To fix this, the update keyword may also be used in conjunction with memo to refresh the memoization of a function, or when used on a non-memoized function, it can change that function to be memoized:
g(x) = 1 memo f(x) = g(x) f(2) > 1 update g(x) = x f(2) // Oops! Memoization stored a value wrong! > 1 update memo f f(2) // There we go. > 2
Calls may be terminated with either an EOF or ;.
All types support = and ~= as "equals" and "not equals," which both return booleans. The one exception is unions, which handle those operators in the same special form that they handle all other operators.
FAI numbers are complex. The literal may contain a single optional decimal point as well as an i at the end for imaginary values. While they may be represented in a complex form like 4+2i, keep in mind that that form is really just an addition of 4 and 2i. +, -, *, /, and ^ operators are legal. - may also be used as a prefix (e.g. -10) to negate the value of a number. The comparison operators >, <, >=, and <= are unique to numbers, and unlike the other numerical operators, they return booleans. It should be noted that comparing the values of complex numbers with imaginary components is impossible in algebra, which is discussed in the challenges section of this post lower down.
In FAI, booleans act as one might expect. They can be either true or false. + serves as the boolean "or" operator and * serves as the boolean "and" operator, with the ~ prefix being "not." Booleans are the only type for which all operators and prefixes used on it will return the same type.
FAI strings are currently barely working and should not be used. However, they do support + for concatenation, and use the "str" literal. You know what, don’t even try to use strings. They’re so broken in this version.
"Lambda" will often be used interchangeably with "function" in FAI, as any lambda is also a function and any function is also a lambda. Lambdas only support the call syntax, which is a special form postfix notation.
Unions really deserve their own category. The point of a union is to be multiple values in a single object. For example, the quadratic function should return up to two numbers, even though it can only return one thing. To solve this, it returns a union of both valid answers. This union may only be manipulated as if it were a single value. Unions may only contain distinct values, and if a union only has one distinct value, it dissolves into that one value. Unions also may not be nested, and any nested union will be automatically flattened upon evaluation. They are defined using the union literal (val1 | val2 | val3 | ... | valn).
For if, else, and cond, FAI has piecewise expressions. The syntax is as such: {cond1: <expr1>; cond2: <expr2>; cond3: <expr3>; ...; condn: <exprn>; <exprelse>}
A lambda expression may also be known of as an anonymous function. It allows you to create a function as an object rather than as a definition, which can be extremely powerful in many different use cases. Other than piecewise expressions, the lambda expression probably has the most special form of any expression in the language: lambda(arg1, arg2, arg3, …, argn: <expression>)
Challenges and Future Goals
Currently, large amounts of recursion will result in a stack overflow. I'll need to restructure the functional call stack to operate iteratively in the future.
Currently, non-real numbers are compared by using their magnitudes. However, this means that (5+2i) >= (5-2i) is true, and even worse, (5+2i) >= (-5+2i) is also true. A possible fix would be to throw an error when comparing non-real numbers, but I would rather not do that if possible.
The common algebraic syntax 2x and 2(x) are not legal. They should be. However, making them legal would require a moderate reworking of how expressions are parsed.
Algebra has a single-argument pipeline syntax called composition (e.g. \(f \circ g(x)\)) that should be added. However, finding a suitable replacement for ∘ may be tricky given that o can be used in names and * is used for multiplication. . may work.
I'm currently debating over whether I should add vectors and matrices. I have a syntax figured out for them, but I'm not sure I want them to be part of the language.
What should happen if part of a union throws an error?
Should a null-like type be introduced? There are benefits from a language perspective, but it's not terribly algebraic.
A function should be able to take in a variable number of arguments, though a syntax and data structure to handle that is tricky to decide on.
Bugs and currently unimplemented features
Order of operations is not necessarily obeyed.
String indexing successfully parses, but has not yet been implemented.
The REPL only has support for one-line calls, despite multi-line calls being fully parseable.
Extraneous content at the end of an call will sometimes parse even though it's not legal code.
Complex math, especially regarding exponents and sqrt, may result in near-zero imaginary errors. These errors could cause major issues with comparison operators, and these forms are just generally less readable.
Lambda expressions should be memoizable.
= and ~= do not work with lambdas. They should.
Unions should not ever be directly transferred as arguments, even in user-defined functions. They should always be run separately and then reunified, like for external functions.
Strings are just completely broken right now and need to be fixed.
How to use the FAI REPL program
Download and unpack the FAI REPL.
Install the .NET Core 2 runtime.
Run dotnet FAIrepl.dll in the unpacked folder using whatever your system's command line is.
