Arc Forumnew | comments | leaders | submitlogin
Help debug some finite state machine code?
2 points by brianru 4161 days ago | 13 comments
Hi - can someone more experienced with Arc help me debug this?

I'm trying to write a finite state machine utility based on this paper: http://cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/paper.pdf

But whenever I load my code into the repl I get an error:

  Error: "Can't take cdr of _"
The code:

  (def mktransition (tn) (list (car tn) (list (last tn) '(cdr str))))

  (def mktransitions (ts)
    (accum accfn
      (each x (map1 mktransition ts)
        (accfn (car x))
        (accfn (last x)))))

  (mac mkrule (r)
    (let i r
      `(list (car ,i) (fn (str)
                        (if (empty str) t
                          (case (car str)
                            ,@(mktransitions (cdr i))))))))

  (mac automaton (i r) `(withr/p ,(map1 [mkrule _] r) ,i))
Every time I dive in to fix this I come up feeling I'm evaluating r at the wrong time - but I can't seem to pin down how to fix it.

Anyone have any ideas?



3 points by akkartik 4160 days ago | link

The issue is with automaton; you're trying to use a macro (mkrule) like a function with map1. Did you turn mkrule into [mkrule _] because you got this error?

  Can't coerce  #(tagged mac #<procedure: mkrule>) fn
Simply using square brackets isn't going to fix that.

---

In general, creating macro helpers for macros is harder to debug. Instead create function helpers to create the right code as a list and invoke it within the top-level macro to turn it into code. Here mkrule should probably be a function.

(This is what people usually mean when they say *don't overuse macros". And then the dictum gradually gets over-generalized into "macros bad" and finally, "lisp? blub blub.")

-----

2 points by brianru 4160 days ago | link

Yep, that's what I did. Thanks for the advice akkartik -- that seems like a simpler pattern to follow.

I'm still finding that line between functions and macros :)

-----

2 points by brianru 4161 days ago | link

Posted a gist with comments: https://gist.github.com/brianru/6133553

-----

3 points by rocketnia 4161 days ago | link

In the definition of 'automaton, you have the macro call (mkrule _). I don't think you want 'mkrule to be a macro, because I don't think you actually care about the symbol _. The first thing I suggest is to replace "mac mkrule" with "def mkrule".

After this change, I'm still not quite sure what your code is trying to do (I haven't clicked your links yet), so I'll try some example cases:

  arc> (mktransition '(1 2 3 4 5))
  (1 (5 (cdr str)))
  
  arc> (mktransitions '((2 3) (4 5)))
  (
    2 (3 (cdr str))
    4 (5 (cdr str)))
  
  arc> (mkrule '(1 (2 3) (4 5)))
  (list (car (1 (2 3) (4 5)))
        (fn (str)
          (if (empty str)
            t
            (case (car str)
              2 (3 (cdr str))
              4 (5 (cdr str))))))
For one thing, it looks like you might want that (car (1 (2 3) (4 5))) to be just 1. You can fix this by changing (car ,i) to ,(car i).

Since you end up with function calls like (3 (cdr str)), it looks like you're trying to make several functions under the same scope (using Anarki's 'withr/p), and it looks like 'str is a variable that contains the remaining inputs of the automaton.

In this case, I recommend changing `(list (cdr ,i) (fn ...)) so that it's (list (cdr i) `(fn ...)), since you probably didn't want that 'list symbol in the 'withr/p call.

To make this easy to test, here's the complete code, with Anarki's definition of 'withr/p and my updates to 'mkrule:

  ; a 'with that works for defining recursive fns
  (mac withr/p (bindings . body)
    " Scheme's 'letrec.
      See also [[withr]] [[where]] "
    `(let ,(map1 car bindings) nil
       ,@(map [cons 'assign _] bindings)
       ,@body))
  
  (def mktransition (tn) (list (car tn) (list (last tn) '(cdr str))))
  
  (def mktransitions (ts)
    (accum accfn
      (each x (map1 mktransition ts)
        (accfn (car x))
        (accfn (last x)))))
  
  (def mkrule (r)
    (let i r
      (list (car i) `(fn (str)
                        (if (empty str) t
                          (case (car str)
                            ,@(mktransitions (cdr i))))))))
  
  (mac automaton (i r) `(withr/p ,(map1 [mkrule _] r) ,i))
Seems to work!

  (= matches-aabb
    (automaton step-a
      (
        (step-a
          (a step-a)
          (b step-b))
        (step-b
          (b step-b)))))
  
  arc> (matches-aabb '(a a a a b b b b))
  t
  arc> (matches-aabb '(a a a a b b b b a))
  nil
  arc> (matches-aabb '(a a a a))
  t
  arc> (matches-aabb '(b b))
  t
  arc> (matches-aabb '())
  t
  arc> (matches-aabb '(b a))
  nil
  arc> (matches-aabb '(c))
  nil
Now that I look at your Gist, I realize I could have saved myself some time figuring this out. :) I also realize you were aiming for a slightly different interface:

  ; example call:
  ; (automaton 'init
  ;            '((init (c more))
  ;              (more (a more)
  ;                    (d more)
  ;                    (r end))
  ;              (end)))
If you want this interface, you can change 'automaton so it's a function that calls 'eval, rather than a macro:

  -(mac automaton (i r) `(withr/p ,(map1 [mkrule _] r) ,i))
  +(def automaton (i r) (eval `(withr/p ,(map1 [mkrule _] r) ,i)))

-----

3 points by brianru 4160 days ago | link

It works, thank you!

I'm trying to make an oauth utility and it seemed like a cool idea to use a state machine. Fingers crossed.

-----

2 points by zck 4159 days ago | link

Good luck. I could use one -- I've wanted to use it with Twitter for a while. I started writing one myself, then realized I needed a unit test framework, so I've been working on that. Oh, the perils of a language lacking libraries.

Would you like some help? As long as it's free software, I'd love to assist.

-----

2 points by akkartik 4158 days ago | link

But anarki has a unit test framework already: https://github.com/arclanguage/anarki/blob/7415f52cdc/lib/ar.... It also has some intermittent unit tests, e.g. https://github.com/arclanguage/anarki/blob/7415f52cdc/arc.ar...

Did you mean in some other language? It's easy to build a test harness, it's usually the first thing I do with a new language, and invariably just a few lines of code.

Here's my test harness in C++, for example: https://github.com/akkartik/wart/blob/cc70d66ee6/literate/00.... Even in C++ it's just 50 lines or so. Dynamic languages are often even shorter.

(It's not a normal C++ project. I use readable diff directives inside :(..) to add the test harness to the skeleton program at https://github.com/akkartik/wart/blob/cc70d66ee6/literate/00.... But now that this is done, any function I write with 'test_' is automatically run in test mode. Look at the makefile to see how I do that with minimal code.)

Anyways, tell me what language and I'm sure we can get you quickly past this hurdle.

-----

3 points by zck 4157 days ago | link

Honestly, there are some fiddly bits about the unit test framework I don't like, but mainly I wanted to write one.

I actually applied with it for Lisp In Summer Projects (http://lispinsummerprojects.org/), which is why I haven't announced it -- you're supposed to do the work yourself, without help. And people here like to help out and post code. :-p

Luckily, at this point it's got the main features I want, so I can actually use it.

-----

3 points by brianru 4157 days ago | link

Sweet. I had been wanting to play around with the unit test code too -- i'm excited to see what you've put together.

The oauth utility is also for the LISP contest -- we'll see how far I get over the next few weeks.

Either way I'm planning on uploading a few bits and pieces to Anarki or my own repos over the next couple of weeks. (spent some time on anarki's web.arc, the state machine stuff, oauth, some lazy evaluation stuff, etc...)

Once it's all up I'd love some help!

-----

4 points by zck 4157 days ago | link

Well, if it might be useful, let's do it. https://bitbucket.org/zck/unit-test.arc

Please let me know what you think -- email in profile, comment here, open bitbucket tickets, find me on the street^1, etc.

[1] Actually, after writing this, I read your profile, and found you're in Hacker School. I'm in nyc too -- we should meet up sometime. Shoot me an email.

-----

1 point by akkartik 4157 days ago | link

That makes sense :) I'd love to hear more about what's fiddly about the existing version (I have different versions at http://github.com/akkartik/arc, etc.) and why you need the features (suites, nested suites, failure messages, anything else?)

-----

4 points by zck 4157 days ago | link

I'm going to have to go to bed soon, as I need to wake up in eight hours and twenty minutes, and I've promised myself I'm going to try to sleep enough, for once.

So I'll just explain what, in my mind, is the biggest difference -- how I want to use it. To run the anarki test-iso test, you execute the entire `(test-iso ..)` sexp. If you want to run a bunch of tests, you have to execute all the sexps.

That's kind of a hassle. Especially if you find a bug, have a bunch of tests that fail, then change a small thing in the function, and want to re-run all the tests.

In my unit-test.arc, all you have to do is call `(run-suites suite-name)`, and it'll run as many tests as you've got in `suite-name`. You don't have to copy a bunch of sexps into the repl or reload the file (and what if you want to run a subset of a file? You can't). Also -- and this is one of the features I'm currently working on (https://bitbucket.org/zck/unit-test.arc/issue/21/after-runni...), what if you run one hundred tests at once? Do you really want to parse -- with your eyes, like a bloody scribe -- every single line of output to find the seven tests that broke? And when you then make a fix, you're not going to want to parse them again, so you'll only run the seven that failed before. So if you broke something else, you won't find that out.

So, what falls out of my desire to run a set of tests easily and repeatably, and have summarized output? Some sort of grouping, with a single point of entry to run the tests -- that is to say, test suites.

Please correct me if I've missed any feature of Anarki's test framework. I did read its code and try it, but I didn't look into other files for supporting functionality.

-----

2 points by akkartik 4157 days ago | link

Thanks! You're absolutely right, I've had every single one of these problems, I just never focused on them. But I'd often comment out a bunch of tests in the middle of debugging just one.

(brianru also reminded me that arc has a whole new recent unit-test framework with suites: https://github.com/brianru/anarki/commit/b62a38ebcd via https://github.com/arclanguage/anarki/pull/15)

-----