![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
Lua closures vs OOP object instances vs Haskell partially applied functions (vs clojure closures)
---
---
thinking about data constructors as a type-within-a-type:
yeah, we could abolish them and replace with typeclasses, and prohibit switches (case statements) on them, but then how would we implement destructuring binds?
this suggests three things:
1) when we say we want a language based around labeled graphs/dicts/trees instead of lists, perhaps a lot of what we mean is: we want a structural type system that supports labeled arcs and that supports destructuring bind based on these
2) if there is a structural type system which is fixed/special/privilaged (as opposed to ADTs), then this provides further support for the need for something like Views
3) but perhaps we also still want to be able to do stuff like: f(list): case list is NIL: do something case list is CONS(x): do something with x
even if we have typeclasses (interface-like open data types) instead of ADTs with a closed (final) list of constructors for each type defined when the type is defined. How to do that? Do we allow the implementations of the typeclass to expose an interface to say that a given object 'acts like CONS(x) in case statements/destructuring binds, and to get x call a specific function on it...')
if this is feasible it seems preferable to hardcoding a structural type system and allowing only that for destructuring bind
hmm, yeah, i guess you can see the data constructors as constructors for a typeclass, that form part of its interface. then you could have a __which function for each objects that asks it which constructor it wants to be (or even __areYou that allows it to say True or False to each constructor)
if you ue __which instead of __areYou then you can statically guarantee that each object is at least one of the allowed constructors at any time, which allows for 'closed' data types and probably exhaustive case statements. how do ADTs and destructuring bind and induction over a sequence mesh with dicts?
maybe just like lists, in that we extract an iterator by pretending that dicts have two constructors, addItem and oldDict, and each dict is constructed by addItem(key, value, olddict), starting with emptyDict()?
but if we have __which is that similar to imposing an ordering on the keys? it doesn't have to but it seems uncomfortably close..
we don't have tail() as a constructor? i guess not, b/c we don't for lists---
from http://list.hypothes.is/archive/dev/2014-09/0000017.html
Date: Wed, 24 Sep 2014 18:40:30 -0700 Subject: [h-dev] Proposal: Best Practices for Modules From: Randall Leeds
....
The guiding document I favor at this point and from which I'm taking my cues is the "Best Practices for App Structure" guidelines [1] Google seems to be using internally.
These are the desired properties I have for our best practices:
1. Simple, familiar, memorable, guidelines for descriptive file names and hierarchies 2. DRY [2] 3. server-side module system ready 4. Bower friendly 5. Isolation of components 6. Smooth transition from in-tree to separated component repos as we grow 7. Less build maintenance 8. Simpler dependency graph for angular imports through component opacity.
These drove me to select the above referenced document. The example at the bottom is most comprehensive.
Steps I'd like to take:
1. Tear down /vendor and add /components
Our main application routing and configuration can live in a top-level app.coffee still, but most of our directives, services, filters, etc should be broken into components and placed in /components. It's important that no .coffee files are in /components, but that everything has its own directory. The motivation is that by doing it this way there is a subtree that contains the changes to each component, making it much easier to break components out into their own repo when that inevitably becomes useful. It also means that we can treat this same directory as our bower components directory and use bower to fetch, install, and update our vendorized libs right alongside the ones in tree.
2. Adopt naming conventions for angular component files
I'm starting to warm up to foo-directive.coffee and foo-controller.coffee. It makes it super easy to know where things are when you're looking at the files.
3. Work on our inter-component dependency granularity
This is easiest to see by example. Right now we have a directory scripts/helpers. Inside this is "form-helpers" and it defines the angular module "h.helpers.formHelpers".
That module name is fine if we were simply using it to obviate the need for a particular order of concatenation when exporting the "h.helpers" module by having it depend on each of its subcomponents. However, our other modules outside helpers should never refer to this, but only to "h.helpers" otherwise the public/private line for a module gets really blurry.
4. Prepare to move to a server-side module system and build step
Our assets.yaml is getting unwieldy. Even if we were doing our build in JS, as we've talked about previously, whatever system we use would have to list all these components anyway. Totally separate from the language issue, we can vastly improve the situation by using a module system. I'm extremely partial to browserify, so unless there's a strong objection for some reason, I'm going to eventually bring that into our stack.
This point relates to number 3, above. Having an angular module like "h.helpers" declare "h.helpers.formHelpers" as a dependency is quite redundant if its file also had "require('./form-helpers')". Using a module system here means we can declare the angular module at the top of the file using the 3-arity call signature of angular.module, then require() the rest of the files, each of which can append to the module using the 1-arity form.
No:
foo.coffee angular.module('foo', 'foo.barDirective', [optional configure function])
barDirective.coffee angular.module('foo.barDirective', ['ui.bootstrap'], [optional configure function]) .directive('bar', -> ...)
Yes:
foo.coffee angular.module('foo', ['ui.bootstrap'], [optional configure function]) require('./barDirective')
barDirective.coffee angular.module('foo').directive('bar', -> ...)
Notice how there's no circular import because barDirective.coffee can use the retrieval, 1-arity form of angular.module since it was defined already by foo.coffee before barDirective was required and there's no need for a separate angular module for barDirective.
This also forces all configuration into a single configure callback for the angular module and lifts all the dependencies into its declaration ('ui.bootstrap' in this example).
The result is that our build system need only point to foo.coffee and the rest is handled by browserify and one can know all the dependencies of the foo module and see all its bootstrap configuration code by looking at one file, foo.coffee.
5. Use bower for our vendor components.
Enough said.
6. Consistent namespaces, prefix injection names, and opaque components
No: angular.module('h.services').service('foo') angular.module('h.auth.session').service('session') angular.module('h', ['h.helpers.formHelpers'])
Yes: angular.module('h').service('hFoo') angular.module('h.auth').service('hSession') angular.module('h', ['h.helpers'])
Three guidelines, one for each of the above lines:
The last of these three guidelines does not apply to situations where the namespace is actually split across separately distributed modules that relate to one another but do not necessarily have dependency relationships. For instance, we might have 'h.auth.persona' and 'h.auth.openid' which are separate components where 'auth' is used as a namespace only and there is no 'h.auth' component.
....
[1] https://docs.google.com/document/d/1XXMvReO8-Awi1EZXAXS4PzDzdNvV6pGcuaF4Q9821Es/pub
the Haskell GHC STG core language, as mostly described in http://www.haskell.org/haskellwiki/Ministg and section 3 ('language') of the paper Simon Marlow and Simon Peyton Jones, How to make a fast curry: push/enter vs eval/apply, made an impact on me. This appears to be 'the roots of Haskell' and it's pretty simple.
i woke up today feeling like there is a thought buried in my mind regarding the guile VM, but i don't know what it is. Maybe it is just an obsessive goal of inventorying the remaining VM instructions. For reference, here is what my instruction looks like as of this time (i guess i should look over this and see if i have any thoughts):
Lexical Environment Instructions:
These instructions access and mutate the lexical environment of a compiled procedure—its free and bound variables.
Top-Level Environment Instructions:
These instructions access values in the top-level environment: bindings that were not lexically apparent at the time that the code in question was compiled. The location in which a toplevel binding is stored can be looked up once and cached for later. The binding itself may change over time, but its location will stay constant. Currently only toplevel references within procedures are cached, as only procedures have a place to cache them, in their object tables.
Procedure Call and Return Instructions: todo
Function Prologue Instructions:
Trampoline Instructions:
Branch Instructions:
Data Constructor Instructions:
Loading Instructions:
Dynamic Environment Instructions:
Miscellaneous Instructions:
Inlined Scheme Instructions:
Inlined Mathematical Instructions:
Inlined Bytevector Instructions:
thoughts: types of instructions are:
"inlined scheme instructions" catches my eye; i glanced at them yesterday but didnt read them; they are:
" 9.3.6.11 Inlined Scheme Instructions
The Scheme compiler can recognize the application of standard Scheme procedures. It tries to inline these small operations to avoid the overhead of creating new stack frames.
Since most of these operations are historically implemented as C primitives, not inlining them would entail constantly calling out from the VM to the interpreter, which has some costs—registers must be saved, the interpreter has to dispatch, called procedures have to do much type checking, etc. It’s much more efficient to inline these operations in the virtual machine itself.
All of these instructions pop their arguments from the stack and push their results, and take no parameters from the instruction stream. Thus, unlike in the previous sections, these instruction definitions show stack parameters instead of parameters from the instruction stream. " Instruction: not x Instruction: not-not x: what is this? Instruction: eq? x y: " #t if x and y are the same object, except for numbers and characters...Numbers and characters are not equal to any other object, but the problem is they’re not necessarily eq? to themselves either. This is even so when the number comes directly from a variable...(let ((n (+ 2 3))) (eq? n n)) ⇒ *unspecified*...Generally eqv? below should be used when comparing numbers or characters...It’s worth noting that end-of-list (), #t, #f, a symbol of a given name, and a keyword of a given name, are unique objects. Instruction: not-eq? x y Instruction: null? Instruction: not-null? Instruction: eqv? x y: "Return #t if x and y are the same object, or for characters and numbers the same value....On objects except characters and numbers, eqv? is the same as eq? above, it’s true if x and y are the same object." Instruction: equal? x y: "Return #t if x and y are the same type, and their contents or value are equal. For a pair, string, vector, array or structure, equal? compares the contents, and does so using the same equal? recursively, so a deep structure can be traversed....For other objects, equal? compares as per eqv? above, which means characters and numbers are compared by type and value (and like eqv?, exact and inexact numbers are not equal?, even if their value is the same)." Instruction: pair? x y Instruction: list? x Instruction: set-car! pair x: "Stores value in the car field of pair." Instruction: set-cdr! pair x Instruction: cons x y Instruction: car x Instruction: cdr x Instruction: vector-ref x y Instruction: vector-set x n y Instruction: struct? x Instruction: struct-ref x n Instruction: struct-set x n v Instruction: struct-vtable x: i think more than just the methods: "The vtable is effectively the type of the structure...Every vtable has a field for the layout of their instances, a field for the procedure used to print its instances, and a field for the name of the vtable itself" Instruction: class-of x: "Return the GOOPS class of any Scheme value." Instruction: slot-ref struct n Instruction: slot-set struct n x
" Inlined implementations of their Scheme equivalents.
Note that caddr and friends compile to a series of car and cdr instructions. "
my reduced version of those:
later i also looked at Data Constructors, here is my reduced version:
also note:
"
Next: rnrs unicode, Previous: Library Usage, Up: R6RS Standard Libraries [Contents][Index] 7.6.2.2 rnrs base
The (rnrs base (6)) library exports the procedures and syntactic forms described in the main section of the Report (see R6RS Base library in The Revised^6 Report on the Algorithmic Language Scheme). They are grouped below by the existing manual sections to which they correspond.
Scheme Procedure: boolean? obj Scheme Procedure: not x
See Booleans, for documentation.
Scheme Procedure: symbol? obj Scheme Procedure: symbol->string sym Scheme Procedure: string->symbol str
See Symbol Primitives, for documentation.
Scheme Procedure: char? obj Scheme Procedure: char=? Scheme Procedure: char<? Scheme Procedure: char>? Scheme Procedure: char<=? Scheme Procedure: char>=? Scheme Procedure: integer->char n Scheme Procedure: char->integer chr
See Characters, for documentation.
Scheme Procedure: list? x Scheme Procedure: null? x
See List Predicates, for documentation.
Scheme Procedure: pair? x Scheme Procedure: cons x y Scheme Procedure: car pair Scheme Procedure: cdr pair Scheme Procedure: caar pair Scheme Procedure: cadr pair Scheme Procedure: cdar pair Scheme Procedure: cddr pair Scheme Procedure: caaar pair Scheme Procedure: caadr pair Scheme Procedure: cadar pair Scheme Procedure: cdaar pair Scheme Procedure: caddr pair Scheme Procedure: cdadr pair Scheme Procedure: cddar pair Scheme Procedure: cdddr pair Scheme Procedure: caaaar pair Scheme Procedure: caaadr pair Scheme Procedure: caadar pair Scheme Procedure: cadaar pair Scheme Procedure: cdaaar pair Scheme Procedure: cddaar pair Scheme Procedure: cdadar pair Scheme Procedure: cdaadr pair Scheme Procedure: cadadr pair Scheme Procedure: caaddr pair Scheme Procedure: caddar pair Scheme Procedure: cadddr pair Scheme Procedure: cdaddr pair Scheme Procedure: cddadr pair Scheme Procedure: cdddar pair Scheme Procedure: cddddr pair
See Pairs, for documentation.
Scheme Procedure: number? obj
See Numerical Tower, for documentation.
Scheme Procedure: string? obj
See String Predicates, for documentation.
Scheme Procedure: procedure? obj
See Procedure Properties, for documentation.
Scheme Syntax: define name value Scheme Syntax: set! variable-name value
See Definition, for documentation.
Scheme Syntax: define-syntax keyword expression Scheme Syntax: let-syntax ((keyword transformer) …) exp1 exp2 … Scheme Syntax: letrec-syntax ((keyword transformer) …) exp1 exp2 …
See Defining Macros, for documentation.
Scheme Syntax: identifier-syntax exp
See Identifier Macros, for documentation.
Scheme Syntax: syntax-rules literals (pattern template) ...
See Syntax Rules, for documentation.
Scheme Syntax: lambda formals body
See Lambda, for documentation.
Scheme Syntax: let bindings body Scheme Syntax: let* bindings body Scheme Syntax: letrec bindings body Scheme Syntax: letrec* bindings body
See Local Bindings, for documentation.
Scheme Syntax: let-values bindings body Scheme Syntax: let*-values bindings body
See SRFI-11, for documentation.
Scheme Syntax: begin expr1 expr2 ...
See begin, for documentation.
Scheme Syntax: quote expr Scheme Syntax: quasiquote expr Scheme Syntax: unquote expr Scheme Syntax: unquote-splicing expr
See Expression Syntax, for documentation.
Scheme Syntax: if test consequence [alternate] Scheme Syntax: cond clause1 clause2 ... Scheme Syntax: case key clause1 clause2 ...
See Conditionals, for documentation.
Scheme Syntax: and expr ... Scheme Syntax: or expr ...
See and or, for documentation.
Scheme Procedure: eq? x y Scheme Procedure: eqv? x y Scheme Procedure: equal? x y Scheme Procedure: symbol=? symbol1 symbol2 ...
See Equality, for documentation.
symbol=? is identical to eq?.
Scheme Procedure: complex? z
See Complex Numbers, for documentation.
Scheme Procedure: real-part z Scheme Procedure: imag-part z Scheme Procedure: make-rectangular real_part imaginary_part Scheme Procedure: make-polar x y Scheme Procedure: magnitude z Scheme Procedure: angle z
See Complex, for documentation.
Scheme Procedure: sqrt z Scheme Procedure: exp z Scheme Procedure: expt z1 z2 Scheme Procedure: log z Scheme Procedure: sin z Scheme Procedure: cos z Scheme Procedure: tan z Scheme Procedure: asin z Scheme Procedure: acos z Scheme Procedure: atan z
See Scientific, for documentation.
Scheme Procedure: real? x Scheme Procedure: rational? x Scheme Procedure: numerator x Scheme Procedure: denominator x Scheme Procedure: rationalize x eps
See Reals and Rationals, for documentation.
Scheme Procedure: exact? x Scheme Procedure: inexact? x Scheme Procedure: exact z Scheme Procedure: inexact z
See Exactness, for documentation. The exact and inexact procedures are identical to the inexact->exact and exact->inexact procedures provided by Guile’s code library.
Scheme Procedure: integer? x
See Integers, for documentation.
Scheme Procedure: odd? n Scheme Procedure: even? n Scheme Procedure: gcd x ... Scheme Procedure: lcm x ... Scheme Procedure: exact-integer-sqrt k
See Integer Operations, for documentation.
Scheme Procedure: = Scheme Procedure: < Scheme Procedure: > Scheme Procedure: <= Scheme Procedure: >= Scheme Procedure: zero? x Scheme Procedure: positive? x Scheme Procedure: negative? x
See Comparison, for documentation.
Scheme Procedure: for-each f lst1 lst2 ...
See SRFI-1 Fold and Map, for documentation.
Scheme Procedure: list elem …
See List Constructors, for documentation.
Scheme Procedure: length lst Scheme Procedure: list-ref lst k Scheme Procedure: list-tail lst k
See List Selection, for documentation.
Scheme Procedure: append lst … obj Scheme Procedure: append Scheme Procedure: reverse lst
See Append/Reverse, for documentation.
Scheme Procedure: number->string n [radix] Scheme Procedure: string->number str [radix]
See Conversion, for documentation.
Scheme Procedure: string char ... Scheme Procedure: make-string k [chr] Scheme Procedure: list->string lst
See String Constructors, for documentation.
Scheme Procedure: string->list str [start [end]]
See List/String Conversion, for documentation.
Scheme Procedure: string-length str Scheme Procedure: string-ref str k Scheme Procedure: string-copy str [start [end]] Scheme Procedure: substring str start [end]
See String Selection, for documentation.
Scheme Procedure: string=? s1 s2 s3 … Scheme Procedure: string<? s1 s2 s3 … Scheme Procedure: string>? s1 s2 s3 … Scheme Procedure: string<=? s1 s2 s3 … Scheme Procedure: string>=? s1 s2 s3 …
See String Comparison, for documentation.
Scheme Procedure: string-append arg …
See Reversing and Appending Strings, for documentation.
Scheme Procedure: string-for-each proc s [start [end]]
See Mapping Folding and Unfolding, for documentation.
Scheme Procedure: + z1 ... Scheme Procedure: - z1 z2 ... Scheme Procedure: * z1 ... Scheme Procedure: / z1 z2 ... Scheme Procedure: max x1 x2 ... Scheme Procedure: min x1 x2 ... Scheme Procedure: abs x Scheme Procedure: truncate x Scheme Procedure: floor x Scheme Procedure: ceiling x Scheme Procedure: round x
See Arithmetic, for documentation.
Scheme Procedure: div x y Scheme Procedure: mod x y Scheme Procedure: div-and-mod x y
These procedures accept two real numbers x and y, where the divisor y must be non-zero. div returns the integer q and mod returns the real number r such that x = q*y + r and 0 <= r < abs(y). div-and-mod returns both q and r, and is more efficient than computing each separately. Note that when y > 0, div returns floor(x/y), otherwise it returns ceiling(x/y).
(div 123 10) ⇒ 12
(mod 123 10) ⇒ 3
(div-and-mod 123 10) ⇒ 12 and 3
(div-and-mod 123 -10) ⇒ -12 and 3
(div-and-mod -123 10) ⇒ -13 and 7
(div-and-mod -123 -10) ⇒ 13 and 7
(div-and-mod -123.2 -63.5) ⇒ 2.0 and 3.8
(div-and-mod 16/3 -10/7) ⇒ -3 and 22/21Scheme Procedure: div0 x y Scheme Procedure: mod0 x y Scheme Procedure: div0-and-mod0 x y
These procedures accept two real numbers x and y, where the divisor y must be non-zero. div0 returns the integer q and mod0 returns the real number r such that x = q*y + r and -abs(y/2) <= r < abs(y/2). div0-and-mod0 returns both q and r, and is more efficient than computing each separately.
Note that div0 returns x/y rounded to the nearest integer. When x/y lies exactly half-way between two integers, the tie is broken according to the sign of y. If y > 0, ties are rounded toward positive infinity, otherwise they are rounded toward negative infinity. This is a consequence of the requirement that -abs(y/2) <= r < abs(y/2).
(div0 123 10) ⇒ 12
(mod0 123 10) ⇒ 3
(div0-and-mod0 123 10) ⇒ 12 and 3
(div0-and-mod0 123 -10) ⇒ -12 and 3
(div0-and-mod0 -123 10) ⇒ -12 and -3
(div0-and-mod0 -123 -10) ⇒ 12 and -3
(div0-and-mod0 -123.2 -63.5) ⇒ 2.0 and 3.8
(div0-and-mod0 16/3 -10/7) ⇒ -4 and -8/21Scheme Procedure: real-valued? obj Scheme Procedure: rational-valued? obj Scheme Procedure: integer-valued? obj
These procedures return #t if and only if their arguments can, respectively, be coerced to a real, rational, or integer value without a loss of numerical precision.
real-valued? will return #t for complex numbers whose imaginary parts are zero.
Scheme Procedure: nan? x Scheme Procedure: infinite? x Scheme Procedure: finite? x
nan? returns #t if x is a NaN value, #f otherwise. infinite? returns #t if x is an infinite value, #f otherwise. finite? returns #t if x is neither infinite nor a NaN value, otherwise it returns #f. Every real number satisfies exactly one of these predicates. An exception is raised if x is not real.
Scheme Syntax: assert expr
Raises an &assertion condition if expr evaluates to #f; otherwise evaluates to the value of expr.
Scheme Procedure: error who message irritant1 ... Scheme Procedure: assertion-violation who message irritant1 ...
These procedures raise compound conditions based on their arguments: If who is not #f, the condition will include a &who condition whose who field is set to who; a &message condition will be included with a message field equal to message; an &irritants condition will be included with its irritants list given by irritant1 ....
error produces a compound condition with the simple conditions described above, as well as an &error condition; assertion-violation produces one that includes an &assertion condition.
Scheme Procedure: vector-map proc v Scheme Procedure: vector-for-each proc v
These procedures implement the map and for-each contracts over vectors.
Scheme Procedure: vector arg … Scheme Procedure: vector? obj Scheme Procedure: make-vector len Scheme Procedure: make-vector len fill Scheme Procedure: list->vector l Scheme Procedure: vector->list v
See Vector Creation, for documentation.
Scheme Procedure: vector-length vector Scheme Procedure: vector-ref vector k Scheme Procedure: vector-set! vector k obj Scheme Procedure: vector-fill! v fill
See Vector Accessors, for documentation.
Scheme Procedure: call-with-current-continuation proc Scheme Procedure: call/cc proc
See Continuations, for documentation.
Scheme Procedure: values arg … Scheme Procedure: call-with-values producer consumer
See Multiple Values, for documentation.
Scheme Procedure: dynamic-wind in_guard thunk out_guard
See Dynamic Wind, for documentation.
Scheme Procedure: apply proc arg … arglst
See Fly Evaluation, for documentation. "
---
if we are going to interpret by walking the AST, how to efficiently represent the AST in memory? how to efficiently represent S-exprs in memory? but Oot has dicts (labeled arcs), not just lists (sequences). So how to efficiently represent a nested dict/labeled tree in memory? do we want to assume that each node has only a few children, so just enumerate them and search them all (or maybe sort alphabetically and then binary search?), rather than making a hash table for each dict?
according to http://www.cl.cam.ac.uk/~mom22/fp/lec6-interp.pdf , Lisp S-exprs are:
so i guess S-exprs fundamentally use linked lists. This gives O(1) insertion and deletion in the middle, but we may only care about pushing and popping at head, esp. if we just want unordered dicts. But maybe we want ordered dicts. But if we assume the outdegree of each node is small (for the AST use-case), then it's not too costly to rearrange the list when needed.
sometimes backspace backspace backspace fixChar retype retype is easier than relocateCursor backspace relocateCursor. any analogies in data structuree manipulation notation?
as i look in programming language implementation documentation, there is a lot of defining operations and abstract machines by drawing a diagram of what's on the stack, what's in memory, and what's in registers before the operation and after the operation. e.g. DUP might be written "a -> a a" (which is assumed to mean "a ... -> a a ..."; POP might be written:
op before: stack acc after: stack acc POP x ... ... -> ... x
An alternative might be to use slice notation, but that requires more explanation and more characters per operation: pop: acc = stack[0]; stack = stack[1:]
it seems like reading these 'what the stack, accumulator, etc look like' diagrams is just a matter of doing a destructuring bind and assignment in your head. Should Oot support a syntax for coding using these sorts of diagrams?
" As for looking upwards being inconvenient and inefficient, this would only be true if you've done a poor job of designing your AST data structure. If each AST node has a pointer to its parent node, this will be extremely efficient, and trivial to develop. "
" In the other case, we're taking an AST as input, and perhaps a different AST as output. Here, the situation is not nearly as clear. The mapping from one AST structure to another is quite complex (see XSLT, TXL, or TreeDL? for example), and a single BNF-like grammar doesn't capture it. "
---
i decided to quickly skim the question of whether making Oot suitable for genetic programming would lead to any cool ideas of important constraints.
a quick read of http://en.wikipedia.org/wiki/Genetic_programming and a skim of notes from Koza's class at http://www.genetic-programming.com/coursemainpage.html lead me to believe:
so far i haven't seen any demand for interesting language features or constraints that would push Oot one way or another.
one interesting tidbit; at least one genetic programming project used directed labeled graphs as its memory representation:
EVOLUTION OF MENTAL MODELS FOR A PATH-PLANNING TASK (BRAVE 1995, 1996) see last few slides at http://www.genetic-programming.com/c2003memory.pdf
after one more skim of Google:
http://geneticprogramming.us/Representation.html suggests a functional language, as opposed to imperative, defined as " Imperative programming languages, the ones most of us are more familiar with like Java and C have some computer state with variables and values and the various commands alter the computer's state. In functional programs, the idea is to take some input and simply return a value without dealing with computer state. You can think of functional programming more like mathematical expressions than instructions for somebody to follow." (the authors wrote Darwin GP which works in OCaml)
http://faculty.hampshire.edu/lspector/push3-description.html is one proposed language
http://www.macs.hw.ac.uk/~ml355/common/thesis/c6.html looks like a great read, todo
http://www.cs.rit.edu/~jmg/courses/ga/20071/slides/4-1-gp.pdf Genetic Mapping slides implicitly suggests that it might be good to have a way for the language to skip syntax errors rather than crashing when being used in GP
Genetic Algorithms and Genetic Programming: Modern Concepts and Practical ... By Michael Affenzeller, Stefan Wagner, Stephan Winkler, Andreas Beham notes the following:
these slides also make the point that instead of working on the AST directly, the genotype could specify a sequence of grammatical operations that write the program, thereby avoiding syntactic errors. http://www.macs.hw.ac.uk/~ml355/common/thesis/c6.html also mentions this and calls it "grammatical evolution" and cites [Ryan et al., 1998];
2.2.1 Hierarchical labeled structure trees
(ASTs)
note: a big deal is made of the terminology "function set" and "terminal set"; "function set" is just constructs that are interior nodes of the AST and "terminal set" is just constructs that are leaves of the AST
2.2.2 automatically defined functions and modular genetic programming
cites "genetic programming II: automatic discovery of reusable programs' Koz94 for the initial inspiration, and also extensions in KIAK99 (Koza et al Genetic Programming III), KKS+03b (Koza et al Genetic Programming IV), and also two techniques for automatical extraction of subroutines into libraries, genetic libraries (Angeline in Ang93 and Ang94) and adaptive representation through learning (ARL) (Rosca in Ros95a and RB96 (Rosca and Ballard, Discovery of subroutines in genetic programming, in Angeline and Kinnear, ???). Also cites "other advanced GP concepts" in this area in Gru94, KBAK99 (Koza et al, the design of analog circuits by means of genetic programming, in Bentley, Evolutionary design by computers, chaper 16), Jac99 (C. Jacob, Lindenmayer systems and growth program evolution, in Hussain, Advanced Grammar Techniques within Genetic Programming and Evolutionary Computation), WC99 (Whigham and Crapper, Time Series Modeling using Genetic Programming).
2.2.3.1 linear genetic programming
a sequence of imperative instructions. can be stack-based or register-based.
2.2.3.2 graphical genetic programming
looks like dataflow, not 100% clear though.
cites Parallel Distributed Genetic Programming (PDGP), Pol97, Pol99b (R. Poli, Parallel Distributed Genetic Programming. In Come, Dorigo, Glover, New Ideas in Optimization, Advanced topics in computer science, chapter 27)
pretty amazing that someone is even working on this: Automatic Quantum Computer Programming A Genetic Programming Approach http://faculty.hampshire.edu/lspector/aqcp/
6.5.1 Linguistic Approaches of http://www.macs.hw.ac.uk/~ml355/common/thesis/c6.html also talks about:
section 6.5.2 Representational Approaches of http://www.macs.hw.ac.uk/~ml355/common/thesis/c6.html also talks about:
www.cs.utsa.edu/~bylander/pubs/AppliedSoftComputing?