meisl / lambda Goto Github PK

• [AbSu96] Harold Abelson and Gerald Jay Sussman. Structure and Interpretation of Computer Programs. MIT Press 1996 (2nd edition) [TODO: YouTube link, Amazon link, Homepage link?]
• [Hutt07] Graham Hutton. Programming in Haskell. Cambride University Press, 2007. [TODO: YouTube link, Amazon link]
• [Kri12] Shriram Krishnamurthi. Programming Languages: Application and
  Interpretation. Homepage [TODO: YouTube link, Amazon link]
• [HiSe08] J. Roger Hindley and Jonathon P. Seldin. Lambda-Calculus and Combinators - an Introduction. Cambridge University Press, 2008. [TODO: Amazon link]

• export a constant hash curryOptions replacing the current $STATS_ENABLED

Steps:

• implement sequential substitution, ie. instead of just taking one "term t for var x" arg accept a list of those Pairs (#29), to be applied one after the other, in the order they appear in the list (-> transitively). Use None (Maybe, #28) as a return value indicating no change and Some t' if the result is indeed a different term t'; in order to support maximal sharing.
• implement β-reduction in terms of sequential substitution, removing and/or adding particular substitutions to the list as required by certain binders of λs, or, resp., for doing necessary α-conversions. Again, use Maybe Term as return type for sharing.

Consider using bit-strings (List Bool) for the type/ctor-tag. This would require to re-do ADT List with at least three-way mutual recursion (-> #33), but has the benefit of greatly simplifying the task of adding more ctors to an ADT.
It'd also open up an easy way of adding support for (runtime) type tags as well: instead a flat List Bool we'd use a List (List Bool), one determining the runtime type, another determining the ctor used, ....
We might even provide the actual fields of the ADT instance in a List (rather than as top-level args), thus making the interface for both, predicates and projections completely uniform.

First main improvement should be to replace several nested ifs by a construct which adds only one level of nesting, independent of the nr of constructors ("ctors").

Secondly, it should improve efficiency in itself already, by reducing the nr of tests to constant 1 as opposed to linear in the nr of ctors of the ADT ("in itself already" meaning: prior to any further compiler optimizations).
The exact inner workings of this depend of course on which pattern is chosen for implementing ADT(-ctor)s in λ: do we have type/ctor tags or not? If so, how to encode them? If not (-> some form of callback convention), then who calls back whom, and maybe there's some indirection?.

Anyhow,

• at first: a rather simple "case"-construct, ie. a function which takes
  • i) an instance of the ADT
  • ii) for each constructor (with which the instance could possibly have been built), a callback fn which in turn would receive the respective fields of the instance. Note the problem of 0-arity ctors, as eg in data Bool = False | True: in such cases lazy evaluation is imperative - so to simulate that in Perl we'll pass a 0-arity Block to indicate that lazy evaluation is needed.
• then, real pattern matching, ie in addition to the above, and in any combination:
  • incomplete patterns (leaving out some cases/ctors), with an "otherwise" clause
  • nested patterns
  • matching against constants OR variables
  • overlapping patterns?
  • ...?

Rather than repeating by hand the same pattern over and over in each and every concrete ADT, we'd like to abstract from the actual λ-implementation of ADTs^1: given some representation of an ADT (abstract description of its ctors and for each of them, the fields and their types, see #7), provide all the standard fns (ctors, predicates, projections, case-construct, full-blown pattern-matching).
Making this separation will allow for two things:

• a) having different actual (λ-)implementations of ADTs^1, and compare them
• b) be able to easily change a particular ADT, ie add/remove/change a ctor, add/remove/change a field

This - hence all pts below - really are to approached from two sides:

• a) the Perl6 side, providing automation when doing things in Perl6: temporarily, as long as we don't have at least a λ evaluator
• b) the λ side, ie doing the automation actually in pure λ

So, given an ADT (representation), auto-generate:

• simple case-construct/fn (see #35)
• ctor-fns
• predicates (with which ctor was the ADT instance at hand made with)
• projections (extract a field from a particular ADT instance)
• full-blown pattern-matching (see #35)

[1] what, actually, are the fns doing which represent instances of the ADT at hand? Do we use tags to differentiate types / ctors? Or do we implement the ctors themselves as "selectors"? In case of tags, how do we encode the tags? etc...

mostly à la Scheme:

• till-end-of-line comments with ;
• comment-out-sexpr with ;( ... )
• multi-line comments with ???

To be done in the order given (within each branch):

branch 0 (most pressing)

• #42 'switch to NQP and add tests (in NQP!)'

branch 1 (make it self-hosting)

• #28 'add ADT Maybe (Church-encoded by hand, everything in λ, too)'
• #29 'add ADT Pair (Church-encoded by hand, everything in λ, too)'
• #32 'add Y combinator for (one-way) recursion'
• #9 'finish ADT List (Church-encoding by hand, everything in λ, too)'
• #10 'add ADT Term for syntax tree / AST entities (Church-encoded by hand)'
• #34 'use ADT Term alone to represent Terms' (branch "switch_to_lambda_repres")
• #41 'add ADT Either'
• #12 'most simple impl of β-red. avoiding accidental capture (in Perl6 only, efficiency is of NO importance)'
  • implement sequential substitution, ie. instead of just taking one "term t for var x" arg accept a list of those Pairs (#29), to be applied one after the other, in the order they appear in the list (-> transitively). Use None (Maybe, #28) as a return value indicating no change and Some t' if the result is indeed a different term t'; in order to support maximal sharing.
  • implement β-reduction in terms of sequential substitution, removing and/or adding particular substitutions to the list as required by certain binders of λs, or, resp., for doing necessary α-conversions. Again, use Maybe Term as return type for sharing.
• #25 'augment syntax tree nodes with src location info'
• #11 'implement β/η-red. and α-conv using ADT Term (simple but correct)'
• #13 'refine β/η-red. and α-conv using ADT Term: clever & efficient & flexible!'
• ...
• #33 'add Y_2, Y_3, ...Y_n fixed-point combinators for multi-way mutual recursion' [TODO: maybe this belongs somewhere else?]
• #19 'make a functional parser (like the parser combinators in [Hutt07])'
• ...
• #23 'make an interpreter using stacked environments' (rather than stupid subst)
• #24 'implement proper tail calls'
• #27 'compile to QAST, using the NQP toolchain'

branch 2 (make it do something)

• #40 'add facility to switch on/off stats for P6Currying'
• #22 'add comments to syntax'
• #38 'add integer literals to syntax'
• #30 'add string literals to the grammar, plus a (native) comparison for equality'
  • syntax
  • comparison for equality
• #37 'λ-like function application in Perl6 (auto-currying & "over-application")':
  • partial application simply by providing fewer arguments (yielding another applicable thing)
  • "over-applying": since every application in λ yields something that can be applied again (except for constants and fns that return constants): providing more than the nomimal nr of args should simply apply the rest-args to the result of the first fn application
  • do it via a role (rather than via an extra class)
  • maybe use Perl6's wrap mechanism (trickier!; and only works with Routines, not Blocks)
  • do it efficiently, ie using as few indirections and as much compile-time binding and type-checking as possible. -> overload/override multi postcircumfix:<( )> (...) with appropriate signatures (nest actual sig in extra parens ( and ), since we'll be passed a capture); avoid introducing extra "internal" methods like "apply" etc.
• #2 'add most simple symbol-lookup using "δ"'
• #3 'add hygienic macros using "µ"'
• #4 'add "if" as a macro'
• #14 'add "cond" (aka "switch") as a macro'
• #5 'add "let" as a macro'
• #6 'add "def"/"define" as a macro, to allow recursive definitions (and maybe local ones)'
• #7 'add a data-type mechanism, desugaring to a Church-encoding'
  • Consider using bit-strings (List Bool) for the type/ctor-tag. This would require to re-do ADT List with at least three-way mutual recursion (-> #33), but has the benefit of greatly simplifying the task of adding more ctors to an ADT.
    It'd also open up an easy way of adding support for (runtime) type tags as well: instead a flat List Bool we'd use a List (List Bool), one determining the runtime type, another determining the ctor used, ....
    We might even provide the actual fields of the ADT instance in a List (rather than as top-level args), thus making the interface for both, predicates and projections completely uniform.
• #35 'add pattern matching (improve "nesting" & perf)
  • at first: a rather simple "case"-construct, ie. a function which takes
    • i) an instance of the ADT
    • ii) for each constructor (with which the instance could possibly have been built), a callback fn which in turn would receive the respective fields of the instance. Note the problem of 0-arity ctors, as eg in data Bool = False | True: in such cases lazy evaluation is imperative - so to simulate that in Perl we'll pass a 0-arity Block to indicate that lazy evaluation is needed.
  • then, real pattern matching, ie in addition to the above, and in any combination:
    • incomplete patterns (leaving out some cases/ctors), with an "otherwise" clause
    • nested patterns
    • matching against constants OR variables
    • overlapping patterns?
    • ...?
• #36 'Given an ADT (representation), auto-generate (two sides: Perl6 & in pure λ):'
  • simple case-construct/fn (see #35)
  • ctor-fns
  • predicates (with which ctor was the ADT instance at hand made with)
  • projections (extract a field from a particular ADT instance)
  • full-blown pattern-matching (see #35)

...

• #17 'add Types (eventually...)' - oh...

Unrelated (any order):

branch 3

• #8 'put all the missing refs into README'
• #15 'make a REPL': unclear when exactly it makes sense - but the sooner the better (can always refine it)
• #26 'add suggestive REPL examples to README, probably involving Y and fact'
• #16 'add β-/η-reduction and α-conversion to Lamda-Intro.md'
• #18 'continue docs explaining how to detect & avoid accidental capture during β-red.'
• #20 'add bibliography'
• #21 'mention Pierce's TAPL'
• #31 'write tutorial on Y combinator, including ones for multi-way mutual recursion'

...rather than stupid substitution/rewriting

• clever: α-convert only what's necessary
• efficient: do substitution and (the clever!) α-conversion in parallel (meaning detection of nodes that need α-conversion in parallel, too!), thus requiring exactly ONE traversal
• flexible: try to not bake in an actual strategy (normal, applicative, "by value", "by name", "by need", lazy...). At best, this should be parameterizable, for experiments.

see #31

A simple, not-too-clever expansion (either of source text, in the syntax tree or the AST).
This is meant just to make slightly more complicated constructions actually feasible, ie not have you get lost in unmatched parentheses / trying to figure out what gets bound to which.

Requirements:

• enable having the symbol being defined ("definiendum") and the definition's body ("definiens") right next to each other in the source (!)
• warn/error if there are unbound symbols in the definiens (ie: not allow recursive definitions)
• not require evaluation with stacked environments, ie still support a simple substitution model
• not complicate the syntax of pure λ any more than by special treatment of the symbol δ in function position of an application
• build on the existing syntax tree structure, ie not introduce "special" nodes

[Note: the following requirements have been dropped:

• disallow redefinition (definiendum/definient already bound)
• (probably) allow only top-level definitions
  ]

This will require ADT Term (#10) to support more fields (more than just the two for AppT and LamT)
...well, depends on how ADT's are actually implemented (now we're at a Church encoding)

If used for syntax nodes as well (as opposed to only for _abstract_ stx nodes), then we'll most probably need more than 4 constructors, thus requiring more than 2 "tag" bits in the Church encoding.

Make applying a Perl6 function feel like applying it in λ:

• partial application simply by providing fewer arguments (yielding another applicable thing)
• "over-applying": since every application in λ yields something that can be applied again (except for constants and fns that return constants): providing more than the nomimal nr of args should simply apply the rest-args to the result of the first fn application
• do it via a role (rather than via an extra class)
• maybe use Perl6's wrap mechanism (trickier!; and only works with Routines, not Blocks)
• do it efficiently, ie using as few indirections and as much compile-time binding and type-checking as possible. -> overload/override multi invoke (...) with appropriate signatures (nest actual sig in extra parens ( and ), since we'll be passed a capture); avoid introducing extra "internal" methods like "apply" etc.

Note: this of course excludes the following Perl6 features:

• a) optional params
• b) named params
• c) slurpy params
• d) capture params
• e) parcel params

requires #2, and probably a List ADT

oh...

done in 0883bbd

yes, by inserting thunks for consequence and alternative

REPL = "Read" - "Eval" - "Print" - "Loop"

• string literal syntax:
  • use " (double-quotes) to indicate start and end
  • use \ (back-slash) for escape inside two "s:
    • \" for a " character
    • \\ for a \ character
    • \n for a newline character (0xA)
    • \r for a carriage-return (0xD)
    • \t for a tab character (0x9)
    • maybe also \b and \f
• comparison for equality:
  • ???