Montreal Scheme/Lisp Users Group Presentation on Cat
Christopher Diggins
presentation about Cat to the Montreal Scheme and Lisp Users Group,
a.k.a MSLUG ( http://schemeway.dyndns.org/mslug )
I only had 15 minutes, and made the novice mistake of trying to
squeeze too many slides in. I have posted the powerpoint slides online
at: http://cat-language.com/scheming_cats_2.ppt . The other
presentations were much better, and I think I'll do better next time.
There were some great questions, and several interesting ideas arose
from the discussion afterwards. I really enjoyed the opportunity to
meet and talk to so many nteresting and intelligent people. Everyone
was very friendly, and didn't seem to mind that I was so inexperienced
with Scheme.
Adrien, who gave a cool presentation about mobile Scheme code, brought up an
interesting point afterwards about the relation between the bin_rec
primitive and the relationship with morphisms.He has written a very
interesting post about anamorphisms, catamorphism, and paramorphisms
at http://pied.mine.nu//index.php?page=Lambda&id=1
Etienne, who gave an interesting presentation about real-time
synthesis of hardware from Scheme code, commented on the compactness
of Cat code. Etienne pointed out to me that small executables are very
important for good performance, since the cache plays an increasingly
singificant role in code efficiency.
Etienne compared Cat to Scheme in reverse point-free form (all
variable names are lifted out using a lambda lifting algorithm). This
is true, but there is one other difference about the Cat format from
Scheme: it is compositional. This means that an expression in Scheme
such as:
(a (b (c d) e) f (g h))
becomes in Cat:
h f g e d c b a
Notice it is no longer a tree! This should make searching for
optimization opportunities (space or speed) much easier. I will
probably need to come up with some concrete examples to show this in
practice. I am not sure how well-established the advantages of
compositional notation are for such problems, or if my ideas are a bit
eccentric.
Marc brought up a great point about the usefulness of shift/reset
primitives in Cat folr the implementation of continuations. My
instinct is that this is going to be the best way to go about things.
I want to implement as few new constructs as possible. The challenge I
will be faced with will be resolving the types of these beasts. I am
optimistic that the types will reveal themselves soon (once I get a
good nights sleep).
Marc also mentioned that there could be a problem with trying to
Scheme to a typed language because Scheme is so dynamic. This is of
course true, and you have to resort to using runtime variants a
significant amount of the time. However, this doesn't mean that type
systems aren't useful to analyzing portions of Scheme that you know to
be static. You simply analyze with types whenever you can, and you
will get the benefit. Strongtalk for example has shown amazing speed
benefits by applying types to Smalltalk which is another particularly
dynamic language.
Another advantage of a type system, is that it doesn't have to occur
only at compile-time. I use the type system in Cat to check things
dynamically too, and even make on the fly optimizations. (look at the
"bin_rec" primitive definition in the file:
http://cat-language.googlecode.com/svn/trunk/CatPrimitives.cs ).
I should probably clarify that my view on typing is that is simply
another tool to help with software development (optimize code, declare
programmer intent, detect bugs).
Overall the strongest argument I can make for trying to convert Scheme
to a typed language is that it is just another form of analysis. In
fact virtually every form of analysis you do, relates to typing in
some way or another! So like any kind of static (or dynamic) analysis
you perform for the purpose of optimization, or detecting bugs, every
little bit helps.
I am glad people are asking these kinds of questions though. It shows
that they are interested, understand what I am trying to do, and it
keeps me on my toes. One of my biggest weaknesses has been to express
precisely what I am trying to do, and why I think it is important.
This is a byproduct from having been working on language design in
isolation for a very long time.
I was also asked about where I got the name "M" for the
self-application combinator. My point of reference was:
http://www.angelfire.com/tx4/cus/combinator/birds.html whose reference
was to Mock a Mockingbird, among others.
I did a quick demo of Cat at the bar afterwards, and what caught some
people's attention wasn't the fancy code viewer I was so proud of but
rather the mechanics of how "dip" can be implemented. Dip applies a
function to a stack, but first removes the top item, restoring it
after the application. The type signature of "dip" is ('A 'b ('A ->
'C) -> 'C 'b). So for example:
1 3 5 [+] dip
Is equal to
4 5
Dip is technically a primitive for reasons of efficiency, but what is
interesting is that it can be implemented from other primitive as:
"swap quote compose apply".
Here is the transcript that illuminates this:
>> 1 3 5 [+]
stack: 1 3 5 [+]
>> swap
stack: 1 3 [+] 5
>> quote
stack: 1 3 [+] [5]
>> compose
stack: 1 3 [+ 5]
>> apply
stack: 4 5
I was happy to see some people appreciated the elegance of this code.
I like it because it shows how function composition make a
single-stack machine turing-complete, and it shows how expressive a
single combinator can be (but in practical terms).
I don't have time to write about all of the interesting encounters I
had, but all in all it was an extremely productive evening, and I look
forward to meeting with them again soon.
Christopher