Cat Version 0.16, Lambda Expressions, and Object-Oriented Cat
I recently posted version 0.16 of the Cat interpreter to Google code hosting. This version fixes several bugs in versions 0.15.0 and 0.15.1
- fixed bugs in the named parameter lambda expressions
- fixed typing issues identified by Colin Hirsch.
- sped up drawing code by 2x
- turned off verbose-type inference default setting
- added missing files
Named parameter lambda expressions were added in version 0.15, without much fanfare. I mentioned lambda expressions on my blog previously while they were still in the design phase, but they are now a stable feature. Technically they aren’t part of the core language, but rather an extension which I’ve dubbed “Lambda Cat”. These are enabled in the interpreter by default, so the difference is academic at this point.
Cat lambda expressions allow quotations to have named parameters. For example:
\x.\y.[y x -]Â
This would be written in Scheme as:
(lambda (x y) (- y x))
And in regular Cat this would be equivalent to:
[swap -]
In the most recent release the type system has been updated, but there are still some glitches with how the recursive types (i.e. “self” types nad recursive function calls) are handled. Equirecursive types are tricky to reconstruct and typecheck. The problem is solvable though and I hope to be able to resolve it by 0.17.
Cat Object System (Expected for 0.17)
For those really interested in the internals of the beast (the Cat type inference engine), I do now differentiate between “int” and constant literals like “42″ which is an instance of a “meta_int”. This is the beginning of allowing the type system to do some interesting computations at compile time, and lays the ground work for an even richer type system. For now I am using this idea of typing literals (like integers and strings) to develop an efficient object system, without adding new syntax, just four new primitives.
Cat already supports associative collections (called “hash_list” in Cat), so a JavaScript approach to objects where every object is a dictionary of runtime-polymorphic variants is already trivial to implement. This approach is very slow, because it doesn;’t leverage information available to the type checker, to determine the structure of objects at compile-time. Cat’s type system, with just a small bit of coaxing, can make objects implemented very efficiently and still maintain functional purity.
The Cat object system will require the addition of four new primitive functions: “null”, “_get_”, “_set_”, and “_def_”. These functions will behave like any other stack function, but are optimized by the type-system and use meta-values to determine object structure at compile-time.
The “null” primitive creates a new null object. For now represented by the type “_0″. This is used to construct object of other types.
null : ( -> _0)Â
The “_def_” field constructs a new object type from another object type, by extending the current object’s definition with a new field. The field name is associated with a “meta_string”. The result of such a type is that “_def_” can only occur after a meta_string. While I can’t actually express the following notation legally (not a big deal), the type checker still enforces it.Â
_def_ : (’object ‘value ‘field:meta_string -> ‘new_object)
The “_get_” field accesses a field from an object using a compile-time string.
_get_ : (’object ‘field:meta_string -> ‘object ‘value)
The “_set_” field behave like “_def_” except that the field is expected to already exist.Â
_set_ : (’object ‘value ‘field:meta_string -> ‘new_object)Â Â
Okay, so if you were able to get grok all of that, hopefully it is apparent how objects in Cat can be type-safe and fast. Let me know if you have some questions. I will need to learn to explain this with more coherence.
In Other Cat News
Frank Krueger wrote the core code for a ray tracer in Cat on Thursday. It’ll be a bit of time before I can get to make the neccessary additions to Cat and release it, but it looks like it will be very cool when it is finished. Gabor Greif who is working on a Cat interpreter in Omega, has started blogging about his adventures.
July 9th, 2007 at 12:38 pm
Very intersting, as always, in particular the outlook on the object system, since that’s a path that I need to take too… It’s great that you wrote down your idea in this way because after reading it I feel that I have understood where you are heading too, and it seems rather similar to, but already better thought out than, what I had in mind…
I would also like to take the opportunity to report on a complementary feature that is now working in Mog (having restarted nearly from scratch this is nearly the only thing that is currently working ;-)
‘z> is a variable for the purity of functions; when I compose a pure function and one whose purity depends on the purity of its argument then the resulting type still depends on the purity of the argument:
If however the first function is impure, then the composed function is “tainted” and deduced to be impure; there’s still a variable ‘c> for the purity of the argument.
Ciao, Colin
July 11th, 2007 at 6:13 pm
Re: Object System
Observation: this means that there will be three completely different syntactic ways to define name mappings:
define foo { } // global name
\x [ ... ] // local name
… “foo” _def_ // member name
But on to the interesting part, the interaction between types, compile-time and run-time. If I understand correctly, meta_string and _xyz_ behave somewhat like symbols and syntactical forms in Scheme? On the other hand the meta_string is a string, not something else, so it behaves somewhat like a literal in C++.
Now in C++ it is possible to perform calculations on “literal int”, i.e. the “literal” behaves like a qualifier that, unfortunately, is not explicitly available in the language, one that remains until a calculation becomes “tainted” by a non-literal int.
If I throw in the idea of performing all purely pure computations at compile time, why do you need meta_string? If, at the moment when the _def_ is handled by the compiler, all preceeding pure expressions have already been evaluated, then it is sufficient to check that there is a regular string, and use that…
Another exampe where the pure/impure distinction plus the immutability of all data gives rise to a cool simplification of things ;-)
Does this work as I imagine?
Ciao, Colin
July 11th, 2007 at 6:28 pm
It is an interesting idea, to make the variable explicit. I do effectively the same thing, but the compiler manages it behind the scenes. Exposing it as you do, might simplify your implementation, but has a cost to the end-user.
However, that said it is a great model, and taken to the next logical step we can imagine the “taint” variables to be more than a simple boolean value, but to actually be a tuple of modules (a module is like a monad, in that it represents a stateful system).
In the end the arrow could stand for a lot of different things in the actual type system, but from a programmer’s perspective, pure/impure, might be enough.
July 11th, 2007 at 7:05 pm
I’ve responded to this question on the Cat discussion group.