Re: (declare (pure ...))
L > On 10 Feb 2024, at 13:30, Peter Bex wrote: > > On Sat, Feb 10, 2024 at 12:24:36PM +, Pietro Cerutti wrote: >> This is not how I reason about referential transparency. It is a property of >> functions applied to values, not variables. >> The fact that you can define x to different values or even rebind it in the >> scope of a let binding doesn't make (lambda (x) (+ x 1)) less referentially >> transparent. >> If you change the value of a slot of a vector, then the vector has a >> different value than before, even if the same name binds to the value. > > This might be true in an abstract sense, but it isn't true for the > CHICKEN type system. The same vector (e.g. eq? returns #t) is always > the same "value", for purposes of the type system. > > It can have different values inside its slots, which is why we have > to differentiate between pure and clean functions (see my other mail). Oh, I've missed it! I thought it was just some mismatch on the naming in scrutinizer, I had not noticed the different semantics. Thanks! -- Pietro Cerutti I've pledged to give 10% of income to effective charities and invite you to join me. https://givingwhatwecan.org Sent from a small device - please excuse brevity and typos.
Re: (declare (pure ...))
On 2024-02-10 14:28, Peter Bex wrote: CHICKEN's type system differentiates between "pure" and "clean". A "pure" Hope this clears things up a bit! Ah, that's what I was looking for. So I shouldn't declare procedures using vector-ref as pure, but as clean. Now how do I declare a scheme procedure as "clean" -- I don't see that in the manual? I'll check out the source, though grep'ing for vector-ref is obviously not an option. -- Al
Re: (declare (pure ...))
On Sat, Feb 10, 2024 at 12:24:36PM +, Pietro Cerutti wrote: > This is not how I reason about referential transparency. It is a property of > functions applied to values, not variables. > The fact that you can define x to different values or even rebind it in the > scope of a let binding doesn't make (lambda (x) (+ x 1)) less referentially > transparent. > If you change the value of a slot of a vector, then the vector has a > different value than before, even if the same name binds to the value. This might be true in an abstract sense, but it isn't true for the CHICKEN type system. The same vector (e.g. eq? returns #t) is always the same "value", for purposes of the type system. It can have different values inside its slots, which is why we have to differentiate between pure and clean functions (see my other mail). Cheers, Peter signature.asc Description: PGP signature
Re: (declare (pure ...))
On Sat, Feb 10, 2024 at 11:12:04AM +, siiky via wrote: > Hi Al, > > > On a practical level, I would be sad if vector-ref, for example, was > > "impure", and thus compiling a vector-ref invalidated all previously- > > checked globals for the current scope. Likewise, I would prefer to > > declare a procedure using vector-ref as pure, to let csc know that it > > does not modify globals (or the filesystem etc). > > The function vector-ref doesn't stop being pure (i.e. referentially > transparent) depending how you use it. The function is always referentially > transparent -- the expression (vector-ref some-global-vec) isn't. Quoting > from "Functional Programming in C++" by Ivan Čukić: CHICKEN's type system differentiates between "pure" and "clean". A "pure" function has no side effects and will always return the same value given the same input (excluding the environment). A "clean" function does not modify any state, but may return different values at different times depending on the value. That's why vector-ref is marked as "clean" and not "pure" in types.db. A procedure like "not" and all type predicates are marked as "pure". Hope this clears things up a bit! Cheers, Peter signature.asc Description: PGP signature
Re: (declare (pure ...))
> On 10 Feb 2024, at 11:10, Al wrote: > > On 2024-02-10 11:53, Pietro Cerutti wrote: > >> I don't see why vector-ref would be any less pure than, say, a let binding. >> Or do you mean vector-set! ? >> > vector-ref, applied to a global, could return different values even when > called with the same arguments. Between calls, some other code could modify > the contents of the vector. So according to referential transparency, > vector-ref could not be pure. Likewise a function that calls vector-ref could > not be pure. > > Further, according to referential transparency no procedure that *reads* a > global (not just vectors -- even imediate values like numbers, booleans) can > be pure. It might return different values if impure code modifies the global > between calls to the procedure in question. This is not how I reason about referential transparency. It is a property of functions applied to values, not variables. The fact that you can define x to different values or even rebind it in the scope of a let binding doesn't make (lambda (x) (+ x 1)) less referentially transparent. If you change the value of a slot of a vector, then the vector has a different value than before, even if the same name binds to the value. -- Pietro Cerutti I've pledged to give 10% of income to effective charities and invite you to join me. https://givingwhatwecan.org Sent from a small device - please excuse brevity and typos.
Re: (declare (pure ...))
> On 10 Feb 2024, at 11:10, Al wrote: > > On 2024-02-10 11:53, Pietro Cerutti wrote: > >> I don't see why vector-ref would be any less pure than, say, a let binding. >> Or do you mean vector-set! ? >> > vector-ref, applied to a global, could return different values even when > called with the same arguments. Between calls, some other code could modify > the contents of the vector. So according to referential transparency, > vector-ref could not be pure. Likewise a function that calls vector-ref could > not be pure. > > Further, according to referential transparency no procedure that *reads* a > global (not just vectors -- even imediate values like numbers, booleans) can > be pure. It might return different values if impure code modifies the global > between calls to the procedure in question. This is not how I reason about referential transparency. It is a property of functions applied to values, not variables. The fact that you can define x to different values or even rebind it in the scope of a let binding doesn't make (lambda (x) (+ x 1)) less referentially transparent. If you change the value of a slot of a vector, then the vector has a different value than before, even if the same name binds to the value. -- Pietro Cerutti I've pledged to give 10% of income to effective charities and invite you to join me. https://givingwhatwecan.org Sent from a small device - please excuse brevity and typos.
Re: (declare (pure ...))
Hi Al, On a practical level, I would be sad if vector-ref, for example, was "impure", and thus compiling a vector-ref invalidated all previously- checked globals for the current scope. Likewise, I would prefer to declare a procedure using vector-ref as pure, to let csc know that it does not modify globals (or the filesystem etc). The function vector-ref doesn't stop being pure (i.e. referentially transparent) depending how you use it. The function is always referentially transparent -- the expression (vector-ref some-global-vec) isn't. Quoting from "Functional Programming in C++" by Ivan Čukić: > We’re going to define purity more precisely now, through a concept called referential transparency. Referential transparency is a characteristic of expressions, not just functions. Let’s say an expression is anything that specifies a computation and returns a result. We’ll say an expression is referentially transparent if the program wouldn’t behave any differently if we replaced the entire expression with just its return value. If an expression is referentially transparent, it has no observable side effects, and therefore all functions used in that expression are pure. (p.104) I think that part just decides whether the procedure is "pure", for whatever purity means. That doesn't say anything about what compiling a call to such a "pure" procedure means (can memoize the value or not, need to re-check globals or closures afterwards or not etc). Both the Declarations and Types manual pages say clearly it means "referencial transparency." And RE local state, that you asked in another email: my understanding is that that refers to variables belonging to the closure, that survive across calls. E.g.: (define foo (let ((x 0)) (lambda (y) (set! x (add1 x)) (* 2 y siiky
Re: (declare (pure ...))
On 2024-02-10 11:53, Pietro Cerutti wrote: I don't see why vector-ref would be any less pure than, say, a let binding. Or do you mean vector-set! ? vector-ref, applied to a global, could return different values even when called with the same arguments. Between calls, some other code could modify the contents of the vector. So according to referential transparency, vector-ref could not be pure. Likewise a function that calls vector-ref could not be pure. Further, according to referential transparency no procedure that *reads* a global (not just vectors -- even imediate values like numbers, booleans) can be pure. It might return different values if impure code modifies the global between calls to the procedure in question. In contrast, a let binding can only be modified by the code in the current scope. There should still be a way to communicate to the optimizer that vector-ref, or some procedure that uses vector-ref on a global identifier (but does not call set! / vector-set! on globals) does not, uh, modify any globals. -- Al
Re: (declare (pure ...))
> On 10 Feb 2024, at 10:45, Al wrote: > > On 2024-02-10 11:20, Pietro Cerutti wrote: > >> Both Haskell and CHICKEN ultimately compile to obiect code. That is not >> important: the important thing is the abstract machine you're programming >> against. This is why I specified "observable" in my previous reply. > > I agree. And if we step out of the monadic framework for just a bit, you'll > see that there's room for an abstract machine in which purity just means > "does not set! globals". This would still let the optimizer know that globals > do not need to be re-checked after such a procedure is invoked, for example. > I'm not sure if csc really uses the full "referentially transparent" > definition (i.e. memoize-able), or just the "does not modify globals" one. > > > On a practical level, I would be sad if vector-ref, for example, was > "impure", and thus compiling a vector-ref invalidated all previously-checked > globals for the current scope. Likewise, I would prefer to declare a > procedure using vector-ref as pure, to let csc know that it does not modify > globals (or the filesystem etc). I don't see why vector-ref would be any less pure than, say, a let binding. Or do you mean vector-set! ? If the latter, well.. wouldn't your reasoning prevent you from using vector-set! on a global variable? -- Pietro Cerutti I've pledged to give 10% of income to effective charities and invite you to join me. https://givingwhatwecan.org Sent from a small device - please excuse brevity and typos.
Re: (declare (pure ...))
> On 9 Feb 2024, at 21:06, Al wrote: > Hi, > > > what does (declare (pure ..)) mean to csc? Is the function supposed to be > > * only side-effect free, or ... > > * also return the same value when called with the same arguments? Back to your original question, to make sure I understand: can you show an example of a function which respects only one of those two points? -- Pietro Cerutti I've pledged to give 10% of income to effective charities and invite you to join me. https://givingwhatwecan.org Sent from a small device - please excuse brevity and typos.
Re: (declare (pure ...))
On 2024-02-10 11:20, Pietro Cerutti wrote: Both Haskell and CHICKEN ultimately compile to obiect code. That is not important: the important thing is the abstract machine you're programming against. This is why I specified "observable" in my previous reply. I agree. And if we step out of the monadic framework for just a bit, you'll see that there's room for an abstract machine in which purity just means "does not set! globals". This would still let the optimizer know that globals do not need to be re-checked after such a procedure is invoked, for example. I'm not sure if csc really uses the full "referentially transparent" definition (i.e. memoize-able), or just the "does not modify globals" one. On a practical level, I would be sad if vector-ref, for example, was "impure", and thus compiling a vector-ref invalidated all previously-checked globals for the current scope. Likewise, I would prefer to declare a procedure using vector-ref as pure, to let csc know that it does not modify globals (or the filesystem etc). Yeah their wording is different but the meaning is the same, i.e., a --> function will be marked as pure (for the implementation, see the last value returned by validate-type in scrutinizer.scm). I think that part just decides whether the procedure is "pure", for whatever purity means. That doesn't say anything about what compiling a call to such a "pure" procedure means (can memoize the value or not, need to re-check globals or closures afterwards or not etc). -- Al
Re: (declare (pure ...))
> On 10 Feb 2024, at 09:27, Al wrote: > > On 2024-02-10 10:13, Pietro Cerutti wrote: > >> I don't get your question: those two things are the same thing :) >> >> Referential transparency means you can substitute an expression with its >> expansion down to a value. If anything happening in between causes >> (observable *) changes, you can't do it anymore. >> >> (*) modifying the program counter is not an observable change, for example. >> > Those two things are the same thing in Haskell and languages that have a > mathematical model of the program, yes. Scheme is... not that, much of the > time. Chicken is implemented on top of C, so it's even less clear. Both Haskell and CHICKEN ultimately compile to obiect code. That is not important: the important thing is the abstract machine you're programming against. This is why I specified "observable" in my previous reply. > But let's not get theoretical, yes, my question is if csc can (does?) > "memoize" the results of "pure" function. > > > In any case, the definitions I quoted above > > * https://wiki.call-cc.org/man/5/Declarations#pure > > * https://wiki.call-cc.org/man/5/Types#purity > > are not the same thing, so either the one or the other should stand. Though > I'm not sure what "local variables or data contained in local variables" > actually means. I think it means you can't "set!" globals. Yeah their wording is different but the meaning is the same, i.e., a --> function will be marked as pure (for the implementation, see the last value returned by validate-type in scrutinizer.scm). -- Pietro Cerutti I've pledged to give 10% of income to effective charities and invite you to join me. https://givingwhatwecan.org Sent from a small device - please excuse brevity and typos.
Re: (declare (pure ...))
On 2024-02-10 10:13, Pietro Cerutti wrote: I don't get your question: those two things are the same thing :) Referential transparency means you can substitute an expression with its expansion down to a value. If anything happening in between causes (observable *) changes, you can't do it anymore. (*) modifying the program counter is not an observable change, for example. Those two things are the same thing in Haskell and languages that have a mathematical model of the program, yes. Scheme is... not that, much of the time. Chicken is implemented on top of C, so it's even less clear. But let's not get theoretical, yes, my question is if csc can (does?) "memoize" the results of "pure" function. In any case, the definitions I quoted above * https://wiki.call-cc.org/man/5/Declarations#pure * https://wiki.call-cc.org/man/5/Types#purity are not the same thing, so either the one or the other should stand. Though I'm not sure what "local variables or data contained in local variables" actually means. I think it means you can't "set!" globals. -- Al
Re: (declare (pure ...))
> On 10 Feb 2024, at 09:06, Al wrote: > > >>> * only side-effect free, or ... >>> >>> * also return the same value when called with the same arguments? >> >> The first implies the second: to be able to choose from a set of return >> values for the same given argument, you do need to have side-effects, e.g., >> interact with a RNG which maintains state, read from a file, maintain an >> index into a circular vector of results, etc.. >> >> Here's what the docs say: >> http://wiki.call-cc.org/man/5/Declarations#pure >> > "referentially transparent, that is, as not having any side effects". You can > read "the environment" (including all globals) without actually modifying the > environment. Between two applications of the procedure, other impure > procedures may modify the environment. So it's not clear if it means Haskell > monad purity or immutable purity, hence my question. I don't get your question: those two things are the same thing :) Referential transparency means you can substitute an expression with its expansion down to a value. If anything happening in between causes (observable *) changes, you can't do it anymore. (*) modifying the program counter is not an observable change, for example. -- Pietro Cerutti I've pledged to give 10% of income to effective charities and invite you to join me. https://givingwhatwecan.org Sent from a small device - please excuse brevity and typos.
Re: (declare (pure ...))
* only side-effect free, or ... * also return the same value when called with the same arguments? The first implies the second: to be able to choose from a set of return values for the same given argument, you do need to have side-effects, e.g., interact with a RNG which maintains state, read from a file, maintain an index into a circular vector of results, etc.. Here's what the docs say: http://wiki.call-cc.org/man/5/Declarations#pure "referentially transparent, that is, as not having any side effects". You can read "the environment" (including all globals) without actually modifying the environment. Between two applications of the procedure, other impure procedures may modify the environment. So it's not clear if it means Haskell monad purity or immutable purity, hence my question. Furthermore, https://wiki.call-cc.org/man/5/Types#purity says: "Using the (... --> ...) syntax, you can declare a procedure to not modify local state, i.e. not causing any side-effects on local variables or data contained in local variables". -- Al
Re: (declare (pure ...))
> On 9 Feb 2024, at 21:06, Al wrote: > > Hi, > > > what does (declare (pure ..)) mean to csc? Is the function supposed to be > > * only side-effect free, or ... > > * also return the same value when called with the same arguments? The first implies the second: to be able to choose from a set of return values for the same given argument, you do need to have side-effects, e.g., interact with a RNG which maintains state, read from a file, maintain an index into a circular vector of results, etc.. Here's what the docs say: http://wiki.call-cc.org/man/5/Declarations#pure -- Pietro Cerutti I've pledged to give 10% of income to effective charities and invite you to join me. https://givingwhatwecan.org Sent from a small device - please excuse brevity and typos.
Re: (declare (pure ...))
Hi Al, what does (declare (pure ..)) mean to csc? Is the function supposed to be * only side-effect free, or ... * also return the same value when called with the same arguments? I can't remember where `(declare)` is documented, but I believe this [0] is also relevant. [0] https://wiki.call-cc.org/man/5/Types#purity Good luck! siiky
(declare (pure ...))
Hi, what does (declare (pure ..)) mean to csc? Is the function supposed to be * only side-effect free, or ... * also return the same value when called with the same arguments? Thanks, Al
