A Functional Programming Language Interpreter written in Python and C. The fundamental idea of this language is to express the functional nature of the language, as every function is a λ
expression bound to an identifier. The language is weakly-typed and borrow many features of the Scheme Language.
Download the interpreter to play around with the language on Windows and Linux, or use the online limited interactive mode at https://mustartt.github.io/interpreter-demo/.
> interp_win_v0_1.exe <filename.lang>
$ interp_lin_v0_1 <filename.lang>
Note: Windows Binaries may not work with Windows Defender https://github.com/mustartt/functional-interpreter/releases
The project can be built with pyinstaller
into a binary executable with the following commands
make build
the built binaries is found in the folder ./interpreter/dist/main/
.
A basic variable declaration is as follows
bind <identifier> (to|as|=|->) <value>
the bind
keyword binds the variable's identifier
to the value
using any of the keyword to
, as
, =
, and ->
.
There are 5 basic literal types in the language: num
, float
, string
, list
, and struct
.
bind pi to 3.1415926
bind num to 1234
bind str to "Hello World!"
bind array to list(1 2 3 4 5 6 7 8 9)
The language implement most syntax and features from Lambda Calculus. A λ
expression in Lambda Calculus, such as the identity function
λx. x
can be defined as
lambda({x} -> x)
a λ
expression with mulitple parameters x
and y
and a function f
, in lambda calculus λxy. f(x y)
can be expressed as
lambda({x y} -> f(x y))
In the language, []
and {}
are interchangable for better readability in λ
expressions.
> (lambda({x} -> x))(5)
5
> (lambda({x y} -> +(x y)))(2 3)
5
> {(lambda({x} -> lambda({y} -> +(x y))))(1)}(4)
5
In the language, all functions are a function_identifier
bound to a λ
expression using the bind
keyword as follows.
bind <function_identifier> (as|to|=|->) lambda({p_1 ... p_n} -> expression);
The function_identifier
can contain all alphanumeric characters except keywords. All expressions should be postfixed by a ;
to indicate a seperate line.
# add(x y) calculates the sum of two numbers
# add: Num Num -> Num
bind add to lambda({x y} -> +(x y));
# !(n) calculates the n!
# !: Nat -> Nat
bind ! to lambda({x} ->
if(<=(x 1)
1
*(x !(-(x 1)))));
and these functions can be called as
> add(2 3)
3
> !(5)
120
Comparison in the language can produce boolean values True
and False
, and decisions can be performed based on the result using the if
function.
if(condition exp_true exp_false)
Use and
, or
, and not
to combined logical result.
One can define local definitions and mulitple subsequent routine in functions using the keyword local
. The syntax is
local((def_1) ... (def_n) exp)
Note: In the global scope, the keyword bind
does not require ()
around it, but in local definitions, ()
are required around binding to ensure that they are seperate parameters as bind(<indentifier> (to|as|=|->) <expressioin>)
.
The language implements scope, which means that local definitions can share same names as definitions from outer scopes.
# add(x y u v) calculates the sum of the four num x y u v
# add: Num Num Num Num -> Num
bind add to lambda({x y u v} ->
local(
bind(sum1 to +(x y))
bind(sum2 to +(u v))
+(sum1 sum2)));
> add(1 2 3 4)
10
TODO: Document syntax
TODO: Document syntax
TODO: To be implemented
The standard library is included under lang
which include files with basic useful functions
Provides the basic higher order function map
, filter
, and reduce
.
$ cat ./lang/higher-order.lang
# map(f lst) maps the function f to every element of lst
# map: (X -> Y) (listof X) -> (listof Y)
bind map to lambda({f lst} ->
if(empty?(lst)
list()
cons(f(car(lst))
map(f cdr(lst)))));
...
Provides some list functions such as quicksort
, length
, and list-ref
.
$ cat ./lang/collections.lang
# quicksort(pred lst) performs quicksort on lst with pred
# quicksort: (X X -> Bool) (listof X) -> (listof X)
bind quicksort to lambda({pred lst} ->
if(empty?(lst)
list()
local(
bind(pivot to car(lst))
bind(less to filter(lambda({x} -> pred(x pivot)) cdr(lst)))
bind(great to filter(lambda({x} -> not(pred(x pivot))) cdr(lst)))
append(
append(
quicksort(pred less)
list(pivot))
quicksort(pred great)))));
...