libera/#commonlisp - IRC Chatlog
Search
20:45:57
hobo
while reading some CL code, I see something like |blahblah|. I remember seeing that before, but can't recall if there's a special name for that.
20:48:15
ecraven
'|foo bar| is a representation of a symbol with printname "foo bar". the || delimits the symbol name.
20:48:52
ecraven
ah, yes, sorry. I've never seen it used for only part of a name, but it could be, right?
0:24:26
_73
I am trying to define a constant hash-table with `defconstant` by calling a lambda function that returns a hash. When I try to compile it however I get an error that I am trying to redefine the variable, even though I have not previouly defined the constant. Here is the code and error: http://dpaste.com/7M56CUYDN
0:31:21
_73
Catie: I understand now. Would you reccomend just using defvar and being careful, or is there a library that provides a macro that does the right thing like in the docs
0:32:29
pjb
or rather, if you don't want to have anybody use (setf gethash), provide your own immutable API.
0:32:39
Catie
I guess what I usually do is just use defvar, I only use defconstant for very simple constants. I don't know that I'd call it a recommendation though
0:34:28
pjb
the fact that the point of constant variables in CL is to be give a hint to the compiler that it can inline the value (that should therefore be immutable).
0:35:22
pjb
With most processors, only small integers and characters can be put inline with the code. And perhaps a reference, aka a pointer, to things like symbols that are essentially immutable (you cannot change the name of a symbol).
0:38:09
pjb
(defclass immutable-hash () ((hash-table :initarg :hash-table :reader hash-table))) (defmethod get-ih (key (table immutable-hash)) (gethash key (hash-table table))) (defvar *table* (make-instance 'immutable-hash :hash-table (let ((h (make-hash-table))) (setf (gethash :k1 h) 'v1 (gethash :k2 h) 'v2) h)))
0:38:41
pjb
_73: ^ there. Then nothing can change the entries in *table*, since the only operator you have is get-ih which cannot change them.
0:39:21
White_Flame
pjb: there is a very slight advantage in defconstant for references, avoiding an indirection and a TLS check
0:39:39
semz
It documents intent I suppose, and iirc SBCL is not very happy if you use the +constant+ convention for defvar/defparameter. If alexandria is already a dependency, using define-constant instead costs nothing (as opposed to ε otherwise).
0:39:40
White_Flame
but of course you'd have to be accessing that a lot in a tight inner loop to matter
0:39:48
Nilby
Keep in mind that unless you're doing something unusual, it's really only developers who keep recompiling/reloading code, that see defconstant redefinitions.
0:39:51
pjb
_73: of course, it's conventionnal. With closures you could ensure a little restrictions, but even with closures, implementations usually have debugging features to inspect and mutate the contents of a closure.
0:40:33
White_Flame
_73: (defconstant +foo+ <whatever>) doesn't guarantee that the <whatever> won't be mutated; it guarantees that +foo+ won't be mutated. If <whatever> is a hashtable, +foo+ is just a constant reference to it.
0:41:14
White_Flame
and the compiler might inline references to that hashtable object in code that references it. But that doesn't prevent mutating the hashtable's contents
0:41:22
Catie
Would you have to alias +foo+ to be able to mutate it, or can you directly (setf (gethash +foo) ...)?
0:42:26
White_Flame
by the way, the fact that the compiler can inline references to your defconstant values is why it complains about redefining defconstant with a new hashtable when you re-evaluate (defconstant +foo+ (make-hash-table)) again, since the prior compiled code points to the old hashtable
0:46:41
White_Flame
Guest74: if that means one with a perfect hash function, isn't that super dependent on the type of key being stored?
0:49:41
White_Flame
if you give a perfect custom hash function to a supporting implementation's regular hash tables, they'll be O(1) anyway
0:50:09
White_Flame
you'd have to do the 'minimal' feature manually, though, by giving it its size up front
0:51:02
Guest74
a minimal perfect hash table would have less indirection than the hash tables we have.
0:51:53
Alfr
Guest74, unless you plan to lookup key/values only (almost always) and not (almost never) modify the table's content, maintaining a minimal perfect hash table isn't wort the overhead.
0:55:50
Alfr
Guest74, CL doesn't specify one; and iirc the hard part is only to guess a appropriate hash function for the given keys, as you don't need to care about hash collisions, empty entries etc.
1:01:16
semz
I don't see how this is a use case for a perfect hash table to be honest. Surely you'd want to handle invalid data by the (e.g. X11) server or check that the library user provides a valid symbol.
1:03:31
Alfr
Guest74, you may want to simply drop the requirement for the hash-function to be minimal, essentially exchanging memory for reasonable table construction times.
1:06:40
hayley
When in doubt, (defun hash (object) (declare (ignore object)) 1) is a perfectly fine hash function.
1:08:28
White_Flame
Guest74: if your keys are symbols, then storing the color lookups in the symbol-plist would probably be faster & smaller than a hashtable
1:08:50
White_Flame
and the overall overhead would depend on how often you manifest them as strings that need to be interned
1:11:18
_73
Guest74: We want similar things. An internal database of immutable program facts that is optimized for read operations. This is something that is intrinsic and natural to do in Prolog.
1:11:24
semz
Guest74: What does that have to do with whether the other end of the connection or the user provides correct data? Unless the entire range is assigned (which I doubt, but I haven't checked), this is possible so you'd need a separate validation step anyway - and a normal hash table can do this (because a false key would be missing).
1:13:01
Guest74
semz: i don't understand what you're getting at. If a user types a wrong key? why would that break anything?
1:15:11
White_Flame
minimal only saves some static memory footprint, which isn't going to be much. perfect saves some (hopefully nondegenerate) few key comparisons. I wouldn't consider it all that great for a mostly static lookup table, unless there are really egregious circumstances
1:19:05
semz
Guest74: A minimal perfect hash is a bijection from some pre-defined key set to some value set. But your code may not actually hand it a value that lies in the key set, e.g. due to user error or a misbehaving/malicious party on the other side of the connection. In that case, your implementation will either error out or compute a completely wrong value and continue with that. So you need some sort of validation that the input lies in the key set anyway.
1:19:21
Alfr
White_Flame, it's not entirely free, there's a theorem stating that the hash function must be at least of size ln(2) bits/entry.
1:20:18
White_Flame
I didn't say it was free, but it's hard to consider that these costs in these situations are worth much
1:22:13
semz
Yes, which is why the error should be from your code, and not some internal thing from the hash table implementation that may or may not trigger at all
1:22:21
White_Flame
and if size+speed was still a concern, I'd seriously consider the symbol-plist off that
1:22:57
Guest74
semz: I don't know what you're arguing. That some implementation that doesn't seem to exist will be written poorly?
1:24:00
semz
Or that somebody is having "fun" with someone running whatever software ends up using it and manages to coax the program into doing something stupid.
1:24:19
semz
The point I'm arguing is that this problem doesn't even exist if you use the simpler implementation - a normal hash table.
1:25:14
semz
As far as I can tell, you're trading correctness and a lot of effort for basically nothing
1:25:31
Guest74
I think the point you're arguing exists regardless if you're using hashtables at all. To say it is a problem with a minimal perfect hash table that doesn't seem to be implented yet, well, i don't know what to think about that.
1:26:22
Bike
isn't the issue that a minimal perfect hash table by definition is not defined for unexpected inputs, and will in fact return some random crap instead of signaling an error
1:26:40
Alfr
Guest74, it's perfectly reasonable for a gethash like function for a minimal perfect hash table to return any object or even read out of bounds. Given the hash function, it doesn't even need to store the keys, as any key provided will by the very definition of perfect hashing map to some position the implementation assumes to store the key's vale. So, it you feed it something which isn't one of the original keys, the results might be quite unexpected.
1:27:50
Bike
like, if it can recognize an unexpected input and do something else, it's not a minimal perfect hash table.
1:33:42
Bike
yeah but if you want The Speed then you skip the boring stuff you do in a general hash table like make sure the key is actually equivalent
1:34:26
semz
Guest74: This isn't flamebait, I'd sincerely like to know this. Do you have C/C++ experience?
1:40:28
Guest74
we can always ask Vseloved if he ran into any problems. I'll have to check out his library.
1:47:16
Guest74
if you store the key with the value you just check that they are eq before returning whatever the hash pointed to. If you want to reduce the problems of malicious software or continous user error. still seem to get more speed and less memory if that's you're concern.
1:51:03
_73
What do you think of this general pattern for a closure that can perform dynamic dispatch? http://dpaste.com/6WNBXQGKP
1:58:35
Bike
_73: case doesn't evaluate the keys, so you don't want those quotes. also, usually one would just use defstruct or defclass.
1:59:02
Bike
also if you do it this way you don't need an alist, you can just close over three variables, and the binding shouldn't be special.
2:03:43
_73
If I were to use a struct for `people` instead of a length 3 list do I gain anything in type safety?
2:05:31
Bike
sure, it means you don't get garbage out if you accidentally have (fred ("aggravated assault" "23 years")) in there
2:06:00
_73
Guest74: right that is a given but does not matter if I never plan on inserting into the alist
2:07:07
Bike
i could write this something like (defstruct person gender age marital) (defvar *people* (list (cons 'fred (make-person ...)) ...))
2:07:37
Bike
and then maybe (defun gender (name) (person-gender (cdr (assoc name *people*)))) etc instead of the dispatch thing
2:07:58
Bike
also, just realized there's another bug, since assoc returns the pair rather than the value your code won't work
2:08:07
pjb
(defstruct person name gender age marital) (defparameter *persons* (list (make-person :name "Bill") (make-person :name "Mary")))
2:08:29
pjb
(find "Mary" *persons* :key (function person-name) :test (function string-equal)) #| --> #S(person :name "Mary" :gender nil :age nil :marital nil) |#
2:10:47
Bike
really i read too quickly because i read "closure that can perform dynamic dispatch" and thought of the scheme pattern of using closures as objects, but you're not actually doing that here. in fact, if *people* is a special variable like it looks like, there's not even a closure involved
2:26:17
Guest74
oops, i think I need more dbus services besides firefox. Just crashed my browser testing a function. This dbus implementation seems like less of a good idea now that I see there's not much there if you aren't running kde or gnome.
4:31:25
phantomics
Morning beach, is anyone around here using Allegro CL? If so I have something amusing for you to try
4:48:56
ns12
Does "Object-Oriented Programming in COMMON LISP: A Programmer's Guide to CLOS" by Sonya E. Keene describe CLOS as it appears in ANSI Common Lisp? Or is the book about pre-ANSI CLOS?
5:18:16
beach
ns12: ANSI pretty much incorporated CLOS as it was defined, or the subset that was necessary for the standard.