Funktal is a functional programming language for the Uxn virtual machine, a tiny VM with 8-bit opcodes and 64 kB of memory. I have written about implementing functional constructs in Uxn’s native stack based assembly language Uxntal in a previous post.
Rationale
The main reason for creating Funktal was to see if it was possible to create a statically typed functional language with algebraic data types and function types that could run on the Uxn VM, with a compiler that could be implemented in Uxntal. This is motivated by the observation that most modern languages are very resource-intensive: typical projects take a lot of disk space, compilers are large and require a lot of CPU cycles and memory to compile code, and the programs themselves are also very often CPU- and memory-intensive.
Hard disks and solid-state drives are major contributors to the embodied carbon in a computer, followed by the CPU and memory. Reducing these resources is an important way to reduce CO₂ emissions from computing. The ability to write useful software for older generations of hardware allows to use them for longer, and that is the main way to reduce embodied carbon.
Funktal design principles
The main principle for the design of Funktal is that it should use as little memory as possible, both for the compiler and the programs it produces. This influences most of the design decisions. But at the same time, it should be minimally but fully featured: I want a pure, strict functional language, with a sufficiently expressive static type system. Also, I want the language to be simple to write easy code but expressive enough to write more complex code.
The main characteristics of Funktal are:
- It uses postfix notations (aka Reverse Polish Notation, Forth-style).
- It is entirely based on lambda functions (anonymous functions), but has named functions too.
- All variables are immutable (as they are lambda function arguments)
- The type system is based on primitive types and product and sum types and function types to create new types.
- Typing is optional, and therefore Funktal is not fully type safe.
- I/O is not pure.
There is a specification (aimed at people who want to program in Funktal) and a design document (aimed at people who want to help develop Funktal or are just curious), both still very much in flux.
Funktal by example
All examples can be found in the examples folder in the repo. To try them out, please see the README for installation instructions.
Basic syntax
Funktal is whitespace separated and consists of a number of blocks, the most important of which are types, constants, functions, and main. There are only expressions, so the entire main program is a single sequence of expressions. Newlines are only for readability and as comment delimiters: anything after a -- until a newline is considered a comment.
main {
6 7 * print -- prints 42
0x0a print -- prints a newline
"Hello" print -- prints Hello
}
Lambdas and named functions
Funktal is a functional language so the key building block is the lambda function (anonymous function). Each lambda is enclosed in parentheses and the arguments are listed between \ and ..
Lambdas do not need to have arguments. Because Funktal is a stack language, if there is anything on the stack, it will be used as argument for the functions. But arguments are often convenient.
main {
6 (\x. x x * x 2 * + x - print ) -- 42
6 (\x. 7 (\y . x y * print ) ) -- 42
2 84 `( / ) (\ x y div . y x div apply ) print -- 0x002a
}
The second example shows a nesting lambdas, with the x argument of the outer lambda in scope in the body of the nested lambda.
The last line is an example of quoting of functions: ( / ) is anonymous function without arguments which only performs a division. More fully we could write it as (\ x y . x y /). Normally, this function would be called right away. By quoting it with a backtick, it is not called until we call it explicitly using apply. The example also shows that functions can be passed as arguments to other functions.
Primitive types
Funktal has primitive types Int8, Int16, AChar, Byte and Short. Int is currently a synonym for Int16. AChar is an ASCII character; Byte is a raw byte value and Short a raw 2-byte value. The arrow <- in the type signature separates arguments and return type of a function. The colon : separates the argument from its type.
main {
6 (\ Int <- x : Int . x x * 2 x * + x - ) print
(\ Int8 . 6 (\ Int8 <- x : Int8 . x x * 2 x * + x - ) print )
0x2a 0x2b (\ Byte <- b1: Byte <- b2 : Byte . b1 b2 & ) print
}
Without type information, Funktal defaults to 16-bit operations. If you want to use 8-bit operations, explicit typing is necessary, as in the examples above. As shown in the second example, a lambda without arguments can still have an explicit return type.
Constants
Constants are a convenience. The main purpose is to define arrays of values (e.g. bitmaps) and strings, but scalars are also supported. There is a built-in type that is not strictly speaking primitive: Array, used to create array constants. Its constructor takes the type and number of the elements in the array.
constants {
hello : AChar 6 Array = "Hello!"
}
main {
hello print
}
Sum types and conditionals
As mentioned above, Funktal has algebraic data types. The Boolean type is an example of a sum type (similar to an enum): it has two alternatives, True and False. The example also shows the if builtin, which takes two quoted lambdas and a condition, i.e. any expression which returns True or False.
The Any type is the supertype of all types. Funktal does (currently) not have polymorphism. The Any type can be used explicitly and is also the type of any untyped expression. Because Funktal allows untyped expressions and does not do type inference (yet), it is not fully type safe.
types {
Bool = True | False
}
main {
True (\ Any <- cond : Bool .
cond
`( "true" print )
`( "false" print )
if
)
}
Product data type construction and pattern matching
This is an example of a record or product type. The RGB type is a triplet of 8-bit integers. The reason why the entire expression is wrapped in a typed lambda is that otherwise the integers would be treated as 16-bit. Funktal does not have proper type checking yet. The return type of a function determines the size of the operations and constants used in the function body.
types {
RGB = Int8 Int8 Int8 RGB
}
main {
(\ Int8 . 42 43 44 RGB (\ Int8 <- (r g b RGB) : RGB . r ) ) print
}
Recursion
Funktal does not have mutable variables so it has no loops. Instead, it uses recursion.
Factorial with named functions
This is a straightforward recursion to calculate a factorial: if b==e then return the result r else recurse with the counter b+1 and the accumulator r*b. This is a tail recursion. It also demonstrates the use if named functions, and Funktal’s natural ability to support point-free programming.
function {
fact = ( 1 1 fact_rec )
fact_rec = (\ Int <- e : Int <- b : Int <- r : Int . b e == `( r e * ) `( e b 1 + r b * fact_rec) if )
}
main {
5 fact 1 * print
}
I use an actual recursive function fact_rec and a wrapper to initialise the counter and the accumulator.
Recursion without named functions
Recursion means a function calls itself. But what if the function doesn’t have a name? A fixed-point combinator allows to do recursion on unnamed functions. The most common one is the Y-combinator. The way I’ve done this here is a bit different, but equivalent. The quoted function describes the recursion. But because that function has no name, it can’t call itself. The function (\f. f f apply) takes it as its argument, so now it has a name and can be called recursively.
main {
5
`(\ n <- f . n 1 == `(1) `( n 1 - f f apply n * ) if)
(\ Int <- f : Any . f f apply ) print
}
Example 8: factorial with fixed-point
Lists and fold
Algebraic data types can also be used to construct lists, like this:
types {
List = List Any Cons | Nil
}
This is a recursive type, a List is either a function Cons with takes a List and some value, or a function Nil which takes no arguments. So we can build lists by writing e.g.
Nil 11 Cons 22 Cons 33 Cons
In practice, it is handy to have a function to generate a range of numbers (range below) and list manipulation functions like head, tail, fold and map. The example shows the use of range and fold to calculate a factorial by multiplying all values in a list.
functions {
-- First element of a list
head = (\ Any <- (xs x Cons) . x )
-- The rest of the list
tail = (\ List <- (xs x Cons) . xs )
-- Creates a list with a range of integers
range = ( Nil range_rec )
range_rec = (\List <- b: Int <- e: Int <- lst : List . b e == `( lst e Cons ) `( b 1 + e lst b Cons range_rec ) if )
-- A reduction: fold takes a list, an accumulator and a function and combines all elements of the list into the accumulator
fold = (\ Any <- lst : List <- acc : Any <- f : Any . lst `Nil is `( acc ) `( lst tail acc lst head f apply f fold ) if )
}
main {
(\Int . 1 5 range 1 `( * ) fold ) print
}
Implementation
The Funktal compiler should be implementable in Uxntal (or even Funktal) and run on Uxn. I did not feel I was sufficiently fluent in Uxntal to use it as the implementation language. Instead, I opted to write the compiler in Fortran, but in such a way that porting to Uxntal should be straightforward.
Why Fortran? Funktal is essentially an art project; using Fortran is a statement. I could have done this in C, but I prefer Fortran’s arrays. I am using Fortran-90 but with a very restricted feature set. In case you don’t know Fortran, here are some of its characteristics:
- No lexical scoping
- Numeric labels for
goto; nobreak - Arrays starting by default at 1 but can start at any integer value
- No unsigned integers
- No native hash tables
- Implicit typing based on the first letter of the variable name (*)
(*) But luckily you can disable that feature in Fortran-90
Furthermore, because of the restricted subset I use:
- No pointers so no native linked lists
- No derived types, so no structs
- No dynamic allocation
It is almost as if I’d have taken the “Real Programmers Don’t Use PASCAL” essay too literally:
LANGUAGES
The easiest way to tell a Real Programmer from the crowd is by the programming language he (or she) uses. Real Programmers use FORTRAN. […]Real Programmers do List Processing in FORTRAN Real Programmers do String Manipulation in FORTRAN. [...] If you can't do it in FORTRAN, do it in assembly language. If you can't do it in assembly language, it isn't worth doing.
STRUCTURED PROGRAMMING
[…] Some quick observations on Real Programmers and Structured Programming:Real Programmers aren't afraid to use GOTO's. [...][…]. As all Real Programmers know, the only useful data structure is the Array. Strings, lists, structures, sets – these are all special cases of arrays and can be treated that way just as easily without messing up your programming language with all sorts of complications. […]
Be that as it may, this restricted subset maps cleanly to Uxntal, and also forces me to think very carefully about data structures. As a result, the compiler in its current states about 5,000 lines of code, allocates less than 64 kB and compiles to an executable of about 100 kB. For reference, uxnasm is 20 kB, uxncli is 25 kB and uxnemu is 50 kB. But gcc and gfortran are 1.2 MB and rustc is 15 MB.
Status
Funktal needs a lot more work (compilers are never finished), but it is now in a state that most of the Uxn demo applications can be ported to it. It already supports devices and state, as explained in the follow-on post. At the top of my long wish list is library support and memory management.
Apart from that, there are plenty of bugs and shortcomings that need fixing. But it is already good enough to have some fun with, which is of course the main purpose.
The banner picture shows a wooden telephone in a temple in Kyoto