freenode/#lisp - IRC Chatlog
Search
22:04:45
drmeister
Anywho - I get a pass on using Python to write a gdb/lldb extension because I'm developing a Common Lisp implementation to avoid using Python in the rest of my life.
22:05:26
p_l
drmeister: you have my honest condolences that you had to deal with it, and well wishes for your work :)
22:06:32
drmeister
I wish I could convince my colleagues though. They think the height of scientific software development is to develop a Python bindings for Fortan code.
8:22:33
remexre
haven't found anything googling around, but figured I'd ask here before writing my own / deciding not to support unicode
8:35:12
remexre
uh, just assuming all characters are one column wide and leaving a comment, "stick to ascii or implement uax11"
9:14:21
pve
Good morning! A terminology question: is it correct to say that a cons is a "persistent data structure", whereas something like a hash table (at least in CL) is not?
9:16:26
flip214
or do you mean that the in-memory layout is fixed for a CONS cell, but a hash table can change in size?
9:17:09
phoe
if it's https://en.wikipedia.org/wiki/Persistent_data_structure then neither conses nor hash tables in CL are like that
9:18:53
phoe
you can treat both of them as functional data structures which means not mutating them; this means consing up new lists and sharing structure wherever possible, and making new hash tables instead of modifying old ones
9:18:56
pve
yeah, I was looking for a name to distinguish between those kinds of data structures, which at least to me, seem different in how they are usually used
9:21:34
phoe
in Lisp, it's more of a contextual question, especially since conses are CDTs and not ADTs
9:21:49
pve
ok, suppose we don't mutate conses, would "functional data structure" be the correct term?
9:26:46
pve
I'm looking at https://en.wikipedia.org/wiki/Persistent_data_structure and also https://en.wikipedia.org/wiki/Purely_functional_data_structure
9:28:33
phoe
a singly linked list is not such a structure because the result of (CDR '(1 2 3)) does not refer to (1 2 3) anywhere
9:33:51
phoe
OK, "preserve" means a different thing in this context; it doesn't mean explicitly refering to them, it means that the previous values are unchanged
9:38:59
phoe
every purely functional data structure is persistent, but is it true that every persistent data structure is also purely functional?
9:45:09
treflip
Persistent data structures may be implemented in imperative style. There is a great book "Purely Functional Data Structures" by Chris Okasaki, it has a clear explanation of these things in its first chapter IIRC.
9:45:27
sm2n
it's a bit odd because these categories kind of cut across both implementation/interface
9:46:33
sm2n
purely functional is a property of the interface, in that the interface doesn't mutate its arguments
9:46:51
sm2n
persistent is basically an optimization, where shared structure is used wherever possible
9:49:56
treflip
In his book Okasaki divides data structures into persistent and ephemeral, meaning that persistent data structures kinda provide access to their previous states, and ephemeral don't.
9:53:35
pve
treflip: you mean that when you add something to a red-black tree, you get a new tree back?
9:56:21
beach
If you can't access the old three, there is no great difference between a functional an imperative data structure.
9:57:20
beach
Imperative: (insert <thing> <tree>) Functional: (let ((tree (insert <thing> <tree>))))
9:58:00
beach
So, yes, a new tree would be returned, probably sharing structure with the previous one.
9:58:33
beach
But then, a red-black tree is not an abstract data type either, so it's not a great example.
9:59:13
beach
The abstract data type would be a dictionary with a totally ordered key domain, or an editable sequence.
10:00:04
beach
A red-black tree is a way to implement those abstract data types, and the very definition of a red-black tree seems to require destructive modifications to maintain a balanced tree.