[racket-users] Re: help on coding finite state automata

[Michael Myers]

You might want to take a look at https://github.com/mromyers/automata
specifically, https://github.com/mromyers/automata/blob/master/examples.rkt
and https://github.com/mromyers/automata/blob/master/machines.rkt

I more or less just use the definition that was in my textbook: you provide 
a transition function, and the DFA or NFA just uses stream-fold to get the 
extended transition. I used a bunch of generics stuff to try to generalize
everything past the point of practicality, but it's still reasonably
fast.

It's not documented, but use (in-machine? M seq) to check for acceptance,
(extended-transition M start seq) for final state(s).

There's also a minimization function and nfa->dfa conversion in there, but
they're a bit fragile, so use at your own risk.


-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[racket-users] Re: Racket2 possibilities

[Michael Myers]

I'm somewhat reluctant to write this, as I am more conscious then ever of 
my limitations in terms of what time/energy I can commit and the 
consistency with which I can do so. But insofar as Honu was mentioned, I 
feel a bit obligated to at least chime in with some of my knowledge and 
observations of it, and some related possible strategies.

At the moment, aside from Matt and Jon, I think I have the most direct 
experience of Honu's inner workings. I've also spent a good number of years 
trying to toy with what I feel is a simpler and more modular approach, but 
I've often gotten caught up in bike shedding about names, interfaces and 
what to expose where. For various reasons, this is a domain which 
unfortunately makes it *very* easy to do so. My efforts so far can be found 
here: https://pkgs.racket-lang.org/package/infix-syntax, it is 
unfortunately under documented though. That being said, I would really 
recommend reading the source if possible, as it manages to do a lot in a 
really astoundingly little amount of code (the core logic that drives 
everything is a 7-line function). Specifically this 
https://github.com/mromyers/infix-syntax/tree/master/infix-syntax/private/core 
.


Anyhow, regardless of the exact approach chosen, there are a couple of 
issues I forsee with trying to integrate honu-like features into racket-X. 
These aren't meant to be objections, just things that need to be worked on.

The most trivial one is that define-primitive-splicing-syntax-class 

 
really should graduate out of experimental, since Honu depends really 
crucially on it for its nice integration with syntax-parse. While this 
function hasn't changed in years, the fact that it's in experimental does 
speak to some uncertainty about the interface it provides, which should be 
addressed one way or another. I do dislike the interface slightly, as 
requiring the number of items consumed is slightly awkward in Honu's case, 
introducing a slight inefficiency in redundantly needing to traverse the 
same input list a couple of times, but that's a minor annoyance at worst.

A more general problem is one of style. In racket currently, it seems to be 
encouraged to define keywords in a macro (using ~literal instead of 
~datum), as in 'else' for cond. This has the nice result of allowing you to 
rename keywords. Unfortunately, this introduces a couple headaches in 
something like Honu, which ends up making some things less flexible.

As an example, suppose you have the C ternary operator 'x ? y : z' . If you 
define : as a keyword, either everyone else that uses : as a keyword, like 
a list comprehension macro, will need to use the same one, or you can't use 
both simultaneously. In the best case scenario, : is defined either in 
core, or in a very central library, so most macros that use : as a keyword 
will use the same one. However, if someone later wants to define a : 
operator in a non-core library, using it will break every macro that uses : 
, since it's not the ~literal they're looking for.

The same problem exists for normal macros of course, but in practice it's 
not as much of a problem, because for one there just aren't that many of 
them, since #:keywords fill most of their role. No one seems to grumble for 
instance about the fact that their lovely 'else' function silently breaks 
all of their cond expressions. For operators however, you're usually 
drawing from a much smaller set, and so collisions are a bit more painful. 
Naturally, the solution is to just match : as a datum when it's used as a 
keyword, though this does prevent renaming the keyword if someone should 
wish. Still, I think as a matter of style and convention it's worth 
thinking about good rules of thumb and best practices for deciding when to 
define a keyword literal, and when to just use a datum.

This also ties into one of the other major sore points surrounding scope 
and collision. In languages like haskell and sml, one can 'upgrade' an 
already defined function to an operator with infixr / infixl statements. 
These are fairly convenient to work with, but it's hard to get something 
similar working in Racket, and would require greatly complicating how 
parsing works. The status quo is, if you want to define a new + function, 
one needs to do something like either:
(require (rename-in racket/base [+ add]))
(define-id-operator + add #:left- assoc #:prec 3)

or define the operator as add and use rename-out.

Now, you might not see this as too much of a hassle, but it does add a bit 
of mental overhead and room for user error compared to just, say, 
(declare-infixl + #:left-assoc #:prec 3)
The most natural way to implement something like the latter would be 
something like chez scheme's define-property, so this would be very nice to 
have if at all possible. It does require 

[racket-users] On Fire and Brimstone, Gnashing of Teeth, and the Death of All that is Holy

[Michael Myers]

This is getting out of hand. There is a lot of misinformation swirling 
around, sparking a lot of unnecessary panic and misunderstanding.

Changing surface syntax, even for something as invasive as infix notation, 
is not synonymous with abandoning s-expressions.

Let me repeat this, for emphasis: changing the surface syntax, even to 
introduce infix notation, does *NOT* require abandoning s-expressions.

Let me assert a stronger point: even if, for the sake of calming people's 
nerves, we were to make the following restrictions:

   1. Racket2 cannot use any reader other than the standard racket reader.
   2. Racket2 is not even allowed to be a #lang, the most it can do is be 
   an optional (require racket2) after #lang racket/base.

...we could still significantly alter racket's surface syntax, even to 
introduce infix expressions.

Now, which of the following are real s-expressions?
x 
(+ x y)
(x + y)
x 
(+ x y)
(x + y)
'x
('x ,y '(x y z) ('x'y'z)(x,y,z))
(parse-sexpr '(f (x,y) = 2 x ^ 2 + 3 x - 4))
(#%parse f (x,y) = 2 x ^ 2 + 3 x - 4)
The answer, of course, is all of them.

In fact, the last one is a macro I use fairly often, though I tend to give 
it the shorter name $. 
Consider the following: 
https://github.com/mromyers/infix-syntax/blob/master/infix-syntax/test/core/base-test.rkt

Now, consider the following possible programs:

(def (abs x)(if (< x 0) (- x) x))

def abs(x) = if x < 0 then - x else x

def abs(x) = @(if (< x 0) (- x) x)

(def (abs x)($ if x < 0 then - x else x))

def sign(x) =
  @(cond [($ x > 0)  'positive]
 [($ x = 0)  'zero]
 [($ x < 0)  'negative])

If we treat $ as a macro that recursively parses its contents, and @ as a 
unary operator that treats the expression to its right as a normal 
s-expression, it is possible for all of the above to coexist with the 
standard racket reader, with nothing more invasive than a redefined #%app 
or #%module-begin.

An 's-expression' does not have an inherent order of evaluation associated 
with it. An 's-expression' does not have an inherent evaluation context, or 
namespace, or semantics associated with it. What mflatt is proposing isn't 
"abandoning s-expressions", it's just introducing some amount of parsing 
and interleaving into the process of expansion, in a flexible and 
extensible way, which doesn't even require modifying the expander in the 
slightest. It doesn't inherently require changing the reader. It doesn't 
inherently require changing anything about the syntax of fully-expanded 
programs. It's likely that the reader would be tweaked a bit in the 
process, but at the end of the day, 'read' will still turn strings into 
s-expressions.

If what you're worried about is that you won't be able to write programs 
that look the way you want, you have nothing to fear. With this approach, 
it is trivial to allow seamlessly switching between standard prefix style 
lisp, and infix expressions, even in the exact same program. In Honu, the 
equivalent of the @ operator above is a macro called racket_syntax. Now, 
granted, it's not 100% automatic that switching and interop between these 
will be painless and smooth. So the solution, if you're feeling scared, is 
not to panic, but to stick around, and voice your preference for such 
interoperability as a priority. Racket is a big tent, and so long as you're 
friendly and willing to express your needs and constraints in a civil 
manner, there's a lot of room to make something that appeals to many 
different sensibilities.

Lastly, if what you're worried about is that this somehow makes racket 'no 
longer a true lisp', whatever that means, have no fear. The techniques Honu 
uses are a development and refinement of techniques deeply tied to the 
history of Lisp, originally implemented as a similar, but less 
sophisticated reader macro for Maclisp. By sheer history it's lispier than 
lexical binding! If that's not enough, and you have some reservation about 
'losing homoiconicity' or somerthing, I'd recommend reading the following: 
http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-point/

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/25b3868f-41e2-43ff-afe8-d7c1c8a8253d%40googlegroups.com.