Felix - a fast scripting language
felix-lang.org
felix-lang.org
$ time lua empty.lua
real 0m0.005s
user 0m0.002s
sys 0m0.002s
$ time ./luajit empty.lua
real 0m0.005s
user 0m0.001s
sys 0m0.002s
# generates a typical set of Pick 6 lottery numbers
x[⍋x←6?40]
# finds all prime numbers from 1 to R
(~R∊R∘.×R)/R←1↓⍳R
# game of life
life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
[1] I guess it should be faster than hand-written C, which is, of course, possible. ATS supposedly generates C code which is very competitive.
For some strange reason, certain misconceptions in CS/programming have half-lives measured in several decades, such as this annoying distinction between interpreters/VMs/compiled languages. We're at least 20 years out from interpreters being meaningfully distinct from VMs and compiled languages.
Compiled languages generally don't support eval. That's a pretty meaningful difference.
Python is compiled to bytecode. It supports eval. So does Smalltalk. Lua would fall into this category as well, and a whole bunch of others. I don't think "compiled" means what you think it means anymore, which is my whole point.
See my other reply (http://news.ycombinator.com/item?id=5012218). "Compiled language" is an informal term that usually means "to machine code." If you take it to mean "compiles to any kind of IR at all," then basically all languages are compiled and the term is meaningless. But that's not how the term is generally used -- for example, see the Wikipedia article (http://en.wikipedia.org/wiki/Compiled_language).
There is a real difference between languages that can meaningfully be compiled directly to machine code and those that can only JIT-compile type-specialized traces/functions (with guards that fall back to the interpreter if the assumptions do not hold).
That's my point. It's a misnomer. It's the same thing as calling technology with the ability to parse context free grammars "regexes." It's a common usage that pollutes the precise meaning of technical terms. (And at the same time, generates misconceptions based on those technical terms.)
> There is a real difference between languages that can meaningfully be compiled directly to machine code and those that can only JIT-compile type-specialized traces/functions
Well, not so much as you'd think. In theory, the ability to do things like eval cuts off a lot of direct compilation to machine code, but in practice, we know this isn't necessarily true.
I disagree (as do the books sitting on my shelf), but I'm not really interested in debating this point of terminology.
> Well, not so much as you'd think.
No, really there is. Trying to deny this isn't insightful, it's myopic. Take the C function:
int plus2(int x) { return x + 2; }
lea eax,[rdi+0x2]
ret
def plus2(x):
return x + 2
3 0 LOAD_FAST 0 (x)
3 LOAD_CONST 1 (2)
6 BINARY_ADD
7 RETURN_VALUE
I expect you will want to talk about the limited circumstances where you can specialize this function ahead-of-time, thereby avoiding the fully-general implementation. This would again be missing the point. Python and C are different beasts, and this difference has far-reaching consequences on their implementations. Trying to draw an equivalence between all "compiled languages" does a disservice to people who are trying to understand the differences between them.
(Yes, most languages compile to bytecode, but people generally use the colloquial term "compiled language" to refer to a language whose implementations usually compile to machine code. JIT compilers for dynamic languages are quite a different thing because they generally only compile type-specialized fragments of code; such machine code has guards that fall back to the general-purpose interpreter if the expected preconditions do not hold.)
~/felix>flx --test=build/release --static mt
~/felix>time ./mt
real 0m0.004s
user 0m0.001s
sys 0m0.002s
~/felix>time ../lua-5.2.1/src/lua mt.lua
real 0m0.006s
user 0m0.001s
sys 0m0.003sDepending on how you look, it is C++ speed OCaML, or perhaps more correctly C++ in a fully type-inferred (unfortunately, nowadays almost everything gets called type-inferred. Hence the added qualification "fully"), ML like language.
It does whole program optimization. It uses a mix of lazy and eager evaluation strategies for speed.
I believe it can generate Python modules too, thanks to how well it interacts with C. The details have to be gleaned from the mailing list though.
I found the tutorial ( http://felix-lang.org/web/tutorial.fdoc ) to be a bit info sparse when I had no clue what I was looking at. Once I’d poked a round a bit it was much better, and started answering questions I was having - mainly how FFI is handled: http://felix-lang.org/web/nutut/intro/intro_01.fdoc
A very cool project.
I can't remember how many times in my life I've done a link expedition through a website or docs just to see a simple programming example.
for var i in 1 upto 15 do
println$
match i % 3, i % 5 with
| 0,0 => "Fizz-Buzz"
| 0,_ => "Fizz"
| _,0 => "Buzz"
| _ => str i
endmatch
;
done
My goto-languages for quick development are Perl 5, Clojure and Javascript.
All 3 are adequately fast for real tasks. All are cross-platform, and all 3 support a REPL that allows doing real work interactively.
These conditions are the absolute minimum to be viable as a scripting or sketch/prototyping language.
I also use re.pl from Devel::REPL (https://metacpan.org/module/Devel::REPL).
I agree this is not the same as a REPL with line by line interactive execution/editing with an environment that saves well defined symbols. Ultimately this would be tough to see through because Felix binds functions statically and lookup is setwise (like function scope in C) not linear, so recursive definitions cannot be introduced one at a time.
I'm curious though: has it been used in production? I'd be very interested in reading real use stories, with up and down sides!
Also, how is the community doing, and what about contributors? Do both groups grow?
one killer feature that would make me start learning it immediately is good, well-documented qt bindings (i'm sure it is possible, since felix compiles down to c++, but with the sparse documentation i have no idea how i would go about getting it up and running, and insufficient motivation to first learn the language and then figure out how to do it).
That being said, I like the idea very much, I just object to the claim of fastest and the value the claim implies. Beating C is very easy if you know some very basic things about the restrictions placed on it by standards... :)
If you REALLY need end of line markers, any half-way competent text editor can display them for you.
I went through this transition before in Scala, the error messages got a lot worse after semi-colon inference was added. I wound up telling people to add semi-colons to their code when they were scratching their head at some sort of parse/type error message.
Also, I do not think of those semicolons as noise They make text easier to parse for humans, too That's why you see most people end sentences, paragraphs and HN posts with a 'superfluous' period
EDIT: Some people will find the above quite readable I am somewhat in that camp Problem is, however, that in English and other languages capitals like I and E are not guaranteed to be sentence starters That muddles the waters considerably Many programming languages have worse problems.
The Facebook group: http://www.facebook.com/groups/243958412369802/
And google group: https://groups.google.com/forum/?fromgroups#!forum/felix-lan...
int*int*int*int*int === int^5
int*int*int*int*int int^5
Internally such arrays have a special representation which allows arrays of 100,000 values, something which could never be represented by a tuple type (and still get reasonable compile times :)
I see that it's billed as a "C++ code generator" and as a "scripting engine".... Does it generate C++ code that I could use without Felix afterwards?
There is actually an option of flx, --bundle=dirname, which puts the generated C++ in a single directory, to make it simpler to ship the generated C++ to another platform.
This does not do a full bundle, i.e. it doesn't package all the run time support code as well. That's on the TODO list, so you could literally copy the target directory to another machine and run "make" or something and only need a C++ compiler to build it.
There's another aspect to your question: if by "use" you also mean "modify" then the current state is that Felix generated C++ is a bit hard to read. The code is "good enough" to add debugging prints but not much more. It would be good to improve this so the code is more readable.
When a function is inlined, there are two things you can do with the arguments: assign them to variables representing the parameters (eager evaluation) or just replace the parameters in the code with the arguments (lazy evaluation).
Substitution doesn't just apply to functions: a sequence of straight line code with assignments can be converted into an expression by replacing occurrences of the variables with the initialising expressions.
For a small number of uses, substitution is the usually the most efficient. For many uses, lifting the common expressions to a variable is more efficient. If we're dealing with a function (in C++ the model is a class) for which a closure is formed (in C++ the model is an object of the class) lazy evaluation is very expensive because the argument itself must be wrapped in an object to delay evaluation.
By default, Felix val's and function arguments use indeterminate evaluation semantics, meaning the compiler gets to choose the strategy. This leads to high performance, but it also means we need a way to enforce a particular strategy: for example vars and var parameters always trigger eager evaluation. This leads to some complication in the language.
Felix also does other optimisations, for example it does the usual self-tail call optimisation. This one works best if you do inlining at the right point to convert a non-self tail call (which cannot be represented for functions in C) into a self-tail call (which is replaced by a goto).
Felix also does parallel assignment optimisation.
It ensures type-classes have zero cost (unlike Haskell which, by supporting separate compilation, may have to pass dictionaries around).
There is quite a lot more: eliminating useless variables, functions, unused arguments, etc. There are even user specified optimisations based on semantics, such as
reduce idem[T] (x:list[T]) : list[T] = x.rev.rev => x;
Actually one important aspect to the optimisation process: by default a function is a C++ class with an apply() method. This allows forming a closure (object). The object is usually allocated on the heap. However Felix "knows" when it can get away with allocating such an object on the machine stack instead (saving a malloc and garbage collection). Furthermore, Felix "knows" when it can get away with a plain old C function, and generates one of those instead if it can. And all of that occurs only if the function wasn't entirely eliminated by inlining all the calls.
So although you should think of Felix functions and procedures as objects of C++ classes allocated on the heap and garbage collected, any significant program implemented with this model without optimisations would just drop dead.
The utility of closures derives from being able to split a data context into two pieces and program the two halves separately and independently. For example for many data structures you can write a visitor function which accepts a closure which is called with each visited value. Lets say we have N data structures.
Independently you can write different calculations on those values formed incrementally one value at a time, such as addition, or, multiplication. Lets say we have M operations.
With now you can perform N * M distinct calculations whilst only writing N + M functions. You have achieved this because both halves of the computation are functions: lambda abstraction reduces a quadratic problem to a linear one.
The downside of this is that the abstraction gets in the way of the compiler re-combining the visitor HOF and the calculation function to generate more efficient code.
There's another more serious structural problem though. The client of a HOF is a callback. In C, this is very lame because functions have no state. In more advanced languages they can have state. That's an improvement but it isn't good enough because it's still a callback, and callbacks are unusable for anything complex.
A callback is a slave. The HOF that calls it is a master. Even if the context of the slave is a finite state machine, where there is theory which tells you how to maintain the state, doing so is very hard. What you really want is for the calculation part of the problem to be a master, just like the HOF itself is. You want your calculation to read its data, and maintain state in the first instance on the stack.
Many people do not believe this and answer that they have no problems with callbacks, but these people are very ignorant. Just you try to write a simple program that is called with data from a file instead of reading the file. An operating system is just one big HOF that calls back into your program with stream data, but there's an important difference: both your program and the operating system are masters: your program reads the data, it isn't a function that accepts the data as an argument.
Another common example of master/master programming is client/server paradigm. This is usually implemented with two threads or processes and a communication link.
Felix special ability is high performance control inversion. It allows you to write threads which read data, and translates them into callbacks mechanically.
Some programming languages can do this in a limited context. For example Python has iterators and you can write functions that yield without losing their context, but this only works in the special case of a sequential visitor.
Felix can do this in general. It was actually designed to support monitoring half a million phone calls with threads that could perform complex calculations such as minimal cost routing. At the time no OS could come close to launching that number of pre-emptive threads yet Felix could do the job on a 1990's desktop PC (with a transaction rate around 500K/sec where a transaction was either a thread creation or sending a null message).
http://felix-lang.org/web/slides/language-overview.fdoc?text
All the documentation and layout needs a lot more work. [BTW: I'm the primary developer]
Yes, clicking links to get a small page of content to only find another link to click .. gets old really fast. (Old as in it feels like the Java documentation circa 2001)
Over those 12 years, what are some of the biggest changes (in the language or its implementation) you have made? Where the changes mostly evolutionary?
Probably the single biggest feature was the introduction of Haskell style type classes as a way to systematically provide "generic" features like comparisons and conversions to string which are de rigueur in dynamically typed scripting languages.
Less obvious but quite important was switching the parser from Ocamlyacc to Dypgen combined with OCScheme, which together put the grammar in user space, allowing almost the entire grammar to be put in the library. A lot of new features were added with very little or no change to the compiler by just adding some EBNF grammar and suitable Scheme action code to the parser.
This can be very effective. For example, with only one extra term in the compiler, I added a dynamic object system that looks a lot like Java with objects and interfaces including "implements" and "extends" stuff. It just uses records of closures (the compiler mod added record extension), but the syntax is neat and almost immediately I used it to factor the webserver into separately compiled plugins. I originally implemented this as a kind of joke, to show off the expressive power in respect of Domain Specific Sub-Languages, but not intended for use. The joke was on me :)
I said "entirely" above because semantics and optimisation are heavily intertwined in any system.
The comment about "syntactic sugar" is valid: there are at least four operators with different precedences all meaning "application of function to arguments". However note that in most languages this is true anyhow: x + y is really just add (x,y). Finding a good set of squiggles and marks that's acceptable to many people isn't easy.
However the syntax is defined in the library, in user space, so you can add your own grammar or design your own domain specific sub-language, and add your favorite squiggles that way. Any contributions to making the standard syntax simpler would be welcome: I'm constantly struggling with this issue because I'm well aware syntax matters, especially early in learning a language.
~/felix>python3 Python 3.2.3 (v3.2.3:3d0686d90f55, Apr 10 2012, 11:25:50) [GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
and also on Linux with this:
skaller@felix:~$ python3 Python 3.2.3 (default, Oct 19 2012, 20:10:41) [GCC 4.6.3] on linux2
I have been told that the script fails if you use a slightly different version of Python:
File "/usr/lib/python3.3/subprocess.py", line 906, in communicate