So, one of my favorite pasttimes is language design, and a few weeks ago I whipped up the following grammar for a purely functional, typeless language, which consistes solely of lambdas and symbols. It's essentially the \(\lambda\)-calculus, with global, immutable binds (much like substituting a symbol).
Anyways, here's the grammar:
lam ::= (\ var1 ... varn :: exp) exp ::= lam | var | (prim exp1 ... expn) | (exp1 ... expn) prim ::= #bind | #halt
Aside from the grammar, comments are defined with double slashes and run to the end of the line, C++/Java style.
The two primitives have the following meaning:
(#bind sym val) => binds sym to val in the global symbol table (#halt exp) => evaluates exp and returns that value to the calling context (OS level) as a string
As I mentioned, it's small. Masochistically small, it appears. There's also absolutely no concept of I/O aside from return values. But it fully supports the \(\lambda\)-calculus, and therefore is Turing complete.
However, in implementation, a few things would be pre-bound to make the programmer's life simpler. These would not be part of the grammar, and therefore not a part of the syntax of the language, as they would be stored like any other bound symbol internally. There would be one exception to these pre-bound values, and that's the storage of numbers. Church numerals would be auto-converted on the fly, and then cached into the global bind table.
Semantically speaking, functions would be evaluated identically to the \(\lambda\)-calculus. Also, the interpreter would perform automated currying internally.
(\ a b :: b a) => (\ a :: (\ b :: b a)) (\ a b :: b a) someval => (\ a :: (\ b :: b a)) someval => (\ b :: b someval)
Here's an example program in this small language, which I'd like to call axio:
// fibonacci generator // supporting functions (#bind succ (\ w y x :: y (w y x))) (#bind + (\ a b :: a succ b)) (#bind phi (\ a b f :: f a b)) (#bind sigma (\ x :: phi (x false) (+ (x true) (x false)))) (#bind fib (\ n :: (n sigma (phi 0 1)) false)) // fib (fib (fib 5)) // exit (#halt)
This would calculate the 5th Fibonacci number, let's call it f_5, and then would calculate the f_5th Fibonacci number.
There really isn't much purpose to this language, especially given the complete lack of I/O, other than it may be a neat challenge to implement, and an excuse to write a state-machine interpreter.
Ah well, that's axio.
Thanks for reading!