## lambdacode-form.api
#
# As compilation proceeds, the program being compiled is tranformed
# into a sequence of representations. In the front end, these representations
# are primarily syntactic. In the backend tophalf they are machine-independent
# intermediate languages. In the backend lowhalf they are machine-dependent.
#
# In this file we define the first of the representations used in the
# backend tophalf (machine-independent optimizer). This representation
# is essentially typed polymorphic lambda calculus.
#
# The Mythryl compiler backend upper half is derived from the Yale
# FLINT Project, which has home page:
#
# http://flint.cs.yale.edu/flint/
#
# In particular see Zhong Shao's PhD thesis:
#
# Compiling Standard ML for Efficient Execution on Modern Machines
# http://flint.cs.yale.edu/flint/publications/zsh-thesis.html
#
# More recent useful background may be found in Stefan Monnier's
# http://www.iro.umontreal.ca/~monnier/
# 2003 PhD Thesis "Principled Compilation and Scavenging"
# http://www.iro.umontreal.ca/~monnier/master.ps.gz
#
# Translation into this form from deep syntax is done in
#
# src/lib/compiler/back/top/translate/translate-deep-syntax-to-lambdacode.pkg#
#
# Compiled by:
# src/lib/compiler/core.sublib### "I went to my first computer conference at the New York Hilton
### about 20 years ago. When somebody there predicted the market
### for microprocessors would eventually be in the millions,
### someone else said, "Where are they all going to go? It's not
### like you need a computer in every doorknob!"
###
### "Years later, I went back to the same hotel. I noticed the room
### keys had been replaced by electronic cards you slide into slots
### in the doors.
###
### "There was a computer in every doorknob."
###
### -- Danny Hillis
# NB: "lambdacode" is a form of polymorphically typed lambda calculus.
#
### "Combinatory play seems to
### be the essential feature
### in productive thought."
###
### -- Albert Einstein
stipulate
package hcf = highcode_form; # highcode_form is from src/lib/compiler/back/top/highcode/highcode-form.pkg package hbo = highcode_baseops; # highcode_baseops is from src/lib/compiler/back/top/highcode/highcode-baseops.pkg package tmp = highcode_codetemp; # highcode_codetemp is from src/lib/compiler/back/top/highcode/highcode-codetemp.pkg package hut = highcode_uniq_types; # highcode_uniq_types is from src/lib/compiler/back/top/highcode/highcode-uniq-types.pkg package sy = symbol; # symbol is from src/lib/compiler/front/basics/map/symbol.pkg package vh = varhome; # varhome is from src/lib/compiler/front/typer-stuff/basics/varhome.pkgherein
# This api is implemented in:
#
# src/lib/compiler/back/top/lambdacode/lambdacode-form.pkg #
api Lambdacode_Form {
#
# The following types are defined and documented
# starting on page 52 of Zhong Shao's PhD thesis:
# http://flint.cs.yale.edu/flint/publications/zsh-thesis.html
# (Obviously, the code has evolved a lot since then...)
# Constructor records the name of the constructor,
# the corresponding Valcon_Form,
# and the lambda type hut::Uniqtypoid.
# Value carrying data constructors have arrow type.
#
Constructor
=
( sy::Symbol,
vh::Valcon_Form,
hut::Uniqtypoid
);
# A casetag is anything which can be a,b,c in:
#
# case x
# a => ... ;
# b => ... ;
# c => ... ;
# esac;
#
# Used to specify all possible switching statements.
#
# Efficient switch generation can be applied to Valcon and INTcon.
#
# Otherwise, it is just a shorthand for binary branch trees.
#
# In the future, we probably should make it more general,
# including constants of any numerical type. XXX SUCKO FIXME
#
Casetag # Constant in a 'case' rule lefthandside.
#
= VAL_CASETAG (Constructor, List(hut::Uniqtype), tmp::Codetemp)
| INT_CASETAG Int
| INT1_CASETAG one_word_int::Int
| INTEGER_CASETAG multiword_int::Int # Only used with in matchcomp.
| UNT_CASETAG Unt
| UNT1_CASETAG one_word_unt::Unt
| FLOAT64_CASETAG String
| STRING_CASETAG String
| VLEN_CASETAG Int
;
# lambda_expression: The universal typed intermediate language.
#
# TYPEFUN, APPLY_TYPEFUN are abstraction and application on type constructors.
#
# package abstractions and generic abstractions are
# represented as normal package and generic definitions
# with its component properly PACKed.
#
# FN defines normal functions.
# MUTUALLY_RECURSIVE_FNS defines a set of recursive functions.
# LET (v, e1, e2) is syntactic sugar for exprs like APPLY (FN (v, _, e2), e1);
# the type of v will be that of e1.
# APPLY is function application.
# STRECD and STRSEL are package record selection.
# VECTOR and VCTSEL are vector record and vector selection.
# EXCEPTION_TAG, RAISE, and EXCEPT are for exceptions.
#
# For (dated) background discussion see p39 of http://flint.cs.yale.edu/flint/publications/zsh-thesis.pdf
#
Lambdacode_Expression
#
= VAR tmp::Codetemp
| INT Int
| INT1 one_word_int::Int
| UNT Unt
| UNT1 one_word_unt::Unt
| FLOAT64 String
| STRING String
| FN # Function definition -- "Lambda abstraction".
( tmp::Codetemp, # Argument
hut::Uniqtypoid, # Argument type
Lambdacode_Expression # Function body.
)
| MUTUALLY_RECURSIVE_FNS
( List( tmp::Codetemp ), # The function names.
List( hut::Uniqtypoid ), # The function types.
List( Lambdacode_Expression ), # The function definitions.
Lambdacode_Expression # ?
)
| APPLY
( Lambdacode_Expression, # Function.
Lambdacode_Expression # Argument.
)
| LET
( tmp::Codetemp, # Let this variable
Lambdacode_Expression, # have this value
Lambdacode_Expression # during evaluation of this expression.
)
| TYPEFUN (List(hut::Uniqkind), Lambdacode_Expression)
| APPLY_TYPEFUN (Lambdacode_Expression, List(hut::Uniqtype))
| RAISE (Lambdacode_Expression, hut::Uniqtypoid)
| EXCEPT (Lambdacode_Expression, Lambdacode_Expression)
| EXCEPTION_TAG (Lambdacode_Expression, hut::Uniqtypoid)
| CONSTRUCTOR (Constructor, List(hut::Uniqtype), Lambdacode_Expression)
| SWITCH ( Lambdacode_Expression, # SWITCH represents table-lookup; used to implement the dense part of case statements with int key values.
vh::Valcon_Signature,
List( (Casetag, Lambdacode_Expression) ),
Null_Or(Lambdacode_Expression)
)
| VECTOR (List(Lambdacode_Expression), hut::Uniqtype) # Translates ds::VECTOR_IN_EXPRESSION
| RECORD List(Lambdacode_Expression) # Translates ds::RECORD_IN_EXPRESSION
| PACKAGE_RECORD List(Lambdacode_Expression) # Translates ds::PACKAGE_DEFINITION
| GET_FIELD (Int, Lambdacode_Expression) # Translates ds::RECORD_SELECTOR_EXPRESSION -- i.e., record.field.
| BASEOP # BASEOP is used for stuff like int addition which we absolutely want inlined in the final native code.
(
hbo::Baseop, # Operation -- 'add' or 'shift' or boolean 'not' or fetch-from-vector or whatever.
hut::Uniqtypoid, # Result type.
List( hut::Uniqtype ) # Argument types.
)
# "PACK is not currently supported" -- src/lib/compiler/back/top/lambdacode/translate-lambdacode-to-anormcode.pkg # This one is NEVER USED, unless you count src/lib/compiler/back/top/lambdacode/prettyprint-lambdacode-expression.pkg # It may be related to the 'pack' that shows up in some SML-semantics theory papers, which is also a complete mystery to me.
| PACK ( hut::Uniqtypoid,
List(hut::Uniqtype),
List(hut::Uniqtype),
Lambdacode_Expression
)
# The following two are NEVER USED, unless you count src/lib/compiler/back/top/lambdacode/prettyprint-lambdacode-expression.pkg # They may have been obseleted by hbo::IS_BOXED and hbo::IS_UNBOXED..?
#
| BOX # Wrap given expression with given type into exactly one word.
( hut::Uniqtype, # Type
Bool, # ?
Lambdacode_Expression # Expression
)
| UNBOX # Given wrapped expression of given type, unwrap into natural unboxed representation.
( hut::Uniqtype, # Type.
Bool, #
Lambdacode_Expression # Expression
)
| GENOP
(
Dictionary,
hbo::Baseop,
hut::Uniqtypoid,
List( hut::Uniqtype )
)
# "GENOP" may be "generic op" here.
#
# 'Dictionary' contains a list of (type, make_foo) pairs
# plus a default make_foo \\; the idea is evidently to
# delay selecting the actual make_foo until the relevant
# type is known and/or finalized.
#
# This gets used to translate hbo::MAKE_NONEMPTY_RW_VECTOR_MACRO in fun translate_variable_in_expression in src/lib/compiler/back/top/translate/translate-deep-syntax-to-lambdacode.pkg # That may be its only use. (?)
withtype # Used only in GENOP, above.
Dictionary
=
{ default: Lambdacode_Expression,
#
table: List( (List(hut::Uniqtype), Lambdacode_Expression) )
};
};
end;
## COPYRIGHT (c) 1997 YALE FLINT PROJECT
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.