Is there a simple way to say, for a struct that is one of the node types for an abstract syntax tree, “ignore this field when testing equality using equal?
”? I know I can write a recursive equality procedure for the whole tree that does this, but it seems like overkill.
No, there’s not a way to write equality predicates like that
Is this different than implementing gen:equal+hash
/prop:equal+hash
for the node struct type?
I think @plragde is looking for a declarative way to implement those without writing new code
I’m revisiting a Racket port of a Haskell program, and Racket does really well aesthetically w/ just a few simple macros. I’m not quite satisfied with porting a list comprehension though. The Haskell is: [ (p, dst) \| (neighbor, dst) <- pairs,
isOccupied b neighbor &&
isEmpty b dst ]
my current Racket version is: (for/list ([pair pairs]
#:when (and (is-occupied? b (car pair))
(is-empty? b (cdr pair))))
(cons p (cdr pair)))
but it would be nice to do something like: (for/list ([(cons neighbor dst) pairs]
#:when (and (is-occupied? b neighbor)
(is-empty? b dst)))
(cons p dst))
Would pattern matching in the for
family be desirable? Are there gotchas that others have already bumped into in this area? In this particular case, if it wasn’t for the #:when
, I’d probably be satisfied with an extra match-define
, but being able to refer to neighbor
and dst
in the guard would be nice.
I see. I interpreted the question more as how to write a relatively local bit of code (which prop:equal+hash
can support), as opposed to having to write code that walks over all node structs.
Maybe wrap pairs
with a sequence constructor/wrapper that returns (values (car x) (cdr x))
for each element?
I think pattern-matching versions of for
are desirable, but making for
extensible in the right way is tricky
I had looked at the equal+hash
docs but I don’t know how to say “just do what you did for all the other fields”.
So unstable/sequence
has been merged with racket/sequence
except for the stuff I need :)
Any particular reason in-pairs
didn’t make the cut?
#lang racket
(struct p [x y ignore]
#:property prop:equal+hash
(list (lambda (a b rec)
(and (rec (p-x a) (p-x b))
(rec (p-y a) (p-y b))))
;; bad but sound hash functions
(lambda _ 1)
(lambda _ 2)))
(equal? (p 1 2 5)
(p 1 2 6))
whether you think that’s “simple” or “a recursive equality procedure” is somewhat up to you :slightly_smiling_face:
Thanks, that is clarifying. In my case, the structs for which I want to do this are leaves, so I presume I can ignore the recursion in the spirit of ignoring the hashing? Since it’s in a pedagogical presentation, I’m not sure I want to invoke this kind of magic anyway.
you should write it the way i wrote it; the rec
function takes care of recursion, and you should definitely not call equal?
in the definition
If the data definition is: ; A Tree is one of
; - Number
; - (p Tree Tree String)
that that means that equal?
will compare all Trees correctly, ignoring all the strings
Okay. Also, I was wrong, they’re not leaves, so the recursion has to work properly. Thank you for the help!
Creating some custom streams should work for now: (for/list ([ (neighbor dst) (pair-stream pairs) ]
#:when (and (is-occupied? b neighbor)
(is-empty? b dst)))
(cons p dst)))
(define-struct pair-stream (v)
#:methods gen:stream
[(define (stream-empty? stream)
(empty? (pair-stream-v stream)))
(define (stream-first stream)
(let ([ pair (first (pair-stream-v stream)) ])
(values (car pair) (cdr pair))))
(define (stream-rest stream)
(pair-stream (rest (pair-stream-v stream))))])
My recollection is it seemed quite niche and less-used (I think I wrote it and was the only one using it).
I would just install that package and use it.
“unstable” makes me uncomfortable :) I just created a stream which should suffice for now. If I end up needing a lot of variety in comprehensions, I’ll consider something more elegant then.
Those libraries are, contrary to the name, extremely stable now, since they don’t change at all. :slightly_smiling_face:
Sure, but “unstable” also seems to imply “might go away later”. If not, maybe a rename is in order.
Renaming would break things — my point is that those pieces of code are effectively frozen.
I may experiment with a more general list comprehension later. It seems Racket has all the tools to do that nicely.
If renaming would break things, maybe just a doc change then, but when I see "NOTE: This library is deprecated" - I generally don’t feel comfortable using it.
I expect I’m not alone in this.
Actually, I see no reason to not add those three functions to racket/sequence
Did in-spine
where (in-spine '(a b c))
runs through (a b c) (b c) (c) ()
ever get added?
(under a different name)
@plragde I’m sort of curious how you are creating your abstract syntax trees. Are you using any macros/the great syntax that Racket apparently has, or just using normal structs without regard to the stuff Racket specifically has for building languages? I want to start getting familiar with the “syntax” and “language-building” things that Racket already provides, but I find myself stuck with creating normal tree struct
s instead of actually using Racket’s built-in things, mainly because I have no idea where to start. Does anyone know a good place to start reading how to make an assembler for, say C++ (or any other language), in Racket?
The “language building” features of Racket are mostly not about defining a bunch of structs for an AST and then processing them in the traditional compiler style. Instead, languages in Racket lean on Racket’s syntax objects and support for macros.
Oh wow, I see. I was taught Racket with the teaching languages as an introduction to functional programming so I don’t really have any background on this side of Racket. What is a good place to start learning about Racket’s syntax objects and support for macros? Is https://beautifulracket.com/ by Matthew Butterick a good introduction? Recently stumbled upon this when looking about on how to implement DSLs, but haven’t had a chance to look at much of anything except the appendices.
Yes, that’s an excellent intro
just a quick one, how do i write the #lang
syntax if i want to use #lang racket/gui
and racket/draw
?
#lang racket
(require racket/gui racket/draw)
thanks,
Maybe require file/resource
too.
But only if you need it.
yes
thank you :slightly_smiling_face:
hi, can you please guide? i’m trying to add a rectangle to a snip, #lang racket
(require racket/gui racket/draw pict)
(define base-rect (class snip%) (init-field (rectangle 50 50) ) )
what do you mean by “add a rectangle to a snip”?
@kokou.afidegnon before you do that, I recommend learning simpler things, like creating a pasteboard, showing it on the screen, and drawing something on it
i though i need to create a snip before adding to the pasteboard
right, you can only add snips to pasteboards, but you should probably start with some of the built-in snips, like image-snip%
ok, this is my latest update, #lang racket
(require racket/gui racket/draw pict)
(define f (new frame% [label "Simple Edit"]
[width 200]
[height 200]))
(define c (new editor-canvas% [parent f]))
(define pb (new pasteboard%))
(send c set-editor pb)
(send f show #t)
how do i add the rectangle ?
you need to create a subclass of snip. I recommend following the Snip guide here: https://docs.racket-lang.org/gui/editor-overview.html#%28part._snip-example%29 which is about a circle, then you can change it to draw a rectangle
thanks, please, bear with me, even though i read over and over, i’m coding with baby steps
also, much of that isn’t necessary to start with; the list at the top points out that only draw
, get-extent
, and copy
are required
can you please explain further? this is what i have done so far: #lang racket
(require racket/gui racket/draw pict)
(define f (new frame% [label "Simple Edit"]
[width 200]
[height 200]))
(define c (new editor-canvas% [parent f]))
(define pb (new pasteboard%))
(send c set-editor pb)
(send f show #t)
(define circle-snip%
(class snip%
(inherit set-snipclass
get-flags set-flags
get-admin)
(init-field [size 20.0])))
Here’s the latest comparison of Racket & Haskell using the <https://www.joenord.com/puzzles/peggame/index.html|Cracker Barrel peg game>. A number of folks helped me with the original about 6 years ago on the mailing list :)
I made a few more tweaks, and I think it compares pretty favorably with the Haskell solution: https://gist.github.com/lojic/6dfbed4065db888ed89f618ee390d9d2 I organized the two files so that similar functions started on the same line, so if you view them in split screen, it should allow easy comparison. I think it’s a pretty good toy program with which to compare languages - not too complex, not too trivial.
With a little more work, I think it might handily beat the Haskell version aesthetically, of course that’s very subjective, but I’ll know it when I see it :)
@kokou.afidegnon I recommend starting with the exact code on that page
the code on the page seems to be complex and confusing
isn’t defpat
just define/match
?
nonetheless, I recommend starting with that and then editing it and trying to understand it more
unfortunately snips are complex, and there’s a lot to learn
i copied the code but i had no output when ran
checking…
well, you would need to show the frame, as you did, and add the snip to the pasteboard
Here’s the definition - it was given to me back in 2014 by someone on the mailing list I think :) (define-syntax defpat
(syntax-rules ()
[(_ (fn pat) b1 b2 ...)
(define fn (match-lambda [pat b1 b2 ...]))]))
It’s not the same, but it may be close enough that I could re-work to use define/match.
shouldn’t a shape being drawn and added to the snip, then to the pasteboard ?
no, the snip is the thing that draws the shape
I’m confident Racket can get there w/ some macro work, but the deconstruction in Haskell is pretty nice.
I’m getting this weird feeling of deja vu that you and I had this same conversation before! :)
oh!
ok, I got it: (define/match (move b move)
[(b (cons src dst))
(match-let* ([ (cons (cons sr sc) (cons dr dc)) (cons src dst) ]
[ neighbor (cons (/ (+ sr dr) 2) (/ (+ sc dc) 2)) ]
[ pred (λ (p) (and (not (equal? p src)) (not (equal? p neighbor)))) ])
(cons dst (filter pred b)))])
I’m not thrilled with having to use a single [ … ] clause.
i.e. I’m not selecting between various patterns, there will be just one pattern for deconstruction, so it looks a little odd, but I do appreciate the generality of define/match
It also allows a more natural invocation in this case vs. (move (list b m))
Oh, I forgot that @alexknauth created a fancier defpat
https://docs.racket-lang.org/defpat-main/index.html
Wow @alexknauth that package has a ton of dependencies !!!
please, can you post a simple example about a snip on a paste board? i’m still not able to make it work
Reference thread: https://groups.google.com/g/racket-users/c/6Lk1BHmpNjc/m/CTO-fwzZUfUJ
if you can wait, tonight I can do that
well, unless someone else get to this before me
sure, i’m here
can you please let me know when you are free?
#lang racket/gui
(require pict)
(define board (new pasteboard%))
(define toplevel (new frame%
[label "My board"]
[width 500]
[height 500]))
(define canvas (new editor-canvas%
[parent toplevel]
[editor board]))
(send toplevel show #t)
(define my-snip-class
(new (class snip-class%
(super-new)
(send this set-classname "my-snip"))))
(send (get-the-snip-class-list) add my-snip-class)
(define rectangle-snip%
(class snip%
(init-field w h)
(super-new)
(send this set-snipclass my-snip-class)
(define/override (get-extent dc x y width height . other)
(when width (set-box! width w))
(when height (set-box! height h)))
(define/override (draw dc x y . other)
(draw-pict (rectangle w h) dc x y))))
(send board insert (new rectangle-snip% [w 30] [h 80]) 100 300)
You should read that blog post.
It’s very detailed
yes, i have been reading the post over and over with no light at the end of the tunnel yet
i hope i will be able to fully grasp the concept
will you be around tomorrow 15H UTC ?
I mean, if I’m free I am happy to help, but I can’t guarantee that I will be free
You don’t need to fully grasp the concept at once. It’s impossible to do that. Instead, try out examples and modify them a little bit to see how things work, bit by bit.
My application is in a second-year course so I am just parsing S-expressions into ASTs built with structs in the obvious structurally-recursive way. I’m not using any advanced language features.
Beautiful Racket is the best introduction to macros and DSLs in Racket that I know of, but I still think the learning curve is too steep, and it’s on my to-do list to think about how to make macros more accessible to beginners.
Cool! Yeah, even doing it the normal way is much easier in Racket due to pattern matching. Are you a lecturer/professor at a university teaching a second year course since you talked about making macros more accessible to beginners?
Can we create a stream with random things? Eg. A stream that contains a mix of various structs, lists, booleans, numbers, whatever we want, and gradually read things in, just like a file port?
(define my-stream (for/stream ([i '(1 "string" sym)]) i))
(define input (read my-stream))
This gives me an error for some reason hmmm…
I am a professor at the University of Waterloo. I started using Racket (then PLT Scheme) in a first-year course in 2004 and now we have nearly three thousand students taking a first Racket course this fall. I have taught macros in a fourth-year PL course, but recently I’m trying to think outside the university course format: what things people don’t know could help them in their work or further learning, and how can I contribute to their progress?
read takes an input-port not a stream
Can you turn a stream into a port?
not easily
why do you want to?
and how would it work? ports fundamentally produce bytes
New to streams, so not sure if this is a good way to use them, but say you have a flattened preorder traversal of a tree where any tree node has an arbitrary # of children, so each item in this list is a pair: (cons tree-value #of children that this tree-node will have).
Now, you want to recreate the tree struct. With a port this is easy: read in the root node, now recurse to create the tree node of the first child, and read in however many nodes that the first child had to make it a tree (and yes, do recursion on the first child’s children too), and now when you get back to the parent root tree, the stream has moved forward to no longer contain the first child’s children. Now, the next thing you read from the “stream” is guaranteed to be the second child, and so on
This is a bit cleaner if you do it with Racket lists which can store more information easily instead of writing to a file and reading from a file port for instance
Basically I just want that “once you have read this in, nobody else can read this thing in” sort of behaviour. This might be a terrible explanation
What you’re doing there is implicitly passing your position in the file via mutation. You could do that by iterating over a stream and using set!
to change the variable that points to the stream, but I would recommend that instead you just write it as a functional program and pass the stream around
Hmm, are you suggesting something like (set! my-stream (stream-rest my-stream))
whenever we exit the function, and have my-stream
as a global mutable variable?
Never really used set!
yes, or something like this: (define (stream-reader stream) (let ([x stream]) (lambda () (begin0 (stream-first x) (set! x (stream-rest x))))))
(define my-read (stream-reader my-stream))
... use (my-read) here ...
but really I suggest writing a functional program
Ok, thank you!
Wait, @samth I’m not sure I actually understand how you would write a functional program to do this. Say you read in the root node from the stream. Now, to find the next tree, you do (my-read stream-rest)
to find the first child, and everything is fine and well until we hit the base case (the node has zero children) and return. When we return back to the parent, we have an unmodified stream, and so we will have to read in the same child again.
A naive solution to this might be to move the stream forward (apply stream-rest
) a number of times. This “number of times” will be equal to not only the number of children our subtree had, but the number of children all of its subtrees had, and so on. So we don’t really know where the next child is going to be in the stream and we “get lost” if you get what I mean… It’s hard to explain :disappointed:
What would the design of a purely functional program that reads in the pre-order traversal of a tree look like? Seems impossible, unless we have a global “pointer” of some sort
You just have to return both the value and the new stream from the recursive call
Something like this? #lang racket
(struct tree (value children) #:transparent)
(define (my-make-tree cur-stream)
(define my-children '())
(define cur-node (stream-first cur-stream))
(define cur-value (first cur-node))
(define num-children (second cur-node))
(for ([i num-children])
(match (my-make-tree (stream-rest cur-stream))
[(list child-tree new-stream)
(set! my-children (cons child-tree my-children))
(set! cur-stream new-stream)]))
(list (tree cur-value my-children) cur-stream))
;; Example
(define my-stream (stream '(bob 2) '(rob 1) '(job 0) '(foo 0)))
(first (my-make-tree my-stream))
I have never done this type of thing where I return multiple things from a function, because I thought that was not the type of thing we did in functional programming, from somewhere I think I had formed the notion that we should always only have one return value.
Also, this seems kind of weird since we have set!
in order to modify my-children
and cur-stream
, which also seems very non-functional. Sorry to be annoying lol… what is your way of implementing this? Am I doing it the “functional” way? I used match
to implement multiple assignment, please let me know if there’s a better way :slightly_smiling_face:
@phanthero I think @samth meant something like this:
#lang racket
(struct tree (value children) #:transparent)
(define (make-tree st)
(define (loop st)
(match-define (list val num-children) (stream-first st))
(for/fold ([children '()]
[st (stream-rest st)]
#:result (values (tree val children) st))
([_ (in-range num-children)])
(define-values (sub-tree new-st) (loop st))
(values (cons sub-tree children) new-st)))
(call-with-values (λ () (loop st)) (λ (tree _) tree)))
(define my-stream (stream '(bob 2) '(rob 1) '(job 0) '(foo 0)))
(make-tree my-stream)
In PL, you can write a functional interpreter that supports mutable state by using what’s known as “store passing style”. This is similar, but instead of passing the store around, you pass the stream around.
ok
> I have never done this type of thing where I return multiple things from a function, because I thought that was not the type of thing we did in functional programming, from somewhere I think I had formed the notion that we should always only have one return value. There are two meanings of “return multiple things”. One is Racket’s support for multiple values (https://docs.racket-lang.org/reference/eval-model.html#%28part._values-model%29 — which is what I used in the above solution) and another is returning a compound value. They are closely related though.
In any case, the fact that compound value exists means that there’s really no distinction between “multiple things” and “one thing”. If you don’t like returning (list a b)
or (values a b)
, you can create:
(struct my-pair (a b) #:transparent)
and then return (my-pair a b)
instead. Now, suddenly you are returning one value!
And returning multiple values is absolutely idiomatic for functional programming.
And, since values
is a little more efficient that returning a list, it’s a nice thing to have.
See also a discussion at https://github.com/racket/rhombus-brainstorming/issues/78 regarding multiple values.
I personally dislike values
(says someone who just used it lol). I think a better way is to have a tuple value which can be passed around just like any single value, but the compiler tries to optimize so that it’s as efficient as values
when the values are extracted immediately after the call.
@sorawee I like that idea.