freenode/#lisp - IRC Chatlog
Search
4:26:33
no-defun-allowed
Also, numbers with decimal parts will never be perfect squares, so you could test for that too, but 8.99999 is getting uncomfortably close to 9 for single floats.
4:28:51
beach
gabbiel: I think you need to follow the advice of no-defun-allowed and only work with integers.
4:32:37
no-defun-allowed
Sorry I didn't mention what isqrt did, it only handles positive integers and gives you the (lower) closest integer to the square root of that number.
4:34:59
no-defun-allowed
Your initial definition for perfect-square-p is also incorrect as you forgot to do something with the square root (eg floor it) to make its square not the number you started with, gabbiel.
4:36:20
aeth
gabbiel: Convert floats to integers with truncate (or any of the other similar functions). Use multiple-value-bind like this: (multiple-value-bind (n remainder) (truncate n) ...)
4:36:29
beach
gabbiel: Try something like (defun perfect-square-p (n) (let ((root (isqrt n))) (= n (* root root))))
4:36:58
aeth
gabbiel: if the remainder isn't 0 (or use some epsilon e.g. 0.01 or something) then it cannot pass anyway
4:37:43
aeth
but e.g. 43f0 or 43d0 will have 0.0f0 or 0.0d0 respectively as their remainders, so they are potential candidates, as 43
4:38:55
aeth
If you use truncate, you actually have to check for closeness to both 0 and 1 if you're not doing an exact zerop on the remainder. round will be closeness to 0 on either side (positive and negative), and the others will all have their own quirks.
4:41:27
aeth
The real question there, though is if you only want to count 1d0 or if you do want to count 0.99999999d0 as 1
4:41:55
aeth
Naturally, doing the latter is going to complicate things, and probably have two cases, for when you're very close above and very close below.
4:43:00
aeth
I guess round probably is the simplest because there the second value is the diff between the old value and the new value.
4:47:59
aeth
I think it would look something like this, if you're going the zerop route: (defun perfect-square-p (n) (let ((n (ctypecase n (integer n) (float (multiple-value-bind (n* remainder) (truncate n) (if (zerop remainder) n* nil))) (number nil)))) (if n (= (expt (isqrt n) 2) n) nil)))
4:48:58
aeth
If you're doing the more complicated route and you want to count 0.99999999d0 as 1, then you have to replace TRUNCATE with ROUND and do a more complicated check than ZEROP on the remainder. Something like (< (abs remainder) epsilon)
5:09:25
aeth
gabbiel: if you were going to cover 0.999999 you'd need to break up the floats into each different kind of float because they'd all have a different optimal epsilon there. You could even use some multiple of short-float-epsilon, single-float-epsilon, double-float-epsilon, and long-float-epsilon as your epsilons.
5:09:41
aeth
You'd probably want to do the order single-float double-float long-float short-float and unfortunately SBCL will warn you about deleting unreachable code for the latter two cases because in SBCL short-float is single-float and long-float is double-float
5:14:09
gabbiel
seems complicated. but it would be useful for computed values which are meant to be 1, but come 0.99999
5:14:31
gabbiel
for now, I think I'll do the truncate implementation, and maybe later I'll do the round version
5:32:04
gabbiel
this is weird, I ended up with this https://pastebin.com/wK7xN2TS:, but 63.9999999999 still passes the predicate
5:47:10
beach
gabbiel: I really, really think you should stick to integers, and not trying floating point numbers, because you seem to lack some understanding in how they work.
5:48:50
no-defun-allowed
I agree with beach here, it'd be much less work to just use integers, remembering there are no non-integer perfect squares.
5:52:29
gabbiel
I got the cases like 9.0 where it should work, I don't think I require the cases like 0.9999999
5:55:34
gabbiel
yeah I haven't dealt much with floats, and never read the standard on floats/doubles
5:56:37
no-defun-allowed
You might want to skip through a video like https://www.youtube.com/watch?v=jsLiDQyyBXk where the loss of precision in floating point numbers has an effect in a game.
5:57:38
no-defun-allowed
The calculation here that goes wrong could be something like (+ (float (expt 2 21)) 0.1). If you evaluate that, you'll notice the 0.1 seemingly isn't added.
5:59:10
White_Flame
single precision tracks 7.22 decimal digits; double precision tracks 15.95 decimal digits
5:59:14
no-defun-allowed
If you keep incrementing that 0.1 slowly, you'll notice that past 0.15 it jolts up to 2097152.3. This is why you see the video jump between positions, and is also (although, with numbers scaled down) why you can't get 0.9999999 to not "equal" 1.0.
6:07:31
gabbiel
somebody here talked about a cl library where decimal arithmetic was precise but I forgot the name
7:52:24
aeth
well, nothing is perfectly precise unless you have symbols for things like "pi"... but even then you'd probably quickly wind up with stuff like 23434/3495935*pi as your numbers
8:02:27
pjb
aeth: there's an infinite number of trancendantal numbers. So you would need to express your numbers as vectors of rationals of infinite size.
8:07:16
aeth
pjb: I'm assuming this system wouldn't be able to represent all numbers, but would be able to represent some like pi and e, which would probably be good enough for most calculations.
8:07:53
saturn2
any number that you thought up without taking infinite time can be represented with finite space
8:09:07
pjb
aeth: square roots are often irrational. And they can often be encountered in real problem as solutions of equations.
8:09:23
pjb
aeth: so already you'd need an infinite number of the square roots of all prime numbers…
8:11:31
aeth
pjb: true, so you'd have to have square roots represented... although maybe not, maybe they'd just be a special case of powers.
9:37:49
phoe
dim: reviewed. I don't have the domain knowledge yet so I've mostly commented on Lisp-related stuff.
10:09:06
no-defun-allowed
shangul: reinventing the wheel is a hip thing to do now, don't worry about it!
10:09:30
shangul
phoe, solving problems with just functions from the original LISP and building my own LISP
10:11:10
phoe
shangul: I'd say that would be reinventing the wheel only if you've already done that exercise
10:11:46
phoe
doing these things, e.g. writing your own mapcar, reduce, map, assoc, assoc-value, etc.. is a pretty good exercise in list processing in general
10:12:38
phoe
as for building your own, that's also pretty good - projects like BYOL and MAL exist exactly for that
10:13:36
no-defun-allowed
i would not reccomend BYOL and MAL tbh, usually the ordering of parts in the book just confuses the reader
10:15:02
no-defun-allowed
the really big sin i've spoken up about is trying to write eval before you have a proper environment model, which really throws you off, and if you're writing a Lisp in Lisp quite a bit of both books is not really necessary since they assume you are working in C for BYOB or who knows for MAL
10:19:35
shangul
I think it will be interesting if I build my Lisp in Lisp, with a few blocks as base
10:19:52
phoe
shangul: nah, I'm just being silly - BYOB is an acronym for Bring Your Own Booze, among others
10:20:04
phoe
as for building Lisp in Lisp, you can write a metacircular evaluator - that would be the simplest thing to do
10:20:47
no-defun-allowed
It really isn't hard to make a Lisp out of Lisp pieces. Just implement lambda, cond, defun and copy in some host functions and you're set.
10:22:12
phoe
write a TAGBODY* macro that actually returns the results of the last form via what no-defun-allowed has suggested
10:22:50
White_Flame
yeah, that seems to get around it. Didn't think of that. Was thinking I might have to rewrite this as a LOOP or seomthing
10:23:02
White_Flame
it's emulator guts where it does some work and then goes back and retries prior stuff again
10:25:29
no-defun-allowed
anyways making a metacircular evaluator is really easy, after some practise you can probably write one in about 15 minutes (cause DSLs are fun)
10:27:29
White_Flame
wow, x86 is pretty amazing. SBCL inserted a 10-byte NOP, plus a 1-byte NOP for alignment
10:28:38
White_Flame
shangul: so that the next instruction starts on a 16-byte alignment, for whatever reason
10:30:10
no-defun-allowed
pjb: SICL is probably a bit much for someone who hasn't written an interpreter before
10:34:27
TMA
White_Flame: shangul: you can turn it up to eleven: https://stackoverflow.com/a/36361832
10:36:57
no-defun-allowed
Or, if you don't hate yourself, labels, lambda, cons, eq , cond and quote are also enough to make a decent Lisp.
10:37:27
phoe
no-defun-allowed: it's hard to use CONS without CAR and CDR, you should have those too
10:37:45
shangul
no-defun-allowed, How about https://www.informatimago.com/develop/lisp/com/informatimago/small-cl-pgms/aim-8/index.html ?
10:38:05
no-defun-allowed
Maybe look into some example Kilo LISP programs to see what that does: http://t3x.org/klisp/index.html
10:46:30
no-defun-allowed
And Kilo LISP (and most Lisp making resources) use an environment model, whereas that AIM-8 interpreter uses substitution evaluation which just substitutes, making side effects about as friendly for the user as in Haskell for the programmer
10:49:15
TMA
phoe: that too can be reduced to a dumb enough lambda (like the one scheme with dotted lists for &rest)
11:17:20
no-defun-allowed
phoe: disadvantages of Scheme macros: a bunch. advantages: i don't have to work out the inverse transformation of that cursed LET in my head
11:17:52
no-defun-allowed
and actually there is no transform, i'm just stupid and didn't remember &rest is a variable name too
11:18:37
LdBeth
The inner sin of lexical macros: gives the writer a excuse for not finish the design
11:19:23
no-defun-allowed
also, are there any books beside the end of SICP and Lisp In Small Pieces that go over making a Lisp compiler?
11:25:46
no-defun-allowed
I was thinking of something like "The Implementation of Functional Programming Languages" but on Lisp instead of ML
11:29:32
another-user
i tried (sb-sys:with-deadline (:seconds 3) (uiop:run-program '("aplay" "/dev/urandom")))
11:29:50
ggole
"Essentials of Compilation" is also worth a look, it iterates through a series of more interesting compilers, culminating in a Scheme-like thing
11:30:32
ggole
And roughly a million other papers on functional languages have ideas that can profitably be applied to Lisp
11:31:39
no-defun-allowed
Is this the Essentials of Compilation you have in mind? https://jeapostrophe.github.io/courses/2017/spring/406/notes/book.pdf
11:33:24
no-defun-allowed
I don't know much about compilation to a low level target so I'm not sure I'd get most of the papers you suggest too.
11:35:00
no-defun-allowed
The preface to EoC seems to suggest they tried to make it easy to get into.
11:39:12
ggole
I would start by writing a compiler for a (much) simpler language before tackling something like Common Lisp
12:52:42
TheWild
the question is about the detail of Lisp design. Between (xxx ...) and (... xxx ...), the xxx not only differs in meaning but also refers to something else. Is that correct?
13:15:49
TheWild
I suspect I can define in Lisp such a function/macro that doesn't have their arguments immediately evaluated, just takes them straight as if they were quoted, right?
13:21:55
pjb
TheWild: the value and the function slots were different. The question is when did it occur to somebody to conflate them like in Scheme. Was Scheme the first one?
13:24:04
LdBeth
Until it supports function pointer/higher order function stuff it doesn’t really matter
13:26:36
pjb
phoe: Algol report was published in 1958, just like AIM-8. Since AIM-8 is from March, chances are it was first.
13:27:40
Bike
algol lets you reference functions. i don't know if they're "first class" exactly, but you can pass them as arguments.
13:28:18
pjb
http://www.softwarepreservation.org/projects/ALGOL/report/Algol58_preliminary_report_CACM.pdf/
13:29:27
pjb
This reports refers in the past to dates up to June 2, 1958, so it was posterior to AIM-8. LISP was first!
13:30:03
pjb
Now, of course, JMC heard about the works on Algol, and because they refused to include COND, he forked out LISP and beat them.
13:41:00
beach
TheWild: when the arguments are not evaluated until they are needed, we call it "lazy evaluation" or "outermost evaluation", and it is what Haskell is doing.
13:51:28
pjb
Before macros, there were FEXPR and EXPR. You could write in LISP 1.5 special FEXPR functions that would get their arguments un-evaluated, and they would decide at run-time what to do with them. Normal functions were SUBR or FSUBR. see https://pastebin.com/pSgKMGeZ
14:59:43
TheWild
In the context of designing an experimental dialect of Lisp, from time to time I take a peek how Lisp does a thing
15:00:18
TheWild
(lambda (x) x). I suspected that lambda itself cannot be evaluated any further, and indeed it was the case. (eval (lambda (x) x))
15:01:09
Bike
symbols and cons are the only types of objects the evaluator deals with. everything else is just returned as-is.
15:01:41
Bike
because in CL the only thing allowed at the head of a form is a symbol or (lambda ...)
15:02:23
Bike
"If the car of the compound form is not a symbol, then that car must be a lambda expression,"
15:06:40
TheWild
*lambda form n.* a [form] that is a [list] and that has a first element which is a [lambda expression] representing a [function] to be called on [arguments] which are the result of evaluating subsequent elements of the [lambda form].
15:08:06
TheWild
okay, don't get anything from it. I only suspect that it's not yet a phase in which *eval* works, that's why that expression wasn't considered a lambda
15:10:53
Bike
all the bit i quoted said is that the only thing allowed at the head of a form is a symbol or (lambda ...)