libera/#commonlisp - IRC Chatlog
Search
9:31:40
gin
thanks shka. Is that true in general too? does it take constant time for any proper sequence?
9:34:01
beach
gin: If you think about how lists are represented, you can see that it has to traverse every CONS cell as shka is saying, so there is no way it can be O(1).
9:36:39
beach
gin: And if you don't know how lists are represented, it is time to learn that part. Otherwise, may things will likely confuse you in the future.
9:38:06
beach
... like why (defun push-it (element list) (push element list)) won't "work" as expected.
9:40:04
beach
shka: Indeed. But a significant number of newbies here don't seem to find it useful to read about things like that.
16:05:47
lisp123
Any good resources to learn algorithms when working with trees and also searching / traversing across trees & nodes?
16:07:52
beach
Aho Hopcroft Ullman, "The Design and Analysis of Computer Algorithms" is the classic text.
16:08:57
beach
Apparently, they also wrote "Data Structures and Algorithms" later. I haven't read that one.
16:09:54
beach
Be careful with any old book on data structures and algorithms. I estimate around half of published books get a simple thing like binary search wrong.
16:11:27
beach
Publishing houses will print and sell anything you are willing to write, and they fired all the copy editors decades ago.
16:11:49
beach
Apress seems to be the exception. They recruit qualified editors to screen the material.
16:12:04
lisp123
Yeah, their business models are coming under fire a lot (especially for technical books)
16:12:27
jackdaniel
there is an interesting book that touches this topic in polish "przejęzyczenie" (misspell) - it is a set of interviews with well known translators
16:15:12
beach
Speaking of which, the reason "Lisp in Small Pieces" is better in its English version, is that the translator is also an experienced editor. The original publishing house doesn't have staff like that as far as I know.
16:17:05
beach
As far as I remember, it was just the original text. He later wrote a revised French version, but I don't know more about it.
16:17:44
beach
Though, the translation was made interactively, i.e., they met on a regular basis to discuss the material, so it is not a "blind" translation.
16:19:07
beach
But the translator had knowledge of Lisp, so was able to introduce improvements because of that as well.
16:22:13
jcowan
jackdaniel: I saw a list of Russian surnames somewhere that look scary even to Russians because they are of (remote) Polish origin:
16:23:27
jcowan
Not as clever as the English title, which shows how flexible (twisty) English actually is
16:24:00
beach
hendursaga: No, I am familiar with the French one because I used it in a course, and with the English one because I know the translator.
16:24:27
jcowan
jackdaniel: Here's a few of them: "Yastrzhembsky (the diplomat), Krzhizhanovsky (the writer), and even Przhevalsky (of the horse)."
16:27:11
jackdaniel
I think that Russian nicknames are written in cirillic :) that would be Jastrzębski (Hawk-ski), Chrzanowski (horserasish-ski) and Przewalski (bulldoze-ski); sorry for bringing offtopic :)
16:40:36
Bike
a little while back i wrote up this thing for a type-expand extension https://github.com/Bike/clhs-extension/tree/main/type-expand and i was thinking of filing a pull request to add it (i.e. type-expand(-1), not the other) to ECL, but i was wondering if anyone had opinions on typexpand versus type-expand versus typeexpand
16:43:32
jackdaniel
following convention used for macroexpand that would be typeexpand (and typeexpand-1)
16:44:02
hendursaga
beach: not sure how complete/accurate this is but.. https://github.com/ilammy/lisp
16:44:14
Bike
right, but the double e is weird so maybe it should be type-expand, and alternately maybe it should be typexpand to collapse the double e (this is what sbcl does)
16:53:40
jcowan
jackdaniel: Sure, I just can't type Cyrillic easily so I do Russian in romanization.
16:54:28
jcowan
Part of the trouble is the cyrillicization of "rzh" as such rather than using just zh (or sh)
16:55:11
jcowan
So if I happen to mention Przhewalski's horse (rare, but not unknown), I call it "Shevalski's horse" (with silent "p" as usual in English).
16:55:14
Bike
ecl actually builds on my home machine without the weird problems about floating point i had before, neat
16:57:30
Bike
i think this was probably more an issue with my build environment than ecl. plus i didn't try very hard to figure it out
16:59:13
Bike
i expect there are very few users of sbcl's typexpand to begin with, so renaming things shouldn't be too horrible if it comes to that
16:59:55
lisp123
A philosophical question: How do you choose to order your functions? Say you have A calling B calling C calling D. Do you write D at the top of your file, then C, then B, then A or the other way? Writing bottom up means you will progressively build up the functions so easier to follow (somewhat), whereas writing top down is easier to understand the purpose (since A will contain the main goal, and the remaining functions help it achieve it)
17:01:24
mfiano
I suppose it depends if any are proclaimed inline, and if they even belong next to each other (same file, same package, etc)
17:04:18
White_Flame
I have big demarcations between sections of the file, and keep tightly/privately correlated functions together. Ordering has more to do how commenting works best
17:04:22
lisp123
I started doing topdown (start with exported functions and then working one's way down), although I'm finding today if I write literate programs, bottom up is easier
17:04:59
White_Flame
any aesthetics of your source code files should be driven by documentation/readability, not the code specifically
17:06:13
lisp123
White_Flame: Although one could argue having certain conventions (regardless of the code), helps in consistency - if every file is top down for example, then one would come to expect that format, and vice versa
17:17:12
Bike
jackdaniel: if i want to add exported symbols to the EXT package, do i add them in symbols_list.h somewhere or is there a preferred procedure?
17:22:52
jackdaniel
yes, you add them to symbols_list.h; also you need to add the function to src/h/external.h with a C name declared in symbols_list.h (i.e cl_type_expand) and src/cmp/proclamations.lsp
17:24:04
jackdaniel
it doesn't, but if it is an exported interface it should (so C programmers may invoke it:)
17:24:32
jackdaniel
also you have a gain of direct call instead of dispatching the symbol (in compiled code)
17:25:47
jackdaniel
whatever you put in symbols_list as the C name that name will be used in transpiled code; symbols_list.h is arranged alphabetically afair
18:33:39
scymtym
Bike: would it make sense for TYPE-EXPAND and TYPE-EXPAND-1 to specify the exceptional situations that TYPE-SPECIFIER is not a valid type specifier and ENV is not an environment?
18:37:35
Bike
scymtym: maybe, but i mentally filed that under https://github.com/s-expressionists/wscl/blob/invalid-type-specifier/wscl-issues/proposed/invalid-type-specifier
20:32:13
lisp123
Is there some sort of override on the last cdr being nil not being recognised as an element? Is this why some functions require proper lists as inputs?
20:35:23
aeth
list iteration for the most part is effectively doing MAPCAR with emphasis on CAR (well, in that case, MEMBER could be implemented with MAPLIST because it needs to return the sublist, but can't be implemented with MAPCAR, but it still mostly cares about the CAR)
20:40:18
aeth
A possible implementation of MEMBER (excluding the keyword arguments) could be something like: (defun member* (item list) (maplist (lambda (sublist) (if (eql (car sublist) item) (return-from member* sublist) nil)) list) nil)
20:43:42
aeth
'(1 2 3 NIL) would return (NIL) in our hypothetical, while '(1 2 3 . NIL) i.e. '(1 2 3) would still just be NIL
20:44:36
lisp123
and there is some check that the cdr is nil and then the function stops there (hence the requirement for list to a proper list)
20:44:48
aeth
it will error at some point: if it turns out that the last "sublist" is '(1 . 2) instead of '(1 . NIL)
20:45:21
aeth
MEMBER and the things that you could trivially implement MEMBER with (such as MAPLIST) check for a proper list at the very end, because it's more efficient that way.
20:45:48
lisp123
so basically because (car nil) is defined, it works --> but if the last item was 2 (as in your example), the error comes from (car 2)?
20:45:50
aeth
i.e. it's more efficient to assume that it's the correct input, and fail on the rare case when it's not, rather than slowing down the common path for the fast error path
20:46:23
aeth
lisp123: the error comes because '(1 . 2) isn't a proper list, so the sublist assumption is violated. You just won't find out until the final iteration
20:47:12
lisp123
aeth: (sorry to be obtuse), but that specific error occurs in the final iteration since car will no longer work on "2" as in your example?
20:47:55
_death
as an exercise, you can try to implement the basic MEMBER operation without using any of the existing mapping functions
20:48:28
aeth
lisp123: it doesn't work because list-iteration (or especially sequence-iteration that works on lists) tends to iterate until the CDR is NIL, so when that's not the case, the assumption has been violated. You usually have to work with dotted lists yourself.
20:48:51
aeth
worst case is actually infinite loop, never reaching the NIL. The built-ins are just friendly enough to fail with an error
20:49:09
aeth
although I guess you'd (cdr '(1 . 2)) treat 2 as a sublist, then try to take the car/cdr of it and error
20:49:48
lisp123
_death: I can now see the value of doing this, when I get time I'll try and re-implement the CL functions from scratch
20:50:32
aeth
right, what you'd want to do as an exercise (or for real, if you really need this behavior) is rewrite sequence/proper-list built-in functions on top of LOOP/DO/etc. to handle dotted lists
20:50:56
aeth
you lose elegance because now you're not sure that the CDR is a CONS-or-NIL, unlike a proper list.
20:51:41
lisp123
aeth: unfortunatley, there's a million and one ways to handle lists --> Indeed, it can get confusing at times. But at least today I finally learned WHY i needed to use proper lists (vs. just the standard says so)
20:51:49
aeth
oh, and you could also do tail recursion locally inside of LABELS (and arguably this is the most elegant way), it just won't be guaranteed to work, unlike in Scheme
20:52:10
_death
lisp123: actually it's very important that you do this and similar exercises if you plan on using Lisp, because they require you to learn and understand fundamental concepts
20:52:52
aeth
and sometimes abstractions do break down and you're just stuck working with raw sublists/CONSes inside of LOOP (or similar)
20:53:41
aeth
you might also want to write your own cons-like thing, in which case you don't get access to any of the built-ins, but the API is well-known (so, foo-car, foo-cdr, foo-cons, etc.)
20:54:32
lisp123
_death: so much to learn, so little time ;) I've decided to go down the path of build first, fix later - it optimises the process and IMO one learns more from making mistakes and fixing them. Otherwise I would be stuck with too many books and concepts to read, and then forget it all anyway
20:55:14
_death
lisp123: this is not a good approach when it comes to concepts fundamental to Lisp, such as conses and atoms
20:57:53
_death
lisp123: the book ANSI Common Lisp is not long and contains good exercises.. the two first chapters are available on Graham's site.. there are other basic sets of exercises on the internet, such as "ninty nine Lisp problems" or "Lisp koans", though it's been a long time since I checked them out and I'm not sure about their quality
20:57:53
lisp123
_death: you are probably right :) I'll try and do it (re-do all the basic functions to understand how they exactly work) sooner rather than later
21:04:06
lisp123
_death: thanks, I read that book. And I've been reading / re-reading CLTL2e a lot (have a hard copy on my desk :D). But this has been a very good discussion (thanks aeth in particular), since even the CLHS isn't 100% precise on the implementation details for MEMBER, a lot of it must be from other parts (quoting the CLHS: " each search list for item or for a top-level element that satisfies the test. The argument to the predicate function is
21:05:46
_death
lisp123: if you read ANSI Common Lisp but didn't do the exercises, my advice is to go back and do them
21:08:05
_death
(actually, the traversal rules link is not helpful.. but if you click on the "element" link to the glossary you can see what is meant)