Actually, especially since Arc lacks a debugger, I find it very convenient to be able to just place a pr: or pr. in front of some symbol to get an expression printed out without the behavior changing.
It could return the list (1 2), but this would mean to cons up a new list every time we use 'pr just to throw it away. Multiple return values would solve the problem. Why not add them to the language?
> How much more expensive is cons compared to multiple return values?
It depends on the GC used and on the implementation. mrvs are usually pushed on the stack, so there is no GC overhead. When I develop applications with Lisp, I notice that most of the time reducing the amount of garbage speeds up the program noticeably. It's not only a problem of consing, it's also a problem of collecting the garbage. More garabage, more collection cycles.
Shame I didn't notice before the edit limit expired, but this post got screwed up by the formatting system. The first first line should read "Arc's (errr....MzScheme's) * :". The example in the last paragraph should read "that .* gets translated to (#<eof> *)". And everything in between should not be italicized...
Well, since I voted for the basic library with sin, cos, pi, gcd, etc, I felt obligated to implement a basic math library with sin, cos, pi, gcd, closely related fucntions, and everything I needed or thought I'd need to implement those.
Implementations guaranteed not to be optimally efficient:
Edit: Fixed a mistake in bringing out-of-period numbers into period in sin and cos
(= pi 3.141592653589793238)
(= 2*pi (* 2 pi))
(def signum (n)
(if (> n 0)
1
(< n 0)
-1
0))
(def floor (x)
(if (< x 0)
(- (trunc x) 1)
(trunc x)))
(def ceil (x)
(if (< x 0)
(trunc x)
(+ (trunc x) 1)))
(defmemo fac (n)
(if (is n 0)
1
(* n (fac (- n 1)))))
;Existing mod only accepts integers. Left intact as "modulo"
;This mod copies the behavior of Ruby's mod
(def mod (dividend divisor)
"Returns the remainder from dividing dividend by divisor.
Adds divisor once more if they are of different signs so that the result is always of the same sign as divisor."
(if (is divisor 0)
(error "modulo undefined for 0")
(isnt (signum dividend) (signum divisor))
(+ divisor (- dividend (* divisor (trunc (/ dividend divisor)))))
(- dividend (* divisor (trunc (/ dividend divisor))))))
(def sin (x)
"Returns the sine of x in radians."
(let x (let red (mod x 2*pi)
(if (> (abs red) pi)
(- red (* (signum red) 2*pi))
red))
;Taylor polynomial; 0.0 is to cast to float
(- (+ 0.0 x (/ (expt x 5) (fac 5)) (/ (expt x 9) (fac 9)))
(/ (expt x 3) (fac 3)) (/ (expt x 7) (fac 7)))))
(def cos (x)
"Returns the cosine of x in radians."
(let x (let red (mod x 2*pi)
(if (> (abs red) pi)
(- red (* (signum red) 2*pi))
red))
;Taylor polynomial
(- (+ 1.0 (/ (expt x 4) (fac 4)) (/ (expt x 8) (fac 8)))
(/ (expt x 2) (fac 2)) (/ (expt x 6) (fac 6)))))
(def tan (x)
"Returns the tangent of x in radians."
;Lazy definition
(/ (sin x) (cos x)))
(def int? (x)
"Returns whether x is an integer"
(is (mod x 1.0) 0.0))
(defmemo prime (n)
"Returns the nth prime. 2 is the 0th prime."
(if (< n 0)
nil
(is n 0)
2
(let prev-primes (map prime (range 0 (- n 1)))
((afn (i)
(if (no (breakable:each p prev-primes ;Each always returns nil, so a break returns t
(if (int? (/ i p))
(break t))))
i
(self (+ i 1))))
(+ 1 (last prev-primes))))))
(def prime-factorization (n)
"Returns a list each prime up to the greatest prime in n paired with the power of that prime in n.
E.g.: (prime-factorization 20) returns ((2 2) (3 0) (5 1)).
Use (reduce * (map [apply expt _] ...)) to change a prime factorization into the number."
(rev:accum keep
(let p-ord 0
(while (> n 1)
(with (p (prime p-ord)
pow 0)
(until (isnt (mod n p) 0)
(++ pow)
(zap [/ _ p] n))
(keep (list p pow)))
(++ p-ord)))))
(def gcd (x y)
"Returns the greatest common divisor of x and y."
(reduce * (map [apply expt _]
(map (fn (a b)
(list (car a) (min (cadr a) (cadr b))))
(prime-factorization x) (prime-factorization y)))))
(def lcm (x y)
"Returns the least common multiple of x and y."
(/ (* x y) (gcd x y)))
Nice. I only did the gcd function, so you've got an amazing head start on me. However, the version of gcd that I did was Euclid's algorithm. Probably faster than prime factorization; and I included a case for only one number, and a list of greater than two.
Since I couldn't commit to github for some reason, here's the code:
;;Int (predicate)
(def int (n)
"Returns true if n is an integer; i.e. has no decimal part."
(is (trunc n) n)) ; return true if the number is the same as itself without the decimal part
;;Greatest Common Denominator
(def gcd l
"returns the greatest common denominator, or divisor, of a list of numbers. Numbers should be integers,
or the result will default to 0."
(with (a (car l) c (cdr l))
(if (len> c 1)
(gcd a (gcd (car c) (cdr c))) ; handle lists of more than two numbers
(no a) 0
(no c) (abs a)
(let b (car (flat c))
(if (or (~int a) (~int b)) 0 ; skip non-integers
(is a b) a ; return common divisor
(if (> a b)
(gcd (- a b) b)
(gcd (- b a) a)))))))
Update:
Figured out what I was doing wrong with github. Math library now started in lib/math.arc. Currently it only contains my gcd function and the 'int test, but feel free to add any other math functions.
In the future, we may need to make it a math folder, with individual files for trig functions, hyperbolic functions, calculus, matrix and vector function, quaternions, etc. But for now one file is more than enough to contain my lowly gcd :)
My original int? was identical to yours, but that's why I changed it. Although, now that I think about it, since prime-factorization discards the results of operations that cast n to a rational, that's unnecessary. Still, there will need to be separate functions for testing if a num's type is int (which yours does), and testing if a num lacks decimal places (which mine does).
(And yes, Euclid's is definitely faster than prime factorization -- I originally looked at better algorithms for prime finding and gcd but I decided to settle for the "pure" approach -- sieve instead of some Fermat's or another fast primality test, prime factorization based instead of Euclid's.)
Ah, I didn't notice that. Apparently I should test things more carefully next time :)
I don't know if you have github access, but if you do, you can feel free to add your own code to the math.arc lib. I probably won't have a chance to add it myself in the next week or so. If I can, though, I will definitely try to do so.
In doing so, I noticed one bug in Darmani's original implementation of 'floor and 'ceil. 'floor would return incorrect results on negative integers (e.g. (floor -1) => -2), and 'ceil on positive integers (e.g. (ceil 1) => 2). This has been corrected on Anarki.
I also used mzscheme's 'sin, 'cos, and 'tan instead of Darmani's, not because of speed issues, but because of decreased precision in those functions. In order to get maximum precision it would be necessary to calculate the Taylor series an extra couple of terms, which I didn't feel like doing at the time.
I didn't commit 'signum, 'mod, 'prime, or 'prime-factorization, because I wasn't sure if they were needed except for computing 'sin, 'cos, and 'gcd... but feel free to commit them if you want.
1) Isn't pushing those math functions straight from scheme sort of cheating? I mean, maybe I'm just wrong, but wouldn't the solution be more long term if we avoided scheme and implemented the math in arc?
2) Shouldn't fac be tail recursive? Or is it, and I just can't tell? Or are you just expecting that no one will try and compute that large of a factorial
3) If some one did compute that large of a factorial, is there some way for arc to handle arbitrarily sized integers?
1) No, you should implement in the math in the underlying machine instructions, which are guaranteed to be as precise and as fast as the manufacturer can make it. The underlying machine instructions are fortunately possible to access in standard C libraries, and the standard C library functions are wrapped by mzscheme, which we then import in arc.
2) It should be, and it isn't.
(defmemo fac (n)
((afn (n a)
(if (> n 1)
(self (- n 1) (* a n))
a))
n 1))
3) Yes, arc-on-mzscheme handles this automagically. arc2c does not (I think it'll overflow)
Implementing numerically stable and accurate transcendental functions is rather difficult. If you're going down that road, please don't just use Taylor series, but look up good algorithms that others have implemented. One source is http://developer.intel.com/technology/itj/q41999/pdf/transen...
That said, I don't see much value in re-implementing math libraries in Arc, given that Arc is almost certainly going to be running on a platform that already has good native math libraries.
I figured that being close to machine instructions was a good thing, but I thought that we should do that via some other method, not necessarily scheme, which may or may not remain the base of arc in the future.
That being said, if you think that pulling from scheme is a good idea, why don't we just pull all of the other math functions from there as well?
Actually I think it might be better if we had a spec which says "A Good Arc Implementation (TM) includes the following functions when you (require "lib/math.arc"): ...." Then the programmer doesn't even have to care about "scheme functions" or "java functions" or "c functions" or "machine language functions" or "SKI functions" - the implementation imports it by whatever means it wants.
Maybe also spec that the implementation can reserve the plain '$ for implementation-specific stuff.
A month or two ago, I wrote Sokoban in Arc, and produced a small library for multidimensional lists in the process. This function should interest you:
;dims needed because ((abc)) may be a two-dimensional list containing abc or
;a one-dimensional list containing (abc)
(def muldim-map (dims f lst)
((afn (lst)
(if (no lst)
nil
(if (is dims 0)
(f lst)
(cons (muldim-map (- dims 1) f (car lst)) (self (cdr lst))))))
lst))
If I read it right, it is a function that for example, can grab the nth entry from a cell (or nth row / column from a matrix)?
You have the code out there somewhere? It is probably good to have some more examples of Arc out in the open, and there'll be things in it I can learn from.
Sorry, I misunderstood your query last night.I just realized the function actually doesn't apply in this specific instance here.
It's a version of the normal map generalized to n-dimensional lists; I forgot when writing it that normal map accepts multiple lists.
However, with that added, it would be useful if you, say, had (((1 2) (3 4)) ((5 6) (7 8))) and wanted ((6 8) (10 12)); that would end up being (apply muldim-map 2 + (list (list (list 1 2) (list 3 4)) (list (list 5 6) (list 7 8))))
(I was going to download Arc's source code and use the source of the original map as a guide to writing a version of muldim-map that could handle multiple multi-dimensional lists on the spot, but I don't believe these high school computers have software that can handle tarballs.)
However, I just realized I had another function in that library that could perform the task you described, although it would be overkill. It's called something like move-muldim-block; it takes a multi-dimensional list and returns a new multi-dimensional list with a multi-dimensional piece of that list moved elsewhere, using a combining function to determing the value of the area in which it was moved (I used it in Sokoban to simplify code that would let let me move a crate character onto a storage character and change it to the crate-on-storate character).
In other words, if lst is set to ((1 2) (3 4)) and f is some function, (move-muldim block (list 1 0) (list 1 2) (list 0 0) +) would be equivalent to (((+ 1 3) (+ 2 4)) ((f 3) (f 4))) (it moves a 1x2 block from coordinates (1 0) to coordinates (0 0)). Just take the car of the result and you have what you're looking for (in which case, we could omit the last argument and use the default value).
For this specific task, apply is a heck of a lot simpler, but I can still post the code if you're interested. I personally found it very interesting to realize that this could be done, and that muldim-move-block is a little more useful than I first thought.
Hmm. Right now I store the positions of my mobile piec elsewhere than in the world-list. Your function might be handy later on. I haven't yet decided if I want every actor of the world stored in the world (even if some of them might overlap), or store the mobile actors in a separate list.
Right now the thing about sokoban implementations that would interest me most is if you've done anything fancy to generate the output. Having an update of a 2d world scroll by ever so often makes it hard to track movement of a single character through this world. Did you work on that?
Since Arc is a language targeted for the web... have you considered the possibility of generating a web page for it, with maybe next >> and << prev links?
That might actually work, and just autorefresh the page every second or so :)
First priorities now are finishing the wandering algorithm for the animals so that they're no longer steered but steer themselves, and generalize the code I've some more so that adding more behaviours than just biting things is easy. I'll add the visuals-through webpage idea to that list :)
Sorry, not really. I just used a simple function to print out a 2-dimensional list and resized my terminal window so that the grid would be in the same place after every sequence of moves, which gives the illusion that the same grid is being redrawn.
Small mistake -- the invocation would be (move-muldim block (list 1 0) (list 1 2) (list 0 0) + f) (I hope no-one thought I'd be silly enough to set the function to find the replacement-fn by looking up the global value of f...).
From there, just hack the REPL to include an on-error around everything. Perhaps some more complex hacking could be done to insert code that would allow one to track where in a function one before an error occurs.
Since we don't have first-class special forms, in the meantime, one can just replace this redefinition of fn with a similarly-named macro and then replace all invocations of fn to this macro. Should probably wrap this around the primitives too.
Of course, I'm not advocating this as ideal; I'm just exploring the possibility of doing this in pure Arc (or almost pure; I forget whether the REPL is in Arc or Scheme). Aside from seed issues, I'm sure this setup has many problems. Is it possible to get this kind of thing to work with multiple threads?
'range is an arc.arc function in canonical Arc, so you should be leery of redefining it - if you decide to use some random library, and it uses 'range in the canonical sense, you can expect it to break.
Instead, define it in subfunction form:
(def directawayfrombound (creature)
(withs (range
cons
within
(fn (range num)
(let (min . max) range
(<= min num max)))
awaydir
(fn (pos dim dir)
(if (within (range 0 (- dim 1)) (+ pos dir))
dir
(- dir)))
(xpos ypos) creature!pos
(xdir ydir) creature!dir)
(list
(awaydir xpos (len world.0) xdir)
(awaydir ypos (len world.0) ydir))))
Thanks for the correction. Although I did know about the canonical range function, it slipped my mind when I wrote that (though I did have the feeling that there was a "real" range function). I should have mentioned that I wasn't near any computer with Arc when I wrote, though I still should have known better.
Both of you, thanks!, more learning arc. (1) "withs" is "with sequentially"', so that "range" makes sense in the function "awaydir". (2) cons isn't just appending a number to a list.
I like the table!key syntax, not sure what I'm thinking about world.0 as a syntax, especially because world.0.0 doesn't give what I'd expect (first element of the first element of world), but just returns the same as world.0
(def makeworld (x)
(= world (n-of x (n-of x nil))) ; world of nil
nil)
Actually, almkglor's code would (I'm pretty sure) have worked with just a normal with; function definitions are unevaluated at definition, so that (fn (x) (afergergghersgergferg x)) would not give "Error: afergergghersgergferg is not a function" until it's called. If a defined a function called afergergghersgergferg in the meantime, as with a normal with statement, it should have worked.
Anyway, you're not alone in being surprised that x.y.z expands to (x y z) instead of (x (y z)).
Not quite. It works in the toplevel because doing (def name args ...) is effectively to (= name (fn args ...)); this establishes a global, not a lexical, binding. Using let/with/withs adds a lexical binding, and since functions (or "closures") close over their scopes, they can't get at functions defined at the same time. Thus, you need to use withs. Observe:
That implies that at the top level, the order in which I define my functions (which use each other) doesn't matter..
nice! Then I can group them in a way that is more sensible for humans.
Anyway, the program is now far enough that I've a critter running around the field and filling its memory with associations between the things it encounters. Next stop is to let it learn what is edible and to let it steer itself based on its observations :).
Unfortunately, that won't work because the form is being returned to a place outside the closure where olddef was defined; when eval is given the form containing olddef, it will not recognize it.
