Cat in Scheme
Christopher Diggins
; released into the public domain by Christopher Diggins, 2007
; cat-primitive instructions
(define (cat-pop s) (cdr s))
(define (cat-dup s) (cons (car s) s))
(define (cat-swap s) (cons (cadr s) (cons (car s) (cddr s))))
(define (cat-apply s) (apply (car s) (list (cdr s))))
(define (cat-unit s) (cons (list (car s)) (cdr s)))
(define (cat-cat s) (cons (append (cadr s) (car s)) (cddr s)))
(define (cat-quote s) (cons (lambda (x) (cons (car s) x)) (cdr s)))
(define (cat-car s) (cons (car s) s))
(define (cat-cdr s) (cons (cdr s) s))
(define (cat-compose s) (cons (lambda (x) (apply (cadr s) (list (apply
(car s) (list x))))) (cddr s)))
(define (cat-add s) (cons (+ (car s) (cadr s)) (cddr s)))
; used for literals
(define (make-literal x) (lambda (s) (cons x s)))
(define (make-quotation x) (lambda (s) (cat-eval x s)))
; convert a Cat program into a list of function calls
(define (cat-compile p)
(map
(lambda (x)
(cond
((procedure? x)
x)
((pair? x)
(make-quotation (cat-compile x)))
(else
(make-literal x))))
p))
; run a compiled Cat program on a particular stack
(define (cat-eval p s)
(if (null? p)
s
(cat-eval (cdr p) (apply (car p) (list s)))))
; run a Cat program
(define (cat-main p) (cat-eval (cat-compile p) (list)))
; tests
(define t0 (cat-main (list 1 2 3)))
(define t1 (cat-main (list '(1) 2 3)))
(define t2 (cat-main (list 1 cat-dup)))
(define t3 (cat-main (list 1 2 cat-swap)))
(define t4 (cat-main (list 1 2 cat-pop)))
(define t5 (cat-main (list 1 cat-quote)))
(define t6 (cat-main (list 1 cat-quote cat-apply)))
(define t7 (cat-main (list 1 cat-quote 2 cat-quote cat-compose cat-
apply)))
; There is probably a better way to define these using function
(define inc (cat-compile (list 1 cat-add)))
(define dip (list cat-swap cat-quote cat-compose cat-apply))
(define t8 (cat-main (list 41 inc)))
(define t9 (cat-main (list 1 3 5 (list cat-add) dip)))
; Have fun!
; Christopher
; =^,,^=
Ben Chambers
trying to find a little project to play with to practice writing
Scheme macros. Rewriting the above Scheme program into a macro allows
the compiler to transform Cat programs into Scheme programs at compile
time, and then optimize them. The basic idea is that each command is
converted into a function that takes a stack and returns a stack.
Then, the macro cat does a bit of magic to thread the stack
transformations together. A couple of macros to make defining
functions using Cat syntax and invoking a program in Cat syntax on the
empty list are provided for convenience. I haven't tested this very
much, so I probably missed some aspect of the original implementation,
but I think the result is nice, and provides an interesting example of
implementing little languages using Macros.
;; This converts a single cat command into a Stack -> Stack
transformation
;; The implementation of these transformations are based pretty much
on
;; code from the last post
(define-syntax cat-cmd
(syntax-rules (pop dup swap apply unit cat quote car cdr compose
add)
((_ pop) cdr)
((_ dup) (lambda (s) (cons (car s) s)))
((_ swap) (lambda (s) (cons (cadr s) (cons (car s) (cddr s)))))
((_ apply) (lambda (s) (apply (car s) (list (cdr s)))))
((_ unit) (lambda (s) (cons (list (car s)) (cdr s))))
((_ cat) (lambda (s) (cons (append (cadr s) (car s)) (cdr
s))))
((_ quote) (lambda (s) (cons (lambda (x) (cons (car s) x)) (cdr
s))))
((_ car) (lambda (s) (cons (car s) s)))
((_ cdr) (lambda (s) (cons (cdr s) s)))
((_ compose) (lambda (s) (cons (lambda (x) (apply (cadr s)
(list (apply
(car s) (list x)))))
(cddr s))))
((_ add) (lambda (s) (cons (+ (car s) (cadr s)) (cddr s))))
((_ (cmds ...)) (cat cmds ...))
((_ other) (lambda (s)
(cond
((procedure? other) (other s))
(#t (cons other s)))))))
;; This converts a series of cat commands into a single Stack -> Stack
transform
;; by threading the stack through all of the commands
;; This serves to 'compile' the program into a scheme lambda, that can
then be
;; optimized by the underlying implementation
(define-syntax cat
(syntax-rules ()
((_ cmd)
(cat-cmd cmd))
((_ cmd cmds ...)
(lambda (s)
((cat cmds ...) ((cat-cmd cmd) s))))))
;; Defines a new top level procedure that operates on stacks, for
instance:
;; > (cat-define inc (1 add))
(define-syntax cat-define
(syntax-rules ()
((_ name (prog ...))
(define name (cat prog ...)))))
;; Runs a cat program on the empty list. Use:
;; > (cat-main 1 quote 2 quote compose apply)
;; (1 2)
(define-syntax cat-main
(syntax-rules ()
((_ prog ...)
((cat prog ...) (list)))))
;; Some simple tests
(cat-define inc (1 add)) ;; We can define a function
(cat-main (41 inc)) ;; We can invoke cat code
(inc (list 5)) ;; We can use the function in Scheme!
Any comments are welcome, and I suspect that there is much room for
improvement, as I'm pretty new to writing interesting Macros.
Tom Schouten
I saw this post on Reddit and was interested in Cat because I've been
trying to find a little project to play with to practice writing
Scheme macros. Rewriting the above Scheme program into a macro allows
the compiler to transform Cat programs into Scheme programs at compile
time, and then optimize them. The basic idea is that each command is
converted into a function that takes a stack and returns a stack.
Then, the macro cat does a bit of magic to thread the stack
transformations together. A couple of macros to make defining
functions using Cat syntax and invoking a program in Cat syntax on the
empty list are provided for convenience. I haven't tested this very
much, so I probably missed some aspect of the original implementation,
but I think the result is nice, and provides an interesting example of
implementing little languages using Macros.
hello ben,
i spent much of my summer trying to implement my compositional language
as (plt) scheme macros. (my cat is now called basecat due to an unfortunate
name clash. basecat is similar to christopher's cat, except that it's dynamicly
typed, and used mostly as an intermediate representation in a forth compiler)
i came to the following conclusions:
- macros written in syntax-rules cannot be composed, unless they are written
in some form of CPS. i found out that using CPS makes them also very slow.
implementing a dsl tends to scream for macro composition at some point.
- the alternative is to use syntax-case, which is now part of the new scheme standard.
this allows you to still be hygienic, but makes it easier to factor the macro transformer
into independent parts which are scheme code, making it easier for the little language
to grow.
- i see no reason for operating on a single function argument as a stack, because
you loose a simple notational device:
(lambda (a b . s) (cons (+ a b) s)) is really equivalent to
(lambda args (cons (+ (car args) (cadr args)) (caddr args)))
- it is easy to automate the 'snarfing': automaticly translate scheme primitives to cat primitives.
- i'm not sure if it's standard, but in mzscheme (part of plt scheme) you can distinguish
between lexical and global/module variables in syntax-case macros. this allows a tight
mixing of scheme and cat code that allows you to use closures. closures are something
i really miss in compositional languages, so i've opted for a solution that at least allows me
to use it in the implementation of the language, with the possibility to simple extend the cat
syntax if i ever need it.
- an open question is if it makes sense to implement the variable passing using 'values', or
some other approach that avoids consing every time a primitive is executed. maybe a linear
stack (i.e. baker's linear lisp) that is copied whenever it is somehow frozen might be a
good idea.
since i know there are at least 2 people now interested in doing cat in scheme, why don't
we work together a bit more? i feel i already solved a lot of problems in the path i've traveled,
and while i very much understand the necessity of re-inventing the wheel as a learning
experience, i'm more interested now in combining (christopher's) cat's type system with my
language core.
( another thing to mention is that i'm really interested in implementing a linear functional
compositional language. i've been working on Packet Forth (PF) for a couple of years now,
and part of what i'm doing with Brood is to do PF right. PF is 'almost linear'. It still uses pointers
that need to be explicitly managed. The thing that really would make things fly is to make it
linear, and typed, mostly aiming at efficient compilation. )
i don't have a lot of promo material, but here are the links to the darcs archives:
http://darcs.goto10.org/packetforth/
http://darcs.goto10.org/brood/
each of them has a 'doc/ramblings.txt' which contains most of my not so
eloquently expressed ideas.
i'm working on a paper for Brood, but i'm a bit stuck at... types :)
the draft of the paper is here:
http://darcs.goto10.org/brood/tex/brood.pdf
cheers
tom
Christopher Diggins
Welcome aboard, thanks a lot for sharing your macros with us!
I can't really provide any meaningful comments on them, since I am a
very new to programming with Scheme, but I look forward to hearing
other people's comments. I will show them to some colleagues and
hopefully I will get some useful feedback that I can share with you.
- Christopher
Ben Chambers
primitives except for while and a bunch of the other primitives as
well. I also made some macros to help clean up the definition of
primitives.
Then I decided to start playing with more efficient ways of doing
things. The implementation behind Chicken Scheme (Cheney on the MTA)
should be able to perform some of the stuff in registers (I think)
because it won't immediately cons arguments. I use improper argument
lists to pull things off the stack, which in theory is a bit easier.
Unfortunately, the new version will only run on chicken-scheme because
it uses the environment extension to let me tell the difference
between a primitive and something that has been defined. Basically, a
primitive is just a function that gets put in the primitive
environment, and all the primitives actually execute immediately when
their seen. Other functions get put on the top of the stack and won't
run until apply.
I think this provides an interesting comparison to the older
implementation. I'll also be interested in seeing how efficient this
version is compared to some of the other implementations available.
(require-extension syntax-case)
(require-extension environments)
(use test)
(define-syntax compose-reverse-help
(syntax-rules ()
((_ args f)
(apply f args))
((_ args f g ...)
(compose-reverse-help (apply f args) g ...))))
;; Compose backwards:
;; (compose-reverse f g) = (g (f ...))
(define-syntax compose-reverse
(syntax-rules ()
((_ f ...)
(lambda args (compose-reverse-help args f ...)))))
;; An environment containing all the primitives that we've defined
(define cat-primitives (make-environment))
;; A definition of the valid primitives
(define (valid-primitive? prim)
(environment-has-binding? cat-primitives prim))
;; Convert a single expression into a function
;; TODO: I'd like to convert this to syntax-case and put the valid-
primitive?
;; as the fender, but unfortunately the environment stuff doesn't seem
to be
;; usable in macros
(define-syntax cat-cmd
(syntax-rules ()
((_ (x ...)) (lambda s (cons (cat-compile x ...) s)))
((_ x)
(if (and (symbol? 'x) (valid-primitive? 'x))
(environment-ref cat-primitives 'x)
(lambda s (cons x s))))))
;; Convert into a cat-expression
(define-syntax cat-compile
(syntax-rules ()
((_ exps ...)
(compose-reverse (cat-cmd exps) ...))))
;; Macro for defining a new cat-primitive. Ideally I wouldn't have
;; to pass the env in, but that would violate hygiene, and I'm not
sure
;; how to do that using syntax-rules.
(define-syntax cat-prim
(syntax-rules (=>)
;; This syntax is kind of the most general -- lets them specify
;; an arbitrary scheme vararg expression
((_ env prim definition)
(environment-extend! env 'prim definition))
;; This syntax allows them to specify only the arguments they need
;; and automatically adds it to the front of the list, also binds
;; top to the value on top of the stack
((_ env prim (args ...) top => definition ...)
(cat-prim env prim
(lambda (args ... . s)
(let ((top (car s)))
(append (reverse (list definition ...)) s)))))
;; This syntax allows them to specify only the arguments they need
;; and automatically adds it to the front of the list
((_ env prim (args ...) => definition ...)
(cat-prim env prim
(lambda (args ... . s)
(append (reverse (list definition ...)) s))))))
;; A macro for defining a bunch of primitives
(define-syntax cat-prims
(syntax-rules ()
((_ env (prim ...) ...)
(begin
(cat-prim env prim ...) ...))))
;; Rename apply for running cat expressions
(define run-cat apply)
;; Add the level-0 primitives
(cat-prims cat-primitives
(add_int (x y) => (+ x y))
(swap (x y) => x y)
(dup () x => x)
(apply (lambda (proc . s) (run-cat proc s))))
;; Run cat expression on the empty list
(define-syntax cat-main
(syntax-rules ()
((_ exp ...)
(run-cat (cat-compile exp ...) ()))))
;; Macro for defining test cases
;; usage: (cat-test (expected list) (cat expressions))
(define-syntax cat-test
(syntax-rules (=>)
((_ (cat ...) => (exp ...))
(test (list exp ...) (cat-main cat ...)))))
;; Tests for each of the individual operations
(cat-test (8 5) => (5 8))
(cat-test (8 5 swap) => (8 5))
(cat-test (8 dup) => (8 8))
(cat-test (8 5 add_int) => (13))
(cat-test ((8 5 add_int) apply) => (13))
On Sep 16, 7:31 am, "Tom Schouten" <tom.goto10....@gmail.com> wrote:
> http://darcs.goto10.org/packetforth/http://darcs.goto10.org/brood/
Tom Schouten
about 'environment-ref':
in PLT scheme, using 'indentifier-binding', you can make the constant/function distinction at compile time. i think this is part of R6RS now too. i use this to distinguish between lexical/module/toplevel identifiers.
for my global identifiers i use a separately implemented namespace so it won't clash with the scheme toplevel namespace. all names are resolved once from a hash table when they are executed using delay/force. all symbols are assumed to be functions.
(it should be possible to use PLT module namespaces only, basicly you get a CAT module system for free then.)
as you allude this makes it possible to expand a code list
(A 123 C)
to
(lambda s (apply C (cons 123 (apply A s))))
where 'apply' is replaced by 'cons' directly if you know that the atom is a constant.
my code that does this is here:
http://darcs.goto10.org/brood/brood/rpn-tx.ss
(http://darcs.goto10.org/brood/ is the root of a darcs archive)
it abstracts the way the global namespace is handled, and defers the real parsing using a 'compiler' object: i'm using it for a couple of different syntaxes (plain CAT, "writer monad lifted", and compositional forth macros / postponed forth)
cheers
tom
Ben Chambers
of the level 0 and level 1 primitives working, except for some of the
ones that use while and empty. As far as I can tell there is a
mistake in the specification of either some of the unit tests or some
of the functions. Specifically, if the predicate for a while changes
the stack, these changes should actually affect the stack, right? If
yes, than the empty primitive shouldn't pop the list off the stack (at
least, according to the test cases for a bunch of the things that use
whilene -- or whilene should duplicate the list before calling empty).
Can anyone confirm that this is a bug?
On Sep 25, 8:58 am, "Tom Schouten" <tom.goto10....@gmail.com> wrote:
> hi ben,
>
> about 'environment-ref':
>
> in PLT scheme, using 'indentifier-binding', you can make the
> constant/function distinction at compile time. i think this is part of R6RS
> now too. i use this to distinguish between lexical/module/toplevel
> identifiers.
>
> for my global identifiers i use a separately implemented namespace so it
> won't clash with the scheme toplevel namespace. all names are resolved once
> from a hash table when they are executed using delay/force. all symbols are
> assumed to be functions.
>
> (it should be possible to use PLT module namespaces only, basicly you get a
> CAT module system for free then.)
>
> as you allude this makes it possible to expand a code list
>
> (A 123 C)
>
> to
>
> (lambda s (apply C (cons 123 (apply A s))))
>
> where 'apply' is replaced by 'cons' directly if you know that the atom is a
> constant.
>
> my code that does this is here:
>
> http://darcs.goto10.org/brood/brood/rpn-tx.ss
>
> (http://darcs.goto10.org/brood/is the root of a darcs archive)
Ben Chambers
if I define whilene as
(define-cat whilene => [dup empty not] while pop)
The original specification online has (define-cat whilene => (empty
not) while pop) which is problematic because empty takes the list off
the stack.
(P.S if anyone cares to see my implementation of everything, just ask
and I'll post it. My next game is going to be adding the IO stuff
from the later levels, and then toying around with type systems).
There are 150 lines of tests (all of the unit tests from levels 0 and
1), 75 lines of glue code that describe how to define new primitives
and stitch them together, and 130 lines defining all the primitives
(most primitives are one line each).
-- Ben Chambers
> > (http://darcs.goto10.org/brood/isthe root of a darcs archive)
Christopher Diggins
On 9/25/07, Ben Chambers <bjcha...@gmail.com> wrote:
>
> Specifically, I can get all the level 0 and level 1 tests to pass only
> if I define whilene as
> (define-cat whilene => [dup empty not] while pop)
> The original specification online has (define-cat whilene => (empty
> not) while pop) which is problematic because empty takes the list off
> the stack.
Thanks for the bug report. The problem is that "empty" should not pop
the list. I'll fix this in the next release.
> (P.S if anyone cares to see my implementation of everything, just ask
> and I'll post it.
Please post it. Thanks! :-)
Ben Chambers
Level 0 and Level 1 (without type systems). You can define functions
and use them. My next step is either to add more of the primitives or
work on types... either way, I plan on playing with this a bit more.
I attempted to keep this as clean/simple as I could, and I think it is
pretty readable (although comments would help).
-- Ben Chambers
On Sep 25, 5:48 pm, "Christopher Diggins" <cdigg...@gmail.com> wrote:
> Hi Ben,
>
> > > > (http://darcs.goto10.org/brood/istheroot of a darcs archive)
Christopher Diggins
http://catlanguage.googlegroups.com/web/cat-scheme.tgz . I have now
granted permissions to all members to upload files.
Thanks for sharing your Scheme implementation of Cat Ben!
- Christopher
On 9/25/07, Ben Chambers <bjcha...@gmail.com> wrote:
>
Christopher Diggins
Ben Chambers
like recursive function definitions. I'm planning on trying to get it
to support more of the cat language, as well as the type system -- as
a result I've decided to start a google project to get some version
control and issue tracking for it. It can be found here
http://code.google.com/p/scheme-cat/. I'm hoping to eventually turn
it into a language for writing modules for DrScheme, but that is still
a ways in the future. Anyway, just thought I'd post this for anyone
interested so they could look at the source code where it is and keep
up with it. If it's ok with Christopher I'll post any significant
milestones here (such as support for later levels of language, the
type system, etc) -- I doubt enough people will be interested in it to
justify creating a separate discussion group.
On Sep 25, 11:13 pm, "Christopher Diggins" <cdigg...@gmail.com> wrote:
> Sorry wrong URL, you'll have to navigate to:http://groups.google.com/group/catlanguage/files
>
> On 9/25/07, Christopher Diggins <cdigg...@gmail.com> wrote:
>
> > Ben sent me the files, and I posted them to
> >http://catlanguage.googlegroups.com/web/cat-scheme.tgz. I have now
> > granted permissions to all members to upload files.
>
> > Thanks for sharing your Scheme implementation of Cat Ben!
>
> > - Christopher
>
> > > > > > > (http://darcs.goto10.org/brood/istherootof a darcs archive)
Christopher Diggins
>
> Well, I've been doing some more work on getting it to support things
> like recursive function definitions. I'm planning on trying to get it
> to support more of the cat language, as well as the type system -- as
> a result I've decided to start a google project to get some version
> control and issue tracking for it. It can be found here
> http://code.google.com/p/scheme-cat/.
Great stuff, thanks for sharing it. And thanks for filing bug reports
against Cat. I promise to do a new Cat release before the end of the
month which will address your issues, and add many more tests. I'm
currently submitting an article on Cat to CC 08, which I will share
here soon.
> I'm hoping to eventually turn
> it into a language for writing modules for DrScheme, but that is still
> a ways in the future.
That would be nice. Have you considered the possibility of supporting
Gambit/Snow? My advisor (Marc Feeley) would probably be particularly
interested in that. :-)
> Anyway, just thought I'd post this for anyone
> interested so they could look at the source code where it is and keep
> up with it. If it's ok with Christopher I'll post any significant
> milestones here (such as support for later levels of language, the
> type system, etc)
Please do.
> -- I doubt enough people will be interested in it to
> justify creating a separate discussion group.
Currently I only have 32 people on this mailing list, but you never
know what could happen in the future. There is supposed to be a Doctor
Dobbs article on Cat coming out next month, which could generate some
more momentum. I mention this because maybe more people will be
interested in the Scheme version of Cat than a C# implementation.
Keep up the great work and thanks for sharing. I promise to link to
your work soon from the Cat-language.com web site once I get a spare
moment.
Cheers,
Christopher
Christopher Diggins
system for Scheme-Cat? It should be relatively easy to do with Scheme
macros.
- Christopher
Ben Chambers
optimizations. But for now I think the important thing is to get
something that does the rest of the primitives. I say this because it
would then be an alternate implementation of the semantics of Cat
which would allow for comparison to the C# implementation.
As far as the Gambit implementation I'm not sure but it should be
relatively easy to port most things. I'm not sure what kind of module
system Gambit has or how well it'll support some of the interesting
macro tricks, but the specification of the primitives and all the
tests should be pretty much 100% portable (once the core macros are
fixed). So I guess that's just a long winded way of saying, Gambit
support isn't planned at this point, but it should be easy enough if
someone wanted to add -- all they'd need to do is figure out how to
get the module system to work and then fix the macros in core.scm and
test-support.scm (in the new layout).
I'm mainly using PLT scheme because I go to Northeastern University
and they have a big group of really experienced PLT hackers. In fact
once I get this hammered out a bit better I may run it by some of them
and see if they have any suggestions.
I'm still digging deeper into Cat, but I like the language. I think
the Scheme implementation provides a very convenient place to play
with various tweaks to the semantics (since the entirety is currently
only 429 lines of code -- including whitespace and tests and such).
Great job on the specification -- the fact that I was only able to
find very small mistakes in the semantics is impressive.
-- Ben Chambers