For those of us who are going to have to learn the ins and outs of Scheme in order to play in this tournament, I’ve got a couple questions:
Why are the terms “passing source code” and “passing a lambda” being used interchangeably? My experience with functional programming does not allow for any inspection into a lambda except by experimentation, whereas “passing the source code” implies more direct knowledge of its internals. It seems to me to be a much more interesting competition if we didn’t have to worry so much about such tangential (if interesting) canonical computer science problems such as parsing in order to play effectively.
As well as quining. I assume that there is some algorithm that will generate a quine program that emulates a specified program. But I’d prefer not to have to deal with the details of Scheme in order to implement this, unless somebody were to convince me that this were sufficiently easy. When my initial reflection of the problem has me desiring to implement solutions where effectiveness is a function of my knowledge of language specifics, I fear we’ve lost the spirit of what this competition should be.
Why are the terms “passing source code” and “passing a lambda” being used interchangeably? My experience with functional programming does not allow for any inspection into a lambda except by experimentation, whereas “passing the source code” implies more direct knowledge of its internals.
I don’t see any other occurrences of “a lambda” on this page, but maybe the original post has been edited.
I would assume that “a lambda” should be taken as short for “a lambda expression”, i.e. an evaluatable s-expression (a form, in Common Lisp terminology; it is unclear to me whether Scheme has a corresponding word). The result of evaluating a lambda expression is not “a lambda”, it is “a procedure [value]”. Procedures (‘functions’ in most languages) have the opaqueness you are thinking of.
(Irrelevant to this question, but relevant to the topic of use/mention, expression/value, syntax/semantics, distinctions in programming: The process of obtaining a procedure/function essentially involves three inputs:
the lambda expression (or other form of function definition),
the environment for free variables (or other form of context/stdlib/set-of-primitives), and
the evaluator (or “the language implementation”)
One of the things language designers can play with is what goes in part 2 and what goes in part 3.)
I think it would be useful for somebody to provide some further insights into what the specifics of the Scheme language imply for the higher level considerations of this competition. Some further questions:
How simple is it to write your program in Scheme to make simple modifications to the passed program, and to call the result? Interesting possibilities here are to insert or remove timing functionality (to, perhaps, beat your opponent to the punch in evaluating the result of passing your function to theirs).
How simple is it to parse a program in Scheme, with Scheme, into an abstract syntax tree for more complex modification and inspection? Does anybody have a resource for this? Interesting possibilities have already been widely discussed here, and involve things such as looking for proofs of cooperability, as well as annoyingly language-specific things like removing stack-length checks.
It appears pretty easy to turn any given Scheme program into a quine, but I agree with another poster that this is unnecessary complexity.
How simple is it to write a program generator in Scheme, in order to do things such as pass the resulting set to the opponent for statistical analysis?
My hope is that intelligent answers to questions such as these will help potential participants evaluate the value of learning language specifics in order to participate in all the theoretical fun.
How simple is it to parse a program in Scheme, with Scheme, into an abstract syntax tree for more complex modification and inspection? Does anybody have a resource for this?
Scheme programs shine at manipulating lists and symbols, and a scheme program is written as a list of symbols. Writing a program generator is trivial. If you know what you’re doing, you can write a basic scheme interpreter, from parser to interpreter, in under four hours.
The book “Structure and Interpretations of Computer Programs” is a classic and freely available online.
For those of us who are going to have to learn the ins and outs of Scheme in order to play in this tournament, I’ve got a couple questions:
Why are the terms “passing source code” and “passing a lambda” being used interchangeably? My experience with functional programming does not allow for any inspection into a lambda except by experimentation, whereas “passing the source code” implies more direct knowledge of its internals. It seems to me to be a much more interesting competition if we didn’t have to worry so much about such tangential (if interesting) canonical computer science problems such as parsing in order to play effectively.
As well as quining. I assume that there is some algorithm that will generate a quine program that emulates a specified program. But I’d prefer not to have to deal with the details of Scheme in order to implement this, unless somebody were to convince me that this were sufficiently easy. When my initial reflection of the problem has me desiring to implement solutions where effectiveness is a function of my knowledge of language specifics, I fear we’ve lost the spirit of what this competition should be.
I don’t see any other occurrences of “a lambda” on this page, but maybe the original post has been edited.
I would assume that “a lambda” should be taken as short for “a lambda expression”, i.e. an evaluatable s-expression (a form, in Common Lisp terminology; it is unclear to me whether Scheme has a corresponding word). The result of evaluating a lambda expression is not “a lambda”, it is “a procedure [value]”. Procedures (‘functions’ in most languages) have the opaqueness you are thinking of.
(Irrelevant to this question, but relevant to the topic of use/mention, expression/value, syntax/semantics, distinctions in programming: The process of obtaining a procedure/function essentially involves three inputs:
the lambda expression (or other form of function definition),
the environment for free variables (or other form of context/stdlib/set-of-primitives), and
the evaluator (or “the language implementation”)
One of the things language designers can play with is what goes in part 2 and what goes in part 3.)
The input to your program will be a quoted list which evaluates to a function.
The wikipedia article on quines contains an example which shouldn’t be too hard to adapt to Scheme.
I think it would be useful for somebody to provide some further insights into what the specifics of the Scheme language imply for the higher level considerations of this competition. Some further questions:
How simple is it to write your program in Scheme to make simple modifications to the passed program, and to call the result? Interesting possibilities here are to insert or remove timing functionality (to, perhaps, beat your opponent to the punch in evaluating the result of passing your function to theirs).
How simple is it to parse a program in Scheme, with Scheme, into an abstract syntax tree for more complex modification and inspection? Does anybody have a resource for this? Interesting possibilities have already been widely discussed here, and involve things such as looking for proofs of cooperability, as well as annoyingly language-specific things like removing stack-length checks.
It appears pretty easy to turn any given Scheme program into a quine, but I agree with another poster that this is unnecessary complexity.
How simple is it to write a program generator in Scheme, in order to do things such as pass the resulting set to the opponent for statistical analysis?
My hope is that intelligent answers to questions such as these will help potential participants evaluate the value of learning language specifics in order to participate in all the theoretical fun.
Scheme programs shine at manipulating lists and symbols, and a scheme program is written as a list of symbols. Writing a program generator is trivial. If you know what you’re doing, you can write a basic scheme interpreter, from parser to interpreter, in under four hours.
The book “Structure and Interpretations of Computer Programs” is a classic and freely available online.