If you're learning about mazes you'll have plenty of fun reading "Mazes for programmers". I've been reading through it and it's a nice change of pace. I've thrown a few of the algorithms on my pen plotter site https://plott.id/mazes. I definitely encourage you to give the book a look.
PSA: please use clojure.edn/read-string instead of read-string. The latter can execute code when it parses the string (try running `(read-string "#=(println \"oops\")")`.
It's useful because the read-string in core is passing a string to the reader, essentially like an eval[1].
The edn namespace is for Extensible Data Notation[2], and exports functions for reading an object from a stream and from a string without passing it to the lisp reader.[3]
Performance differences are likely not that critical between reading small amounts of data using string I/O vs reading small amounts of data using a library routine that reads and evaluates the data. Runtime evaluation of a string as a language expression is often available in interpreted languages like Python, Ruby, or the Lisp family, and these languages are not usually used in the most performance sensitive programs.
Three factors may make a difference between using the two aforementioned functions. First, performance can matter if the program is doing enough I/O. Secondly, the machinery needed to evaluate language expressions will have to be available at runtime, meaning that the executable will have to be interpreted by an interpreter capable of doing the evaluation (which Lisp, Python, etc. are—they have REPLs after all) or the executable in languages without a runtime interpreter will have to be linked statically or dynamically with code that does the evaluation, making it resulting executable larger. Third, there is the really important reason that programs should avoid reading and evaluating their inputs as expressions: security.
A process runs code within a certain security context, generally with the same privileges as the user running the program. If the data input to the process can run expressions not found in the code, the program’s author can make few security guarantees about the results of running the program. Programs may receive input from the network and may even run at elevated security levels (e.g. setuid); these programs should not evaluate arbitrary input. For example, many security vulnerabilities come from database programs reading strings that are passed directly to the SQL interpreter. See the XKCD “Exploits of a Mom” [1].
Compilers for Lisp have been around in some form for many years—I can remember hearing Patrick Winston talking about them when I first learned Lisp in his class in 1973. There are both interpreters and compilers for many languages and translators that are in between that use JIT compilation at run time.
Lisp and it’s offshoots (Scheme, Dylan, Common Lisp, Clojure, etc.) have a wider range of compilation and interpretation strategies used in their implementations than other programming languages. Perhaps this is due to the fact that Lisp has been around longer than almost any other important language or perhaps its due to its homoiconicity.
However my point was really about the availability of eval at run time, however it is implemented, and particularly eval that runs in the program’s address space and security context.
It’s true that the SBCL implementation of Common Lisp, by default, compiles eval’s arguments at runtime, but it may also use interpretation at runtime depending on the value of the a global variable. Other implementations of Common Lisp always use interpretation, like CLISP. Also, Common Lisp has eval-when which affects the compile vs interpret decision [1].
Readers interested in interpretation vs compilation can find introductory coverage of the topic in Wikipedia, see [2]. Lisp has an interesting and important history to computer science as the first interpreted high level language, see it’s Wikipedia entry at [3].
Sure, just categorizing Lisp as an interpreted languages isn't correct.
> However my point was really about the availability of eval at run time, however it is implemented, and particularly eval that runs in the program’s address space and security context.
Right, but technically Common Lisp doesn't requite eval to use a compiler and it can also load compiled code from the file system, at runtime.
> Other implementations of Common Lisp always use interpretation, like CLISP.
CLISP also provides a virtual machine with a byte code compiler (also optionally a JIT native code compiler), though the compiler needs to be called explicitly.
> Also, Common Lisp has eval-when which affects the compile vs interpret decision [1].
Depends. In an implementation like SBCL or CCL, which use compilation for EVAL, it has no effect on such a decision.
First of all, thanks for sharing;
it's a very educational piece of code!
I have some generic coding advice though.
With slightly better names you can get rid of a lot of the comments. There is a lot of repetition in the code. If you factor that out, you will have even less need for comments. I highly recommend watching some Kevlin Henney talks on such topics, for example https://youtu.be/ZsHMHukIlJY?t=487 (but he has even better talks recently)
The input of the program should be supplied in a more format more natural to humans and let the computer do the transformation into whatever data structure it's comfortable with. So I would propose a simple, multi-line text as an input:
The result of `parse` function will contain character data types instead of 1 character long strings. I think in this case it's actually more readable and more concise too:
Next `println` actually accepts multiple arguments and concatenates them with a space, after stringifying them, so you can drop the extra `(str ...)` wrapping around them.
Then again, the comment is superfluous. It's obvious that you are printing stuff. If you really want to tell what is it, just wrap it in a well-named function. Eg:
(defn report [paths]
(println "The maze has" (count paths) "paths.")
(println "The shortest path in the maze is:" (count (first paths)) "steps long.")
(println "The path is" (first paths))
(println "The longest path in the maze is:" (count (last paths)) "steps long.")
(println "The path is" (last paths)))
So you can just put `(report sorted-paths)` in your `-main`.
Looks similar to A* to my non-Clojure using eye. How has your performance been? If I use a 1000 x 1000 grid in my A* Python implementation I wrote last night it takes forever.
For 20 years I couldn't make a Warcraft 2 clone because I just couldn't figure out A*. And now it turns out this Clojure program is probably doing just that! I can't wait to share this with my son. Having him help me port it to Lua might also end up teaching him a little Clojure too.
I wouldn't expect performance to take forever (> 1 hr) for 1000x1000 in python. I know I have made not optimized path-finding that can solve 100x100 instantly (< 1 sec), and because the time complexity scales with # of vertices for planar networks that should mean that it would only take ~100 sec to solve 1000x1000.
I was being hyperbolic, run time was more in the two minute range. Thank you for the numbers it seems my idea of thousands of units pathfinding over long distances isn't feasible in this way.
My next idea is to "prerender" a series of interconnected waypoints across the map at the start and then pathfind to the nearest one before moving long distances using small bursts of pathfinding to move around obstacles and stay on track.
It's very useful. I once had a codebase where we wrote two (parallel) variants of trampoline called tramampoline and trambopoline, and I'm not even a little bit sorry.
I'm looking at the source, but I'm not sure why "without stack consumption" is true. Is this because trampoline is written such that it takes advantage of tail call optimization even if the inner function doesn't?
Just a nit-picky comment... your 'can-go-left?' and 'move-left', etc. functions would probably be more idiomatic by either passing the direction as an argument, (and maybe using multi-methods, though it might be overkill for this).
Can you please not post unsubstantive comments here? We're trying for a bit better than internet default on this site. If you wouldn't mind reading the site guidelines and abiding by them when posting, we'd be grateful.
Here's the source for the site: https://github.com/blakedietz/plott.id